Существует ли вид карты, которая оптимизирует * последовательности ключей * с одинаковым значением?

Question

Если вы сопоставляете шорты Java с несколькими неизменяемыми объектами, и часто последовательная последовательность коротких ключей (соседей) отображается на одно и то же значение, существует некоторая структура карты, которая позволяет сэкономить больше памяти, чемхэш-карту, сохраняя при этом высокую скорость доступа (O (1) или O (log (N)))?

Я мог бы перевернуть карту и использовать гораздо меньше памяти, но тогда мне пришлось быпросмотрите каждое сопоставление, чтобы узнать, сопоставлено ли определенное короткое замыкание и чему оно сопоставлено (O (N)).

Я полагаю, что какое-то древовидное отображение могло бы сделать это;может быть, что-то подобное в какой-то библиотеке коллекций?

Answer 1

Посмотрите на деревья интервалов .

Answer 2

Однажды я использовал TreeMap с пользовательским классом ключей и соответствующим компаратором для реализации этого.Мой ключевой класс содержал оба конца диапазона значений double.Запросы были заданы в виде диапазона, причем оба конца одинаковы, а компаратор сделал все остальное.

Однако было сделано несколько вариантов:

• Как следуетremove() обрабатывается?

• Что должно произойти, если get() выдан с диапазоном клавиш, который перекрывает два или более диапазонов?

• Имеет ли смысл объединить это поведение в новой реализации Map - возможно, подкласс TreeMap?

Answer 3

Это решение совсем другое - очень старомодное, но приближающееся к O (1), маленькое и быстрое. 90% значений поместятся в 4 бита, в то время как запись карты или дерева требует сотен бит для представления (без большого количества пользовательских переопределений). Итак, начните с представления их в массиве 4-битных записей:

// Used to store nybbles containing small values, with direct arithmetic mapping.
// A value of 15 indicates that the value is larger than 14.
// Size: 32KB
byte[] zeroTo14Array = new byte[(1<<Short.SIZE)/2];
static final short BIGGER_THAN_NYBBLE = 15;

Затем используйте эффективную кратко-байтовую карту (от fastutil или gnu trove для представления значений от 15 до 255:

// Use to store bytes with values 15-255.
// If value is 0, value is larger than 255.
Short2ByteOpenHashMap byteMap = new Short2ByteOpenHashMap();

Наконец, используйте эффективную карту коротких объектов для всего остального:

// Use to store values larger than 255 
Short2ObjectOpenHashMap<Value> objectMap = new Short2ObjectOpenHashMap();

// just a sketch
public class Value
{
    short shortValue;
    String optional;
}

Я могу опубликовать оставшуюся часть непроверенного кода, если хотите.

Answer 4

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

Таким образом, чтобы найти, сопоставлено ли заданное короткое замыкание, вам нужно найти узел в дереве с наивысшим ключом, который меньше заданного (O (logn)), и проверить, попадает ли заданный ключ в интервал, который представляет этот узел.