Asp Forum - Solve a Debate - comp.lang.python

nexes

2/15/2008 4:25:00 PM

Alright so me and my friend are having argument.

Ok the problem we had been asked a while back, to do a programming
exercise (in college)
That would tell you how many days there are in a month given a
specific month.

Ok I did my like this (just pseudo):

If month = 1 or 3 or etc ....
noDays = 31
Elseif month = 4 or 6 etc ....
noDays = 30
Else
noDays = 29
(we didn't have to take into account a leap year)

He declared an array and assigned the number of days in a month to its
own element in an array. Now
I realise that in this example it would not make a difference in terms
of efficiency, but it is my belief that if
there is more data that needed to be assigned(i.e. a couple megs of
data) it would be simpler (and more efficient) to
do a compare rather then assigning all that data to an array, since
you are only going to be using 1 value and the rest
of the data in the array is useless.

What are everyone else's thoughts on this?

25 Answers

Tim Chase

2/15/2008 5:11:00 PM

> Ok the problem we had been asked a while back, to do a programming
> exercise (in college)
> That would tell you how many days there are in a month given a
> specific month.
>
> Ok I did my like this (just pseudo):
>
> If month = 1 or 3 or etc ....
> noDays = 31
> Elseif month = 4 or 6 etc ....
> noDays = 30
> Else
> noDays = 29
> (we didn't have to take into account a leap year)
>
> He declared an array and assigned the number of days in a month to its
> own element in an array. Now
> I realise that in this example it would not make a difference in terms
> of efficiency, but it is my belief that if
> there is more data that needed to be assigned(i.e. a couple megs of
> data) it would be simpler (and more efficient) to
> do a compare rather then assigning all that data to an array, since
> you are only going to be using 1 value and the rest
> of the data in the array is useless.
>
> What are everyone else's thoughts on this?

Well, the standard library offers its opinion:

>>> import calendar
>>> calendar.mdays
[0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
>>> month = 2
>>> calendar.mdays[month]
28

If you want the actual number of days, taking leap-years into
consideration

>>> calendar.monthrange(2008,2)[1]
29
>>> calendar.monthrange(2007,2)[1]
28

So the answer is "mu"...let Python do the work for you :)

-tkc

Ivan Van Laningham

2/15/2008 6:05:00 PM

Hi All--
Lookup tables are always significantly faster than a bunch of ifs.

Metta,
Ivan

On Fri, Feb 15, 2008 at 10:10 AM, Tim Chase
<python.list@tim.thechases.com> wrote:
> > Ok the problem we had been asked a while back, to do a programming
> > exercise (in college)
> > That would tell you how many days there are in a month given a
> > specific month.
> >
> > Ok I did my like this (just pseudo):
> >
> > If month = 1 or 3 or etc ....
> > noDays = 31
> > Elseif month = 4 or 6 etc ....
> > noDays = 30
> > Else
> > noDays = 29
> > (we didn't have to take into account a leap year)
> >
> > He declared an array and assigned the number of days in a month to its
> > own element in an array. Now
> > I realise that in this example it would not make a difference in terms
> > of efficiency, but it is my belief that if
> > there is more data that needed to be assigned(i.e. a couple megs of
> > data) it would be simpler (and more efficient) to
> > do a compare rather then assigning all that data to an array, since
> > you are only going to be using 1 value and the rest
> > of the data in the array is useless.
> >
> > What are everyone else's thoughts on this?
>
> Well, the standard library offers its opinion:
>
> >>> import calendar
> >>> calendar.mdays
> [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
> >>> month = 2
> >>> calendar.mdays[month]
> 28
>
> If you want the actual number of days, taking leap-years into
> consideration
>
> >>> calendar.monthrange(2008,2)[1]
> 29
> >>> calendar.monthrange(2007,2)[1]
> 28
>
> So the answer is "mu"...let Python do the work for you :)
>
> -tkc
>
>
>
>
>
>
> --
> http://mail.python.org/mailman/listinfo/p...
>

--
Ivan Van Laningham
God N Locomotive Works
http://www.pau...
http://www.python.org/workshops/1998-11/proceedings/papers/laningham/lani...
Army Signal Corps: Cu Chi, Class of '70
Author: Teach Yourself Python in 24 Hours

Reedick, Andrew

2/15/2008 6:10:00 PM

> -----Original Message-----
> From: python-list-bounces+jr9445=att.com@python.org [mailto:python-
> list-bounces+jr9445=att.com@python.org] On Behalf Of nexes
> Sent: Friday, February 15, 2008 11:25 AM
> To: python-list@python.org
> Subject: Solve a Debate
>
> Alright so me and my friend are having argument.
>
> Ok the problem we had been asked a while back, to do a programming
>
> He declared an array and assigned the number of days in a month to its
> own element in an array. Now
> I realise that in this example it would not make a difference in terms
> of efficiency, but it is my belief that if
> there is more data that needed to be assigned(i.e. a couple megs of
> data) it would be simpler (and more efficient) to
> do a compare rather then assigning all that data to an array, since
> you are only going to be using 1 value and the rest
> of the data in the array is useless.
>
> What are everyone else's thoughts on this?

Efficient how?

Looking up the data in a array would probably be faster (look-up tables
normally are.)

You could make the array efficient by using pointers, gaining both space
and time efficiency. Mon[1] and mon[3] ... would point to 31.

The array can also just be collection of pointers to the multi-megabyte
objects on disk. Most languages have modules letting you maintain an
index in memory that points to data on disk.

If the array is static or otherwise only loaded once into memory at
startup, and you have plenty of memory and patience, then who cares if
it is inefficient? Simple solutions are normally faster to implement.
It's not often that you need to spend three days to save three seconds.

Then there's debug and change efficiency. An array lookup is simple to
understand and thus less prone to bugs. It can also be easier to change
a single array element than to change a complicated formula or a cluster
of nested if-then-else statements.

*****

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from all computers. GA625

Grant Edwards

2/15/2008 6:32:00 PM

On 2008-02-15, Ivan Van Laningham <ivanlan9@gmail.com> wrote:

> Lookup tables are always significantly faster than a bunch of
> ifs.

Mostly always. It depends on what you mean by "lookup table",
and it depends on how the language implements things. If you
by "lookup table" you mean a linearly indexed array, then an
array lookup is O(1), and a series of if/then/elses is O(n).
The indexing operation is going to be faster for all practical
examples I can think of.

If by "lookup table" you mean an arbitrary mapping (e.g. a
"dict" in Python), then it depends on the hashing/searching
used to implement the lookup operation. It's possible for small
mappings using some types of keys that a series of compares
could be faster than the hashing operation.

In the general case, if the key being used consists of a lot of
bits, you might have to hash all of the bits before you can
start looking up the result. When doing compares, you can quite
after the first bit doesn't match. IOW, you might be able to
do a lot of failed key compares in the time it takes to hash
the key.

--
Grant Edwards grante Yow! Can you MAIL a BEAN
at CAKE?
visi.com

Aaron Brady

2/16/2008 2:22:00 AM

On Feb 15, 12:32 pm, Grant Edwards <gra...@visi.com> wrote:
> On 2008-02-15, Ivan Van Laningham <ivanl...@gmail.com> wrote:
>
> > Lookup tables are always significantly faster than a bunch of
> > ifs.
>
> Mostly always. It depends on what you mean by "lookup table",
> and it depends on how the language implements things. If you
> by "lookup table" you mean a linearly indexed array, then an
> array lookup is O(1), and a series of if/then/elses is O(n).
> The indexing operation is going to be faster for all practical
> examples I can think of.
>
> If by "lookup table" you mean an arbitrary mapping (e.g. a
> "dict" in Python), then it depends on the hashing/searching
> used to implement the lookup operation. It's possible for small
> mappings using some types of keys that a series of compares
> could be faster than the hashing operation.
>
> In the general case, if the key being used consists of a lot of
> bits, you might have to hash all of the bits before you can
> start looking up the result. When doing compares, you can quite
> after the first bit doesn't match. IOW, you might be able to
> do a lot of failed key compares in the time it takes to hash
> the key.
>
> --
> Grant Edwards grante Yow! Can you MAIL a BEAN
> at CAKE?
> visi.com

I forget the name, or it's not on the web. "D-tables"-- sorry, by
example:

D= []

insert 00101110

D= [ 00101110 ]

insert 00101111

D= [ 0010111: [ 0, 1 ] ]

insert 1

D= [ [ 0: 010111: [ 0, 1 ] ], 1 ]

def insert( x ):
for bit in x:
if curnode.bit!= bit:
addnode( node( curnode, x ) )
return
addleaf( x )

Which doesn't do it justice. Anyway, I think it's a log-n lookup on
arbitrary data types. How does the Python implementation handle hash
collisions? Shoot and pray?

Dan Bishop

2/16/2008 4:49:00 AM

On Feb 15, 10:24 am, nexes <nexes...@gmail.com> wrote:
> Alright so me and my friend are having argument.
>
> Ok the problem we had been asked a while back, to do a programming
> exercise (in college)
> That would tell you how many days there are in a month given a
> specific month.
>
> Ok I did my like this (just pseudo):
>
> If month = 1 or 3 or etc ....
> noDays = 31
> Elseif month = 4 or 6 etc ....
> noDays = 30
> Else
> noDays = 29
> (we didn't have to take into account a leap year)
>
> He declared an array and assigned the number of days in a month to its
> own element in an array. Now
> I realise that in this example it would not make a difference in terms
> of efficiency, but it is my belief that if
> there is more data that needed to be assigned(i.e. a couple megs of
> data) it would be simpler (and more efficient) to
> do a compare rather then assigning all that data to an array, since
> you are only going to be using 1 value and the rest
> of the data in the array is useless.
>
> What are everyone else's thoughts on this?

days_in_month = lambda m: m - 2 and 30 + bool(1 << m & 5546) or 28

Steve Holden

2/16/2008 5:50:00 AM

Dan Bishop wrote:
> On Feb 15, 10:24 am, nexes <nexes...@gmail.com> wrote:
>> Alright so me and my friend are having argument.
>>
>> Ok the problem we had been asked a while back, to do a programming
>> exercise (in college)
>> That would tell you how many days there are in a month given a
>> specific month.
>>
>> Ok I did my like this (just pseudo):
>>
>> If month = 1 or 3 or etc ....
>> noDays = 31
>> Elseif month = 4 or 6 etc ....
>> noDays = 30
>> Else
>> noDays = 29
>> (we didn't have to take into account a leap year)
>>
>> He declared an array and assigned the number of days in a month to its
>> own element in an array. Now
>> I realise that in this example it would not make a difference in terms
>> of efficiency, but it is my belief that if
>> there is more data that needed to be assigned(i.e. a couple megs of
>> data) it would be simpler (and more efficient) to
>> do a compare rather then assigning all that data to an array, since
>> you are only going to be using 1 value and the rest
>> of the data in the array is useless.
>>
>> What are everyone else's thoughts on this?
>
> days_in_month = lambda m: m - 2 and 30 + bool(1 << m & 5546) or 28

Elegant, but the 5546 is way too magical for readability.

regards
Steve
--
Steve Holden +1 571 484 6266 +1 800 494 3119
Holden Web LLC http://www.hold...

Aaron Brady

2/16/2008 7:44:00 PM

On Feb 15, 11:50 pm, Steve Holden <st...@holdenweb.com> wrote:
> Dan Bishop wrote:
> > On Feb 15, 10:24 am, nexes <nexes...@gmail.com> wrote:
> >> Alright so me and my friend are having argument.
>
> >> Ok the problem we had been asked a while back, to do a programming
> >> exercise (in college)
> >> That would tell you how many days there are in a month given a
> >> specific month.
>
> >> Ok I did my like this (just pseudo):
>
> >> If month = 1 or 3 or etc ....
> >> noDays = 31
> >> Elseif month = 4 or 6 etc ....
> >> noDays = 30
> >> Else
> >> noDays = 29
> >> (we didn't have to take into account a leap year)
>
> >> He declared an array and assigned the number of days in a month to its
> >> own element in an array. Now
> >> I realise that in this example it would not make a difference in terms
> >> of efficiency, but it is my belief that if
> >> there is more data that needed to be assigned(i.e. a couple megs of
> >> data) it would be simpler (and more efficient) to
> >> do a compare rather then assigning all that data to an array, since
> >> you are only going to be using 1 value and the rest
> >> of the data in the array is useless.
>
> >> What are everyone else's thoughts on this?
>
> > days_in_month = lambda m: m - 2 and 30 + bool(1 << m & 5546) or 28
>
> Elegant, but the 5546 is way too magical for readability.

>>> int( '0101010110101'[::-1], 2 )
5546

John Machin

2/16/2008 9:44:00 PM

On Feb 16, 3:48 pm, Dan Bishop <danb...@yahoo.com> wrote:
> On Feb 15, 10:24 am, nexes <nexes...@gmail.com> wrote:
>
>
>
> > Alright so me and my friend are having argument.
>
> > Ok the problem we had been asked a while back, to do a programming
> > exercise (in college)
> > That would tell you how many days there are in a month given a
> > specific month.
>
> > Ok I did my like this (just pseudo):
>
> > If month = 1 or 3 or etc ....
> > noDays = 31
> > Elseif month = 4 or 6 etc ....
> > noDays = 30
> > Else
> > noDays = 29
> > (we didn't have to take into account a leap year)
>
> > He declared an array and assigned the number of days in a month to its
> > own element in an array. Now
> > I realise that in this example it would not make a difference in terms
> > of efficiency, but it is my belief that if
> > there is more data that needed to be assigned(i.e. a couple megs of
> > data) it would be simpler (and more efficient) to
> > do a compare rather then assigning all that data to an array, since
> > you are only going to be using 1 value and the rest
> > of the data in the array is useless.
>
> > What are everyone else's thoughts on this?
>
> days_in_month = lambda m: m - 2 and 30 + bool(1 << m & 5546) or 28

Alternatively:

days_in_month = lambda m: m - 2 and 31 - ((m + 9) % 12 % 5 % 2) or 28

the guts of which is slightly more elegant than the ancient writing
from which it was derived:

MOD(MOD(MOD(M+9,12),5),2)

Steve Holden

2/16/2008 10:36:00 PM

castironpi@gmail.com wrote:
> On Feb 15, 11:50 pm, Steve Holden <st...@holdenweb.com> wrote:
>> Dan Bishop wrote:
>>> On Feb 15, 10:24 am, nexes <nexes...@gmail.com> wrote:
[...]
>>>> What are everyone else's thoughts on this?
>>> days_in_month = lambda m: m - 2 and 30 + bool(1 << m & 5546) or 28
>> Elegant, but the 5546 is way too magical for readability.
>
>>>> int( '0101010110101'[::-1], 2 )
> 5546

Yes, I'm aware of that. Adding it as a comment might help.

regards
Steve
--
Steve Holden +1 571 484 6266 +1 800 494 3119
Holden Web LLC http://www.hold...

comp.lang.python

Solve a Debate

nexes

Tim Chase

Ivan Van Laningham

Reedick, Andrew

Grant Edwards

Aaron Brady

Dan Bishop

Steve Holden

Aaron Brady

John Machin

Steve Holden

x Login to ForumsZone