Easiest way to find total matches in a list

[Yamil Dagger]

Can somebody tell me what the easiest way would be to find a string/value in a list and return how many times that string or value is in the list?

 

so...

[1,2,2,2,3,4,5,5]

How can I pull the total number of "2"s from this string so it would return 3? Would I have to make a loop check each index?

[Rolig Loon]

Yes.  That's how I'd do it.

[irihapeti]

if your list is sorted as in your example then can consider doing a binary/library search rather than a linear/sequential search

for comparison

linear search
1 : 2 its. 1,2
2 : 5 its. 1,2,2,2,3
3 : 6 its. 1,2,2,2,3,4
4 : 7 its. 1,2,2,2,3,4,5
5 : 7 its. 1,2,2,2,3,4,5

total: 27 its

library search going low
1 : 3 its. 2,1,2
2 : 5 its. 2,2,2,1,3
3 : 3 its. 2,4,3
4 : 4 its. 2,4,3,5
5 : 3 its. 2,4,5

total: 18 its

+

this said

if you have a list where some items are more frequently searched for than others then can consider a Move-To-Front linear search algo

where whenever items are searched for they are moved to the front of the list. The basis being that the last searched items are more likely to be searched for again

is a reference here about all this: http://en.wikipedia.org/wiki/Binary_search_algorithm

[LepreKhaun]

Doesn't matter if the list is sorted or not and length of list is immaterial. One needs only to iterate the number of times that there are matches:

// Call with (list, (list)item), item may be any lsl variable type (except list, of course)
integer numberTimesFound(list theList, list item){    integer place;    if(~(place = llListFindList(theList, item)))        return 1 + numberTimesFound(llDeleteSubList(theList, 0, place), item); // Edited, see Note below    else        return 0;}

 Just have to know the tools at hand.

[Note: I first had llDeleteSubList(theList, place, place) but later realized it was much better to trim off the start of the list up to place, sending an ever smaller list into the recursion.]

[irihapeti]

when the list is sorted as OP showed then performance-wise by the tools is probably

 

integer NumberOf(list lst, integer this){  integer i = llListFindList(lst, [this]);  integer j = 1 + i;  if (j && j < llGetListLength(lst))    while(llList2Integer(lst, j) == this) j++;  return j - i;} 

  
if was unsorted then i probably sort it first

[LepreKhaun]

---

irihapeti wrote:

when the list is sorted as OP showed then performance-wise by the tools is probably

 

integer NumberOf(list lst, integer this){  integer i = llListFindList(lst, [this]);  integer j = 1 + i;  if (j && j < llGetListLength(lst))    while(llList2Integer(lst, j) == this) j++;  return j - i;} 

  

if was unsorted then i probably sort it first

---

Wrong, this fails if there is no match:

integer numberTimesFound(list theList, list item){    integer place;    if(~(place = llListFindList(theList, item)))        return 1 + numberTimesFound(llDeleteSubList(theList, 0, place), item);    else        return 0;}integer NumberOf(list lst, integer this){    integer i = llListFindList(lst, [this]);    integer j = 1 + i;    if (j && j < llGetListLength(lst))        while(llList2Integer(lst, j) == this) j++;    return j - i; // If no match is found, then this line is "return 0 - (-1)"} default{    touch_end(integer num){        list haystack = [1,2,3];        integer needle = 5;            llOwnerSay((string)NumberOf(haystack, needle)); // 1        llOwnerSay((string)numberTimesFound(haystack, (list)needle)); // 0    }}

 [Edited to show exactly where and how your error is occuring.]

[LepreKhaun]

Of course, I do realize that recursion may be beyond the grasp of most novice programmers. Here's my solution (which works for the general case as well as the specifc case of an ordered list) done within a loop:

integer numberTimesFound(list theList, list item){    integer place;    integer count = 0;        while (~(place = llListFindList(theList, item)))    {        theList = llDeleteSubList(theList, 0, place);        ++count;    }        return count;}

 

[irihapeti]

yes. my bad. 0 - -1 != 0

fixed. is a bit more efficient as well by the tools

 

integer NumberOf(list lst, integer this){  integer i = llListFindList(lst, [this]);  integer j = i;  if (i >= 0)     while(llList2Integer(lst, (++j)) == this);  return j - i;}

 +

am curious why you recommending a deletion search to novices given the amount of memory thrashing that LSL lists incur when copying. Can understand why to use a deletion search in a special case. Just not getting why that might be recommended in the general case of getting counts

can see tho how it might seem more efficient in the case of unsorted. Altho probably have to do a whole bunch of tests on typical inputs for the particular app to make a determination as to its efficiency compared to a straightout counting algo. Given that they both O(n) linear search algos

is good tho that you did provide a non-recursive alternative. Recursion can blow the stack if not careful and should probably only be recommended to novices for the special case

 

[LepreKhaun]

---

irihapeti wrote:

yes. my bad. 0 - -1 != 0

fixed. is a bit more efficient as well by the tools

 

integer NumberOf(list lst, integer this){  integer i = llListFindList(lst, [this]);  integer j = i;  if (i >= 0)     while(llList2Integer(lst, (++j)) == this);  return j - i;}

 +

am curious why you recommending a deletion search to novices given the amount of memory thrashing that LSL lists incur when copying. Can understand why to use a deletion search in a special case. Just not getting why that might be recommended in the general case of getting counts

can see tho how it might seem more efficient in the case of unsorted. Altho probably have to do a whole bunch of tests on typical inputs for the particular app to make a determination as to its efficiency compared to a straightout counting algo. Given that they both O(n) linear search algos

is good tho that you did provide a non-recursive alternative. Recursion can blow the stack if not careful and should probably only be recommended to novices for the special case

 

---

I agree that any looping construct, elementary (for, while, do...while) or extended (recursive, dataserver, etc) , can "blow the stack if not careful".

 

And though "the amount of memory thrashing that LSL lists incur when copying" sounds scary, you do realize that LSL is pass by value to any and all functions, yes? Which means every call to a Linden Library list manipulation function is resulting in a copy of the list being made. I reckon we'll just have to live with beating that poor memory to death if we're going to deal with lists. Hopefully the screams won't keep anyone awake at night.

 

Anyway, I'm glad you worked out your attempt to count the occurances of an integer in an ordered list finally. Keep up the good work!

 

[ETA: FYI- You've gotten your definitions backwards; any subset of a group is regarded as a "special case" of the entire grouping, which is called the "general case". So, an ordered list is a "special case" of lists in general, not the other way around. ]

[irihapeti]

about memory thrashing

is bc LSL lists are passed by value that causes the memory thrashing. So best to avoid that if possible

+

about loops

for x = 1 to somelargenumber

wont blow the stack all by itself. It just takes a long time to execute

need to be pushing other stuff inside the loop onto the stack for a for/while/do loop to blow. A recursion loop does push stuff onto the stack by design

+

about the last

the reference was made to unsorted which is the general case as you say

[LepreKhaun]

Back to the topic at hand:

 

To find the total matches of an element in a list, it is sub-optimal to loop through all of the list indices. And it grows more sub-optimal as the size of the list increases, with the worse case being no occurances at all.

 

Much better is to use an algorithm that will only loop as many times as the element occurs., where the worse case would be all the elements in the list matching.

 

In the case of an integer within an ordered or sorted list, irihapeti has furnished an adequate a very good [Edited for correctness] solution. For the more general case of counting any variable within any list, there's mine.

 

Use either as needed.

[Dora Gustafson]

---

Yamil Dagger wrote:

Can somebody tell me what the easiest way would be to find a string/value in a list and return how many times that string or value is in the list?

---

Another answer to that question is in this in line code

It uses no recursition and no list sorting

In return it is short and simple

// count occurrences in list; by Dora Gustafson, Studio Dora// v1.1 inline codedefault{    state_entry()    {        list haystack = [1,2,1,2,1,2,3,2,4,5,2,6,4,2,3,2,1,8];        list needle = [2];        integer i = 0;        integer j = 0;        integer k = llListFindList( haystack, needle);        integer m = llGetListLength( haystack );        while ( k >= 0 && i < m )        {            i += k+1;            k = llListFindList( llList2List( haystack, i, -1), needle);            ++j;        }        llOwnerSay((string)needle+" occurs "+(string)j+" times in "+llDumpList2String( haystack, ", "));    }}

This program is straight, a recursive approach follows 

// count occurrences in list; by Dora Gustafson, Studio Dora 2014// v1.1 inline code// v1.2 recursive approachlist haystack = [1,2,1,2,1,2,3,2,4,5,2,6,4,2,3,2,1,8];list needle = [2];integer j = 0;tin( list L ){    integer k = llListFindList( L, needle);    if ( k >= 0 )    {        ++j;        if ( k+1 < llGetListLength(L) ) tin( llList2List( L, k+1, -1));    }}default{    state_entry()    {        tin( haystack);        llOwnerSay((string)needle+" occurs "+(string)j+" times in "+llDumpList2String( haystack, ", "));    }}

The advantage of recursion over straight code is a shorter code(the code is reused)

The disadvantages are longer execution time and more overhead generated at runtime

For these reasons the recursion approach is a bad choice to search a long list in LSL

:smileysurprised::smileyvery-happy:

[LepreKhaun]

Correct, there are a number of possible solutions to this problem.

And it should be pointed out that any recursive function can be made into a more elementary loop (as I showed earlier), any non-recursive function can be inlined and any inlined code can also be made into a function. Which is most appropriate in any given script should be determined by the programmer on a case by case basis.