计算大长数组中的不同值（性能问题）

Question

我有这个：

long hnds[] = new long[133784560]; // 133 million

然后我快速填充数组（几毫秒）然后我想知道唯一（即不同）值的数量。现在，我什至不需要这个实时，我只需要尝试几个变体，看看每个变体有多少个独特的价值。

我尝试过，例如这个：

import org.apache.commons.lang3.ArrayUtils;
....
HashSet<Long> length = new HashSet<Long>(Arrays.asList(ArrayUtils.toObject(hnds)));
System.out.println("size: " + length.size());

等待半小时后出现堆 space 错误（我有 Xmx4000m）。

我也试过初始化 Long[] hnds 而不是 long[] hnds，但是数组的初始填充需要永远。或者，例如，在添加值时从一开始就使用 Set，但也需要永远。有什么方法可以计算 long[] 数组的不同值而无需永远等待？如果必须的话，我会把它写到一个文件中，只是某种方式。

Answer 1

我最好的建议是使用像 fastutil (http://fastutil.di.unimi.it/) 这样的库，然后使用自定义的未装箱哈希集：

import it.unimi.dsi.fastutil.longs.LongOpenHashSet;
System.out.println(new LongOpenHashSet(hnds).size());

（另外，顺便说一下，如果您可以接受近似答案，您可以尝试多更有效的算法；请参阅 this paper 了解详细信息。）

Answer 2

只需排序并计数。

 int sz = 133784560;
 Random randy = new Random();
 long[] longs = new long[sz];
 for(int i = 0; i < sz; i++) { longs[i] = randy.nextInt(10000000); }
 Arrays.sort(longs);
 long lastSeen = longs[0];
 long count = 0;
 for(int i = 1; i < sz; i++) {
   if(longs[i] != lastSeen) count++;
   lastSeen = longs[i];
 }

在我的笔记本电脑上大约需要 15 秒。

计算大长数组中的不同值（性能问题）

count distinct values in big long array (performance issue)

java

performance

hashset