ภาพรวม
ในภาษา Java มีการจัดเตรียมกรอบการรวบรวมข้อมูลซึ่งกำหนดประเภทข้อมูลที่เป็นนามธรรมบางประเภทเช่นรายการและชุด แต่ละประเภทข้อมูลนามธรรมมีการใช้งานเฉพาะของตัวเองและเลเยอร์พื้นฐานใช้วิธีการใช้งานที่แตกต่างกันเช่น ArrayList และ LinkedList
นอกจากนี้ Java ยังมีวิธีการต่าง ๆ ในการสำรวจชุดข้อมูล นักพัฒนาจะต้องเข้าใจคุณลักษณะที่เกี่ยวข้องอย่างชัดเจนโอกาสและประสิทธิภาพในการใช้งานพื้นฐานที่แตกต่างกัน มาวิเคราะห์เนื้อหานี้โดยละเอียดด้านล่าง
องค์ประกอบข้อมูลถูกเก็บไว้ในหน่วยความจำอย่างไร?
มีสองวิธีการจัดเก็บหลักสำหรับองค์ประกอบข้อมูลในหน่วยความจำ:
1. ที่เก็บข้อมูลตามลำดับการเข้าถึงแบบสุ่ม (การเข้าถึงโดยตรง):
ด้วยวิธีนี้องค์ประกอบข้อมูลที่อยู่ติดกันจะถูกเก็บไว้ในที่อยู่หน่วยความจำที่อยู่ติดกันและที่อยู่หน่วยความจำทั้งหมดจะต่อเนื่อง ที่อยู่หน่วยความจำสามารถคำนวณได้โดยตรงตามตำแหน่งขององค์ประกอบและอ่านโดยตรง ความซับซ้อนของเวลาเฉลี่ยในการอ่านองค์ประกอบในสถานที่เฉพาะคือ O (1) โดยปกติแล้วชุดที่ใช้งานตามอาร์เรย์เท่านั้นที่มีคุณสมบัตินี้ ArrayList เป็นตัวแทนใน Java
2. การจัดเก็บโซ่, การเข้าถึงแบบต่อเนื่อง:
ด้วยวิธีนี้องค์ประกอบข้อมูลแต่ละรายการไม่จำเป็นต้องอยู่ในตำแหน่งที่อยู่ติดกันในหน่วยความจำและแต่ละองค์ประกอบข้อมูลมีที่อยู่หน่วยความจำขององค์ประกอบถัดไป ที่อยู่หน่วยความจำไม่สามารถคำนวณได้โดยตรงตามตำแหน่งขององค์ประกอบและองค์ประกอบสามารถอ่านได้ตามลำดับเท่านั้น ความซับซ้อนของเวลาเฉลี่ยในการอ่านองค์ประกอบในสถานที่เฉพาะคือ o (n) ส่วนใหญ่จะแสดงโดยรายการที่เชื่อมโยง
LinkedList เป็นตัวแทนใน Java
วิธีการสำรวจที่มีให้ใน Java คืออะไร?
1. แบบดั้งเดิมสำหรับการสำรวจแบบวนรอบตามเคาน์เตอร์:
Traverser นั้นรักษาตัวนับนอกคอลเลกชันแล้วอ่านองค์ประกอบในแต่ละตำแหน่งตามลำดับและหยุดเมื่อมีการอ่านองค์ประกอบสุดท้าย สิ่งสำคัญคือการอ่านองค์ประกอบตามตำแหน่ง นี่เป็นวิธีการสำรวจแบบดั้งเดิมมากที่สุด
วิธีการเขียนคือ:
สำหรับ (int i = 0; i <list.size (); i ++) {list.get (i);}2. Iterator Traversal, Iterator:
Iterator เดิมเป็นรูปแบบการออกแบบ OO โดยมีวัตถุประสงค์หลักเพื่อบล็อกลักษณะของชุดข้อมูลที่แตกต่างกันและเพื่อสำรวจอินเทอร์เฟซของคอลเลกชันอย่างสม่ำเสมอ ในฐานะภาษา OO Java สนับสนุนโหมดตัววนซ้ำในคอลเลกชันโดยธรรมชาติ
วิธีการเขียนคือ:
ตัววนซ้ำ iterator = list.iterator (); ในขณะที่ (iterator.hasnext ()) {iterator.next ();}3. Foreach Loop Traversal:
ตัววนซ้ำและเคาน์เตอร์ที่ประกาศอย่างชัดเจนจะถูกบล็อก
ข้อดี: รหัสมีความกระชับและไม่มีแนวโน้มที่จะเกิดข้อผิดพลาด
ข้อเสีย: การเดินทางแบบง่าย ๆ เท่านั้นที่สามารถทำได้และไม่สามารถดำเนินการคอลเลกชันข้อมูล (ลบแทนที่) ในระหว่างกระบวนการข้าม
วิธีการเขียนคือ:
สำหรับ (ElementType Element: list) {}หลักการดำเนินการของแต่ละวิธีการเดินทางแต่ละวิธีคืออะไร?
1. แบบดั้งเดิมสำหรับการสำรวจแบบวนรอบตามเคาน์เตอร์:
Traverser นั้นรักษาตัวนับนอกคอลเลกชันแล้วอ่านองค์ประกอบในแต่ละตำแหน่งตามลำดับและหยุดเมื่อมีการอ่านองค์ประกอบสุดท้าย สิ่งสำคัญคือการอ่านองค์ประกอบตามตำแหน่ง
2. Iterator Traversal, Iterator:
โดยทั่วไปชุดข้อมูลการใช้งานเฉพาะแต่ละชุดจะต้องจัดเตรียมตัววนซ้ำที่สอดคล้องกัน เมื่อเปรียบเทียบกับแบบดั้งเดิมสำหรับลูปตัววนซ้ำจะห้ามเคาน์เตอร์ข้ามผ่านที่ชัดเจน ดังนั้นตัววนซ้ำตามที่เก็บข้อมูลตามลำดับของคอลเลกชันสามารถเข้าถึงข้อมูลโดยตรงตามตำแหน่ง ตัววนซ้ำตามชุดการจัดเก็บโซ่การใช้งานปกติจะต้องมีการบันทึกตำแหน่งการเดินทางในปัจจุบัน จากนั้นเลื่อนตัวชี้ไปข้างหน้าหรือย้อนกลับตามตำแหน่งปัจจุบัน
3. Foreach Loop Traversal:
ตาม Bytecode ที่ถอดรหัสได้พบว่า Foreach ยังใช้วิธีการวนซ้ำในการใช้งาน แต่คอมไพเลอร์ Java ได้ช่วยให้เราสร้างรหัสเหล่านี้
แต่ละวิธีการเดินทางแต่ละวิธีทำงานสำหรับวิธีการจัดเก็บที่แตกต่างกันอย่างไร
1. แบบดั้งเดิมสำหรับการสำรวจแบบวนรอบตามเคาน์เตอร์:
เพราะมันขึ้นอยู่กับตำแหน่งขององค์ประกอบอ่านตามตำแหน่ง ดังนั้นเราจึงสามารถรู้ได้ว่าสำหรับการจัดเก็บตามลำดับเนื่องจากความซับซ้อนของเวลาเฉลี่ยขององค์ประกอบการอ่านในสถานที่เฉพาะคือ O (1) ความซับซ้อนของเวลาเฉลี่ยของการข้ามชุดทั้งหมดคือ O (n) สำหรับการจัดเก็บโซ่เนื่องจากความซับซ้อนของเวลาเฉลี่ยขององค์ประกอบการอ่านในสถานที่เฉพาะคือ o (n) ความซับซ้อนของเวลาเฉลี่ยของการข้ามทั้งชุดคือ O (N2) (สี่เหลี่ยมจัตุรัส N)
รหัสอาร์เรย์ลิสต์อ่านโดยตำแหน่ง: อ่านโดยตรงตามตำแหน่งองค์ประกอบ
วัตถุชั่วคราว [] ElementData; Public E GET (INT ดัชนี) {RangeCheck (ดัชนี); return elementData (ดัชนี);} e elementData (INT ดัชนี) {return (e) ElementData [ดัชนี];}LinkedList Code อ่านโดยตำแหน่ง: ทุกครั้งที่คุณต้องอ่านย้อนหลังจากองค์ประกอบที่ 0 ในความเป็นจริงมันได้ทำการปรับให้เหมาะสมขนาดเล็กภายใน
transient int size = 0; โหนดชั่วคราว <e> ก่อน; โหนดชั่วคราว <e> สุดท้าย; สาธารณะ e รับ (ดัชนี int) {checkElementIndex (ดัชนี); ส่งคืนโหนด (ดัชนี) .item;} โหนด <E> โหนด (ดัชนี int) {ถ้า (ดัชนี <(ขนาด >> 1)) <ดัชนี; i ++) x = x.next; return x;} else {// ตำแหน่งการสืบค้นอยู่ในช่วงครึ่งหลังของรายการที่เชื่อมโยงและมองหาโหนด <e> x = สุดท้าย;2. Iterator Traversal, Iterator:
จากนั้นสำหรับคอลเลกชันประเภทสุ่มตัวอย่างมีความหมายไม่มากนัก แต่การดำเนินการเพิ่มเติมบางอย่างจะเพิ่มเวลาทำงานเพิ่มเติม อย่างไรก็ตามมันมีความสำคัญอย่างยิ่งสำหรับคอลเลกชันการเข้าถึงแบบต่อเนื่องเนื่องจาก Iterator รักษาตำแหน่งการเดินทางในปัจจุบันดังนั้นทุกครั้งที่คุณข้ามไปมาคุณไม่จำเป็นต้องเริ่มมองหาองค์ประกอบแรกของคอลเลกชัน เพียงแค่เลื่อนตัวชี้ทีละคน ด้วยวิธีนี้ความซับซ้อนของเวลาในการสำรวจชุดทั้งหมดจะลดลงเป็น o (n);
(นี่เป็นตัวอย่างที่ใช้ LinkedList เท่านั้น) ตัววนซ้ำของ LinkedList จะถูกนำไปใช้ภายในซึ่งคือการรักษาตำแหน่งการเดินทางในปัจจุบันและจากนั้นใช้ตัวชี้เพื่อย้าย:
รหัส:
public e next () {checkforcomodification (); ถ้า (! hasnext ()) โยน nosuchelementexception ใหม่ (); lastreturned = ถัดไป; ถัดไป = next.next; nextindex ++; return lastreturned.item;} public e ก่อนหน้า () == null)? สุดท้าย: next.prev; nextindex-; return lastreturned.item;}3. Foreach Loop Traversal:
ด้วยการวิเคราะห์จาวาไบต์เราจะเห็นได้ว่าหลักการการใช้งานภายในของ foreach นั้นถูกนำไปใช้ผ่านตัววนซ้ำ แต่ตัววนซ้ำนี้สร้างขึ้นโดยคอมไพเลอร์ Java สำหรับเราดังนั้นเราจึงไม่จำเป็นต้องเขียนด้วยตนเอง อย่างไรก็ตามเนื่องจากจำเป็นต้องมีการตรวจสอบการแปลงประเภททุกครั้งจึงใช้เวลานานกว่าตัววนซ้ำเล็กน้อย ความซับซ้อนของเวลาเหมือนกับของตัววนซ้ำ
bytecode โดยใช้ตัววนซ้ำ:
รหัส: # // คลาส java/util/arraylistdupinvokespecial # // เมธอด java/util/arraylist "<init>" :() vastore_aload_invokeinterface #, // interfacemethod java/util/list.iterator :() Interfacemethod Java/util/iterator.next :() ljava/lang/object; popaload_invokeinterface #, // interfacemethod java/util/iterator.hasnext :() zifne return
ใช้ bytecode ของ foreach:
รหัส: # // คลาส java/util/arraylistdupinvokespecial # // เมธอด java/util/arraylist "<init>" :() vastore_aload_invokeinterface #, // interfacemethod java/util/list.iterator :() Interfacemethod Java/Util/Iterator.next :() ljava/lang/object; ตรวจสอบ # // class loop/modelastore_aload_invokeinterface #, // interfacemethod java/util/iterator.hasnext :() zifne return
แต่ละวิธีการเดินทางแต่ละครั้งใช้ในโอกาสใดบ้าง?
1. แบบดั้งเดิมสำหรับการสำรวจแบบวนรอบตามเคาน์เตอร์:
ที่เก็บข้อมูลตามลำดับ: ประสิทธิภาพการอ่านสูง เหมาะสำหรับคอลเลกชันการจัดเก็บแบบต่อเนื่องแบบ Traversal
การจัดเก็บโซ่: ความซับซ้อนของเวลาสูงเกินไปและไม่เหมาะสำหรับการข้ามคอลเลกชันของการจัดเก็บโซ่
2. Iterator Traversal, Iterator:
ที่เก็บข้อมูลตามลำดับ: หากคุณไม่สนใจเวลามากเกินไปขอแนะนำให้เลือกวิธีนี้ ท้ายที่สุดรหัสนั้นกระชับมากขึ้นและยังป้องกันปัญหาของการปิดโดยหนึ่ง
การจัดเก็บโซ่: มันมีความสำคัญอย่างยิ่ง ความซับซ้อนของเวลาโดยเฉลี่ยจะลดลงเป็น O (n) ซึ่งค่อนข้างน่าสนใจดังนั้นจึงแนะนำให้ใช้วิธีการสำรวจ
3. Foreach Loop Traversal:
Foreach ทำให้รหัสกระชับมากขึ้น แต่มีข้อเสียบางประการนั่นคือมันไม่สามารถใช้งานคอลเลกชันข้อมูล (การลบ ฯลฯ ) ในระหว่างกระบวนการข้ามทางดังนั้นจึงไม่ได้ใช้ในบางโอกาส ยิ่งไปกว่านั้นมันถูกนำไปใช้ตามตัววนซ้ำ แต่เนื่องจากปัญหาของการแปลงประเภทมันจะช้ากว่าการใช้ตัววนซ้ำโดยตรงเล็กน้อย โชคดีที่ความซับซ้อนของเวลาเหมือนกัน ดังนั้นวิธีการเลือกอ้างอิงสองวิธีข้างต้นเพื่อเลือกการประนีประนอม
แนวทางปฏิบัติที่ดีที่สุดสำหรับ Java คืออะไร?
ในกรอบการรวบรวมข้อมูล Java จะมีการจัดอินเตอร์เฟสแบบสุ่มซึ่งไม่มีวิธีการเพียงแท็ก โดยปกติแล้วการใช้งานของอินเทอร์เฟซรายการเพื่อทำเครื่องหมายว่าการใช้งานรายการรองรับการเข้าถึงแบบสุ่มหรือไม่
ชุดข้อมูลใช้อินเทอร์เฟซนี้ซึ่งหมายความว่ารองรับการเข้าถึงแบบสุ่มและความซับซ้อนของเวลาเฉลี่ยขององค์ประกอบการอ่านตามตำแหน่งคือ O (1) ตัวอย่างเช่น ArrayList
หากอินเทอร์เฟซนี้ไม่ได้ใช้งานหมายความว่าไม่รองรับการเข้าถึงแบบสุ่ม ตัวอย่างเช่น LinkedList
ดังนั้นดูเหมือนว่านักพัฒนา JDK ได้สังเกตเห็นปัญหานี้เช่นกัน วิธีที่แนะนำคือการตรวจสอบก่อนว่ารองรับการเข้าถึงแบบสุ่มนั่นคือรายการอินสแตนซ์ของการสุ่มตัวอย่าง
ตัวอย่างเช่น:
if (รายการอินสแตนซ์ของ RandomAccess) {// ใช้แบบดั้งเดิมสำหรับ Loop Traversal } else {// ใช้ตัววนซ้ำหรือ foreach -ข้างต้นคือการวิเคราะห์วิธีการรวบรวม Java Traversal (หลักการดำเนินการประสิทธิภาพอัลกอริทึมและโอกาสที่เกี่ยวข้อง) แนะนำโดยบรรณาธิการ ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน!