Est-ce que l'itération Speed à travers une matrice (ou liste, LinkedList, Dictionary ECT) dépend du type de données?
exemple: Un tableau de 10 bools v / s Un tableau de 10 entiers?
3 Réponses :
Oui, le type de données est important. Cela n'a rien à voir avec l'itération; Il a tout ce qui concerne les types de données.
Types de valeur forte> p> AN boxe strong> p> Si vous itérez une collection, il existe également la possibilité que vous ayez du type de changement. Par exemple: P> int code> est de 4 octets de longueur. Un décimal code> est de 16 octets de longueur. Ainsi, un décimal code> est 4 fois plus grand qu'un int code>. Chaque fois que vous récupérez une valeur de la matrice, la valeur de cette valeur est copiée. Dans le cas d'un décimal code> al 16 octets sont copiés. (En cas de type de référence, la référence est copiée, normalement 4 ou 8 octets). Copier plus d'octets va simplement ralentir l'itération. P> foreach(Person p in new object[] { ... })
....
En fait, lorsque vous avez une liste
@Chibueze: Où dois-je dire dans mon texte qu'une décimale est la boxe ou la boîte de passage?
+1 pour les captures d'écran. Votre point clé est que les données sont copiées lors de l'itération et que la copie de ces données créera une variation de temps. De plus, vous forcez la boxe et la boîte de consigne qui n'est pas la question de la question. La question pose spécifiquement de l'itération à travers des tableaux ou des collections. Ce n'est pas la manière dont les collections telles que la liste sont implémentées en interne.
Je ne parle pas de la façon dont la collection travaille en interne. Je parlais de la façon dont vous avez itérus à travers une collection. Et oui, je force cette situation dans mes exemples, car je vois ces types d'itérations à plusieurs reprises (avec la boxe, la boîteboxing, la coulée, etc.)
En réalité, forcer la boxe et le non-cas0 est inutile et doivent être informés dans un scénario de vie réel.
@Chibueze: vrai, mais ils ne peuvent pas toujours être évités. Par exemple, à l'aide d'une collection de basesyypes (c.-à-d. personne , qui contiennent des instances différentes de différents types hérités (c.-à-d. Employeur et employé ). Ou un Liste avec une interface (c.-à-d. icomparable ) et différentes implémentations de celui-ci ( int et décimal ).
Exécutez le code ci-dessous si vous le souhaitez, mais voici une comparaison rapide. Tout ce que cela fait est itérer sur le tableau / liste et définir une variable TEMP à la valeur de cet index.
Notez que la performance int a pris un coup de contact Maintenant ... aucune idée de pourquoi ... mais cela se produit sur des courses répétées aussi ...
La mesure de la mesure est de l'art. Il semble que INT64 prend plus de temps qu'un int32, mais autant de temps que l'INT. Ce n'est pas correct. Un Int est un alias pour INT32 et devrait fonctionner également rapidement.
Eh bien, il semble que cela fait :) J'ai mis à jour le code et la capture d'écran, les numéros sont à peu près les mêmes. Notez qu'un millisecondes compte 10 000 ticks, mais les chiffres que je vois dans la sortie ne semblent pas très précis. Même dans ce cas, cela représente un million d'itérations, donc à la fin, cela n'a pas d'importance.
Plus vous excluez les itérations du test, les choses plus courantes que vous excluez. Un peu de conseils pour la prochaine fois: 1) exécutez toujours un test d'abord (une seule itération) sans mesure de temps. Au cours de ces itérations, des assemblages pourraient être chargés (ce qui aurait pu monter le test réel). 2) Définissez la priorité de votre processus et de votre filetage à la valeur la plus élevée, empêchant ainsi le contexte autant que possible, entrave les testsultats.
Ou vous pouvez faire un traitement statistique des données au lieu de s'appuyer sur des valeurs moyennes ou du résultat de grandes itérations, comme le calcul des intervalles de confiance.
Martin: Suggestions suivies, je ne peux pas dire que les résultats diffèrent :) Caian: C'est pourquoi le petit poisson ne devrait pas nager avec les requins ... depuis un certain temps depuis UNI, et nous n'avons pas fait d'intervalles de confiance (ou du moins , je ne m'en souviens pas :)
La réponse simple est En effet, la mise en œuvre des génériques .NET est faite de manière que c'est Boxe / Unboxing est évitée lors de l'utilisation Types de valeur mais pas dans les arraylistes. Par exemple, une liste Voir comparaison entre Décider lequel utiliser entre Liste Liste hashset code> et . p> list code> à l'aide de chaînes et d'objets Liste code>, linkedlist code>, Dictionnaire code>, hashset code>, etc. " Vous faites un grand nombre de itérations em> consiste principalement à comprendre comment ils sont stockés et leurs complexités d'exécution. Vous trouverez ci-dessous une liste des complexités de la mise en œuvre et de l'indexation asymptotique / de l'itération de certaines des génériques .NET Generics: p> Mise en œuvre interne / Complexités de temps asymptotiques pour .NET Generics h3>
+------------------+---------------------------------------+-------------------------+-------------+
| | | Item[i] | |
| Name | Internal Implementation |------------+------------| Iteration |
| | | Avg. Case | Worst Case | |
+------------------+---------------------------------------+------------+------------+-------------+
| List | Array | O(1) | O(1) | O(n) |
| LinkedList | Doubly Linked List | O(n) | O(n) | O(n) |
| Dictionary | Hashtable with links to another array | O(1) | O(n) | O(n) |
| HashSet | Hashtable with links to another array | O(1) | O(n) | O(n) |
| SortedDictionary | Red-black tree | O(log n) | O(log n) | O(n) |
| SortedList | Array | O(1) | O(n) | O(n) |
| SortedSet | Red-black tree | O(n) | O(n) | O(n) |
+------------------+---------------------------------------+------------+------------+-------------+
Une réponse beauté, mais je ne pense pas que vous avez répondu à la vraie question. Je pense d'abord que votre première ligne devrait être: "Non pour les types de référence et oui pour les types de valeur", car la question est en bref: "La vitesse d'itération à travers une matrice dépend du type de données". Il ne demande pas des différences de types de collecte. En outre, vous combinez le élément [i] et trouver (i) qui sont des opérations totalement différentes. Dans un tableau élément [i] est une opération O (1), mais trouve (i) est une opération O (n).
Non. En fait, cela compte pour les types de référence mais pas pour les types de valeur et non l'inverse. Voir remarque MSDN . Quant à l'article [i] / élément trouve le titre, peut-être qu'il est ambigu, mais il n'est pas destiné à signifier la même chose que la liste
S'il vous plaît répondre à la première moitié de mon commentaire.
Et votre argument est que le détail supplémentaire était inutile ou quoi?
En outre, vous avez mentionné dans votre réponse que le casting prend du temps alors pourquoi dire non pour les types de référence?
Oui, le casting prend du temps pour les types de référence et les types de valeurs. Mon café ne fonctionnait pas. Il devrait être oui + oui, selon la situation. Sans casting et sans (ONU) Boxing, il aurait été non pour les types de référence, oui pour les types de valeur.
Essayez-le et vous le découvrirez.
@ERIFLIPPERT Au moins, vous devriez lui dire comment essayer? Vous pensez qu'il est un programmeur principal (ou au moins avec 3-4 ans d'expérience dans la programmation professionnelle), n'est-ce pas?
@Kingking: Si l'OP est incapable d'écrire un programme qui itière à travers deux tableaux, qu'est-ce que cela importe à quelle vitesse le programme qu'ils ne peuvent pas écrire est? Ils ne peuvent pas l'écrire. (Cela dit, il peut être difficile d'écrire un point de repère correct; cela fera l'objet d'une série d'articles par moi à venir bientôt; regardez mon blog pour plus de détails.)
Mon rant standard sur la raison pour laquelle vous ne devriez pas poser à cette question sur Stackoverflow est ici: Ericlippert.com / 2012/12/17 / Performance-Rant
J'ai juste pensé à tester toute chose liée à la vitesse de la performance, un débutant se sentirait mal à l'aise, car le problème principal est de mettre en œuvre un programme de référence, content de regarder votre prochain prochain article d'articles, est votre blog ericlippert.com?
@Kingking: Oui. Maintenant, cela dit, la leçon clé ici est que Les différences de performance ne sont intéressantes que si l'utilisateur peut remarquer la différence entre la bonne et la mauvaise performance . Donc, écrivez un programme des deux manières, courez-la des deux manières - pourriez-vous dire la différence? Sinon, alors peu importe que l'on est plus rapide! Peu importe que la licorne invisible est plus jolie. ]
@ERIFLIPPERT CORRECT CORRECT, j'utilise habituellement le tri de sélection pour le tri de petits tableaux (bien sûr dans un autre environnement, pas In.net, où je peux utiliser une méthode de tri intégrée), ne vous souciez pas d'autres algorithmes de tri efficaces comme rapide Trier ou fusionner Trier. Cependant, lorsque le nombre de calculs est important, la différence entre les méthodes bonnes et mauvaises sera visible et perceptible. Le PO peut vouloir signifier la comparaison de performance dans un tel cas.
Comme vous l'avez dit, je pouvais écrire un programme simple pour le tester, mais je ne saurais pas tester les résultats de manière efficace (le mieux que je puisse penser est itérant à travers d'énormes tableaux avec une montre d'arrêt dans ma main) Je suis également conscient que Ces différences ne peuvent pas vraiment être remarquées, alors pourquoi vous déranger de me demander? Eh bien, je suis juste curieux c'est tout ...
@ user2320115 Utilisez une programmation chronomètre
À mon avis, cette question est trop grosse pour être recouverte correctement et complètement.