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++編碼來呢..