Python中两个列表的全部比较

Question

我正在努力解决一些性能问题。 手头的任务是提取两个字符串之间的相似度值。对此，我正在使用fuzzywuzzy：

from fuzzywuzzy import fuzz 

print fuzz.ratio("string one", "string two") 
print fuzz.ratio("string one", "string two which is significantly different") 
result1 80 
result2 38 

但是，这是可以的。我面临的问题是我有两个列表，一个列有1500行，另外一个列表有数千列。我需要比较第一个元素和第二个元素的所有元素。 for循环中的简单操作将需要大量的时间进行计算。

如果有人有一个建议，我怎么能加快这一点，这将不胜感激。

Answer 1

如果您需要统计每个语句出现的次数，那么不会，我不知道如何在比较每个列表中的元素所需的n^2操作上获得巨大的加速。您可以通过使用长度来避免某些字符串匹配，以排除匹配可能发生的可能性，但您仍然嵌套for循环。您可能会花费更多时间来优化它，而不是它可以节省的处理时间。

Answer 2

我做我自己的东西给你（蟒蛇2.7）：

from __future__ import division 

import time 
from itertools import izip 

from fuzzywuzzy import fuzz 


one = "different simliar" 
two = "similar" 


def compare(first, second): 
    smaller, bigger = sorted([first, second], key=len) 

    s_smaller= smaller.split() 
    s_bigger = bigger.split() 
    bigger_sets = [set(word) for word in s_bigger] 

    counter = 0 
    for word in s_smaller: 
     if set(word) in bigger_sets: 
      counter += len(word) 
    if counter: 
     return counter/len(' '.join(s_bigger))*100 # percentage match 
    return counter 


start_time = time.time() 
print "match: ", compare(one, two) 
compare_time = time.time() - start_time 
print "compare: --- %s seconds ---" % (compare_time) 
start_time = time.time() 
print "match: ", fuzz.ratio(one, two) 
fuzz_time = time.time() - start_time 
print "fuzzy: --- %s seconds ---" % (fuzz_time) 
print 
print "<simliar or similar>/<length of bigger>*100%" 
print 7/len(one)*100 
print 
print "Equals?" 
print 7/len(one)*100 == compare(one, two) 
print 
print "Faster than fuzzy?" 
print compare_time < fuzz_time 

所以我觉得我的速度更快，但对您更准确？你决定。

编辑 现在不仅速度更快，而且更准确。

结果：

match: 41.1764705882 
compare: --- 4.19616699219e-05 seconds --- 
match: 50 
fuzzy: --- 7.39097595215e-05 seconds --- 

<simliar or similar>/<length of bigger>*100% 
41.1764705882 

Equals? 
True 

Faster than fuzzy? 
True 

当然，如果你有话请检查像fuzzywuzzy的话，那么在这里你去：

from __future__ import division 
from itertools import izip 
import time 

from fuzzywuzzy import fuzz 


one = "different simliar" 
two = "similar" 


def compare(first, second): 
    smaller, bigger = sorted([first, second], key=len) 

    s_smaller= smaller.split() 
    s_bigger = bigger.split() 
    bigger_sets = [set(word) for word in s_bigger] 

    counter = 0 
    for word in s_smaller: 
     if set(word) in bigger_sets: 
      counter += 1 
    if counter: 
     return counter/len(s_bigger)*100 # percentage match 
    return counter 


start_time = time.time() 
print "match: ", compare(one, two) 
compare_time = time.time() - start_time 
print "compare: --- %s seconds ---" % (compare_time) 
start_time = time.time() 
print "match: ", fuzz.ratio(one, two) 
fuzz_time = time.time() - start_time 
print "fuzzy: --- %s seconds ---" % (fuzz_time) 
print 
print "Equals?" 
print fuzz.ratio(one, two) == compare(one, two) 
print 
print "Faster than fuzzy?" 
print compare_time < fuzz_time 

结果：

match: 50.0 
compare: --- 7.20024108887e-05 seconds --- 
match: 50 
fuzzy: --- 0.000125169754028 seconds --- 

Equals? 
True 

Faster than fuzzy? 
True 

Answer 3

最好的解决方案我可以想到的是使用IBM Streams framework来并行化你基本上不可避免的O（n^2）解决方案。

使用框架，你就可以写类似这样

def matchStatements(tweet, statements): 
    results = [] 
    for s in statements: 
     r = fuzz.ratio(tweet, s) 
     results.append(r) 
    return results 

单线程内核然后使用类似于此

def main(): 
    topo = Topology("tweet_compare") 
    source = topo.source(getTweets) 
    cpuCores = 4 
    match = source.parallel(cpuCores).transform(matchStatements) 
    end = match.end_parallel() 
    end.sink(print) 

这个多线程的处理设置并行化，大幅加快速度，同时节省您自己实现多线程细节的工作（这是Streams的主要优势）。

这个想法是，每条推文都是一个Streams元组，要跨多个处理元素进行处理。

Streams的Python拓扑框架文档是here，并且parallel运算符特别描述了here。