คำนำ
ผ่านบทความนี้คุณสามารถเข้าใจวิธีการสำรวจห้ารายการการแสดงที่เกี่ยวข้องและการใช้งาน foreach และ iterator และทำให้ความเข้าใจของคุณเกี่ยวกับการใช้งาน ArrayList และ LinkedList ลึกซึ้งยิ่งขึ้น ลองมาดูกันด้านล่าง
1. ห้าวิธีในการสำรวจรายการ
1. สำหรับแต่ละลูป
รายการ <จำนวนเต็ม> list = new ArrayList <Integer> (); สำหรับ (จำนวนเต็ม j: รายการ) {// ใช้ j}2. แสดงการเรียกคอลเลกชันตัววนซ้ำ
รายการ <จำนวนเต็ม> list = new ArrayList <จำนวนเต็ม> (); สำหรับ (iterator <teeger> iterator = list.iterator (); iterator.hasnext ();) {iterator.next ();};หรือ
รายการ <จำนวนเต็ม> list = new ArrayList <Integer> (); Iterator <Integer> iterator = list.iterator (); ในขณะที่ (iterator.hasnext ()) {iterator.next ();}3. การวนซ้ำที่เพิ่มขึ้นของตัวห้อยเงื่อนไขการเลิกจ้างคือการเปรียบเทียบและตัดสินทุกครั้งที่มีการเรียกฟังก์ชันขนาด ()
รายการ <จำนวนเต็ม> list = new ArrayList <จำนวนเต็ม> (); สำหรับ (int j = 0; j <list.size (); j ++) {list.get (j);}4. วัฏจักรที่เพิ่มขึ้นของตัวห้อยการเปรียบเทียบและการตัดสินของตัวแปรชั่วคราวที่มีเงื่อนไขการเลิกจ้างเท่ากับขนาด ()
รายการ <จำนวนเต็ม> list = new ArrayList <integer> (); int size = list.size (); สำหรับ (int j = 0; j <size; j ++) {list.get (j);};5. วงจรลดลงของตัวห้อย
รายการ <จำนวนเต็ม> list = new ArrayList <integer> (); สำหรับ (int j = list.size ()-1; j> = 0; j--) {list.get (j);}การทดสอบประสิทธิภาพและการเปรียบเทียบวิธีการสำรวจห้าวิธีของรายการ
ต่อไปนี้เป็นรหัสทดสอบประสิทธิภาพซึ่งส่งออกเวลาที่ใช้ในวิธีการสำรวจต่าง ๆ ของ ArrayList และ LinkedList ของคำสั่งซื้อที่แตกต่างกัน
แพ็คเกจ CN.TRINEA.JAVA.TEST; นำเข้า java.text.decimalformat; นำเข้า java.util.arraylist; นำเข้า java.util.calendar นำเข้า java.util.iterator; นำเข้า Java.util.linkedList; 2013-10-28 */คลาสสาธารณะ Javalooptest {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {system.out.print ("เปรียบเทียบประสิทธิภาพการวนซ้ำของ ArrayList"); looplistcompare (getarraylists (10,000, 100000, 100000, 9000000)); System.out.print ("/r/n/r/ncompare loop ประสิทธิภาพของ LinkedList"); looplistCompare (getLinkedLists (100, 1,000, 10,000, 100000)); } รายการคงที่สาธารณะ <จำนวนเต็ม> [] getArrayLists (int ... sizeArray) {list <integer> [] listarray = arrayList ใหม่ [sizearray.length]; สำหรับ (int i = 0; i <listarray.length; i ++) {int size = sizearray [i]; รายการ <จำนวนเต็ม> list = new ArrayList <จำนวนเต็ม> (); สำหรับ (int j = 0; j <size; j ++) {list.add (j); } listarray [i] = list; } return listarray; } รายการคงที่สาธารณะ <จำนวนเต็ม> [] getLinkedLists (int ... sizeArray) {รายการ <teger> [] listarray = new LinkedList [sizearray.length]; สำหรับ (int i = 0; i <listarray.length; i ++) {int size = sizearray [i]; รายการ <จำนวนเต็ม> list = new LinkedList <จำนวนเต็ม> (); สำหรับ (int j = 0; j <size; j ++) {list.add (j); } listarray [i] = list; } return listarray; } โมฆะคงที่สาธารณะ looplistCompare (รายการ <teger> ... listarray) {printheader (listarray); เริ่มต้นใช้งานนานเวลาสิ้นสุด; // type 1 สำหรับ (int i = 0; i <listarray.length; i ++) {list <integer> list = listarray [i]; startTime = calendar.getInstance (). getTimeInmillis (); สำหรับ (จำนวนเต็ม j: รายการ) {// ใช้ j} endtime = calendar.getInstance (). getTimeInmillis (); PrintCostTime (i, listarray.length, "สำหรับแต่ละ", endtime - starttime); } // type 2 สำหรับ (int i = 0; i <listarray.length; i ++) {list <integer> list = listarray [i]; startTime = calendar.getInstance (). getTimeInmillis (); // iterator <integer> iterator = list.iterator (); // ในขณะที่ (iterator.hasnext ()) {// iterator.next (); //} สำหรับ (iterator <teger> iterator = list.iterator (); iterator.hasnext ();) {iterator.next (); } endtime = calendar.getInstance (). getTimeInmillis (); PrintCostTime (i, listarray.length, "สำหรับ iterator", endtime - starttime); } // Type 3 สำหรับ (int i = 0; i <listarray.length; i ++) {list <integer> list = listarray [i]; startTime = calendar.getInstance (). getTimeInmillis (); สำหรับ (int j = 0; j <list.size (); j ++) {list.get (j); } endtime = calendar.getInstance (). getTimeInmillis (); printCostTime (i, listarray.length, "สำหรับ list.size ()", endtime - starttime); } // type 4 สำหรับ (int i = 0; i <listarray.length; i ++) {list <integer> list = listarray [i]; startTime = calendar.getInstance (). getTimeInmillis (); ขนาด int = list.size (); สำหรับ (int j = 0; j <size; j ++) {list.get (j); } endtime = calendar.getInstance (). getTimeInmillis (); printCostTime (i, listarray.length, "สำหรับ size = list.size ()", endtime - starttime); } // type 5 สำหรับ (int i = 0; i <listarray.length; i ++) {list <integer> list = listarray [i]; startTime = calendar.getInstance (). getTimeInmillis (); สำหรับ (int j = list.size ()-1; j> = 0; j--) {list.get (j); } endtime = calendar.getInstance (). getTimeInmillis (); PrintCostTime (i, listarray.length, "สำหรับ j--", endtime-starttime); }} int คงที่ first_column_length = 23, other_column_length = 12, total_column_length = 71; decimalformat สุดท้าย comma_format = new DecimalFormat ("#, ###"); Public Static Void Printheader (รายการ <จำนวนเต็ม> ... ListArray) {PrinTrowDivider (); สำหรับ (int i = 0; i <listarray.length; i ++) {ถ้า (i == 0) {StringBuilder sb = new StringBuilder (). ผนวก ("ขนาดรายการ"); ในขณะที่ (sb.length () <first_column_length) {sb.append (");} system.out.print (sb);} stringbuilder sb = stringbuilder ใหม่ (). ภาคผนวก (" | "). sb.append ("); (sb.length () <total_column_length) {sb.append ("-");} system.out.println (sb); <first_column_length) {sb.append (");} system.out.print (sb); System.out.print (SB); - PS: หากรายงานการเรียกใช้ข้อยกเว้น in thread “main” java.lang.OutOfMemoryError: Java heap space โปรดลดขนาดของ list size ในฟังก์ชัน main
ฟังก์ชั่น getArrayLists จะส่งคืน ArrayList ด้วย size ที่แตกต่างกันและฟังก์ชั่น getLinkedLists จะส่งคืน LinkedList ด้วย size ที่แตกต่างกัน
ฟังก์ชั่น loopListCompare จะใช้วิธีการสำรวจด้านบน 1-5 เพื่อสำรวจรายการในแต่ละรายการอาร์เรย์ (รวมถึงรายการขนาดที่แตกต่างกัน)
ฟังก์ชั่นเริ่มต้นด้วย print เป็นฟังก์ชั่นผู้ช่วยเอาต์พุต
สภาพแวดล้อมการทดสอบคือ Windows 7 ระบบ 32 บิต 3.2G Dual -core CPU 4G หน่วยความจำ, Java 7, Eclipse -xMS512M -xmx512m
ผลการทดสอบขั้นสุดท้ายมีดังนี้:
เปรียบเทียบประสิทธิภาพการวนซ้ำของ ArrayList ------------------------------------------------------------------- ขนาดรายการ | 10,000 | 100,000 | 1,000,000 | 10,000,000 ------------------------------------------------------------------- สำหรับแต่ละ | 1 ms | 3 ms | 14 ms | 152 MS ----------------------------------------------------------------------- สำหรับ Iterator | 0 ms | 1 ms | 12 ms | 114 MS ----------------------------------------------------------------------- สำหรับ list.size () | 1 ms | 1 ms | 13 ms | 128 ms ------------------------------------------------------------------------------- สำหรับขนาด = list.size () | 0 ms | 0 ms | 6 ms | 62 MS ----------------------------------------------------------------------- สำหรับ J-- | 0 ms | 1 ms | 6 ms | 63 MS --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 100 | 1,000 | 10,000 | 100,000 ----------------------------------------------------------------------- สำหรับแต่ละ | 0 ms | 1 ms | 1 ms | 2 MS ----------------------------------------------------------------------- สำหรับ Iterator | 0 ms | 0 ms | 0 ms | 2 MS ----------------------------------------------------------------------- สำหรับ list.size () | 0 ms | 1 ms | 73 ms | 7972 ms ---------------------------------------------------------------------------------------------------------------------------------- 0 ms | 0 ms | 67 ms | 8216 MS ------------------------------------------------------------------- สำหรับ J-- | 0 ms | 1 ms | 67 ms | 8277 MS --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
ตารางแรกคือผลการเปรียบเทียบของ ArrayList และตารางที่สองคือผลการเปรียบเทียบของ LinkedList
ทิศทางแนวนอนของตารางคือการใช้เวลาของการสำรวจขนาดต่าง ๆ ของรายการในวิธีการข้ามแบบเดียวกันและทิศทางแนวตั้งคือการใช้เวลาของการเดินทางข้ามวิธีการสำรวจที่แตกต่างกันของรายการเดียวกัน
PS: เนื่องจากการเดินทางครั้งแรกของรายการจะใช้เวลามากขึ้นเล็กน้อยผลลัพธ์ของ for each จะเบี่ยงเบนเล็กน้อย หากคุณสลับหลายประเภทในรหัสทดสอบคุณจะพบว่า for each ครั้งใกล้เคียงกับตัววนซ้ำ for iterator
การวิเคราะห์ผลการทดสอบประสิทธิภาพของวิธีการสำรวจ
1. การแนะนำ foreach
Foreach เป็นโครงสร้างลูปที่ทรงพลังมากที่แนะนำโดย Java SE5.0 for (Integer j : list) ควรอ่าน for each int in list
for (Integer j : list) เกือบจะเทียบเท่ากับ
Iterator <Integer> iterator = list.iterator (); ในขณะที่ (iterator.hasnext ()) {จำนวนเต็ม j = iterator.next ();}รหัส foreach นั้นง่ายต่อการเขียนและไม่จำเป็นต้องใส่ใจเกี่ยวกับค่าเริ่มต้นการยกเลิกมูลค่าและข้ามพรมแดนดังนั้นจึงไม่ใช่เรื่องง่ายที่จะทำผิดพลาด
2. การวิเคราะห์ผลลัพธ์ของวิธีการสำรวจอาร์เรย์ลิสต์
. ก่อนที่ขนาด arraylist คือ 100,000 การบริโภคเวลาของวิธีการสำรวจห้าวิธีเกือบเท่ากัน
ข. หลังจาก 100,000 วิธีการสำรวจครั้งที่สี่และห้านั้นเร็วกว่าสามวิธีแรกวิธี GET นั้นดีกว่าวิธีการวนซ้ำและ
ขนาด int = list.size (); สำหรับ (int j = 0; j <size; j ++) {list.get (j);} การแทนที่ list.size() ด้วยขนาดตัวแปรชั่วคราวคือประสิทธิภาพที่ดีกว่า ลองมาดูการใช้งาน Iterator และ get วิธีการใน ArrayList
คลาสส่วนตัว ITR ใช้ Iterator <E> {int Cursor; // ดัชนีขององค์ประกอบถัดไปเพื่อส่งคืน int lastret = -1; // ดัชนีขององค์ประกอบสุดท้ายที่ส่งคืน; -1 ถ้าไม่มี int ที่คาดหวัง rostmodcount = modcount; บูลีนสาธารณะ hasnext () {กลับเคอร์เซอร์! = ขนาด; } @suppresswarnings ("ไม่ได้ตรวจสอบ") สาธารณะ e ถัดไป () {checkForcomodification (); int i = เคอร์เซอร์; if (i> = size) โยน nosuchelementException ใหม่ (); Object [] ElementData = ArrayList.his.ElementData; if (i> = elementData.length) โยนใหม่พร้อมกันใหม่ Exception (); เคอร์เซอร์ = i + 1; return (e) elementData [lastret = i]; } …} สาธารณะ e get (int index) {rangecheck (ดัชนี); ส่งคืน ElementData (ดัชนี);} จากนี้เราจะเห็นได้ว่าฟังก์ชั่น next ของ get และ Iterator ซ้ำยังได้รับองค์ประกอบโดยการวางตำแหน่งข้อมูลโดยตรง แต่มีการตัดสินอีกสองสามครั้ง
ค. จากด้านบนเราจะเห็นได้ว่าแม้ใน Arraylist ของหลายสิบล้านความแตกต่างระหว่างวิธีการข้ามทางหลายวิธีมีเพียงประมาณ 50ms และเวลาเกือบเท่ากับประมาณ 100,000 เมื่อพิจารณาถึงข้อดีของ foreach เราสามารถเลือกที่จะใช้วิธีการง่าย ๆ ของ foreach foreach สำหรับ traversal
3. การวิเคราะห์ผลลัพธ์ของวิธีการสำรวจ LinkedList Traversal
. เมื่อขนาดของ LinkedList ใกล้เคียงกับ 10,000 วิธี get และวิธี Iterator มีขนาดที่แตกต่างกันสองคำสั่ง เมื่อ 100,000 ประสิทธิภาพของวิธี Iterator ซ้ำดีกว่าวิธีการรับ
ลองมาดูการใช้งานของตัววนซ้ำและ get วิธีการใน LinkedList
คลาสส่วนตัว listitr ใช้ listiterator <e> {โหนดส่วนตัว <e> lastreturned = null; โหนดส่วนตัว <E> ถัดไป; Int Nextindex ส่วนตัว; Private Int คาดหวัง ModCount = ModCount; listitr (ดัชนี int) {// ยืนยัน ispositionindex (ดัชนี); next = (index == ขนาด)? null: โหนด (ดัชนี); NextIndex = ดัชนี; } บูลีนสาธารณะ hasnext () {return nextindex <size; } สาธารณะ e next () {checkforcomodification (); if (! hasnext ()) โยน nosuchelementexception ใหม่ (); lastreturned = ถัดไป; next = next.next; NextIndex ++; กลับ lastreturned.item; } …} สาธารณะ e get (int index) {checkElementIndex (ดัชนี); ส่งคืนโหนด (ดัชนี) .item;} /*** ส่งคืนโหนด (ไม่ใช่ NULL) ที่ดัชนีองค์ประกอบที่ระบุ */node <e> node (int index) {// ยืนยัน isElementIndex (ดัชนี); if (index <(ขนาด >> 1)) {node <e> x = ก่อน; สำหรับ (int i = 0; i <index; i ++) x = x.next; กลับ x; } else {node <e> x = สุดท้าย; สำหรับ (int i = size-1; i> index; i--) x = x.prev; กลับ x; - จากรหัสด้านบนเราจะเห็นว่าฟังก์ชั่น next ของ Iterator LinkedList เพิ่งได้รับองค์ประกอบถัดไปผ่านตัวชี้ถัดไปและส่งคืน วิธีการ GET จะสำรวจตั้งแต่ต้นจนกระทั่งตัวห้อยดัชนีและค้นหาองค์ประกอบที่มีความซับซ้อนของเวลาของ O (n) และความซับซ้อนของเวลาของการสำรวจจะไปถึง O (N2)
ดังนั้นจึงขอแนะนำให้ใช้ foreach สำหรับ traversal ของ LinkedList เพื่อหลีกเลี่ยงการใช้ get
4. การวิเคราะห์เปรียบเทียบผลลัพธ์ของวิธีการสำรวจ ArrayList และ LinkedList Traversal
จากลำดับความสำคัญด้านบนมันยังเป็นวงวนรอบ foreach และเวลาของ ArrayList และ LinkedList นั้นคล้ายคลึงกัน หากคุณปรับเปลี่ยนตัวอย่างนี้เล็กน้อยและเพิ่ม list size คุณจะพบว่าทั้งสองนั้นอยู่ในลำดับขนาดเดียวกัน
อย่างไรก็ตามความซับซ้อนของเวลาของฟังก์ ArrayList get คือ O (1) ในขณะที่ความซับซ้อนของเวลาของฟังก์ชั่น Get LinkedList คือ O (n)
หากคุณพิจารณาการบริโภคพื้นที่ขอแนะนำให้เลือก ArrayList ก่อน สำหรับการแทรกและการลบแต่ละรายการคุณสามารถใช้ LinkedList
สรุปสรุป
ผ่านการวิเคราะห์ข้างต้นเราสามารถสรุปได้โดยทั่วไป:
สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่าเนื้อหาของบทความนี้จะเป็นประโยชน์กับทุกคนเมื่อเรียนรู้หรือใช้ Java หากคุณมีคำถามใด ๆ คุณสามารถฝากข้อความไว้เพื่อสื่อสาร