C++, most obvious solution


  • 0
    S

    maybe i missed it, but i haven't seen the most obvious solution. it performs better than the deterministic solutions in both theory and practice

    while(true) {
      int i = rand() % nums.size();
      if(nums[i] == target)return i;
    }
    

  • 0

    Sorry, equivalent to this one :-P

    Can you tell more about how it "performs better than the deterministic solutions in both theory and practice"?


  • 0
    S

    @StefanPochmann my bad. new to this problem. as to the performance issue, consider it as a poisson process: the expected comparisons to hit the right value is n/k where k is the multiplicity. so for unique value, it matches the n comparisons of the scanning method. and perform much better otherwise. the non-comparison operations per comparison remains the same(assuming rand() is as fast as std operation).


  • 0

    @siwei.yang But it uses one rand call in every iteration, and random number generation can be slow (don't know how slow in the language you used). It could be faster to use just one rand call per pick call, as some solutions do. Also, there's at least one solution with O(lg(n)) pick which I don't think is worse than yours.


  • 0
    S

    @StefanPochmann true, therefore it depends. but at least with c++ std, sudo-rand isn't too bad. a lot can count in the real world, but we are testing against the test cases here. it clocked faster on leetcode. the O(lg(n)) solution is an interesting idea. but sorting the entire list is costly. if that much time is allowed per list, we can use better data structures.


  • 0

    @siwei.yang said in C++, most obvious solution:

    sudo-rand

    Is that a rand that normal users aren't allowed to use? :-)

    it clocked faster on leetcode.

    If you already measured that, then why not share the results? Would be nice to see, and more useful than an unclear claim.


  • 0
    S

    @StefanPochmann afaict, most rand are implemented as sudo-rand. it is called so because the number is generated from predefined sequence (e.g. n*23409852 it should be more complicated but you get the idea). without knowing the hidden parameter, the sequence looks random and takes on values uniformly. for all intents and purpose with respect to most programmers, sudo-rand is random. however, the crypto ppl define true randomness as underlying no patterns at all. therefore, we have to call it sudo-rand. to the best of my knowledge, sudo-rand costs about 3 std ops(in other words, it will match the linear scan when k = 2). it is possible to use faster sudo-rand, but im not an expert on that :P

    as to my own runs, it clocked:

    1 day, 17 hours ago Random Pick Index Accepted 123 ms cpp
    1 day, 17 hours ago Random Pick Index Accepted 152 ms cpp

    123ms is the obvious solution.


  • 0

    It's not "sudo". It's "pseudo". What you're talking about has nothing to do with sudo.


  • 0
    S

    @StefanPochmann said in C++, most obvious solution:

    pseudo

    my bad. pseudo random it is.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.