Meilleure façon de trier une longue liste de chaînes

Question

Je voudrais savoir la meilleure façon de trier une longue liste de chaînes avec l'efficacité du temps et de l'espace. Je préfère l'efficacité du temps à l'efficacité de l'espace. Les chaînes peuvent être numériques, alpha, alphanumériques etc. Je ne suis pas intéressé par le comportement de tri comme le tri alphabétique tri alphabétique v/s juste le tri lui-même.

Certaines façons ci-dessous que je peux penser.

1. En utilisant le code ex: la fonction Arrays.Sort() du framework .Net. Je pense que la façon dont cela fonctionne est que les hashcodes pour les chaînes sont calculés et la chaîne est insérée à la bonne position en utilisant une recherche binaire.

2. Utilisation de la base de données (ex: MS-sql). Je n'ai pas fait ça. Je ne sais pas à quel point cela serait efficace. Utilisation d'une structure de données arborescente de préfixe comme un trie. Le tri nécessite de parcourir tous les trieNodes de l'arbre trie en utilisant l'heure DFS (depth first search) - O (| V | + | E | (La recherche prend O (l) heure où l est la longueur de la chaîne à comparer).

D'autres moyens ou structures de données?

Answer 1

Vous dites que vous avez une base de données, et que les chaînes sont probablement stockées dans la base de données. Ensuite, vous devriez obtenir la base de données pour faire le travail pour vous. Il peut être en mesure de tirer parti d'un index et donc pas besoin de trier réellement la liste, mais juste le lire de l'index dans l'ordre trié.

S'il n'y a pas d'index, la base de données peut toujours vous aider. Si vous n'obtenez que les k premières lignes pour un petit nombre constant k, par exemple 100. Lorsque vous utilisez ORDER BY avec une clause LIMIT, SQL Server peut utiliser une optimisation spéciale appelée TOP N SORT qui s'exécute en temps linéaire au lieu de O (n log (n)) heure.

Si vos chaînes ne sont pas déjà dans la base de données, vous devez utiliser les fonctionnalités fournies par .NET à la place. Je pense qu'il est peu probable que vous serez en mesure d'écrire du code personnalisé qui sera beaucoup plus rapide que le tri par défaut.

Answer 2

J'ai trouvé this paper qui utilise trie structure de données pour trier efficacement de grands ensembles de chaînes. Je n'ai pas examiné en détail cependant.

Answer 3

Radix sort peut également être une bonne option si les chaînes ne sont pas très longues, par ex. liste des noms

Answer 4

Supposons que vous avez une grande liste de chaînes et que la longueur de la liste est N.

En utilisant une comparaison algorithme de tri en fonction comme mergesort, HeapSort ou Quicksort vous donnera un

où n est la taille de la liste et d la longueur maximale pour toutes les chaînes de la liste.

Nous pouvons essayer d'utiliser le tri Radix dans ce cas. Soit b la base et soit d la longueur de la chaîne maximale, puis nous pouvons montrer que le temps d'exécution en utilisant le tri radix est .

De plus, si les chaînes sont dites le minuscules anglais Alphabets le temps d'exécution est

Source: conférence MIT Opencourse Algorithmes par le prof. Eric Demaine.