Flash as3 How do I remove duplicates in an array?

Hi I just have an array o开发者_如何学Cf names (strings) in flash, and I want to make sure that any duplicates from the array are removed, or at least that a function is performed only once per reocurring value in the array.

Many ways. You can sort the array and iterate over it ignoring entries that match the previous iteration. Or you can use indexOf() to search for duplicates. Or you can take one pass over the array, build a dictionary keyed on the strings (and just ignore keys that already have an entry).

Here is the Dictionary way, memory cost of 1 boolean per unique entry, easy on memory for when you expect a lot of dupes, and fast. If you have relatively few dupes, the sort + culling of consecutive dupes is probably more efficient

import flash.utils.Dictionary;

var array:Array = ["harry","potter","ron","harry","snape","ginny","ron"];
var dict:Dictionary = new Dictionary();

for (var i:int = array.length-1; i>=0; --i)
{
    var str:String = array[i] as String;
    trace(str);
    if (!dict[str])
    {
        dict[str] = true;
    }
    else
    {
        array.splice(i,1);
    }
}

dict = null;


trace(array);

Here's a sorting way, but note: THIS DOES NOT PRESERVE ORDER! You didn't say if that matters. But because it's using quicksort, it does tend to have O(N log N) performance plus the one extra pass, unless of course your data is a pathological case.

var array:Array = ["harry","potter","ron","harry","ron","snape","ginny","ron"];

array.sort();
trace(array);

for (var i:int = array.length-1; i>0; --i)
{
    if (array[i]===array[i-1])
    {
        array.splice(i,1);
    }
}


trace(array);

In addition to not specifying whether order matters, you did not say if it matters which of the dupes is left: the one at the lowest index, or the last one found. If that matters, you will need to re-order my dictionary example to run in the opposite direction. I started at the end because that makes it OK to do a splice without invalidating the loop count (i.e. by changing the array.length during the looping) If order matters, loop in the usual forward direction and copy out the first occurrence of each string to a new array, or modify the loop counter like this. This is probably the technique I'd use, because it preserves order and keeps the first-encountered instance of each string:

import flash.utils.Dictionary;

var array:Array = ["harry","potter","ron","harry","snape","ginny","ron"];
var dict:Dictionary = new Dictionary();

var len:int = array.length;
for (var i:int = 0; i<len; ++i)
{
    var str:String = array[i] as String;
    if (!dict[str])
    {
        dict[str] = true;
    }
    else
    {
        array.splice(i,1);
        i--; len--;
    }
}

dict = null;


trace(array);

More cat skinning:

var a:Array = ["Tom", "John", "Susan", "Marie", "Tom", "John", "Tom", "Eva"];
a.sort();
var i:int = 0;
while(i < a.length) {
    while(i < a.length+1 && a[i] == a[i+1]) {
        a.splice(i, 1);
    }
    i++;
}

Good answers!

I've checked a few of them, and they have worse results in contrast to mine. Example:

const origin: Vector.<String> = Vector.<String>(["a", "c", "d", "c", "b", "a", "e", "b", "a"]);

function getUniqueVector(origin: Vector.<String>): Vector.<String> {
    const n: uint = origin.length;
    var res: Vector.<String> = new Vector.<String>();
    var i: int = 0;

    while(i < n) {
        var el: String = origin[i];
        if(res.indexOf(el) == -1) res.push(el);
        i += 1;
    }

    return res;
}

trace(getUniqueVector(origin)); // unique elements vector

Statistics with my data:

Dict approach: 8946ms, 8718ms, 8936ms

Obj approach: 8800ms, 8809ms, 8769ms

My old approach: 8723ms, 8599ms, 8700ms

This approach: 6771ms, 6867ms, 6706ms

Update 02 / JUL / 2019

Worth noting that for better performance, to create the object, and set each pushed value there as the key for O(1) complexity retrieving, so results will be a bit better.

But Flash is dead, and probably ActionScript, so this was a funeral speech :(

This is one way to do it, I'm sure there are others.

function removeDuplicate(sourceArray:Array) : void
{
    for (var i:int = 0; i < sourceArray.length - 1; i++)
    {
        for (var j:int = i + 1; j < sourceArray.length; j++)
        {
                if (sourceArray[i] === sourceArray[j])
                {   
                     // Remove duplicated element and decrease j index.
                     sourceArray.splice(j--, 1);
                }
        }
    }
}

Here's another way to do it, possibly a little nicer to look at:

var removeList:Array = [];

// loop over every item in the original array
for each (var item:* in array) {
    // loop over every item again, checking for duplicates
    for each (var other:* in array) {
        // if two items that aren't the same item are equal and `other` doesn't
        // exist in the remove list, then cache it for later removal.
        if (item == other && item !== other && removeList.indexOf(other) == -1)
            removeList.push(other);
    }
}

// next, loop over the cached remove list and remove 'selected' items for removal
for each (var remove:* in removeList) 
    array.splice(array.indexOf(remove), 1);

This probably isn't the most performant way of doing it, @prototypical's method is probably much more efficient, but it's the theory that you asked for :)

I voted for Adam's option, but then I found this, and it looks to me this could be better performance wise still?

  for (var i:uint = array.length; i > 0; i--){
     if (array.indexOf(array[i-1]) != i-1){
        array.splice(i-1,1);
     }
  }     

The idea here is that you loop backwards through the array, and since indexOf gives you the first occurring index, you can check the found index with the current index(i) and remove if not the same.

Here is a more elegant way of removing duplicates:

var items:Vector.<String> = Vector.<String>(['tortoise', 'cat', 'dog', 'bunny', 'dog', 'cat', 'bunny', 'lion']);

var uniqueItems:Vector.<String> = items.filter(function(item:String, index:int, vector:Vector.<String>):Boolean {
    return index==0?true:(vector.lastIndexOf(item, index-1) == -1);
});

Same approach for an array:

var items:Array = ['tortoise', 'cat', 'dog', 'bunny', 'dog', 'cat', 'bunny', 'lion'];

var uniqueItems:Array = items.filter(function(item:String, index:int, array:Array):Boolean {
        return index==0?true:(array.lastIndexOf(item, index-1) == -1);
    });

would @prototypical s response not give issues if the sourceArray[i] matches sourceArray[j] more than once because the length of sourceArray would be shorter if an element has been .splice()d out of it?

I've rewritten this method to count from the end so that this doesn't happen

for (var i:int = sourceArray.length - 2; i >= 0; --i) 
{
    for (var j:int = sourceArray.length - 1; j > i; --j)
    {
        trace(i, j);
        if (sourceArray[j] === sourceArray[i]) sourceArray.splice(j, 1);
    }
}

function removeDuplicateElement(_arr:Array):Array{
   //set new Dictionary
   var lDic:Dictionary = new Dictionary();
   for each(var thisElement:* in _arr){
      //All values of duplicate entries will be overwritten
      lDic[thisElement] = true;
   }
   _arr = [];
   for(var lKey:* in lDic){
     _arr.push(lKey);
  }
  return _arr;
}