Listendatenstruktur [Java / Scala]
Neulich nahm ich an Einführung in die Scala- und Funktionsprogrammierung aus der Implementierung der Liste teil. Ich habe ein wenig über Struktur gelernt. Lassen Sie es uns zusammen mit der Java List-Datenstruktur überprüfen.
Java-Liste
Apropos Java-Liste, ich denke, es gibt ArrayList und LinkedList, daher möchte ich einen Blick auf den Inhalt werfen. Das Folgende ist nur ein Auszug aus dem Teil, der sich auf das Hinzufügen und Erfassen von Elementen (Daten) bezieht.
ArrayList ArrayList enthält intern Elementinformationen als Array.
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;
}
/*Unterlassung*/
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];
}
/*Unterlassung*/
}
elementData ist ein Array von Elementinformationen. Elemente werden mit der Methode add hinzugefügt und die Eingabeelemente werden in elementData gespeichert. Das Interessante ist, wie das Array erweitert wird. Wenn Sie jedoch das erste Element in elementData speichern, wird standardmäßig ein Array mit einer Länge von 10 erstellt. Wenn Sie danach versuchen, ein Element zu speichern, das die Länge von elementData überschreitet, wird ein Array mit einer 1,5-fachen Länge von elementData erstellt und die Daten werden an dieses übertragen. Sie reduzieren die Kosten für das Erstellen einer Array-Instanz, indem Sie ein Spiel im Array erstellen.
int newCapacity = oldCapacity + (oldCapacity >> 1) // 1.Holen Sie sich 5 mal länger
Um das Element abzurufen, wird der Index des Arrays mithilfe der Indexeingabe durch die get-Methode direkt referenziert, sodass nicht nur für den sequentiellen Zugriff, sondern auch für den wahlfreien Zugriff eine hohe Leistung erzielt wird. Ich habe keine Ahnung von dem Bild, aber ich habe ein Bild gemacht, also werde ich es posten.
LinkedList
LinkedList verwaltet Elemente in einer inneren Klasse namens Node. Die LinkedList selbst enthält nur die Informationen des ersten und des letzten Knotens, und der Knoten selbst enthält die Informationen des vorherigen und des nächsten Knotens. Jedes Mal, wenn ein Element mit der add-Methode hinzugefügt wird, wird ein neuer Knoten erstellt, und die neuen Knoteninformationen werden im nächsten des nachfolgenden Knotens gespeichert, und die nachfolgenden Knoteninformationen werden im vorherigen des neuen Knotens gespeichert.
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;
}
/*Unterlassung*/
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;
}
}
/*Unterlassung*/
}
Um das Element abzurufen, folgen Sie dem von der get-Methode eingegebenen Index von Anfang bis Ende, je nachdem, welcher Wert näher liegt. Dies ist der Grund, warum es im Gegensatz zu ArrayList für den Direktzugriff anfällig ist. Wenn Sie im Bild unten das Element von node_3 erhalten möchten, müssen Sie von node_1 folgen.
Verwenden Sie ArrayList und LinkedList ordnungsgemäß
Dies ist meine persönliche Meinung, und ich würde mich über jeden Rat von jemandem freuen, der mit dem Algorithmus vertraut ist, aber ich frage mich, ob ArrayList die Basis ist. ArrayList ermöglicht den schnellen Zugriff auf Elemente und benötigt weniger Speicher als LinkedList. Wenn Sie jedoch eine große Datenmenge in der Liste haben und das Hinzufügen und Löschen von Elementen (z. B. eine Rolle wie eine Warteschlange) wiederholen möchten, sollten Sie LinkedList verwenden. Dies liegt daran, dass im Fall von ArrayList die Verarbeitung von Elementbewegungen erfolgt, wenn aufgrund des Löschens von Elementen oder beim Hinzufügen zwischen Elementen Platz im Array vorhanden ist. Im Fall von LinkedList ist es effizient, da nur die Informationen des vorherigen und des nächsten Knotens neu geschrieben werden.
Scala-Liste
In Scalas Liste werden Elementinformationen durch Kopf und Schwanz dargestellt. Wenn man nur den Namen betrachtet, scheint er der LinkedList von Java ähnlich zu sein, hat jedoch eine völlig andere Struktur. Kopf ist die Information des ersten Elements, Schwanz ist die Elementinformation, die nicht der Anfang ist, sondern wird im Listentyp ausgedrückt .. Erstens hat Scalas Liste ein unveränderliches Design, und anstatt wie in Java Änderungen am List-Objekt selbst vorzunehmen, wird nach der Änderung eine neue Liste erstellt.
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)
/*Unterlassung*/
}
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 }
/*Unterlassung*/
}
Führen Sie in Scala das Programm aus und überprüfen Sie Kopf und Schwanz. Fügen Sie zunächst einige Elemente zur Liste hinzu. Elemente werden mit der :: -Methode hinzugefügt.
//(1)Listenerstellung
val list1 = List("ABC")
println(list1) // List(ABC)
//(2)Element hinzufügen
val list2 = "DEF"::list1
println(list2) // List(DEF, ABC)
//(3)Element hinzufügen
val list3 = list2.::("GHI")
println(list3) // List(GHI, DEF, ABC)
(2) und (3) verwenden dieselbe Methode, obwohl die Notation unterschiedlich ist. Im Gegensatz zu Java handelt es sich beim Hinzufügen eines Elements ohne Angabe eines Index um ein Bild des Hinzufügens eines Elements am Anfang, da Java am Ende ein Element hinzufügt. Schauen wir uns den Kopf und den Schwanz der Objekte (1) bis (3) an.
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)
Immerhin gibt das head-Element das erste Element zurück, und das tail-Element gibt die anderen Elemente als den Anfang als Liste zurück. Ich habe auch ein Bild davon gemacht, also schauen Sie bitte, wenn Sie möchten.
Übrigens, wenn Sie den Klassennamen von der Instanz erhalten und einen Blick darauf werfen
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
Es ist geworden. Dies scheint die Klasse scala.collection.immutable. :: Zu sein, und es scheint, dass diese Klasse cons heißt (wahrscheinlich der Konstruktor). Wenn Sie sich die List. :: () -Methode ansehen, können Sie sehen, dass die :: -Instanz erstellt wird, das Argument auf head gesetzt ist und die List selbst tail ist.
Methode
Ich werde ein wenig über die Methode schreiben. Das Schreiben ist jedoch nur eine Liste von Dingen, die ich persönlich nützlich finde.
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
Die meisten gängigen Prozesse werden als Methoden definiert, was es sehr einfach macht (es gibt viele andere nützliche Methoden). Scala hat auch Typinferenz und Taples, daher denke ich, dass das Programmieren intuitiver und effizienter ist als Java, und vor allem macht das Schreiben Spaß.
Schließlich
Schon ein paar Blicke auf die Standardbibliothek können sehr lehrreich sein. Die Standardbibliothek steckt voller genialer und künstlerischer Designs und Techniken. Von diesen Punkten aus scheint es gut zu sein, objektorientierte Programmierung in Java und funktionale Programmierung in Scala zu verstehen und zu lernen.
Recommended Posts