Python 线性搜索效率更高

Question

我有一个关于 Linear Searching 的问题在Python .假设我有

的基本代码

for l in lines:
  for f in search_data:
     if my_search_function(l[1],[f[0],f[2]]):
        print "Found it!"
        break

我们想确定在search_data中的位置存在存储在 l[1] 中的值.说 my_search_function()看起来像这样:

def my_search_function(search_key, search_values):
   for s in search_values:
      if search_key in s:
         return True
    return False

有什么办法可以提高处理速度吗？ Binary在这种情况下搜索将不起作用，因为行和 search_data是多维列表，我需要保留索引。我尝试了一种由外而内的方法，即

for line in lines:
    negative_index = -1
    positive_index = 0
    middle_element = len(search_data) /2 if len(search_data) %2 == 0 else (len(search_data)-1) /2
    found = False

    while positive_index < middle_element:
        # print str(positive_index)+","+str(negative_index)
        if my_search_function(line[1], [search_data[positive_index][0],search_data[negative_index][0]]):
            print "Found it!"
            break
        positive_index = positive_index +1
        negative_index = negative_index -1

但是，我没有看到任何速度因此而提高。有没有人有更好的方法？当我处理大量 CSV 时，我希望将处理速度减半一个文件的处理时间 > 00:15 这是 Not Acceptable ，因为我正在处理 30 多个文件的批处理。基本上，我正在搜索的数据本质上是 SKU。来自 lines[0] 的值可能类似于 AS123JK并且该值的有效匹配项可以是 AS123 .所以 HashMap 在这里不起作用，除非有一种方法可以在 HashMap 查找中进行部分匹配，不需要我分解像 ['AS123', 'AS123J', 'AS123JK'] 这样的值。 ，这在这种情况下并不理想。谢谢!

Answer 1

Binary Search would not work in this case, as lines and search_data are multidimensional lists and I need to preserve the indexes.

无论如何，将字符串(连同对原始数据结构的一些引用)提取到一个平面列表中，对其进行排序，并在 bisect module 的帮助下对其执行快速二进制搜索可能是值得的。 .

或者，不是进行大量搜索，而是对所有搜索键的组合列表进行排序，并并行遍历两个列表，寻找匹配项。 (与归并排序中的归并步骤类似，不实际输出归并列表)

说明第二种方法的代码:

lines = ['AS12', 'AS123', 'AS123J', 'AS123JK','AS124']
search_keys = ['AS123', 'AS125']

try:
    iter_keys = iter(sorted(search_keys))
    key = next(iter_keys)
    for line in sorted(lines):
        if line.startswith(key):
            print('Line {} matches {}'.format(line, key))
        else:
            while key < line[:len(key)]:
                key = next(iter_keys)
except StopIteration: # all keys processed
    pass