0

我正在使用 Python。

我有一个疑问，用词。例如，query=[hello, tree, blue]

我已经为每个单词选择了它所在的文档，因此我为每个单词都有一个列表，其中每个位置都是文档之一。比方说：

list_query[0]=[1,4,5]
list_query[1]=[5,8]
list_query[2]=[4,5,8]

所以，我应该得到一个结果 = [5]

但是，我不想用交集来做。我需要使用迭代 i，j 来完成它。

hello:
      i
      |
      1    4    5
tree:
      5    8
      |
      j

我必须从 i=0 开始，比较 list_query[0][i]==list_query[1][j]，如果是，则将该数字添加到列表中。如果不是，我应该迭代较少数量的两个迭代器，依此类推，结果是这些列表和查询的其余元素的交集。但是请找到如何做到这一点，这让我发疯。

因此，如果有人可以帮助我...在此先感谢。

4

2 回答 2

0

如果您对代码简单性而不是性能最感兴趣，那么迭代地与列表的内容相交并不难：

def intersect(query_lists):
    # initialize to first result set
    combined_results = query_lists[0]

    # filter out values missing in any other result set
    for query in query_lists[1:]:
        combined_results = filter(lambda i: i in query, combined_results)

    # turn nested generators into a list
    return list(combined_results)

使用实例而不是列表会快得多set，但是如果您使用它们，您可以只使用内置的交集方法，而不必手动进行。

您还可以通过组合列表、对组合结果进行排序然后扫描以查找与原始列表完全相同次数的值来实现几乎相同的加速。但是，如果您的输入集中可能有重复项，这将不起作用。

如果您知道每个输入列表都已排序，则可以检查它们的第一个值是否都相同，并拒绝任何小于最大值的值。如果您的子列表未排序，则可能不值得这样做，因为如果您自己对每个子列表进行排序，您将失去一些性能优势。

于 2012-10-27T15:45:37.250 回答
0

我觉得你已经走得很远了。我可以向您展示一个实现，但您已经描述了该算法，因此您自己实现它应该不难。但也许你对你的描述没有信心。

让我以缓慢而准确的方式重述您的描述，省略我们不需要的关于查询等的信息。我们有两个预先排序的列表，我们想找到它们的交集。用一个稍微完整的例子来调整你的图表，从 list a = [1, 4, 5, 7, 8]、b = [5, 8, 9]、i=0和开始j=0，以及一个空的输出列表out = []，我最初将在图表中省略...

i = 0
a = 1 4 5 7 8

j = 0
b = 5 8 9

首先我们检查它们是否相等。它们不是，所以我们取 和 的a[i]最小值b[j]。在这种情况下，a[i] == 1和b[j] == 5，所以我们想要增加i。

i =   1
a = 1 4 5 7 8

j = 0
b = 5 8 9

通过相同的步骤，我们i再次递增：

i =     2
a = 1 4 5 7 8

j = 0
b = 5 8 9

现在情况不同了；a[i]和b[j]是相同的，所以我们想将该值附加到输出列表并增加两个值：

i =       3
a = 1 4 5 7 8

j =   1
b = 5 8 9

out = 5

现在我们继续。再次小于... a[i]_b[j]

i =         4
a = 1 4 5 7 8

j =   1
b = 5 8 9

并且值是相同的，所以我们将该值添加到out并递增i和j...

i =           5
a = 1 4 5 7 8

j =     2
b = 5 8 9

out = 5 8

但现在我们发现了i == len(a)。所以我们知道算法已经终止。

现在我们拥有了确定我们需要哪些变量以及逻辑应该如何工作所需的一切。我们需要 list a、 list b、 index i、 indexj和 list out。我们想创建一个在i == len(a)或时停止的循环j == len(b)，并且在该循环中，我们想测试a[i]与 是否相等b[j]。如果它们相等，我们将iandj和 appenda[i]都递增out。如果它们不相等，那么我们测试是否a[i] < b[j]。如果是，那么我们增加i; 否则，我们增加j.

这决定了两个列表之间的交集；现在我们只需要将它应用于第一个和第二个列表，然后将结果应用于第三个列表，然后将结果应用于第四个，依此类推。

于 2012-10-27T16:00:50.107 回答