Quel est le grand rang d'O pour JavaScript lorsqu'il est utilisé comme un hash?
Quel est le grand O pour l'accès au tableau de JavaScript lorsqu'il est utilisé comme un hash?
Par exemple,
var x= []; for(var i=0; i<100000; i++){ x[i.toString()+'a'] = 123; // using string to illustrate x[alpha] } alert(x['9999a']); // linear search? On peut espérer que les moteurs JS n'utiliseront pas une recherche linéaire en interne O (n), mais est-ce sûr?
- Comment Gmail gère / renvoie-t-il dans JavaScript riche?
- Ajouter un fragment à l'URL sans provoquer de redirection?
- Existe-t-il une bonne implémentation hash (code / table) ici?
- Existe-t-il un type de fonction de code hash en JavaScript?
- Existe-t-il des implémentations de javascript SHA-256 qui sont généralement considérées comme fiables?
- Javascript location.hash rafraichissant dans IE
- Performance de la recherche de clé dans l'objet JavaScript
- Comment est implémentée une carte hash JavaScript?
- Parsing URL hash / fragment identifier avec JavaScript
- Comment puis-je mettre à jour window.location.hash sans sauter le document?
L'accès aux propriétés de l'objet et aux éléments du tableau dans JavaScript est syntaxiquement supposé être effectué en temps constant : O (1). Les caractéristiques de performance ne sont pas garanties dans la spécification ECMAScript, mais tous les moteurs JavaScript modernes récupèrent les propriétés de l'objet en temps constant.
Voici un exemple simple montrant comment les temps d'accès augmentent lorsque le conteneur est x1000 fois plus grand:
var largeObject = {}; var smallObject = {}; var x, i; for (i = 0; i < 1000000; i++) { largeObject['a' + i] = i; } for (i = 0; i < 1000; i++) { smallObject['b' + i] = i; } console.time('10k Accesses from largeObject'); for (i = 0; i < 10000; i++) x = largeObject['a' + (i % 1000000)]; console.timeEnd('10k Accesses from largeObject'); console.time('10k Accesses from smallObject'); for (i = 0; i < 10000; i++) x = largeObject['a' + (i % 1000)]; console.timeEnd('10k Accesses from smallObject');
Résultats dans Firebug, Firefox 3.6.10 (Mac OS X 10.6.4 – 2.93Ghz Intel Core 2 Duo):
10k Accesses from largeObject: 22ms 10k Accesses from smallObject: 19ms
Résultats dans Chrome Dev Tools 6.0.472:
10k Accesses from largeObject: 15ms 10k Accesses from smallObject: 15ms
Internet Explorer 8.0.7600 avec Firebug Lite sous Windows 7
10k Accesses from largeObject: 250ms 10k Accesses from smallObject: 219ms
Tout d'abord, les Arrays sont en fait des hachis . Toujours . C'est pourquoi x[5] === x["5"] :
var x = []; x[5] = 10; alert( x[5] === x["5"] ); // true
Les objets sont des hashes et les Arrays ne sont que des objets spéciaux. Si vous souhaitez utiliser des hachages généraux, passez pour Objets. Les «tableaux associatifs» en Javascript sont des objets. Les tableaux sont pour les données indexées numériquement. Les tableaux possèdent une propriété de length et des méthodes similaires à celles du tableau comme push , pop , sort , etc., ce qui n'a aucun sens à utiliser sur les hachis.
En ce qui concerne le grand O pour la recherche dans Objets: dépend de l'implémentation .
Probablement les 2 meilleures choses que vous pouvez faire pour:
-
Vérifiez le code source de certaines implémentations de navigateur
-
Faites un benchmark pour le grand n et faites votre conclusion
La partie connexe de la spécification linguistique :
4.3.3 objet
Un objet est une collection de propriétés et possède un seul prototype d'objet.
8.6.2 Propriétés et méthodes internes de l'objet
Les objets Array ont une implémentation légèrement différente de la méthode interne [[DefineOwnProperty]]. Les objets Array apportent un traitement spécial à une certaine classe de noms de propriété.