J'ai une source de données avec un champ de type flotteur. Une collection de ces structures doit être triée par la valeur du flotteur. Existe-t-il une implémentation de tri radix pour cela.
S'il n'y a pas, y a-t-il un moyen rapide d'accéder à l'exposant, au signe et à la mantissa. Parce que si vous triez d'abord les flotteurs sur Mantissa, Exponent et sur Exponent la dernière fois. Vous triez des flotteurs dans O (N).
5 Réponses :
Je pense que votre meilleur pari si les valeurs ne sont pas trop proches et une exigence de précision raisonnable, vous pouvez simplement utiliser les chiffres réels du flotteur avant et après le point décimal pour faire le tri.
Par exemple, vous pouvez simplement utiliser les 4 premières décimales (qu'ils soient 0 ou non) pour faire le tri.
J'étais intéressé par ce sujet, alors je me suis assis et je l'ai mis en œuvre (en utilisant Cette implémentation conservatrice très rapide et de mémoire ). Je lis aussi Celui-ci (merci Celion ) et a découvert que vous n'avez même pas besoin de diviser les flotteurs en mantissa et à l'exposant pour le trier. Vous devez juste prendre les bits un à un et effectuer un type INT. Il vous suffit de vous soucier des valeurs négatives, qui doivent être inversement placées devant les positifs à la fin de l'algorithme (je l'ai fait en une étape avec la dernière itération de l'algorithme pour économiser du temps de processeur). Il est légèrement plus lent que la sorte d'int Radix, en raison de la copie du réseau à Le début et la fin de la fonction, où les floattes sont copiés dans le sens du sens à l'intérieur et à l'arrière. Toute la fonction est néanmoins de nouveau o (n). Dans tous les cas beaucoup plus rapidement que le tri 3 fois de suite comme vous avez proposé. Je ne vois plus beaucoup de place à des optimisations, mais si quelqu'un le fait: N'hésitez pas à me le dire. P> Pour trier les modifications descendantes de cette ligne à la fin: P> RadixSort: 00:00:00.0012944
Linq OrderBy: 00:00:00.0072271
Array.Sort: 00:00:00.0002979
Au fait que l'algorithme est aussi utilisable pour Double Tableaux, il suffit de remplacer float par double , int par par < Code> long , TOINT32 par TOINT64 , .TOSOSSLEL par .TOdouble et modifier int bitlength = 32; à 64.
Bien fait! Je ne m'attendais pas à ce que quelqu'un puisse mettre en œuvre ce problème. Très beau code et analyse. :RÉ
@Philip DauBmeier Pouvez-vous vérifier la version améliorée de mes performances?
Il y a une belle explication de la manière d'exécuter Radix Trier sur des flotteurs ici: http://www.codercorner.com/radixsortrevisited.htm
Si toutes vos valeurs sont positives, vous pouvez vous éloigner de la représentation binaire; Le lien explique comment gérer les valeurs négatives.
Vous pouvez utiliser un bloc danger à memcpy ou alias A float * à un uint * pour extraire les bits.
En effectuant des tableaux de moulage et d'échange de fantaisie au lieu de copier cette version est 2 fois plus rapide pour les numéros de 10 m en tant qu'intrigé de Philip Daubmereiers avec la longueur grouplée définie sur 8. Il est 3 fois plus rapide comme Array.sort pour cette faille.
Radix trite conceptuellement conceptuellement pour INTS, ou au moins des chiffres dans un système décimal? Rappelez-vous: Les flotteurs sont stockés en interne dans un double système.
En effet, mais comme je décris que vous pouvez le faire. Vous le triez d'abord sur la mantissie (voir la Mantissa comme un entier, sans utiliser le signe). Ensuite, vous les trompez sur l'exposant (également un entier signé). Vous concluez en les triant par signe (booléen). En exécutant trois fois un algorithme de tri radix, vous pouvez trier des flotteurs.
Je vois ce que tu veux dire. Toutefois, un algorithme de tri O (n) pourrait être de façon plus lente qu'un type standard O (Nlogn), dans la plupart des cas, si N ne prolonge jamais un point mort.
Gardez à l'esprit la mémoire de mémoire pour une sorte de radix sur ce grand de domaine également. Ou diminuer votre empreinte mémoire augmente également votre temps de tri. En ce moment, vous avez une sorte de O (kN) où K est déjà 3 au moins. En fonction de la configuration de votre Radix, cela pourrait aller à deux chiffres. Ajouter dans n'importe quel code de conversion de la pièce flottante / double à int int et n va devoir être assez grand pour battre un tri standard Nlogn.
Je dois dire, après tout le travail, c'était vraiment la peine d'être essayé. Merci d'avoir posé cette question, sans cela je n'aurais jamais essayé de sortir :)