A Little List Advice

I'm making something that registers names into a list, many will be and should be duplicate.

What I need to do is find out how many of each name is in the list.

Say in list we have:

"apple", "apple", "orange", "orange", "orange", "orange", "orange", "orange", "orange", "orange";

What's the most efficent way to find how many times orange appears in the list? it will be a dynamic but not static value.

I think stepping through it would avoid making extra copies of the list, which would be expensive:

int i = llListFindList(i, "orange"; // find first

if (i == -1) return 0;

int n = llGetListLength(l);
int c = 1;

while(++i < n) // preincrement, so we step over first match and step through to end
if(llList2String(l, i) == "orange" c++;

return c;

If memory isn't your main concern, sort the list, then find do a search for the first implementation of orange, then step through the list until you find that it isn't orange anymore, but Agent's way is most likely your best route in what you want.

This sounds faster to me...

llListSort is a bubble sort.

My suggestion is O(N), llListSort is O(n*n).

Why not set up a strided list and simply increment the count, each time you add an identical name? So, from your example, you would have:

list fruits = ["apple", 2, "orange", 7];

function add(string item){
integer idx = llListFindList[fruits,[item]) + 1;
if(idx < 1){
fruits = (fruits = []) + fruits + [item, 1];
}else{
integer cnt = llList2Integer(fruits,idx) + 1;
fruits = llListReplaceList(fruits, [cnt], idx, idx);
}
}

integer function getCount(string item){
integer idx = llListFindList[fruits,[item]) + 1;
if(idx > 0){
return llList2Integer(fruits,idx);
}
return -1;
}

To add an "apple" you could then simply call add("apple";

And, to get your item count, you simply call getCount("apple";

An impl such as the above, trumps unnecessary resource intensive looping and reduces memory reqs. In other words, you've just reduced your list memory from 42 bytes to 13 bytes. And, if you add more apples and oranges, you're still only looking at 13 bytes. If you add a "banana" or whatever, the list memory will increase by the number of characters pls, one byte, at the very least.

or you could parse the list to a string, with a separator, parse it back to a list removing both the separators and the specific item, then count the difference.

You sure it's a bubble sort? Wouldn't surprise me if it was, but a pivot sort isn't that hard to implement for any programmer. There is a big difference between O(nlog n) vs O(n^2), but then again, in SL you aren't dealing with that big of lists to make huge differences.

That's what the wiki claims.

I thought mono lists were ArrayList objects.. Google says:

The semantics of LSL sorting are a little odd, particularly when lists contain elements of different types, and I suspect that they aren't using a standard sort operator.

It's a dynamtic list I wont know any values to start with.

if you are building the list yourself (programatically) you can though. this is what Anna's suggestion looks like in a non strided version.

list gLstItems;
list gLstCount;

//-- when you recevie a new item to add
integer vIdxLst = llListFindList( gLstItems, (list)vStrAdd );
if (~vIdxLst){
 gLstCount = llListReplaceList( gLstCount, llList2Integer( gLstCount, vIdxLst ) + 1, vIdxLst, vIdxLst );
else{
  gLstItems += (list)vStrAdd;
  gLstCount += (list)1;
}

then all you have to do to get a count of each unique item is check the same index in the count list. not using strides makes it easier to search a specific item, but using strides will allow you to sort on the count. but you can get the greatest and least counts by using llListStatistics to get the min or max in the count list, and then search for them to get the index (although this will only return the first one for items with the same count)

if the list is coming for an outside source that isn't read in one at a time, thihs should work to reduce the list to unique items, and counts.

integer vIntCnt;
list vLstTmp;
list vLstCount;
while ((vLstInput != vLstCount){
  vLstTmp = llList2List( vLstInput, vIntCnt ) + llParseString2List ( llDumpList2String( vLstInput, ";" ), llList2List( vLstInput, vIntCnt ) + (list)";", [] );
  vLstCount = (list)((vLstInput == vLstTmp) + 1);
  vLstInput = vLstTmp;
  ++vIntCnt;
}

So basicly like

New item comes....find in list, if found update it's count, if not found add it to the list?

ayup