Je vais avoir un tableau de symboles (256 symboles ascii) et un tableau de leurs fréquences (certains des symboles apperent zéro fois) .Est-il préférable complexité sage d'utiliser le tri de comptage pour le tri et ce que soultion prendra plus de lignes de code (le code sera écrit en assemblée, tasm).Dois-je utiliser le tri par comptage ou toute autre alternative pour trier les fréquences des symboles de complexité
Le tri par comptage doit être excellent si vos entrées sont longues (chaînes ou tampons significativement plus longs que 256).
Serait-il préférable complexité sage d'utiliser sorte de comptage pour le tri
Il est certainement simple à mettre en œuvre, et a O (1) la complexité. Si de grandes entrées sont possibles ou communes, le tri par comptage est très bon. Cependant, si les petites entrées sont communes, le tri par comptage doit encore passer du temps à effacer tout le tableau de comptage et à le scanner à nouveau, et ce coût n'est pas réduit pour les petites entrées. En fonction de la CPU, (p. Ex. Memset rapide pour effacer une matrice de comptage), le tri avec 256 symboles peut être bon pour des entrées aussi petites que 64. Vous mentionnez TASM, donc vous parlez spécifiquement de x86, et probablement x86-16. Moderne x86 a memset très rapide, en utilisant soit les magasins SSE ou rep stosd. (256 ou 512 octets (pour les compteurs 16 bits) est assez grand que l'utilisation de rep stos n'est pas une idée terrible, le temps de démarrage est principalement amorti, donc proche de la même vitesse qu'une boucle vectorielle.)
, Je ne sais pas si qsort ou mergesort feraient mieux. En dessous de 16 éléments (et en tant que base de qsort/merge-sort), vous voulez probablement InsertionSort pour les performances. Sur les x86 modernes avec SSSE3 (pour pshufb), vous pouvez utiliser SSE2 pminub/pmaxub comme des comparateurs dans un réseau de tri avec granularité des octets (et oui, ces instructions fonctionnent en mode 16 bits). Voir Using SIMD Registers and Instructions to Enable Instruction-Level Parallelism in Sorting Algorithms pour les éléments 32 bits, ainsi que Fast in-register sort of bytes?.
Ou utilisez SIMD pour un tri partiel, il y a donc moins d'échanges à faire avec InsertionSort. Peut-être juste un peu de charge, pminub/pmaxub, et stocker, sans beaucoup ou pas de brassage.
et quelle solution prendra plus de lignes de code
En asm, les lignes de code source est la mesure la moins utile. (Toutes les lignes ne se regroupent pas en instructions, certaines sont des étiquettes ou des directives).
Le nombre d'instructions est parfois important, mais certaines instructions sont plus lentes que d'autres, et la façon dont vous les commandez dépend de la sortie de l'autre.
Si vous ne vous souciez pas de la performance, mais plutôt de la taille du code, vous devez regarder le nombre d'octets du code machine. Les instructions x86 sont de longueur variable.
Si vous vous souciez uniquement de la taille du code et non de la performance, vous pouvez envisager le tri à bulles ou le tri par sauts. (Sans le contrôle de départ, il suffit de boucler les temps max). Voir un hilarante-lent JumpDown sort in 19-bytes of x86-32 machine code.Avec seulement quelques octets de code supplémentaires, il pourrait échanger sans utiliser xchg -with-mem (préfixe implicite lock). Une implémentation de tri à bulles plus "normale" ressemble à like this (TASM pour les entiers de 8 bits).
Mais vous pouvez aussi mettre en œuvre Insertion Sort avec seulement quelques octets de code, et il effectue généralement bien (par rapport à d'autres O (n^2) des algorithmes comme bulle ou sélection)