J'étais assez surpris quand j'ai découvert qu'il n'y a pas de mauvaise façon de trier ou d'effectuer une recherche binaire sur un actuellement: P> class List
{
static Sort<T>(IList<T> list);
static int BinarySearch<T>(IList<T> list, T item);
}
5 Réponses :
Vous avez Pour les deux types de référence et de valeur, l'expédition d'interface pourrait être coûteuse, ce qui signifie un appel à arraylist.adapter qui permet d'utiliser les routines de tri de l'arraylist , mais cela entraînerait un impact énorme des performances pour les listes génériques des types de valeur non complets, plus à la fois des frais d'appels virtuels et d'interface.
icollection t [] suivi d'un tri séparé pourrait être l'option à usage général la plus rapide, y compris une extension personnalisée à trier directement sur l'objet list t [] . Il n'y a tout simplement aucun moyen de le faire pour un arbitraire
Basé sur la poste de Hallgrim à
Je pense qu'il y a un très bon cas pour ne pas inclure une méthode de tri pour Généralement ce que je fais si je dois exécuter une sorte sur un Donc, par exemple: ilist Ilist ilist
Cependant, il est important de réaliser que cela ne triera pas la liste en place (ce qui pourrait ne pas être un problème).
@LOMAXX: Comment créerait-il une complexité ajoutée pour ces cours qui implémentent IList <>? Les propriétés d'obtention d'index / définies existent déjà et celles-ci pourraient simplement être utilisées dans la méthode STATIC TRI (Liste
@dewald: Parce que c'est plus de code à écrire et qu'il n'a aucun sens de trier tous les types de collecte.
Désolé, pas un gars C # ... S'il y a déjà un tri statique (liste
@KIP: Il y a une méthode d'instance dans la liste
Il ne demande pas une fonction de membre de tri sur l'interface, mais une fonction statique ailleurs, prenant un argument iliste. Cela n'apporterait pas de complexité pour ceux qui mettraient la mise en œuvre d'une ilist.
Ce n'est pas une sorte sur mesure. Alors pourquoi ne pas accepter iEnumerable et retour adresses.orderby (x => x) .tolist () ?
Je ne suis pas un expert C #, mais très peu de mises en œuvre de la liste prennent en charge le tri, la recherche binaire ou même la récupération indexée. Les listes sont généralement basées sur Listes liées qui n'offrent généralement pas de Je trouve le fait que O (1 ) moyen de récupérer un élément par son index. Si vous souhaitez localiser un élément rapidement, utilisez quelque chose qui conserve les éléments dans la commande triée comme un arbre ou un tableau comme suggéré par d'autres.
iList inclut un Méthode de récupération indexée intéressante. Vous voudrez peut-être envisager d'utiliser TritedList au lieu de Liste car il semble que cela devrait prendre en charge les recherches par index ou clé dans o (1) heure. En général, si vous avez besoin de quelque chose qui prend en charge une recherche rapide, recherchez une structure de données qui conserve ses éléments dans l'ordre au lieu de les trier explicitement. Si rien d'autre, c # a déjà la litanie des structures de données.
En C #, une "liste" fournit généralement une indexation directe d'élément au-dessus d'une "collection" qui consiste simplement ajouter / supprimer des éléments.
Vous pouvez trier des listes liées à O (NLGN) avec le tri de la fusion.
Je ne suis pas au courant d'aucune implémentation de IList LinkedList ilist
LINQ a une méthode de commande qui fonctionne sur tous les // Order a list of addresses:
IList<string> list = ...
var orderedList = list.OrderBy(input => input);
Savez-vous comment ils le font sous les couvertures? Je suppose que, puisque les énumérateurs ne sont généralement évalués que comme si elles sont nécessaires (évaluation paresseuse), alors quelque chose comme un tri de sélection sera utilisé, ce qui risquerait de piquer puisqu'il s'agit de O (n ^ 2).
@dewald - Je pense que la règle générale est que les opérateurs LinQ-to-Obsect sont "comme paresseux que cela convient à la plupart des utilisations". Compte tenu des implémentations iénumérables peut être paresseuse, après avoir été énumérées à plusieurs reprises à travers l'entrée à la recherche de valeurs successivement basses, serait extrêmement gaspillée. Cela dit, si je lis les choses correctement, il utilise énumérableorter
Si vous craignez de savoir si le tri est immédiat ou paresseux, alors au lieu de liste.orderby (...), utilisez list.orderby (...). Tolist (), qui obligera le tri immédiatement.
@KKYRALESSA - C'est une bonne suggestion de contourner l'évaluation paresseuse, cependant, cela ne se contente pas de créer une copie d'une copie d'un
"Savez-vous comment ils le font sous les couvertures?" Ils allouent probablement une classe d'itérateur et renvoient les éléments comparés à l'aide de la fonction Orderby que vous avez transmise.
La bonne nouvelle est que vous pouvez maintenant tout ce qui reste est le code TODO (et probaby réécrire important, trier ;-p); mais après cela: ilist
@MARC: Ce sont de bonnes méthodes d'extension, cependant, je suis simplement surpris que nous devions écrire du code pour effectuer ces opérations de base. Comme si vous l'avez dit, "Ilist
Pouvez-vous reformuler cela comme une question, peut-être "y a-t-il une raison quelconque C # n'a pas de tri intégré et de recherche binaire de IList?" Vous trouverez maintenant un peu une déclaration et appelez des personnes à voter pour cela sur le site de Microsoft, qui risquent d'être fermée comme spam
C'est un peu caché dans la randonnée, mais il y a une question de là pour m'aider à comprendre pourquoi elle n'est pas là si Microsoft l'ait intentionnellement quitté: "Y a-t-il une raison pour laquelle ils ont délibérément omis cette caractéristique?"
Well Stack Overflow est un site de questions / réponses. C'est une bonne étiquette de mettre davantage la concentration sur votre question (surtout dans le titre de la question). À l'heure actuelle, cela ressemble à vous avoir déjà supposé que ceci est un bogue, et vous voulez que les autres disent que vous êtes d'accord avec Microsoft. Un meilleur esprit de telle serait de préciser que la question est "y a-t-il une bonne raison pour cela ou est-ce un bug?"
@Kip: J'ai changé le titre en une question. Merci pour la suggestion.
Fwiw: meta.stackexchange.com/questions/7211/...
Je n'étais certainement pas l'intention de "abuser" la communauté avec cette question (ou une pétition d'amélioration, mais je l'examine), et je m'excuse si je l'ai fait. À l'avenir, je vais essayer de rendre les questions plus facilement apparentes et de rester sur toutes les pétitions, sauf s'il y a beaucoup de commentaires qui méritent un.
Ce n'est pas une vraie question. Posez une question ou postez ceci sur votre blog.
Connexes: Stackoverflow.com/questions/3844463/how-do -Je-tri-ilistclass