6
votes

Java: Comment la flagliste gère la mémoire

Dans ma classe de structures de données, nous avons des études la classe Java ArrayList et comment elle augmente la matrice sous-jacente lorsqu'un utilisateur ajoute plus d'éléments. Qui est compris. Cependant, je ne peux pas comprendre comment cette classe libère exactement la mémoire lorsque de nombreux éléments sont supprimés de la liste. En regardant la source, il existe trois méthodes qui retirent les éléments:

public E remove(int index) {
 RangeCheck(index);

 modCount++;
 E oldValue = (E) elementData[index];

 int numMoved = size - index - 1;
 if (numMoved > 0)
     System.arraycopy(elementData, index+1, elementData, index,
        numMoved);
 elementData[--size] = null; // Let gc do its work

 return oldValue;
}

public boolean remove(Object o) {
 if (o == null) {
            for (int index = 0; index < size; index++)
  if (elementData[index] == null) {
      fastRemove(index);
      return true;
  }
 } else {
     for (int index = 0; index < size; index++)
  if (o.equals(elementData[index])) {
      fastRemove(index);
      return true;
  }
        }
 return false;
}


private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, 
                             numMoved);
        elementData[--size] = null; // Let gc do its work
}


2 commentaires

Veuillez reformater votre code. Stackoverflow ne comprend pas [Code], Modifiez votre message, sélectionnez l'extrait de code et appuyez sur la touche "CODE" pour le formater.


Oui, c'est mon premier post et j'étais en train de déterminer comment utiliser le formatage. Quelqu'un m'a aidé cependant :)


5 Réponses :


10
votes

Ils ne réduisent pas la matrice sous-jacente. Ils décontent simplement la taille. Le raisonnement est-il que si vous avez 1000 éléments dans une matrice et la suppression 1, pourquoi réaffecter et copier le tableau? C'est extrêmement gaspillé pour un très petit gain.

Fondamentalement Java ArrayList S ont deux propriétés importantes et il est important de comprendre qu'ils sont différents:

  • Taille: Combien d'éléments sont notionnellement dans la liste ; et

  • Capacité: Combien d'éléments peut s'adapter à la matrice sous-jacente.

    Lorsqu'un ArrayList se développe, il s'agit d'environ 50% de taille, même si vous n'ajoutez qu'un seul élément. C'est un principe similaire en sens inverse. Fondamentalement, cela revient à cela: réaffecter la matrice et la copie des valeurs est (relativement) coûteuse. Tellement de sorte que vous voulez minimiser cela se produisant. Tant que la taille notionnelle est avec une usine d'environ 2 de la taille de la matrice, il ne vaut rien d'avis.


4 commentaires

Oui, je comprends qu'il serait idiot de réaffecter après avoir retiré un élément. Mais que se passe-t-il si j'ajoute un million d'éléments, puis supprimez-les, mais n'ayez rien ajouter avant la fin du programme. Ce serait un gaspillage de mémoire pour conserver un réseau à cellules au lieu de la taille par défaut.


@ CKA3O4NIK: Ce n'est qu'un éventail de références. Un million d'entre eux ne prend toujours que 4 Mo - ne vaut pas vraiment la peine d'être inquiétant pour un cas aussi rare.


@ CKA304NIK Comme Michael dit, la réduction de la taille de la matrice n'est pas considérée comme un gros problème. Si vous voulez faire cela, vous pouvez appeler arraylist.trimtosize () .


Merci pour vos explications.



1
votes

Je dois avoir un autre regard sur le code source de ArrayList, mais supprimer supprime l'objet de la matrice, puis si l'objet n'est pas référencé par aucun autre objet, le GC peut supprimer cet objet. . Mais la taille de la matrice n'est pas diminuée.


0 commentaires

0
votes

Il n'y a pas beaucoup de gain en redimensionnant la matrice interne de l'arrayage, même que vous utilisez ArrayList pour contenir un objet important.

List<LargeObject> list = new ArrayList<LargetObject>();


1 commentaires

C'est étrange comment les gens ont tellement peur des indicateurs de C et sont si bien avec la référence référence dans Java.



1
votes

La taille de la matrice n'est jamais réduite automatiquement. Il est très rare d'avoir une liste d'abord remplie d'un grand nombre d'éléments, puis de l'avoir vidé mais toujours gardé. Et garder à l'esprit qu'il y a eu suffisamment de mémoire pour tenir la liste (qui consiste uniquement à références) et à ses éléments - il est peu probable que la mémoire consommée par la liste vide serait un problème.

Si vous rencontrez vraiment un algorithme bizarre suffisamment que cela devienne un problème, vous pouvez toujours libérer la mémoire en appelant trimtosize () manuellement.


0 commentaires

4
votes

Une arracheliste ne rétrécit pas automatiquement, autant que je sache. Cependant, vous pouvez dire quelque chose comme: xxx

note, la quantité de mémoire disponible ne changera probablement pas jusqu'à ce que GC fonctionne à nouveau.


1 commentaires

J'ai fini par copier le code source ArrayList dans mon projet de test et ajouté une méthode getcapacité () pour accéder au tableau sous-jacent. Comme vous l'avez prédit, il ne dépasse jamais si je le demande manuellement par trimtosize (). Merci.