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]

Reply via email to