Existe-t-il un moyen de trier d'abord puis de rechercher un objet dans une liste d'objets liés. Je pensais juste à vous un moyen de tri et une recherche binaire qu'en pensez-vous? Mercirechercher une liste d'ordre sans la convertir en tableau
La classe Collections a beaucoup d'autres méthodes étonnantes pour rendre la vie plus facile aux programmeurs.
Notez que la mise en œuvre de la méthode de tri sera en effet de convertir la liste à un tableau, mais de vous avez besoin de convertir pas explicitement la liste à un tableau avant d'appeler la méthode :)
Notez que ces méthodes vont d'abord déverser toute la liste dans un tableau, puis reconstituer la liste. Ce n'est donc pas un algorithme spécifique aux listes chaînées. – Thilo
@Thilo - c'est correct. Cela "fonctionne", mais si vous le faites naïvement sur une liste chaînée, la performance sera * pire * que si vous appelez simplement java.util.List # contains() '!! –
Vous voudrez peut-être à la question si la recherche sur un tri La liste est la meilleure option pour votre cas d'utilisation car cela ne fonctionne pas bien. Le tri par liste est O (NlogN) et la recherche binaire est O (logN). Vous pouvez envisager de créer un Set à partir de vos éléments de liste, puis de le rechercher via la méthode contains, qui est O (1), si vous voulez juste voir si un élément existe. Il serait beaucoup plus facile de vous donner des conseils sur la collection que vous pourriez envisager si vous pouviez expliquer plus sur votre cas d'utilisation.
EDIT: Envisagez performance issues of List sorting si vous envisagez de le faire pour les grandes listes.
Notez que la méthode sort() de java utilise une version modifiée du tri de fusion –
@Suraj - cela n'a probablement pas d'importance. Le plus important est de comprendre votre cas d'utilisation et de choisir l'approche la plus appropriée. La différence entre les approches les plus appropriées et les moins appropriées * pourrait * être * autant que "O (N ** 2)" ... et c'est une GRANDE différence! –
Ce n'est pas une bonne approche, IMO. Si vous utilisez Collections.sort(list), où le list est un LinkedList, cela copie le list dans un tableau temporaire, le trie, puis le copie dans la liste, c'est-à-dire O(NlogN) pour trier plus les copies 2 * O(N). Mais quand vous essayez ensuite de faire une recherche binaire (par exemple en utilisant Collections.binarySearch(list), chaque recherche fera opérations O(N) liste traversal. Vous pouvez aussi bien avoir pas pris la peine de tri de la liste!
Une autre approche serait de convertir la liste à une array ou ArrayList, puis trier et rechercher ce tableau/ArrayList.Cela donne une copie plus un type à configurer, et O(logN) pour chaque recherche
Mais ni l'un ni l'autre n'est la meilleure approche. vous devez effectuer des opérations de recherche
Si vous voulez simplement faire une recherche dans la liste, alors appeler list.contains(...) est O(N) ... et c'est mieux que tout ce qui implique le tri et la recherche binaire.
Si vous souhaitez effectuer plusieurs recherches dans une liste qui ne change jamais, il vaut probablement mieux placer les entrées de la liste dans un HashSet. La construction d'un HashSet est O(N) et la recherche est O(1). (Cela suppose que vous n'avez pas besoin de votre propre comparateur.)
Si vous souhaitez effectuer plusieurs recherches dans une liste qui ne cesse de changer lorsque la commande N'EST PAS significative, remplacez la liste par un HashSet. Le coût incrémentiel de la mise à jour du HashSet sera O(1) pour chaque ajout/suppression, et O(1) pour chaque recherche.
Si vous souhaitez effectuer plusieurs recherches dans une liste qui ne cesse de changer et que l'ordre EST significatif, remplacez la liste par une LinkedHashMap à ordre d'insertion.Ce sera O(1) pour chaque ajout/suppression, et O(1) pour chaque recherche ... mais avec de grandes constantes de proportionnalité que pour un HashSet.
+1 pour une belle écriture. – harschware
La recherche binaire ne fonctionnera pas correctement avec une liste chaînée. Vous avez besoin d'un accès aléatoire pour cela. – Thilo
Selon les docs de l'API, 'binarySearch' pour les grandes listes chaînées fera des comparaisons O (log n) avec des traversées de liaisons O (n). Un algorithme naïf ferait des traversées de liens O (n log n). –
Est-ce que vous faites cela pour construire une routine de benchmarking de performance informatique et que vous devez mettre en place autant d'obstacles hautement inefficaces que possible pour tester la performance efficace des processeurs? –