-1

我一直在尝试在 python 中写下一个处理重复的列表交集算法。我是 python 和编程的新手，如果这听起来效率低下，请原谅我，但我想不出其他任何东西。这里，L1 和 L2 是有问题的两个列表，L 是交集。

  1. 遍历 L1
  2. 遍历 L2
  3. 如果元素在 L1 和 L2 中
  4. 将其添加到 L
  5. 从 L1 和 L2 中删除它
  6. 遍历 L
  7. 将元素添加回 L1 和 L2

我 100% 确定这不是 Mathematica 中用于评估列表交集的算法，但我真的想不出更有效的方法。我不想在此过程中修改 L1 和 L2，因此我将交集添加回两个列表。有任何想法吗？我不想使用列表以外的任何内置函数/数据类型，所以没有导入集或类似的东西。就我而言，这是一个算法和实现练习，而不是编程练习。

4

6 回答 6

3

这是一个更快的解决方案：

def intersect_sorted(a1, a2):
  """Yields the intersection of sorted lists a1 and a2, without deduplication.

  Execution time is O(min(lo + hi, lo * log(hi))), where lo == min(len(a1),
  len(a2)) and hi == max(len(a1), len(a2)). It can be faster depending on
  the data.
  """
  import bisect, math
  s1, s2 = len(a1), len(a2)
  i1 = i2 = 0
  if s1 and s1 + s2 > min(s1, s2) * math.log(max(s1, s2)) * 1.4426950408889634:
    bi = bisect.bisect_left
    while i1 < s1 and i2 < s2:
      v1, v2 = a1[i1], a2[i2]
      if v1 == v2:
        yield v1
        i1 += 1
        i2 += 1
      elif v1 < v2:
        i1 = bi(a1, v2, i1)
      else:
        i2 = bi(a2, v1, i2)
  else:  # The linear solution is faster.
    while i1 < s1 and i2 < s2:
      v1, v2 = a1[i1], a2[i2]
      if v1 == v2:
        yield v1
        i1 += 1
        i2 += 1
      elif v1 < v2:
        i1 += 1
      else:
        i2 += 1

它运行在O(min(n + m, n * log(m)))时间中，其中 n 是长度的最小值，m 是最大值。它同时遍历两个列表，在开始时跳过尽可能多的元素。

此处提供了分析：http: //ptspts.blogspot.ch/2015/11/how-to-compute-intersection-of-two.html

于 2015-11-27T18:49:50.157 回答
2

任何迭代L1，L2每次都迭代，将花费二次时间。改善这一点的唯一方法是避免遍历所有L2. （有一个类似的问题，从L最后删除重复。）

如果你使用setfor L2（和 for L），当然每in L2一步都是常数时间，所以整体算法是线性的。而且您始终可以构建自己的哈希表实现，而不是使用set. 但这是很多工作。

使用二叉搜索树，甚至只是一个排序列表和一个binary_find函数，您都可以在 O(N log N) 中完成。这binary_find更容易自己编写。所以：

S2 = sorted(L2)
L = [element for element in L1 if binary_find(element, S2)]
S = remove_adjacent(sorted(L))

或者，更简单地说，也对 L1 进行排序，然后你就不需要了remove_adjacent：

S1, S2 = sorted(L1), sorted(L2)
L = []
for element in S1:
    if binary_find(element, S2) and (not L or L[-1] != element):
        L.append(element)

无论哪种方式，这是 O(N log N)，其中 N 是较长列表的长度。对比一下，原来是O(N^2)，其他答案是O(N^3)。当然它有点复杂，但它仍然很容易理解。

您需要编写binary_find（并且，如果适用，remove_adjacent），因为我假设您不想使用 stdlib 之外的东西，如果您甚至不想使用额外的内置函数。但这真的很容易。例如：

def binary_find(element, seq):
    low, high = 0, len(seq), 
    while low != high:
        mid = (low + high) // 2
        if seq[mid] == element:
            return True
        elif seq[mid] < element:
            low = mid+1
        else:
            high = mid
    return False

def remove_adjacent(seq):
    ret = []
    last = object()
    for element in seq:
        if element != last:
            ret.append(element)
        last = element
    return ret

如果你甚至不想使用sortedor list.sort，你也可以很容易地编写自己的排序。

于 2013-02-13T01:58:15.853 回答
1

怎么样：

  1. 通过 L1 迭代
  2. 通过 L2 迭代
  3. 如果（在 L1 和 L2 中）而不是在 L -> 添加到 L

不是特别有效，但在代码中它看起来像这样（通过重复来说明这一点）：

>>> L1 = [1,2,3,3,4]
>>> L2 = [2,3,4,4,5]
>>> L = list()
>>> for v1 in L1:
        for v2 in L2:
            if v1 == v2 and v1 not in L:
                L.append(v1)
>>> L
[2,3,4]

您只需检查元素是否已经在 L 中，如果不在则添加到 L 中，即可避免从 L1 和 L2 中删除。那么L1和L2中是否有重复并不重要。

于 2013-02-13T01:23:02.157 回答
1

编辑：我读错了标题，并浏览了内置部分。无论如何我都会把它留在这里，可能会帮助别人。

您可以使用该set类型来实现这一点。

>>> a = [1,2,3,4]
>>> b = [3,4,5,6]
>>> c = list(set(a) & set(b))
>>> c
[3, 4]
于 2013-02-13T01:23:48.217 回答
0
  1. 做一个临时清单。
  2. 遍历两个列表之一。不管是哪一个。
  3. 对于每个元素，检查该元素是否存在于另一个列表 ( if element in list2) 中并且不在您的临时列表中（相同的语法）
  4. 如果这两个条件都为真，请将其附加到您的临时列表中。

我对发布解决方案感到难过，但老实说，它比我的文字更具可读性：

def intersection(l1, l2):
    temp = []

    for item in l1:
        if item in l2 and item not in temp:
            temp.append(item)

    return temp
于 2013-02-13T01:26:28.607 回答
0

计算两个列表的交集并保留顺序并消除重复项的 Pythonic 和有效方法如下：

L1 = [1,2,3,3,4,4,4,5,6]
L2 = [2,4,6]
aux = set()
L = [x for x in L1 if x in L2 and not (x in aux or aux.add(x)) ]

该解决方案使用集合“aux”来存储已添加到结果列表中的元素。

请注意，您不需要“导入”集合，因为它们是 Python 中的本机数据类型。但是如果你坚持不使用集合，你可以选择这个使用列表的效率较低的版本：

L1 = [1,2,3,3,4,4,4,5,6]
L2 = [2,4,6]
aux = []
L = [x for x in L1 if x in L2 and not (x in aux or aux.append(x)) ]
于 2018-06-06T17:29:55.600 回答