Python中两个迭代器的Mergesort样式迭代 [英] Mergesort-style iteration over two iterators in Python

问题描述

Python中是否有一种优雅的方式以mergesort算法在合并阶段的方式迭代两个迭代器？我的意思是假设 list1 和 list2 按排序顺序（让我们说升序，但它没有'无所谓）。我想同时遍历两个列表，其中返回的下一个项目是两个列表中的两个 next 项中最小的一个。如果list1为空，它还必须处理像这样的逻辑：，只需从list2返回。

Is there an elegant way in Python to iterate over two iterators in the way that the mergesort algorithm does during the merge phase? What I mean by that is assume that list1 and list2 are in sorted order (let's say ascending, but it doesn't matter). I want to iterate through both lists simultaneously, where the next item returned is the smallest of the two next items from either list. It would also have to handle logic like if list1 is empty:, just return from list2.

此外，我希望能够选择用于比较的特定键，就像Python允许进行所有标准排序一样。

Furthermore, I would like the ability to select a specific key to use for comparison, just like Python allows when doing all its standard sorting.

推荐答案

我认为最简单的方法是使用临时变量（每个迭代器一个）来存储迭代器中的当前值。然后你可以对两个变量进行比较，而不是从迭代器中取出，这会导致你的问题。

I would think the easiest way to do this is to have temporary variables, one for each iterator, to store the "current" value from that iterator. Then you can perform comparisons on the two variables instead of fetching from the iterator, which will cause you problems.

# This function dumps one iterator into your list, in case one of the two
# runs out of values.
def dump_iter(iterator, newlist):
  for i in iterator:
    newlist.append(i)
    return newlist

iter1 = # Your first iterator.
iter2 = # Your second iterator.
newlist = []

# Get initial values.
try:
  var1 = iter1.next()
except StopIteration:
  return dump_iter(iter2, newlist)
try:
  var2 = iter2.next()
except StopIteration:
  newlist.append(var1)
  return dump_iter(iter1, newlist)

# Now we actually perform the merge sort.
while True:
  if var1 <= var2:
    newlist.append(var1)
    try:
      var1 = iter1.next()
    except StopIteration:
      newlist.append(var2)
      return dump_iter(iter2, newlist)
  else:
    newlist.append(var2)
    try:
      var2 = iter2.next()
    except StopIteration:
      newlist.append(var1)
      return dump_iter(iter1, newlist)

这里，我们将每个迭代器的next值存储在一个变量中，我们可以查看并比较它而不触发迭代器本身。当我们将其中一个变量添加到新列表中时，我们通过触发迭代器来替换它。在这里，我们正在捕获 StopIteration ，以了解其中一个迭代器何时耗尽数据;当发生这种情况时，我们只是将其他迭代器的剩余内容转储到我们的列表中。 （虽然我们还必须从其他列表中附加该变量。）

Here, we're storing the "next" value of each iterator in a variable, which we can look at and compare without triggering the iterator itself. When we add one of the variables to the new list, we replace it by triggering that iterator. Here we're catching StopIteration to know when one of the iterators has run out of data; when that happens, we just dump the remaining contents of the other iterator into our list. (Though we also have to append that variable from the other list.)

这篇关于Python中两个迭代器的Mergesort样式迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！