此問題與Simulating file system access有關。從文件系統中隨機選擇一個文件
我需要隨機選擇文件和目錄作爲文件操作的參數，如重命名，寫入，讀取等。我打算做的是將所有文件和目錄與他們的路徑列表並隨機選擇這個清單。但是，隨着文件和目錄在實際文件系統中的創建和刪除，列表也必須更新。我發現維護列表並以這種方式更新它是低效的，並且它也必須是原子的，以便稍後的操作不訪問先前操作刪除的文件。
你能否提出一種選擇文件的不同方式..可能有點直接從文件系統中完成...但是我們如何知道文件路徑。
感謝
我發現了一些有趣的事情在這裏Randomly selecting a file from a tree of directories in a completely fair manner特別是在 邁克爾·巴伯的答案，但是不能夠完全按照它由於我的無知蟒
你不想嘗試維持當文件系統在那裏時的文件列表。你應該能夠從C.從根目錄走，從中選擇一個隨機文件。您可以選擇一個隨機最大深度，如果您在此之前或之前擊中了常規文件，請使用它。如果是目錄，則重複最大深度。如果它是一個特殊的文件，可能會重新開始。
這應該很快。操作不應該是原子的。如果文件不存在，當您想要進行操作時，請重試。不應該太複雜。您可以在找到目標文件時建立路徑。這將比直接與fs直接混淆（我假設你的意思是低得多）並且應該很容易實現。
我認爲分佈將有很大的不同，取決於結構。 – 2011-09-02 06:04:32
@ keith.layne它將如何隨機？我的意思是，當我從根行走時，我總是沿同一個子樹行走，因此從某些子樹中選擇文件的可能性要大得多。事實上，一些文件可能永遠不會被選擇。我可能不瞭解你的方法。 –
如果你隨機選擇根目錄，你爲什麼總是沿着同一條路走？當然，在計算機上隨機通常不是隨機的。隨機意味着每個文件具有完全相同的選擇機會。我說這是一個昂貴的目標。如果你正在模擬文件訪問，那麼你只需要足夠隨機的來滿足你的模擬需求。 –
這是我提出的解決方案。它不是最快的，但應該是快速的（準備後），只使用適度的內存，並且「相當分佈」。這是當然的，100％未測試和有點複雜（複雜如保持RB-樹或類似，反正） - I皮蒂一個用於具有利用C ;-)
對於在每個目錄目標域，使用文件系統的深度優先遍歷來構建目錄樹，並記錄「之前」文件計數（到目前爲止，在樹中發現的文件）和「之後」文件計數（「之前」計數加上數字目錄中的文件）。它不應該存儲文件本身。 Fast way to find the number of files給出了一些C代碼示例。它仍然需要迭代目錄內容，但不需要自己存儲文件。
計算樹中文件的總數。 （這應該只是樹中最後一個節點的「之後」計數。）
選擇範圍[0，最大文件數）範圍內的一個隨機數。
導航到樹中的節點，使「之前」文件數< =隨機數<「之後」文件數。這只是沿着（RB-）樹形結構走，它本身就是O（lg n）或類似的。
在與所選節點相關的目錄中選擇一個隨機文件 - 確保再次對目錄進行計數並將其用作選擇中的[0，limit]（在跑步 - 由於併發問題導致的最終結果）。如果文件數量發生變化，請確保使用此類信息更新樹。如果目錄已被刪除等，也更新/修復樹（這裏額外的完整計數不應該像聽起來那麼糟糕，因爲readdir（平均）必須已經瀏覽通過目錄中1/2的條目。但是，應該探討重計的好處，如果有的話）。
根據需要重複步驟2-5。
定期重建整個樹（步驟＃1）以解釋文件系統的變化。刪除/添加文件將緩慢地歪曲隨機性 - 步驟＃5可以幫助在某些情況下更新樹。重建的頻率應通過實驗確定。也可以通過重建父/祖父節點或每次通過的[隨機]子節點來減少錯誤介紹等。使用修改的時間作爲檢測變化的快速方式也值得研究。
快樂編碼。
:-)。它確實很複雜 –
在我的linux的非常小的VM安裝上，fsck告訴我'/ dev/sdb1：340669/8536064文件'。我不記得哪個數字很重要，但我敢打賭這是第二個。需要多長時間才能完成DFS？爲什麼模擬FS訪問，如果它不是整個FS？我誤解了，它只是一個子樹？我只是爲了*時尚和空間需求很小的*發行。 –
@ keith.layne整個樹結構（對於任何需要的根目錄而言，它可能僅在'/ opt'上對我所知道的只有需要，並且與將它用作根而不是'/'不同，只是一個開始樹;-)被讀取 - 但只保留結構本身和文件數量。它只需要標準的POSIX API，因此與原始文件系統或特定的[內核級別]功能相比，它可能相對較慢，而且更「手動」。至於「多長時間」，這取決於環境因素（這一步*不便宜* - 改變後的措辭），這就是爲什麼攤銷糾正可能是有益的。 – 2011-09-02 07:09:43
您應該知道的是，每個目錄中有多少個文件才能選擇您應該穿越的目錄。避免遍歷符號鏈接並在符號鏈接中計數文件。
您可以使用與pst相似的解決方案。
示例您有3個目錄，每個目錄中有20,40和1000個文件。 你使總數[20,60,1060]，你選擇隨機數0-1060。如果這個數字大於或等於60，你去第三個文件夾。
一旦你到達文件夾沒有文件夾，你就停止遍歷。
通過此路徑查找隨機文件，您可以像之前一樣應用相同的技巧。
這樣，你會選擇任何文件白色相等的概率。
我的回答幾乎描述了他的臨時解決方案。隨機化最大深度應該有所幫助。我認爲這個問題最大的不同在於它涉及到文件系統的一個子樹。我不想經常從根目錄走，只是爲了確保每個文件都有被選中的機會。 –
該操作沒有「是原子的」 - 在選擇一個文件（來自緩存列表）之後，可以對其進行測試。另一位（不使用各種通知系統）會變得相當昂貴。 – 2011-09-02 06:02:59
@pst ...啊，沒有想到像測試存在的簡單興奮。謝謝。沒有得到你的意思，「另一位（沒有使用各種通知系統）可能會相當昂貴」 –