小编Jus*_*tin的帖子

我试图了解HAMT的细节.我已经用Java实现了一个只是为了理解.我熟悉Tries,我认为我得到了HAMT的主要概念.

基本上,

两种类型的节点:

核心价值

Key Value Node:
  K key
  V value

指数

Index Node:
  int bitmap (32 bits)
  Node[] table (max length of 32)

1. 为对象生成32位哈希.
2. 一次遍历5位哈希.(0-4, 5-9, 10-14, 15-19, 20-24, 25-29, 30-31) 注意:最后一步(第7步)只有2位.
3. 在每个步骤中,找到位图中该5位整数的位置.例如integer==5 bitmap==00001
   1. 如果该位为1,则存在该部分哈希.
   2. 如果该位为0,则密钥不存在.
4. 如果密钥存在,通过计算位图中0和位置之间的1的数量,找到它在表中的索引.例如integer==6 bitmap==0101010101 index==3
   1. 如果表指向键/值节点,则比较键.
   2. 如果表指向索引节点,则转到2向前移动一步.

我不太了解的部分是碰撞检测和缓解.在链接的论文中,他提到了:

然后将现有密钥插入新的子哈希表中并添加新密钥.每次使用5个比特的散列时,碰撞的概率减少1/32.有时可能会消耗整个32位散列,并且必须计算新的散列以区分这两个密钥.

如果我要计算一个"新"哈希并将该对象存储在该新哈希中; 你怎么能够在结构中查找对象？在进行查找时,它不会生成"初始"哈希而不是"重新计算的哈希".

我肯定错过了什么.....

BTW:HAMT表现相当不错,它在我的测试中位于哈希映射和树图之间.

Data Structure                    Add time   Remove time     Sorted add time Sorted remove time   Lookup time     Size     
Java's Hash Map                   38.67 ms   18 ms           30 ms           15 …

我有这样的路径列表

/mnt/sdcard/folder1/a/b/file1
/mnt/sdcard/folder1/a/b/file2
/mnt/sdcard/folder1/a/b/file3
/mnt/sdcard/folder1/a/b/file4
/mnt/sdcard/folder1/a/b/file5
/mnt/sdcard/folder1/e/c/file6
/mnt/sdcard/folder2/d/file7
/mnt/sdcard/folder2/d/file8
/mnt/sdcard/file9

因此,从这个路径列表(Stings)我需要创建一个Java Tree结构,其中包含文件夹作为节点,文件作为leaf(不会将空文件夹作为叶子).

我需要的是我想的是add方法,我向它们传递一个String(文件的路径),然后将它添加到树中的正确位置,如果它们不在那里,则创建正确的节点(Folder)

当我在节点和叶子列表上时,这个树结构将需要我获取节点列表(但我认为这将是树的常规功能)

我总是将字符串作为路径而不是真正的文件或文件夹.是否有可以使用的东西或源代码开始？

非常感谢你.

问题是,如何解决1/x + 1/y = 1/N!(N阶乘).找出大N值满足x和y的值的数量.

我已经解决了相对较小的N值(任何N!都适合长)的问题.所以,我知道我通过获得(N!)^ 2的所有除数来解决问题.但是当(N!)^ 2无法适应长时间时,开始失败.我也知道我可以找到N的所有除数!通过将N中每个数字的所有素因子相加起来!我缺少的是如何使用factorial中的所有数字来查找x和y值.

编辑:不寻找"答案"只是一两个提示.

我难以从托管在code.google上的SVN存储库切换到github上的git repo.特别:

1. 如何在保留修订历史记录的同时将code.google上的代码从SVN更改为GIT？
2. 如何在保留修订历史记录的同时将code.google上的wiki从SVN更改为GIT？
3. 如何将我的GIT存储库从code.google移动到GitHub？
4. 如何使两个存储库保持同步,同时仍然使用GitHub作为主要存储库？

我有一个管道分隔文件,我解析它以获取系统选项.环境对堆分配很敏感,我们正在尝试避免垃圾回收.

下面是我用来解析管道分隔字符串的代码.该函数调用约35000次.我想知道是否有更好的方法不能创造更多的内存流失.

static int countFields(String s) {
    int n = 1;
    for (int i = 0; i < s.length(); i++)
        if (s.charAt(i) == '|')
            n++;

    return n;
}

static String[] splitFields(String s) {
    String[] l = new String[countFields(s)];

    for (int pos = 0, i = 0; i < l.length; i++) {
        int end = s.indexOf('|', pos);
        if (end == -1)
            end = s.length();
        l[i] = s.substring(pos, end);
        pos = end + 1;
    }

    return l;
}

编辑1,关于java版本:

出于商业原因,我们坚持使用JDK 1.6.0_25.

编辑2关于String和String …

我有一些从Java到C++的代码

// since this point is a vector from (0,0,0), we can just take the
// dot product and compare
double r = point.dot(normal);
return (r>=0.0);

但是在C++ r中可以是+0.0或者-0.0,当r等于-0.0它时,检查失败了.

我试图在下面的代码中调整负零,但它从未达到DEBUG("负零")线.但r2打印出来的等于+0.0.

// since this point is a vector from (0,0,0), we can just take the
// dot product and compare
double r = point.dot(normal);
if (std::signbit(r)){
    double r2 = r*-1;
    DEBUG("r=%f r=%f", r,r2);
    if (r2==0.0) {
        DEBUG("Negative zero");
        r …

我正在查看KD树最近邻搜索的维基百科页面.

维基百科中给出的伪代码在点为2-D(x,y)时起作用.

我想知道,当点是3-D(x,y,z)时,我应该做出什么改变.

我google了很多,甚至在堆栈溢出中经历了类似的问题链接,但我没有找到任何地方的3-d实现,所有以前的问题都需要2-D点作为输入,而不是我的3-D点寻找.

用于构建KD树的Wiki中的伪代码是::

function kdtree (list of points pointList, int depth)
{
    // Select axis based on depth so that axis cycles through all valid values
    var int axis := depth mod k;

    // Sort point list and choose median as pivot element
    select median by axis from pointList;

    // Create node and construct subtrees
    var tree_node node;
    node.location := median;
    node.leftChild := kdtree(points in pointList before median, depth+1);
    node.rightChild := kdtree(points in pointList after median, …