1

我正在尝试为正整数（数百万个元素）的排序列表找到最佳数据结构。要求是（按重要性排序）：

  1. 内存占用小

  2. 快速O(log n)搜索

  3. 插入/删除速度比memcpy()

我正在考虑保留两个数组：一个用于搜索，一个用于插入。每隔几个操作，我都会重新组织主要的操作并清理第二个操作。有什么想法吗？我在正确的轨道上吗？

附言。没有重复项。它不需要是线程安全的。读取会经常发生，而写入很少发生。整数在结构中的分布不均匀，这意味着一些结构将只包含几个元素，而其他结构可能有数百万个元素，位置从零到0xFFFFFFFF.

4

7 回答 7

2

我想你想用Van Emde Boas Tree

它具有以下特点： 

Space   O(M)
Search  O(log log M)
Insert  O(log log M)
Delete  O(log log M)
于 2012-07-02T18:27:39.750 回答
1

你能用char[65536][]吗？其中顶部或底部 16 位是其他 16 位数组的索引。这可以使用少于 4 * X 每个条目。

抬头

 private final char[][] bitsArray = new char[65536][];

 public int countFor(int num) {
     int topBits = num >>> 16;
     int lowerBits = num & 0xFFFF;
     char[] lowerBitsArray = bitsArray[topBits];
     int count = 0;
     for(char l : lowerBitsArray)
        if(l == lowerBits)
           count++;
     return count;
 }

如果计数永远不会超过 1，那么 BitSet 可能是更好的选择。（可能是一组 BitSet，具体取决于数据模式）例如，如果您要记录看到的 IP 地址，您可能不需要担心 0. 、 10.、 127.* 或 224-255.*

an int[]orchar[]访问速度是否更快，包括转换为 int。

public static void main(String... args) {
    char[] chars = new char[1000000];
    for (int i = 0; i < 5; i++)
        timeSum(chars);
    int[] ints = new int[1000000];
    for (int i = 0; i < 5; i++)
        timeSum(ints);
}

private static int timeSum(char[] chars) {
    long start = System.nanoTime();
    int sum = 0;
    for (char ch : chars) {
        sum += ch;
    }
    long time = System.nanoTime() - start;
    System.out.printf("Took %,d us to sum %,d chars%n", time / 1000, chars.length);
    return sum;
}

private static int timeSum(int[] ints) {
    long start = System.nanoTime();
    int sum = 0;
    for (int i : ints) {
        sum += i;
    }
    long time = System.nanoTime() - start;
    System.out.printf("Took %,d us to sum %,d ints%n", time / 1000, ints.length);
    return sum;
}

印刷

Took 5,378 us to sum 1,000,000 chars
Took 11,551 us to sum 1,000,000 chars
Took 437 us to sum 1,000,000 chars
Took 407 us to sum 1,000,000 chars
Took 407 us to sum 1,000,000 chars
Took 5,539 us to sum 1,000,000 ints
Took 532 us to sum 1,000,000 ints
Took 530 us to sum 1,000,000 ints
Took 511 us to sum 1,000,000 ints
Took 507 us to sum 1,000,000 ints

我的结论是缓存效率比转换成本更重要。

于 2012-07-02T18:33:51.890 回答
1

这实际上是一个有趣且不平凡的问题。最佳答案将取决于您的具体要求以及您执行的操作的精确组合。

如果数据密集且不允许重复，则大位图可能是最佳选择。只需设置一点以显示每个可能的整数值的存在/不存在。这种方法对于读取和写入都将非常快并且 O(1)，但内存使用量显然取决于您拥有的范围有多大/数据的稀疏程度。

如果数据密集并且允许/常见重复，那么存储每个可能值的出现次数的数组可能会很好地工作。在性能上与位图方法相似，但是假设出现次数为整数，您可能需要 32 倍的内存。

如果您阅读量大且数据稀疏，那么基于排序数组的方法（使用二进制搜索进行查找）可能是最好的。如果您了解值的粗略分布，那么您可以通过使用启发式算法来猜测目标值在数组中的可能位置（例如，如果您利用这些知识，您可以显着击败 log2(N)分布大致均匀）

如果您有大量写入并且数据稀疏，那么您可能需要一个基于树的结构，该结构基于整数中位的子集进行拆分（例如，在每个节点的下一个最重要的 5 位上进行 32 路 trie 拆分） . Clojure 的持久数据结构使用这种技术效果很好。

于 2012-07-02T18:36:04.813 回答
1

我认为@Peter Lawrey 有一个好的开始：细分。部分不同的是，我将细分为 256 个事物，每个事物跟踪 2^23 个事物。根据整数的分布，使用顶部或底部 8 位进行细分。

至于子事物，当整数稀疏时，从 Set （或类似的）开始。但是，一旦 Set 达到一定大小，（它开始变得密集）切换到 BitSet。我不知道您是否需要支持删除值，在这种情况下，您需要从 BitSet 切换回 Set。

ps如果一切都失败了，所有正整数的一个简单的BitSet“只有”268MB（如果我的计算是正确的......）

于 2012-07-02T18:50:37.403 回答
0

那么链表呢？记忆约束将是整数的大小+前一个和下一个指针的一点开销。至于插入和删除，时间要求只是在列表中向下查找，直到找到比您要插入的那个更小的一个并将其放在该记录之前。删除只需要更改previous和next的指针，搜索就像插入一样容易。

于 2012-07-02T18:30:42.090 回答
0

您可以查看一些现代尝试（该链接未提及融合树）。但是，我认为它们的实现都非常复杂。如果你很幸运，你可能会发现一些大胆的人已经编写并开源了一个你可以使用的实现。

另一件事是经典的B-tree。

如果您的数据集大小相对一致，您甚至可以编写一个单级 B 树（因此具有单个根节点和多个子节点），这大大简化了实现（因为您可以只存储一个int[][]，并用窥视叶子替换内部键，如果这有任何意义的话）。

于 2012-07-04T11:27:55.970 回答
0

如果您不太担心速度，并且对内存使用感到害怕，您可以加载一个整数数组，创建另一个数组，对数组进行排序，直到您有一个数字 X（1K 左右以防止内存过载）然后将数组的该部分保存为文本文件（objectOutputStream 将整数保存为整数），清除数组，然后对数组中的下一个 X 个整数执行相同操作。只需确保将输出流标记为附加文件（true）与覆盖，这是默认值。

于 2012-07-02T18:49:22.453 回答