J'utilise TLIST / TOBEJECTLISTLIST et TStringList (avec des objets associés) pour une multitude de tâches, soit comme, soit comme base pour des structures plus complexes. Alors que la fonctionnalité de tri est généralement assez bonne, j'ai parfois besoin de faire un stable Trier, et les deux listes utilisent Quicksort.
Quel est le moyen le plus simple de mettre en œuvre un tri stable pour TLIST et / ou TStringList? Dois-je écrire ma propre routine de tri ou peut-il être fait en utilisant une astuce intelligente avec TstringListCompare / TLSTRISTCompare?
4 Réponses :
Vous devrez écrire votre propre routine de tri.
Vous pouvez lire la mise en œuvre actuelle QuicksTort et écrire votre propre version stable (par exemple, une sorte de fusion ou tout autre Variante stable ).
Quelques astuces:
tlist.list [] ) au lieu d'éléments plus lents [ ] ou getItem () : Sous-méthode appelant et la vérification de la plage ralentissement de l'exécution;
- La fonction de comparaison est la plupart du temps le goulot d'étranglement de la vitesse de la recherche - alors prenez soin de cette partie;
- Si vous avez besoin d'une vitesse, utilisez un véritable profileur sur des données réelles (par exemple) - mais faites-la juste avant de le rendre rapide;
- Commencez par une implémentation existante du tri;
- Pour minimiser l'espace de pile, vous pouvez utiliser un enregistrement temporaire pour stocker et partager des variables entre les appels récursifs.
Je pensais avoir dû écrire le mien, mais j'ai dû demander. J'espérais un tour "magique" :-) Venez penser à cela, n'est-ce pas étrange Borland / Embarcadero n'a-t-il pas fait de tlist.Sort stable? Je ne suis pas expert, mais je crois qu'il existe des algorithmes de tri avec les mêmes performances que l'utilisation de la mémoire rapide et toujours modeste. Et bien.
En ce qui concerne tous les comptes de livre, Quicksort est un algorithme de tri bien connu à la fois rapide, facile à coder et à déboguer, et à une utilisation faible de la mémoire. Les variations stables (telles que la fusion ou l'insertion Tries) sont plus complexes et ne fournissent pas de meilleures performances. Le tri dans la VCL n'a pas besoin d'être stable, donc QuicksTort était le meilleur candidat à une mise en œuvre du tri général.
Cette question est plutôt vieille, mais voici ma réponse pour les futurs lecteurs: J'en avais aussi besoin récemment et adapté la mise en œuvre trouvée dans le livre "Les tomes des algorithmes de Delphes et des structures de données" de Julian Bucknall. Mise en œuvre pour les classes de TLIST, TOBEJECTLISTÉES ET DESCENDANTES. Cela fonctionne avec Delphi 2009 à XE7 et probablement d'autres versions également: http://alexandrecmachado.blogspot.com.br/2015 /02/merge-sort-for-Delphi.html
Joli! Merci mec. Je note cependant qu'il n'y a pas de tests d'unité. Dans quelle mesure êtes-vous confiant que le code est solide? Souhaitez-vous l'utiliser dans le code de production?
J'ai écrit des tests unitaires et malheureusement, le genre ne semble pas être complètement stable :( Je vais poster le test sur votre blog.
Il y avait un bogue dans le code d'origine. Merci de la trouver et de l'informer. Le code est corrigé et oui, je vais l'utiliser dans la production. Voici les informations sur le problème et le correctif: alexandrecmachado.blogspot.com.br/2015/03/...
Frais. Merci de la résoudre.
Link Seules les réponses ne doivent pas être encouragées.
@DavidHeffernan je pense que vous vous êtes réveillé du mauvais côté du lit? Passez-vous votre temps à suivre toutes les questions de chaque utilisateur qui pointe certaines informations incomplètes que vous avez fournies dans votre réponse ou est juste dans mon cas? MDR
Que diriez-vous de se concentrer sur le contenu de mon commentaire au lieu de le rendre personnel.
"Oh, je vais donc descendre toutes ses réponses juste pour montrer qui est responsable ici" lol. Tu es pathétique
Non. Une fois de plus concentrer sur le contenu et ne le prenez pas personnellement. Link Seules les réponses sont découragées. Cela a été discuté sur Meta et les lignes directrices sont claires. Parler à cela.
de la question similaire Comment peut-on Je remplace StressList.sort avec un tri stable dans Delphi? , lié ici dans le commentaire de Lkessler, je dois copier ici un tour vraiment facile comme mentionné en question.
Vous pouvez facilement faire un tricot de tri rapide comportant stable juste par Ajout de numéros de commande initiaux dans des données pour trier et ajouter la dernière condition de comparaison dans la fonction de comparaison de la douane pour comparer ces numéros de commande initiaux. P>
facile, rapide et intelligent. Coûte un seul entier supplémentaire (ou octet ou utilisez un stockage réservé comme TComponent.tag si vous triez les TComponents) sur chaque élément tri et une boucle d'initialisation sur eux. P>
TObjectToSort = class
...
Index: Integer;
end;
function MyStableSortComparer(List: TStringList; Index1, Index2: Integer): Integer;
var
o1, o2: TObjectToSort;
begin
o1 := TObjectToSort(List.Objects[Index1]);
o2 := TObjectToSort(List.Objects[Index2]);
...
if Result = 0 then
Result := o1.Index - o2.Index;
end;
for i := 0 to MyStrtingList.Count - 1 do
TObjectToSort(MyStrtingList.Objects[i]).Index := i;
MyStrtingList.CustomSort(MyStableSortComparer);
Pour toute personne utilisant des génériques Voici une implémentation prête à l'emploi d'insertion et de trier de fusion, les deux algorithmes de tri stables.
var AList: TList<T>; AComparer: IComparer<T>; begin ... TMySort.MergeSort<T>(AList.List, 0, AList.Count-1, AComparer); ... end;
Voir aussi: Stackoverflow.com/Questtions/9303488/...