Поиск частичных свойств

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

public class Properties {
    private String propertyOne;
    private String propertyTwo;
    private String propertyThree;
    private String propertyFour;
    ...
    ...
}

Теперь предположим, что у меня есть несколько записей на карте, как показано ниже:

41111 -> {1,2,3,4,5}

41112 -> {1,2,3,4,6}

41234 -> {1,2,345,87,65}

51123 -> {100,200,30000,345,123}

51122 -> {100,200,30000,556,989}

Теперь, если я сделаю map.get("12567"), я получу желаемый объект свойства.

У меня есть проблема: мне нужно создать структуру данных, которая может сохранять частичные данные. Под частичными данными я подразумеваю, что если я сделаю map.get("4111"), я должен получить пересечение {1,2,3,4,5} (свойство для 41111) и {1,2,3,4,6} (свойство для 41112), которое это {1,2,3,4,null}.

Точно так же map.get("41") должен произвести {1,2,null,null,null}.

У меня прямо сейчас есть решение, которое заключается в том, что я создал несколько HashMaps, которые содержат все возможные частичные ключи и их соответствующие значения, например:

Map<String, Property>`` keyValuesForOneChar содержит все возможные одиночные символы в качестве ключей и соответствующие им значения.

Map<String, Property> keyValuesForTwoChars содержит все возможные два символа в качестве ключей и соответствующие им значения.

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

  1. Решение должно быть строго только в памяти.
  2. Поиск должен быть быстрее. Вот почему, если обработка необработанных данных и подготовка структуры данных требуют дополнительного времени и памяти, это не должно быть проблемой.

java hashmap in-memory data-structures
person Khandekar Mohammad Saleh    schedule 17.05.2016    source источник
comment
Для @Т. Ответ Clarverie было бы интересно, если требуется найти 11 как ключ, который должен затем пересекать 41111, 41112, 51123 и 51122 или поиск всегда начинается с начала ключа?   -  person Rainer    schedule 17.05.2016
comment
это всегда должно начинаться с начала.   -  person Khandekar Mohammad Saleh    schedule 18.05.2016

Ответы (1)


arrow_upward
4
arrow_downward

HashMap определенно не самая подходящая структура данных для вашей задачи. Поскольку ваши ключи являются строками, вы можете реализовать trie (также называемое деревом префиксов).

Он работает путем разделения строковых ключей на более мелкие строки или символы. Таким образом, вы можете хранить значения для ключей, а также для общих префиксов. То есть вы можете сохранить пересечение «41111» и «41112» на общем префиксе «4111». При поиске 4111 требуется O(m) шагов, где m — длина ключа, и вы сможете получить пересечение {1,2,3,4,5} и {1,2,3 ,4,6}, если вы обновляете пересечения при вставке элементов в дерево.

Получить частичные свойства

Вы можете обновить частичные свойства при построении дерева. Допустим, вы вставляете пару (41111, {1,2,3,4,5}). Попытки — это определенные деревья, и это может выглядеть так. Обозначение k,v означает, что это узел с ключом k и значением v.

4,{1,2,3,4,5}
      |
1,{1,2,3,4,5}
      |
1,{1,2,3,4,5}
      |
1,{1,2,3,4,5}
      |
1,{1,2,3,4,5}

В каждом узле на пути вы сохраняете частичное свойство. Теперь при вставке пары (41112,{1,2,3,4,6}) вы обновляете trie:

       4,{1,2,3,4,null}
             |
       1,{1,2,3,4,null}
             |
       1,{1,2,3,4,null}
             |
       1,{1,2,3,4,null}
      /                \
1,{1,2,3,4,5}     2,{1,2,3,4,6}

И снова, если вы вставите 41234,{1,2,345,87,65}, это будет выглядеть так:

              4,{1,2,null,null,null}
                         |
              1,{1,2,null,null,null}
             /                      \
       1,{1,2,3,4,null}          2,{1,2,345,87,65}
             |                           |
       1,{1,2,3,4,null}          3,{1,2,345,87,65}
      /                \                 | 
1,{1,2,3,4,5}     2,{1,2,3,4,6}  4,{1,2,345,87,65}

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

person T. Claverie    schedule 17.05.2016
comment
полностью согласен .. теперь мне не нужно заканчивать свой ответ ^^. Hashmap (любая реализация карты) — совершенно неправильная структура данных. - person Rainer; 17.05.2016
comment
Спасибо за ваши предложения. Но проблема все еще заключается в получении частичных свойств. Что до сих пор я вручную просматриваю каждую запись и выясняю это. Итак, подход выглядит следующим образом: сначала вручную найти все возможные частичные данные, а затем подготовить Trie. - person Khandekar Mohammad Saleh; 17.05.2016
comment
Я добавил пример того, что имел в виду, и это более эффективно, чем хранить 6 разных HashMap и вычислять все возможные комбинации и частичные свойства. - person T. Claverie; 17.05.2016
comment
Только одно последнее сомнение. Как я вижу, операция поиска для Trie займет больше времени, чем HashMap, чтобы получить свойство для любого ключа, который мне нужно пройти от одного узла к другому, где, как и для HashMap, это будет просто поиск на основе индекса (при условии, что моя хеш-функция такой эффективный). - person Khandekar Mohammad Saleh; 18.05.2016
comment
Это интересный вопрос. Исходя из своего опыта, я сравнил базовое дерево (не оптимизированное) с java HashMap, и мое дерево было на несколько процентов менее эффективным, чем хэш-карта, в рандомизированной последовательности put/get/delete. (правда ключи были длиннее ~15-20 символов). Итак, мой ответ: я не знаю, вам нужно сравнить его, чтобы получить ответ. Но при правильной реализации я уверен, что у вас не будет сумасшедшей потери производительности. И с некоторыми оптимизациями вы, скорее всего, сможете конкурировать с HashMap. - person T. Claverie; 18.05.2016
comment
Я попробую оба подхода и экстраполирую свои результаты и посмотрю, какой из них более осуществим, поскольку количество необработанных данных может увеличиться в будущем. - person Khandekar Mohammad Saleh; 18.05.2016