Быстрые коллекции строк в Java
Я использую Java и ищу коллекции строк (наборы и списки), которые оптимизированы в пространстве и являются быстрыми. Мои строки имеют фиксированный размер: 3 или 5 символов.
Пожалуйста, предложите мне, если есть какие-либо библиотеки коллекций, которые могут быть лучше всего подходят для меня. Я думал о некоторых словарных коллекциях.
Спасибо.
5 ответов
Если Мне нужна была скорость, я бы использовал C ++ и STL, а также специальный строковый класс, фиксированный до 8 байтов. 8 байтов хорошо выровнены и составляют 64 бита, поэтому их можно сравнить в одной машинной инструкции.
Используя STL, вы можете выбрать использование std :: set, std :: map, unordered_set, std :: list или любую другую совместимую с STL структуру.
'словарные коллекции'? HashMap - выбор по умолчанию. Это так же быстро, как O (1). И это не имеет ничего общего с фиксированным размером элемента или нет.
Предполагая, что вы говорите о C или C++, потому что я не могу представить другой язык, в котором кому-то нужна библиотека строк, я бы посоветовал использовать bstring от Paul Hsieh.
Хотя я никогда не использовал ее сам, потому что она просто не работала в моем случае, я адаптировал ее для своего собственного использования еще в 2007 году, взяв ее концепции за основу. Он очень хорошо документирован, и, по крайней мере, вы можете узнать много нового о строках, просто перейдя по этим ссылкам и прочитав материал Пола.
Если вы имеете в виду коллекцию строк, я бы выбрал стандартный HashSet в Java. Если вам нужно что-то еще более быстрое (с точки зрения времени поиска), вы можете использовать Trie. Трии дают очень быстрый поиск (O(длина строки)) независимо от количества строк в структуре данных и могут быть очень компактными.
Но, пожалуйста, сначала протестируйте свой код с HashSet. С несколькими миллионами строк небольшого размера, я не думаю, что это будет очень медленно.
У вас не может быть "быстрой коллекции" вообще, потому что у каждой структуры данных есть свои сильные и слабые стороны.
Если вам нужно быстрое добавление и итерация, ArrayList хороши. Если вы делаете довольно много удалений, вы можете использовать LinkedList. Если вам нужен быстрый поиск, хорошо подойдут HashSet и т. д.
Если у вас есть параллельный доступ, есть и другие потенциально более подходящие структуры данных. Иногда также может помочь объединение нескольких структур данных.
Короче говоря, вам нужно сообщить нам, для чего вы собираетесь использовать свою структуру данных.