Какова наиболее эффективная библиотека коллекций Java? [закрытый]

вопрос (теперь) о хранении большого количества данных, которые могут быть представлены с помощью примитивных типов, таких как int в карту. Некоторые из ответов здесь очень вводят в заблуждение, на мой взгляд. Давайте разберемся почему.

Я изменил бенчмарк с trove для измерения времени выполнения и потребления памяти. Я также добавил PCJ к этому эталону, который является еще одной библиотекой коллекций для примитивных типов (я использую ее широко). "Официальный" клад benchmark не сравнивает IntIntMaps с коллекцией Java Map<Integer, Integer>, возможно хранение Integers и хранение ints это не то же самое с технической точки зрения. Но пользователь может не заботиться об этой технической детали, он хочет хранить данные, представляемые с ints эффективно.

первая часть кода:

new Operation() {

     private long usedMem() {
        System.gc();
        return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
     }

     // trove
     public void ours() {
        long mem = usedMem();
        TIntIntHashMap ours = new TIntIntHashMap(SET_SIZE);
        for ( int i = dataset.size(); i-- > 0; ) {
           ours.put(i, i);
        }
        mem = usedMem() - mem;
        System.err.println("trove " + mem + " bytes");
        ours.clear();
     }

     public void pcj() {
        long mem = usedMem();
        IntKeyIntMap map = new IntKeyIntOpenHashMap(SET_SIZE);
        for ( int i = dataset.size(); i-- > 0; ) {
           map.put(i, i);
        }
        mem = usedMem() - mem;
        System.err.println("pcj " + mem + " bytes");
        map.clear();
     }

     // java collections
     public void theirs() {
        long mem = usedMem();
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(SET_SIZE);
        for ( int i = dataset.size(); i-- > 0; ) {
           map.put(i, i);
        }
        mem = usedMem() - mem;
        System.err.println("java " + mem + " bytes");
        map.clear();
     }

Я предполагаю, что данные приходят как примитивные ints, что кажется нормальным. Но это подразумевает штраф во время выполнения для Java util, из-за авто-бокс, который не является необходимым для примитивных коллекций фреймворков.

результаты выполнения (без gc() звонки, конечно) на WinXP, jdk1.6. 0_10:

                      100000 put operations      100000 contains operations 
java collections             1938 ms                        203 ms
trove                         234 ms                        125 ms
pcj                           516 ms                         94 ms

хотя это уже может показаться радикальным, это не причина использовать такую структуру.

причина-производительность памяти. Результаты для карты, содержащей 100000 int данные:

java collections        oscillates between 6644536 and 7168840 bytes
trove                                      1853296 bytes
pcj                                        1866112 bytes

Java Collections needs более чем в три раза память сравнивается с примитивными фреймворками коллекций. Т. е. вы можете хранить в три раза больше данных в памяти, не прибегая к дисковому IO, который снижает производительность во время выполнения на величины. И это имеет значение. Читайте высокая масштабируемость чтобы выяснить, почему.

по моему опыту, высокое потребление памяти является самой большой проблемой производительности с Java, что, конечно же, приводит к ухудшению производительности во время выполнения. Примитивные механизмы сбора может реально помочь здесь.

итак: нет, java.util-это не ответ. И "добавление функциональности" в коллекции Java-это не тот момент, когда вы спрашиваете об эффективности. Также современные коллекции JDK делают не "out-perform даже специализированные коллекции Trove".

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

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

вот более глубокий анализ, с точки зрения эталонная механика и библиотеки охвачены. этой это поток в списке Mahout dev.

охватываемые библиотеки

• HPPC
• Trove
• FastUtil
• Mahout (Colt )
• Коллекции Java

Обновление Июня 2015: К сожалению, оригинальные бенчмарки больше не доступны и к тому же немного устарели. здесь сравнительно недавно (Jan 2015) контрольные показатели, сделанные кем-то другим. Он не так всеобъемлющ и не имеет интерактивных исследовательских инструментов, как исходная ссылка.

Как заметили другие комментаторы, определение "эффективный" бросает широкую сеть. Однако никто еще не упомянул библиотека Javolution.

некоторые из основных моментов:

• классы Javolution быстры, очень быстры (например, вставка/удаление текста в O[Log(n)] вместо O[n] для стандартного StringBuffer/StringBuilder).
• все классы Javolution являются жесткими совместимыми в реальном времени и имеют очень детерминированное поведение (в микросекундный диапазон). Кроме того (в отличие от стандартной библиотеки), Javolution является безопасным RTSJ (без столкновения памяти или утечки памяти при использовании с расширением Java в режиме реального времени).
• классы коллекции Javolution в режиме реального времени (карта, список, таблица и набор) могут использоваться вместо большинства стандартных классов коллекции и обеспечивают дополнительную функциональность.
• коллекции Javolution обеспечивают гарантии параллелизма, чтобы упростить реализацию параллельных алгоритмов.

дистрибутив Javolution включает в себя набор тестов, чтобы вы могли видеть, как они складываются против других библиотек/встроенных коллекций.

некоторые коллекции libs для рассмотрения:

• коллекции Java в java.утиль
• Trove
• Коллекции Google библиотека
• Apache Commons Collections
• High-scale lib от Клиффа нажмите
• Дуга Lea коллекции lib-больше не поддерживается и в основном перестраивается в JDK

Я бы в первую очередь достичь библиотека коллекции JDK. Он охватывает наиболее распространенные вещи, которые нужно сделать, и, очевидно, уже доступны для вас.

Google Collections, вероятно, лучшая высококачественная библиотека за пределами JDK. Он широко используется и хорошо поддерживается.

Apache Commons Collections старше и немного страдает от проблемы "слишком много поваров", но также имеет много полезных вещей.

Trove имеет очень специализированные коллекции для таких случаев, как примитивные ключи/значения. Эти дни мы обнаруживаем, что на современных JDKs и с коллекциями Java 5+ и параллельными случаями использования коллекции JDK превосходят даже специализированные коллекции Trove.

Если у вас действительно высокие случаи использования параллелизма, вы обязательно должны проверить такие вещи, как NonBlockingHashMap в крупномасштабной lib, которая является реализацией без блокировки и может топать на ConcurrentHashMap, если у вас есть правильный вариант использования для него.

java.util

извините за очевидный ответ, но для большинства применений, по умолчанию Коллекции Java более чем достаточно.

хранить миллионы String на карте, взгляните на http://code.google.com/p/flatmap

Я разработчик счастливых коллекций от happy-collections on source-forge

1. коллекции на основе событий
2. Unmodifiable
3. SortedList
4. кэш

ConcurrentHashMap а также java.util.concurrent пакет должен быть упомянут, если вы планируете использовать HashMap в нескольких потоках. небольшой объем памяти оценивается, так как это часть стандартной java.

зависит от того, как мы определяем "эффективный".

каждая структура данных имеет свое собственное поведение Big-Oh для чтения, записи, итерации, объема памяти и т. д. Связанный список в одной библиотеке, скорее всего, будет таким же, как любой другой. И хэш-карта будет быстрее для чтения O(1), чем связанный список O (n).

но когда я читаю ответы на вопрос "самые полезные бесплатные библиотеки Java?- Я заметил, что троув почти не упоминается.

этот не похоже на "самый эффективный". Это звучит как "самый популярный" для меня.

просто некоторые отзывы - я никогда не слышал о нем, и я не знаю никого, кто использовал его. Коллекции, встроенные в JDK, Google или Apache Commons, мне хорошо известны.

Trove предлагает несколько преимуществ.

• меньший объем памяти, он не использовал карту.Объекты ввода
• вы можете использовать хэш-стратегии вместо ключей для карт, это экономит память и означает, что вам не нужно определять новый ключ каждый раз, когда вы хотите кэшировать объект на новом наборе его атрибутов
• он имеет примитивные типы коллекций
• думаю, что он имеет некоторую форму внутреннего итератора

тем не менее, многое было сделано, чтобы улучшить коллекций с JDK, поскольку клад был написан.

Это хеширование стратегии, которые делают его привлекательным для меня, хотя... Google для trove и прочитать их обзор.

Если вы хотите хранить миллионы записей в хэш-таблице, то шансы, что вы столкнетесь с проблемами памяти. Это произошло со мной, когда я попытался создать карту с 2,3 миллиона строковых объектов, например. Я пошел с BerkeleyDB, который очень зрел и выполняет хорошо. У них есть Java API, который обертывает API коллекций, поэтому вы можете легко создавать произвольно большие карты с очень небольшим объемом памяти. Доступ будет медленнее, хотя (как он хранится на диске).

вопрос: есть ли приличная (и эффективная), ухоженная библиотека для неизменяемых коллекций? Clojure имеет отличную поддержку для этого, и было бы неплохо иметь что-то подобное для Java.