Быстрые коллекции строк в Java

Question

Я использую Java и ищу коллекции строк (наборы и списки), которые оптимизированы в пространстве и быстры.Мои строки имеют фиксированный размер: 3 или 5 символов.

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

Спасибо.

Answer 1

Если вы имеете в виду коллекцию строк, я бы пошел с Java по умолчанию HashSet.Если вам нужно что-то еще быстрее (с точки зрения времени поиска), вы можете использовать Trie .Попытки дают очень быстрый поиск (O (длина строки)) независимо от количества строк в структуре данных и могут быть очень компактными.

Но, пожалуйста, сначала проверьте ваш код с HashSet.Я думаю, что до нескольких миллионов небольших струн будет очень медленным.

Answer 2

«коллекции на основе словаря»? HashMap является выбором по умолчанию. Это так же быстро, как O (1). И это не имеет ничего с размером элемента фиксированным или нет.

Answer 3

В общем, у вас не может быть «быстрого сбора», потому что у каждой структуры данных есть свои сильные и слабые стороны.

Если вы хотите быстрое сложение и итерацию, ArrayList s - это хорошо.Если вы делаете довольно много удаления, вы можете использовать LinkedList s.Если вам нужны быстрые просмотры, HashSet s - это хорошо и т. Д.

Если у вас есть параллельный доступ, есть и другие потенциально более подходящие структуры данных.Иногда может помочь объединение нескольких структур данных.

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

Answer 4

Если бы я хотел скорости, я бы использовал C ++ и STL, а также класс пользовательских строк, фиксированный до 8 байтов. 8 байтов хорошо выровнены и составляют 64 бита, поэтому их можно сравнить в одной машинной инструкции.

Используя STL, вы можете выбрать использование std :: set, std :: map, unordered_set, std :: list или любой другой структуры, совместимой с STL.

Answer 5

Предполагая, что вы говорите о C или C ++, потому что я не могу представить себе другого языка, где кто-то искал бы библиотеку строк, я бы посоветовал использовать bstring от Пола Се .

Хотя я никогда не использовал его сам, потому что он просто не работал в моем случае, я адаптировал его для собственного использования еще в 2007 году, взяв его за основу.Это очень хорошо задокументировано, и, по крайней мере, вы можете многое узнать о строках, просто переходя по этим ссылкам и читая материалы Пола.