Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re: Re: A short meditation about hash search performance

by Anonymous Monk
on Nov 16, 2003 at 05:19 UTC ( #307421=note: print w/ replies, xml ) Need Help??


in reply to Re: A short meditation about hash search performance
in thread A short meditation about hash search performance

Perhaps I need to re-review the analysis of CLR-1990*, because they clearly state on page 223:

The worst-case running time for insertion is O(1). For searching, the worst-case running time is proportional to the length of the list: we shall analyze this more closely below. Deletion of an element x can be accomplished in O(1) time if the lists are doubly linked.

Note, I wasn't referring to perl's hashes in particular, just hashes in general.

* Cormen, Leiserson, Rivest 1990: Introduction to Algorithms. MIT Press, Cambridge Massachusetts.


Comment on Re: Re: A short meditation about hash search performance
Re: Re: Re: A short meditation about hash search performance
by Schemer (Scribe) on Nov 16, 2003 at 08:03 UTC
    Deletion of an element x can be accomplished in O(1) time if the lists are doubly linked.

    It still means you need to find an object before you can delete it.
Re: A short meditation about hash search performance
by Abigail-II (Bishop) on Nov 16, 2003 at 22:15 UTC
    If you read page 223 carefully, you see that the arguments to the function Chained-Hash-Delete are (T, x) and not (T, k). Now x is here the node to be deleted. That is, you have already found the node with key k to be deleted. So, yes, for a double linked list, the actual deletion is in constant time, but that does not include the time to search for the node to be deleted.

    Abigail

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://307421]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (5)
As of 2015-07-03 18:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (55 votes), past polls