Comment insérer rapidement un élément dans un tableau avec des doublons après tous les éléments égaux?

Question

J'ai une ArrayList, qui contient des objets de jeu triés par leur position 'Z' (float) de bas en haut. Je ne sais pas si ArrayList est le meilleur choix pour elle, mais je suis venu avec une telle solution pour trouver un indice d'insertion dans une complexité plus rapide que linéaire (pire des cas):

 GameObject go = new GameObject(); 
     int index = 0; 
     int start = 0, end = displayList.size(); // displayList is the ArrayList 
     while(end - start > 0) 
     { 
      index = (start + end)/2; 
      if(go.depthZ >= displayList.get(index).depthZ) 
       start = index + 1; 
      else if(go.depthZ < displayList.get(index).depthZ) 
       end = index - 1; 
     } 
     while(index > 0 && go.depthZ < displayList.get(index).depthZ) 
      index--; 
     while(index < displayList.size() && go.depthZ >= displayList.get(index).depthZ) 
      index++; 

Le hic est que l'élément doit être inséré à un endroit spécifique dans la chaîne d'éléments de valeur égale à depthZ - à la fin de cette chaîne. C'est pourquoi j'ai besoin de 2 boucles supplémentaires après la recherche binaire qui je suppose ne sont pas trop chères car la recherche binaire me donne une approximation de cet endroit.

Encore je me demande s'il existe une meilleure solution ou des algorithmes connus pour un tel problème dont je n'ai pas entendu parler? Peut-être utiliser une structure de données différente de ArrayList? Au moment où j'ignore l'insertion de cas le plus défavorable O (n) (en insérant au début ou au milieu) parce que j'utilise une liste normale, je ne serais pas capable de trouver un index à insérer en utilisant la méthode ci-dessus.

Answer 1

Ajouter 1 à l'octet le moins significatif de la touche (avec report); recherche binaire pour cette position d'insertion; et insérez-le là.

Votre recherche binaire doit être construite de manière à se terminer à l'extrême gauche d'une séquence de doublons, mais cela est trivial compte tenu de la compréhension des différents algorithmes de recherche binaire.

Answer 2

Vous devriez essayer d'utiliser l'arbre de recherche équilibré (arbre rouge-noir par exemple) au lieu de tableau. D'abord, vous pouvez essayer d'utiliser TreeMap sorcière utilise un arbre rouge-noir à l'intérieur pour voir si elle répond à vos besoins. la mise en œuvre possible:

Map<Float, List<Object>> map = new TreeMap<Float, List<Object>>(){ 
    @Override 
    public List<Object> get(Object key) { 
     List<Object> list = super.get(key); 
     if (list == null) { 
      list = new ArrayList<Object>(); 
      put((Float) key, list); 
     } 
     return list; 
    } 
}; 

Exemple d'utilisation:

map.get(0.5f).add("hello"); 
map.get(0.5f).add("world"); 
map.get(0.6f).add("!"); 
System.out.println(map); 

Answer 3

Une façon de le faire serait de faire une recherche de réduction de moitié, où la première recherche est à mi-chemin à travers votre liste (list.size()/2), puis pour la prochaine, vous pouvez faire la moitié de cela, et ainsi de suite. Avec cette méthode exponentielle, au lieu d'avoir à faire 4096 recherches lorsque vous avez 4096 objets, vous avez seulement besoin de 12 recherches

désolé pour le mépris des termes techniques, je ne suis pas le meilleur à des conditions: P

Answer 4

À moins Je néglige quelque chose, votre approche est essentiellement correcte (mais il y a une erreur, voir ci-dessous), en ce sens que votre premier essaie de calculer l'index d'insertion de sorte qu'il sera placé après tout OR inférieur Z: il y a connectez-vous à votre premier test (en mettant à jour "start" si le résultat est TRUE).

Ensuite, bien sûr, il n'y a plus besoin de s'inquiéter de sa position parmi ses pairs. Cependant, votre suivi tout en détruisant cette belle situation: le test au premier suivi alors que les rendements sont toujours VRAIS (une fois) et donc vous reculez; et alors vous avez besoin du second suivi pour l'annuler. Donc, vous devez supprimer les deux suivis et vous avez terminé ...

Cependant, il y a un petit problème avec votre premier moment, de sorte qu'il ne fait pas toujours exactement ce que l'objectif est. Je suppose que les résultats erronés vous ont incité à mettre en place les mesures de suivi pour «réparer» cela.

Voici le problème dans votre temps. Supposons que vous ayez un try-index (start + end)/2 qui pointe vers un Z plus grand, mais celui juste avant qu'il ait la valeur Z. Vous entrez alors dans votre deuxième test (elseif) et placez "end" à la position où cette valeur Z réside. Finalement vous finissez avec précisément cette position. La solution est simple: dans votre affectation elseif, mettez "end = index" (sans le -1). Remarque finale: le test dans l'elseif est inutile, sinon c'est suffisant.

Ainsi, dans tout ce que vous obtenez

GameObject go = new GameObject(); 
int index = 0; 
int start = 0, end = displayList.size(); // displayList is the ArrayList 
while(end - start > 0) 
{ 
    index = (start + end)/2; 
    if(go.depthZ >= displayList.get(index).depthZ) 
     start = index + 1; 
    else 
     end = index; 
} 

(je l'espère, je ne l'ai pas oublié quelque chose trivial ...)