1

背景

我有两个列表，第一个items包含大约 250 个元组，每个元组包含 3 个元素

(path_to_a_file, size_in_bytes, modified_time)

第二个列表result包含最多 250 个元素，这是数据库查询的结果，该查询根据列表中的路径查找行items。元素的数量result取决于这些文件是否已经在数据库中。

结果中的每个元素都是从 SQLAlchemy 查询返回的行对象，其中包含行值的属性，（path，mtime并且hash是我在这里感兴趣的）

我正在尝试做的是过滤掉其中具有相同 mtime 的所有元素items（results并跟踪过滤的数量和总大小），并创建一个新列表，其中包含具有不同 mtime 或不具有不同 mtime 的项目存在于result. 需要存储具有不同 mtime 的(path,size,mtime_from_result,hash_from_result)项目以及不在数据库中的项目(path,size,mtime,None)。

我希望我没有把它过于本地化，但我觉得我需要解释我想要完成的问题才能提出这个问题。

问题

我想尝试让这个循环尽可能快，但最重要的部分是让它按预期工作。

当我遍历它们时从列表中删除项目是否安全？我注意到向前迭代有一个奇怪的结果，但向后迭代似乎没问题。有更好的方法吗？

我正在删除我匹配的项目（i.path == j[0]）因为我知道关系是 1 到 1 并且它不会再次匹配所以通过减少列表我可以在下一次迭代中更快地迭代它，更重要的是我得到留下所有不匹配的项目。

我不禁觉得我忽略了一个更好的解决方案，也许是列表理解或生成器。

send_items=[]
for i in result[::-1]:
    for j in items[::-1]:
        if i.path==j[0]:
            result.remove(i) #I think this remove is possibly pointless?
            items.remove(j)
            if i.mtime==j[2]:
                self.num_skipped+=1
                self.size_skipped+=j[1]
            else:
                send_items.append((j[0],j[1],i.mtime,i.hash))
            break
send_items.extend(((j[0],j[1],j[2],None) for j in items))
4

4 回答 4

1

我会这样做：

def get_send_items(items, results):
    send_items = []
    results_dict = {i.path:i for i in results}
    for p, s, m in items:
        result = results_dict.get(p)
        if result is None:
            send_items.append((p, s, m, None))
        elif result.mtime != m:
            send_items.append((p, s, result.mtime, result.hash))
    return send_items

这是我对您的解决方案的分析（假设两者result的items长度均为 N）：

  • result[::-1]创建resultso 调用的副本result.remove(i)不会影响迭代，也不会影响迭代。您只循环result一次，因此删除元素有点毫无意义。它只会创造额外的工作。
  • 您可以调用result[::]创建result.
  • 调用items.remove(j)实际上会降低效率。remove()花费 O(N) 时间。所以调用它会将算法的效率从 O(N^2) 降低到 O(N^3)。
  • 通过使用 O(N) 额外内存（如在我的解决方案中），如果您使用字典或具有 O(1) 查找的集合，则可以将运行时间减少到 O(N)。
于 2012-06-21T14:34:05.020 回答
0

First stab:

items_dict = dict( (el[0], el[1:]) for el in items )
new = []
modified = []
other = []
for res in result:
    put_to = None
    item = items_dict.get(res.path, (None, None))
    if item is (None, None):
        put_to = new
    elif res.mtime != item[1]:
        put_to = modified
    else:
        put_to = other
    put_to.append( (res.path, item) )
于 2012-06-21T14:39:04.127 回答
0

首先，我假设文件路径标识一个文件——它们是唯一的。

我们创建了一个结果字典，因此我们可以轻松地检查成员资格，并检查与其关联的值。

dict_results = {file: (size, modified_time) for file, size, modified_time in results}

然后我们可以使用列表推导来过滤掉你不想要的元素：

[(file, size, modified_time) for file, size, modified_time in items if (file not in dict_results) or (not dict_results[file][1] == modified_time)]

例如：

>>> results = [(1, 1, 1), (2, 2, 3)]
>>> items = [(1, 1, 1), (2, 2, 2), (3, 3, 3)]
>>> dict_results = {file: (size, modified_time) for file, size, modified_time in results}
>>> [(file, size, modified_time) for file, size, modified_time in items if (file not in dict_results) or (not dict_results[file][1] == modified_time)]
[(2, 2, 2), (3, 3, 3)]
于 2012-06-21T14:31:22.730 回答
0

如何按照 Marcin 的建议将结果插入到集合中，并使用列表推导来过滤项目：

mtimes_set = set(result[2] for result in results)
send_items = (item for item in items if item[2] not in mtimes_set)

误解了路径部分。这仍然可以完成（尽管最后一组括号有点难看）：

path_dict = dict((result[0], result) for result in results)
send_items = (item for item in items if item[0] in path_dict and path_dict[item[0]][2] != item[2])

在这里，我正在创建一个可见路径的字典，然后是一个生成器，它返回在字典中具有路径并且具有不同 mtime 的那些。可以很容易地更改返回 path_dict 结果项目而不是现在而不是项目。

于 2012-06-21T14:32:57.890 回答