Analisis kaedah traversal koleksi Java (prinsip pelaksanaan, prestasi algoritma, peristiwa yang berkenaan)_kemahiran javascript

Ikhtisar

Bahasa Java menyediakan satu set rangka kerja pengumpulan data, yang mentakrifkan beberapa jenis data abstrak seperti Senarai dan Set Setiap jenis data abstrak mempunyai pelaksanaan tertentu, dan lapisan bawah menggunakan kaedah pelaksanaan yang berbeza, seperti ArrayList dan LinkedList.

Selain itu, Java juga menyediakan beberapa cara berbeza untuk merentasi pengumpulan data. Pembangun mesti memahami dengan jelas ciri, situasi yang berkenaan dan prestasi setiap kaedah traversal pada pelaksanaan asas yang berbeza. Mari analisa kandungan ini secara terperinci di bawah.

Bagaimanakah elemen data disimpan dalam ingatan?

Elemen data disimpan dalam ingatan, dan terdapat dua kaedah penyimpanan utama:

1. Storan berjujukan, Akses Rawak (Akses Terus):

Dengan cara ini, elemen data bersebelahan disimpan dalam alamat memori bersebelahan dan keseluruhan alamat memori adalah berterusan. Alamat memori boleh dikira terus berdasarkan kedudukan elemen dan dibaca terus. Purata kerumitan masa membaca elemen pada kedudukan tertentu ialah O(1). Biasanya, hanya koleksi yang dilaksanakan berdasarkan tatasusunan yang mempunyai ciri ini. Java diwakili oleh ArrayList.

2. Storan rantai, Akses Berjujukan:

Dengan cara ini, setiap elemen data tidak perlu berada dalam kedudukan bersebelahan dalam memori Setiap elemen data mengandungi alamat memori elemen seterusnya. Alamat memori tidak boleh dikira secara langsung berdasarkan kedudukan elemen, elemen hanya boleh dibaca mengikut urutan. Purata kerumitan masa membaca elemen pada kedudukan tertentu ialah O(n). Terutamanya diwakili oleh senarai terpaut.

Diwakili oleh LinkedList di Java.

Apakah kaedah traversal yang disediakan di Jawa?

1. Tradisional untuk lintasan gelung, berdasarkan pembilang:

Traverser mengekalkan kaunter di luar koleksi, kemudian membaca elemen pada setiap kedudukan dalam urutan dan berhenti apabila elemen terakhir dibaca. Perkara utama ialah membaca elemen mengikut kedudukannya. Ini juga merupakan kaedah traversal koleksi yang paling primitif.

ditulis sebagai:

for (int i = 0; i < list.size(); i++) {
list.get(i);
} 

2. Pelintasan Peulang, Pendahulu:

Iterator pada asalnya ialah corak reka bentuk OO Tujuan utamanya adalah untuk melindungi ciri-ciri pengumpulan data yang berbeza dan menyatukan antara muka untuk merentasi koleksi. Sebagai bahasa OO, Java secara semula jadi menyokong mod Iterator dalam Koleksi.

ditulis sebagai:

Iterator iterator = list.iterator();
while (iterator.hasNext()) {
iterator.next();
}

3. setiap lintasan gelung:

Perisai diisytiharkan secara eksplisit sebagai Iterator dan pembilang.

Kelebihan: Kod ini ringkas dan kurang terdedah kepada ralat.

Kelemahan: Ia hanya boleh melakukan traversal mudah, dan tidak boleh mengendalikan (memadam, menggantikan) pengumpulan data semasa proses traversal.

ditulis sebagai:

for (ElementType element : list) {
}

Apakah prinsip pelaksanaan setiap kaedah traversal?

1. Tradisional untuk lintasan gelung, berdasarkan pembilang:

Traverser mengekalkan kaunter di luar koleksi, kemudian membaca elemen pada setiap kedudukan dalam urutan dan berhenti apabila elemen terakhir dibaca. Perkara utama ialah membaca elemen mengikut kedudukannya.

2. Pelintasan Peulang, Pendahulu:

Setiap pengumpulan data yang dilaksanakan secara khusus secara amnya perlu menyediakan Iterator yang sepadan. Berbanding dengan gelung tradisional, Iterator menghapuskan kaunter traversal yang jelas. Oleh itu, Iterator berdasarkan koleksi yang disimpan secara berurutan boleh terus mengakses data mengikut kedudukan. Pelaksanaan biasa Iterator berdasarkan koleksi storan berantai memerlukan menyimpan kedudukan yang dilalui semasa. Kemudian gerakkan penunjuk ke hadapan atau ke belakang berdasarkan kedudukan semasa.

3. setiap lintasan gelung:

Menurut kod bait yang dinyahkompilasi, boleh didapati bahawa foreach juga dilaksanakan secara dalaman menggunakan Iterator, tetapi pengkompil Java menjana kod ini untuk kami.

Apakah prestasi setiap kaedah traversal untuk kaedah penyimpanan yang berbeza?

1. Tradisional untuk lintasan gelung, berdasarkan pembilang:

Oleh kerana ia berdasarkan kedudukan unsur, ia dibaca mengikut kedudukan. Jadi kita boleh tahu bahawa untuk penyimpanan berjujukan, kerana purata kerumitan masa membaca elemen pada kedudukan tertentu ialah O(1), purata kerumitan masa merentasi keseluruhan koleksi ialah O(n). Untuk storan berantai, kerana purata kerumitan masa membaca elemen di lokasi tertentu ialah O(n), purata kerumitan masa merentasi keseluruhan koleksi ialah O(n2) (n kuasa dua).

Kod untuk membaca ArrayList mengikut kedudukan: baca terus mengikut kedudukan elemen.

transient Object[] elementData;
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
} 

Kod untuk membaca LinkedList mengikut kedudukan: Setiap kali anda perlu membaca ke belakang bermula dari elemen ke-0. Malah, ia juga telah membuat pengoptimuman kecil secara dalaman.

transient int size = 0;
transient Node<E> first;
transient Node<E> last;
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int 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;
}
}

2、迭代器遍历，Iterator：

那么对于RandomAccess类型的集合来说，没有太多意义，反而因为一些额外的操作，还会增加额外的运行时间。但是对于Sequential Access的集合来说，就有很重大的意义了，因为Iterator内部维护了当前遍历的位置，所以每次遍历，读取下一个位置并不需要从集合的第一个元素开始查找，只要把指针向后移一位就行了，这样一来，遍历整个集合的时间复杂度就降低为O(n)；

（这里只用LinkedList做例子）LinkedList的迭代器，内部实现，就是维护当前遍历的位置，然后操作指针移动就可以了：

代码：

public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}

3、foreach循环遍历：

分析Java字节码可知，foreach内部实现原理，也是通过Iterator实现的，只不过这个Iterator是Java编译器帮我们生成的，所以我们不需要再手动去编写。但是因为每次都要做类型转换检查，所以花费的时间比Iterator略长。时间复杂度和Iterator一样。

使用Iterator的字节码：

Code:
new # // class java/util/ArrayList
dup
invokespecial # // Method java/util/ArrayList."<init>":()V
astore_
aload_
invokeinterface #, // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
astore_
goto 
aload_
invokeinterface #, // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
pop
aload_
invokeinterface #, // InterfaceMethod java/util/Iterator.hasNext:()Z
ifne 
return 

使用foreach的字节码：

Code:
new # // class java/util/ArrayList
dup
invokespecial # // Method java/util/ArrayList."<init>":()V
astore_
aload_
invokeinterface #, // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
astore_
goto 
aload_
invokeinterface #, // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
checkcast # // class loop/Model
astore_
aload_
invokeinterface #, // InterfaceMethod java/util/Iterator.hasNext:()Z
ifne 
return 

各遍历方式的适用于什么场合？

1、传统的for循环遍历，基于计数器的：

顺序存储：读取性能比较高。适用于遍历顺序存储集合。

链式存储：时间复杂度太大，不适用于遍历链式存储的集合。

2、迭代器遍历，Iterator：

顺序存储：如果不是太在意时间，推荐选择此方式，毕竟代码更加简洁，也防止了Off-By-One的问题。

链式存储：意义就重大了，平均时间复杂度降为O(n)，还是挺诱人的，所以推荐此种遍历方式。

3、foreach循环遍历：

foreach只是让代码更加简洁了，但是他有一些缺点，就是遍历过程中不能操作数据集合（删除等），所以有些场合不使用。而且它本身就是基于Iterator实现的，但是由于类型转换的问题，所以会比直接使用Iterator慢一点，但是还好，时间复杂度都是一样的。所以怎么选择，参考上面两种方式，做一个折中的选择。

Java的最佳实践是什么？

Java数据集合框架中，提供了一个RandomAccess接口，该接口没有方法，只是一个标记。通常被List接口的实现使用，用来标记该List的实现是否支持Random Access。

一个数据集合实现了该接口，就意味着它支持Random Access，按位置读取元素的平均时间复杂度为O(1)。比如ArrayList。

而没有实现该接口的，就表示不支持Random Access。比如LinkedList。

所以看来JDK开发者也是注意到这个问题的，那么推荐的做法就是，如果想要遍历一个List，那么先判断是否支持Random Access，也就是 list instanceof RandomAccess。

比如：

if (list instanceof RandomAccess) {
//使用传统的for循环遍历。
} else {
//使用Iterator或者foreach。
}

以上所述是小编给大家介绍的Java遍历集合方法分析（实现原理、算法性能、适用场合），希望对大家有所帮助！