| 12-27-2009, 08:21 AM | #1 |
This does 90 iterations (78+12) worst case scenario I need to improve the algorithm it uses : ). Any ideas? I don't see any way to do this in an indexed array for quick sorting or shell sorting, so this is the best I could come up with. I tried to keep the operations down to a minimum and made the comparisons as small as possible. going to try moving this to a binary tree : ) Code:
scope PlayerVoting initializer Initialization {
//ini demo vars
private int playerOrder[12]
private int curPlayer = 0
private int iterations = 0
//ini demo vars
private int curNumber
private constant int VOTE_MAX_SIZE = 100
//sorting
private int sortCount = 2
private int sorted[13]
private int sortedNext[13]
private int sortedPrevious[13]
private int curSort
private int sortedPlayer[13]
private int sortedLast = 1
define private <this.ini> = {
playerOrder[curPlayer++] = 6
playerOrder[curPlayer++] = 10
playerOrder[curPlayer++] = 8
playerOrder[curPlayer++] = 4
playerOrder[curPlayer++] = 1
playerOrder[curPlayer++] = 9
playerOrder[curPlayer++] = 3
playerOrder[curPlayer++] = 11
playerOrder[curPlayer++] = 7
playerOrder[curPlayer++] = 2
playerOrder[curPlayer++] = 5
playerOrder[curPlayer++] = 0
}//this.ini
define private <this.code> = {
sortedNext[1] = 0
whilenot curPlayer == 0 {
curPlayer--
curNumber = GetRandomInt(1, VOTE_MAX_SIZE)
curSort = sortedLast
whilenot curNumber > sorted[curSort] {
curSort = sortedPrevious[curSort]
iterations++
}//whilenot
//set up new sorted
sorted[sortCount] = curNumber
sortedPlayer[sortCount] = curPlayer
sortedNext[sortCount] = sortedNext[curSort]
sortedPrevious[sortCount] = curSort
sortedNext[curSort] = sortCount
sortedPrevious[sortedNext[sortCount]] = sortCount
if curSort == sortedLast {
sortedLast = sortCount
}//if
sortCount++
}//whilenot
//now run the votes, this will give bigger votes priority
curSort = sortedNext[1]
whilenot curSort == 0 {
printf(I2S(sortedPlayer[curSort]) + " voted " + I2S(sorted[curSort]))
curSort = sortedNext[curSort]
}//whilenot
printf("Iterations: " + I2S(iterations))
}//this.code
private void Initialization() {
this.ini
this.code
}//onInit
}//PlayerVoting |
| 12-27-2009, 09:23 AM | #2 |
just copy method from wikipedia. |
| 12-27-2009, 09:54 AM | #3 |
Finished writing it ^^ edit Code:
scope PlayerVoting initializer Initialization {
//ini demo vars
private int playerOrder[12]
private int curPlayer = 0
private int iterations = 0
//ini demo vars
private int curNumber
private constant int VOTE_MAX_SIZE = 100
//sorting
private int leaves[14]
private int leafCount = 1
private int leafLeft[14]
private int leafRight[14]
private int leafParent[14]
private int leafPlayer[14]
private int curLeaf
private int curLeafRight
private int curBranch
define private <this.ini> = {
playerOrder[curPlayer++] = 6
playerOrder[curPlayer++] = 10
playerOrder[curPlayer++] = 8
playerOrder[curPlayer++] = 4
playerOrder[curPlayer++] = 1
playerOrder[curPlayer++] = 9
playerOrder[curPlayer++] = 3
playerOrder[curPlayer++] = 11
playerOrder[curPlayer++] = 7
playerOrder[curPlayer++] = 2
playerOrder[curPlayer++] = 5
playerOrder[curPlayer++] = 0
}//this.ini
void traverse(int leaf) {
int localLeaf = leaf
whilenot leafLeft[localLeaf] == 0 {
iterations++
localLeaf = leafLeft[localLeaf]
}//whilenot
whilenot localLeaf == leafParent[leaf] {
iterations++
printf(I2S(leafPlayer[localLeaf]) + " voted " + I2S(leaves[localLeaf]))
traverse(leafRight[localLeaf])
localLeaf = leafParent[localLeaf]
}//whilenot
}//leftSide
define private <this.code> = {
whilenot curPlayer == 0 {
curPlayer--
curNumber = GetRandomInt(1, VOTE_MAX_SIZE)
if leafCount != 1 {
curBranch = 1
whilenot false {
iterations++
curLeaf = curBranch
if curNumber <= leaves[curLeaf] {
curBranch = leafLeft[curLeaf]
if curBranch == 0 {
leafParent[leafCount] = curLeaf
leafLeft[curLeaf] = leafCount
exitwhen true
}//if
}//if
else {
curBranch = leafRight[curLeaf]
if curBranch == 0 {
leafParent[leafCount] = curLeaf
leafRight[curLeaf] = leafCount
exitwhen true
}//if
}//else
}//whilenot
}//else
leaves[leafCount] = curNumber
leafPlayer[leafCount] = curPlayer
leafCount++
}//whilenot
//print out entire structure
traverse(1)
printf("Iterations: " + I2S(iterations))
}//this.code
private void Initialization() {
this.ini
this.code
}//onInit
}//PlayerVotingSo the previous worst case scenario was 90 for display + setup, 78 worst on setup This one's worst case scenario is more but it's much more stable but the traverse code- Code:
void traverse(int leaf) {
int localLeaf = leaf
whilenot leafLeft[localLeaf] == 0 {
iterations++
localLeaf = leafLeft[localLeaf]
}//whilenot
whilenot localLeaf == leafParent[leaf] {
iterations++
printf(I2S(leafPlayer[localLeaf]) + " voted " + I2S(leaves[localLeaf]))
traverse(leafRight[localLeaf])
localLeaf = leafParent[localLeaf]
}//whilenot
}//leftSide#2 doesn't do function calls like this, it's all inlined, so... and here I had absolutely no choice ><. oh, and here is #1 Code:
scope PlayerVoting initializer Initialization {
//ini demo vars
private int playerOrder[12]
private int curPlayer = 0
//ini demo vars
private int curNumber
private int playerTypeVote[12][12]
private int playerTypeVoteCount[12]
define private <this.ini> = {
playerOrder[curPlayer++] = 6
playerOrder[curPlayer++] = 10
playerOrder[curPlayer++] = 8
playerOrder[curPlayer++] = 4
playerOrder[curPlayer++] = 1
playerOrder[curPlayer++] = 9
playerOrder[curPlayer++] = 3
playerOrder[curPlayer++] = 11
playerOrder[curPlayer++] = 7
playerOrder[curPlayer++] = 2
playerOrder[curPlayer++] = 5
playerOrder[curPlayer++] = 0
}//this.ini
define private <this.code> = {
whilenot curPlayer == 0 {
//demo using ini
curPlayer--
curNumber = GetRandomInt(1, 12)
//vote of type count is increased
playerTypeVote[curNumber][playerTypeVoteCount[curNumber]++] = curPlayer
//demo using ini
//actual code, one line
//playerTypeVote[theVote][playerTypeVoteCount[theVote]++] = votingPlayer
}//whilenot
//players done in reverse order to save operations
//now run the votes, this will give bigger votes priority
curNumber = 12
whilenot curNumber == 0 {
curNumber--
whilenot playerTypeVoteCount[curNumber] == 0 {
playerTypeVoteCount[curNumber]--
//just to show the vote
printf(I2S(playerTypeVote[curNumber][playerTypeVoteCount[curNumber]]) + " voted " + I2S(curNumber))
//just to show the vote
//actual code
//player
//playerTypeVote[curNumber][playerTypeVoteCount[curNumber]]
//vote
//curNumber
}//whilenot
}//whilenot
//smaller votes priority-
/*
curNumber = 0
whilenot curNumber == 12 {
whilenot playerTypeVoteCount[curNumber] == 0 {
playerTypeVoteCount[curNumber]--
printf(I2S(playerTypeVote[curNumber][playerTypeVoteCount[curNumber]]) + " voted " + I2S(curNumber))
}//whilenot
curNumber++
}//whilenot
*/
}//this.code
private void Initialization() {
this.ini
this.code
}//onInit
}//PlayerVoting#1 would be extremely good if you only had like a range of 12 or something : ). samples+(range-1) or 23 every time But what if your range was 1000? >< 999+12?? Yea, it can only deal with small ranges and would probably be good up to like 25ish ^_^. |
| 12-27-2009, 11:48 AM | #4 |
algorithm name? if you wanna sort something, use Introsort or grim's sortingUtils (or whatever) |
| 12-27-2009, 07:57 PM | #5 |
er.. I don't know what those are ^_^ But I'm moving this over to a self balancing BST I think that's the best possible way to build up a sorted data structure ^_^ I'll also be tracking bottom leaves to lower iteration count to tree size for going through the data = D edit Ok, here's what I came up with, and when I can figure out a great way to do it with minimal operations and variables I'll implement it in JASS. I haven't seen any sorted data structure or algorithm like this because it works on the fact that data is already sorted in a given set and that you are adding to it piece at a time. So, let's say we add 16. [16] Now we add 32 < 16? no > 16? yes [16] [32] Now we add 60 < 16? no > 32? yes [16] [32] [60] Now 40 < 16? no > 60? no split [16] [32] - [60] < 32? no > 32 and < 60? yes [16] [32] [40] [60] 17 < 16? no > 60? no split [16] [32] -- [40] [60] < 32? yes split [16] -- [32] < 16? no > 16 and less than 32? yes [16] [17] [32] [40] [60] And that's the general list. The only part is actually splitting it up without 0 iterations (one operation), meaning I'd need direct indexed pointers to positions in the linked list as well as sizes to determine where to split ;o. Furthermore, if the data set is less than a given value, iterating through until finding the correct spot would be better =). Also I'm concerned about the number of operations ;o. Yea, a balanced BST would be better, but... balancing it out takes quite a few operations in the worst case scenario ><. Also iterating through it in a sorted fashion requires a recursive function, =p. edit Now that I research this, I guess the actual full end data structure for the above would be a B+-Tree, haha ;p. Actually, I figured out how to do the above and it happens to match with B+ Tree model ><. It allows for extremely fast iteration through a linked list and it gives the advantage of binary tree ;o. Well, I'll figure something out but I'm slowly but surely getting to the best solution no thanks to you guys : (. |