In response to Zecronious
Zecronious wrote:
This is tutorials and snippits. It's where you put things for other people to use. And yes of course my attitude seems hostile because I can't believe my eyes that Lugia put this here for other people to use. It's a really bad example of how to write a shuffle process.

Yes I use a new list but that's what makes mine work so effectively.

Here, I took out the extra list and it still works fine.

> proc
> shuffle(list/givenList)
> var/nextElement
>
> for(var/i = 1; i <= givenList.len; i++)
>
> nextElement = rand(1, givenList.len)
> nextElement = givenList[nextElement]
>
> givenList.Remove(nextElement)
> givenList.Add(nextElement)
>
> return givenList
>

That's a fully optimized, fully functional, completely effective shuffle.

Something people should use, something that should be in tutorials and snippits, not this snippit by Lugia.

Hostility is never acceptable due to something being a poor example of how something should be done. Would you give someone in the developer help section hostility due to asking how to make something, or providing an inefficient/broken sample of programming? I don't think so. Your correct, this is the snippits and turotials area. Lugia provided a snippit that people can use and alter. Regardless of the quality, or if it's exactly what you'd prefer, it's still exactly that. A viable snippit to be used by anyone who would like to. I'm grateful for him for posting it because it is an approach i'd take rather than the one he linked to.

To address the "inefficientcy" of his snippit, it's not a really bad example in the least. It properly demonstrates how to use the list swap() proc, which is something he even states in the OP he was trying to do; something yours does not use. Yet if you haven't noticed a lot of programming languages "random" procedures aren't completely random. BYOND's isn't entirely random, nor is Javas from my experience. This could lead to less than desirable results. Lugia was also correct about a prior point - You can never shuffle too much. That's exactly where he'd beat the non-fully randomized issues, regardless of him not needing it to be there. He'd shuffle once in a more realistic way, then again, then twice more. Giving a fully realisticly randomized deck. Think about it, would you shuffle a deck by taking out one card and adding it to a new pile, or would you take two "cuts" of the deck, and shuffle those together by essentially "Swaping" cards from the two cuts with a bridge(forgive me if this is the wrong term, it's 3 AM and i'm yet to sleep)? Lugia's approach was a more realistic way to shuffle as apposed to one of the other various simple ways to create a shuffle procedure alike the one you created. That's all.

It's obvious an apology to those in the thread - due to your implied tone and lack of regard for the topic itself - from you won't be coming, but I'd personally appreciate it if you'd keep the hostile attitude to a minimum. Regardless of right or wrong a hostile environment helps nothing. Thank you.
I just tested both Zecro's most recent snippet and my original post.

For small lists, his is more efficient, because as he pointed out, my iterations is bogging down the process. But you can be flexible with the iterations.

For large lists my original snippet takes over, especially if I modify iters = 3 or 4 * L.len. Once we start talking 7000 element lists, my code uses half the memory his does (With the adjustment to iters = 3 or 4 * L.len).

He's right, for DM, his snippet is better. I made my code with my work in numerical analysis in mind.
In response to Lugia319
Did you test mine as well, Lugia? I would like to know how actual card-shuffling techniques fair against other shuffling techniques. Just run the Shuffle() proc five times on the list per randomization because 5 is some sort of standard for card shuffling.
No but I went at it. I had your code loop 5 times to account for your shuffle.

Shuffle1() is my shuffle, Shuffle2() is Oasis, and Shuffle3() is Zecro's.

NOTE: I have iters = 4 * L.len in all of the following examples.

100 Elements
Profile results (total time)
Proc Name Self CPU Total CPU Real Time Calls
---------------------- --------- --------- --------- ---------
/mob/proc/Shuffle1 0.001 0.001 0.001 1
/mob/proc/Shuffle2 0.000 0.000 0.000 1
/mob/proc/Shuffle3 0.000 0.000 0.000 1

1000 Elements
Profile results (total time)
Proc Name Self CPU Total CPU Real Time Calls
---------------------- --------- --------- --------- ---------
/mob/proc/Shuffle2 0.010 0.010 0.010 1
/mob/proc/Shuffle1 0.005 0.005 0.005 1
/mob/proc/Shuffle3 0.003 0.003 0.003 1

2000 Elements
Profile results (total time)
Proc Name Self CPU Total CPU Real Time Calls
---------------------- --------- --------- --------- ---------
/mob/proc/Shuffle2 0.023 0.023 0.023 1
/mob/proc/Shuffle3 0.015 0.015 0.015 1
/mob/proc/Shuffle1 0.014 0.014 0.014 1


5000 elements
Profile results (total time)
Proc Name Self CPU Total CPU Real Time Calls
---------------------- --------- --------- --------- ---------
/mob/proc/Shuffle2 0.135 0.135 0.135 1
/mob/proc/Shuffle3 0.047 0.047 0.047 1
/mob/proc/Shuffle1 0.024 0.024 0.024 1

10000 elements
Profile results (total time)
Proc Name Self CPU Total CPU Real Time Calls
---------------------- --------- --------- --------- ---------
/mob/proc/Shuffle2 0.254 0.254 0.254 1
/mob/proc/Shuffle3 0.071 0.071 0.071 1
/mob/proc/Shuffle1 0.050 0.050 0.050 1

20000 elements
Profile results (total time)
Proc Name Self CPU Total CPU Real Time Calls
---------------------- --------- --------- --------- ---------
/mob/proc/Shuffle2 0.913 0.913 0.913 1
/mob/proc/Shuffle3 0.251 0.251 0.251 1
/mob/proc/Shuffle1 0.100 0.100 0.100 1

As you can see, as the lists get larger, Shuffle1() takes over by quite a bit. When I ran the 20000 element list through Oasis shuffle it took a visible second to process. Sorry to say but your shuffle, Oasis, gets pretty ugly pretty fast (when run 5 times over a list).
In response to Lugia319
Haha nice! Thanks for running this.
Luckily my shuffle was designed for 52 elements. ;)

It gets ugly so fast because it's O(N^5) if you run it five times. :P
This is what we have to put up with for the sake of realism.
With Lugia's code, as soon as the number of iterations is less than the size of the array Lugia is only shuffling some of the elements. Lugia's code at that point can't possibly shuffle the whole thing.

Once that happens I don't think my algorithm and his compare. He's shuffling part of the array and leaving other parts alone. My algorithm gives every single element in the array a new random position.

Do you see how they do different things? Of course his runs faster, it runs at the same speed every time. I still think my shuffling algorithm is superior because Lugia's sacrifices effectiveness for a shorter run time.

"Do the job right or don't do it at all" is the way I feel about shuffling. Sorry if that sounds cough 'hostile' but that's just what I think.
In response to Zecronious
Zecronious wrote:
With Lugia's code, as soon as the number of iterations is less than the size of the array Lugia is only shuffling some of the elements. Lugia's code at that point can't possibly shuffle the whole thing.

Once that happens I don't think my algorithm and his compare. He's shuffling part of the array and leaving other parts alone. My algorithm gives every single element in the array a new random position.

Do you see how they do different things? Of course his runs faster, it runs at the same speed every time. I still think my shuffling algorithm is superior because Lugia's sacrifices effectiveness for a shorter run time.

"Do the job right or don't do it at all" is the way I feel about shuffling. Sorry if that sounds cough 'hostile' but that's just what I think.

Rather than being hostile, you can just create your own Tutorial/Snippet if you find this ineffective. Others may prefer his snippet, some may not.
My proc can never shuffle less elements than its size. Rather, it always swaps elements 4 * L.len times (read the note I put).

EDIT: I actually Histogrammed this out (source available here if desired). I made a list of permutations of the list (1, 2, 3, 4). Then I compared each outcome of a shuffle to an element in that list of lists.

Oasis only lets 4 permutations through. I wasn't expecting that but hey, math.

As far as probabilities go, both my code and Zecro's give each permutation a fair shot at being drawn. So I guess it comes down to preference, really. Of course I only tested this on 4 element lists because I didn't feel like going through over nine thousand permutation definitions and outputting all of those. So for higher list lengths, who knows?
I dunno about you guys, but in my no-longer published card game, I shuffle it like this:

        Shuffle()
for(var/i=1 to talon.len)
talon.Swap(i, rand(1,talon.len))


It works.
haha ^Small and Effecient
SSX: The problem with that approach is that it's not a fair shuffle. Elements at the start of the list are going to get swapped more times than elements at the end of the list, which distorts the probability distribution of outcomes.

Zecro's approach is definitely the best if you want a uniform distribution of permutations. 'emulating' a hand shuffle like Oasis does is fine if you want to emulate a hand shuffle rather than a uniform output distribution.

Frankly I can't see a good reason to use your approach, Oasis, when Zecro's does the same thing, but cleaner.
Page: 1 2