A footnote to sorting parallel lists

[PeterCanessa Oh]

The routines I gave in the library for indexing and sorting parallel lists are probably as quick as they can get since they hardly do anything (!), but with all those copies of lists flying around they do need a sizeable chunk of memory.  If you're using a number of parallel lists for data, the chances are that memory is going to be in short supply, so that's a problem.

This in-place indexing routine requires about 6k for a 100-integer list and runs in approx 1.2s

 

list IndexCreateInPlace(list MasterList, integer Ascending){
    // Returns a list of original indices in sorted order
    integer Element = llGetListLength(MasterList);
    MasterList = (MasterList = []) + MasterList + [--Element];
    while(Element--)
        MasterList = llListInsertList((MasterList = []) + MasterList, [Element], (Element + 1));
    return llList2ListStrided(llDeleteSubList(llListSort((MasterList = []) + MasterList, 2, Ascending), 0, 0), 0, -1, 2);
}

 

In contrast this more-or-less-optimised version that creates a new list requires 12k and runs in approx 0.3s, so twice the memory for 4 times the speed.  Your call on whether time or memory are more important in your application.

 

list IndexCreate(list MasterList, integer Ascending){
    // Returns a list of original indices in sorted order
    integer Element = llGetListLength(MasterList);
    list SortList;
    while(Element--)
        SortList = (SortList = []) + llList2List(MasterList, Element, Element) + [Element] + SortList;
    SortList = llListSort((SortList = []) + SortList, 2, Ascending);
    return llList2ListStrided(llDeleteSubList(SortList, 0, 0), 0, -1, 2);
}

 

With the actual sorting I had much less success.  The routine that creates a new list takes approx 0.3s (again) and 2.7k

 

list IndexSort(list ParallelList, list IndexList){
    // Returns a sorted list using pre-sorted indices
    integer Element = llGetListLength(ParallelList);
    integer From;
    list SortList;
    while(Element--){
        From = llList2Integer(IndexList, Element);
        SortList = (SortList = []) + llList2List(ParallelList, From, From) + SortList;
    }
    return SortList;    
}

 And here I thought I'd definitely be able to make memory improvements by soritng in-place.  Unfortunately this routine is 6 times slower and requires more memory (6.5k), not less :-(

 

list IndexSortInPlace(list ParallelList, list IndexList){
    // Returns a sorted list using pre-sorted indices
    integer Counter = llGetListLength(ParallelList);
    integer Current;
    integer ShouldBe;
    list Temp;
    while(Counter--){
        Current = Counter;
        ShouldBe = llList2Integer(IndexList, Current);
        if(ShouldBe!= Current){
	        Temp = llList2List(ParallelList, Current, Current);
	        do{
	            IndexList = llListReplaceList(IndexList, [Current], Current, Current);
	            if(ShouldBe == Counter){
	                ParallelList = llListReplaceList((ParallelList = []) + ParallelList, Temp, Current, Current);
	            }else{
	                ParallelList = llListReplaceList(ParallelList, llList2List((ParallelList = []) + ParallelList, ShouldBe, ShouldBe), Current, Current);
	            }
	            Current = ShouldBe;
	            ShouldBe = llList2Integer(IndexList, Current);
	        }while(ShouldBe != Current);
        }
    }
    return ParallelList;
}

 Pity - I had high hopes for that one :-(

While this post is mainly for information, I'd welcome any further optimisation anyone has to offer.

[Void Singer]

well there's one obvious optimization to be had... or course it breaks the generality of the functions.... don't send the lists inside of the function call....

[PeterCanessa Oh]

:-) Since the functions are so short I hope that people will have no trouble in-lining them if appropriate. Do you think I should give an example?

[Void Singer]

could be helpful ::shrug::