0

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

4

3 回答 3

1

在这种情况下，二进制搜索不起作用，因为 lines 和 search_data 是多维列表，我需要保留索引。

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

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

说明第二种方法的代码：

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
于 2015-10-21T13:10:21.727 回答
0

取决于问题的细节。

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

填充哈希表是伪线性的。

于 2015-10-20T13:19:58.850 回答
0

最终，我崩溃了，并通过使用sorted()带有 lambda 作为关键参数的函数进行排序，在我的多维列表上实现了二进制搜索。这是我准备的第一个密码。它不是 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 基于子数组的第二个元素对多维数组进行排序

于 2015-10-22T13:48:57.820 回答