Hacker News Reader

Comment by subwindow | Hacker News Reader

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.

View on HN

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).

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-h... for more info.

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.

"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?

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/e56b3e4c0b60b2b86f5ca9c5e...

Reply on news.ycombinator.com