Альтернативная карта для примитивных значений

Ответ 1

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

Альтернатива 1: используйте простые старые массивы.

Простой массив double[] может быть не таким сексуальным, как причудливая карта, но очень мало может превзойти его в компактности и скорости доступа.

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

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

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

Альтернатива 2: Настройте свои объекты.

Вместо того, чтобы сохранять карту из ключевых объектов в примитивные значения, почему бы просто не сделать эти значения в свойствах самих объектов? Это, в конце концов, то, что объектно-ориентированное программирование - все о — группируя связанные данные в значимые объекты.

Например, вместо сохранения HashMap<Point2D, Boolean> onSea, почему бы просто не дать своим точкам логическое свойство onSea? Конечно, вам нужно будет определить свой собственный класс точек для этого, но нет причин, по которым вы не можете заставить его расширить стандартный класс Point2D, если хотите, чтобы вы могли передавать свои пользовательские точки в любой метод который ожидает a Point2D.

Опять же, этот подход может не всегда работать напрямую, например. если вам нужно работать с классами, которые невозможно изменить (но см. ниже), или если значения, которые вы хотите сохранить, связаны с несколькими объектами (как в вашем ConcurrentHashMap<Point2D, HashMap<Point2D, Double>>).

Однако для последнего случая вы все равно сможете решить проблему, соответствующим образом переработав представление данных. Например, вместо представления взвешенного графика как Map<Node, Map<Node, Double>> вы можете определить класс Edge, например:

class Edge {
    Node a, b;
    double weight;
}

а затем добавьте свойство Edge[] (или Vector<Edge>) к каждому node, содержащему любые ребра, связанные с этим node.

Альтернатива 3: Объединение нескольких карт в один.

Если у вас есть несколько карт с одинаковыми ключами и не может просто превратить значения в новые свойства объектов ключей, как было предложено выше, рассмотрите их группировку в один класс метаданных и создайте одну карту из ключей в объекты этого класс. Например, вместо Map<Item, Double> accessFrequency и a Map<Item, Long> creationTime рассмотрим определение одного класса метаданных, например:

class ItemMetadata {
    double accessFrequency;
    long creationTime;
}

и имеет единственный Map<Item, ItemMetadata> для хранения всех значений метаданных. Это более эффективно с точки зрения памяти, чем наличие нескольких карт, а также позволяет экономить время, избегая избыточных поисков карт.

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

Альтернатива 4: Используйте декоратор.

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

class PointWrapper {
    Point2D point;
    boolean onSea;
    // ...
}

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

Этот подход наиболее полезен, если вы можете организовать хранение и работу только с обертками, так что вам никогда не нужно искать оболочку, соответствующую разворачиваемому объекту. Конечно, если вам это нужно делать иногда (например, потому что вы только получаете разворачиваемые объекты из другого кода), вы можете сделать это с помощью одного Map<Point2D, PointWrapper>, но затем вы снова вернетесь к предыдущей альтернативе.

Ответ 2

Коллекции Eclipse имеет объект и примитивные карты и имеет Mutable и неизменяемые версии для обоих.

MutableObjectDoubleMap<String> doubleMap = ObjectDoubleMaps.mutable.empty();
doubleMap.put("1", 1.0d);
doubleMap.put("2", 2.0d);

MutableObjectBooleanMap<String> booleanMap = ObjectBooleanMaps.mutable.empty();
booleanMap.put("ok", true);

ImmutableObjectDoubleMap<String> immutableMap = doubleMap.toImmutable();
Assert.assertEquals(doubleMap, immutableMap);

A MutableMap может использоваться как factory для ImmutableMap в коллекциях Eclipse, вызывая toImmutable, как я сделал в примере выше. Оба изменяемые и неизменяемые карты имеют общий родительский интерфейс, который в случае MutableObjectDoubleMap и ImmutableObjectDoubleMap выше, называется ObjectDoubleMap.

Eclipse Collections также имеет синхронизированные и не поддающиеся модификации версии для всех изменяемых контейнеров в библиотеке. Следующий код даст вам синхронизированное представление, обернутое вокруг примитивных карт.

MutableObjectDoubleMap<String> doubleMap = 
        ObjectDoubleMaps.mutable.<String>empty().asSynchronized();
doubleMap.put("1", 1.0d);
doubleMap.put("2", 2.0d);

MutableObjectBooleanMap<String> booleanMap = 
        ObjectBooleanMaps.mutable.<String>empty().asSynchronized();
booleanMap.put("ok", true);

Это сравнение производительности больших карт было опубликовано пару лет назад.

Большой обзор HashMap: JDK, FastUtil, Goldman Sachs, HPPC, Koloboke, Trove - версия для января 2015 г.

Коллекции GS с тех пор были перенесены в Eclipse Foundation и теперь являются коллекциями Eclipse.

Примечание. Я являюсь коммиттером для коллекций Eclipse.

Ответ 3

То, что вы ищете, это Object2DoubleOpenHashMap из fastutil (структура коллекций с небольшой площадью памяти и быстрым доступом и вставкой), которая предоставляет методы типа double getDouble(Object k) и double put(K k, double v).

Например:

// Create a Object2DoubleOpenHashMap instance
Object2DoubleMap<String> map = new Object2DoubleOpenHashMap<>();
// Put a new entry
map.put("foo", 12.50d);
// Access to the entry
double value = map.getDouble("foo");

Класс Object2DoubleOpenHashMap представляет собой реальную реализацию Map, которая не является потокобезопасной, однако вы все равно можете использовать метод утилиты Object2DoubleMaps.synchronize(Object2DoubleMap<K> m), чтобы сделать его потокобезопасным благодаря декоратору.

Тогда код создания:

// Create a thread safe Object2DoubleMap
Object2DoubleMap<String> map =  Object2DoubleMaps.synchronize(
    new Object2DoubleOpenHashMap<>()
);

Ответ 4

Существует несколько реализаций:

• http://labs.carrotsearch.com/hppc.html
• http://trove.starlight-systems.com/

Вот вопросы, связанные с лучшей производительностью:

• Наиболее эффективная библиотека примитивных коллекций Java
• Что такое быстрая альтернатива HashMap для сопоставления примитивным типам?

Фактическая реализация также может влиять на производительность

• Разница между HashMap, LinkedHashMap и TreeMap

Ответ 5

Чтобы лучше оценить, как эти разные библиотеки складываются друг против друга, я собрал небольшой контрольный показатель, который проверяет производительность:

• общее время для 300 000 вставок
• среднее время проверки сдерживаний с 1000 выборками, которые находятся на карте
• Размер памяти структуры данных Я посмотрел на структуру Map, которая принимает ключ String в качестве ключа и double как значение. Проверенные рамки Коллекция Eclipse, HPPC, Trove и FastUtil, так как а также для сравнения HashMap и ConcurrentHashMap.

Короче говоря, это следующие результаты:

Filling in 300000 into the JDK HashMap took 107ms
Filling in 300000 into the JDK ConcurrentHashMap took 152ms
Filling in 300000 into the Eclipse map took 107ms
Filling in 300000 into the Trove map took 855ms
Filling in 300000 into the HPPC map took 93ms
Filling in 300000 into the FastUtil map took 163ms
1000 lookups average in JDK HashMap took: 550ns
1000 lookups average in JDK Concurrent HashMap took: 748ns
1000 lookups average in Eclipse Map took: 894ns
1000 lookups average in Trove Map took: 1033ns
1000 lookups average in HPPC Map took: 523ns
1000 lookups average in FastUtil Map took: 680ns
JDK HashMap:            43'809'895B
JDK Concurrent HashMap: 43'653'740B => save  0.36%
Eclipse Map:            35'755'084B => save 18.39%
Trove Map:              32'147'798B => save 26.62%
HPPC Map:               27'366'533B => save 37.53%
FastUtil Map:           31'560'889B => save 27.96%

Для всех подробностей, а также тестового приложения посмотрите мою запись .