Talk:LlListSort

Bubble Sort?

This script: <lsl> default {

   state_entry()
   {
       llOwnerSay(llList2CSV(llListSort([3,2,3,5,3,1,1,4], 2, TRUE)));
   }

} </lsl>

outputs

1, 4, 3, 5, 3, 1, 3, 2

both in LSO and in Mono. This means that the sort is not stable. Since stability is a characteristic of Bubble Sort, it looks like the claim of using Bubble Sort is not correct. --Pedro Oval 20:01, 5 April 2014 (PDT)

Good point. -- Strife ^{(talk|contribs)} 21:26, 5 April 2014 (PDT)

maybe... needs an extended example to see if LSL backwards ordering isn't the culprit
-- Void ^{(talk|contribs)} 22:19, 5 April 2014 (PDT)

If it's in reverse order, it's not stable either. The reverse would be 3,1,3,5,3,2 but the actual result is 3,5,3,1,3,2 --Pedro Oval 12:39, 6 April 2014 (PDT)

doh, you're right... comb sort perhaps? looking at the ordering exchange seems more likely than insertion
-- Void ^{(talk|contribs)} 17:20, 6 April 2014 (PDT)

Best option could be to pose this question on the scripting mail list, Kelly appears to prefer that channel for tech information dumps. The bubble sort presumption probably came from a function included with the viewer part of the source, but its comments describe list syntax and functions that never made it to LSL2. --ObviousAltIsObvious Resident 17:30, 6 April 2014 (PDT)

I think it was a semantic problem, the existing list functions don't leave any room for embedded lists. When they couldn't get pass-by-reference to work properly (assumption), they likely killed embedded lists because it didn't fit well in 16KiB.

Q: Why does the viewer source contain code that is obviously server LSL VM source code?

A: A bit of history, before the age of Mono, scripts were compiled by the client, and the viewer source included a copy of much of the server VM code. You have to remember that the viewer wasn't always open source, it's likely that the client and server code once existed in a single repository, that would be recompiled at the same time. When LL opensourced the viewer, they split the repository, but because of interdependence between the server and client code, some files were duplicated between the two repositories. LSL related files overtime diverged, largely driven by Mono's server side compilation. So while it may seem strange now that the viewer contains server source, it wasn't at the time the article was written.

-- Strife ^{(talk|contribs)} 19:08, 6 April 2014 (PDT)

It's probably not very polite to bring up this link, but it may shed some light on the reasons behind usage of Bubble Sort and the presumption that it was used in the server code: [1]. It mentions what it calls "type specific feathered sorting", which I assume it to mean the individual sorting of elements of each type. The code claims that "unoptimized bubble sort" is the only way to achieve it. I haven't given it much thought yet, but I wonder if comb sort, as mentioned by Void, would also preserve that ordering. --Pedro Oval 03:09, 8 April 2014 (PDT)

I think that 3 passes index, sort, write could do this as well. Miranda's comment in SVC-2988 suggests that there is some other kind of overhead in there. --ObviousAltIsObvious Resident 05:31, 8 April 2014 (PDT)

I've tried Quicksort and Comb Sort. My input list was [3,2,1,3,3,4,3,3,1,4,1,9,3,6] with stride 2. llListSort returns [1,3,1,4,1,9,3,3,3,2,3,4,3,6]. I could not reproduce this result with Comb sort, not even pre-inverting the array nor by pre-inverting, sorting descending and post-inverting it. I've tried two variations and all possible shrink values for this length. I've also tried with Quicksort with a decent amount of possible choices of pivot (first, central, last, median, and sorting the first, central and last elements, using several variations of < and <= for median and sorting), to no avail. --Pedro Oval 07:01, 8 April 2014 (PDT)

I wish I had more time to play with this. Going by what is typically found in LL code, my first guess would be "whatever the GNU library is using in std::sort". It could very well be a wrapper around that. Adding to fun, there are 2 major C++ libraries in GNU land, each uses a different approach. --ObviousAltIsObvious Resident 07:30, 8 April 2014 (PDT)

Boost? P.S. I've looked at opensim code. I have no problem with us documenting opensim functions etc. -- Strife ^{(talk|contribs)} 08:58, 8 April 2014 (PDT)

Same difference, as Boost uses std::sort: [2]. Digging a bit I have found this: Introsort#Implementations (Wikipedia) which made it sound like any attempt at reproducing the results without GNU libstdc++ was going to be too painful to be worth it. Then I've tried with the C++11 program below; it was sorted in a stable way, as the result is: "1,3, 1,4, 1,9, 3,2, 3,4, 3,3, 3,6, ". I'm willing to make more experiments but I'm out of ideas at the moment. Any suggestions? (P.S.: who chose the colors for the C++ highlighter? Yuck!) --Pedro Oval 09:30, 9 April 2014 (PDT)

<cpp>

1. include <iostream>
2. include <algorithm>
3. include <vector>

struct Rec {

   int key;
   int data;

};

bool sortByKey(const Rec &lhs, const Rec &rhs) { return lhs.key < rhs.key; }

int main() {

   std::vector<Rec> v = {{3,2},{1,3},{3,4},{3,3},{1,4},{1,9},{3,6}};
   std::sort(v.begin(), v.end(), sortByKey);
   for (Rec &n : v)
       std::cout << n.key << "," << n.data << ", ";
   std::cout << std::endl;
   return 0;

} </cpp>

tried substituting partial_sort (I think that bypasses the insertion sort libstdc++ likes to use on small sets), almost the same as LSL but not close enough. 1,4, 1,3, 1,9, 3,3, 3,2, 3,4, 3,6, --ObviousAltIsObvious Resident 15:34, 9 April 2014 (PDT)

I don t know why you are using boost c++ library . Probably the key of the answer is inside the implementation of sort in the mono library .

I dont know which version mono is , and which algorithm it uses for sort . Nevertheless , the documentation from microsoft on dotnet c# gives :

from [ http://msdn.microsoft.com/en-us/library/b0zbh7b6(v=vs.110).aspx ]

This method uses the Array.Sort method, which applies the introspective sort as follows:
* If the partition size is fewer than 16 elements, it uses an insertion sort algorithm.
* If the number of partitions exceeds 2 * LogN, where N is the range of the input array, it uses a Heapsort algorithm.
* Otherwise, it uses a Quicksort algorithm.
This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. 
In contrast, a stable sort   preserves the order of elements that are equal.
On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n ^ 2) operation.

We should verify if the actual version of mono used by linden uses the same strategy as microsoft. But , at first view , it seems coherent with the actual observations

<cpp> using System; using System.Collections.Generic;

class Program {

   public  static int compareStridedList(List<int> first , List<int> second)
   {
       if ( first[0] <= second[0] )
       return -1;
       else
       return 1;   
       
   }    
   static void Main()
   {
       //1, 4, 3, 5, 3, 1, 3, 2
       List<List<int>> list = new List<List<int>>();
   	list.Add(new List<int>(new int[] { 1, 4}));
       list.Add(new List<int>(new int[] { 3, 5}));
       list.Add(new List<int>(new int[] { 3, 1}));
       list.Add(new List<int>(new int[] { 3, 2}));
   

       Console.WriteLine("Display original list");
   	foreach (var element in list)
   	{
   	    Console.WriteLine("{0} {1}", element[0], element[1]);
   	}
       list.Sort( compareStridedList );
       Console.WriteLine("Display sorted list");    
       foreach (var element in list)
   	{
   	    Console.WriteLine("{0} {1}", element[0], element[1]);
   	}        
   }

} </cpp>

outputs on [ http://www.compileonline.com/compile_csharp_online.php ] with Mono 2.10.2.0

Display original list
1 4
3 5
3 1
3 2
Display sorted list
1 4
3 5
3 1
3 2

With a compare function <cpp>

       if ( first[0] < second[0] )
       return -1;
       else
       return 1;   

</cpp> it outputs

Display sorted list
1 4
3 2
3 1
3 5

Other note : a bubble sort is O(n) if the list is already sorted . Some other algorithms too. And some other algorithms , not. But in LSL/mono , sortig an already sorted list don t make it faster

Miranda Umino 20:55, 17 April 2014 (PDT)