|
A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and simulation. A good example of a random permutation is the shuffling of a deck of cards: this is ideally a random permutation of the 52 cards.
This class provides handy utilities for looping through collections in random orders. This has quite a few uses in RSPS with pid shuffling, finding a random player inside of a region, spawning boss npcs in random orders, etc. This was designed to be extremely performant and wont add any allocations/latency to your application.
Code:package io.insignia.utility import io.insignia.api.utils.Random import kotlin.math.ceil import kotlin.math.ln import kotlin.math.pow /** * Allows collections to be iterated through in a random order without creating any allocations. * * @author Gluon <[email protected]> */ object RandomPermutation { // https://en.wikipedia.org/wiki/Linear_congruential_generator -> Numerical Recipes const val c = 1_0_1_3_9_0_4_2_2_3 // NEVER CHANGE THESE const val a = 1_6_6_4_5_2_5 // NEVER CHANGE THESE inline fun <T> Array<T>.iterateShuffledIndexed(block: (Int, T) -> Unit) { if (size == 0) return doLoop(size) { block(it, this[it]) } } inline fun <T> Array<T>.iterateShuffled(block: (T) -> Unit) { if (size == 0) return doLoop(size) { block(this[it]) } } inline fun <T> List<T>.iterateShuffled(block: (T) -> Unit) { if (size == 0) return doLoop(size) { block(this[it]) } } inline fun doLoop(size: Int, block: (Int) -> Unit) { val m = 2.0.pow(ceil(ln(size.toDouble()) / ln(2.0))).toLong() val seed = Random.get(size) var next = seed.toLong() do { next = (a * next + c) % m while (next >= size) { next = (a * next + c) % m } block(next.toInt()) } while (next != seed.toLong()) } }
Spoiler for Unit tests (if you use unit testing in your server):
Spoiler for My random class (you can use any Random class you want):
You said it works like shuffling a deck of cards, i could use this system for a Box Opening and picking random items to reward?
Good use of extension functions =]. I'd work on your unit tests though!
Most of your tests are useless. Also, why do you use 2 different random variables (SecureRandom and ThreadLocalRandom)?
Also, this won't work for PID shuffling. Because the PID has to be the same for a set amount of ticks. In your implementation you will get a different randomized iteration every time you call doLoop.
For PID it is far more efficient and easier to just maintain an ordered list and shuffle that every x amount of ticks.
Aslo, finding a random player inside a region can be done in O(1) time without iterating by just accessing your data with random index.
Similarly, spawning bosses in random order can just be done by adding a random spawn delay.
If you want to iterate over a data structure in random order it is probably better to just call [Only registered and activated users can see links. ] and then do normal iteration.
#1 This is a legacy code base that initially used ThreadLocalRandom, that method has since been removed.
#2 You would only shuffle your pids when you need it. No one said anything about shuffling pids every tick. If you use this to shuffle pids every tick you have no idea what you're doing. Keeping a list and shuffling it every x ticks is 100% slower than the code above. The code above is always O(1) where your method first needs to clone a list, add all the contents in a random order, then you finally get the O(1) you speak of.
#3 calling shuffled creates an unnecessary allocation. Any allocation is more expensive than what my code does above. If you have a server with thousands of players and you're unnecessarily creating allocations for shuffling pids, spawns, random rewards, etc it will be much slower than what I've posted.
Also how could the unit tests be improved? To me it seems every use case is tested and made sure functionality is working.
Last edited by Gluon; 01-15-2021 at 12:01 AM.
it isn't "far more efficient" without proof. and yes this works perfectly fine for pid shuffling because the whole point of pid shuffling is to NOT get 5 ticks of the same pid; that gives player A an edge over B up to 4 ticks if the duel match starts at the correct time, just after the shuffle.
was this your dissertation? been a while since I've seen someone go balls deep on a snippet topic lol
I would've used one function to test for a dynamic array randomization.Code:@[Only registered and activated users can see links. ] fun test1000() = testArray(fillArray(1000)) @[Only registered and activated users can see links. ] fun test100() = testArray(fillArray(100)) @[Only registered and activated users can see links. ] fun test10() = testArray(fillArray(10)) @[Only registered and activated users can see links. ] fun test5() = testArray(fillArray(5)) @[Only registered and activated users can see links. ] fun test2() = testArray(fillArray(2)) @[Only registered and activated users can see links. ] fun test1() = testArray(fillArray(1))
« Intellij Shortcuts | How to get accurate skill success chances for your server. » |
Thread Information |
Users Browsing this ThreadThere are currently 1 users browsing this thread. (0 members and 1 guests) |