在python中劃分姓氏的最快方法

我有一個包含12K個亞洲姓氏的人口普查名單和一個200K名單的列表。我想根據他們的姓氏出現在我的12K名單上，將這20萬人歸類爲亞洲人或非亞洲人。在python中劃分姓氏的最快方法

有沒有一種快速的方法來驗證列表中的某個元素是否包含12K列表中的某個姓氏？

2016-07-24 NicolasVega

從您的姓氏列表中做一個'''set'''，然後[測試成員資格]（https://docs.python.org/3/reference/expressions.html#membership-test-operations） – wwii

這是社會偏見考慮名稱 - >種族甚至動機種族分類本身是相當令人不安的：https://techcrunch.com/2015/08/02/machine-learning-and-human-bias-an-uneasy-pair/和http://www.fatml.org/cfp.html – alvas

OP也會有一些含糊不清的分類，如Lee或Long。非亞洲人也可以擁有這些名字。 –

-1

取決於你的意思是「快」。

James建議使用Python的內置set來測試成員資格。 Python的set實現使用散列表。 平均值時間複雜度爲O（1），但最壞的情況可以爲O（n）其中n是亞組姓氏的基數。因此，在最壞情況的情況下，您的可能只是以O（mn）而不是O（m）結尾，其中m是要歸類的名稱集合的基數。

僅供參考，請參閱：https://wiki.python.org/moin/TimeComplexity

如果要對最壞的情況下保證，你可以用排序集n和做二進制搜索實現它。這將以O（m lg n）時間複雜度結束。

二進制搜索：https://docs.python.org/3.1/library/bisect.html

這真的取決於哈希函數如何適用於您的數據。

來源

2016-07-24 04:01:05

請加_why_你的解決方案是最快的。根據[James]（http://stackoverflow.com/a/38548652/5488275）的回答，對於這個特定問題，您的方法可能會很慢。 –

@NanderSpeerstra我編輯了答案。基本上這是最壞的保證。 –

當你對字符串進行哈希處理時，遇到最壞情況的機會很少。除非你正在編寫你自己的散列函數，否則你不太可能遇到最糟糕的情況*內置的函數肯定足夠強壯以處理字符串。我刪除了我的downvote，因爲你的答案現在增加了一些東西，但是肯定值得一提的是，提問者在這種最壞的情況下運行起來並不是天文數字。 – James

要做到這一點，最好的方法是將12K列表轉換爲集合數據結構。然後，您可以遍歷人口普查數據並檢查每個數據是否在集合中。

# O(n) where n is the length of the surname_list 
surname_set = set(surname_list) 

for name in census: 
    # This is now O(1) operation 
    if name in surname_set: 
     do whatever...

這是幾乎可以肯定來完成你的Python或任何語言所需要的，應該是相當快的一個200K大小的名單最快的方法。

Wai Leong Yeow提出了一個二進制搜索，它比直接檢查列表更快，但對200K不同名稱仍然是O（log n）操作，其中N爲12,000，這意味着它可能會更多比迭代部分慢10倍（這是一種簡化 - 實際上有一些常數因子被大O標記掩蓋，但恆定時間解決方案肯定仍然更快）。對O（n log n）進行排序需要花費O（n）個時間，這意味着該方法的預處理速度也更快。

來源

2016-07-24 04:08:53 James

這取決於你真正的問題。你想機器學習（如你標籤：分類）來預測亞洲/非亞洲的名字？

如果是：嘗試一些半監督方法。要做到這一點，首先隨機選擇（接近10％）200k數據，然後在12k中搜索它，如果存在，將其標記爲1，否則將其標記爲0.然後使用一些分類算法，如隨機森林，SVM或KNN。你也可以模擬你的名字，比如Bag Of word（在你的問題袋子裏！或類似的東西）：https://en.wikipedia.org/wiki/Bag-of-words_model

分類任務，看看scikit學習lib目錄下：http://scikit-learn.org/

如果NO（你不想使用機器學習的解決方案）：存在着一些快速字符串搜索算法，用一些Technics在其他字符串的語料庫中搜索字符串。有很多算法，如博耶·摩爾：https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

有關詳細信息這可能是不錯的：https://softwareengineering.stackexchange.com/questions/183725/which-string-search-algorithm-is-actually-the-fastest

來源

2016-07-24 15:26:34 Masoud

訓練一個模型來模擬在你已經擁有的列表中查找單詞的過程是什麼？如果你想訓練一個模型，發現負面數據*不是很可能是假陰性。如果你想做直接的字符串匹配，有一個更簡單的解決方案：'set（）'。 – alexis

@alexis，正如我所提到的，它依賴於一個問題，例如，您想要每秒對200k名稱進行分類，並希望以儘可能快的速度檢索結果（因爲用戶問'最快的方式'），我提到'它取決於' – Masoud

你是說統計分類器會比集合中的查找更快嗎？這是不可能的。 – alexis

我會推薦給任何訓練機器學習模型之前在第一步驟中使用local sensitive hashing。這可能會有幫助，因爲你沒有很多功能。如果你想要更強大的東西，你可以使用樸素貝葉斯和一些特徵工程。

來源

2016-07-25 18:34:16

在python中劃分姓氏的最快方法

回答

相關問題