-
16-08-2007, 17:08 #1Member
- 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
-
-
16-08-2007, 17:22 #2no votes
-
16-08-2007, 20:37 #3
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:
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:// 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; }
EDIT Het is wel mogelijk om met Smoerfs voorstel de volgorde te bewaren, maar vraagt nog iets meer werk dan hetgeen ik hierboven geschreven hebCode: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; }
Last edited by L0|2|23; 16-08-2007 at 22:18.
no votes
-
16-08-2007, 23:11 #4
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.
Copy-paste code en gebruiken doe je zo: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; };
Code:var a = [1,2,3,3,'hello','world','hello']; a = a.unique(); alert(a);
no votes
