39 ms·
A missing feature in most dynamic languages: take a random key from an hash table.
- compay 18y agoIt's "missing" because it's not an every day operation, and it's easy to do using other built-in functions. Languages in general should leave out things that are specialized use cases but easy to implement using simpler pieces. If you fill a language's standard library up with "useful" stuff like this, you eventually end up with a morass like PHP.
- antirez 18y agoI'm a minimalist too, but this time I don't agree. You can't have this feature at all if it is not implemented in the core, not in O(1), and is general enough, hash.random_key() will not really bloat the language and it is very clear what it does. If there is 'partition' in Ruby's array I think random_key is not so strange to see inside, especially given that you can't implement it in Ruby itself.
- mooism2 18y agoIt's missing because you can't get O(1) and have each key equally likely to be returned, right?
- antirez 18y agoare you sure? I don't think so. See the new version of the pseudo code. Just select a new random index every time you reach an empty bucket and you are done.
- mooism2 18y agoHmm, yes, I think you are right.
- damienkatz 18y agoUnfortunately, it's not guaranteed to return, ever. It's a psuedo-random generator, it can (though not real likely) get stuck in a cycle of buckets it checking, the worst case time complexity O(∞). Even if it uses a real random generator, I'm not sure it's guaranteed to return.
- antirez 18y agowith an hash table 50% full the probability of it not returning after just 100 tries is: 0.0000000000000000000000000000007 I think we can sleep without problems about it ;)
- lacker 18y agoIf you want to guarantee it returns, then after N failed operations, just convert the hash table to a list and pick something at random. That will take O(N) time, but since you've already spent O(N) time it amortizes out to no additional cost.
- lacker 18y agoTypically you do not need to both randomly select one element and use them as keys in a map. If you do need both, the easy way to do it is to just keep the keys in an array as well as in a hash table. The algorithm the author uses is not a good example. A simpler way to find the approximate most common elements in a large collection is to use a heap to store the (object, count) pairs. Still O(1), and you can remove the element with the lowest count each time instead of getting an approximation.
- antirez 18y agolacker the example was just useful to explain how sometimes it can be useful to run randomized algorithms with hash tables. A real world example is a DNS cache that can't hold more than N elements, you can just remove one at random. Another one is a cache where elements can expire, and you want to perform a lazy cleanup.
- antirez 18y agoStill from this page: http://en.wikipedia.org/wiki/Heap_(data_structure) http://en.wikipedia.org/wiki/Heap_(data_structure) I can't see how it is possible using an heap to count most common elements in large collction, without approximation, and using constant memory. May you please argument better the original comment? Thanks
- abecedarius 18y agoHere's a Brian Hayes column on good algorithms for this problem: http://www.americanscientist.org/issues/id.3822,y.0,no.,content.true,page.1,css.print/issue.aspx http://www.americanscientist.org/issues/id.3822,y.0,no.,cont... I think lacker was probably thinking of a correct algorithm for finding the n largest values in a set, instead of the n most frequent values.
- antirez 18y agovery interesting, thanks. I could like to simulate the problem in order to check how my simple algorithm performs compared to others described in the article. EDIT: I analyzed a bit the differences between Yale University algorithm using M conters and my algorithm. It is interesting that while the Yale's algo gives you all the top elements with a given minimal frequency it is O(M) because you have to decrement M counters for every new element not matching any of elements in the M registers. My algorithm even if randomized (so you are not sure you track all the top M elements, but the output will be an approximation of that) can bring the M-probably-top-elements using O(1) time for element. The memory used is O(M) in both the algorithms. I wonder if the algorithm I proposed was described or not. Note how you can trade time for accuracy selecting more accurately what element to drop to add the next one. If you sample three elements dropping the minimum of the three the accuracy will be a given one, but if you sample ten elements it will be different. I wonder if somebody is able here to analyze this algorithm more in depth.
- subwindow 18y agoIn Ruby (w/ activesupport): myhash[myhash.keys.rand] Is an O(n) operation, for no apparent reason. At least in 1.9, they're obviously keeping track of the keys internally in an array to support the ordered hashes. However, when you do Hash.keys, it does a foreach on the hash and creates a brand new array. I'm still not sure why getting a random key is particularly useful, but the real problem is that getting the keys of a hash should be an O(1) operation, instead of an O(n) one.
- lsb 18y agoUh, here's how a hash table is commonly built. Ruby's may be optimized, but the jist is the same. You have N buckets, a hashing function for key => bucket #, and each bucket has a linked list of value pointers. You hash the key down to a bucket number, walk the list until you find your key, which will give you your value. To get all the keys, you need to walk all the buckets' lists, which is O(n).
- subwindow 18y agoI'm perfectly aware of that, and if you read my comment you'll see that I acknowledge that fact. However, I also said: > they're obviously keeping track of the keys internally in an array to support the ordered hashes. Which means that they can return them in an O(1) operation, but they choose not to for some reason. Edit: I'm wrong- I just remembered why they can't return them, and it is because they're not storing the keys in an array. D'oh. They're using a doubly-linked list. So to return a list of keys you'd need to walk the linked list- an O(n) operation. See: http://www.igvita.com/2009/02/04/ruby-19-internals-ordered-hash/ http://www.igvita.com/2009/02/04/ruby-19-internals-ordered-h... for more info.
- thenduks 18y agoIndeed, I thought the same thing (re: your code snippet). Even better, assuming you _really_ need to get the value for a random key out of the hash, might be: class Hash def random self[self.keys.sort{rand}.first] end end ... myhash.random This doesn't require activesupport, just for comparison.
- anuraggoel 18y agoPython does have built-in support for getting an arbitrary key: popitem() on a dict. It removes the item from the dict, but you can always add it back. http://docs.python.org/library/stdtypes.html#dict.popitem http://docs.python.org/library/stdtypes.html#dict.popitem Edit: This method returns arbitrary (not random) results; each element is not equally likely to be picked.
- ivank 18y agoThat's "arbitrary", and not random at all. Some basic testing shows that the same dictionary keys will always lead to the same popitem order.
- antirez 18y agoI bet this scan the table from the first to the last bucket.
- anuraggoel 18y agoCorrect, nice catch.
- deleted 18y ago[deleted]
- abecedarius 18y agoFor this to be in a library, I'd want it parameterized by the random number generator. (After being convinced it's really worth it.)
- tptacek 18y agoHow is this operation O(1)? In the worst case, in a table with 4096 buckets and 1 entry, and assuming you "color" the buckets or track them somewhere else, you spend 4096 lookup operations getting the key. In reality, as implemented here, the algorithm doesn't even necessarily terminate.
- wildwood 18y agoMaybe I'm missing something, but the pseudocode looks funky. Is he really assuming at most one key per bucket? This code seems like it fails when the number of keys in the table exceeds the number of buckets. Assuming that 'table.size' returns the number of keys, and not the number of buckets, he'll also be hitting 'index out of bounds' errors. Of course, I could be wrong. Pseudocode can have a funky syntax. :)