Эффективность обратного индекса Python

Question

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

Теоретически, создание инвертированного индекса набора документов D, каждый с уникальным идентификатором doc_id, должен включать:

1. Анализ / выполнение лексического анализа каждого документа в D
2. Удаление стоп-слов, выполнение стволов и т. Д.
3. Создание списка всех (word,doc_id) пар
4. Сортировка списка
5. Сжатие дубликатов в {word:[set_of_all_doc_ids]} (инвертированный индекс)

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

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

В SO здесь есть несколько других постов об инвертированных индексах Python, и, как и в текущей реализации MY, они используют словари, отображающие ключи в списки (или наборы). Можно ли ожидать, что этот метод имеет аналогичную производительность с языком, который позволяет прямое кодирование указателей на связанные списки?

Answer 1

Есть несколько вещей, которые можно сказать:

1. Если произвольный доступ требуется для конкретной реализации списка, связанный список не оптимально (независимо от используемого языка программирования).Чтобы получить доступ к i-му элементу списка, связанный список требует, чтобы вы перебрали весь путь от 0-го до i-го элемента.Вместо этого список должен храниться как один непрерывный блок (или несколько больших блоков, если он очень длинный).Списки Python [...] хранятся таким образом, поэтому для начала список Python должен быть достаточно хорошим.

2. В Python любое назначение a = bобъекта b, который не является базовым типом данных (например, int или float), выполняется внутренне с помощью , передавая указатель и увеличивая счетчик ссылок доb.Таким образом, если b является списком или словарем (или определенным пользователем классом, в этом отношении), это в принципе не сильно отличается от передачи указателя в C или C ++.

3. Однако, очевидно, есть некоторые издержки , вызванные а) подсчетом ссылок и б) сборкой мусора.Если бы реализация была для учебных целей, то есть для лучшего понимания концепции инвертированной индексации, я бы об этом не беспокоился.Но для серьезной, высоко оптимизированной реализации использование чистого Python (а не, например, C / C ++, встроенного в Python) не рекомендуется.

4. Поскольку вы оптимизируете реализацию своего списка публикацийКроме того, вы, вероятно, увидите необходимость: a) делать случайные вставки, b) сохранять их отсортированными и c) сохранять их сжатыми - все одновременно.На этом этапе стандартный список Python больше не будет достаточно хорошим, и вы можете захотеть посмотреть на реализацию более оптимизированного представления списка в C / C ++ и встраивать его вPython.Однако даже тогда придерживаться чистого Python, возможно, будет возможно.Например, вы можете использовать большую строку для реализации списка и использовать itertools и buffer для доступа к определенным частям способом, который в некоторой степени похож на арифметику указателей.

5. При работе со строками в Python следует всегда помнить о том, что, несмотря на то, что я сказал выше об операциях присваивания, операция подстроки text[i:j] включает в себя создание фактической (глубокой) копии подстроки , а не просто увеличение счетчика ссылок.Этого можно избежать, используя тип данных buffer, упомянутый выше.

Answer 2

Вы можете увидеть код и документацию для инвертированного индекса в Python по адресу: http://www.ssiddique.info/creation-of-inverted-index-and-use-of-ranking-algorithm-python-code.html

Скоро я буду кодировать его на C ++ ..