คำแนะนำเกี่ยวกับการใช้คอลเลกชัน

1. รายการคอลเลกชัน

อย่างที่คุณคงจำได้ Java มีคอลเล็กชัน ซึ่งเป็นเครื่องมือที่มีประโยชน์สำหรับจัดเก็บออบเจกต์ประเภทเดียวกัน

ลองนึกถึงอินเทอร์เฟซที่เกี่ยวข้องกับคอลเลกชันหลัก:

รายการชุดแผนที่และคิว_ _ _

ตามปกติแล้ว เครื่องมือไม่จำเป็นต้องดีหรือไม่ดี สิ่งสำคัญคือคุณใช้มันตามจุดประสงค์หรือไม่ และในการทำเช่นนั้น เราต้องเข้าใจคุณสมบัติเฉพาะของพวกมันอย่างถี่ถ้วน เพื่อที่จะรู้ว่าควรใช้คอลเล็กชันใดและเมื่อใด

1. รายการ

เริ่มจากคอลเลกชันที่ใช้มากที่สุด

ทำรายการให้ใกล้เคียงกับอาร์เรย์เก่าธรรมดามากที่สุด

คอลเล็กชันนี้ช่วยให้เราจัดเก็บรายการออบเจกต์ประเภทเดียวกันได้อย่างสะดวกสบายโดยไม่ต้องกังวลเกี่ยวกับขนาดของคอลเล็กชัน เนื่องจากเราจะต้องทำหากเราใช้อาร์เรย์ องค์ประกอบของคอลเลกชันสามารถเข้าถึงได้โดยดัชนี หากเราทราบแน่ชัดว่าวัตถุอยู่ที่ใดและจำเป็นต้องเข้าถึงบ่อยครั้งโดยไม่จำเป็นต้องเพิ่มหรือลบองค์ประกอบบ่อยๆ รายการจะเหมาะสมที่สุด

2. ชุด

ชุดมีโครงสร้างที่แตกต่างกันอย่างสิ้นเชิง

ชุดที่เหมาะสมที่สุดเมื่อเราต้องการจัดเก็บวัตถุที่ไม่ซ้ำกัน ตัวอย่างเช่น ชุดผู้เขียนในไลบรารีที่ผู้เขียนแต่ละคนไม่ซ้ำกัน แต่เราไม่สามารถไปคว้าเอาผู้เขียนคนใดคนหนึ่งจากมันได้ Setช่วยให้เราตรวจสอบได้อย่างรวดเร็วว่ามีผู้เขียนคนใดคนหนึ่งอยู่ในไลบรารีของเราหรือไม่ เช่น เราสามารถตรวจสอบได้ว่ามีวัตถุที่ไม่ซ้ำใครอยู่ใน Setหรือไม่ นอกจากนี้ เรายังสามารถวนซ้ำทั้งคอลเลกชั่น เข้าถึงแต่ละองค์ประกอบ แต่การทำเช่นนั้นไม่เหมาะสม

กล่าวอีกนัยหนึ่ง สำหรับห้องสมุดของเราชุดสามารถแสดงถึงคอลเลกชันของผู้เขียนที่ไม่ซ้ำกันทั้งหมด เพื่อตรวจสอบอย่างรวดเร็วว่ามีผู้เขียนคนใดคนหนึ่งอยู่หรือไม่

3. แผนที่

แผนที่เป็นเหมือนตู้เก็บเอกสารซึ่งแต่ละไฟล์จะถูกเซ็นชื่อและสามารถจัดเก็บวัตถุแต่ละชิ้นหรือโครงสร้างทั้งหมดได้ แผนที่ควรใช้ในกรณีที่เราจำเป็นต้องรักษาการแมปจากค่าหนึ่งไปยังอีกค่าหนึ่ง

สำหรับMapความสัมพันธ์เหล่านี้เรียกว่าคู่คีย์-ค่า

เราสามารถใช้โครงสร้างนี้ในห้องสมุดของเราโดยใช้วัตถุผู้เขียนเป็นคีย์และรายการ ( รายการวัตถุ) ของหนังสือเป็นค่า ดังนั้น หลังจากตรวจสอบSet เพื่อดูว่ามีวัตถุผู้เขียน อยู่ในห้องสมุดหรือไม่ เราสามารถใช้วัตถุผู้เขียนเดียวกันเพื่อรับรายการหนังสือของเขาหรือเธอจากแผนที่

4. คิว

Queueเป็นคอลเลกชันที่ - เซอร์ไพรส์! - ใช้พฤติกรรมของคิว และคิวสามารถเป็นได้ทั้ง LIFO (เข้าก่อนออกก่อน) หรือ FIFO (เข้าก่อนออกก่อน) ยิ่งไปกว่านั้น คิวสามารถเป็นแบบสองทิศทางหรือ "double-ended"

โครงสร้างนี้มีประโยชน์เมื่อวัตถุที่เพิ่มเข้ามาในคลาสจำเป็นต้องใช้ตามลำดับที่ได้รับ ตัวอย่างเช่น ใช้ห้องสมุดของเรา

เราสามารถเพิ่มผู้เข้าชมที่เพิ่งมาถึงในคิวและให้บริการตามลำดับ โดยออกหนังสือที่พวกเขามา

อย่างที่เราเห็น โครงสร้างแต่ละอย่างเหล่านี้ดีหากใช้ตามวัตถุประสงค์ที่ตั้งใจไว้ และเราพบประโยชน์ที่ดีสำหรับคอลเลกชันทั้งสี่ประเภทในตัวอย่างไลบรารีเดียว

2. ความซับซ้อน

ตามที่ระบุไว้แล้ว คอลเล็กชันที่เราพิจารณาข้างต้นเป็นอินเทอร์เฟซ ซึ่งหมายความว่าจะต้องมีการใช้งานเพื่อให้เราใช้งานได้

เช่นเดียวกับการตอกตะปูด้วยกล้องจุลทรรศน์ไม่ใช่ความคิดที่ดีที่สุด การใช้งานคอลเลกชันทุกครั้งก็ไม่เหมาะกับทุกสถานการณ์

ในการเลือกเครื่องมือให้เหมาะสมกับงาน โดยทั่วไปเราจะพิจารณา 2 ลักษณะคือ

• เครื่องมือเหมาะสมกับงานแค่ไหน?
• มันจะทำงานเสร็จเร็วแค่ไหน?

เราใช้เวลาพอสมควรในการหาวิธีเลือกเครื่องมือที่เหมาะสมสำหรับงาน แต่ความเร็วนั้นเป็นสิ่งใหม่

ในการคำนวณ ความเร็วของเครื่องมือมักจะแสดงในรูปของความซับซ้อนของเวลา และเขียนแทนด้วยอักษรตัวใหญ่ O

ความซับซ้อนของเวลาในโลกคืออะไร?

พูดง่ายๆ ก็คือ ความซับซ้อนของเวลาบ่งชี้เวลาที่จำเป็นสำหรับอัลกอริทึมในคอลเลกชันเพื่อดำเนินการบางอย่าง (การเพิ่ม/การลบองค์ประกอบ การค้นหาองค์ประกอบ)

ArrayList กับ LinkedList

ลองดูที่สิ่งนี้โดยใช้การใช้งาน อินเทอร์เฟซ List สองรายการ — ArrayListและLinkedList

สำหรับรูปลักษณ์ภายนอก การทำงานกับคอลเลกชันเหล่านี้มีความคล้ายคลึงกัน:

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

อย่างที่คุณเห็น สำหรับคอลเลกชันทั้งสองประเภท การเพิ่ม การรับ และการลบองค์ประกอบจะเหมือนกัน เนื่องจากเป็นการใช้งานบนอินเทอร์เฟซเดียวกัน แต่นั่นคือจุดสิ้นสุดของความคล้ายคลึงกัน

เนื่องจากการใช้งาน อินเทอร์เฟซ รายการ ที่แตกต่างกัน โครงสร้างทั้งสองนี้จึงดำเนินการต่างๆ ได้อย่างมีประสิทธิภาพมากกว่าโครงสร้างอื่นๆ

พิจารณาการลบและเพิ่มองค์ประกอบ

หากเราต้องการลบองค์ประกอบออกจากตรงกลางของArrayListเราจะต้องเขียนทับส่วนใดก็ตามของรายการที่อยู่ถัดจากองค์ประกอบที่เราลบออกไป

สมมติว่าเรามีรายการองค์ประกอบ 5 รายการ และเราต้องการลบรายการที่ 3

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

ในกรณีนี้ การลบจะทำให้เซลล์ว่างหนึ่งเซลล์ ดังนั้นเราต้องเขียนองค์ประกอบที่ 4 โดยที่เซลล์ที่ 3 อยู่ และเซลล์ที่ 5 ตรงที่เซลล์ที่ 4 อยู่

สิ่งนี้ไม่มีประสิทธิภาพอย่างมาก

สิ่งเดียวกันนี้เกิดขึ้นเมื่อเพิ่มองค์ประกอบลงตรงกลางรายการ

LinkedList มีโครงสร้างแตกต่างกัน การเพิ่มหรือลบองค์ประกอบทำได้รวดเร็ว เนื่องจากเราเพียงแค่เปลี่ยนการอ้างอิงในองค์ประกอบก่อนหน้าและถัดไป ดังนั้นจึงไม่รวมวัตถุที่เรากำลังลบออกจากห่วงโซ่ขององค์ประกอบ

กลับไปที่ตัวอย่างรายการ 5 องค์ประกอบเดียวกัน หลังจากลบองค์ประกอบที่ 3 แล้ว สิ่งที่เราต้องทำก็แค่เปลี่ยนการอ้างอิงองค์ประกอบที่ 2 เป็นองค์ประกอบถัดไป และการอ้างอิงองค์ประกอบที่ 4 ไปยังองค์ประกอบก่อนหน้า

เมื่อองค์ประกอบถูกเพิ่มเข้าไปในรายการ กระบวนการเดียวกันจะเกิดขึ้น แต่จะตรงกันข้าม

สังเกตว่าเราต้องทำงานน้อยลงแค่ไหนในLinkedList เมื่อเทียบกับArrayList และนั่นเป็นเพียง 5 องค์ประกอบ หากรายการของเรามีองค์ประกอบตั้งแต่ 100 รายการขึ้นไป ความเหนือกว่าของLinkedListจะเห็นได้ชัดเจนยิ่งขึ้น

แต่สถานการณ์จะเปลี่ยนไปอย่างไรหากเราเข้าถึงองค์ประกอบด้วยดัชนี

ทุกอย่างตรงกันข้ามที่นี่

เนื่องจาก ArrayList มีโครงสร้างเป็นอาร์เรย์ธรรมดา การรับองค์ประกอบใดๆ จากดัชนีจึงเป็นเรื่องง่ายมากสำหรับเรา เราเพียงแค่เลื่อนตัวชี้ไปยังตำแหน่งที่ต้องการและรับองค์ประกอบจากเซลล์ที่เกี่ยวข้อง

แต่LinkedListไม่ทำงานอย่างนั้น เราต้องผ่านองค์ประกอบทั้งหมดของรายการเพื่อค้นหาองค์ประกอบที่มีดัชนีที่แน่นอน

เราจะพยายามแสดงทั้งหมดนี้ในแง่ของ O ใหญ่หรือไม่?

เริ่มจากการเข้าถึงองค์ประกอบด้วยดัชนี

ในArrayListสิ่งนี้จะเกิดขึ้นในขั้นตอนเดียว โดยไม่คำนึงว่าองค์ประกอบจะอยู่ที่ใดในรายการ ไม่ว่าจะในตอนท้ายหรือตอนเริ่มต้น

ในกรณีนี้ ความซับซ้อนของเวลาจะเป็นO(1 )

ในLinkedListเราต้องวนซ้ำองค์ประกอบจำนวนหนึ่งให้เท่ากับค่าของดัชนีที่เราต้องการ

ความซับซ้อนของเวลาสำหรับการดำเนินการดังกล่าวคือO(n)โดยที่ n คือดัชนีขององค์ประกอบที่เราต้องการ

คุณจะเห็นว่าจำนวนที่เราใส่ในวงเล็บ big-O นั้นสอดคล้องกับจำนวนของการดำเนินการที่ทำ

เชลล์เรากลับไปที่การลบและเพิ่ม?

เริ่มจาก LinkedList กันก่อน

เนื่องจากเราไม่จำเป็นต้องดำเนินการจำนวนมากเพื่อเพิ่มหรือลบองค์ประกอบ และความเร็วของการดำเนินการนี้ไม่ได้ขึ้นอยู่กับตำแหน่งขององค์ประกอบแต่อย่างใด ความซับซ้อนจึงแสดงเป็น O(1) และมีการกล่าวว่า ให้คงที่

ความซับซ้อนของเวลาของการดำเนินการนี้สำหรับArrayListก็คือO(n) เช่นกัน ซึ่งเราเรียกว่าความซับซ้อนเชิงเส้น

ในอัลกอริทึมที่มีความซับซ้อนเชิงเส้น เวลาทำงานขึ้นอยู่กับจำนวนองค์ประกอบที่ต้องประมวลผลโดยตรง นอกจากนี้ยังอาจขึ้นอยู่กับตำแหน่งขององค์ประกอบ ไม่ว่าจะเป็นที่จุดเริ่มต้นของรายการหรือที่สิ้นสุด

ความซับซ้อนของเวลาสามารถเป็นลอการิทึมได้เช่นกัน ซึ่งจะแสดงเป็นO (log n)

ตัวอย่างเช่น พิจารณาTreeSet ที่เรียงลำดับ ซึ่งประกอบด้วยตัวเลข 10 ตัว เราต้องการค้นหาหมายเลข 2

เนื่องจากรายการถูกจัดเรียงและไม่มีรายการที่ซ้ำกัน เราจึงสามารถแบ่งครึ่งและตรวจสอบว่าครึ่งใดมีหมายเลขที่ต้องการ ละทิ้งส่วนที่ไม่เกี่ยวข้อง แล้วทำขั้นตอนนี้ซ้ำจนกว่าจะถึงองค์ประกอบที่ต้องการ ในที่สุด เราจะพบ (หรือไม่พบ) หมายเลขหลังจากประมวลผล log(n) จำนวนองค์ประกอบ

นี่คือตารางที่สรุปความซับซ้อนของเวลาสำหรับคอลเล็กชันที่เหลือ

ตอนนี้เรามีตารางแสดงความซับซ้อนของเวลาของคอลเล็กชันยอดนิยมแล้ว เราสามารถตอบคำถามได้ว่าทำไมในคอลเล็กชันจำนวนมาก เราจึงใช้ArrayList , HashSet และ HashMap บ่อย ที่สุด

เป็นเพียงว่ามันมีประสิทธิภาพมากที่สุดสำหรับงานส่วนใหญ่ :)