Flash as3 How do I remove duplicates in an array?

2019-01-19 20:43发布

问题:

Hi I just have an array of 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.

回答1:

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++;
}


回答2:

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);


回答3:

Good answers!

I've checked a few of them, and have worse results in contrast to my. It's quite simple:

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



回答4:

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);
                }
        }
    }
}


回答5:

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 :)



回答6:

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.



回答7:

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);
    }
}


回答8:

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);
    });


回答9:

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;
}