java - 将 HashMap 刷新到磁盘到有序集合中的最快方法

Question

我有一个 Map<byte[], Element>我想对它进行排序并将其写入磁盘，这样我就有了一个文件，其中包含通过 Guava 的 UnsignedBytes.lexicographicalComparator 按键排序的所有元素。 .

我现在正在做的是:

HashMap<byte[], Element> memory;

// ... code creating and populating memory ...

TreeMap<byte[], Element> sortedMap = new TreeMap<byte[], Element>(UnsignedBytes.lexicographicalComparator());
sortedMap.putAll(memory.getMap());

MyWriter writer = new MyWriter("myfile.dat");
for (Element element: sortedMap.values())
    writer.write(element);
writer.close();

可能很难使排序更快 (O(nlogn))，问题是我是否可以改进排序列表的导航。理想情况下，我会分类为 ArrayList而不是 TreeMap , 这样遍历它就会非常快。

我考虑过将 HashMap 放入 ArrayList 中和 Collections.sort()它，但这需要比实际解决方案更多的复制。

有什么想法吗？

编辑:

我在这里添加我的测试 ArrayList这是快 2 倍，但我认为它使用更多内存。也许对这个假设有一些评论？

// ArrayList-based implementation 2x faster
ArrayList<Element> sorted = new ArrayList<Element>(memory.size());
sorted.addAll(memory.values());

final Comparator<byte[]> lexic = UnsignedBytes.lexicographicalComparator();

Collections.sort(sorted, new Comparator<Element>(){
    public int compare(Element arg0, Element arg1) {
        return lexic.compare(arg0.getKey(), arg1.getKey());
    }
});
MyWriter writer = new MyWriter(filename);

for (Element element: sorted)
    writer.write(element);
writer.close();

Answer 1

您的问题是“有什么想法吗？”。我想我能写的任何东西都会是一个答案。

我遇到了与您相同的问题，并对两种解决方案进行了广泛的基准测试:使用树状图以便提前对项目进行排序，或者在事后对它们进行排序。我的基准测试结果与您的相同。事后排序更快。

我不会担心第二种方法需要更多的复制。首先，越快越快，对吧？如果第二种方法占用的 CPU 周期更少，则更好。

如果内存是一个问题，那么请记住，treemaps 和 hashmaps 每个项目占用的内存比 ArrayList 多得多，ArrayList 由一个简单的对象数组支持。 treemap 或 hashmap 中的每个元素至少需要一个对象，通常更多。对象有很多开销，32 个或更多字节。在平面数组中，每个元素仅占用 4 个字节。

我的基准测试表明，一旦数组大小超过几十个字节，从内存分配数组的时间大致与数组的大小成正比。因此，如果 ArrayList 非常大，则分配它可能会很慢。不过，我认为这是更好的选择，只要没有内存不足的危险即可。