Archief - JS/CSS: efficient dubbele woorden verwijderen uit array

MangleR · 16 aug 2007

ik ben op zoek naar een kort scriptje die dubbele woorden van in een array kan halen.

bv ik heb een array
test()
en daarin zitten 10 woorden. Maar nu zijn er bv 4 dezelfde, dus er moeten er 3 uit, zodat ik geen dubbele heb.

mocht iemand zo een sciptje hebben, dan mag hij dat hier gerust es posten.
waarvoor dank.

Smoerf · 16 aug 2007

zet die woorden als key, opgelost

L0|2|23 · 16 aug 2007

Een gewone array uniek maken zou O(n²) zijn. Smoerfs oplossing is O(2n), maar garandeert niet dat de volgorde van de elementen behouden blijft. Gesorteerde arrays kan je op O

, en als het allemaal objecten/functies zijn kan het ook in O

(met een attribute hack).

Hier is een implementatie van Smoerfs voorstel:

Code:

// Alleen voor Strings.
// Voorwaarde is dat er niet geknoeid is geweest met Object.prototype.
function unique(array) {
    var volgorde = {}, unique = new Array(array.length);
    for(var i=array.length-1; i>-1; --i)
        volgorde[array[i]] = i;
    for(var string in volgorde)
        unique[volgorde[string]] = string;
    return unique;
}

Normaal gezien is de volgorde van keys in volgorde van aanmaking, maar dat wordt niet gegarandeerd en ik herinner me vaag dat enkele browsers het willekeurig doen (zoals Opera). Hier is een failsafe algoritme dat trager is maar zeker werkt:

Code:

function unique(array) {
    for(var unique=[], length=array.length, i=0; i<length; ++i) {
        for(var e=array[i], r=1, j=unique.length-1; j>-1 && (r=e!==unique[j]); --j);
        if(r) unique.push(e);
    }
    return unique;
}

EDIT Het is wel mogelijk om met Smoerfs voorstel de volgorde te bewaren, maar vraagt nog iets meer werk dan hetgeen ik hierboven geschreven heb

L0|2|23 · 16 aug 2007

Deze thread was de aanzet om een volledige Array.prototype.unique() te schrijven die complexiteit O

heeft voor niet gesorteerde arrays van (string,number)s of van (object,function)s. Als de array nog andere types bevat of een kruising tussen de voorgaande twee mixes valt het terug op een gewoon O(n²) algoritme.

Code:

Array.prototype.unique =
function() {
    var opt1 = 1,  opt2   = 1,
        seq  = {}, unique = [];
    // Heuristic approach for making mixed string|number or object|function arrays unique.
    for(var e, type, length=this.length, i=0; i<length && (opt1 || opt2); ++i) {
        if(/string|number/.test(type=typeof (e=this[i]))) {
            opt2 = 0;
            seq[type+e] = i;
        }
        else if(/object|function/.test(type)) {
            opt1 = 0;
            if(!e._inc) {
                e._inc = 1;
                unique.push(e);
            }
        }
        else opt1 = opt2 = 0;
    }
    // Clear appended _inc, regardless of successful optimization.
    for(var i=unique.length-1; i>-1; --i)
        unique[i]._inc = undefined;
    // Reconstruct mixed string|number array.
    if(opt1) {
        unique = [];
        var sparse = new Array(length);
        for(var key in seq)
            sparse[seq[key]] = key.substr(0,6)==='number'?1*key.substr(6):key.substr(6);
        for(var length=sparse.length, i=0; i<length; ++i)
            if(e=sparse[i])
                unique.push(e);
    }
    // Optimization failed, resort to an O(n²/2) method.
    else if(!opt2) {
        unique = [];
        for(var i=0; i<length; ++i) {
            for(var r=1, e=this[i], j=unique.length-1; j>-1 && (r=e!==unique[j]); --j);
            if(r) unique.push(e);
        }
    }
    return unique;
};

Copy-paste code en gebruiken doe je zo:

Code:

var a = [1,2,3,3,'hello','world','hello'];
a = a.unique();
alert(a);

Archief - JS/CSS: efficient dubbele woorden verwijderen uit array

MangleR

Legacy Member

Smoerf

Legacy Member

L0|2|23

Legacy Member

L0|2|23

Legacy Member