Нужна быстрая альтернатива Java TreeMap <Integer, Character>, которая может хранить много отображений без замедления

Question

Я пишу Java-программу, которая использует TreeMap и производительность замедляется до сканирования, когда появляются десятки тысяч целочисленных символьных отображений.

Мне было интересно, есть ли реализация какого-либо типареализации сортированного набора, которая может использовать примитивы int и char и имеет что-то вроде функций «headMap» и «tailMap».

Я сейчас смотрю на Trove.Я также посмотрел на реализацию связанного списка, который использует сортировку вставки, но не включает функции head и tail.Я думаю, что связанный список с сортировкой вставки будет медленнее, чем дерево, не так ли?

Answer 1

Если вы ищете замену для чего-то вроде TreeMap<Integer,Character> и если ваши целочисленные ключи плотные, то массив будет наиболее эффективным. Но это будет char[] вместо int[], потому что вы хотите найти char в зависимости от клавиши int. Тогда я читаю что-то про «геном» ?! Предположим, что вы хотите использовать char для обозначения аденина, гуанина, цитозина и тимина (я не эксперт в этом), помните, что char занимает у вас 16 бит каждый - гораздо больше, чем нужно для четырех разных вещей. Возможно, вы можете сделать с somenthing, как

...
public static final byte UNDEF = (byte)-1;
public static final byte ADENIN = 0;
public static final byte GUANIN = 1;
public static final byte CYTOSIN = 2;
public static final byte THYMIN = 3;
...
private byte[] genome = new byte[ 26000000 ]; // or which size ever
...

И если это все еще израсходует слишком много памяти, это станет хитрым: Предположим, вам не нужно значение UNDEF, вам потребуется только 2 бита для четырех значений, то есть можно хранить вашу последовательность с четырьмя значениями в байт в итоге требует около 6,5 МБ. Но для таких вещей вам нужно немного поиграть ...

Answer 2

Если я понял вопрос, вам нужна структура данных, которая сохраняет порядок ключей, то есть положение символа, заменяющего символ в последовательности ссылок для индивидуума.

Я предполагаю, что вы обрабатываете предметы, увеличивая порядок позиций.

Теперь, поскольку TreeMap реализует Красно-Черное дерево , оно имеет логарифмическую сложность для основных операций.

Если вам просто нужно выполнить итерацию последовательности по порядку, вы получаете серьезное снижение производительности при каждой вставке.

Если мои предположения верны , я бы сказал, что вы можете использовать LinkedHashMap .

Как объясняет Javadoc:

Эта реализация избавляет своих клиентов от неопределенных, как правило, хаотическое упорядочение, предоставляемое HashMap (и Hashtable), без увеличение стоимости, связанной с TreeMap.

Это означает, что вы можете перебирать элементы в том же порядке, в котором вы их вводили, но основные операции имеют ту же сложность, что и обычный HashMap, с падением производительности из-за обработки связанного списка.

Вы можете представить это как HashMap, пройденный двойным списком, соединяющим ключи в порядке их вставки.

Обратите внимание, что я не обращаю внимание на тот факт, что ваша последовательность помещается в памяти или нет. Также помните, что LinkedHashMap займет больше памяти, чем простой HashMap.

Answer 3

Один из методов, который работает с очень большими отсортированными картами, - это использование комбинации SortedSet для управления вашими ключами в отсортированном порядке и Map для управления фактическим сопоставлением ключа и значения.Таким образом, вы можете выполнять быстрые итерации ключей, используя headSet () и tailSet (), а затем использовать ключи, возвращенные из набора, для поиска фактической карты.

У меня нет доказательств того, почему эта работа, но по моему опыту это в 10 раз быстрее с очень большими отсортированными картами.

Answer 4

Если вы знаете, что у вас проблемы с производительностью и / или проблема с памятью - тогда я бы рассмотрел использование trove TIntCharHashMap.В прошлом я использовал карты trove для повышения производительности и уменьшения потребления памяти.

Обратите внимание, что ключи не будут отсортированы, но вы можете получить int[] для ключей довольно дешево, которые затем можно отсортировать.Так что если вам нужен только отсортированный обход, вы можете сортировать их по мере необходимости.

Если вы обнаружите, что это некрасиво (или мешает производительности), вы можете обернуть TIntCharHashMap и отсортировать int[] в свою собственную отсортированную карту - выМне просто нужно будет поддерживать инвариант самостоятельно.

Мне немного жаль, что Trove не напрямую поддерживает основанные на деревьях классы карт / наборов для поддержания порядка, но я благодарен за инструменты, которые он предоставляет.

Answer 5

Для хранения огромного количества элементов лучше использовать B-Tree .Этот вид структур широко используется в базах данных для хранения индексов.Например на Oracle и MySQL, если я не ошибаюсь.взгляните на JDBM3 .Также должны существовать другие реализации.

Answer 6

вы смотрели на PriorityQueue?он имеет несколько полезных методов и сортирует элементы в зависимости от определяемого вами компаратора.

Answer 7

Как пишет Стив, может быть стоит проверить с помощью профилировщика, что виновником является TreeMap.

Несколько других опций:

• Используйте HashMap с большими initialCapacity

• Если ваш набор ключей плотный, то вы можете использовать int[]. Это будет быстрее всего.

Answer 8

Если вы просто хотите более быструю реализацию Map, вы рассматривали HashMap ?При этом по-прежнему используются объекты, но если они изначально созданы (см. Третью форму конструктора в предыдущей ссылке) с достаточно большой емкостью, это обеспечит гораздо более быстрый доступ к вашим данным, чем TreeMap.

В качестве альтернативы, есливас интересует только поведение, подобное SortedSet, на вашей карте, вы можете добиться лучшей производительности, используя TreeSet .

Что касается Trove, я не знаком с ним, но подозреваю, что выможет получить существенные улучшения производительности за счет использования классов, предоставляемых Java, вместо обращения к сторонним библиотекам, лишь с небольшим дополнительным усилием изучения того, что вам нужно, из ваших структур данных и какой дополнительной работы они тратят впустую, предоставляя функции, которые вам не нужны ».не нужно.