Алгоритм хранения связей предмет-предмет - PullRequest
Новая
       15

Алгоритм хранения связей предмет-предмет

2 голосов
/ 30 июля 2011

Мне нужна помощь для эффективного хранения некоторых данных.У меня есть большой список объектов (около 100 000) и я хочу хранить ассоциации между этими элементами с коэффициентом.Не все предметы связаны, на самом деле у меня что-то около 1 млн.Ассоциации.Мне нужен быстрый доступ к этим ассоциациям при ссылках по двум пунктам.Я сделал такую ​​структуру: 

Map<Item, Map<Item, Float>>

Я пробовал это с HashMap и Hashtable.Оба работают нормально и достаточно быстро.Моя проблема в том, что все, что Карты создают много накладных расходов в памяти, конкретные для данного сценария более 300 МБ.Есть ли реализация карты с меньшими затратами?Может быть, есть лучший алгоритм для хранения таких данных?

Ответы [ 2 ]

1 голос
/ 30 июля 2011

Вот несколько идей:

  1. Хранить в Map<Pair<Item,Item>,Float>.Если вы беспокоитесь о выделении нового Pair для каждого поиска, и ваш код синхронизируется, вы можете сохранить один экземпляр пары поиска.

  2. Ослабьте внешнюю карту, чтобы она была Map<Item, ?>.Значение может быть простым {Item,Float} кортежем для первой ассоциации, небольшим массивом кортежей для небольшого числа ассоциаций, а затем перейти к полноценной карте.

  3. Использовать коллекции Commons 'Flat3Map для внутренних карт.

  4. Если вы строго контролируете Предметы, и эквивалентность Предмета является ссылочной (т.е. каждый экземпляр Предмета не является equal к любому другому экземпляру Item, тогда вы можете пронумеровать каждый экземпляр. Так как вы говорите о <2 миллиардах экземпляров, один Long будет представлять пару Item с некоторой битовой манипуляцией. Тогда карта становится намного меньше, если вы используете Trove's <a href="http://trove4j.sourceforge.net/javadocs/gnu/trove/TLongObjectHashMap.html" rel="nofollow">TLongObjectHashMap

0 голосов
/ 30 июля 2011

У вас есть два варианта.

1) Сократить то, что вы храните.

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

Другая возможность, которая может сократить относительно небольшой объем ОЗУ, - дать указание вашей JVM использовать указатели сжатых объектов. Это может сэкономить вам около 3 МБ с вашим текущим размером данных.

2) Расширьте свои возможности.

Я не уверен, каково ваше ограничение (оперативная память на рабочем столе, сериализация и т. Д.), Но вы можете либо расширить размер кучи и разобраться с ним, либо вы можете вытолкнуть его из процесса. Со всеми этими магазинами "NoSQL", один, вероятно, подойдет вашим потребностям. Или индексированная таблица БД может быть довольно быстрой. Если вы ищете простое хранилище ключей-значений, Voldemort чрезвычайно прост в настройке и интеграции.

Однако я не знаю, что вы делаете со своим рабочим набором. Вы можете дать более подробную информацию? Вы выполняете агрегацию, разбиение, кластерный анализ и т. Д.? Где у вас проблемы?

...