[JAVA] Liste et cours heureux
introduction
J'ai reçu un commentaire dans Article précédent, donc j'écrirai que j'étais un peu intéressé à écrire. À propos des classes liées à Java List, quand je regarde le code source des autres alors que je travaille habituellement, je me demande s'il y a peu de gens qui en sont conscients.
Classes sous Liste et ce qui est décrit dans cet article
Pour la classe qui implémente l'interface List, consultez «Toutes les classes d'implémentation connues» dans ici. Comme vous pouvez le voir, il y en a beaucoup. Parmi eux, j'écrirai sur les trois classes suivantes, qui sont relativement célèbres (?). · Liste des tableaux ・ LinkedList ・ Tableaux $ ArrayList (Je n'ai jamais utilisé autre chose que ceux-ci, donc je ne suis pas familier avec cela)
ArrayList initialCapacity Vous savez qu'ArrayList est une classe que vous utilisez beaucoup, mais avez-vous déjà été au courant de initialCapacity? C'est probablement la meilleure façon d'écrire une instance ArrayList.
Capacity.java
List<?> list = new ArrayList<>()
D'autre part, saviez-vous que vous pouvez instancier de cette manière?
Capacity.java
List<?> list = new ArrayList<>(100)
Int 100 est spécifié comme argument du constructeur. Ce 100 est le initialCapacity. Spécifie le nombre d'éléments à initialiser dans ArrayList. Et si je ne spécifie pas d'argument? Jetons un œil à la source de ArrayList.
ArrayList.classe (extrait: constructeur 1)
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
D'une manière ou d'une autre, un tableau vide est stocké dans elementData. Je ne sais pas si c'est tout. Ensuite, jetons un coup d'œil au contenu de la méthode add ().
ArrayList.classe (extrait: autour d'ajouter)
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
Immédiatement après add (), la méthode ensureCapacityInternal () est appelée. Dans ensureCapacityInternal (), la méthode ensureExplicitCapacity () est appelée après avoir défini minCapacity. Si vous n'avez pas défini initialCapacity dans le constructeur, comme vous l'avez vu précédemment, elementData est défini sur DEFAULTCAPACITY_EMPTY_ELEMENTDATA (un tableau vide), donc la condition de l'instruction if est satisfaite et "minCapacity = Math.max (DEFAULT_CAPACITY, minCapacity)" est définie. C'est fait. Par conséquent, minCapacity est défini sur 10 (DEFAULT_CAPACITY) et transmis à ensureExplicitCapacity (). ensureExplicitCapacity () est une méthode pour sécuriser la capacité du tableau. En d'autres termes, si aucun argument n'est défini dans le constructeur de ArrayList, les éléments stockés dans ArrayList seront gérés par un tableau de 10 éléments. Alors qu'en est-il du constructeur pour ceux qui spécifient initialCapacity?
ArrayList.classe (extrait 3)
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
Si vous spécifiez un entier autre que 0, un tableau pour le nombre d'éléments spécifié est généré au lieu d'un tableau vide. Le comportement lorsque add () est fondamentalement le même, sauf qu'il ne passe pas par l'instruction if de la méthode ensureCapacityInternal ().
Que signifie spécifier initialCapacity?
Que signifie spécifier initialCapacity? Vous pouvez voir cela en regardant le comportement lors de l'ajout de plus d'éléments que le nombre spécifié par initialCapacity. Il s'agit de la partie implémentation (suite de ensureCapacityInternal ()).
ArrayList.java (extrait)
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
Dans la méthode ensureExplicitCapacity (), la méthode grow () est appelée lorsque la condition est remplie. Le point est ʻint newCapacity = oldCapacity + (oldCapacity >> 1); ʻ de la méthode grow (), et si le nombre d'éléments sécurisés par initialCapacity est dépassé en ajoutant des éléments, la capacité est multipliée par 1,5 (fraction). Troncature).
- ">>" est une opération de décalage. Voir ici Alors, comment le nombre d'éléments dans elementData change-t-il si vous ajoutez un total de 100 éléments, un à la fois, à un ArrayList avec initialCapacity défini sur 10?
Valeur initiale: 10 11ème élément ajouté: 10 * 1.5 = 15 16e élément ajouté: 15 * 1,5 = 22 23ème élément ajouté: 22 * 1.5 = 33 Ajout du 34e élément: 33 * 1.5 = 49 Ajout du 50e élément: 49 * 1,5 = 73 Ajout du 74ème élément: 73 * 1.5 = 109 J'ai finalement pu ajouter 100 éléments ici.
Différence de performances en fonction du paramètre initialCapacity
Ce mouvement est susceptible de causer des frais généraux, n'est-ce pas? Combien ça coûte? J'ai en fait mesuré le temps d'exécution lorsque add () en boucle 100 000 données. C'est le programme utilisé pour la mesure réelle.
DefaultListSize.java
import java.util.ArrayList;
import java.util.List;
public class DefaultListSize {
private static final int CNT = 100000;
public static void main(String... args) {
//initialCapacity non spécifié
List<Integer> defaultList = new ArrayList<>();
long startDefautl = System.currentTimeMillis();
for (int i = 0; i < CNT; i++) {
defaultList.add(i);
}
long endDefautl = System.currentTimeMillis();
System.out.println("Temps d'exécution (millisecondes):" + (endDefautl - startDefautl));
//Spécification initialCapacity
List<Integer> list = new ArrayList<>(CNT);
long start = System.currentTimeMillis();
for (int i = 0; i < CNT; i++) {
list.add(i);
}
long end = System.currentTimeMillis();
System.out.println("Temps d'exécution (millisecondes):" + (end - start));
}
}
Résultat d'exécution
Temps d'exécution (millisecondes):4
Temps d'exécution (millisecondes):1
Si vous n'avez pas spécifié initialCapacity, il était de 4 millisecondes et si vous avez spécifié 100 000, il était de 1 milliseconde. À propos, lorsque 10 millions ont été spécifiés, c'était 731 millisecondes et 258 millisecondes. Je ne peux rien dire sur le nombre de secondes car il est lié aux spécifications du PC, mais vous pouvez voir qu'en spécifiant initialCapacity, il n'y a pas de traitement supplémentaire et la vitesse est augmentée en conséquence. Si vous savez que vous allez gérer une grande quantité de données, il semble préférable de le spécifier correctement.
LinkedList
Fonctionnalité
Vient ensuite la LinkedList. LinkedList est bon pour ajouter et supprimer des éléments, mais ce n'est pas bon pour l'accès aléatoire. L'accès aléatoire est «list.get (i)» au niveau du code source. La cause de cette fonctionnalité est la façon dont les éléments sont gérés. Il est géré en reliant le i-ème élément aux i-1er et i + 1ème éléments. Pour obtenir l'élément, suivez le lien depuis le début ou la fin, et pour le supprimer, remplacez simplement le lien.
Je pense que la différence sera claire lorsque vous la comparerez avec ArrayList. ArrayList est bon pour l'accès aléatoire car vous pouvez obtenir des éléments directement en utilisant index.
D'autre part, si vous le supprimez, vous devez reconstruire le tableau, ce qui ajoute une surcharge.
Différences de comportement d'accès aléatoire
En raison de cette fonctionnalité, ArrayList et LinkedList se comportent différemment lors d'un accès aléatoire. Dans le cas de ArrayList, même si vous accédez de manière aléatoire avec list.get (i), vous pouvez obtenir l'élément immédiatement, vous pouvez donc répondre immédiatement. C'est l'image.
Dans le cas de LinkedList, l'élément cible ne peut être obtenu que si les éléments sont tracés dans l'ordre à partir du premier élément. Si vous écrivez list.get (4), vous pouvez enfin atteindre l'élément cible en suivant l'ordre de 1 → 2 → 3 → 4. C'est l'image.
LinkedList peut également être analysé dans l'ordre inverse, donc list.get (7) dans l'exemple ci-dessus suivra sûrement dans l'ordre 10 → 9 → 8 → 7.
Quelles sont les performances lors de la mise en boucle d'une grande quantité de données?
Jusqu'à ce point, je pense que c'est "Hmm. Alors, que faire si vous parcourez beaucoup de données et list.get (i)?
Plus précisément, si vous avez une classe comme celle-ci, savez-vous ce qui se passe si vous passez une LinkedList avec une grande quantité de données en argument lors de l'appel de cette méthode?
Le fait est que list.get (i) est fait en boucle.
ListSizeLoop.java
class ListSizeLoop {
public void listSizeLoop(List<String> list) {
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
}
J'ai trouvé cet article. C'est exactement ça. Cela peut arriver. Une histoire que je devais faire une pause si j'utilisais LinkedList avec un sentiment léger
Que devrais-je faire?
Comme mentionné dans l'article précédent, utilisez l'extension pour (ou Iterator) au lieu de boucler avec list.size (). Iterator est développé en interne à l'aide de l'extension for for List (pour être exact, pour les classes qui implémentent l'interface Iterable). Iterator est l'un des modèles de conception et est une interface spécialisée pour le traitement séquentiel. Cela seul évite l'accès aléatoire. Cela peut arriver si vous bouclez en utilisant list.size (), alors utilisez l'extension pour à moins que vous n'ayez une raison claire de le faire.
Arrays$ArrayList
Arrays $ ArrayList est une liste de longueur fixe
Le dernier est Arrays $ ArrayList.
Il s'appelle ArrayList, mais il est différent du célèbre java.util.ArrayList. Il y a une classe interne nommée ArrayList dans la classe java.util.Arrays qui implémente l'interface List (" $ "est un mot réservé Java pour indiquer qu'il s'agit d'une classe interne).
Il s'agit d'une liste pratique pour convertir un tableau en liste ou pour spécifier des éléments à l'avance lors de la création d'une instance, et suppose une longueur fixe.
L'utilisation est la suivante.
ArraysAsList.java
import java.util.Arrays;
import java.util.List;
public class ArraysAsList {
public static void main(String... args) {
String[] strList = new String[3];
strList[0] = "a";
strList[1] = "b";
strList[2] = "c";
//Convertir un tableau en liste
List<String> list1 = Arrays.asList(strList);
for (String str : list1) {
System.out.println(str);
}
//Générer une liste qui contient les éléments du début
List<String> list2 = Arrays.asList("d", "e", "f");
for (String str : list2) {
System.out.println(str);
}
}
}
Que se passe-t-il lorsque j'ajoute ()?
J'ai mentionné plus tôt que cela suppose une longueur fixe, mais que se passe-t-il lorsque vous ajoutez ()?
ArraysAsList2.java
import java.util.Arrays;
import java.util.List;
public class ArraysAsList2 {
public static void main(String... args) {
//Ajouter après instanciation()Appel de méthode
List<String> list = Arrays.asList("d", "e", "f");
list.add("a");
for (String str : list) {
System.out.println(str);
}
}
}
Résultat d'exécution
Exception in thread "main" java.lang.UnsupportedOperationException
at java.util.AbstractList.add(AbstractList.java:148)
at java.util.AbstractList.add(AbstractList.java:108)
at ArraysAsList2.main(ArraysAsList2.java:8)
Une exception UnsupportedOperationException s'est produite. Jetons un coup d'œil à Arrays $ ArrayList.
Arrays.java
public class Arrays {
@SafeVarargs
@SuppressWarnings("varargs")
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
/**
* @serial include
*/
private static class ArrayList<E> extends AbstractList<E>
implements RandomAccess, java.io.Serializable
{
private static final long serialVersionUID = -2764017481108945198L;
private final E[] a;
ArrayList(E[] array) {
a = Objects.requireNonNull(array);
}
@Override
public int size() {
return a.length;
}
@Override
public Object[] toArray() {
return a.clone();
}
@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
int size = size();
if (a.length < size)
return Arrays.copyOf(this.a, size,
(Class<? extends T[]>) a.getClass());
System.arraycopy(this.a, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
@Override
public E get(int index) {
return a[index];
}
@Override
public E set(int index, E element) {
E oldValue = a[index];
a[index] = element;
return oldValue;
}
@Override
public int indexOf(Object o) {
E[] a = this.a;
if (o == null) {
for (int i = 0; i < a.length; i++)
if (a[i] == null)
return i;
} else {
for (int i = 0; i < a.length; i++)
if (o.equals(a[i]))
return i;
}
return -1;
}
@Override
public boolean contains(Object o) {
return indexOf(o) != -1;
}
@Override
public Spliterator<E> spliterator() {
return Spliterators.spliterator(a, Spliterator.ORDERED);
}
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
for (E e : a) {
action.accept(e);
}
}
@Override
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
E[] a = this.a;
for (int i = 0; i < a.length; i++) {
a[i] = operator.apply(a[i]);
}
}
@Override
public void sort(Comparator<? super E> c) {
Arrays.sort(a, c);
}
}
}
Je ne trouve pas la méthode add (). Est-ce une classe supérieure? AbstractList est étendu, alors jetons un coup d'œil.
AbstractList.java
public boolean add(E e) {
add(size(), e);
return true;
}
/**
* {@inheritDoc}
*
* <p>This implementation always throws an
* {@code UnsupportedOperationException}.
*
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
Ça y est. Je lance une exception UnsupportedOperationException sans poser de questions. AbstractList est également ArrayList, Vector et [AbstractSequentialList](https: // docs. oracle.com/javase/jp/8/docs/api/java/util/AbstractSequentialList.html) s'étend également. LinkedList étend AbstractSequentialList, donc il est indirectement sous AbstractList. Je ne sais pas si vous l'écrivez en lettres, mais si vous regardez la figure ci-dessous, vous pouvez voir que c'est sous AbstractList.
Différence avec java.util.ArrayList (côté implémentation)
Jetons un coup d'œil à ArrayList comme exemple d'une classe qui étend AbstractList autre que Arrays $ ArrayList.
ArrayList.java (extrait de l'ajout d'une partie)
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
Vous remplacez la méthode add (). Puisque java.util.ArrayList remplace add () de AbstractList, UnsupportedOperationException ne se produit pas et le traitement implémenté est effectué. Arrays $ ArrayList ne remplace pas la méthode add (), donc une exception UnsupportedOperationException est levée. Même s'ils portent le même nom, ArrayList, ils sont complètement différents ... AbstractList est une implémentation partielle de l'interface List. En implémentant le minimum requis, la partie qui doit être implémentée en tant que classe concrète est réduite, mais si vous ne remplacez pas set (), add (), remove (), UnsupportedOperationException sera levée. .. La même chose se produit car Arrays $ ArayList ne remplace pas remove () ni add (). Puisque set () est remplacé, vous pouvez remplacer un élément existant par un autre en appelant cette méthode.
Si vous souhaitez convertir un tableau en une liste de longueur variable
Arrays $ ArayList a une longueur fixe car add () et remove () ne peuvent pas être appelés. Si vous souhaitez convertir un tableau en une liste de longueur variable, procédez comme suit:
ArraysAsList3.java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ArraysAsList3 {
public static void main(String... args) {
String[] strList = new String[3];
strList[0] = "a";
strList[1] = "b";
strList[2] = "c";
//Convertir un tableau en liste via le constructeur ArrayList
List<String> list = new ArrayList<>(Arrays.asList(strList));
for (String str : list) {
System.out.println(str);
}
}
}
Avec la description List <String> list = new ArrayList <> (Arrays.asList (strList));, la conversion est effectuée dans l'ordre Array → Arrays $ ArrayList → ArrayList.
En plus de l'initialCapacity introduit précédemment, il existe un autre constructeur qui reçoit une Collection dans le constructeur ArrayList. Vous pouvez utiliser ce constructeur pour convertir ʻArrays $ ArrayList en java.util.ArrayList`.
AbstractList étend AbstractCollection et AbstractCollection implémente Collection, vous pouvez donc passer Arrays $ ArrayList comme argument à ce constructeur.
Je pense que c'est aussi plus facile à comprendre si vous regardez la figure précédente.
L'implémentation du constructeur pour ArrayList qui reçoit Collection est la suivante.
ArrayList (extrait partiel du constructeur)
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[](see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
Quand je commençais à peine à utiliser Java, j'ai mal compris Arrays $ ArrayList comme étant identique à java.util.ArrayList et j'étais assez confus, alors je l'ai écrit.
À la fin
J'ai l'impression d'avoir beaucoup écrit sur ce que j'ai trouvé à propos de List. J'espère que vous avez remarqué une seule chose, "Oh, c'est vrai!?" c'est tout.
Recommended Posts