在python中对姓氏进行分类的最快方法

Question

我有一份名单，上面有12K个来自人口普查的亚洲姓氏，还有一个名单上有200K个名字。我想根据他们的姓氏是否出现在我的12K名单上，将这20万人归类为亚洲人或非亚洲人。

有没有一种快速的方法来验证列表中的一个元素是否包含12K列表中的一个姓氏？

Answer 1

要做到这一点，最好的方法是将您的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)时间，这意味着这种方法的预处理速度也更快。

Answer 2

这取决于你真正的问题。您是否希望机器学习(如您的标签:分类)来预测亚洲/非亚洲名称？

如果是:尝试一些半监督方法。为此，首先从200k数据中随机选择(接近10%)，然后在12k中搜索它，如果存在，则将其标记为1，否则将其标记为0。然后使用一些分类算法，如随机森林，支持向量机或KNN。你也可以模仿你的名字，比如Bag Of word(在你的字母问题包中！)或者类似的东西)：https://en.wikipedia.org/wiki/Bag-of-words_model

对于分类任务，可以查看scikit-learn lib：http://scikit-learn.org/

如果不是(你不想使用机器学习解决方案)：有一些快速的字符串搜索算法可以通过一些技术在其他字符串的语料库中搜索一个字符串。有很多算法，比如Boyer Moore：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

Answer 3

我建议在训练任何机器学习模型之前的第一步使用local sensitive hashing。这可能会有所帮助，因为你没有太多的功能。如果你想要更强的东西，你可以使用朴素贝叶斯和一些特征工程。