From: "Jonathan E. Paton" <[EMAIL PROTECTED]>
> > affect the performance of:
> > key listings (things like grep /pattern/, keys %hash)
>
> Grep can be slow, especially with patterns. Keys
> could be slow, especially if the dataset is large.
Maybe you could try to use
while (my ($key) = each %hash) {
next unless $key =~ /pattern/
... do whatever you need
}
instead of the
@good_keys = grep /pattern/, keys %hash;
do_something_with(@good_keys);
I'm not sure though ihow much (or if at all) this will help.
> > key lookups (referencing $hash{$key})
>
> Key lookups are done in O(log N), which is pretty
> nippy even with large datasets.
Sorry? If it were a tree then it would be O(log N) (assuming the tree
is reasonably balanced), but hash access should be O(1).
On average of course since if the keys are "well selected" and
behave badly with the hashing function then the accesses will take
time O(N) because all items will end up in the same bucket.
IMHO the only way you could get O(log N) with hashes would be if
the items that end up in one bucket were stored in a tree and it
would be the "worst case scenario".
Jenda
P.S.: I've already forgot quite a lot from the data structures &
computational complexity lectures. I know there are some special
letters for minimum, average and maximum complexity. But I bet
for hashes it's supposed to be
1
1
N
for access and
1
1
N
for insert/delete. (You may end up rebuilding the hash if it gets too
full or too empty).
=========== [EMAIL PROTECTED] == http://Jenda.Krynicky.cz ==========
There is a reason for living. There must be. I've seen it somewhere.
It's just that in the mess on my table ... and in my brain
I can't find it.
--- me
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]