小编Jac*_*ale的帖子

我正在学习Jason Hickey的Objective Caml简介.

这是一个我没有任何线索的练习

首先,这是什么意思实现dictionary的function？我该如何成像呢？

我们需要任何array类似的东西吗？显然,我们不能在这个练习中使用数组,因为array尚未介绍过Chapter 3.但How do I do it without some storage?

所以我不知道该怎么做,我希望得到一些提示和指导.

stringOCaml中的类型是否支持utf8？

或者我应该为utf8字符串使用什么库？

我见过很多地方说quicksort是好的,因为它适合缓存相关的东西,比如维基说

此外,quicksort的顺序和本地化内存引用可以很好地与缓存配合使用

http://en.wikipedia.org/wiki/Quicksort

谁能给我一些关于这个说法的见解？quicksort如何与缓存相关？通常意味着语句中的缓存是什么意思？为什么quicksort更适合缓存？

谢谢

这不是我学校的家庭作业.这是我自己的家庭作业,我是自学算法.

在算法设计手册中,有这样的消费税

4-25假设数组A [1..n]只有{1,...的数字...,n ^ 2}但是这些数字的最多日志log n出现了.设计一种算法,将A排序在一个基本上小于O(n log n)的范围内.

我有两种方法:

第一种方法:

基本上我想对这个问题进行计数.我可以先扫描整个数组(O(N))并将所有不同的数字放入loglogN大小数组(int [] K).

然后应用计数排序.但是,在设置计数数组(int [] C)时,我不需要将其大小设置为N ^ 2,而是将大小设置为loglogN.

但是这样,当计算每个不同数字的频率时,我必须扫描数组K以获得该元素的索引(O(NloglogN),然后更新数组C.

第二种方法:

同样,我必须扫描整个数组以获得具有大小loglogN的不同数字数组K.

然后我只是做了一种类似的快速排序,但是分区是基于K数组的中位数(即,每次转轴是K数组的一个元素),递归地.

我认为这种方法最好用O(NlogloglogN).

我对吗？还是有更好的解决方案？

算法设计手册中存在类似的消息,例如

4-22显示1到k范围内的n个正整数可以在O(n log k)时间内排序.有趣的情况是k << n.

4-23我们寻求对具有许多重复的n个整数的序列S进行排序,使得S中不同整数的数量为O(log n).给出O(n log log n)最坏情况时间算法来对这些序列进行排序.

但基本上对于所有这些消除,我的直觉总是考虑计数排序,因为我们可以知道元素的范围,并且范围与整个数组的长度相比足够短.但是经过更深入的思考,我猜这些消费者正在寻找的是第二种方法,对吧？

谢谢

好的,我是一名没有任何函数编程知识的Java程序员.

现在我已经学习了OCaml 2周,而且我甚至都不知道OCaml.

这里有几个教程和书籍:

/sf/ask/145140551/

但他们似乎都不友好.真的,我的意思是.

这些教程或书籍都没有给我一个Hello World快速入门.两周后,我甚至不知道program entranceOcaml 是什么(如a main()).

我甚至不知道如何将OCaml代码真正写入文件,并以某种方式让OCaml编译它.

好的,投诉已经完成.

我必须学习并做得好.那么,请你给我一些学习的建议吗？我觉得OCaml非常默默无闻,很难理解.请指教我的道路.

我们来定义eleven-non-free数字:

如果我们将数字视为一个字符串,那么如果内部的任何子字符串是(非零)幂11,则该数字是一个eleven-non-free数字.

例如,内部是1123一个eleven-non-free数字.同样是一个为是.但事实并非如此,因为我们无法找到任何内部的非零力量.1111^11215412111^21234511

所以给定ak,找到第k个eleven-non-free数字.例如,第13个这样的数字是211.

我不知道如何有效地做到这一点.蛮力的方法是将i从1增加并检查每个数字和计数直到第k个.

我想我们应该考虑不同长度的字符串(1,2,3,4,...).然后对于每个长度,我们尝试填写11,11 ^ 2,11 ^ 3等,并尝试获得所有组合.

但它似乎也很复杂.

任何人？

这是图表的消费税.

给定具有n个顶点和m个边的无向图G和整数k,给出O(m + n)算法,该算法找到G的最大诱导子图H,使得H中的每个顶点具有度≥k,或证明不这样的图存在.图G =(V,E)的诱导子图F =(U,R)是G的顶点V的U的子集,以及G的所有边R,使得每个边的两个顶点都是U.

我最初的想法是这样的:

首先,这个消息实际上要求我们拥有度数大于或等于k的所有顶点S,然后我们删除S中没有任何边连接到其他边的顶点.然后精化的S是H,其中所有顶点都具有度> = k并且它们之间的边是R.

另外,它问O(m + n),所以我认为我需要一个BFS或DFS.然后我卡住了.

在BFS中,我可以知道顶点的程度.但是一旦我得到v(一个顶点)的程度,我不知道除了它的父之外的其他连接顶点.但如果父母没有度> = k,我就无法消除v,因为它可能仍然与其他人联系.

任何提示？

编辑:

根据@Michael J. Barber的回答,我实现了它并在这里更新代码:

任何人都可以看看代码的关键方法public Graph kCore(Graph g, int k)吗？我做得对吗？是O(m + n)？

class EdgeNode {
   EdgeNode next;
   int y;
}

public class Graph {
   public EdgeNode[] edges;
   public int numVertices;

   public boolean directed;

   public Graph(int _numVertices, boolean _directed) {
      numVertices = _numVertices;
      directed = _directed;
      edges = new EdgeNode[numVertices];
   }

   public void insertEdge(int x, int y) {
      insertEdge(x, y, directed);
   } …

好的,我发布了这个问题,因为这个练习:

我们可以修改Dijkstra算法,通过将最小值改为最大值来解决单源最长路径问题吗？如果是这样,那么证明你的算法正确.如果没有,那么提供一个反例.

对于本练习或与Dijkstra算法相关的所有事情,我假设图中没有负权重.否则,它没有多大意义,因为即使对于最短路径问题,如果存在负边缘,Dijkstra也无法正常工作.

好吧,我的直觉为我解答了:

是的,我认为可以修改.

我只是

1. 将距离数组初始化为MININT
2. 改变distance[w] > distance[v]+weight以distance[w] < distance[v]+weight

然后我做了一些研究来验证我的答案.我发现这篇文章:

从源到DAG中某些节点之间的最长路径

首先,我认为我的答案是错误的,因为上面的帖子.但我发现上面帖子中的答案可能是错误的.它将单源最长路径问题与最长路径问题混淆.

同样在Bellman-Ford算法的 wiki中,它正确地说:

Bellman-Ford算法在加权有向图中计算单源最短路径.对于仅具有非负边缘权重的图形,更快的Dijkstra算法也解决了这个问题.因此,Bellman-Ford主要用于具有负边缘权重的图形.

所以我认为我的答案是对的,对吧？Dijkstra真的可以成为单源最长路径问题,我的修改也是正确的,对吧？

我之前问过一个相关的问题为什么OCaml的线程被认为是"不够"？

无论ocaml的线程有多"糟糕",我都注意到一些图书馆说他们可以做真正的线程化.

例如,Lwt

Lwt提供了一种新的替代方案.它提供了非常轻量级的协作线程; "启动"一个线程是一个非常快速的操作,它不需要新的堆栈,新的进程或其他任何东西.此外,上下文切换非常快.事实上,我们将为每个系统调用启动一个线程非常容易.组成协作线程将允许我们编写高度异步的程序.

另外Jane Street的aync_core也提供了类似的事情,如果我是对的.

但我很困惑.做Lwt或aync_core提供线程Java threading？

如果我使用它们,我可以使用多个CPU吗？

以什么方式,我可以在OCaml中获得"真正的线程"(就像在Java中一样)？

编辑

我还是很困惑.

让我添加一个场景:

我有一个server(16 cpu cores)和一个服务器应用程序.

服务器应用程序的作用是:

• 它会听取请求
• 对于每个请求,它启动一个计算任务(假设花费2分钟完成)
• 当每个任务完成时,任务将把结果返回给main,或者直接将结果发送回客户端

在Java中,它非常简单.我创建了一个线程池,然后对于每个请求,我在该池中创建一个线程.该线程将运行计算任务.这在Java中很成熟,它可以使用16个cpu内核.我对吗？

所以我的问题是:我可以在OCaml中做同样的事情吗？

在OCaml中,我可以Printf.printf用来输出格式化的字符串,比如

Printf.printf "Hello %s %d\n" world 123

但是,printf是一种输出.

我希望的不是输出,而是字符串.例如,我想要

let s = something "Hello %s %d\n" "world" 123

然后我可以得到 s = "Hello World 123"

我怎样才能做到这一点？