GameMaker [SOLVED] Remove Duplicates from ds_list

[Phil Strahl]

Hey, I am just wondering if there's an easy way to go through a ds_list and remove duplicate entries other than picking a candidate entry and going through the whole list looking for matches.

 

[chamaeleon]

Hey, I am just wondering if there's an easy way to go through a ds_list and remove duplicate entries other than picking a candidate entry and going through the whole list looking for matches.

Some unknowns... Is it a short list or a long list? Is it sorted? Does removal need to preserve order?

 

[Phil Strahl]

Some unknowns... Is it a short list or a long list? Is it sorted? Does removal need to preserve order?

It's a short list (usually ~10 entries max) and the order is not important, but it runs at every step.

 

[Marcus12321]

If you sort it, then you just need to check each member against the next one in the list. is x== x+1, etc...

 

[Carbiner]

What I've done in the past is this little snippet, which checks if there already is a duplicate in the list and only adds the entry if there isn't. I don't know how fast it is in comparison to other methods, and it may not be applicable in your case, anyways. My data doesn't need to be sorted, either, so that my introduce complications.

var val = numb; // Or however you get the data
if(!ds_list_find_index(list,val))
    {
    ds_list_add(list,val); // Add it only if it doesn't exist in the list already.
    }

 

[Phil Strahl]

If you sort it, then you just need to check each member against the next one in the list. is x== x+1, etc...

What I've done in the past is this little snippet, which checks if there already is a duplicate in the list and only adds the entry if there isn't. I don't know how fast it is in comparison to other methods, and it may not be applicable in your case, anyways. My data doesn't need to be sorted, either, so that my introduce complications.

var val = numb; // Or however you get the data
if(!ds_list_find_index(list,val))
    {
    ds_list_add(list,val); // Add it only if it doesn't exist in the list already.
    }

Thank you all for the replies! Yep, that could work! I just need to bench all three approaches (the two here and my own) to see which performs best!

 

[chamaeleon]

Thank you all for the replies! Yep, that could work! I just need to bench all three approaches (the two here and my own) to see which performs best!

A naive approach for a list of size 10 should be able to do about 100,000 iterations of removing duplicates in a second.
Edit: About 10 seconds for 1,000,000 iterations for a VM build and around 4 seconds for a YYC build.

 

[Phil Strahl]

Thanks! I guess I should be fine then