clipka wrote:
> I think there's nothing wrong about it 

That's why I was confused. You were characterizing it as "incorrect" and 
"not a good thing", rather than "inefficient", and talking about 
mathematical constructs rather than computational elements.

> if that structure also provides the
> same performance as a true hashtable (which, as a quick guess, it probably
> doesn't). Or if performance is not an issue.

I think if you're using Python or PHP, you're not too worried about the 
performance issues. If you're using PHP and your program runs more than five 
seconds CPU time, you're probably doing something wrong and ought to be 
using a different language anyway.

> Added features typically come with added execution time. So added features you
> don't need for a certain job typically come with wasted execution time.

It adds a handful of instructions to inserts and deletes, and no overhead to 
lookups, and probably *saves* time iterating over the array.

In other words, it's all O(1) with a constant on the order of a dozen 
machine instructions amortized (not counting hashing the key), regardless of 
whether you preserve order or not.



5 million integer key array inserts in PHP: 3.3 seconds
5 million dict inserts in Python: 2.3 seconds
5 million list appends in Python: 1.9 seconds
5 million integer key inserts then lookups in PHP: 4.2 seconds
5 million dict inserts and then lookups in python: 4.3 seconds
5 million list element appends then lookups in Python: 3.4 seconds

5 million inserts and iterate-over-values in PHP:     9.5 seconds
5 million inserts and iterate-over-values in python: 133 seconds

(Each is 5 cycles of a million entries each, lest we run out of RAM
  in the VM. :-)

I guess it depends what you want to do. If you often iterate over the 
values, clearly you should go with PHP. If you often work with more than 
five million entries in one PHP page, you're probably doing something wrong.

> As stated before: No problem if you have enough time to waste.

Given the languages are interpreted to start with, if four machine 
instructions per insert into your dictionary is breaking the bank, you 
probably shouldn't be using hashtables to start with. You should be using 
interned strings and modulus operators on the addresses.

If you want to use PHP or Python and have trouble with how slow the built-in 
data structures are, chances are you should be using PHP anyway.

-- 
   Darren New, San Diego CA, USA (PST)
   There's no CD like OCD, there's no CD I knoooow!

Post a reply to this message