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%.
11 comments:
Ещё можно использовать IdentityHashMap, а у String использовать стандартный метод intern().
И правда! Спасибо, Степа.
Не совсем понял, потому как не большой спец по джаве. Ускорение достигается за счет того, что значение хеша строки не вычисляется каждый раз?
За счет двух вещей:
1. Не вычисляется хэш для строки.
2. Вместо String.equals() для сравнения ключей используется сравнение двух ссылок на ключи.
1) Но ведь это возможно только, если мы работаем все время с одним и тем же набором строк ?
2) Это грабли, так делать в общем случае нельзя. :-)
Метод calculateProbability() вызывается для каждой категории в цикле. Скажем 1000 раз. Соответственно, для каждого входного слова хэш-код будет вычислен эти самые 1000 раз, а это совершенно лишние затраты.
Перед этим большим циклом мы из входного массива слов делаем массив строк-синглтонов (берем их из кэша по значению). В хэшмапе words в каждой категории тоже хранятся строки-синглтоны взятые из того жэ кэша при загрузке.
Синглтоны можно сравнивать по ссылке и хэш-код для них вычисляется нативным методом, который работает очень быстро.
Насчет хеш кода: тогда конечно.
Насчет ссылки: одинаковые строки могут имет разные ссылки. Не боитесь? :-)
Вот как раз идея в том, чтобы перед началом больших вычислений у всех одинаковых строк сделать одинаковые ссылки.
ИМХО, проще написать функцию, которая сначала сравнивает закешированные хеш-коды, а потом уже сами строки. Тем более, что в классе обертке эти значения хранятся. Может будет чуть медленнее, но зато надежно. Ведь это не так уж и просто с приведением ссылок на одинаковые строки.
Просто. Это можно сделать двумя способами:
1. Свой класс SingletonString с методом getInstance(String). Все строки в системе перед работой превращаются в SingletonString.
2. Еще проще. У String есть метод intern(). В JDK уже все сделано за нас, есть пул строк, в котором по значению ищется каноническое представление.
Хэш-код, как оказалось, и так кэшируется в String, поэтому все ускорение достигнуто за счет equals().
Отправить комментарий