PDA

View Full Version : sort vectors


fbitonti
05-10-2006, 04:37 AM
I am storing particle positions in a series of vectors I am then calculating the angle between an origin {0,0,0} point. I want to use the angle to sort the vectors in ascending order. Iím not sure how to structure the script. I know mel has a sort command but if I do this it will sort the vectors and the vectors can only store three values as far as I know. Any information would be a huge help. Iím kind of stuck on this.

scottiedoo
05-10-2006, 05:22 AM
I got some great help a couple days ago on a sorting problem:
http://forums.cgsociety.org/showthread.php?t=354157

Just an idea, not sure if its fool proof but if you wanted to sort them by the first vector (x):

vector $v1 = <<4,1,-3>>;
vector $v2 = <<-1,0,-4>>;
vector $v3 = << 1,3,0>>;
string $vectorList[] = {($v1.x + " " + $v1.y + " " + $v1.z),($v2.x + " " + $v2.y + " " + $v2.z), ($v3.x + " " + $v3.y + " " + $v3.z)};

string $sortedVectorList[] = sort($vectorList);
string $buffer[];
for($vector in $sortedVectorList){
tokenize $vector " " $buffer;
float $vectBuffer[];
for($i=0;$i<size($buffer);$i++){
$vectBuffer[$i] = $buffer[$i];
}
vector $newVector = <<$vectBuffer[0],$vectBuffer[1],$vectBuffer[2]>>;
print ($newVector + "\n");
};


I hope that helps, if that is what you are looking to do
-Scott

fbitonti
05-10-2006, 04:05 PM
Thanks for the input that was a big help but my problem is also that I need a way to sort with a forth value that is not in the vectors. for example the angel between the point and a zero axis then attaching that value and sorting in the order of that new value then droping the value from the variable. so in the end I have a list of points orded by some external variable which has been attached to each vector. Once again thank you for your help. That cleared up a lot.

tciny
05-11-2006, 04:01 PM
I'd say: iterate over your array of vectors and build a new array containing the angle for that item. Then just bubble sort the angle list and make all changes to the vector array as well.
If you have trouble getting that to work just post here again :)

If you haven't used bubble sort before, this should help: http://en.wikipedia.org/wiki/Bubblesort

GennadiyKorol
05-11-2006, 04:32 PM
Considering bubble sort having O(n^2) complexity it's a good practice to avoid it as much as you can:) I'd suggest looking into quick sort algorithm ( O(n logn) complexity).

Robert Bateman
05-11-2006, 05:19 PM
Considering bubble sort having O(n^2) complexity it's a good practice to avoid it as much as you can:) I'd suggest looking into quick sort algorithm ( O(n logn) complexity).

depth sorting polygons is quicker using a bubble sort than a quick sort. Big O notation does not give an accurate indication of how a sort will perform in the real world, it only indicates how the sort will perform on entirely random data.

In the case of sorting particle positions, assuming that the statement "between frames it wont change too much" holds true, a bubble sort will probably outperform a quicksort. (so long as you are not creating the array from scratch each frame).

I would add though, that any mel script sorting algorithm will be slower than the native sort function....

GennadiyKorol
05-11-2006, 05:30 PM
True, but not for a randomised version of quick sort. When data is almost sorted the usual quick sort hits it's worst case (O(n^2)). The randomised quick sort however does not and it's also easier for implementation. So I guess quick sort is a way to go, since radix sort could not be implemented efficiently with mel.

Cheers :)

tciny
05-11-2006, 06:42 PM
I actually said bubble sort because its just the easiest algorithm out there to do sorting. Looking at fbitonti's post it doesnt seem like he studied computer science, so I guess learning how to implement quicksort just seems like a little much to ask...

I personally prefer a multiply and surrender approach to sorting such as slowsort. But that's just personal preference...

GennadiyKorol
05-11-2006, 06:46 PM
Yeah, though there are a lot of already implemented algorithms out there, and quick sort itself is not that complicated :)

BTW, never heard of slow sort, sorry for off-topic but could you tell more about this method? Thanks :)

tciny
05-12-2006, 05:14 PM
Slowsort is a recursive sorting algorithm. It's been described in Broder/Stolfi 1986 "Pessimal Algorithms and Simplexity Analysis".
The best case runtime is: O(n^log(n)/(2+e))

Theres more on the german wikipedia article, you might be able to translate it using bablefish or googles language tools: http://de.wikipedia.org/wiki/Slowsort
enjoy ;)

nessus
05-12-2006, 08:18 PM
those sorting algrithms!! it reminds me my old college days!!

GennadiyKorol
05-12-2006, 10:43 PM
tciny: Hmm, according to the complexity it looks like it's indeed a slow sort :) Sorting 16 000 numbers would take O(n^3)?.. Any particular reason for using this one?

Thanks again.

tciny
05-13-2006, 09:30 AM
I was just kidding actually ;)

fbitonti
05-15-2006, 03:20 AM
thanks every one has been a huge help. I do have one last stupid question.

Can any one tell me how to call up the number of objects in a string.

for example in this case i want to use that number to run a loop.


This is the example:::::::



string $obj1[] = `ls -sl -fl`;

$number_of_obj_in_String = "the number of objects in the sting"

for ($a = 0; $a < $number_of_obj_in_String; $i++) {
print $obj1[$a];
}

scottiedoo
05-15-2006, 03:44 AM
you would want to use the "size" command

and you made a little typo with the end of the for loop, its should be and "a" not an "i" i correceted it below:

for ($a = 0; $a < size($obj1); $a++) {
print $obj1[$a];
}

tciny
05-15-2006, 12:09 PM
On a side note, I think writing the size to a variable before looping would actually be faster.
int $tehSize = size($obj1);
for ($a = 0; $a < $tehSize; $a++) {
print $obj1[$a];
}

Robert Bateman
05-15-2006, 12:19 PM
In this case it'd make next to no difference.

fbitonti
05-15-2006, 05:29 PM
I just want to begin by saying that I realy appreciate this help learning how to do this. This is the first time i've worked with strings like this.

my problem is this:::

I started working with the actual particles. The script should allow you to select a group of individual particles and return the xyz coordinates of each selected particle however, no mater which particles i select it spits out the same value and only for every third particle int he selection. This is the script if some one can point out what i'm doing wrong it would be a huge help.

//contains particle names
string $obj1[] = `ls -sl -fl`;
//contains particle positions
string $partset[];

for ($a = 0; $a < size($obj1); $a++) {
print $obj1[$a];

float $partposxyz[];
$partposxyz = `getParticleAttr -at worldPosition ($obj1[$a])`;
$partposx = $partposxyz[0];
$partposy = $partposxyz[1];
$partposz = $partposxyz[2];

string $appendset[3] = {$partposx +" "+ $partposy +" "+ $partposz};
appendStringArray($partset, $appendset, 3);
print $partset[$a];
print "\n";

}

once again thank you for your help.

tciny
05-15-2006, 06:13 PM
string $obj1[] = `ls -sl -fl`;
float $partposxyz[];
for ($a = 0; $a < size($obj1); $a++)
{
$partposxyz = `getParticleAttr -at worldPosition ($obj1[$a])`;
print ( $obj1[$a] + " Pos: " + $partposxyz[0] + " " + $partposxyz[1] + " " + $partposxyz[2] + "\n");
}
should work and would be shorter.

Theres a couple of bugs there. For one:
string $appendset[3] = {$partposx +" "+ $partposy +" "+ $partposz};
will create just one array element. The second and third indices will be left blank. You'd have to seperate them with commas for the correct assignment.

Then you keep appending to partset over and over without clearing it. Because the array above it has two empty spots the contet of partset will be:
data empty empty data empty empty etc.
So when you access it using $a, you'll hit the empty slots... you'd have to correct the assignment and the print out the indices $a*3+0, $a*3+1 and $a*3+2

Hope that helps. Below is your code corrected:
//contains particle names
string $obj1[] = `ls -sl -fl`;
//contains particle positions
string $partset[];

for ($a = 0; $a < size($obj1); $a++) {
print $obj1[$a];

float $partposxyz[];
$partposxyz = `getParticleAttr -at worldPosition ($obj1[$a])`;
string $partposx = $partposxyz[0];
string $partposy = $partposxyz[1];
string $partposz = $partposxyz[2];

string $appendset[3];
$appendset = {$partposx, $partposy, $partposz};

appendStringArray($partset, $appendset, 3);
print $partset[$a*3+0];
print $partset[$a*3+1];
print $partset[$a*3+2];
print "\n";

}


And Robert Bateman was right :) I just benchmarked it and it's 10 percent speed difference between the two at max... dang! ;)

GennadiyKorol
05-16-2006, 09:02 PM
Interesting question, here's my bench:) :

int $i = 0;
string $dummy;

string $longArray[];

for ($i = 0; $i < 1000000; $i++)
$longArray[$i] = "Bob";


float $totalTime1 = 0, $totalTime2 = 0;
int $k;
for ($k = 0; $k < 10; $k++)
{
int $size = `size $longArray`;
$startTime = `timerX`;

for ($i = 0; $i < $size; $i++)
{
$dummy = $longArray[$i];
}

$totalTime = `timerX -startTime $startTime`;
$totalTime1 += $totalTime;


$startTime = `timerX`;

for ($i = 0; $i < `size $longArray`; $i++)
{
$dummy = $longArray[$i];
}

$totalTime = `timerX -startTime $startTime`;
$totalTime2 += $totalTime;
}
print ("\nAverage time in case 1: "+$totalTime1/10+"\n");
print ("\nAverage time in case 2: "+$totalTime2/10+"\n");
print ("\nThe case 2 is by " +(-100+100*$totalTime2/$totalTime1)+ " percents slower than case 1");

The script creates a longArray of one million length. Then it iterates through it in two ways, one with defined size variable, second with `size longArray` inside for loop each time measuring the time taken.
This is performed 10 times and averaged to get rid of possible random incorrectnesses.
Better perform this on clean opened maya for more correct results.

Here's what I've got (case 1 with variable outside loop, case 2 with `size` inside loop):

Average time in case 1: 0.869

Average time in case 2: 0.887

The case 2 is by 2.071346375 percents slower than case 1


Not sure about 10%, about 2% on one million array, so I guess it's close to "has no effect" :)
Though if you put `size` command inside the body of the for loop, you will get much slower performance, that means that MEL does some optimization with constant expressions in for loop condition statement.

CGTalk Moderation
05-16-2006, 09:02 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.