Python 线性搜索效率更高

Question

我有一个关于 Python 中的 Linear Searching 的问题。假设我有

的基本代码

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这是不可接受的，因为我正在处理 30 多个文件的批次。基本上，我正在搜索的数据本质上是 SKU。来自 lines[0] 的值可能类似于 AS123JK，并且该值的有效匹配可能是 AS123。因此 HashMap 在这里不起作用，除非存在一种在 HashMap 查找中进行部分匹配的方法，不需要我分解像 ['AS123', 'AS123J', 'AS123JK'] 这样的值，这在这种情况下并不理想。谢谢！

Answer 1

取决于问题详情。

例如，如果您搜索完整的单词，您可以在可搜索元素上创建一个哈希表，最后的搜索将是一个简单的查找。

填充哈希表是伪线性的。

Answer 2

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

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

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

用于说明第二种方法的代码：

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

Answer 3

最终，我被分解并在我的多维列表上实现了二进制搜索，方法是使用 sorted() 函数以 lambda 作为键进行排序 argument.Here 是我快速创建的第一个密码。它不是 100% 有效，但与我们之前的水平相比有了很大的改进

def binary_search(master_row, source_data,master_search_index, source_search_index):
    lower_bound = 0
    upper_bound = len(source_data) - 1
    found = False
    while lower_bound <= upper_bound and not found:
        middle_pos = (lower_bound + upper_bound) // 2

        if source_data[middle_pos][source_search_index] < master_row[master_search_index]:

            if search([source_data[middle_pos][source_search_index]],[master_row[master_search_index]]):
                return {"result": True, "index": middle_pos}
                break
            lower_bound = middle_pos + 1

        elif source_data[middle_pos][source_search_index] > master_row[master_search_index] :

            if search([master_row[master_search_index]],[source_data[middle_pos][source_search_index]]):
                return {"result": True, "index": middle_pos}
                break
            upper_bound = middle_pos - 1
        else:

            if len(source_data[middle_pos][source_search_index]) > 5:

                return {"result": True, "index": middle_pos}
            else:
                break

然后我们实际进行二进制搜索调用的地方

#where master_copy is the first multidimensional list, data_copy is the second
#the search columns are the columns we want to search against
for line in master_copy:
    for m in master_search_columns:
        found = False
        for d in data_search_columns:
            data_copy = sorted(data_copy, key=lambda x: x[d], reverse=False)
            results = binary_search(line, data_copy,m, d)
            found = results["result"]
            if found:
                line = update_row(line, data_copy[results["index"]], column_mapping)
                found_count = found_count +1
                break
        if found:
            break

这是对多维列表进行排序的信息Python Sort Multidimensional Array Based on 2nd Element of Subarray

Python 线性搜索效率更高

Python Linear Search Better Efficiency

python

csv

algorithm

binary-search

linear-search