Re: Noob questions about Python

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
.

Relevant Pages

  • Re: Math.random
    ... the ones most suitable for ECMAScript produce 32-bit integers ... language has 16-bit shifts with carry, so that a 64-bit shift by 1 ... The simplest generator I ... John Stockton, Surrey, UK. ...
    (comp.lang.javascript)
  • Re: division by general integer using shifts
    ... > Multiplying using shifts and adds is typically just 'long multiplication' ... > The base 10 equivalent division is simply long division, ... > shifts alone - there's some comparisons and subtractions in there. ... find the largest factor that's less than what's left and subtract ...
    (comp.programming)
  • Re: division by general integer using shifts
    ... <snip stuff about multiplying using shifts and adds> ... > dividing by two. ... I can't seem to work out the algebra though. ... Multiplying using shifts and adds is typically just 'long multiplication' ...
    (comp.programming)
  • About 1.8.7 Array#map! without a block
    ... with e.next to change the value, say, multiplying by 2 as on the first ... case and have a array on the end? ... - Why I get a Generator on "a" elements when I just call e.next? ... cause it's what I'm missing to use with next, ...
    (comp.lang.ruby)
  • Advance SG70 in problems
    ... I recently switched on an old Advance SG70 LF generator and found that the ... It shifts a lot up and down. ... Prev by Date: ...
    (sci.electronics.equipment)