Talk:Equilibrium index: Difference between revisions
(Bogus optimizations?) |
(Yep.) |
||
| Line 1: | Line 1: | ||
Some of the "one pass" solutions, such as in Perl6 and Python examples, are dubious. Both use hash tables to store temp sums ("hash" in Perl, "dict" in Python), so as to save one pass through the input array because the result requires a single dictionary lookup. In reality, however, hash table insertion can be quite expensive, and because all indices are inserted into the hash somewhere, it's almost garanteed to be no smaller than just storing the sums in a flat list. It is probably more efficient, both speed- and space-wise, to just run a second pass through the input list or a stored summation list to pick out the right indices -- it's n array lookup vs n dictionary lookup, generally much faster, without even considering low level things like cache consistency. |
Some of the "one pass" solutions, such as in Perl6 and Python examples, are dubious. Both use hash tables to store temp sums ("hash" in Perl, "dict" in Python), so as to save one pass through the input array because the result requires a single dictionary lookup. In reality, however, hash table insertion can be quite expensive, and because all indices are inserted into the hash somewhere, it's almost garanteed to be no smaller than just storing the sums in a flat list. It is probably more efficient, both speed- and space-wise, to just run a second pass through the input list or a stored summation list to pick out the right indices -- it's n array lookup vs n dictionary lookup, generally much faster, without even considering low level things like cache consistency. |
||
: I remember thionking just that when I added it to Python, but at the time I was trying to have Python versions of most of the techniques shown so added it anyway. If a 2Gig X86 machine was reading data off a paper tape then maybe it would be worth consideration :-) --[[User:Paddy3118|Paddy3118]] 20:41, 7 June 2011 (UTC) |
|||
Revision as of 20:41, 7 June 2011
Some of the "one pass" solutions, such as in Perl6 and Python examples, are dubious. Both use hash tables to store temp sums ("hash" in Perl, "dict" in Python), so as to save one pass through the input array because the result requires a single dictionary lookup. In reality, however, hash table insertion can be quite expensive, and because all indices are inserted into the hash somewhere, it's almost garanteed to be no smaller than just storing the sums in a flat list. It is probably more efficient, both speed- and space-wise, to just run a second pass through the input list or a stored summation list to pick out the right indices -- it's n array lookup vs n dictionary lookup, generally much faster, without even considering low level things like cache consistency.
- I remember thionking just that when I added it to Python, but at the time I was trying to have Python versions of most of the techniques shown so added it anyway. If a 2Gig X86 machine was reading data off a paper tape then maybe it would be worth consideration :-) --Paddy3118 20:41, 7 June 2011 (UTC)