Kata pengantar
Melalui artikel ini, Anda dapat memahami lima metode daftar traversal, kinerja masing -masing dan implementasi foreach dan iterator, dan memperdalam pemahaman Anda tentang daftar array dan implementasi daftar tautan. Mari kita lihat bersama di bawah ini.
1. Lima cara untuk melintasi daftar
1. Untuk setiap loop
Daftar <Integer> Daftar = ArrayList baru <Integer> (); for (integer j: list) {// gunakan j}2. Tampilan koleksi panggilan iterator
Daftar <Integer> Daftar = ArrayList baru <Integer> (); untuk (iterator <integer> iterator = list.iterator (); iterator.hasnext ();) {iterator.next ();}atau
Daftar <Integer> Daftar = ArrayList baru <Integer> (); iterator <Integer> iterator = list.iterator (); while (iterator.hasnext ()) {iterator.next ();}3. Loop tambahan subskrip, kondisi penghentian adalah untuk membandingkan dan menilai setiap kali fungsi size () disebut
Daftar <Integer> Daftar = ArrayList baru <Integer> (); untuk (int j = 0; j <list.size (); j ++) {list.get (j);}4. Siklus tambahan subskrip, perbandingan dan penilaian variabel sementara yang kondisi terminasi yang jumlahnya sama dengan ukuran ()
Daftar <Integer> Daftar = ArrayList baru <integer> (); int size = list.size (); untuk (int j = 0; j <size; j ++) {list.get (j);}5. Siklus penurunan subskrip
Daftar <Integer> Daftar = ArrayList baru <Integer> (); for (int j = list.size ()-1; j> = 0; j--) {list.get (j);}Tes Kinerja dan Perbandingan Lima Metode Perjalanan Daftar
Berikut ini adalah kode uji kinerja, yang menghasilkan waktu yang dihabiskan untuk berbagai metode traversal arraylist dan linkedlist dari orde besar yang berbeda.
Paket cn.trinea.java.test; import java.text.decimalformat; import java.util.arraylist; import java.util.calendar; impor java.util.iterator; Impor Java.util.linkedlist; impor java.util.list; 2013-10-28 */kelas publik javaloopTest {public static void main (string [] args) {System.out.print ("Bandingkan kinerja loop arrayList"); LoopListCompare (GetArrayLists (10000, 100000, 100000, 9000000)); System.out.print ("/r/n/r/nCompare loop kinerja LinkedList"); looplistCompare (getLinkedLists (100, 1000, 10000, 10000)); } Daftar statis publik <Integer> [] getArrayLists (int ... sizeArray) {list <integer> [] listArray = new arraylist [sizeArray.length]; untuk (int i = 0; i <listarray.length; i ++) {int size = sizeArray [i]; Daftar <Integer> Daftar = ArrayList baru <Integer> (); untuk (int j = 0; j <size; j ++) {list.add (j); } listArray [i] = daftar; } return listArray; } Daftar statis publik <Integer> [] getLinkedLists (int ... SizeArray) {List <Integer> [] listArray = LinkedList baru [sizeArray.length]; untuk (int i = 0; i <listarray.length; i ++) {int size = sizeArray [i]; Daftar <Integer> Daftar = LinkedList baru <Integer> (); untuk (int j = 0; j <size; j ++) {list.add (j); } listArray [i] = daftar; } return listArray; } public static void loopListCompare (Daftar <Integer> ... ListArray) {printheader (ListArray); waktu mulai yang lama, waktu akhir; // ketik 1 untuk (int i = 0; i <listarray.length; i ++) {list <integer> list = listArray [i]; startTime = calendar.getInstance (). getTimeInmillis (); untuk (integer j: list) {// gunakan j} endtime = calendar.getInstance (). getTimeInmillis (); printCostTime (i, listarray.length, "untuk masing -masing", endtime - startTime); } // ketik 2 untuk (int i = 0; i <listarray.length; i ++) {daftar <integer> list = listArray [i]; startTime = calendar.getInstance (). getTimeInmillis (); // iterator <integer> iterator = list.iterator (); // while (iterator.hasnext ()) {// iterator.next (); //} untuk (iterator <Integer> iterator = list.iterator (); iterator.hasnext ();) {iterator.next (); } endtime = calendar.getInstance (). getTimeInmillis (); printCosttime (i, listarray.length, "for iterator", endtime - startTime); } // ketik 3 untuk (int i = 0; i <listarray.length; i ++) {list <integer> list = listArray [i]; startTime = calendar.getInstance (). getTimeInmillis (); untuk (int j = 0; j <list.size (); j ++) {list.get (j); } endtime = calendar.getInstance (). getTimeInmillis (); printCosttime (i, listarray.length, "for list.size ()", endtime - startTime); } // ketik 4 untuk (int i = 0; i <listarray.length; i ++) {daftar <integer> daftar = listArray [i]; startTime = calendar.getInstance (). getTimeInmillis (); int size = list.size (); untuk (int j = 0; j <size; j ++) {list.get (j); } endtime = calendar.getInstance (). getTimeInmillis (); printCostTime (i, listarray.length, "for size = list.size ()", endtime - startTime); } // ketik 5 untuk (int i = 0; i <listarray.length; i ++) {list <integer> list = listArray [i]; startTime = calendar.getInstance (). getTimeInmillis (); untuk (int j = list.size ()-1; j> = 0; j--) {list.get (j); } endtime = calendar.getInstance (). getTimeInmillis (); printCostTime (i, listarray.length, "for j--", endtime-startTime); }} static int first_column_length = 23, Other_column_length = 12, total_column_length = 71; static final decimalformat comma_format = new decimalformat ("#, ###"); public static void printheader (Daftar <Integer> ... ListArray) {printrowDivider (); untuk (int i = 0; i <listArray.length; i ++) {if (i == 0) {StringBuilder SB = new StringBuilder (). Append ("List size"); while (sb.length () <first_column_length) {sb.append (");} system.out.print (sb);} stringBuilder sb = stringBuilder baru (). SB.Append ("); (sb.length () <total_column_length) {sb.append ("-"); <First_column_length) {sb.append (""); System.out.print (SB); }}} PS: Jika run melaporkan pengecualian in thread “main” java.lang.OutOfMemoryError: Java heap space , harap kurangi ukuran list size di fungsi main .
Fungsi getArrayLists akan mengembalikan daftar array dengan size yang berbeda, dan fungsi getLinkedLists akan mengembalikan daftar tautan dengan size yang berbeda.
Fungsi loopListCompare akan menggunakan metode traversal di atas 1-5 untuk melintasi daftar di setiap daftar array (termasuk daftar berbagai ukuran).
Fungsi yang dimulai dengan print adalah fungsi pembantu output.
Lingkungan uji adalah sistem Windows 7 32 -bit 3.2g memori CPU 4G dual -core, Java 7, Eclipse -xms512m -xmx512m
Hasil tes akhir adalah sebagai berikut:
Bandingkan Kinerja Loop dari ArrayList ----------------------------------------------------------------------- Ukuran Daftar | 10.000 | 100.000 | 1.000.000 | 10.000.000 ----------------------------------------------------------------------- untuk setiap | 1 ms | 3 ms | 14 ms | 152 MS ----------------------------------------------------------------------- untuk Iterator | 0 MS | 1 ms | 12 ms | 114 MS ----------------------------------------------------------------------- untuk daftar.size () | 1 ms | 1 ms | 13 ms | 128 MS ----------------------------------------------------------------------- untuk size = list.size () | 0 MS | 0 MS | 6 ms | 62 MS ----------------------------------------------------------------------- untuk J-- | 0 MS | 1 ms | 6 ms | 63 MS ----------------------------------------------------------------------- Bandingkan Kinerja Loop LinkedList ------------------------------------------------------------------- Ukuran Daftar | 100 | 1.000 | 10.000 | 100.000 ----------------------------------------------------------------------- untuk masing-masing | 0 MS | 1 ms | 1 ms | 2 MS ----------------------------------------------------------------------- untuk Iterator | 0 MS | 0 MS | 0 MS | 2 MS ----------------------------------------------------------------------- untuk daftar.Size () | 0 MS | 1 ms | 73 ms | 7972 MS ----------------------------------------------------------------------- untuk size = list.size () | 0 MS | 0 MS | 67 ms | 8216 MS ----------------------------------------------------------------------- Untuk J-- | 0 MS | 1 ms | 67 ms | 8277 MS -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Tabel pertama adalah hasil perbandingan dari arraylist, dan tabel kedua adalah hasil perbandingan dari LinkedList.
Arah horizontal tabel adalah konsumsi waktu traversal dari berbagai ukuran daftar dalam metode traversal yang sama, dan arah vertikal adalah konsumsi waktu traversal metode traversal yang berbeda dari daftar yang sama.
PS: Karena traversal pertama daftar akan membutuhkan waktu lebih banyak, hasil for each sedikit menyimpang. Jika Anda bertukar beberapa jenis dalam kode pengujian, Anda akan menemukannya for each kali dekat dengan for iterator .
Analisis hasil uji kinerja metode traversal
1. PENDAHULUAN FOREACH
Foreach adalah struktur loop yang sangat kuat yang diperkenalkan oleh Java SE5.0. for (Integer j : list) harus dibaca for each int in list .
for (Integer j : list) hampir setara dengan
Iterator <Integer> iterator = list.iterator (); while (iterator.hasnext ()) {integer j = iterator.next ();}Kode Foreach mudah ditulis, dan tidak perlu peduli dengan nilai awal, penghentian nilai, dan lintas batas, sehingga tidak mudah untuk membuat kesalahan.
2. Analisis Hasil Metode Traversal ArrayList
A. Sebelum ukuran arraylist adalah 100.000, konsumsi waktu dari lima metode traversal hampir sama
B. Setelah 100.000, metode traversal keempat dan kelima lebih cepat dari tiga yang pertama, metode GET lebih baik daripada metode iterator, dan
int size = list.size (); for (int j = 0; j <size; j ++) {list.get (j);} Mengganti list.size() dengan ukuran variabel sementara adalah kinerja yang lebih baik. Mari kita lihat implementasi Iterator dan get metode di ArrayList
kelas pribadi ITR mengimplementasikan iterator <E> {int kursor; // indeks elemen berikutnya untuk mengembalikan int lastret = -1; // indeks elemen terakhir dikembalikan; -1 Jika tidak ada int diharapkan seperti itu = modcount; public boolean hasnext () {return kursor! = size; } @Suppresswarnings ("Uncecked") public e next () {checkForComodification (); int i = kursor; if (i> = size) melempar nosuchelementException baru (); Objek [] elementData = arraylist.this.elementData; if (i> = elementData.length) melempar concurrentmodificationException baru (); kursor = i + 1; return (e) elementData [lastret = i]; } ...} public e get (int index) {rangeCheck (index); return elementData (index);} Dari sini kita dapat melihat bahwa fungsi get dan Iterator next juga mendapatkan elemen dengan langsung memposisikan data, tetapi hanya ada beberapa penilaian lagi.
C. Dari yang di atas, kita dapat melihat bahwa bahkan dalam daftar array dari puluhan juta, perbedaan antara beberapa metode traversal hanya sekitar 50 ms, dan waktunya hampir sama dengan sekitar 100.000. Mempertimbangkan keunggulan foreach, kami dapat memilih untuk menggunakan metode sederhana foreach foreach untuk traversal.
3. Analisis Hasil Metode Traversal LinkedList
A. Ketika ukuran LinkedList mendekati 10.000, metode get dan metode Iterator sudah sekitar dua urutan besarnya berbeda. Ketika 100.000, kinerja metode Iterator jauh lebih baik daripada metode GET.
Mari kita lihat implementasi iterator dan get metode di LinkedList
private class listitr mengimplementasikan listiterator <E> {private node <E> lastreturned = null; node pribadi <E> Berikutnya; Private Int NextIndex; private int happectedModCount = modcount; Listitr (int index) {// Assert isPositionIndex (index); next = (index == ukuran)? null: node (index); nextIndex = index; } public boolean hasnext () {return nextIndex <size; } public e next () {checkForComodification (); if (! hasnext ()) melempar nosuchelementException baru (); lastreturned = next; next = next.next; nextIndex ++; return lastreturned.item; } ...} public e get (int index) {checkelementIndex (index); return node (index) .item;} /*** Mengembalikan node (non-null) pada indeks elemen yang ditentukan. */Node <E> node (indeks int) {// Assert isElementIndex (index); if (index <(size >> 1)) {node <E> x = pertama; untuk (int i = 0; i <index; i ++) x = x.next; mengembalikan x; } else {node <E> x = terakhir; untuk (int i = ukuran-1; i> index; i--) x = x.prev; mengembalikan x; }} Dari kode di atas, kita dapat melihat bahwa fungsi next dari Iterator LinkedList dengan cepat mendapatkan elemen berikutnya melalui pointer berikutnya dan kembali. Metode GET akan melintasi dari awal hingga subskrip indeks, dan menemukan elemen dengan kompleksitas waktu O (n), dan kompleksitas waktu traversal akan mencapai O (N2).
Oleh karena itu, disarankan untuk menggunakan foreach untuk traversal LinkedList untuk menghindari penggunaan get .
4. Analisis komparatif hasil arraylist dan metode traversal linkedlist
Dari urutan besarnya di atas, itu juga merupakan loop traversal foreach, dan waktu arraylist dan linkedlist serupa. Jika Anda sedikit memodifikasi contoh ini dan meningkatkan list size Anda akan menemukan bahwa keduanya pada dasarnya berada pada urutan besarnya.
Namun, kompleksitas waktu dari fungsi ArrayList get adalah O (1), sedangkan kompleksitas waktu fungsi GET LinkedList adalah O (n).
Jika Anda mempertimbangkan konsumsi ruang, disarankan untuk memilih ArrayList terlebih dahulu. Untuk penyisipan dan penghapusan individual, Anda dapat menggunakan LinkedList.
Ringkasan Kesimpulan
Melalui analisis di atas, kita pada dasarnya dapat meringkas:
Meringkaskan
Di atas adalah seluruh konten artikel ini. Saya berharap konten artikel ini akan membantu semua orang saat belajar atau menggunakan Java. Jika Anda memiliki pertanyaan, Anda dapat meninggalkan pesan untuk berkomunikasi.