Difference between revisions of "LlListSort"

From Second Life Wiki
Jump to: navigation, search
(added usage notes)
m (<lsl> tag to <source>)
 
(29 intermediate revisions by 11 users not shown)
Line 1: Line 1:
 
{{LSL_Function
 
{{LSL_Function
 +
|inject-2={{Issues/SVC-2988}}{{Issues/SVC-5146}}{{LSL_Function/stride|stride}}
 
|func_id=184|func_sleep=0.0|func_energy=10.0
 
|func_id=184|func_sleep=0.0|func_energy=10.0
 
|func=llListSort|return_type=list
 
|func=llListSort|return_type=list
 +
|func_complexity=O(N<sup>2</sup>)
 
|p1_type=list|p1_name=src|p1_desc=List to be sorted.
 
|p1_type=list|p1_name=src|p1_desc=List to be sorted.
|p2_type=integer|p2_name=stride|p2_desc=number of entries per stride, if less then 1 it is assumed to be 1.
+
|p2_type=integer|p2_name=stride
|p3_type=integer|p3_name=ascending|p3_desc=if {{LSLG|FALSE}} then the sort order is descending, otherwise the order is ascending.
+
|p3_type=integer|p3_name=ascending|p3_desc=if [[TRUE]] then the sort order is ascending, otherwise the order is descending.
 
|func_footnote
 
|func_footnote
|func_desc=This function supports [[List#Strided_lists|Strided Lists]].
+
|func_desc
|return_text=that is '''src''' sorted by '''stride'''.
+
|return_text=that is {{LSLP|src}} sorted by {{LSLP|stride}}.
|spec=A slow bubble sort is employed to perform the sort.<br/>
+
|spec=The sort order is affected by type. For strings and keys, it is case sensitive and sorts by Unicode character code.<br/>
The sort order is affected by type.<br/>
+
<source lang="lsl2">llListSort(["a", "á", "B", "C", "d", "e"], 1, TRUE) // returns ["B", "C", "a", "d", "e", "á"]</source>
Each type is sorted individually and then feathered to have the same order of types.
+
<lsl>llListSort([1, "C", 3, "A", 2, "B"], 1, TRUE) returns [1, "A", 2, "B", 3, "C"]
+
llListSort([1, 3, 2, "C", "A", "B"], 1, TRUE) returns [1, 2, 3, "A", "B", "C"]
+
  
llListSort([1, "C", 3, "A", 2, "B"], 2, TRUE) returns [1, "C", 2, "B", 3, "A"]</lsl>
+
For ascending sort, each type is sorted individually and then feathered to have the same order of types.
|caveats=A bubble sort is a sorting algorithm with a Big O of N*N. Why Linden Labs did not use a N*log(N) sorting algorithm such as [http://en.wikipedia.org/wiki/Heapsort Heap Sort] or [http://en.wikipedia.org/wiki/Mergesort Merge Sort] is unkown...
+
<source lang="lsl2">llListSort([1, "C", 3, "A", 2, "B"], 1, TRUE) // returns [1, "A", 2, "B", 3, "C"]
 +
 
 +
llListSort([1, 3, 2, "C", "A", "B"], 1, TRUE) // returns [1, 2, 3, "A", "B", "C"]
 +
 
 +
llListSort([1, "C", 3, "A", 2, "B"], 2, TRUE) // returns [1, "C", 2, "B", 3, "A"]
 +
 
 +
llListSort(["2ae", "ah5", "1ag", "aa6", "3ac", "ad7", "ab8", "4af", "ai9"], 1, TRUE);
 +
// returns ["1ag", "2ae" ,"3ac" ,"4af" ,"aa6" ,"ab8" ,"ad7" ,"ah5" ,"ai9"]</source>
 +
 
 +
 
 +
|caveats=*It uses an unoptimized selection sort algorithm, which is an algorithm with a Big O of N². A [[JIRA]] issue exists to improve this function, {{Jira|SVC-2988}}.
 +
* Originally the wiki stated that non-zero values for the "ascending" parameter would produce an ascending sort. That was incorrect.  For this function, the value must be exactly 1 (or TRUE) for an ascending sort.
 +
* [[Vector]]s are sorted by magnitude. {{Jira|SVC-5643}}
 +
* [[Rotation]]s are not sorted in any meaningful order. If a list containing only rotations is sorted in ascending order, it will be returned unchanged.
 +
* For descending sort, if there are mixed types, the final order is deterministic (the same input will always produce the same output) but it can be completely useless. <source lang="lsl2">llListSort([2, "B", "C", 3, 1, "A"], 1, FALSE) // returns ["A", 3, 1, "C", "B", 2]</source> If there are no mixed types, however, the descending sort works just fine.
 +
* When the stride is greater than 1, if the list length is not a multiple of the stride, the list will be returned unchanged.
 +
* When strings contain numbers, the numbers are still sorted left-to-right like any other character, which may not necessarily match numeric order: <source lang="lsl2">llListSort(["127", "3", "25"], 1, TRUE) // returns ["127", "25", "3"] because the 1 in 127 is before the 2 in 25 which is before the 3</source> To sort them in numeric order, numbers in strings can be padded with zeros: <source lang="lsl2">llListSort(["127", "003", "025"], 1, TRUE) // returns ["003", "025", "127"]</source>
 +
** This order differs from the order of items in a prim's inventory, which is "natural order" (e.g "New Script 2" is sorted before "New Script 11").
 
|constants
 
|constants
 
|examples=
 
|examples=
<lsl>
+
<source lang="lsl2">
 
list numbers = [3, "three", 2, "two", 1, "one"];
 
list numbers = [3, "three", 2, "two", 1, "one"];
 
default
 
default
Line 31: Line 47:
 
     }
 
     }
 
}
 
}
</lsl>
+
</source>
 +
 
 +
===Video Tutorial===
 +
{{KBvideo|BNIUHnpeUQs|640|385|type=youtube}}
 
|helpers
 
|helpers
|also_functions
+
|also_functions=
 +
{{LSL_DefineRow||[[llListRandomize]]|Shuffles the elements of a list.}}
 
|also_events
 
|also_events
 
|also_tests
 
|also_tests
 
|also_articles
 
|also_articles
 
|notes=
 
|notes=
'''Data Types'''
+
===Data Types===
  
 
llListSort really only works on items of the same type. It will work on lists that hold diverse data types -- to be clear, it won't blow up your script -- but the results returned are usually meaningless.
 
llListSort really only works on items of the same type. It will work on lists that hold diverse data types -- to be clear, it won't blow up your script -- but the results returned are usually meaningless.
  
<lsl>
+
<source lang="lsl2">list mylist = ["brown", <0.000000, 0.000000, 0.000000>, "house", 17.005, 100, "cat", <3.000000, 3.000000, 3.000000>, 39];
list mylist = ["brown", <0.000000, 0.000000, 0.000000>, "house", 17.005, 100, "cat", <3.000000, 3.000000, 3.000000>, 39];<br />
+
list tmplist = llListSort(mylist, 1, TRUE);
list tmplist = llListSort(mylist,1,TRUE);<br />
+
llSay(0, llList2CSV(tmplist));</source>
llSay(0, llList2CSV(tmplist));<br />
+
</lsl>
+
  
 
This returns in chat:
 
This returns in chat:
  
brown, <0.000000, 0.000000, 0.000000>, cat, 17.004999, 39, house, <3.000000, 3.000000, 3.000000>, 100
+
brown, <0.000000, 0.000000, 0.000000>, cat, 17.004999, 39, house, <3.000000, 3.000000, 3.000000>, 100
  
 +
The same ordered in descending order returns even more meaningless results:
 +
<source lang="lsl2">list mylist = ["brown", <0.000000, 0.000000, 0.000000>, "house", 17.005, 100, "cat", <3.000000, 3.000000, 3.000000>, 39];
 +
list tmplist = llListSort(mylist, 1, FALSE);
 +
llSay(0, llList2CSV(tmplist));</source>
  
 +
returns in chat:
  
 +
39, <3.000000, 3.000000, 3.000000>, cat, 100, 17.004999, house, <0.000000, 0.000000, 0.000000>, brown
  
'''Using the Results'''
+
===Utilizing the Results===
  
It's important to note that the source list that you are sorting will remain unchanged. Instead, a new, sorted list will be produced. So, it's important that you capture this with a variable (unless you are acting directly on the results.
+
It's important to note that the source list that you are sorting will remain unchanged. Instead, a new, sorted list will be produced. So, it's important that you capture this with a variable (unless you are acting directly on the results.)
  
<lsl>
+
<source lang="lsl2">llListSort(myList, 1, TRUE); // You've wasted cpu time; you didn't capture the results
llSortList(myList,1,TRUE); // you've sorted for nothing; you didn't capture the results<br />
+
list newlist = llSortList(myList,1,TRUE);//okay. You've captured the results.<br />
+
llSay(0,list2CSV(llSortList(myList,1,TRUE))); //no need to capture, using the results right away.
+
</lsl>
+
  
 +
list newlist = llListSort(myList, 1, TRUE);// Okay. You've captured the results.
  
'''"Stride" parameter'''
+
llSay(0,llList2CSV(llListSort(myList, 1, TRUE))); // No need to capture, using the results right away.</source>
 +
 
 +
==={{LSLPT|Stride}} parameter===
  
 
Most times, you will want to set "integer stride" to 1 (0 also works) to tell it to sort each item in the list on its own basis. (If you are working with a strided list, though, see the special section below on sorting strides.)
 
Most times, you will want to set "integer stride" to 1 (0 also works) to tell it to sort each item in the list on its own basis. (If you are working with a strided list, though, see the special section below on sorting strides.)
  
 +
===Sort Order===
  
'''Sort Order'''
+
Setting the parameter "integer ascending" to [[TRUE]] returns a sorted list that is in ascending order. <br/>
 +
For example: ["Apples", "Bananas", "Oranges"]
  
Setting the parameter "integer ascending" to TRUE gives you back a sort that is in ascending order. E.g.:
+
Setting the parameter "integer ascending" to [[FALSE]] returns a sorted list that is in descending order. <br/>
 +
For example: ["Oranges", "Bananas", "Apples"]
  
Apples<br />
+
===Sorting Strided Lists===
Bananas<br />
+
Citrus<br />
+
 
+
 
+
Setting the parameter "integer ascending" to FALSE gives you back a sort that is in descending order. E.g.:
+
 
+
Citrus<br />
+
Bananas<br />
+
Apples<br />
+
 
+
 
+
'''Sorting Strided Lists'''
+
  
 
If you have a [[List#Strided_lists|strided list]], in which you are keeping related pieces of data together in chunks, letting each list element sort on its own basis would be disastrous.
 
If you have a [[List#Strided_lists|strided list]], in which you are keeping related pieces of data together in chunks, letting each list element sort on its own basis would be disastrous.
  
Sample List:
+
<source lang="lsl2">list demographics = ["John Adams", "male", "2007-06-22", "Shirley Bassey", "female", "2005-11-02", "Matt Damon", "male", "2008-05-19"];</source>
  
list demographics = ["John Adams", "male", "2007-06-22", "Shirley Bassey", "female", "2005-11-02", "Matt Damon", "male", "2008-05-19"];<br />
+
====Bad Example====
  
Example 1:
+
<source lang="lsl2">list tmplist_1 = llListSort(demographics, 1, TRUE);
 +
//tmplist_1 == ["2005-11-02", "2007-06-22", "2008-05-19", "John Adams", "Matt Damon", "Shirley Bassey", "female", "male", "male"]
 +
//The strides have been destroyed, the sorted data is now useless</source>
  
list tmplist = llListSort(demographics,01,TRUE);<br />
+
====Good Example====
llSay(0, llList2CSV(tmplist));<br />
+
 
+
This gives you:
+
 
+
2005-11-02, 2007-06-22, 2008-05-19, John Adams, Matt Damon, Shirley Bassey, female, male, male
+
 
+
Which destroys your data collection.
+
 
+
 
+
Example 2:
+
  
 
Instead, because you have the data grouped (aka "strided") in sets of 3, you need to do this:
 
Instead, because you have the data grouped (aka "strided") in sets of 3, you need to do this:
  
list tmplist = llListSort(demographics,3,TRUE);<br />
+
<source lang="lsl2">list tmplist_2 = llListSort(demographics, 3, TRUE);
llSay(0, llList2CSV(tmplist));<br />
+
//templist_2 = ["John Adams", "male", "2007-06-22", "Matt Damon", "male", "2008-05-19", "Shirley Bassey", "female", "2005-11-02"]
 
+
</source>
This gives us the correct sort.
+
 
+
John Adams, male, 2007-06-22, Matt Damon, male, 2008-05-19, Shirley Bassey, female, 2005-11-02
+
 
+
  
 
When storing data in strided lists, it's often worth it down the road to take a moment at the outset to think about how you are most likely to want to sort them, if ever the need arose. Remember, you can only sort on the first element in each group of elements. If you think you're mostly likely to want to sort on gender (to use the above list example), you should make gender the first element in the data grouping.
 
When storing data in strided lists, it's often worth it down the road to take a moment at the outset to think about how you are most likely to want to sort them, if ever the need arose. Remember, you can only sort on the first element in each group of elements. If you think you're mostly likely to want to sort on gender (to use the above list example), you should make gender the first element in the data grouping.
 
  
 
|permission
 
|permission
Line 129: Line 130:
 
|cat3
 
|cat3
 
|cat4
 
|cat4
|location=lsa_bubble_sort(): 'linden\indra\lscript\lscript_alloc.h'
+
|location
 +
|issues=
 
}}
 
}}

Latest revision as of 11:17, 22 January 2015

Summary

Function: list llListSort( list src, integer stride, integer ascending );
184 Function ID
0.0 Forced Delay
O(N2) Compl.
10.0 Energy

Returns a list that is src sorted by stride.

• list src List to be sorted.
• integer stride number of entries per stride, if less than 1 it is assumed to be 1
• integer ascending if TRUE then the sort order is ascending, otherwise the order is descending.

This function supports Strided Lists.

Specification

The sort order is affected by type. For strings and keys, it is case sensitive and sorts by Unicode character code.

llListSort(["a", "á", "B", "C", "d", "e"], 1, TRUE) // returns ["B", "C", "a", "d", "e", "á"]

For ascending sort, each type is sorted individually and then feathered to have the same order of types.

llListSort([1, "C", 3, "A", 2, "B"], 1, TRUE) // returns [1, "A", 2, "B", 3, "C"]
 
llListSort([1, 3, 2, "C", "A", "B"], 1, TRUE) // returns [1, 2, 3, "A", "B", "C"]
 
llListSort([1, "C", 3, "A", 2, "B"], 2, TRUE) // returns [1, "C", 2, "B", 3, "A"]
 
llListSort(["2ae", "ah5", "1ag", "aa6", "3ac", "ad7", "ab8", "4af", "ai9"], 1, TRUE);
// returns ["1ag", "2ae" ,"3ac" ,"4af" ,"aa6" ,"ab8" ,"ad7" ,"ah5" ,"ai9"]

Caveats

  • It uses an unoptimized selection sort algorithm, which is an algorithm with a Big O of N². A JIRA issue exists to improve this function, SVC-2988.
  • Originally the wiki stated that non-zero values for the "ascending" parameter would produce an ascending sort. That was incorrect. For this function, the value must be exactly 1 (or TRUE) for an ascending sort.
  • Vectors are sorted by magnitude. SVC-5643
  • Rotations are not sorted in any meaningful order. If a list containing only rotations is sorted in ascending order, it will be returned unchanged.
  • For descending sort, if there are mixed types, the final order is deterministic (the same input will always produce the same output) but it can be completely useless.
    llListSort([2, "B", "C", 3, 1, "A"], 1, FALSE) // returns ["A", 3, 1, "C", "B", 2]
    If there are no mixed types, however, the descending sort works just fine.
  • When the stride is greater than 1, if the list length is not a multiple of the stride, the list will be returned unchanged.
  • When strings contain numbers, the numbers are still sorted left-to-right like any other character, which may not necessarily match numeric order:
    llListSort(["127", "3", "25"], 1, TRUE) // returns ["127", "25", "3"] because the 1 in 127 is before the 2 in 25 which is before the 3
    To sort them in numeric order, numbers in strings can be padded with zeros:
    llListSort(["127", "003", "025"], 1, TRUE) // returns ["003", "025", "127"]
    • This order differs from the order of items in a prim's inventory, which is "natural order" (e.g "New Script 2" is sorted before "New Script 11").
All Issues ~ Search JIRA for related Bugs

Examples

list numbers = [3, "three", 2, "two", 1, "one"];
default
{
    state_entry()
    {
        llOwnerSay(llDumpList2String(numbers, ","));
        // Object: 3,three,2,two,1,one
        numbers = llListSort(numbers, 2, TRUE);
        llOwnerSay(llDumpList2String(numbers, ","));
        // Object: 1,one,2,two,3,three
    }
}

Video Tutorial

Notes

Data Types

llListSort really only works on items of the same type. It will work on lists that hold diverse data types -- to be clear, it won't blow up your script -- but the results returned are usually meaningless.

list mylist = ["brown", <0.000000, 0.000000, 0.000000>, "house", 17.005, 100, "cat", <3.000000, 3.000000, 3.000000>, 39];
list tmplist = llListSort(mylist, 1, TRUE);
llSay(0, llList2CSV(tmplist));

This returns in chat:

brown, <0.000000, 0.000000, 0.000000>, cat, 17.004999, 39, house, <3.000000, 3.000000, 3.000000>, 100

The same ordered in descending order returns even more meaningless results:

list mylist = ["brown", <0.000000, 0.000000, 0.000000>, "house", 17.005, 100, "cat", <3.000000, 3.000000, 3.000000>, 39];
list tmplist = llListSort(mylist, 1, FALSE);
llSay(0, llList2CSV(tmplist));

returns in chat:

39, <3.000000, 3.000000, 3.000000>, cat, 100, 17.004999, house, <0.000000, 0.000000, 0.000000>, brown

Utilizing the Results

It's important to note that the source list that you are sorting will remain unchanged. Instead, a new, sorted list will be produced. So, it's important that you capture this with a variable (unless you are acting directly on the results.)

llListSort(myList, 1, TRUE); // You've wasted cpu time; you didn't capture the results
 
list newlist = llListSort(myList, 1, TRUE);// Okay. You've captured the results.
 
llSay(0,llList2CSV(llListSort(myList, 1, TRUE))); // No need to capture, using the results right away.

Stride parameter

Most times, you will want to set "integer stride" to 1 (0 also works) to tell it to sort each item in the list on its own basis. (If you are working with a strided list, though, see the special section below on sorting strides.)

Sort Order

Setting the parameter "integer ascending" to TRUE returns a sorted list that is in ascending order.
For example: ["Apples", "Bananas", "Oranges"]

Setting the parameter "integer ascending" to FALSE returns a sorted list that is in descending order.
For example: ["Oranges", "Bananas", "Apples"]

Sorting Strided Lists

If you have a strided list, in which you are keeping related pieces of data together in chunks, letting each list element sort on its own basis would be disastrous.

list demographics = ["John Adams", "male", "2007-06-22", "Shirley Bassey", "female", "2005-11-02", "Matt Damon", "male", "2008-05-19"];

Bad Example

list tmplist_1 = llListSort(demographics, 1, TRUE);
//tmplist_1 == ["2005-11-02", "2007-06-22", "2008-05-19", "John Adams", "Matt Damon", "Shirley Bassey", "female", "male", "male"]
//The strides have been destroyed, the sorted data is now useless

Good Example

Instead, because you have the data grouped (aka "strided") in sets of 3, you need to do this:

list tmplist_2 = llListSort(demographics, 3, TRUE);
//templist_2 = ["John Adams", "male", "2007-06-22", "Matt Damon", "male", "2008-05-19", "Shirley Bassey", "female", "2005-11-02"]

When storing data in strided lists, it's often worth it down the road to take a moment at the outset to think about how you are most likely to want to sort them, if ever the need arose. Remember, you can only sort on the first element in each group of elements. If you think you're mostly likely to want to sort on gender (to use the above list example), you should make gender the first element in the data grouping.

See Also

Functions

•  llListRandomize Shuffles the elements of a list.

Deep Notes

All Issues

~ Search JIRA for related Issues
   Convert llListSort() to use faster sorting methods!
   llSortedListFindList() - improved llListFindList() for known to be sorted lists

Signature

function list llListSort( list src, integer stride, integer ascending );