1. #1

    Registered
    18/09/03
    Location
    ingelmunster
    Posts
    2,829
    iTrader
    16 (100%)
    Mentioned
    0 Post(s)
    Reputation
    0/6

    JS/CSS: efficient dubbele woorden verwijderen uit array

    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.
    no votes  

  2. #2
    Smoerf's Avatar
    Registered
    28/07/04
    Location
    Wevelgem
    Posts
    552
    iTrader
    0
    Mentioned
    0 Post(s)
    Reputation
    0/0
    zet die woorden als key, opgelost
    no votes  

  3. #3
    L0|2|23's Avatar
    Registered
    09/08/02
    Location
    Mortsel
    Posts
    605
    iTrader
    0
    Mentioned
    0 Post(s)
    Reputation
    0/0
    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(n), en als het allemaal objecten/functies zijn kan het ook in O(n) (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
    Last edited by L0|2|23; 16-08-2007 at 22:18.
    no votes  

  4. #4
    L0|2|23's Avatar
    Registered
    09/08/02
    Location
    Mortsel
    Posts
    605
    iTrader
    0
    Mentioned
    0 Post(s)
    Reputation
    0/0
    Deze thread was de aanzet om een volledige Array.prototype.unique() te schrijven die complexiteit O(n) 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);
    no votes  

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Log in

Log in