SparseArrayList, новая версия

Выложил новую версию SparseArrayList. Добавил возможность итерации по паре индекс-значение в порядке возрастания индекса. Очень удобно, когда надо слить несколько списков в один.

Заодно провел несколько измерений расхода памяти и скорости доступа по сравнению с HashMap и TreeMap.

• SparseArrayList позволяет сэкономить около 5% памяти по сравнению с HashMap
• Скорость произвольного доступа к элементам выше у HashMap при маленьком числе элементов (100-200) и становится одинаковой при большом числе (>5000)
• Скорость последовательного (по возрастанию индекса) доступа у SparseArrayList выше чем у TreeMap более чем в 2 раза
  

SparseArrayList

Бывают такие ситуации, когда стандартный HashMap слишком медленный и затратный по памяти, а возможностей SparseVector из MTJ не хватает, поскольку надо хранить произвольные объекты. Для таких случаев я написал простой класс SparseArrayList, который практически идентичен SparseVector за вычетом, собственно, векторных операций. Плюс для хранения данных используется не массив, а ArrayList, и размер контейнера не ограничивается в конструкторе.

В архиве лежит еще и класс Arrays (дополнение к стандартному) из MTJ. В библиотеке он package-local, для реализации SparseArrayList пришлось сделать его public.

Поправки к прошлому посту

Степа указал мне на две мои ошибки в прошлом посте:

1. Не нужно делать специальный класс обертку над String, можно использовать метод intern(), который как раз и вернет нужную нам строку-синглтон.
2. Оказывается результат работы hashCode() у класса String кэшируется. Это, кстати, объясняет почему прирост производительности получился таким маленьким. Я ожидал на порядок больше.

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%.