Jump to content

A footnote to sorting parallel lists


PeterCanessa Oh
 Share

You are about to reply to a thread that has been inactive for 4040 days.

Please take a moment to consider if this thread is worth bumping.

Recommended Posts

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.

Link to comment
Share on other sites

You are about to reply to a thread that has been inactive for 4040 days.

Please take a moment to consider if this thread is worth bumping.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...