Second Life Forums Archive - Finding a character string in a strided list

Rolig Loon

Not as dumb as I look

Join date: 22 Mar 2007

Posts: 2,482

07-01-2009 07:37

I'm trying to get my head around what should be an easy problem. The script I'm writing builds a list that contains strides of three elements each. The first element of each stride is an identifier that will sometimes be named "ALLxxx," where xxx is a unique number assigned as the list is built. That is, some of the strides will be of the type ALL and each of those will have a unique xxx so that I can tell them apart. The question is, how can I search the list for instances of ALL, regardless of what xxx is? If I write llListFindList(mylist, ["ALL"]), I won't find anything because "ALLxxx" != "ALL". I know I could of course store xxx as a separate variable in each stride, but I'm trying to keep my strided list from getting too big. Any ideas?

_____________________

It's hard to tell gender from names around here but if you care, Rolig = she. And I exist only in SL, so don't ask....

Look for my work in XStreetSL at

Dora Gustafson

Registered User

Join date: 13 Mar 2007

Posts: 779

07-01-2009 08:18

Tell me, why do you want to search for "ALL"?
You already know where it is: in each stride on first position!
In the list it will be on all positions: 0, 3, 6, 9, ....

Oh I see you have different identifiers from "ALLxxx"

In that case:

integer i = llGetListLength ( yourlist )-3;
while ( i >= 0 )
{
if ( llSubStringIndex( llList2String( yourlist, i), "ALL"

==0 ) ...; // you have a hit, do your stuff
i -= 3;
}

_____________________

From Studio Dora

Rolig Loon

Not as dumb as I look

Join date: 22 Mar 2007

Posts: 2,482

07-01-2009 08:28

There! I knew it had to be easy. I poked at versions of that idea this morning and kept missing it. Strided lists still give me a headache. Thanks, Dora.

_____________________

It's hard to tell gender from names around here but if you care, Rolig = she. And I exist only in SL, so don't ask....

Look for my work in XStreetSL at

Void Singer

Int vSelf = Sing(void);

Join date: 24 Sep 2005

Posts: 6,973

07-01-2009 10:50

I habitually make multiple lists for each stride (1 per stride length) because for starters you don't have to deal with down converting a stride, or searching data that you KNOW isn't going to return (all the off-strided elements) or make a custom stride search (which skips intervening elements)... plus there is no messy hack of removing leading elements to get a listing (or search) of non leading strided elements... that and the math is easier when addressing them...

sadly the only really good usage of strides I see is for flat records with only one key search criteria (the first one). otherwise you tend to save yourself a lot of headaches in design by using matched lists.

the good uses of strides let you insert, remove, and replace single strides easily and sort them quickly (well as quickly as a bubble sort allows, and only on the leading element of your strides, but you could implement your own heap or merge sorts, though I doubt they'll be much faster than the built in bubble sort for smaller lists), but the bad comes in the search and and dump of non-primary strides, and all the offsetting you need to do when addressing non leading stride elements, or looping to search them

_____________________

|
| . "Cat-Like Typing Detected"
| . This post may contain errors in logic, spelling, and
| . grammar known to the SL populace to cause confusion
|
| - Please Use PHP tags when posting scripts/code, Thanks.
| - Can't See PHP or URL Tags Correctly? Check Out This Link...
| -

Dora Gustafson

Registered User

Join date: 13 Mar 2007

Posts: 779

Bubble sort

07-01-2009 11:38

From: Void Singer

(well as quickly as a bubble sort allows, and only on the leading element of your strides, but you could implement your own heap or merge sorts, though I doubt they'll be much faster than the built in bubble sort for smaller lists)

Interesting! Is that a fact that the build in sort is a bubble sort? It is the slowest sort ever composed for lists with more than a few elements and lists not already sorted. The straight insertion sort is faster and don't require more code, so why bubble sort?

_____________________

From Studio Dora

Rolig Loon

Not as dumb as I look

Join date: 22 Mar 2007

Posts: 2,482

07-01-2009 12:16

From: Void Singer

The good uses of strides let you insert, remove, and replace single strides easily and sort them quickly (well as quickly as a bubble sort allows, and only on the leading element of your strides, but you could implement your own heap or merge sorts, though I doubt they'll be much faster than the built in bubble sort for smaller lists), but the bad comes in the search and and dump of non-primary strides, and all the offsetting you need to do when addressing non leading stride elements, or looping to search them

This is the part that gives me headaches. A list can easily grow long enough to start causing memory problems, so I like to be able to remove list elements when I know that they are outdated. Doing that on a strided list, though, often means sorting on more than one criterion (an identifier and a timestamp, for example), which I find hard to do without losing track of a counter somewhere, and which is a cumbersome process even when I get it figured out.

_____________________

It's hard to tell gender from names around here but if you care, Rolig = she. And I exist only in SL, so don't ask....

Look for my work in XStreetSL at

Void Singer

Int vSelf = Sing(void);

Join date: 24 Sep 2005

Posts: 6,973

07-01-2009 13:38

From: Dora Gustafson

Interesting! Is that a fact that the build in sort is a bubble sort? It is the slowest sort ever composed for lists with more than a few elements and lists not already sorted. The straight insertion sort is faster and don't require more code, so why bubble sort?

unless they've finally fixed it (which I've not heard about, but that doesn't mean anything) there's a jira on it, I think it's linked in the Portal

@Rolig
yeah when you do the removals with multiple lists the math is easy, but you have to repeat the operation for each list at the same index..which is a pain, but sorting is ungodly painful with multiple lists, esentailly doubling one list size by inserting sequntial numbers after each element, then sorting, then using those (now out of order) numbers to sort your other lists.... it's not pretty (the stride and search functions leave alot to be desired

_____________________

|
| . "Cat-Like Typing Detected"
| . This post may contain errors in logic, spelling, and
| . grammar known to the SL populace to cause confusion
|
| - Please Use PHP tags when posting scripts/code, Thanks.
| - Can't See PHP or URL Tags Correctly? Check Out This Link...
| -

Dora Gustafson

Registered User

Join date: 13 Mar 2007

Posts: 779

07-01-2009 14:58

From: Void Singer

unless they've finally fixed it

Fixed what? Isn't the bubble sort working?

From: Void Singer

there's a jira on it, I think it's linked in the Portal

In other words: You know nothing, right?
You are right it says so on the portal: under 'Caveats' and under 'Specification'
I apologize

_____________________

From Studio Dora

Void Singer

Int vSelf = Sing(void);

Join date: 24 Sep 2005

Posts: 6,973

07-01-2009 21:16

From: Dora Gustafson

Fixed what? Isn't the bubble sort working?

fixed it to something sensible?

From: someone

In other words: You know nothing, right?

in general... yeah =P

_____________________

|
| . "Cat-Like Typing Detected"
| . This post may contain errors in logic, spelling, and
| . grammar known to the SL populace to cause confusion
|
| - Please Use PHP tags when posting scripts/code, Thanks.
| - Can't See PHP or URL Tags Correctly? Check Out This Link...
| -

Viktoria Dovgal

…

Join date: 29 Jul 2007

Posts: 3,593

07-01-2009 22:38

Yeah, LL's linked list classes use bubble sorts. indra/llcommon/linked_lists.h and indra/llcommon/doublelinkedlist.h for the lulz.

Finding a character string in a strided list
Rolig Loon Not as dumb as I look Join date: 22 Mar 2007 Posts: 2,482	07-01-2009 07:37 I'm trying to get my head around what should be an easy problem. The script I'm writing builds a list that contains strides of three elements each. The first element of each stride is an identifier that will sometimes be named "ALLxxx," where xxx is a unique number assigned as the list is built. That is, some of the strides will be of the type ALL and each of those will have a unique xxx so that I can tell them apart. The question is, how can I search the list for instances of ALL, regardless of what xxx is? If I write llListFindList(mylist, ["ALL"]), I won't find anything because "ALLxxx" != "ALL". I know I could of course store xxx as a separate variable in each stride, but I'm trying to keep my strided list from getting too big. Any ideas? _____________________ It's hard to tell gender from names around here but if you care, Rolig = she. And I exist only in SL, so don't ask.... Look for my work in XStreetSL at
Dora Gustafson Registered User Join date: 13 Mar 2007 Posts: 779	07-01-2009 08:18 Tell me, why do you want to search for "ALL"? You already know where it is: in each stride on first position! In the list it will be on all positions: 0, 3, 6, 9, .... Oh I see you have different identifiers from "ALLxxx" In that case: integer i = llGetListLength ( yourlist )-3; while ( i >= 0 ) { if ( llSubStringIndex( llList2String( yourlist, i), "ALL"==0 ) ...; // you have a hit, do your stuff i -= 3; } _____________________ From Studio Dora
Rolig Loon Not as dumb as I look Join date: 22 Mar 2007 Posts: 2,482	07-01-2009 08:28 There! I knew it had to be easy. I poked at versions of that idea this morning and kept missing it. Strided lists still give me a headache. Thanks, Dora. _____________________ It's hard to tell gender from names around here but if you care, Rolig = she. And I exist only in SL, so don't ask.... Look for my work in XStreetSL at
Void Singer Int vSelf = Sing(void); Join date: 24 Sep 2005 Posts: 6,973	07-01-2009 10:50 I habitually make multiple lists for each stride (1 per stride length) because for starters you don't have to deal with down converting a stride, or searching data that you KNOW isn't going to return (all the off-strided elements) or make a custom stride search (which skips intervening elements)... plus there is no messy hack of removing leading elements to get a listing (or search) of non leading strided elements... that and the math is easier when addressing them... sadly the only really good usage of strides I see is for flat records with only one key search criteria (the first one). otherwise you tend to save yourself a lot of headaches in design by using matched lists. the good uses of strides let you insert, remove, and replace single strides easily and sort them quickly (well as quickly as a bubble sort allows, and only on the leading element of your strides, but you could implement your own heap or merge sorts, though I doubt they'll be much faster than the built in bubble sort for smaller lists), but the bad comes in the search and and dump of non-primary strides, and all the offsetting you need to do when addressing non leading stride elements, or looping to search them _____________________ \| \| . "Cat-Like Typing Detected" \| . This post may contain errors in logic, spelling, and \| . grammar known to the SL populace to cause confusion \| \| - Please Use PHP tags when posting scripts/code, Thanks. \| - Can't See PHP or URL Tags Correctly? Check Out This Link... \| -
Dora Gustafson Registered User Join date: 13 Mar 2007 Posts: 779	Bubble sort 07-01-2009 11:38 From: Void Singer (well as quickly as a bubble sort allows, and only on the leading element of your strides, but you could implement your own heap or merge sorts, though I doubt they'll be much faster than the built in bubble sort for smaller lists) Interesting! Is that a fact that the build in sort is a bubble sort? It is the slowest sort ever composed for lists with more than a few elements and lists not already sorted. The straight insertion sort is faster and don't require more code, so why bubble sort? _____________________ From Studio Dora
Rolig Loon Not as dumb as I look Join date: 22 Mar 2007 Posts: 2,482	07-01-2009 12:16 From: Void Singer The good uses of strides let you insert, remove, and replace single strides easily and sort them quickly (well as quickly as a bubble sort allows, and only on the leading element of your strides, but you could implement your own heap or merge sorts, though I doubt they'll be much faster than the built in bubble sort for smaller lists), but the bad comes in the search and and dump of non-primary strides, and all the offsetting you need to do when addressing non leading stride elements, or looping to search them This is the part that gives me headaches. A list can easily grow long enough to start causing memory problems, so I like to be able to remove list elements when I know that they are outdated. Doing that on a strided list, though, often means sorting on more than one criterion (an identifier and a timestamp, for example), which I find hard to do without losing track of a counter somewhere, and which is a cumbersome process even when I get it figured out. _____________________ It's hard to tell gender from names around here but if you care, Rolig = she. And I exist only in SL, so don't ask.... Look for my work in XStreetSL at
Void Singer Int vSelf = Sing(void); Join date: 24 Sep 2005 Posts: 6,973	07-01-2009 13:38 From: Dora Gustafson Interesting! Is that a fact that the build in sort is a bubble sort? It is the slowest sort ever composed for lists with more than a few elements and lists not already sorted. The straight insertion sort is faster and don't require more code, so why bubble sort? unless they've finally fixed it (which I've not heard about, but that doesn't mean anything) there's a jira on it, I think it's linked in the Portal @Rolig yeah when you do the removals with multiple lists the math is easy, but you have to repeat the operation for each list at the same index..which is a pain, but sorting is ungodly painful with multiple lists, esentailly doubling one list size by inserting sequntial numbers after each element, then sorting, then using those (now out of order) numbers to sort your other lists.... it's not pretty (the stride and search functions leave alot to be desired _____________________ \| \| . "Cat-Like Typing Detected" \| . This post may contain errors in logic, spelling, and \| . grammar known to the SL populace to cause confusion \| \| - Please Use PHP tags when posting scripts/code, Thanks. \| - Can't See PHP or URL Tags Correctly? Check Out This Link... \| -
Dora Gustafson Registered User Join date: 13 Mar 2007 Posts: 779	07-01-2009 14:58 From: Void Singer unless they've finally fixed it Fixed what? Isn't the bubble sort working? From: Void Singer there's a jira on it, I think it's linked in the Portal In other words: You know nothing, right? You are right it says so on the portal: under 'Caveats' and under 'Specification' I apologize _____________________ From Studio Dora
Void Singer Int vSelf = Sing(void); Join date: 24 Sep 2005 Posts: 6,973	07-01-2009 21:16 From: Dora Gustafson Fixed what? Isn't the bubble sort working? fixed it to something sensible? From: someone In other words: You know nothing, right? in general... yeah =P _____________________ \| \| . "Cat-Like Typing Detected" \| . This post may contain errors in logic, spelling, and \| . grammar known to the SL populace to cause confusion \| \| - Please Use PHP tags when posting scripts/code, Thanks. \| - Can't See PHP or URL Tags Correctly? Check Out This Link... \| -
Viktoria Dovgal … Join date: 29 Jul 2007 Posts: 3,593	07-01-2009 22:38 Yeah, LL's linked list classes use bubble sorts. indra/llcommon/linked_lists.h and indra/llcommon/doublelinkedlist.h for the lulz.

Welcome to the Second Life Forums Archive

Finding a character string in a strided list