Solve a Debate

[nexes]

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?

 

[Tim Chase]

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]

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

Metta,
Ivan

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
God N Locomotive Works
http://www.pauahtun.org/
http://www.python.org/workshops/1998-11/proceedings/papers/laningham/laningham.html
Army Signal Corps: Cu Chi, Class of '70
Author: Teach Yourself Python in 24 Hours

 

[Reedick, Andrew]

-----Original Message-----

From: [email protected] [mailtoython-
[email protected]] On Behalf Of nexes
Sent: Friday, February 15, 2008 11:25 AM
To: (e-mail address removed)
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]

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.

 

[castironpi]

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.

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]

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]

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

 

[castironpi]

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]

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]

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

 

[castironpi]

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:

Lacks citation.

 

[John Machin]

Lacks citation.

Maxima mea culpa.

Pages 294-295 (in particular formula 23.12) in "MAPPING TIME\nThe
Calendar and Its History", by E. G. Richards. OUP, 1998. ISBN
0-19-286205-7.

 

[Gabriel Genellina]

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)

I wonder why one would write such arcane expressions [in Python] instead
of using a small dictionary {1:31, 2:28, 3:31...} which is auto
documented, obviously correct, several times faster, and provides input
validation for free (days_in_month(13)?)

 

[John Machin]

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)

I wonder why one would write such arcane expressions [in Python] instead
of using a small dictionary {1:31, 2:28, 3:31...} which is auto
documented, obviously correct, several times faster, and provides input
validation for free (days_in_month(13)?)

Some people write such arcane expressions in Python solely for
amusement in the newsgroup. I suggest that if you actually find any
who write such expressions in Python *instead* of using a dictionary,
you should don your nice red uniform and arraign them before the
Inquisition forthwith.

 

[Steve Holden]

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)

I wonder why one would write such arcane expressions [in Python] instead
of using a small dictionary {1:31, 2:28, 3:31...} which is auto
documented, obviously correct, several times faster, and provides input
validation for free (days_in_month(13)?)

Some people write such arcane expressions in Python solely for
amusement in the newsgroup. I suggest that if you actually find any
who write such expressions in Python *instead* of using a dictionary,
you should don your nice red uniform and arraign them before the
Inquisition forthwith.

Not the comfy chair!

 

[Dennis Lee Bieber]

you should don your nice red uniform and arraign them before the
Inquisition forthwith.

I think I'd beg sanctuary from a Franciscan before letting the
Dominicans take me into custody...
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[Wolfgang Draxinger]

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.

Ouch, you're hurting my brain...

Okay, let's state this first: A lookup table IS the more
efficient solution.

Somehow you seem to think, that a lookup table will require more
resources (memory I guess you thought) than a sequence of
comparisons. However you didn't take into account, that the
program code itself requires memory, too (for the operation
codes). For the sake of simplicity let's assume, that every
operation code and every variable takes exactly one "blurp" of
memory (what a blurp is exactly we leave undefined here, it's
just the smallest unit of memory our hypothetically machine can
process).

Let's also assume, that you can pack everything, that happens in
a operation into a single opcode, which by definition fits into
a blurp: In case of a comparision this would include the value,
to operand to compare to and where to jump if the comparision
satisfies. Assignment is a own operation, thus it doesn't go
into the compare operation (it would be rather inefficient to
try to fit all possible things you do after a comparision into a
huge variety of comparision opcodes).

In the following example each line should be considered as a
single operation. And let's assume that every operation takes one
tick to execute. Labels take no memory. A table is a label with
a number of values following. The label of the table itself
doesn't consume memory either, however a compiler/assembler
might decide to insert a relative jump just before the table so
that the program doesn't run into it.

The operations are like this:

compare $variable $value $jump_label

assign $variable $value | $table[$index]

jump $jump_label

$jump_label:

$table $number_of values:
$value
$value
....

The shortest compare/assign program for the month problem would
look like this

compare month 1 month_31
compare month 2 month_28
compare month 3 month_31
compare month 4 month_30
....
compare month 11 month_30
compare month 12 month_31
month_30: assign $days 30
jump end
month_31: assign $days 31
jump end
month_28: assign $days 28
end:

This program consists of 12+5 = 18 operations. There are no
tables, to the program consumes only those 18 blurps. Running
time is between 3 and 14 ticks.

Now let's have a look on the table based variant

days_in_month 12:
31
30
28
31
....
30
31
assign $days days_in_month[$month]

This program consists of 2 operations (table jump and assignment)
and 12 values. This makes a memory consumption of 12+2 = 14
blurps. Running time is always 2 ticks. You see that the table
based approach both takes less memory (14 blurbs vs. 18 blurps)
and always runs faster (2 ticks vs. 3...14 ticks) than the
comparison/jump/assignment based solution.

And that was just this artificial example. In most real world
applications the operands to a comparision would take additional
memory, at it's best the opcode would also address some
register(s), but not more, so this would also add the
instructions to fill the registers with the values.

Now you might want to state the above examples are indeed
artificial. But OTOH they're not so artificial then again. Most
assembler code works that way and if you take the AVR
architecture it almost looks that way there. And if you're
thinking of Python you can bet, that an opcode will not contain
all information, but have the operands encoded in additional
values, consuming memory.

Look up Table is more efficient: Debate solved.

Wolfgang Draxinger

 

[castironpi]

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.

Ouch, you're hurting my brain...

Okay, let's state this first: A lookup table IS the more
efficient solution.

Somehow you seem to think, that a lookup table will require more
resources (memory I guess you thought) than a sequence of
comparisons. However you didn't take into account, that the
program code itself requires memory, too (for the operation
codes). For the sake of simplicity let's assume, that every
operation code and every variable takes exactly one "blurp" of
memory (what a blurp is exactly we leave undefined here, it's
just the smallest unit of memory our hypothetically machine can
process).

Let's also assume, that you can pack everything, that happens in
a operation into a single opcode, which by definition fits into
a blurp: In case of a comparision this would include the value,
to operand to compare to and where to jump if the comparision
satisfies. Assignment is a own operation, thus it doesn't go
into the compare operation (it would be rather inefficient to
try to fit all possible things you do after a comparision into a
huge variety of comparision opcodes).

In the following example each line should be considered as a
single operation. And let's assume that every operation takes one
tick to execute. Labels take no memory. A table is a label with
a number of values following. The label of the table itself
doesn't consume memory either, however a compiler/assembler
might decide to insert a relative jump just before the table so
that the program doesn't run into it.

The operations are like this:

compare $variable $value $jump_label

assign $variable $value | $table[$index]

jump $jump_label

$jump_label:

$table $number_of values:
$value
$value
...

The shortest compare/assign program for the month problem would
look like this

compare month 1 month_31
compare month 2 month_28
compare month 3 month_31
compare month 4 month_30
...
compare month 11 month_30
compare month 12 month_31
month_30: assign $days 30
jump end
month_31: assign $days 31
jump end
month_28: assign $days 28
end:

This program consists of 12+5 = 18 operations. There are no
tables, to the program consumes only those 18 blurps. Running
time is between 3 and 14 ticks.

Now let's have a look on the table based variant

days_in_month 12:
31
30
28
31
...
30
31
assign $days days_in_month[$month]

This program consists of 2 operations (table jump and assignment)
and 12 values. This makes a memory consumption of 12+2 = 14
blurps. Running time is always 2 ticks. You see that the table
based approach both takes less memory (14 blurbs vs. 18 blurps)
and always runs faster (2 ticks vs. 3...14 ticks) than the
comparison/jump/assignment based solution.

And that was just this artificial example. In most real world
applications the operands to a comparision would take additional
memory, at it's best the opcode would also address some
register(s), but not more, so this would also add the
instructions to fill the registers with the values.

Now you might want to state the above examples are indeed
artificial. But OTOH they're not so artificial then again. Most
assembler code works that way and if you take the AVR
architecture it almost looks that way there. And if you're
thinking of Python you can bet, that an opcode will not contain
all information, but have the operands encoded in additional
values, consuming memory.

Look up Table is more efficient: Debate solved.

Wolfgang Draxinger

m - 2 and 30 + bool(1 << m & 5546) or 28
sub x' x 2
cjump x' 0 $but_28
shift x'' 1 x
and x'' 5546
cjump x'' 0 $not_31
add x'' 1
$not_31:
add x'' 30
cjump x'' 0 $but_28
assign $days x''
jump $end
$but_28:
assign $days 28
jump $end
$end:

22 blups, 4, 9, 10, 12, or 13 ticks.

 

[castironpi]

days_in_month 12:

31
30
28
31
...
30
31
assign $days days_in_month[$month]

This is missing
days_in_month 12:
31
break
30
break

Or the addition
add $x' $x offset
store $r0 $x'
assign $days $r0

Is that 4 ticks or 5; or 24 blips?