Noob questions about Python

[Steven D'Aprano]

On Wed, 17 Oct 2007 23:06:24 -0700, Ixiaus wrote:

> I know '<<' is shifting x over by n bits; but could you point me to some
> literature that would explain why it is the same as "x*2**n"? (Googling
> only returns bit shift, but doesn't necessarily explain the manner in
> which you are using it)

In decimal, multiplying by ten shifts the digits to the left by one place:

31 * 10 => 310
310 * 10 => 3100
3100 * 10 => 31000

In binary, multiplying by two shifts the bits to the left by one place:

101 * 10 => 1010
1010 * 10 => 10100
10100 * 10 => 101000

Because the underlying numbers are the same regardless of what base we 
use to write it in, bit-shifts to the left are equivalent to repeated 
multiplication by two regardless of the display base. Hence:

>>> 7 << 1
14
>>> 14 << 1
28
>>> 28 << 1
56

or to do it another way:

>>> 7 << 3  # multiplication by 2**3
56



Similarly, a bit-shift to the right is equivalent to dividing by two and 
dropping any remainder.



> I will have to read up more on Generators, but maybe you can give me a
> lowdown on why
> sum([1 << k for k, i in enumerate(reversed(val)) if int(i)]) is less
> efficient than using a Generator (is the generator a 'temporary' list?)
> sum(1 << k for k, i in enumerate(reversed(val)) if int(i))

The list comprehension:

[1 << k for k, i in enumerate(reversed(val)) if int(i)]

creates the entire list first. That potentially can require a lot of 
memory, leading to all sorts of complicated memory shuffles as the list 
is resized, paging, etc. 

Using a generator expression means that you avoid creating the entire 
list all in one go. That saves you memory, which may mean that you save 
time.

However, for small sets of input, it is likely that the overhead of 
creating the generator in the first place outweighs the saving of not 
creating the whole list.

The definition of "small" depends on what you are trying to do. In my 
tests, I have found that sum(list comprehension) is marginally faster 
than sum(generator expression) even for 10,000 items.


-- 
Steven