Best method of storing lists of numbers
|
Kermitt Quirk
Registered User
Join date: 4 Sep 2004
Posts: 267
|
09-21-2004 21:01
For a project I'm working on I need to store many sets of numbers (it might be something like 50 x 3 numbers). At the moment I'm storing strings in a list where each string is one set of the 3 numbers. e.g. "1,2,3"
When I want to retrieve one of these 3 values I need to... - get the line (string) from the list that contains the set of values I'm after. - Split that string into a list by separating it at the commas using llParseString2List - Get the value I need from the new list
Needless to say this is a very slow process.
The ideal solution here would be to use some sort of structure in an array, but I don't think that'll happen anytime this century.
What I was thinking of doing instead was storing the values as 3 doublebyte values. i.e. convert each value to the ascii equivilent, then put the 3 together as a string. That way the 3 values could be stored in only 6 bytes total. Now the conversion to get a value back would just be a matter of using llGetSubString to grab the correct 2 bytes, and convert them back to the original value, which should be a lot faster than having to parse a string to a list.
I've probably rambled enough by now so I'll just get to the point. To do this I think I would need some sort of Asc() and Chr() functions (for converting between ascii chars and there decimal equivilent) but it appears LSL doesn't have this.
Can anyone suggest any way I could achieve this, or suggest some similar method of storing/retrieving groups of values like this which is effiecient on memory, and fast?
On a side note, does any one know if using llCSV2List() is faster than using llParseString2List(string, [", "], [])?
|
Strife Onizuka
Moonchild
Join date: 3 Mar 2004
Posts: 5,887
|
09-22-2004 06:41
it depends on the range of your numbers and what you need to use them for. If you know the range of them you can then pack them into a single integer and then if you really want to pack 4 integers into a key. The more list entries you have the more space that will be used up for list overhead.
But if you are just storing 150 integers you don't have to worry about it. I think you can store about 700 in a list before you start running out of space.
_____________________
Truth is a river that is always splitting up into arms that reunite. Islanded between the arms, the inhabitants argue for a lifetime as to which is the main river. - Cyril Connolly
Without the political will to find common ground, the continual friction of tactic and counter tactic, only creates suspicion and hatred and vengeance, and perpetuates the cycle of violence. - James Nachtwey
|
Wednesday Grimm
Ex Libris
Join date: 9 Jan 2003
Posts: 934
|
09-22-2004 08:10
Computers (on a lower level) don't have arrays, they're just something the compiler does for you. Here's a quick (an probably syntatically wrong) 3xN array. integer XMAX = 3;
list lArr = [5, 23, 45, 2, 19, 56, 45, 76, 128, 0, 15, 16 ... ];
integer getVal(integer x, integer y) { integer idx = 0; idx = y * XMAX + x; if (idx >= llGetListLength(lArr)) return -1; // or your favourite error value return llList2Integer(lArr, idx); } So, one way to look at this is as a 3xN array, another way is as an array of structures, where the struct is 3 integers. If you wanted to use different kinds of variables, you would have a different "get" function for each member, with a hardcoded x. If you were wondering what all the list functions with "stride" in the name were for, it's this, storing structures in lists.
_____________________
Sarcasm meter: 0 |-----------------------*-| 10 Rating: Awww Jeeze!
|
Tiger Crossing
The Prim Maker
Join date: 18 Aug 2003
Posts: 1,560
|
09-22-2004 09:01
list data = [ 1,2,3 , 4,5,6 , 7,8,9 , 10,11,12 , 13,14,15 , 16,17,18 , 19,20,21 ];
integer a; for ( a=0; a<llGetListLength( data ); a=a+3 ) { integer x = llList2Integer( data, a ); integer y = llList2Integer( data, a+1 ); integer z = llList2Integer( data, a+2 );
// do somthing with x,y,z here }
_____________________
~ Tiger Crossing ~ (Nonsanity)
|
Strife Onizuka
Moonchild
Join date: 3 Mar 2004
Posts: 5,887
|
09-22-2004 09:17
i've done a number of projects where counting bytes has been important (while i have *never* packed integers into keys, i do reguraly pack multiple integers into a single integer) this will pack ten - 3 bit integers into one integer. it also uses hte third bit as negative; if you don't want that just remove the 29 left/right bit shifts. The intpacker doesn't do proper rounding on the integers if they are to big or small. integer intpack(list_rt) { integer_b; integer_d; for(d=llGetListLength(rt);d;d--) b=b*8+(llList2Integer(rt,d_-_1)&7); return b; }
list intunpack(integer a) { list b; integer c; for(;c<10 && a;c++,a=(a&(~7))>>3) b+=(((a&7)<<29)>>29); return b; }
_____________________
Truth is a river that is always splitting up into arms that reunite. Islanded between the arms, the inhabitants argue for a lifetime as to which is the main river. - Cyril Connolly
Without the political will to find common ground, the continual friction of tactic and counter tactic, only creates suspicion and hatred and vengeance, and perpetuates the cycle of violence. - James Nachtwey
|
Morgaine Dinova
Active Carbon Unit
Join date: 25 Aug 2004
Posts: 968
|
09-22-2004 10:02
From: someone Originally posted by Wednesday Grimm Computers (on a lower level) don't have arrays, they're just something the compiler does for you. Actually, computers (on the hardware level) do have arrays, they're just something that the LSL compiler decides not to expose. 
|
Wednesday Grimm
Ex Libris
Join date: 9 Jan 2003
Posts: 934
|
09-22-2004 10:19
From: someone Originally posted by Morgaine Dinova Actually, computers (on the hardware level) do have arrays, they're just something that the LSL compiler decides not to expose. Are you calling me out?
_____________________
Sarcasm meter: 0 |-----------------------*-| 10 Rating: Awww Jeeze!
|
Samhain Broom
Registered User
Join date: 1 Aug 2004
Posts: 298
|
09-22-2004 10:24
I guess that means you can almost use the list parsing with the strides as if it were an associative variable... gee, wouldn't THAT be nice?
Even a "NOT REAL" language like PERL has an Associative array variable type!
I guess I'm preaching to the choir here... so I'll stop and just sigh!
_____________________
rm -rf /bin/ladden #beware of geeks bearing grifts
|
Morgaine Dinova
Active Carbon Unit
Join date: 25 Aug 2004
Posts: 968
|
09-22-2004 10:28
From: someone Originally posted by Wednesday Grimm Are you calling me out? I don't need to, since I'm right. 
|
Wednesday Grimm
Ex Libris
Join date: 9 Jan 2003
Posts: 934
|
09-22-2004 10:53
What archiceture has hardware support of arrays of abritrary structures? Or n-dimensional arrays?
_____________________
Sarcasm meter: 0 |-----------------------*-| 10 Rating: Awww Jeeze!
|
Morgaine Dinova
Active Carbon Unit
Join date: 25 Aug 2004
Posts: 968
|
09-22-2004 16:49
From: someone Originally posted by Wednesday Grimm What archiceture has hardware support of arrays of abritrary structures? Or n-dimensional arrays? Haha, I see that you've finally noticed your earlier error and so you've now changed your statement to refer to multi-dimensional arrays. See, I told you I was right. 
|
Wednesday Grimm
Ex Libris
Join date: 9 Jan 2003
Posts: 934
|
09-22-2004 20:14
From: someone Originally posted by Morgaine Dinova Haha, I see that you've finally noticed your earlier error and so you've now changed your statement to refer to multi-dimensional arrays. See, I told you I was right. A single dimensional byte array is just an offset to a memory address. It's base + offset. Yes, let me be the first to admit that almost all modern CPUs natively support integer addition.
_____________________
Sarcasm meter: 0 |-----------------------*-| 10 Rating: Awww Jeeze!
|
Kermitt Quirk
Registered User
Join date: 4 Sep 2004
Posts: 267
|
09-22-2004 21:40
Well, from the look of the replies there really isn't a lot of choices. I think I can probably save a bit of memory by getting away from the strings and just using integers in a list, in this kinda fake 2d structure that many of you described. Reminds me of back when I used to program on an Atari 130XE. Atari Basic couldn't do 2d arrays of strings so I used the same trick for storing strings that defined a map. Hadn't actually notice the stride functions though, so that's to Wednesday for that one. I'll have to have a closer look at them. Although you didn't use them in your example (and nor did anyone else). I get the impression, from a quick glance at the wiki, that maybe the stride commands don't work the way they should. Is this why noone else pointed them out?
The trick that Strife has descibed is definately what I was looking for when I was talking about converting to ascii values, cept you're still not storing them as strings which is something I hadn't thought of. I'm guessing those pack/unpack routines are pretty fast too, but I think I'll have to do a few tests to work out if I'm saving enough memory with it to make the extra processing worthwhile.
All in all a very nice response. Thanx to all!
|
Strife Onizuka
Moonchild
Join date: 3 Mar 2004
Posts: 5,887
|
09-22-2004 23:47
Just FYI the pack function is partialy imported form another script i wrote and the unpacker i custom wrote here and haven't tested it to make sure it's 100% accurate. (where i used it i had the unpacker built into the function that would have used it.)
About the strided functions, i usualy don't have even amounts of data in each row. So they aren't very useful to me. Or if i do i end up using multiple lists, by spliting it into multiple lists it allows you to grow the lists longer.
_____________________
Truth is a river that is always splitting up into arms that reunite. Islanded between the arms, the inhabitants argue for a lifetime as to which is the main river. - Cyril Connolly
Without the political will to find common ground, the continual friction of tactic and counter tactic, only creates suspicion and hatred and vengeance, and perpetuates the cycle of violence. - James Nachtwey
|
Azelda Garcia
Azelda Garcia
Join date: 3 Nov 2003
Posts: 819
|
09-23-2004 00:19
FWIW, theres another way to store tables in lists. You can use one list per table column: list lsAvatarName = []; list lfAvatarHeight = []; list lvAvatarPosition = [];
Then just treat the whole thing as a single table. Azelda
|
Morgaine Dinova
Active Carbon Unit
Join date: 25 Aug 2004
Posts: 968
|
09-23-2004 01:40
From: someone Originally posted by Wednesday Grimm A single dimensional byte array is just an offset to a memory address. It's base + offset. Yes, let me be the first to admit that almost all modern CPUs natively support integer addition. Nice to see you admit it.  For the benefit of anyone who isn't acquainted with computer architecture and who might not have known what we're on about here ... All normal computer memory spaces in current-day machinery are organized as one or more linear arrays of basic virtual data cells of various sizes. Each such data or memory cell normally has a size that is an integer power of 2 in bytes, ie. 1 byte, 2, 4, 8, etc (regardless of the width of actual physical memory), and all modern processor instruction sets directly support array indexing into these linear arrays of virtual cells in their hardware. Individual data access instructions actually have one or more addressing modes dedicated to such array indexing, ie. all that a compiler needs to do is to interface to this native hardware ability. This O(1) operation (ie. constant time regardless of the value of the array index) is one of the most efficient operations that a processor can perform, and every serious computer program that handles random access into large data sets tries to use this underlying hardware support for array indexing in order to remain efficient. This isn't always possible however, because a few languages don't expose the array access operation to their users, one example of this being LSL. Fortunately Don Linden said that array indexing is on his to-do list for LSL, which is no surprise really since the O(1) of array indexing vs the O(n) of list traversal should contribute to decreasing the loading on sims and also provide a better experience for users.
|
Samhain Broom
Registered User
Join date: 1 Aug 2004
Posts: 298
|
09-23-2004 09:55
Hey Kermitt,
If your three digits you are storing can be floating numbers, perhaps you can store the three digits in a vector class variable?
ie:
vector var1 = <1.0, 2.0, 3.0>; vector var2 = <4.0, 5.0, 6.0>;
Later to access the numbers
float new1 = var1.x; // new1 = 1.0 float new2 = var1.y; // new2 = 2.0 float new3 = var1.z; // new3 = 3.0 float new6 = var2.z; // new6 = 6.0
Why not?
_____________________
rm -rf /bin/ladden #beware of geeks bearing grifts
|
Samhain Broom
Registered User
Join date: 1 Aug 2004
Posts: 298
|
09-23-2004 10:22
Oops, I thought I posted a reply to this... I guess it went off into the ether!
Why not try using a vector type variable?
vector var1 = <1.0, 2.0, 3.0>; vector var2 = <4.0, 5.0, 6.0>; ... vector var50 = <151.0, 152.0, 153.0>;
later you can access with:
float x = var1.x; // = 1.0 float y = var2.y; // = 5.0
Would that work?
_____________________
rm -rf /bin/ladden #beware of geeks bearing grifts
|