（多少）在檢查2個列表時，首先排序的是多少？

我在大約50k個文件中尋找800個元素的列表，每個文件大約50行。（這些是帶有非通用名稱的xml標籤 - 搜索很簡單，因此我沒有使用美麗的湯。）（多少）在檢查2個列表時，首先排序的是多少？

每找到一個元素就會縮短800個元素的列表。

迭代通過文件，

不要緊，我經過第一 - 檢查對所有可能的元素每條線（檢測線的「點」，「流浪者」，「汪汪」，等...）或者一次檢查所有行檢查一個元素（例如，檢查文件中的所有行是否爲「spot」，然後檢查所有行爲「rover」等）。

還是這一切效率低下？（這是使用python）我在想：

for line in somefile: 
     for element in somelist: 
       if re.search(element, line): 
        ....

或：

for element in somelist: 
     for line in somefile: 
       if re.search(element, line): 
        ....

來源

2012-10-20 Donnied

你一般假大數據集做爲所順序訪問的一個，並保持你感興趣的值在內存中或作爲較大數據集的索引。所以是的，這很重要，在你的例子中，你正在尋找多次掃描文件，這是一個批次較慢。

我們舉一個例子，其中每個文件都是50行，並且您要查找800個「單詞」。

for filename in filenames: 
    for line in open(filename): 
     if any(word in line for word in words): 
      pass # do something

由於words是內存和容易掃描，這比在打開每個文件800次好多了 - 這是一個昂貴的操作。

所以，我想我應該說，你應該試圖順序掃描「最昂貴」的數據集（可能不是最長的）。

來源

2012-10-20 14:43:39

要查找的元素是在一個列表中，這是更長的列表（與行相比） - 所以我應該先遍歷它們？ – Donnied

@Donnied我澄清了 - 並檢查出kindall的答案 –

複雜性的順序是O(n*m)，其中n和m可以表示您的列表和文件中的條目數量，因此無論您首先採用哪種方式都無關緊要。

來源

2012-10-20 14:45:23

這就是我的想法。這似乎是多種類型算術的交換性質，但我不確定。 – Donnied

好吧，常數因子可能很重要......如果兩組中的一組非常適合緩存，則使用外部循環在另一組中循環。 –

@DietrichEpp同意。數據訪問的物理特性然後在算法複雜性後出現。 –

描述算法複雜性的big-O符號是相同的，但是如果你的一個迭代文件（例如文件）訪問速度慢很多，並且可能比其他文件大，你應該儘可能少地重複它，即一次。

除此之外，該算法可能更容易編寫或理解這種或那種方式。例如，如果您想要一個列表中的所有字符串與任何正則表達式匹配的列表，那麼首先遍歷字符串列表並檢查每條正則表達式會更容易，當匹配時會跳出內部循環。

其實整個任務可以是一個班輪當你重複這樣的說法：

foundlines = [line for line in inputlines if any(r.search(line) for r in regexes)]

作爲獎勵，你會使用列表理解/發電機表達式得到最快的迭代Python是能夠，和any()。

首先對正則表達式進行迭代，最合適的做法是列出與每個正則表達式匹配的行列表，或者匹配任何正則表達式（包括多個正則表達式）的行的一個大列表（帶有重複項）。如果你想要最終匹配一個正則表達式的行列表，那麼你將需要以某種方式消除重複（在迭代期間或之後），這會影響算法的複雜性。結果可能會以不同的順序出現，這可能是一個問題。

總之，選擇最適合您嘗試解決的問題的方法時，迭代的性能是等價的。

來源

2012-10-20 14:58:11 kindall

我正在看那個。因此，每個文件都被讀入 - 問題是，是通過每行查看所有元素還是遍歷所有查找每個元素的行。看來，鑑於乘法的交換性質並不重要。 – Donnied

增加了一些您可能考慮的因素。 – kindall

我認爲這比我嘗試的解釋+1更容易理解 –

（多少）在檢查2個列表時，首先排序的是多少？

回答

相關問題