Noob questions about Python

George Sakkis george.sakkis at gmail.com
Thu Oct 18 07:33:48 CEST 2007


On Oct 17, 6:23 pm, Paul Hankin <paul.han... at gmail.com> wrote:
> On Oct 17, 10:58 pm, Ixiaus <parnel... at comcast.net> wrote:
>
>
>
> > Thank you for the quick responses.
>
> > I did not know that about integer literals beginning with a '0', so
> > thank you for the explanation. I never really use PHP except for
> > handling basic forms and silly web stuff, this is why I picked up
> > Python because I want to teach myself a more powerful and broad
> > programming language.
>
> > With regard to why I asked: I wanted to learn about Binary math in
> > conjunction with Python, so I wrote a small function that would return
> > a base 10 number from a binary number. It is nice to know about the
> > int() function now.
>
> > Just for the sake of it, this was the function I came up with:
>
> > def bin2dec(val):
> >     li = list(val)
> >     li.reverse()
> >     res = [int(li[x])*2**x for x in range(len(li))]
> >     res.reverse()
> >     print sum(res)
>
> > Now that I look at it, I probably don't need that last reverse()
> > because addition is commutative...
>
> > def bin2dec(val):
> >     li = list(val)
> >     li.reverse()
> >     res = [int(li[x])*2**x for x in range(len(li))]
> >     print sum(res)
>
> Right idea: now to remove all those intermediate lists you construct.
> 1. reversed(val) creates an iterator that runs over the elements (here
> of a string) in reverse order.
> 2. enumerate() is usually better than using an explicit list index.
> 3. You can use a generator in your sum to avoid constructing the final
> list.
>
> Applying these to your function, and noting that n << k is nicer than
> n * 2 ** k, we get a one-liner:
>
> def bin2dec(val):
>     return sum(int(i) << k for k, i in enumerate(reversed(val)))
>
> Or a slightly nicer alternative is to filter the generator using 'if':
>
> def bin2dec(val):
>     return sum(1 << k for k, i in enumerate(reversed(val)) if int(i))

Changing the condition to if i=='1' makes it than twice faster.
There's also a small improvement by looping forward rather than
reversed:

def bin2dec_2(val):
    n = len(val)-1
    return sum(1<<n-i for i,bit in enumerate(val) if bit=='1')

These one-liners are short and sweet and have decent performance for
most use cases. Still, for squeezing every last drop of performance
while staying in pure Python, use Psyco and a more verbose version.
The following is two orders of magnitude faster with Psyco enabled:

def bin2dec_3(val):
    s = 0
    p = 1 << len(val)
    for bit in val:
        p >>= 1
        if bit == '1':
            s += p
    return s

And here's the benchmark:

if __name__ == '__main__':
    # uncomment for Psyco
    # import psyco; psyco.full()
    import timeit
    setup = 'import __main__; bin="101001010001001010"'
    for func in bin2dec, bin2dec_2, bin2dec_3:
        name = func.__name__
        timer = timeit.Timer('__main__.%s(bin)' % name, setup)
        print '%s: %s' % (name, timer.timeit())

### Without Psyco ####
bin2dec: 17.6126108206
bin2dec_2: 7.57195732977
bin2dec_3: 5.46163297291

### With Psyco ####
bin2dec: 17.6995679618
bin2dec_2: 8.60846224869
bin2dec_3: 0.16031255369

George




More information about the Python-list mailing list