Pythonic方法：用最少的運行時間找到第一個匹配路徑

什麼是在Python中用相當低的運行時查找第一個匹配路徑的有效方法？Pythonic方法：用最少的運行時間找到第一個匹配路徑

例如，

我作爲輸入的路徑：

test1/testA/testB

和一組可以匹配路徑（在我的使用情況下，這將是在千元）。

test1/testB 
test1/testA 
testC/testD

不會有像下面任何重疊的路徑和只能被匹配到一個路徑：

test1/testA 
test1/testA/testB

在上面的例子中，由於是test1/testA/testB在test1/testA，我想返回test1/testA。

我的方法是構建一個內存樹並在樹中標記每個節點（如果它是端點的話）。然後，我會每次遍歷樹來查找路徑是否可以匹配。不幸的是，這需要一點點工作。

是否有一個Python函數或庫很容易完成這個工作？或者我需要從頭開始寫這個？

來源

2014-10-02 Andy

你能解釋一下你試圖解決的問題嗎？可能有比你想要的更好的方法。 – 2014-10-02 17:03:00

當你說「沒有重疊的路徑」時，你的意思是所有的終端都是唯一的嗎？ – theodox 2014-10-02 17:03:51

我試圖解決一個問題，我有一個文件路徑，我需要它來自的項目。我有一個項目名稱及其相關路徑的列表。但是，文件路徑可能不一定與項目路徑直接匹配，但可能駐留在項目路徑中。我可能會每秒多次調用此函數，並且可能會有數千個項目路徑。 – Andy 2014-10-02 17:10:31

這並不直接解決「如何構建算法」的問題（貌似更多的澄清，從上述意見需要），但...

如果這些是實際的現實世界的文件/目錄路徑，那麼您可能需要在標準庫中使用os.path.commonprefix function。它可以與OS /平臺無關的方式匹配，以及路徑的通用前綴。

在開始之前，您還應該將所有路徑標準化爲絕對路徑（使用os.path.abspath）或相對路徑（使用os.path.relative）。

來源

2014-10-02 17:05:14

如果輸入路徑不是太長，則以斜線分隔組件;並且如果可能的匹配集合全部是全部分量; 即，不會出現類似stA/tes的東西;那麼我會這樣做。

Read the set of possible matches into a `set`. 
Divide the input path into all possible substrings; in this case: 
test1 
test1/testA 
test1/testA/testB 
testA 
testA/testB 
testB 

For `n` components there will be `n(n+1)/2` substrings. 

Search the `set` for each one: if substring in matches: ...

來源

2014-10-02 17:11:14

對於給出你可以通過索引你與該路徑的頭部和尾部的路徑列表削減搜索空間下來很遠的問題：

paths =[ 
    'a/b/c/d', 
    'a/b/d', 
    'a/c/b/s/e', 
    'a/e', 
    'a/b/d/e' 
] 

def head_and_tail(pth, offset = -1): 
    splitted = pth.split('/') 
    return splitted[0], splitted[offset] 

index = dict ([(head_and_tail(p),[]) for p in paths]) 
# produce a dictionary with each head/tail combination as a key and a list as value 

for p in paths: 
    ht = head_and_tail(p) 
    index[ht].append(p) 

# now index contains all paths indexed by their head and tail 

def search (pth): 
    ht = head_and_tail(pth, -2) 
    root = "/".join(pth.split("/"))[:-1][:-1] 
    for item in index[ht]: 
     if item == root: 
     return item 
    return None 

print search ("a/b/c/d/e")

這將很好的工作「廣闊'數據有很多路徑來自獨特的根，或以獨特的葉子結尾。如果數據「根深蒂固」，而且沒有根源，它將不會提供太多加速。

來源

2014-10-02 17:22:54 theodox

Pythonic方法：用最少的運行時間找到第一個匹配路徑

回答

相關問題