Python倒排索引效率

Question

我在写一些Python代码来实现我最近学习的一些概念，这些概念与倒排索引/发布列表有关。我对Python很陌生，在某些情况下对于它的效率有些麻烦。

理论上，产生一组文档的倒排索引d，每一个独特的ID doc_id应包括：

1. 解析/在d执行每个文档的词法分析
2. 卸下停用词，执行所产生等
3. 创建所有(word,doc_id)双
4. 列表进行排序，列表
5. 凝重复到{word:[set_of_all_doc_ids]}（反向索引）

步骤5通常是由具有包含与元数据字（词频，字节偏移）和指针的贴子列表的字典进行（文件清单它发生在） 。发布列表经常被实现为允许有效的随机插入的数据结构，即链接列表。

我的问题是，Python是一种更高级别的语言，直接使用内存指针（因此链接列表）的东西似乎超出了范围。我在分析之前进行了优化，因为对于非常大的数据集，已经知道效率必须最大化，以保留在合理时间内计算指数的任何能力。

这里有几个关于Python倒排索引的文章，像MY当前的实现一样，它们使用映射键来映射列表（或集合）的字典。有人期望这种方法具有与允许直接编码指向链接列表的指针的语言相似的性能吗？

Answer 1

有许多的话要说：

1. 如果随机存取需要一个特定的列表实现，一个链表是不是最佳（不管编程语言的使用）。要访问列表中的第i个元素，链表需要从0开始迭代到第i个元素。相反，列表应该被存储为一个连续的块（或者如果它非常长，则存储几个大块）。 Python列表[...]以这种方式存储，所以首先，Python列表应该足够好。

2. 在Python，任何分配a = b对象b这不是一个基本数据类型（如int或float）的，由内部执行指针传递和递增引用计数到b 。因此，如果b是一个列表或一个字典（或用户定义的类，就此而言），原则上与在C或C++中传递指针不同。

3. 但是，明显有一些开销引起的a）引用计数和b）垃圾收集。如果实施是为了研究目的，即为了更好地理解倒排索引的概念，我不担心这一点。但对于一个严格的，高度优化的实现，使用纯Python（而不是Python，嵌入到Python中的C/C++）是不可取的。

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++编码来呢..