Loading ...
Sorry, an error occurred while loading the content.

5187Re: [hackers-il] Algorithm for randomly choosing a question

Expand Messages
  • Omer Zak
    Jul 6, 2012
      On Sat, 2012-07-07 at 08:20 +0300, Ori Idan wrote:
      [... description of the problem was snipped ...]
      > My wish is to have an algorithm which requires only bounded
      > number of
      > computations of random numbers (i.e. no loop) to accomplish
      > the above.
      > Assume that N is large, so keeping lists of questions in
      > memory is ruled
      > out.
      > You don't have to keep a list of questions, just a list of numbers
      > where each number represent a question.
      > A question you want to appear twice as much as any other, put it twice
      > in the list.
      > For a question you want to appear 100 times less then any other, use
      > the algorithm you suggested.

      Thanks for your interest.

      The proposed approach has the problem of memory consumption of order of
      O(N) (where N is the number of the questions). I'd like to see an
      algorithm whose memory consumption is closer to O(1) than to O(N).

      --- Omer

      Bottom posters are filthy heretics and infidels and ought to be burned
      on the stake after having been tarred, feathered and having rotten eggs
      thrown at their faces!
      My own blog is at http://www.zak.co.il/tddpirate/

      My opinions, as expressed in this E-mail message, are mine alone.
      They do not represent the official policy of any organization with which
      I may be affiliated in any way.
      WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
    • Show all 7 messages in this topic