文件系統的數據結構

我在內存中存儲/緩存文件系統（僅限文件名）以便能夠快速研究àla Everything。因此我不想使用操作系統的內置文件搜索GUI。文件系統的數據結構

我做：

import os 
L = [] 
for root,dirs,files in os.walk(PATH): 
    L.append([root, files])

，結果是這樣的：

[['D:\\', ['a.jpg', 'b.jpg']], 
... 
['D:\\Temp12', ['test.txt', 'test2.txt']]]

的問題是，做研究需要太多的時間，當L將包含數百萬個元素：

query = 'test2' #searching for filename containg this text 
for dir in L: 
    for f in dir[1]: 
     if query in f: 
      print '%s found: %s' % (query, os.path.join(dir[0],f))

事實上，這是一個非常幼稚的搜索，因爲它需要瀏覽ŧ他整個列表找到物品。

如何使查詢速度更快？

也許看起來列表並不是正確的數據結構來做全文研究，有沒有樹狀結構？

來源

2016-12-16 Basj

在Python中，我覺得'字典'是你正在尋找的東西！ – Acepcs

@Acepcs：即使我使用字典'{'D：\\'：['a.jpg'，'b.jpg']，...，'D：\\ Temp12'：['test.txt '，'test2.txt']}'，我將不得不迭代所有數千個鍵/值來進行搜索......你能確切地記住你的想法嗎？ – Basj

我的腦海裏恰好有一個完整的算法。當你瀏覽你的操作系統中的目錄時，試着製作一個文件名字典，每個鍵是字母表中的一個字符，每個值都是一個以該字符開頭的文件名列表，例如'{'a'： ['a3.jpg'，'ab.jpg']，'b'：['banana.gif'，'bad.jpg']}'，所以通過建立前綴鍵可以節省大量的時間。如果你的數據量真的很大，你可以構建嵌套的前綴字典，就像在Python中實現的樹（在一定程度上） – Acepcs

研究一個列表是O（n）時，在研究的字典攤銷O（1）。如果您不需要關聯值，請使用集合。

如果您想了解更多關於這一點：https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

在你的情況，我會用套。它會讓你的查詢更快。

編輯：

你正在做它，檢查比賽的每個文件不能更快這樣的方式。即使你使用字典，你也要檢查每個文件名的匹配。

新的想法：您可以創建所有的文件名作爲密鑰和根爲每個值的字典。這樣您可以稍後重新創建完整路徑。

現在的想法是創建一個樹是每個節點都是一個字母，是每次必做的話（文件名）之間的路徑。這可能很難實現，並且結果可能不會更快，這取決於您構建樹的方式。

你必須記住要檢查每個文件名，並使用列表或字典也不會改變這一點。樹/圖是我能想到的唯一解決方案。

來源

2016-12-16 08:43:00 iFlo

正如其他評論所述，即使我使用字典'{'D：\\'：['a.jpg'，'b.jpg']，...，'D：\\ Temp12'：['' test.txt'，'test2.txt']}'，我將不得不遍歷所有數千個鍵/值來執行搜索......您能詳細說明如何使用'dict'來實現此操作，或者'set'？在我看來，人們必須迭代整個結構才能進行搜索。 – Basj

你可以考慮使用數據庫嗎？

SQLite提供：memory：option，它只在內存中創建數據庫。當然，你可以像其他答案和評論中指出的那樣，優化你的算法和數據結構，但是數據庫一般都已經非常擅長編制索引，而且你不需要設計類似的東西。

您的表格可能只是一個帶有full_path和filename字段的表格，如果您通過文件名索引它，它會很快。這會存儲大量冗餘信息，因爲每個文件都將在full_path中具有完整路徑。更好的解決方案是爲目錄設置一個表格，爲文件設置另一個表格，並且僅從文件中引用目錄以獲取匹配的完整路徑。

只是一個想法。

Hannu

來源

2016-12-16 12:29:16 Hannu

文件系統的數據結構

回答

相關問題