Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re: A short meditation about hash search performance

by Anonymous Monk
on Nov 15, 2003 at 21:58 UTC ( #307389=note: print w/replies, xml ) Need Help??


in reply to A short meditation about hash search performance

The epected or average search time is O(1) under reasonable assumptions, the worst case is O(n) for the fully degenerate case. Insertion and deletion can be done in O(1) worst case time. Most people just state that basic hash operations can be done in O(1) average time.

  • Comment on Re: A short meditation about hash search performance

Replies are listed 'Best First'.
Re: A short meditation about hash search performance
by Abigail-II (Bishop) on Nov 16, 2003 at 02:58 UTC
    Well, if you can't do queries in O(1) time, you can't do deletes in O(1) time (because to delete something, you first need to find it), and you can only do inserts in O(1) if you accept duplicates - which Perl hashes don't.

    Abigail

      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.

        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

        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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://307389]
help
Chatterbox?
[marto]: hey Corion, good weekend?
[Corion]: marto: Yeah, even though I didn't write any code :)
[Corion]: But at least I have a plan of action to move the site to https, played some (free!) VR games with friends and watched the plans for the next German Perl workshop progress ;)
[Corion]: AltSpace VR is amazingly good - highly polished and with some of the games you get for free what you'd pay EUR 20 or EUR 40 otherwise
[Corion]: But maybe it's also due to that I play with friends, which makes a game more enjoyable anyway ;)

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (8)
As of 2017-08-21 09:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Who is your favorite scientist and why?



























    Results (319 votes). Check out past polls.

    Notices?