[Tutor] lists+sort

Peter Otten __peter__ at web.de
Tue Jan 5 07:03:23 EST 2016


Pooja Bhalode wrote:

> Hi, I wanted to check if this program can be used to merge the lists
> together and sort them. This seems to work, but i wanted to check if there
> are drawbacks in writing it in this manner.

When you start out lists are the natural datatype to use, but as you get 
more experienced you'll often switch to generators and iterators. These 
allow you to defer calculations until they are actually necessary and to 
reduce memory footprint. For example:

>>> import heapq
>>> a = range(0, 10**100, 2)
>>> b = range(0, 10**100, 7)
>>> for item in heapq.merge(a, b):
...     print(item)
...     if item > 20:
...         break
... 
0
0
2
4
6
7
8
10
12
14
14
16
18
20
21

A list-based implementation would try to build a list with 

>>> 10**100//2 + 10**100//7
6428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428

items. CPython can't even determine the length of such a list:

>>> len(range(0, 10**100, 2))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: Python int too large to convert to C ssize_t

Anyway, heapq.merge() is written in Python, so you can easily take a look:

https://hg.python.org/cpython/file/737efcadf5a6/Lib/heapq.py#l349






More information about the Tutor mailing list