L'autre jour, j'ai participé à Introduction to Scala & Functional Programming Learned from the Implementation of List J'ai étudié un peu la structure. Passons en revue avec la structure de données Java List.

Liste Java

En parlant de Java List, je pense qu'il y a ArrayList et LinkedList, je voudrais donc jeter un coup d'œil au contenu. Ce qui suit est un extrait de seulement la partie liée à l'ajout et à l'acquisition d'éléments (données).

ArrayList ArrayList contient en interne les informations sur les éléments sous forme de tableau.

`ArrayList.class`


package java.util;

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    transient Object[] elementData;

    private int size;

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /*Omission*/

    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);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    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);
    }

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    E elementData(int index) {
        return (E) elementData[index];
    }

    /*Omission*/

}

elementData est un tableau d'informations sur les éléments. Les éléments sont ajoutés avec la méthode add et les éléments d'entrée sont stockés dans elementData. La chose intéressante est de savoir comment étendre le tableau, mais lorsque vous stockez le premier élément dans elementData, un tableau de 10 longueurs est créé par défaut. Après cela, lorsque vous essayez de stocker un élément qui dépasse la longueur de elementData, un tableau d'une longueur 1,5 fois celle de elementData est créé et les données sont transférées vers ce tableau. Vous réduisez le coût de création d'une instance de tableau en créant du jeu dans le tableau.

int newCapacity = oldCapacity + (oldCapacity >> 1) // 1.Obtenez 5 fois plus

Pour obtenir l'élément, l'index du tableau est directement référencé à l'aide de l'entrée d'index par la méthode get, de sorte que des performances élevées sont obtenues non seulement pour l'accès séquentiel, mais également pour l'accès aléatoire. Je n'ai aucune idée de la photo, mais j'ai fait une image, alors je la posterai. LinkedList LinkedList gère les éléments dans une classe interne appelée Node. La LinkedList elle-même ne contient que les informations du premier nœud et du dernier nœud, et le nœud lui-même contient les informations des nœuds précédents et suivants. Chaque fois qu'un élément est ajouté avec la méthode add, un nouveau nœud est créé, et les nouvelles informations de nœud sont stockées dans le nœud suivant du nœud de fin, et les informations de nœud de fin sont stockées dans le précédent du nouveau nœud.

`LinkedList`


package java.util;

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{

    transient int size = 0;

    transient Node<E> first;

    transient Node<E> last;

    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

      /*Omission*/

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

      /*Omission*/

}

Pour obtenir l'élément, suivez l'index entré par la méthode get depuis le début ou la fin, selon celui qui est le plus proche. C'est la raison pour laquelle il est vulnérable à l'accès aléatoire contrairement à ArrayList. Dans l'image ci-dessous, lorsque vous souhaitez obtenir l'élément de node_3, vous devez suivre à partir de node_1.

Utiliser correctement ArrayList et LinkedList

Ceci est mon opinion personnelle, et j'apprécierais tout conseil de quelqu'un qui connaît l'algorithme, mais je me demande si ArrayList est la base. ArrayList permet un accès rapide aux éléments et utilise moins de mémoire que LinkedList. Cependant, si vous souhaitez avoir une grande quantité de données dans la liste et répéter l'ajout et la suppression d'éléments (par exemple, un rôle comme une file d'attente), vous devez utiliser LinkedList. En effet, dans le cas de ArrayList, le traitement du mouvement d'élément se produit lorsqu'il y a de l'espace dans le tableau en raison de la suppression d'éléments ou lors de l'ajout entre les éléments. Dans le cas de LinkedList, il est efficace car il ne réécrit que les informations des nœuds précédents et suivants.

Liste Scala

Dans la liste de Scala, les informations sur les éléments sont représentées par la tête et la queue. En regardant uniquement le nom, il semble être similaire à LinkedList de Java, mais en fait il a une structure complètement différente, head est l'information du premier élément, tail est l'élément information autre que le début est exprimé en type List .. En premier lieu, la liste de Scala a une conception immuable, et au lieu d'apporter des modifications à l'objet List lui-même comme en Java, elle est conçue pour créer une nouvelle liste après la modification.

`List.scala`


package scala
package collection
package immutable

sealed abstract class List[+A] extends AbstractSeq[A]
                                  with LinearSeq[A]
                                  with Product
                                  with GenericTraversableTemplate[A, List]
                                  with LinearSeqOptimized[A, List[A]]
                                  with Serializable {
  override def companion: GenericCompanion[List] = List

  import scala.collection.{Iterable, Traversable, Seq, IndexedSeq}

  def isEmpty: Boolean
  def head: A
  def tail: List[A]

  def ::[B >: A](x: B): List[B] =
    new scala.collection.immutable.::(x, this)

    /*Omission*/

}

final case class ::[B](overridevalhead:B,private[scala]vartl:List[B]) extends List[B] {
  override def tail : List[B] = tl
  override def isEmpty: Boolean = false
}

object List extends SeqFactory[List] {
  /** $genericCanBuildFromInfo */
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, List[A]] =
    ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]

  def newBuilder[A]: Builder[A, List[A]] = new ListBuffer[A]

  override def empty[A]: List[A] = Nil

  override def apply[A](xs:A*): List[A] = xs.toList
  
  private[collection] val partialNotApplied = new Function1[Any, Any] { def apply(x: Any): Any = this }

    /*Omission*/

}

Dans Scala, exécutez réellement le programme et vérifiez la tête et la queue. Tout d'abord, ajoutez quelques éléments à la liste. Les éléments sont ajoutés à l'aide de la méthode ::.

//(1)Création de liste
val list1 = List("ABC")
println(list1) // List(ABC)
//(2)Ajouter un élément
val list2 = "DEF"::list1
println(list2) // List(DEF, ABC)
//(3)Ajouter un élément
val list3 = list2.::("GHI")
println(list3) // List(GHI, DEF, ABC)

(2) et (3) utilisent la même méthode, bien que la notation soit différente. Lors de l'ajout normal sans spécifier d'index, il s'agit d'une image d'ajout d'un élément au début contrairement à Java, car Java ajoute un élément à la fin. Jetons un coup d'œil à la tête et à la queue des objets (1) à (3), respectivement.

List(list1, list2, list3).zip(Range(1, 4)).foreach { 
  case (x, i) => println(s"list${i} => head:${x.head} tail:${x.tail}") 
}
//  list1 => head:ABC tail:List()
//  list2 => head:DEF tail:List(ABC)
//  list3 => head:GHI tail:List(DEF, ABC)

Après tout, l'élément head renvoie le premier élément et la queue renvoie les éléments autres que le début sous forme de liste. J'en ai également fait une image, alors jetez un œil si vous le souhaitez.

Au fait, si vous obtenez le nom de classe de l'instance et jetez un œil

val list4 = List("ABC")
println(list4.getClass) // class scala.collection.immutable.$colon$colon
val list5 = Array("ABC").toList
println(list5.getClass) // class scala.collection.immutable.$colon$colon

Il est devenu. Cela semble être la classe scala.collection.immutable. ::, et il semble que cette classe s'appelle cons (probablement le constructeur). Si vous regardez la méthode List. :: (), vous pouvez voir que l'instance :: est créée, que l'argument est défini sur head et que la List elle-même est tail.

Méthode

J'écrirai un peu sur la méthode. Cela dit, l'écriture n'est qu'une liste de choses que je trouve personnellement utiles.

val range = Range(0, 10).toList
println(range) // List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

val fill = List.fill(10)(5)
println(fill) // List(5, 5, 5, 5, 5, 5, 5, 5, 5, 5)

val rangefill = range.zip(fill).map { case (x, y) => x * y }
println(rangefill) // List(0, 5, 10, 15, 20, 25, 30, 35, 40, 45)

val flatmap = List(List(1, 2, 3), List(3, 4, 5), List(5, 6, 7)).flatten.distinct
println(flatmap) // List(1, 2, 3, 4, 5, 6, 7)

val reduce = List("ABC", "DEF", "GHI").reduceLeft(_+_)
println(reduce) // ABCDEFGHI

La plupart des processus courants sont définis comme des méthodes, ce qui les rend très faciles (il existe de nombreuses autres méthodes utiles). Scala a aussi l'inférence de type et les taples, donc je pense que c'est plus intuitif et efficace à programmer que Java, et surtout, c'est amusant à écrire.

finalement

Même quelques regards sur la bibliothèque standard peuvent être très instructifs. La bibliothèque standard regorge de conceptions et de techniques géniales et artistiques. Il semble bon de comprendre et d'apprendre la programmation orientée objet en Java et la programmation fonctionnelle dans Scala à partir de ces points.

Liste de la structure de données [Java / Scala]