removing duplicates from a list
|
|
Thanto Usitnov
Lord Byron wannabe
Join date: 4 Aug 2006
Posts: 68
|
11-12-2006 14:40
I have a list of vectors compiled from multiple different lists of vectors, some of which may contain some of the same vectors as the other lists. I only need unique vectors, though. So, my problem is figuring out how to delete multiple vectors from the list. here's what I have so far: list culllist(list input)
{
list output = input;
integer len = llGetListLength(input);
integer i;
integer j;
for (i = 0; i < len; i++) //delete all instances of llList2Vector(i)
{
for (j = i + 1; j < len; j++) //compare to everything after i...
{
if (llList2Vector(output,i) == llList2Vector(output,j) )
{
output = llDeleteSubList(output,j,j); //if it matches, delete it
len--; //decrement len and iterator so we don't skip or go over bounds
j--;
}
}
}
return output;
} This is entirely untested, of course. So, questions: 1. is it possible to compare vectors in the way given above? 2. can lists of vectors be usefully sorted? 3. is there a more efficient way to do this? |
|
Newgate Ludd
Out of Chesse Error
Join date: 8 Apr 2005
Posts: 2,103
|
11-12-2006 15:26
From: Thanto Usitnov I have a list of vectors compiled from multiple different lists of vectors, some of which may contain some of the same vectors as the other lists. I only need unique vectors, though. So, my problem is figuring out how to delete multiple vectors from the list.
This is entirely untested, of course. So, questions:
1. is it possible to compare vectors in the way given above?
2. can lists of vectors be usefully sorted?
3. is there a more efficient way to do this? I have never tried it with vectors but the llListSort function may help. |
|
Llauren Mandelbrot
Twenty-Four Weeks Old.
Join date: 26 Apr 2006
Posts: 665
|
11-12-2006 15:53
Also,
if (llList2Vector(output,i) == llList2Vector(output,j) )
{
output = llDeleteSubList(output,j,j);
might be better off as
if (llList2Vector(output,i) == llList2Vector(input,j) )
{
output = llDeleteSubList(output,i,i);
You are comparing the list you are modifying against itself. You should be comparing it against the unmodified list.
On the other hand, you could do something like this:
list culllist(list input)
{
integer i;
integer j;
for (i = llGetListLength(input) - 1; i >0; i--) //delete all instances of llList2Vector(i)
{
for (j = i + 1; j < len; j++) //compare to everything after i...
{
if (llList2Vector(input,i) == llList2Vector(input,j) )
{
input = llDeleteSubList(input,j,j); //if it matches, delete it
j--;
}
}
}
return input;
} ...which would reduce the memory used.
_____________________
- ninjafoo Ng Says:
November 4th, 2006 at 7:27 am We all love secondlife so much and were afraid that the magic will end, nothing this good can ever last…. can it?
|
|
Newgate Ludd
Out of Chesse Error
Join date: 8 Apr 2005
Posts: 2,103
|
11-12-2006 16:15
Except that you are deleting form the list you are indexing ....
list culllist(list input)
{
list output;
integer i = 0;
for(i =0; i < llGetListLength(input); ++i)
{
vector v = llList2Vector(input,i);
if( llListFindList(output, [ v ] ) < 0 )
{
output = (output = []) + output + [ v ];
}
}
return output;
}
|
|
Haravikk Mistral
Registered User
Join date: 8 Oct 2005
Posts: 2,482
|
11-12-2006 16:17
From: Newgate Ludd I have never tried it with vectors but the llListSort function may help. Newgate is right, a solution something like this would therefore be better: list cullList (list input) {
input = llListSort(input, 1, TRUE);
output = [];
integer x = llGetListLength(input) - 1;
while (x > 0) {
vector current = llList2Vector(input, x);
if (y != llList2Vector(input, --x))
output += [y];
}
return output;
}This works because it goes through the list starting at the end, notice that every time it does a comparison, it decrements x by one (thus it works it's way down to index 0). It also only needs to go through N times where N is the number of list elements, since the sorting puts all identical elements side-by-side. It needs to be noted though that the overhead associated with a function like this is double the size of the list. I highly recommend instead of using this as a function you copy/paste the culling code into your script where you need to perform the cull, as that way you don't have to pass the list into function (thus creating another copy!). If you had a 1kb list, you'd need at least 3kb of free memory to work with it (1kb for the original, 1kb for the copy passed into the cullList function, and 1kb for the manipulation, probably another 1kb for LSL to work with it all). You'd be better off taking each list you want to concatenate and check for duplicates before adding an element, such as: list theList;
addList(list listToAdd) {
integer x = llGetListLength(listToAdd);
while (x > 0) {
vector current = llList2Vector(listToAdd, --x);
if (llListFindList(theList, [current]) < 0)
theList += [current];
}
} This way you only add non-duplicates, and there is no overhead except to copy listToAdd, even better, you can make listToAdd a global and copy the list you want to add into it, then clear it, e.g: list theList;
list listToAdd;
addList() {
integer x = llGetListLength(listToAdd);
while (x > 0) {
vector current = llList2Vector(listToAdd, --x);
if (llListFindList(theList, [current]) < 0)
theList += [current];
} listToAdd = [];
}
default {
state_entry() {
list items = [<1.0, 1.0, 1.0>, <0.5, 0.1, 0.8>];
listToAdd = items;
items = [];
addList();
}
} Hope some of that helps!
_____________________
Computer (Mac Pro):
2 x Quad Core 3.2ghz Xeon
10gb DDR2 800mhz FB-DIMMS
4 x 750gb, 32mb cache hard-drives (RAID-0/striped)
NVidia GeForce 8800GT (512mb)
|
|
Strife Onizuka
Moonchild
Join date: 3 Mar 2004
Posts: 5,887
|
11-12-2006 17:28
From: Haravikk Mistral list theList;
addList(list listToAdd) {
integer x = llGetListLength(listToAdd);
while (x > 0) {
vector current = llList2Vector(listToAdd, --x);
if (llListFindList(theList, [current]) < 0)
theList += [current];
}
} You can make it faster and not vector specific too.
addList(list listToAdd) {
integer x = [] != listToAdd;
if(x) {
list current = [];
do
{
if(~llListFindList(theList, current=llList2List(listToAdd, x,x)))
theList += current;
}while((x=-~x));
}
}
_____________________
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
|
|
Llauren Mandelbrot
Twenty-Four Weeks Old.
Join date: 26 Apr 2006
Posts: 665
|
11-12-2006 17:36
Except that you are deleting form the list you are indexing ....Yes, Newgy, I know that. That`s why I reversed the index in the outer loop. The way I did it, it doesn`t matter that they are being deleted from the same list. On second thought, I suppose I should have reversed the index on the inner loop too, and for the same reason. Also, because the argument is a copy of the original list already, the it doesn`t matter to the calling program that we`re modifying the argument in-place instead of making yet another copy of it.
_____________________
- ninjafoo Ng Says:
November 4th, 2006 at 7:27 am We all love secondlife so much and were afraid that the magic will end, nothing this good can ever last…. can it?
|
|
Thanto Usitnov
Lord Byron wannabe
Join date: 4 Aug 2006
Posts: 68
|
11-12-2006 21:04
From: Llauren Mandelbrot You are comparing the list you are modifying against itself. You should be comparing it against the unmodified list. I considered that the first time I checked, and checking against the unmodified list doesn't make sense, because I'd be checking from things that were taken out, which would be a waste of time. From: Newgate Ludd Except that you are deleting form the list you are indexing .... That was my intention. Instead of going over the long list containing duplicates, I'd only go over what was left after each pass. That way, instead of going over the whole list every time, comparing the index value, which could be a duplicate that would already be removed and would thus be a completely wasted pass, to values which could also be duplicates, which may have been removed in previous passes, I'd be going over a presumably shorter, partially culled list. From: Haravikk Mistral It needs to be noted though that the overhead associated with a function like this is double the size of the list. I kinda forgot about that. Good point. This is especially important, because the compiled could end up being quite huge, and I'd rather not overload the script's buffer. Anyway, I did some experimental testing. setup: veclist = [<1.0,2.0,3.0>,<4.0,5.0,6.0>,<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,<7.0,8.0,9.0>,<1.0,2.0,3.0>]; my method: 4.4 4.6 4.7 4.6 Strife's method: 1.8 1.9 1.8 much faster. But it's still prohibitively slow for my application. I need something under 1 second. blah. I have to go. |
|
Jesse Barnett
500,000 scoville units
Join date: 21 May 2006
Posts: 4,160
|
11-12-2006 21:14
Oh goodie! Another else-if type thread comparing script times!!! WooHoo. If I wasn't brain dead I might try a couple of intinerations myself tonight. O well, always tomorrow. But really, these threads with these discussions help the scripting community a great deal. PS (No I didn't post this just to get my posting count up some Newgate
_____________________
I (who is a she not a he) reserve the right to exercise selective comprehension of the OP's question at anytime. From: someone I am still around, just no longer here. See you across the aisle. Hope LL burns in hell for archiving this forum
|
|
Elsewhere Essex
Registered User
Join date: 8 Sep 2006
Posts: 50
|
11-12-2006 21:22
your out of luck for a faster way Thanto.
I've tried every form of removing duplicates from lists, mostly for applications in which i have a large list of notecardsstored UUID's, and using llListFindList() was the fastest solution.... and if it's used as values are to be added to the list, you never have to worry about them taking up your overhead. the ListFindList will just pass them over. at this point i've managed to get roughly 200+ UUID's stored, unmodified or compressed, to be loaded, scanned for duplicates, and passed along into memory before hitting a Stack Heap Collision.
at some point, i think i may see just how many exactly i can get in there before i hit the extent of script memory, then start playing with compression techniques to fit even more.
unless someone else has done the foot work in that territory, to which i kindly ask for a link pointing me in the right direction....
|
|
Strife Onizuka
Moonchild
Join date: 3 Mar 2004
Posts: 5,887
|
11-13-2006 00:12
What is the range & percision you need on the vectors? Worst come to worst you could pack them into an integer. The packing wouldn't be fast but you would probably make it back on the list operation.
What exactly are these vectors and what are they used for?
_____________________
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
|
|
Kator Bergson
I'm freakin out man!
Join date: 24 Nov 2005
Posts: 125
|
11-13-2006 00:31
ZOMG!!! Thanto Usitnov You broke the forums!!! lol...
(yes I know, nothing helpful, but had to say it.)
|
|
Haravikk Mistral
Registered User
Join date: 8 Oct 2005
Posts: 2,482
|
11-13-2006 03:32
From: Thanto Usitnov much faster. But it's still prohibitively slow for my application. I need something under 1 second. Can you give us more detail on what you're doing with this information? Perhaps there's another solution depending on what you're trying to do? Part of the problem is that llListFindList() is fairly slow, since the lists aren't properly sorted so it goes through EVERY element till it finds it (or worse if it doesn't find it, it goes through ALL of them to the end just to be sure). I can't think of any easy way around this though, as we have no facility to create any better structures, for example trees, which would fairly easily sort the info and be quick to search.
_____________________
Computer (Mac Pro):
2 x Quad Core 3.2ghz Xeon
10gb DDR2 800mhz FB-DIMMS
4 x 750gb, 32mb cache hard-drives (RAID-0/striped)
NVidia GeForce 8800GT (512mb)
|
|
Llauren Mandelbrot
Twenty-Four Weeks Old.
Join date: 26 Apr 2006
Posts: 665
|
11-13-2006 08:30
Hmm, keep the list sorted, and use a binary search to prevent adding duplicates?
_____________________
- ninjafoo Ng Says:
November 4th, 2006 at 7:27 am We all love secondlife so much and were afraid that the magic will end, nothing this good can ever last…. can it?
|
|
Jesse Barnett
500,000 scoville units
Join date: 21 May 2006
Posts: 4,160
|
11-13-2006 11:06
This is close and is very fast but I messed up somewhere and it is deleting and not returning the last vector. I have to take a break and can't finish debugging it yet:
list veclist = [<1.0,2.0,3.0>,<4.0,5.0,6.0>,<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,
<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,
<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,<7.0,8.0,9.0>,<1.0,2.0,3.0>];
list veclist_new;
list compare;
integer del_pos;
default
{
state_entry() {
veclist = llListSort(veclist, 1, TRUE);
integer length = llGetListLength(veclist);
compare = llList2List(veclist, 1, 1);
del_pos = llListFindList(veclist, compare);
if(del_pos == 0){
veclist = llDeleteSubList(veclist, 0, 0);
state loop;
}
else if(length != 0){
veclist_new += llList2List(veclist, 0, 0);
veclist = llDeleteSubList(veclist, 0, 0);
state loop;
}
else{
llOwnerSay((string)veclist_new + " time= " + (string)llGetTime());
}
}
}
state loop{
state_entry(){
state default;
}
}
That as it is will return :11:01] Object: <1.000000, 2.000000, 3.000000><4.000000, 5.000000, 6.000000> time= 0.222995
_____________________
I (who is a she not a he) reserve the right to exercise selective comprehension of the OP's question at anytime. From: someone I am still around, just no longer here. See you across the aisle. Hope LL burns in hell for archiving this forum
|
|
Jesse Barnett
500,000 scoville units
Join date: 21 May 2006
Posts: 4,160
|
11-13-2006 11:25
got it and yes I am going to be late!!!!!
list veclist = [<1.0,2.0,3.0>,<4.0,5.0,6.0>,<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,
<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,
<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,<7.0,8.0,9.0>,<1.0,2.0,3.0>];
list veclist_new;
list compare;
integer del_pos;
default
{
state_entry() {
veclist = llListSort(veclist, 1, TRUE);
integer length = llGetListLength(veclist);
compare = llList2List(veclist, 1, 1);
del_pos = llListFindList(veclist, compare);
if(del_pos == 0 && length >= 2){
veclist = llDeleteSubList(veclist, 0, 0);
state loop;
}
else if(length != 0){
veclist_new += llList2List(veclist, 0, 0);
veclist = llDeleteSubList(veclist, 0, 0);
state loop;
}
else{
llOwnerSay((string)veclist_new + " time= " + (string)llGetTime());
}
}
}
state loop{
state_entry(){
state default;
}
}
returns: [11:24] Object: <1.000000, 2.000000, 3.000000><4.000000, 5.000000, 6.000000><7.000000, 8.000000, 9.000000> time= 0.291803
_____________________
I (who is a she not a he) reserve the right to exercise selective comprehension of the OP's question at anytime. From: someone I am still around, just no longer here. See you across the aisle. Hope LL burns in hell for archiving this forum
|
|
Elektra Hesse
Sexy Scripter
Join date: 10 Oct 2006
Posts: 3
|
11-13-2006 11:42
Got 0.08 / 0.09 results using this method:
list veclist = [<1.0,2.0,3.0>,<4.0,5.0,6.0>,<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,
<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,
<7.0,8.0,9.0>,<1.0,2.0,3.0>,<4.0,5.0,6.0>,<7.0,8.0,9.0>];
default
{
state_entry() {
veclist = llListSort(veclist, 1, TRUE); //sort the list first
integer i;
integer lsize = llGetListLength(veclist); //get list length
list newlist; //create a new tmp list where to store the results
string last;
for (i=0; i<lsize; i++)
{
string s = llList2String(veclist, i); //element in the list
if (s != last)
{
newlist += ; //add to the new result list
last = s; //set the last element as the current one in the tmp variable "last"
}
}
llOwnerSay((string)newlist + " | " + (string)llGetTime());
}
}
result: [11:41] Object: <1.000000, 2.000000, 3.000000><4.000000, 5.000000, 6.000000><7.000000, 8.000000, 9.000000> | 0.089429 |
|
Jesse Barnett
500,000 scoville units
Join date: 21 May 2006
Posts: 4,160
|
11-13-2006 11:52
Viva Italia!! Elektra!
_____________________
I (who is a she not a he) reserve the right to exercise selective comprehension of the OP's question at anytime. From: someone I am still around, just no longer here. See you across the aisle. Hope LL burns in hell for archiving this forum
|
|
Thanto Usitnov
Lord Byron wannabe
Join date: 4 Aug 2006
Posts: 68
|
11-13-2006 14:13
The blazingly fast algorithm Elektra Hesse posted is great, but... I just discovered a problem with my setup that might make it a moot point, I think.
So, here's the setup:
I have a series of sensors covering some volume of space without gaps (the sensors overlap somewhat)--I'm actually working on two applications of this, one for a building (this is for a group), and the other for a field (for myself, an upcoming project). The sensors go off once every 0.5 seconds. The position vectors of the objects they detect, converted to a list then converted to a string via llDumpList2String, are broadcasted through an llShout(). This will be received either by a display unit or a relay (depending on the size of the thing). The display unit is a 3-dimensional representation of the volume covered (EX: a transparent representation of a building), where the blips are individual prims linked to the display, moved according to the vector list (so blip #1 in the linkset is moved to position vector #1 in the list, and so on).
The problem I just noticed is that the radars probably won't fire simultaneously--at least, it would be kinda silly to assume that they would. For that reason, if anything is moving, it will give off multiple unique position vectors, depending on how many sensors overlap, *and* these will be given off at different times, meaning that I only have one scanned area to work with at any given time, unless I wait to compile multiple lists (which doesn't seem to be a good idea at the moment). So, even if I get rid of all duplicate vectors, the result will still be misleading.
ideally, I'd like to get the UUIDs of all things involved (accomplished via llDetectedKey(), I think), then get their positions and display accordingly, but it doesn't look like there's any way to get the position of something via its key.
another implementation detail: I'm currently considered having display units consist of multiple subassemblies of listeners and blips, one for each radar, so the listener only listens to one radar and only sets its blips accordingly. That should solve a few problems.
The potential solutions I see to this are:
1) make the detection unit one ginormous linked object using really long invisible prims (like wires... is this actually possible, by the way? the wiki entry on Link is unclear), and use an llMessageLinked() to activate all sensors simultaneously. This *should* solve the problem of delays, but it might not, because there is still presumably some fraction of a second delay due to whatever.
2) have the blips light up as soon as they are given info, and fade over time (I think I want to do this anyway, but I'm not sure whether I want to do this with a texture animation or by repeatedly setting the alpha channel)
|
|
Jesse Barnett
500,000 scoville units
Join date: 21 May 2006
Posts: 4,160
|
11-13-2006 14:27
What you are asking is definitely possible. A great example is the whole sim radar. Unfortunately that code won't ever be released.
BTW Sorry Thanto, but I guess you are using MS Word or something and probably spellchecking which is cool. God I know I have enough typos. But when you are pasting into the forum here you need to do some formatting or something. The posts are difficult to read
EIDT: NEVERMIND. I guess it is just me. Now your post is displaying correctly.
_____________________
I (who is a she not a he) reserve the right to exercise selective comprehension of the OP's question at anytime. From: someone I am still around, just no longer here. See you across the aisle. Hope LL burns in hell for archiving this forum
|
|
Elektra Hesse
Sexy Scripter
Join date: 10 Oct 2006
Posts: 3
|
11-13-2006 14:54
@Thanto hehe thank you ) i'm glad you liked the algorithm ) anyway, you can get position from a key, firing another sensor afterwards, targetted to that specific key. llSensor("", your_key_here , type, range, arc) and in sensor() event get llDetectedPos(0) ... nasty and awful, but should do... |
|
Ziggy Puff
Registered User
Join date: 15 Jul 2005
Posts: 1,143
|
11-13-2006 15:08
If these are 'real' vectors (for example, returned by a sensor), you might want to replace: if (v1 == v2) by: if (llVegMag(v2 - v1) < someArbitraryErrorMargin) Especially if you plan to be doing any math on these vectors. Float precision in SL isn't all that great, and you could easily end up with 1.0 turning into 0.99999 (or whatever) after a couple of operations on it. It might break some of the search/replace techniques discussed here, I don't know. All this is IMO, of course. If Strife disagrees, then I'm wrong Edit: Just read your last post, and it looks like you've already realized the problem with directly comparing vectors. So... if you know the max delay between 2 sensors firing, and have some idea of the max speed a target could be moving at, you could take a swag at the max error for two vectors that represent the "same position". Hope that makes sense. Or, save UUIDs along with positions, somehow. But then you can't use list sorting tricks. |
|
Jesse Barnett
500,000 scoville units
Join date: 21 May 2006
Posts: 4,160
|
11-13-2006 15:39
From: Ziggy Puff Or, save UUIDs along with positions, somehow. But then you can't use list sorting tricks. Sure you can. The sort function sorts in strides. Save the uuid first and then the vector. Sort the list by uuid and throw away the duplicates.
_____________________
I (who is a she not a he) reserve the right to exercise selective comprehension of the OP's question at anytime. From: someone I am still around, just no longer here. See you across the aisle. Hope LL burns in hell for archiving this forum
|
|
Thanto Usitnov
Lord Byron wannabe
Join date: 4 Aug 2006
Posts: 68
|
11-13-2006 15:43
I think I just figured out how to do the equivalent of getting position from UUID. In the list culling algorithm, create a list for source UUIDs paralell to the vector source list, then add an output UUID list parallel to the output vector list. Then, instead of comparing vectors, compare UUIDs, then work on both lists. Come to think of it, assuming there's only going to be an overlap of 2, I could compare the vectors and determine a velocity for that thing, assuming I knew which vector came first.
Of couse, I still have the problem of collecting the lists together in the first place from distant sensors.
I figure I'll just go the mutiple sub-assembly route now, since that seems to be the only way that will work.
|
|
Ziggy Puff
Registered User
Join date: 15 Jul 2005
Posts: 1,143
|
11-13-2006 15:50
From: Jesse Barnett Sure you can. The sort function sorts in strides. Save the uuid first and then the vector. Sort the list by uuid and throw away the duplicates. LOL. Thanks. Tells you how many times I've used that function |
