Re: Solve a Debate
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 Along the same lines, you could populate the table somewhat sparsely, and goto a modulo key. You could even put functions in it: setreturn $endoftable hash month goto -0 -1 -2 jan.- 3: setvjmp janfun -4 -5 apr.- 6: setvjmp aprfun $endoftable Sweet! Are you stack-ops? -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
Past a many-small certain point on numbers of hash-tables, if that's the right word, in a program, and intepreter process on a machine, is it be more time-efficient to allocate a 2**32-byte table? Are 'modulo' and 'doublesize' the only steps of the lookup process that it would eliminate, and are they expensive ones? If so, what point? If not, what's a tighter bottleneck?- Hide quoted text - - Show quoted text - There's something to it. As stated, your idea cannot be implemented with current assumptions that Python makes, specifically that integers are their own hash values, possible others. Relax this, and you may be on to something, have a path, such as keying the object id into the hash value. -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
On Feb 17, 11:23 pm, greg [EMAIL PROTECTED] wrote: Wolfgang Draxinger wrote: 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). In Python, there's the additional twist that for lookup tables based on a mutable type, such as a dictionary, you need to execute code to build the dictionary. So you end up using very roughly twice the memory -- for the code to build the dictionary, and the dictionary itself. If the dictionary isn't too huge, and it's looked up many times during each run of the program, the extra speed of the dict lookup is probably worth the overhead of creating it. If the dict is very large, and is consulted relatively few times in a given run, then it might well be faster and not use too much more memory to use a tree (NOT a linear sequence!) of if-else statements in the code. You could also consider loading the dict from some other form, such as a pickle, instead of creating it using code. This would use less memory, although probably would take roughly the same time to set up the table. For extremely large infrequently-used tables, it's probably better to look at not loading the whole table into memory at all, and keeping it in some kind of external indexed structure such as a b-tree, relational database, etc. In other languages, the tradeoffs will be completely different. E.g. in C, if you can describe the table entirely with static data, it'll be very fast to load and incur no overhead for code to create it at all. Also, with demand-paging out of the executable file, and infrequent lookups, only parts of the table will actually get loaded anyway. -- Greg Past a many-small certain point on numbers of hash-tables, if that's the right word, in a program, and intepreter process on a machine, is it be more time-efficient to allocate a 2**32-byte table? Are 'modulo' and 'doublesize' the only steps of the lookup process that it would eliminate, and are they expensive ones? If so, what point? If not, what's a tighter bottleneck? -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
nexes wrote: 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 -- E-Mail address works, Jabber: [EMAIL PROTECTED], ICQ: 134682867 -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
On Feb 17, 7:05 am, Wolfgang Draxinger [EMAIL PROTECTED] wrote: nexes wrote: 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 -- E-Mail address works, Jabber: [EMAIL PROTECTED], ICQ: 134682867 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
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? -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
[EMAIL PROTECTED] wrote: 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 What shall there be missing? breaks? You noticed, that I defined some artificial architecture on purpose. days_in_month 12: tells it, that the next 12 blurps are tabular data, that can be indexed. If the interpreter hits the line days_in_month 12: it will unconditionally jump 12 instructions forward, where it hits the assign instruction, which assignes a value from a table by an index given into a variable. We're not talking about Python here. I introduced this architecture just to showcase that even in the most optimal situation, where special RISC operations are avaliable a LUT is still better suited. Wolfgang Draxinger -- E-Mail address works, Jabber: [EMAIL PROTECTED], ICQ: 134682867 -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
What shall there be missing? breaks? You noticed, that I defined some artificial architecture on purpose. days_in_month 12: tells it, that the next 12 blurps are tabular data, that can be indexed. If the interpreter hits the line days_in_month 12: it will unconditionally jump 12 instructions forward, where it hits the assign instruction, which assignes a value from a table by an index given into a variable. We're not talking about Python here. I introduced this architecture just to showcase that even in the most optimal situation, where special RISC operations are avaliable a LUT is still better suited. Month lengths are tabular, as opposed to formulaic. -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
Wolfgang Draxinger wrote: 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). In Python, there's the additional twist that for lookup tables based on a mutable type, such as a dictionary, you need to execute code to build the dictionary. So you end up using very roughly twice the memory -- for the code to build the dictionary, and the dictionary itself. If the dictionary isn't too huge, and it's looked up many times during each run of the program, the extra speed of the dict lookup is probably worth the overhead of creating it. If the dict is very large, and is consulted relatively few times in a given run, then it might well be faster and not use too much more memory to use a tree (NOT a linear sequence!) of if-else statements in the code. You could also consider loading the dict from some other form, such as a pickle, instead of creating it using code. This would use less memory, although probably would take roughly the same time to set up the table. For extremely large infrequently-used tables, it's probably better to look at not loading the whole table into memory at all, and keeping it in some kind of external indexed structure such as a b-tree, relational database, etc. In other languages, the tradeoffs will be completely different. E.g. in C, if you can describe the table entirely with static data, it'll be very fast to load and incur no overhead for code to create it at all. Also, with demand-paging out of the executable file, and infrequent lookups, only parts of the table will actually get loaded anyway. -- Greg -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
On Feb 15, 11:50 pm, Steve Holden [EMAIL PROTECTED] wrote: Dan Bishop wrote: On Feb 15, 10:24 am, nexes [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
On Feb 16, 3:48 pm, Dan Bishop [EMAIL PROTECTED] wrote: On Feb 15, 10:24 am, nexes [EMAIL PROTECTED] 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) -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
[EMAIL PROTECTED] wrote: On Feb 15, 11:50 pm, Steve Holden [EMAIL PROTECTED] wrote: Dan Bishop wrote: On Feb 15, 10:24 am, nexes [EMAIL PROTECTED] 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.holdenweb.com/ -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
On Feb 17, 9:57 am, [EMAIL PROTECTED] wrote: 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. 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
En Sat, 16 Feb 2008 19:43:37 -0200, John Machin [EMAIL PROTECTED]
escribi�:
On Feb 16, 3:48 pm, Dan Bishop [EMAIL PROTECTED] wrote:
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)?)
--
Gabriel Genellina
--
http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
On Feb 17, 11:11 am, Gabriel Genellina [EMAIL PROTECTED]
wrote:
En Sat, 16 Feb 2008 19:43:37 -0200, John Machin [EMAIL PROTECTED]
escribi�:
On Feb 16, 3:48 pm, Dan Bishop [EMAIL PROTECTED] wrote:
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.
--
http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
John Machin wrote:
On Feb 17, 11:11 am, Gabriel Genellina [EMAIL PROTECTED]
wrote:
En Sat, 16 Feb 2008 19:43:37 -0200, John Machin [EMAIL PROTECTED]
escribi�:
On Feb 16, 3:48 pm, Dan Bishop [EMAIL PROTECTED] wrote:
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!
--
Steve Holden+1 571 484 6266 +1 800 494 3119
Holden Web LLC http://www.holdenweb.com/
--
http://mail.python.org/mailman/listinfo/python-list
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 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? -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
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/python-list
Re: Solve a Debate
If the data becomes much bigger, change your way of storing it, not the code. You don't want to code hundreds of if - elif - else because you have hundreds of different data, right ? TheDailyWTF is full of horror stories like this, by the way ;-) Data growth shouldn't result in modification in logic code. Also I find that avoiding conditionals is always a win. That's in the spirit of the pythonic way of removing what would be an if-elif chain (or a switch statement in another language) by a dict-based dispatch. Returning to your month exercise... Since code is data, assigning the numbers of days or comparing the month number in if statements is basically the same. In the end, you have twelve different values stored in one way or another in your program and loaded in RAM at execution time. Therefore, I find the array solution (or whatever storage you wish to use) better by all counts. Cheers, Quentin On Fri, Feb 15, 2008 at 5:24 PM, nexes [EMAIL PROTECTED] 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? -- http://mail.python.org/mailman/listinfo/python-list -- http://mail.python.org/mailman/listinfo/python-list
RE: Solve a Debate
-Original Message- From: [EMAIL PROTECTED] [mailto:python- [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
On 2008-02-15, Ivan Van Laningham [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
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 [EMAIL PROTECTED] 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/python-list -- 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
On Feb 15, 12:32 pm, Grant Edwards [EMAIL PROTECTED] wrote: On 2008-02-15, Ivan Van Laningham [EMAIL PROTECTED] 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 0010 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? -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
On Feb 15, 10:24 am, nexes [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Solve a Debate
Dan Bishop wrote: On Feb 15, 10:24 am, nexes [EMAIL PROTECTED] 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.holdenweb.com/ -- http://mail.python.org/mailman/listinfo/python-list
