Индексированная коллекция строк в Java

Question

Используя Java, предполагая v1.6.

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

В настоящее время я использую HashMap<String, Integer>, но меня беспокоит, что бокс / распаковка Integer в int делает это медленнее.

Я думал об использовании ArrayList<String> в сочетании с int[].

т.е. Вместо:

int value = (int) HashMap<String, Integer>.get("key");

Я мог бы сделать

int value = int[ArrayList<String>.indexOf("key")];

Есть мысли? Есть ли более быстрый способ сделать это?

p.s. Я соберу коллекцию только один раз и, возможно, изменю ее один раз, но каждый раз буду знать размер, чтобы я мог использовать String[] вместо ArrayList, но не уверен, что есть более быстрый способ репликации indexOf ...

Answer 1

Распаковка происходит быстро - выделения не требуются. Бокс потенциально медленнее, так как ему нужно выделить новый объект (если он не использует объединенный объект).

Вы уверены, что у вас действительно есть проблема? Не усложняйте ваш код, пока вы не докажете, что это значительный удар. Я очень сомневаюсь, что это так.

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

Я бы предложил использовать intValue() вместо приведения для преобразования значения в int, хотя - это делает более понятным (IMO), что происходит.

РЕДАКТИРОВАТЬ: Чтобы ответить на вопрос в комментарии, HashMap.get(key) будет быстрее, чем ArrayList.indexOf(key) , когда коллекция достаточно большая . Если у вас есть только пять предметов, список может быть быстрее. Я полагаю, что это не совсем так.

Если вы действительно, действительно не хотите бокс / распаковку, попробуйте Trove (TObjectHashMap). Также нужно рассмотреть COLT , но я не смог найти там нужного типа.

Answer 2

Любой прирост производительности, который вы получаете от отсутствия необходимости помещать в коробку / распаковывать, значительно стирается циклом for, который вам необходим для метода indexOf.

Используйте HashMap. Также вам не нужно (int) приведение, компилятор позаботится об этом за вас.

С массивом все будет в порядке с небольшим количеством элементов в массиве, но так же и с HashMap ...

Единственный способ сделать поиск в массиве быстрым (а не реальным предложением, поскольку у него слишком много проблем), если для работы с хэш-кодом строки используется как индекс в массиве - даже не думайте об этом! (Я упоминаю об этом только потому, что в Google вы можете найти что-то, что говорит об этом ... если они не объяснят, почему это плохо, не читайте больше об этом!)

Answer 3

Если стоимость построения карты один раз и только один раз не имеет значения, вы можете посмотреть идеальное хеширование , например код Боба Дженкинса .

Answer 4

Поскольку вы говорите, что это действительно узкое место, я предложу Примитивные коллекции для Java ; в частности, ObjectKeyIntMap выглядит именно так, как вы хотите.

Answer 5

Я думаю, что сканирование вашего ArrayList, чтобы найти соответствие для вашего "ключа" будет намного медленнее, чем ваши проблемы с боксом / распаковкой.

Answer 6

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

РЕДАКТИРОВАТЬ: Кроме того, здесь не используется бокс, просто распаковка уже сохраненных объектов, что должно быть довольно быстрым, поскольку на этом шаге не выполняется выделение объектов. Поэтому я не думаю, что это даст вам больше скорости, но вы все равно должны запустить тесты.

Answer 7

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

Я предлагаю ввести небольшую оболочку с геттером для int, такую ​​как SimpleInt. Он содержит int без преобразования. Конструктор не дорогой и в целом дешевле, чем целое число.

public SimpleInt
{
    private final int data;

    public SimpleInt(int i)
    {
        data = i;
    }

    // getter here
    ....
}

Answer 8

List.indexOf выполнит линейное сканирование списка - обычно O (n). Бинарный поиск сделает работу в O (log n). Хеш-таблица сделает это в O (1).

Наличие большого количества Integer объектов в памяти может быть проблемой. Но тогда то же самое верно для String с (как String, так и char[]). Вы можете сделать свою собственную реализацию в стиле БД, но я рекомендую сначала провести сравнительный анализ.

Answer 9

Одна небольшая проблема: у вас могут быть повторяющиеся элементы в списке. Если вы действительно хотите сделать это вторым способом, попробуйте вместо этого использовать Set.

Сказав это, вы провели тест производительности на двух, чтобы увидеть, быстрее ли один, чем другой?

Редактировать: Конечно, самый популярный тип набора (HashSet) сам опирается на HashMap, поэтому переключение на набор может и не быть таким мудрым изменением.