我正在尝试使用python生成器实现某种合并排序,以便在生成的数字中找到最小数量并生成下一个,下面是我的示例代码:
class GeneratorSort():
def __init__(self, *args):
self.values = [(arg.next(), i) for i, arg in enumerate(args)]
self.generators = args
def generate(self):
r, index = min(self.values)
self.values[index] = self.generators[index].next()
yield r
def t(l):
for each in l:
yield each
l1 = [2, 5, 6, 8]
l2 = [1, 4, 5, 7]
l3 = [0, 3, 9, 10]
a = GeneratorSort(t(l1), t(l2), t(l3))
但当我试图打印排序结果时,我只得到0
,下次出现错误:
错误就在这里:
>>> a.generate()
<generator object generate at 0x7fa7bcc37a00>
>>> a.generate().next()
Traceback (most recent call last):
File "<pyshell#1>", line 1, in <module>
a.generate().next()
File "/home/hamid/projects/bfl/workspace/testo.py", line 10, in generate
r, index = min(self.values)
TypeError: 'int' object is not iterable
>>>
我希望这个函数可以打印像1
、2
、3
、4
、5
和。。。已排序。还有别的办法吗?在
注意,我需要使用发电机。在
将
(value, index)
元组替换为仅值:您需要用一个新的元组替换它:
^{pr2}$否则iterable赋值失败;不能将一个
int
分配给两个变量。在发电机和发电机的处理是空的:
这会将
self.values
列表的元素设置为None
,以指示iterable已用尽。这并不是处理这种边缘情况的最有效的方法;在version I wrote before中,我使用字典来跟踪活动的iterable,并简单地从中删除以保持索引(键)的稳定。在注意,您可以用内置的^{} function 替换
t()
函数。在演示:
标准库仍然使用^{} function 更有效地完成这项工作;它使用堆以非常有效的方式将iterable按最低值排序;
min()
需要遍历所有K个iterable,而使用堆只需要log-K步骤来保持堆不变。在您可以研究source code,它已经过高度优化以获得最佳性能。在
我使用Martijn Pieters的
heapq.merge
的思想编写了这个简单的代码相关问题 更多 >
编程相关推荐