Je suis intéressé par la complexité asymptotique (Big O) de l'opération Groupby sur des jeux de données non annexés. Quelle est la complexité de l'algorithme le plus connu et quelle est la complexité des algorithmes que les serveurs SQL et Linq utilisent?
3 Réponses :
Ignorer la base SQL que le groupe en fonctionne, lorsqu'il est présenté au groupe par opération elle-même, la complexité n'est que O (n) car les données sont numérisées par rangées et agrégées en une seule passe. Il échoue linéairement à n (la taille de l'ensemble de données).
Lorsque le groupe par est ajouté à une requête complexe, les changements d'équation, O (n) devient la limite supérieure que le groupe par ajoute à l'équation globale; Il pourrait être moins que si la requête complexe interne est telle que dans la résolution de la requête de base, les données sont déjà triées.
Et comme il n'y a pas d'index, lorsque les données sont triées, vous avez déjà dépensé O (n log n) le trier. (Nitpick: Il échoue linéairement à N, c'est-à-dire à la taille de l'ensemble de données, pas à la taille de n)
Désolé mais c'est faux. Lorsque vous êtes itération du jeu de données, vous devez décider de quel groupe vous souhaitez mettre en ligne / objet donné. Je ne peux pas voir comment peut-on faire une sélection de groupe en temps constant.
@Jak - SQL Server Strever STREVET Agrégate fonctionne en temps quasi linéaire à N, de sorte que même si le temps total est O (n) + o (n log n journal), il est de complexité O (n)
O (n) n'est pas une durée constante, son temps linéaire. O (1) est une durée constante.
@sixlettervariables: je sais. Pour effectuer en groupe, vous devez passer par tous les articles (c'est O (n)) et pour chaque élément décider de quel groupe il appartient (ce n'est pas O (1)).
Certes, si vous concevez un mécanisme de sélection de groupe plus compliqué que O (1), il ajoutera à la complexité. Cependant, disent que le groupement est sur des entiers, le regroupement est certainement O (1). Si les groupements sont des clés de chaîne, c'est O (k) où K est la longueur de chaîne maximale que nous dirions est toujours O (1). Ai-je manqué quelle partie que vous dites est> O (1)?
@sixlettervariables: Je discute que tous les mécanismes de sélection du groupe sont dans le pire des cas plus complexes que O (1). Je ne vois pas comment peut regrouper sur des entiers réalisés en temps constant (et espace).
@sixlettervariables Si je pouvais le long de ce commentaire, je le ferais. Vous ne pouvez pas être correct qu'un algorithme de comparaison de chaîne défini comme O (k) est réductable à O (1). Si c'était le cas, alors le tri radiologique a une complexité de O (n) - en réalité, c'est O (nk) car, dans la limite des chaînes, la longueur de la clé de comparaison peut varier d'ensemble des ensembles de données ( et cette variation impacte directement le temps de calcul de manière bien définie et prévisible).
@Legatou: Et je suis d'accord ... j'aurais dû dire que les comparaisons sont O (k) et O (1) .
À propos de Linq, je suppose que vous voulez savoir sur le groupe LINQ-TO-Object par complexité ( énumérable.groupby ).
Vérification de la mise en œuvre avec ILSPY, il me semble que c'est O (n). (La série 4SNET Framework 4)
Il énumère la collection source une fois. Pour chaque élément, il calcule sa clé de regroupement. Ensuite, il vérifie s'il a déjà la clé dans une mappage de hashtable aux listes d'éléments, ajoutant la clé à la haquetable s'il manque. Ensuite, il ajoute l'élément à la liste d'entrée correspondante dans la haquetable.
+1, bien que la peine de noter que les opérations de hashtable ne sont que attendues amortize O (1); Le pire des cas est O (n) qui fait le pire cas de Groupby O (n ^ 2), bien que peu probable dans la pratique. Il convient également de noter que certaines implémentations de table de hachage peuvent accéder à plusieurs éléments en moyenne tout en étant toujours (1) car le nombre moyen d'éléments accédés ne se développe pas avec N, bien que je pense que .NET utilise un facteur de charge de 1 en fait seulement 1 élément en moyenne.
Le regroupement peut être fait en une seule passe (N complexité) sur des lignes triées (N log (n) complexité) de sorte que la complexité du groupe par est N log (n) où n est le nombre de lignes. S'il y a des indices pour chaque colonne utilisée dans le groupe par déclaration, le tri n'est pas nécessaire et la complexité est N.
Notez que le groupe par SQL et LINQ sont deux opérations très différentes.