Insertion dans une liste triée

Avec Java, j'ai une classe, connu comme TestClass, qui a un membre nommé du Nom, qui est une chaîne de caractères. J'ai aussi une liste de tableaux de ce type, qui est déjà triée par ordre alphabétique des noms. Ce que je veux faire est de trouver le meilleur indice pour mettre une nouvelle instance de TestClass. La meilleure approche, j'ai pu arriver jusqu'ici est: est-ce

public static int findBestIndex(char entry, ArrayList<TestClass> list){
    int desiredIndex = -1;
    int oldPivot = list.size();
    int pivot = list.size()/2;
    do
    {
        char test = list.get(pivot).Name.charAt(0);
        if (test == entry)
        {
            desiredIndex = pivot;
        }
        else if (Math.abs(oldPivot - pivot) <= 1)
        {
            if (test < entry)
            {
                desiredIndex = pivot + 1;
            }
            else
            {
                desiredIndex = pivot - 1;
            }
        }
        else if (test < entry)
        {
            int tempPiv = pivot;
            pivot = oldPivot - (oldPivot - pivot)/2;
            oldPivot = tempPiv;
        }
        else
        {
            int tempPiv = pivot;
            pivot = pivot - (oldPivot - pivot)/2;
            oldPivot = tempPiv;
        }

    } while (desiredIndex < 0);

    return desiredIndex;
}

Essentiellement, Briser le tableau en deux, vérifier pour voir si votre valeur se passe avant, après, ou à ce point. Si c'est après, cochez la première moitié du tableau. Autres sage, cochez la seconde moitié. Ensuite, répétez. Je comprends que cette méthode ne teste que par le premier caractère, mais c'est facilement résolu, et n'est pas adapté à mon problème principal. Pour certains cas, cette approche fonctionne assez bien. Pour la plupart, il fonctionne très mal. Je suppose que ce n'est pas la recherche d'un nouveau point de pivot correctement, et si c'est le cas, comment pourrais-je résoudre ce problème?

Edit: Pour plus de précisions, je suis en utilisant ce pour un système d'inventaire, donc je ne suis pas sûr qu'un LinkedList serait approprié. Je suis à l'aide d'une liste de tableaux parce qu'ils sont plus familiers pour moi, et serait ainsi plus facile à traduire dans une autre langue, si nécessaire (ce qui est probable, à l'heure actuelle, pourrait être le déplacement de plus de C#). J'essaie d'éviter des choses comme Comparables pour cette raison, comme je l'avais complètement ré-écrire si C# n'en a pas.

Modifier la partie Duex: Compris ce que je faisais mal. Au lieu d'utiliser le précédent point de pivot, j'aurais été de la définition et la modification des frontières de la région, j'ai été vérifier, et la création du nouveau pivot sur cette base.

  • Pourquoi ne pas vous suffit d'insérer tous les éléments, puis utilisez Collections.sort()?
  • Peut-être que je ne suis pas à la recherche à ce droit, mais si vous déterminez que la valeur va après les sélectionné (test) le point, n'est-ce pas vérifier la deuxième moitié du tableau?
  • recours après chaque insertion serait susceptible d'être le plus lent de chemin à faire, bien que la vitesse n'est pas mon plus gros souci, car il n'y aura probablement pas beaucoup d'objets décalés et sortir rapidement.
  • c'est ce que j'essayais de faire, mais probablement ma tentative de le faire c'était complètement faux, et c'est là que je vais avoir le problème.
  • il dépend de la fréquence de cette liste triée est accessible. Si pas souvent que vous pouvez simplement reconstruire cette liste en cas de besoin.
InformationsquelleAutor user2423158 | 2013-05-26
  1. 4

    Il pourrait ne pas être une bonne idée d'utiliser un SortedSet (par exemple, un TreeSet) pour cela, parce que les arbres ne permettent pas de dupliquer des éléments. Si vous avez les éléments en double (c'est à dire TestClass cas, avec le même nom), puis une Liste doit être utilisé. Pour insérer un élément dans une liste déjà triée est aussi simple que cela:

    void insert(List<TestClass> list, TestClass element) {
    int index = Collections.binarySearch(list, element, Comparator.comparing(TestClass::getName));
    if (index < 0) {
        index = -index - 1;
    }
    list.add(index, element);
}

    Ce code nécessite Java 8 ou plus tard, mais peut être réécrit pour travailler dans les anciennes versions de Java ainsi.

    InformationsquelleAutor Daniel Beer
  2. 3

    Comme l'a déjà souligné, il n'y a pas de raison de mettre en œuvre ce par vous-même, exemple de code simple:

    

    class FooBar implements Comparable<FooBar> {

        String name;

        @Override
        public int compareTo(FooBar other) {
           return name.compareTo(other.name);
        }
    }

    TreeSet<FooBar> foobarSet = new TreeSet<>();
    FooBar f1;
    foobarSet.add(new FooBar("2"));
    foobarSet.add(f1 = new FooBar("1"));

    int index = foobarSet.headSet(f1).size();

    (Basé sur Comment trouver l'indice d'un élément dans un TreeSet?)

    • Je pense également que nous devrions utiliser la liste triée. Dans la réponse, nous utilisons Comparables. Et une autre option est d'utiliser un Comparateur.
    InformationsquelleAutor mrak
  3. 1

    Vous devriez utiliser quelque chose comme un PriorityQueue qui a déjà un sens de l'ordre. L'insertion dans une collection avec un sens de la commande sera automatiquement placer l'élément à la bonne place avec un minimum de temps(généralement log(n) ou moins).

    Si vous voulez faire arbitraire insère sans cela, je suggérerais à l'aide d'une LinkedList que de ne pas avoir recours ou complètement copié sur pour insérer un élément unique comme la liste de tableaux que vous avez actuellement. Alors que vous trouver le bon emplacement pour insérer une LinkedList peut prendre jusqu'à O(n) le temps, dans la pratique, il sera toujours plus rapide que d'utiliser un log(n) recherche pour l'emplacement correct dans une ArrayList, mais alors avoir besoin de les copier ou de les trier par la suite.

    Également le code pour trouver l'emplacement insérer dans une liste chaînée est beaucoup plus simple.

    if (next != null && next.compareTo(insertElement) > 0){
    //You have the right location
}
    • Je ne suis pas sûr qu'un PriorityQueue ou LinkedList serait le mieux pour ce que je suis en utilisant cette pour (Qui, faut vraiment que j'ai mentionné dans le post original, et ont maintenant corrigé).
    • Eh bien, je dois dire que votre raison de ne pas vouloir utiliser une LinkedList b/c il serait plus facile de traduire une liste de tableaux à la C# n'est pas correct. Les deux seraient tout aussi facile à traduire ( je dirai même de la LinkedList plus facile). La chose la plus importante est bien que vous ne pouvez pas insérer un élément au milieu d'une liste de tableaux sans se déplacer tous les éléments d'après elle. Cela implique la copie de la partie de la liste de tableaux, nettement plus lent que d'une LinkedList insérer. En gros, si vous êtes à la recherche pour plus d'efficacité, vous utilisez le mauvais discbased.
    InformationsquelleAutor greedybuddha
  4. 1

    Il existe d'autres structures de données utilisées pourrait utiliser à la place de la liste comme un arbre, la priorité de la file d'attente etc.

    • Je suis allé avec Arraylist en raison de la familiarité, et pour la facilité de l'accès à un élément donné. Une autre structure de données, cependant, peut être une bonne idée, bien que j'aurais à faire un peu de recherche en premier.
    InformationsquelleAutor Ayodeji
  5. 1

    Je pense que le problème est dans ce morceau de code:

    else if (test < entry)
{
    int tempPiv = pivot;
    pivot = oldPivot - (oldPivot - pivot)/2;
    oldPivot = tempPiv;
}
else
{
    int tempPiv = pivot;
    pivot = pivot - (oldPivot - pivot)/2;
    oldPivot = tempPiv;
}

    Vous présenteront les pièces les mêmes actions que test < entrée ou si test > entrée. Cela conduira à une recherche linéaire lorsque l'élément que vous recherchez se trouve au début du tableau.

    Je préfère utiliser (basse et haute) comme

    high = list.size();
low = 0;

do {
   pivot = (high + low) / 2;
   if (test < entry) {
      low = pivot;
   } else if (test > entry) {
      high = pivot
   } else {
      ....
   }
} while ...;
    • Pourquoi n'est-ce pas la accepté de répondre (si @user2423158 voulu accepter un...)? Il dispose de la clé à travailler en O(log(n)) sur les tableaux. Merci!
    • merci pour la voix, je soupçonne que l'utilisateur voulait sa réponse à la question et n'avait aucun intérêt après que
    InformationsquelleAutor Bruce Martin
  6. 0

    Faire une liste de mise en œuvre de votre propre, et dans votre méthode ajouter ces lignes:

    wrappedList.add(object);
Collections.sort(wrappedList);
    InformationsquelleAutor hd1