Aucune garantie pour Arrays.BinarySearch?

http://java.sun.com/j2se/1.4.2/docs/api/java/util/Arrays.html Aucune garantie pour Arrays.BinarySearch?

Sun ne mentionne pas la complexité de leur implemention recherche binaire. Est-ce une erreur? Je sais que cela devrait être O(logn), mais cela me rend nerveux quand ils ne le disent pas explicitement. Ils font pour certains de leurs algorithmes, comme Arrays.sort.

L'un de vous connaît-il l'implémentation actuelle? Je n'ai pas encore eu l'occasion de télécharger le code source moi-même! Je suppose que c'est une recherche binaire triviale, mais Sun modifie parfois les algorithmes pour de meilleures performances.

Source

2010-02-06 Frederik Wordenskjold

Plus récemment, http://java.sun.com/javase/6/docs/api/java/util/Arrays.html – trashgod

L'implémentation de java.util.Array est simple et il n'y a pas de place pour des optimisations.

Vous trouverez le code source dans JAVA_HOME/src.zip. L'algorithme de tri de cette classe, ~~requis pour l'utilisation de la recherche binaire,~~, est un quicksort optimisé offrant des performances n * log (n) (sur de nombreux jeux de données).

Source

2010-02-06 11:51:02 stacker

"L'alogrithme de tri de cette classe, nécessaire pour utiliser la recherche binaire ...". Pour être clair, vous n'êtes pas obligé d'utiliser Array.sort (...) '. Vous pouvez vous assurer que le tableau est commandé en utilisant une technique qui fonctionne !! –

Merci, c'était inexact – stacker

Qu'est-ce que la complexité de l'algorithme de tri a à voir avec la complexité de 'binarySearch' de toute façon? Je peux aussi bien trier en utilisant un tri à bulles, puis trouver des éléments dans O (log n) en utilisant 'binarySearch'. – MAK

La recherche binaire est par définition O (log n) (en moyenne) supposez qu'il n'est pas nécessaire de le mentionner explicitement.

Source

2010-02-06 03:54:39 leeeroy

En regardant le code même si le tableau n'est pas trié, il ne peut apparemment pas être pire que O (log n). – SyntaxT3rr0r

@WizardOfOdds - mais vous obtiendrez probablement la mauvaise réponse, bien sûr. –

Si le tableau n'est pas trié, le doco dit explicitement que le résultat n'est pas défini. –

Arrays.sort est garanti pour retourner un tableau trié, peu importe ce que votre tableau contient. (Minuscule 'b' btw) ne peut garantir rien vu que votre tableau peut être non trié. Maintenant, éditer ma réponse: en regardant le code, il n'est apparemment pas possible de faire pire que O (log n). Mais il n'y a bien sûr aucune garantie que vous aurez trouvé la bonne valeur.

Source

2010-02-06 04:13:37 SyntaxT3rr0r

L'un de vous connaît-il l'implémentation actuelle?

Vous pouvez trouver vous-même le code source de l'implémentation réelle dans votre installation JDK ou à l'aide d'une recherche Google. Par exemple, recherchez "java.util.Arrays.java.html".

Mais je n'ai aucun doute que les méthodes de binarySearch sont O(logN). Si ce n'était pas quelqu'un l'aurait remarqué ... au cours des 10 dernières années.

Source

2010-02-06 04:15:39

Aucune garantie pour Arrays.BinarySearch?

Répondre

Questions connexes