Практические советы по реализации систем извлечения информации

среда, октября 11, 2006

HashMap со строковыми ключами

В реализации классификатора Байеса, в классе Category вполне может встретиться следующий метод:
public double calculateProbability(String[] tokens) {
double probability = this.probability;
for (String token : tokens) {
Double partProbability = words.get(token);
if (partProbability != null) {
probability *= partProbability;
} else {
probability *= LOW_PROBABILITY;
}
}
return probability;
}
В данном случае words это HashMap<String, Double>, вероятности для каждого слова в данной категории. Получение элемента по ключу в HashMap работает быстро, за константное время.

Если прогнать классификатор под профайлером, то основное время придется как раз на вызов метода get(). Как он работает: для ключа вычисляется его хэш-код, по этому хэшу достается список пар ключ-значение, который последовательно проходится в поисках ключа равного данному. Как можно ускорить работу hashCode() и equals() для класса String? Ответ прост! Надо заменить их на Object.hashCode() и Object.equals() (что эквивалентно ==). Для этого нужно всего лишь вместо объектов String хранить в words обертку-синглтон над String и передавать в calculateProbability() массив таких оберток вместо String[]. Это простое решение дает прирост производительности примерно на 100%.

13 комментариев:

Stepan Koltsov комментирует...

Ещё можно использовать IdentityHashMap, а у String использовать стандартный метод intern().

krondix комментирует...

И правда! Спасибо, Степа.

LB комментирует...

Не совсем понял, потому как не большой спец по джаве. Ускорение достигается за счет того, что значение хеша строки не вычисляется каждый раз?

krondix комментирует...

За счет двух вещей:
1. Не вычисляется хэш для строки.
2. Вместо String.equals() для сравнения ключей используется сравнение двух ссылок на ключи.

LB комментирует...

1) Но ведь это возможно только, если мы работаем все время с одним и тем же набором строк ?
2) Это грабли, так делать в общем случае нельзя. :-)

krondix комментирует...

Метод calculateProbability() вызывается для каждой категории в цикле. Скажем 1000 раз. Соответственно, для каждого входного слова хэш-код будет вычислен эти самые 1000 раз, а это совершенно лишние затраты.

Перед этим большим циклом мы из входного массива слов делаем массив строк-синглтонов (берем их из кэша по значению). В хэшмапе words в каждой категории тоже хранятся строки-синглтоны взятые из того жэ кэша при загрузке.

Синглтоны можно сравнивать по ссылке и хэш-код для них вычисляется нативным методом, который работает очень быстро.

LB комментирует...

Насчет хеш кода: тогда конечно.
Насчет ссылки: одинаковые строки могут имет разные ссылки. Не боитесь? :-)

krondix комментирует...

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

LB комментирует...

ИМХО, проще написать функцию, которая сначала сравнивает закешированные хеш-коды, а потом уже сами строки. Тем более, что в классе обертке эти значения хранятся. Может будет чуть медленнее, но зато надежно. Ведь это не так уж и просто с приведением ссылок на одинаковые строки.

krondix комментирует...

Просто. Это можно сделать двумя способами:
1. Свой класс SingletonString с методом getInstance(String). Все строки в системе перед работой превращаются в SingletonString.
2. Еще проще. У String есть метод intern(). В JDK уже все сделано за нас, есть пул строк, в котором по значению ищется каноническое представление.

Хэш-код, как оказалось, и так кэшируется в String, поэтому все ускорение достигнуто за счет equals().

x комментирует...
Этот комментарий был удален автором.
Alex комментирует...

Золотой серфер|Лучшие бесплатные CMS интернета

http://goldserfer.ru

klochcovigor комментирует...

полезная статья- спасибо.