Индекс поиска в памяти для приложения занимает слишком много памяти - есть предложения?

В нашем настольном приложении мы реализовали простую поисковую систему с использованием инвертированного индекса.

К сожалению, некоторые наборы данных наших пользователей могут стать очень большими, например занимает ~ 1 ГБ памяти до создания инвертированного индекса. Сам инвертированный индекс занимает много памяти, почти столько же, сколько индексируемые данные (еще 1 ГБ ОЗУ).

Очевидно, что это создает проблемы с ошибками нехватки памяти, поскольку 32-разрядный лимит Windows в 2 ГБ памяти на приложение исчерпан, или пользователи с компьютерами с меньшими характеристиками изо всех сил пытаются справиться с потребностями в памяти.

Наш инвертированный индекс хранится как:

Dictionary<string, List<ApplicationObject>>

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

Итак, мой вопрос: можно ли хранить поисковый индекс более эффективно с точки зрения пространства? Возможно, необходимо использовать другую структуру или стратегию? Как вариант, можно ли создать своего рода CompressedDictionary? Поскольку он хранит много строк, я ожидал, что он будет очень сжимаемым.


search c# optimization memory search-engine
person RickL    schedule 21.10.2008    source источник

Ответы (7)


arrow_upward
3
arrow_downward

Если будет 1 ГБ ... поместите на диск. Используйте что-то вроде Berkeley DB. Это все равно будет очень быстро.

Вот проект, который предоставляет ему интерфейс .net:

http://sourceforge.net/projects/libdb-dotnet

person bobwienholt    schedule 21.10.2008
comment
Я бы хотел по возможности избежать этого, так как будет проще иметь индекс поиска в памяти. Но, возможно, это невозможно, но мне кажется, что это должно быть возможным. - person RickL; 21.10.2008

arrow_upward
3
arrow_downward

Я вижу несколько решений:

  1. Если у вас есть ApplicationObjects в массиве, сохраните только индекс - может быть меньше.
  2. Вы можете использовать немного C ++ / CLI для хранения словаря, используя UTF-8.
  3. Не пытайтесь сохранять все разные строки, используйте Trie
person MSalters    schedule 21.10.2008
comment
Для пункта 1) они не хранятся в массиве, но имели ли вы в виду сохранить индекс вместо строкового ключа? Тогда как искать по строкам? Или вы имели в виду вместо List ‹ApplicationObject›, чтобы иметь List ‹int›? Я предполагаю, что это может быть меньше, но, вероятно, не очень много. - person RickL; 21.10.2008

arrow_upward
3
arrow_downward

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

Я предлагаю вам примерно узнать, какова частота - сколько из ваших словарных статей имеют списки с одним элементом, сколько - с двумя списками элементов и т. Д. Вы можете потенциально хранить несколько отдельных словарей - один для «У меня есть только один элемент» (прямое сопоставление), затем «У меня есть два элемента» (сопоставление со структурой Pair с двумя ссылками внутри) и т. д. до тех пор, пока это не станет глупым - вполне возможно, примерно при трех записях - после чего вы вернетесь к обычным спискам. Инкапсулируйте все в простом интерфейсе (добавляйте / извлекайте записи). Таким образом, у вас будет намного меньше потраченного впустую места (в основном пустые буферы, счетчики и т. Д.).

Если все это не имеет особого смысла, дайте мне знать, и я постараюсь придумать какой-нибудь код.

person Jon Skeet    schedule 21.10.2008
comment
Это интересное наблюдение ... да, я думаю, что большинство списков будут очень маленькими. С вашим предложением, я предполагаю, что создание инвертированного индекса займет больше времени, поскольку вам придется перемещать элементы между словарями с 1, 2 и т. Д., Но потенциально может сэкономить место. - person RickL; 21.10.2008
comment
Честно говоря, я подозреваю, что разница в производительности будет довольно небольшой, но да, будут некоторые накладные расходы. Определенно стоит проверить дистрибутив, прежде чем писать его :) - person Jon Skeet; 21.10.2008
comment
Одна мысль сделать это потенциально дешевле для начала: просто иметь одну строку Dictionary ‹, IEnumerable ‹ApplicationObject››. Это означает наличие объекта для каждого значения, а не использование структур, чтобы избежать этого, но вам нужно будет только заменить запись в словаре вместо удаления / добавления - person Jon Skeet; 21.10.2008
comment
Правда, завтра попробую и сообщу, что изменилось. - person RickL; 21.10.2008
comment
Я исследовал, и думаю, что это изменение окажет некоторое влияние, хотя и не сильно. например около 50% списков состоят из 1, 2 или 3 элементов. Но в целом эти списки составляют около 5% от общего количества элементов. - person RickL; 22.10.2008

arrow_upward
1
arrow_downward

Я согласен с bobwienholt, но если вы индексируете наборы данных, я предполагаю, что они пришли откуда-то из базы данных. Имеет ли смысл просто искать это с помощью поисковой системы, такой как DTSearch или Lucene.net?

person Andrew Cowenhoven    schedule 21.10.2008
comment
Возможно, но я полагаю, что это было бы сложнее? то есть applicationObject хранятся во многих разных таблицах, которые сопоставляются с разными конкретными объектами приложения. Ах, также наше приложение буферизуется, поэтому набор данных в памяти может быть не синхронизирован с базой данных. - person RickL; 21.10.2008

arrow_upward
1
arrow_downward

Вы могли бы воспользоваться подходом Люсена. Сначала вы создаете поток в памяти с произвольным доступом (System.IO.MemoryStream), этот поток отражает поток на диске, но только его часть (если у вас неправильная часть, загрузите еще одну с диска) . Это вызывает одну головную боль, вам нужен формат с отображением файлов для вашего словаря. В Википедии есть описание техники разбиения по страницам.

По сценарию с отображением файлов. Если вы откроете Reflector и отразите класс Dictionary, вы увидите, что он состоит из ведер. Вероятно, вы можете использовать каждую из этих корзин как страницу и как физический файл (таким образом вставка выполняется быстрее). Затем вы также можете свободно удалять значения, просто вставляя в файл значение «элемент x удален» и время от времени очищая файл.

Кстати, в ведрах хранятся значения с одинаковыми хешами. Очень важно, чтобы ваши значения, которые вы храните, переопределяли метод GetHashCode () (и компилятор предупредит вас о Equals (), поэтому также переопределите его). Если вы это сделаете, вы получите значительное увеличение скорости поиска.

person Jonathan C Dickinson    schedule 22.10.2008

arrow_upward
1
arrow_downward

Как насчет использования Win32 API файла с отображением памяти для прозрачной поддержки структуры памяти?

http://www.eggheadcafe.com/articles/20050116.asp имеет PInvokes необходимо для его включения.

person stephbu    schedule 22.10.2008
comment
Начиная с .NET Framework версии 4, вы можете использовать управляемый код для доступа к файлам с отображением памяти таким же образом, как собственные функции Windows обращаются к файлам с отображением памяти, как описано в разделе «Управление файлами с отображением памяти в Win32 в библиотеке MSDN. msdn.microsoft.com/en-us/library/dd997372.aspx - person Tony; 07.04.2012

arrow_upward
0
arrow_downward

Индекс только добавляется или вы также удаляете из него ключи?

person Lasse V. Karlsen    schedule 21.10.2008
comment
Ключи должны быть удалены из индекса, если и когда будет удален указанный ApplicationObject. - person RickL; 21.10.2008