Самый быстрый способ записать хэш-карту на диск в отсортированный набор

Question

У меня есть Map<byte[], Element>, и я хочу отсортировать его и записать на диск, чтобы у меня был файл со всеми элементами, отсортированными по ключу через UnsignedBytes.lexicographicalComparator.

в Guava.сейчас нужно сделать следующее:

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

Ваш вопрос был "Есть идеи?" Я думаю, все, что я мог написать, было бы ответом.

У меня была та же проблема, что и у вас, и я тщательно сравнил два решения: используйте древовидную карту, чтобы элементы были отсортированы заранее, или отсортируйте их по факту. Мой тест показал тот же результат, что и ваш. По факту сортировать быстрее.

Меня не будет беспокоить тот факт, что второй подход требует большего копирования. Во-первых, быстрее, быстрее, верно? Если второй подход требует меньше циклов ЦП, то лучше.

Если речь идет о памяти, имейте в виду, что древовидные карты и хеш-карты занимают гораздо больше памяти на элемент, чем ArrayList, который поддерживается простым массивом объектов. Каждый элемент в древовидной или хэш-карте требует как минимум один объект, а обычно и больше. Объекты имеют много служебных данных, 32 или более байтов. В плоском массиве каждый элемент занимает всего 4 байта.

Мои тесты показали, что время для выделения массива из памяти было примерно пропорционально размеру массива, как только вы получили размер массива в несколько десятков байт. Поэтому выделение ArrayList может быть медленным, если оно действительно большое. Тем не менее, я думаю, что это лучшая ставка, если нет опасности нехватки памяти.