Я много работаю в НЛП и машинном обучении, поэтому мне приходится все время заниматься такими вещами, и есть тонна возможностей для оптимизации.
Несколько моментов для рассмотрения:
Прежде всего, вас убивает стандартный класс JDK HashMap. Это хороший контейнер для вычислений общего назначения, но он ужасен для высокопроизводительных вычислений. Для каждой записи в вашей коллекции (строка из четырех символов (8 байтов) и целое число (4 байта)) стандартная java HashMap будет использовать:
- строковый объект
- 8-байтовые данные объекта
- 4-байтовая ссылка на массив
- 4-байтовое поле длины строки
- массив символов
- 8-байтовые данные объекта
- 2 байта для каждого символа (умножено на 4 символа) = 8 байтов
- 4-байтовое поле длины массива
- Целочисленный объект
- 8-байтовые данные объекта
- 4-байтовое значение типа int
- Объект HashMap.Entry
- 8-байтовые данные объекта
- 4-байтовая ссылка на ключ
- 4-байтовое значение Ссылка
Итак, ваши крошечные 12 байтов данных становятся 64 байтами. И это до того, как HashMap выделил массив значений хеш-функции для использования во время операций поиска. Имейте в виду, что все эти крошечные маленькие объекты означают больше работы для ГХ, но, что более важно, это означает, что ваши объекты занимают большую область основной памяти и с меньшей вероятностью помещаются в кэш процессора. Когда у вас много кешей, вы теряете производительность.
ПРИМЕЧАНИЕ. Комментатор напомнил мне, что все подстроки будут использовать один и тот же базовый массив символов, что является хорошим моментом, о котором я забыл. Но, тем не менее, это означает, что каждая запись карты идет от 64 байтов до 44 байтов. Который все еще позор, когда должно быть только 12 байтов.
Упаковка и распаковка всех этих целочисленных значений заставляет ваш код работать медленнее и потреблять больше памяти. В большинстве случаев нас это не волнует, и ванильная реализация HashMap хороша, даже с ее обязательным боксом и жадным потреблением памяти. Но в вашем случае, если этот код выполняется в узком внутреннем цикле, мы бы предпочли иметь специализированный класс, который знает, что его значения всегда будут целыми числами, и устраняет необходимость в упаковке.
Если вы покопаетесь в исходном коде JDK, вы увидите, что ваш код будет в итоге дважды вызывать строковые методы hashCode() и equals(). Один раз для map.get() и один раз для map.put(). Но есть другой тип коллекции, называемый HashBag , который может выполнять поиск, вставку и увеличение количества только с одним поиском. Коллекция «bag» отчасти похожа на «набор», за исключением того, что она может содержать дубликаты и отслеживает, сколько существует дубликатов. Для каждой из ваших тетраграмм вам нужно было бы просто позвонить bag.put(tetragram) без необходимости сначала получать и обновлять счет. К сожалению, в JDK нет реализаций пакетов, поэтому вам нужно найти их в другом месте или написать самому.
К счастью, ваши тетраграммы можно кодировать без потерь в виде значений long (поскольку каждый символ java имеет ширину 2 байта, а long дает вам восемь байт для работы). Поэтому вы можете выполнять итерацию по массиву символов и преобразовывать каждую тетраграмму в long, а также избегать лишних затрат на создание такого количества крошечных строк. Затем вы можете сохранить свои результаты в LongIntHashMap (из библиотеки Trove). Это будет намного быстрее, чем ваша текущая реализация, потому что вы можете избежать создания всех этих крошечных строковых объектов.
Хотя Trove LongIntHashMap довольно превосходен, он не так хорош, как LongHashBag.Нет вызова equals (так как long можно сравнить с оператором ==), но вы все равно заплатите цену за два вызова hashCode.Если вы хотите быть действительно агрессивным в оптимизации, вы можете посмотреть на исходный код LongIntHashMap и выяснить, как его преобразовать в LongHashBag.Это не так сложно, и, в конце концов, это именно то, что я сделал в своем собственном коде.
Обновление 1:
Хорошо, вот немногос кодом:
private LongHashBag countTetragrams(String text) {
// Homework assignment: find a good LongHashBag implementation, or
// grab the LongIntHashMap implementation from Trove, and tweak it
// to work as a Bag
LongHashBag bag = new LongHashBag(500);
// There are no tetragrams in this string.
if (text.length() < 4) return bag;
// Shortcut: if we calculate the first tetragram before entering
// the loop, then we can use bit-shifting logic within the loop
// to create all subsequent tetragram values.
char[] c = text.toCharArray();
long tetragram = ((long) c[0] << 48) |
(((long) c[1]) << 32) |
(((long) c[2]) << 16) |
((long) c[3]);
bag.add(tetragram);
for (int i = 4, last = text.length(); i < last; i++) {
// During each loop iteration, the leftmost 2-bytes are shifted
// out of the tetragram, to make room for the 2-bytes from the
// current character.
tetragram = (tetragram << 16) | ((long) c[i]);
bag.add(tetragram);
}
return bag;
}
Обновление 2:
Я только что провел несколько испытаний различных решений, и я собирался получить примерно 25% -ное улучшение производительности при использовании LongHashBagподход вместо стандартного подхода HashMap.
Тем не менее, я собирался получить улучшение на 300% путем переработки полученных объектов.По сути, вместо этого:
private LongHashBag countTetragrams(String text) {
// Creates a new HashBag on every invocation. Very wasteful.
LongHashBag bag = new LongHashBag(500);
// ...blah blah blah...
return bag;
}
... Я сейчас делаю это ...
private void countTetragrams(String text, LongHashBag bag) {
// Return the object to a neutral state, and recycle it.
bag.clear()
// ...blah blah blah...
}
Вызывающий код отвечает за создание объекта LongHashBag и обеспечение того, чтобымы закончили с этим, когда мы снова вызываем метод count.
Но это также сработает ...
private LongHashBag countTetragrams(String text) {
// Return the object to a neutral state, and recycle it.
LongHashBag bag = retrieveLongHashBagFromObjectPool();
// ...blah blah blah...
return bag;
}
... что немного прибавитнемного накладных расходов на поддержание пула.И вызывающий код должен помнить, чтобы положить сумку обратно в бассейн, когда он закончит ее использовать.Но выигрыш в производительности определенно стоил того.
Кстати, именно такие приемы я использую каждый день.Объединение объектов стало одним из моих самых надежных приемов для повышения производительности.
Но, как я уже сказал, утилизация этих объектов дает повышение производительности на 300%.