Merge multiple sorted inputs into a single sorted output. Similar to sorted(itertools.chain(*iterables)) but returns a generator, does not pull the data into memory all at once, and assumes that each of the input streams is already sorted (smallest to largest). >>> list(merge([1,3,
(*iterables, key=None, reverse=False)
| 328 | _siftdown_max(heap, startpos, pos) |
| 329 | |
| 330 | def merge(*iterables, key=None, reverse=False): |
| 331 | '''Merge multiple sorted inputs into a single sorted output. |
| 332 | |
| 333 | Similar to sorted(itertools.chain(*iterables)) but returns a generator, |
| 334 | does not pull the data into memory all at once, and assumes that each of |
| 335 | the input streams is already sorted (smallest to largest). |
| 336 | |
| 337 | >>> list(merge([1,3,5,7], [0,2,4,8], [5,10,15,20], [], [25])) |
| 338 | [0, 1, 2, 3, 4, 5, 5, 7, 8, 10, 15, 20, 25] |
| 339 | |
| 340 | If *key* is not None, applies a key function to each element to determine |
| 341 | its sort order. |
| 342 | |
| 343 | >>> list(merge(['dog', 'horse'], ['cat', 'fish', 'kangaroo'], key=len)) |
| 344 | ['dog', 'cat', 'fish', 'horse', 'kangaroo'] |
| 345 | |
| 346 | ''' |
| 347 | |
| 348 | h = [] |
| 349 | h_append = h.append |
| 350 | |
| 351 | if reverse: |
| 352 | _heapify = heapify_max |
| 353 | _heappop = heappop_max |
| 354 | _heapreplace = heapreplace_max |
| 355 | direction = -1 |
| 356 | else: |
| 357 | _heapify = heapify |
| 358 | _heappop = heappop |
| 359 | _heapreplace = heapreplace |
| 360 | direction = 1 |
| 361 | |
| 362 | if key is None: |
| 363 | for order, it in enumerate(map(iter, iterables)): |
| 364 | try: |
| 365 | next = it.__next__ |
| 366 | h_append([next(), order * direction, next]) |
| 367 | except StopIteration: |
| 368 | pass |
| 369 | _heapify(h) |
| 370 | while len(h) > 1: |
| 371 | try: |
| 372 | while True: |
| 373 | value, order, next = s = h[0] |
| 374 | yield value |
| 375 | s[0] = next() # raises StopIteration when exhausted |
| 376 | _heapreplace(h, s) # restore heap condition |
| 377 | except StopIteration: |
| 378 | _heappop(h) # remove empty iterator |
| 379 | if h: |
| 380 | # fast case when only a single iterator remains |
| 381 | value, order, next = h[0] |
| 382 | yield value |
| 383 | yield from next.__self__ |
| 384 | return |
| 385 | |
| 386 | for order, it in enumerate(map(iter, iterables)): |
| 387 | try: |
searching dependent graphs…