对比 Python 中的两个排序列表

Question

我有两个排序列表，我需要在每个列表中找出奇数。

目前我正在使用两个列表理解 not in:

> if foo != bar:
      in_foo = [i for i in foo if i not in bar]
      in_bar = [i for i in bar if i not in foo]

但是，此方法没有利用列表的排序结构。

我可以使用带有计数器变量和递归的替代方法，但是是否有更 pythonic 的方法来做到这一点？

编辑：首选排序输出。谢谢

Answer 1

任何时候你遇到这样的事情，通常最好使用集合并忽略排序（由于语言开销，Python 对于小列表比其他编程语言重要得多）

_foo   = set(foo)
_bar   = set(bar)
in_foo = _foo - _bar
in_bar = _bar - _foo

Answer 2

通过在每个列表的末尾放置一个 None 尾部，我们可以使用迭代器并专注于记录差异。这个算法是 O(n+m):

foo = [1, 3, 4, 5]
bar = [2, 4, 5, 6]

i_foo = iter(foo + [None])
i_bar = iter(bar + [None])

n_foo = next(i_foo)
n_bar = next(i_bar)
in_foo = []
in_bar = []
while True:
    if n_foo is None:
        if n_bar is None:
            break
        in_bar.append(n_bar)
        n_bar = next(i_bar)
        continue
    if n_bar is None:
        in_foo.append(n_foo)
        n_foo = next(i_foo)
    if n_foo == n_bar:
        n_foo = next(i_foo)
        n_bar = next(i_bar)
        continue
    if n_foo < n_bar:
        in_foo.append(n_foo)
        n_foo = next(i_foo)
    else:
        in_bar.append(n_bar)
        n_bar = next(i_bar)
print(in_foo, in_bar)
# [1, 3] [2, 6]

Answer 3

这里是三种方法的比较。 with_intersection 方法允许在每个列表中重复值，其他两个则不允许。该测试考虑了两个排序列表，每个列表都有一百万个不同的整数。

using_sorted 方法利用了两个列表都已排序且不使用集合的事实。同时，它是最慢、最冗长和最容易出错的。

import numpy as np # only for data generation

lst1 = np.random.randint(1, 20, 10**6).cumsum().tolist()
lst2 = np.random.randint(1, 20, 10**6).cumsum().tolist()

def with_intersection(lst1, lst2):
  common = set(lst1).intersection(lst2)
  res1 = [x for x in lst1 if x not in common]
  res2 = [x for x in lst2 if x not in common]
  return res1, res2

def set_then_sort(foo, bar):
  _foo   = set(foo)
  _bar   = set(bar)
  in_foo = _foo - _bar
  in_bar = _bar - _foo
  return sorted(in_foo), sorted(in_bar)

def using_sorted(lst1, lst2):
  res1 = list()
  res2 = list()
  n1 = len(lst1)
  n2 = len(lst2)
  i = j = 0
  while True:
    while i < n1 and j < n2 and lst1[i] < lst2[j]: 
      res1.append(lst1[i])
      i += 1
    while j < n2 and i < n1 and lst1[i] > lst2[j]:
      res2.append(lst2[j])
      j += 1
    while i < n1 and j < n2 and lst1[i] == lst2[j]:
      i += 1
      j += 1
    if i == n1:
      res2.extend(lst2[j:])
      break
    elif j == n2:
      res1.extend(lst1[i:])
      break
  return res1, res2
      
assert with_intersection(lst1, lst2) == set_then_sort(lst1, lst2) == using_sorted(lst1, lst2)

# %timeit with_intersection(lst1, lst2) # 306 ms
# %timeit set_then_sort(lst1, lst2)     # 491 ms
# %timeit using_sorted(lst1, lst2)      # 870 ms

对比 Python 中的两个排序列表

Contrasting two sorted lists in Python

python

sorting

list-comprehension

list