ArrayList sans le surcoût de copie?

Question

Quelqu'un sait-il d'une implémentation List qui a un temps constant get (index int) (par exemple implémente RandomAccess) mais ne doit pas copier la liste entière quand il se développe comme le fait ArrayList?

Je pense que la mise en œuvre pourrait bien se faire en termes d'autres listes, par ex.

public class ChunkedList<T> implements List<T>, RandomAccess { 
    private LinkedList<ArrayList<T>> chunks; 
    public T get(int index) { 
    return findCorrectChunk(index).get(computeChunkIndex(index)); 
    } 
} 

Answer 1

S'il existait une telle structure, tout le monde l'utiliserait à la place des tableaux. Cependant, je pense à une structure plus proche dont on m'a parlé dans une conférence universitaire. Il a un temps d'accès constant et le temps d'ajouter/enlever un élément à une position arbitraire est principalement O (sqrt (N)) et seulement quand N croise le carré de la valeur entière, il prend O (N). Le temps amorti est O (sqrt (N)). Voici l'idée. N éléments dans cette structure sont stockés dans un tableau contigu, qui est divisé en sqrt (N) blocs d'éléments contigus sqrt (N) (peut-être, le dernier morceau contient moins d'éléments). Chaque fragment est un ring buffer, pour lequel la position du premier élément est stockée dans un tableau distinct de sqrt (N). Pour accéder à un élément, vous devez déterminer à quel bloc il appartient (prend une division) et effectuer un décalage approprié dans le tampon circulaire (somme et module). C'est une heure constante d'accès.

Pour ajouter un élément avant la position i-ème, déterminer le tronçon k l'élément se terminera, puis marquer tous les derniers éléments dans chaque tronçon dans k .. sqrt(N)-1 plage. Décalez l'élément marqué dans l'avant-dernier bloc vers l'emplacement libre dans un dernier morceau qui sera la tête d'un tampon d'anneau là (accédez à un tableau supplémentaire pour déterminer où exactement). Ensuite, à la position de l'élément déplacé par rapport à l'avant-dernier bloc, déplacez l'élément marqué du segment pré-avant-dernier. Répétez ceci et vous obtiendrez un emplacement libre au milieu du tableau pour placer l'élément que vous alliez ajouter. La magie est que vous ne devez augmenter les valeurs que d'une unité dans le tableau supplémentaire (en prenant le temps O (sqrt (N))), rendant ainsi la structure cohérente pour y accéder à nouveau. La magie de sqrt (N) est également ici: vous devez opérer sur chacun des morceaux X et sur chacun des éléments N/X d'un tableau auxilliaire. min (X + N/X) est atteint pour X = sqrt (N).

S'il n'y a pas de place dans le dernier morceau d'ajouter un élément (à savoir le sqrt (N) utilisé jusqu'à présent est trop petit), remballer le tableau avec sqrt (N) a augmenté d'un. Cela prend le temps O (N). Le temps amorti est toujours O (sqrt (N)) par élément.

Par conséquent, en ajoutant un élément dans un endroit arbitraire de tableau prend O (sqrt (N)). La suppression prend le même temps. Le temps d'accès prend O (1).

C'est l'idée.Je ne sais pas comment ça s'appelle, et le professeur ne le savait pas non plus parce qu'il l'avait inventé tout seul. Toute référence serait appréciée. Et l'OP pourrait l'implémenter, mais je parie que quelqu'un l'a déjà fait.

Answer 2

Eh bien, pas vraiment une solution idéale, mais vous pouvez utiliser TreeMap pour cela. Votre ChunkedList sera un warapper autour de cela. Vos clés dans TreeMap seront de type Integer ou Long et contiendront vos index de liste. Les temps d'accès et d'insertion seront o (log (n)) (pas une constante, mais bien meilleure que n). Et en interne TreeMap fonctionne de manière similaire à LinkedList, c'est-à-dire que les nœuds sont simplement liés à des références.

EDIT: Quelque chose comme ça:

public class ChunkedList<T> implements List<T>, RandomAccess { 

    private TreeMap<Integer, T> data = new TreeMap<Integer, T>(); 

    public T get(int index) { 
     return data.get(index); 
    } 

    public boolean add(T o) { 
     data.put(data.size() + 1, o); 
     return true; 
    } 

     // Other operations 

} 

Bien sûr, d'autres opérations sera un peu plus complexe et prendra plus de temps que dans ArrayList.

Answer 3

Vous pouvez, bien sûr, écrire une implémentation de liste sous la forme d'un tableau de tableaux. Il y a beaucoup de choix quant à l'algorithme exact. La performance est théoriquement constante (en ignorant les effets de cache, etc.).

En pratique, il n'y a pas beaucoup de points dans la plupart des situations. Il y a des implémentations de cordes (cordes formées comme un ensemble de segments), mais elles sont relativement rares. La copie n'est pas vraiment chère et pour les annexes elle est amortie sur de nombreuses opérations pour disparaître.

(BTW, dans le code exemple question du LinkedList est hors de propos, car il est presque toujours.)

Answer 4

Avez-vous regardé juste laissant entendre la taille maximale au constructeur ArrayList?

Answer 5

Jetez un coup d'œil aux listes d'accès aléatoires. Vous pouvez obtenir l'insertion O (1) aux deux extrémités et l'accès O (log (n)) aux éléments. En fin de compte, une sorte de structure arborescente devrait donner les meilleurs temps de recherche/insertion.

Answer 6

Cela ressemble à une optimisation prématurée. Avez-vous profilé la fonction add() et l'a montré lent? Parce que ArrayList double la taille du tableau sous-jacent chaque fois qu'il manque d'espace, vous n'avez pas besoin de copier la liste chaque fois que vous ajoutez.

Vous essayez probablement de résoudre un problème qui n'existe pas.

Answer 7

Il est impossible d'écrire une telle structure de données. Le plus proche que vous pouvez obtenir est de pré-dimensionner le ArrayList à la taille maximale en supposant que vous connaissez le maximum. Ce qui est intéressant est que les algorithmes tels que Collections.sort() effectuera pire sur ChunkedList si son marqué RandomAccess.