4 ms·

In 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 k

In 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 ago
Uh, 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 ago
  I'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 ago
Indeed, 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.
- Tichy 18y ago
  "sort{rand}" I am not very experienced with Ruby, but this sounds like a really bad idea? In the worst case, sort might run forever? Don't know what sort algorithms Ruby uses by default, maybe for some it doesn't matter, but it seems best to not make assumptions about the underlying algo?
  - thenduks 18y ago
    You're right that `sort{rand}` is a bad idea, but not because it could run forever. `rand` in Ruby just returns a number like 0.9307038377384, used in sorting this will just always sort the same way (since it's always > 0). So Ruby will use the result of `rand` to determine if one element should be sorted before or after another. So maybe a better solution would be to use `sort{rand - 0.5}` or something, so that it will randomly be either < or > 0. I was curious so I looked Array#rand in the Active Support source code[1], the implementation uses the following code to get a random element: def rand self[Kernel.rand(length)] end So, this is much better than sorting the whole array in random order and pulling one off the top :) But it still uses `rand`. [1] http://github.com/rails/rails/tree/e56b3e4c0b60b2b86f5ca9c5e5a0b22fa34d37ab/activesupport http://github.com/rails/rails/tree/e56b3e4c0b60b2b86f5ca9c5e...

lsb 18y ago

Uh, 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 ago
I'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 ago

Indeed, 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.

Tichy 18y ago
"sort{rand}" I am not very experienced with Ruby, but this sounds like a really bad idea? In the worst case, sort might run forever? Don't know what sort algorithms Ruby uses by default, maybe for some it doesn't matter, but it seems best to not make assumptions about the underlying algo?
- thenduks 18y ago
  You're right that `sort{rand}` is a bad idea, but not because it could run forever. `rand` in Ruby just returns a number like 0.9307038377384, used in sorting this will just always sort the same way (since it's always > 0). So Ruby will use the result of `rand` to determine if one element should be sorted before or after another. So maybe a better solution would be to use `sort{rand - 0.5}` or something, so that it will randomly be either < or > 0. I was curious so I looked Array#rand in the Active Support source code[1], the implementation uses the following code to get a random element: def rand self[Kernel.rand(length)] end So, this is much better than sorting the whole array in random order and pulling one off the top :) But it still uses `rand`. [1] http://github.com/rails/rails/tree/e56b3e4c0b60b2b86f5ca9c5e5a0b22fa34d37ab/activesupport http://github.com/rails/rails/tree/e56b3e4c0b60b2b86f5ca9c5e...