两个列表中匹配元素的数量

Question

我有很多套两条线。我试图确定这两个字符串中匹配元素的数量。规则是，如果字符串共享一个公共字母，这是一点，顺序确实重要，但第一个字符串中的每个字母只能匹配第二个字符串中的一个字母。所以在字符串'aaaab'，'acccc'中，只授予1点，因为第二个字符串中只有一个'a'匹配。以下是几个例子：

aaabb  bbaaa  5
aabbb  bbbaa  5
aaabb  aabbb  4
aaabb  ccaaa  3
aaaaa  bbbbb  0
ababa  babab  4
aabcc  babaf  3
abcde  abfgh  2
bacde  abdgh  3

希望你能理解它的工作原理。在

这里是我所能想到的最高效的代码，但是它非常复杂。我希望有人能想出更好的办法。在

^{pr2}$

当然这不是最好的办法，但我还没能想出别的办法。我试着用Counter创建一个算法，然后做guess&solution，这很有效，但是结果慢了很多。有人有什么想法吗？在

Answer 1

你可以用NumPy以矢量化的形式来做！在

import numpy as np

counts1 = np.bincount(np.array('aaadez', 'c').view(np.uint8), minlength=128)
counts2 = np.bincount(np.array('eeeedddddaa', 'c').view(np.uint8), minlength=128)
np.min((counts1, counts2), axis=0).sum()

counts1看起来像这样：

^{pr2}$

这是一个由ASCII码索引的数组。非零元素位于位置97、100和101，即ASCII“a”、“d”和“e”。然后我们执行一个成对的min（），然后用sum得到分数（在本例中是4）。在

这个解决方案的一个优点是，您可以将它应用于任意多个字符串，而不会降低效率，甚至非常长的字符串也会非常快，因为Python本身没有循环，只在编译过的NumPy代码中。在

在编辑之前，我使用Pandas和SciPy有一个类似但速度较慢、更复杂的解决方案。这里是：

import scipy.stats
import numpy as np
import pandas

x1 = scipy.stats.itemfreq(np.array('aaade', 'c').view(np.uint8))
x2 = scipy.stats.itemfreq(np.array('bbacadde', 'c').view(np.uint8))
merged = pandas.merge(pandas.DataFrame(x1), pandas.DataFrame(x2), on=0)
np.sum(np.min(merged.values[:,1:], axis=1))

结果是4.0。前两行将字符串转换为整数数组，并运行itemfreq（）计算每个字符出现的次数。在本例中，x1为：

arrray([[  97.,    3.],
        [ 100.,    1.],
        [ 101.,    1.]])

然后，我们通过第0列联接两个表，删除另一个表中不存在的任何字符：

     0  1_x  1_y
0   97    3    2
1  100    1    2
2  101    1    1

然后我们做一个最小值求和得到最后的分数（在这个例子中是2+1+1）。在

Answer 2

这是

list_a = list("aabbb")
list_b = list("bbbaa")

list_c = set(list_b)

counter = 0

for i in list_c:
    if i in list_b:
        counter = list_a.count(i)
        print "counter : %s  element : %s" %(counter,i )

我只想展示如何计算公共元素，你可以改变代码作为计数器结果的总和。在

Answer 3

只需使用list的remove()方法而不是使用index()进行查找，就可以获得大约10%*的速度。在

另外，您不需要将guess复制到list中。在

def Score(guess, solution):
    solution = list(solution)
    c = 0
    for g in guess:
        if g in solution:
            c += 1
            solution.remove(g)

    return c

---

*至少这是我在我的机器上测量的