Solved Debate for the MathHeads

Discussion in 'Plugin Development' started by Scimiguy, Oct 15, 2015.

Thread Status:
Not open for further replies.
  1. Offline

    Scimiguy

    I suppose it's not strictly Bukkit related.. but I'm going to end up using it in a Bukkit plugin so... ;)

    I already know a method or two, but I'm curious to see how other people here would approach this.


    Given a list of numbers 1-10, how would code it so that the chance of randomly returning any number is less than any number lower than it?

    So the idea is to be able to randomly provide a number between 1 and 10, but the higher the number, the rarer the chance must be.
    The actual scale of chances can be anything.. if you do it so that 10 is 10x more rare than 1, that's fine. If you want 10 to be exponentially more rare than 1, that's fine too.

    Best answer will be chosen based on code efficiency
     
  2. Offline

    Xerox262

    So you're trying to do something like, there's a 1 in 10 % chance that it's a 10 item, a 1 in 9 for a 9 item and so on, with 1 being always if they didn't get something before it?
     
  3. Offline

    Scimiguy

    @Xerox262
    More or less.
    You must return a number from the range 1-10, but the higher the number, the lower the chance.
    You'd want to look into weighted randoms, and weighted sampling to get the idea

    As for the scale (I.E. 10=1/10. 9=1/9), it doesn't matter. If you want to use that scale, it's fine. If you want to make it like 10=1/10000000000, 9=1/1000000000, etc.. That's fine too
    It's all about coming up with the most efficient way to do scaled weighted random sampling
     
  4. Offline

    LucasEmanuel

    Use a weighted RNG.
     
  5. Offline

    Xerox262

    Make a random, get an int between 0 and 9, if it's exactly 0 then it's a 10 number, make an else if, get an int from the random between 0 and 8, if it's exactly 0 then it's a nine number, continue this until you get to your 1 number then make it an else.
     
  6. Offline

    LucasEmanuel

    No, this is very inefficient.

    Here i use this for weighted randoms:
    https://github.com/Chilinot/LucasUt...ucasarnstrom/lucasutils/RandomCollection.java

    EDIT:
    It has an O(log n) time complexity for the lookup.
     
    Xerox262 likes this.
  7. Offline

    mythbusterma

    @LucasEmanuel

    Clever, but nowhere near as good as a simple math trick.

    @Scimiguy

    You could chose a random and take the square root of it, then round down. As the number gets higher, they get progressively more likely to happen. For example, 1 can only be gotten if the value is less than 2.4 or so.

    This is always run in constant time (O(1)).
     
    LucasEmanuel likes this.
  8. Offline

    Scimiguy

    @mythbusterma
    Taking the square root programmatically is very inefficient
     
  9. Offline

    mythbusterma

    @Scimiguy

    In theory, yes. It is an O(n) operation. However, since Java works with a constant number of bits (either 32 or 64, depending on your runtime) it can be considered constant time, as it will always take the same amount of time, not matter the size of the number.

    In all reality, on modern hardware (read: on my outdated i7 running Windows) it takes around 17 nanoseconds (and this never changes), which is far faster than any data structure is.

    So in theory, it could be slow. In practice, it is by far and away the fastest method.
     
  10. Offline

    Scimiguy

    @Xerox262
    Yeah I know your method, it's not the best..


    @mythbusterma

    I'm not sure I understand what your method is exactly, I think I'm misinterpreting it
     
  11. Offline

    LucasEmanuel

    Since the value you are taking the root of has a fixed size-limit (32 or 64 bit) it will always take a constant time to produce a result. I.e. the time it takes to calculate the root of a value on your machine will not change no matter the value, since all values will be of the same size.
     
  12. Offline

    Scimiguy

    @LucasEmanuel

    I mean the method itself -- how it's performed
     
  13. Offline

    LucasEmanuel

    Ah, my misstake.
     
  14. Offline

    mythbusterma

    @Scimiguy

    Something like:

    Code:
    int number = new Random().nextInt(100);
    
    int value = (int) Math.floor(Math.sqrt(number));
    
    switch (value) {
          case 1:
              // do something
          case 2:
              // do something slightly more likely
          ........
          case 9:
              // do something most likely
    }
     
    Scimiguy likes this.
  15. Offline

    Scimiguy

    @mythbusterma
    Definitely the most efficient for low scaling coefficients.
     
Thread Status:
Not open for further replies.

Share This Page