Производительность HashMap

Question

Мне нужно обработать 450 уникальных строк около 500 миллионов раз. Каждая строка имеет уникальный целочисленный идентификатор. Для меня есть два варианта.

1. Я могу добавить идентификатор строки и по прибытию строки я могу разделить строку, чтобы получить идентификатор и использовать его.
2. Я могу хранить 450 строк в HashMap<String, Integer> и на Прибытие строки, я могу запросить HashMap, чтобы получить идентификатор.

Может кто-нибудь предложить, какой вариант будет более эффективным с точки зрения обработки?

Answer 1

Разделение строки должно работать быстрее, если вы достаточно хорошо пишете свой код. Фактически, если у вас уже есть int-id, я не вижу причин отправлять только строку и поддерживать сопоставление.

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

OTOH, только 450 строк не имеют большого значения, и, если вы входите в него, написание собственного хэширования algo/function на самом деле будет самым элегантным и совершенным.

Answer 2

Все зависит от размеров строк и т.д.

Вы можете сделать все виды вещей.

Вы можете использовать двоичный поиск, чтобы получить индекс в списке, а по этому индексу - идентификатор.

Вы можете хэшировать только первые 2 символа, а не всю строку, которая, вероятно, будет быстрее, чем двоичный поиск, если строки имеют распределение ОК.

Вы можете использовать первый символ или первые два символа, если они уникальны как «идеальный индекс» в массиве 255 или 65K, который указывает на идентификатор.

Кроме того, если ваш идентификатор является числовым, лучше предварительно вычислить это, а не преобразовывать его на лету все время. Текст -> Двоичный на самом деле довольно дорогой (Binary -> Text хуже). Поэтому, вероятно, приятно избегать этого, если это возможно.

Но вам надлежит работать. 1 миллион всего на 1 мс каждый, составляет 20 минут обработки. На 500 м каждая нано-секунда впустую добавляет до 8+ минут дополнительной обработки. Вы можете не беспокоиться, но просто демонстрируете, что в этих масштабах «каждый бит помогает».

Итак, не принимайте наши слова за это, проверяйте разные вещи, чтобы найти то, что дает вам лучший результат для вашего рабочего набора, а затем идите с этим. Также рассмотрите чрезмерное создание объекта и избегайте этого. Обычно я не задумываюсь. Создание объекта происходит быстро, но нано-секунда - нано-секунда.

Если вы работаете на Java и вам не нужен UNICode (т. Е. Вы работаете с одиночными символами диапазона 0-255), я бы вообще не использовал строки. Я бы работал с необработанными байтами. Строки основаны на символах Java, которые являются UTF-16. Читатели Java конвертируют UTF-8 в UTF-16 каждый. Один. время. 500 миллионов раз. Ага! Еще несколько наносекунд. 8 наносекунд добавляет час к обработке.

Итак, снова, посмотрите во всех углах.

Или, не надо, напишите это легко, запустите его, запустите в выходные и сделайте с ним.

Answer 3

Если каждая строка имеет уникальный идентификатор, то поиск является O (1) только в случае hashmaps.

Я бы не предложил первый метод, потому что вы разбиваете каждую строку на 450 * 500 м, если ваш заказ не является одной строкой в ​​500 м раз, а затем на следующую. Как сказал Уилл, добавление числа к строкам, то извлечение может показаться прямым, но не рекомендуется.

Так что если ваши данные являются статическими (всего 450 строк), поместите их в Hashmap и поэкспериментируйте. Удачи.

Answer 4

Использование HashMap<Integer, String>. Разделение строки для получения идентификатора является дорогостоящей операцией, поскольку оно предполагает создание новых строк.

Answer 5

Я не думаю, что кто-то сможет дать вам убедительный «правильный» ответ, тем более, что вы не предоставили весь фон/свойства вычисления. (Например, средняя длина строк может иметь большое значение.)

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

Я также хотел бы найти способ извлечь и протестировать «уникальный целочисленный идентификатор», который не влечет за собой разделение строки.