Day #4 - Data Structure's Exercises

[chunrapeepat]

• ถ้าหากว่าคุณได้รับมอบหมายให้พัฒนาห้องสมุดต่อจาก v3 คุณจะพัฒนาต่อในแง่ไหน ด้วยวิธีการไหน? สามารถบรรเจิดไอเดียได้เต็มที่ (หรือจะเพิ่ม use-cases การใช้ห้องสมุดใหม่ก็ได้เช่นกัน)
• ยกตัวอย่าง data structure อื่น ๆ ที่ไม่มีในบทนี้มา 1 ตัว; มี operation อะไรบ้าง และแต่ละ operation มี time complexity เท่าไหร่? (ลองหาอันที่เพื่อนยังไม่ได้หยิบมาแชร์กันก็ได้นะ)

[sebsvt]

1st exercise

อย่างแรกจะมีแบ่ง subcategory เข้าไปในแต่ละ category อีกทีซึ่งก็ high frequency, normal frequency อย่างเช่น high frequency และ normal frequency ของหมวด computer เวลาค้นหาก็จะค้นหาจาก high frequency ก่อนจะมองว่าเป็น cache ก็ได้(รึเปล่า) โดยนับจากจำนวนการยืมนั่นเอง อ้างอิงจากร้านหนังสือมาที่มักจะเอาหนังยอดนิยมหรือแนะนำมาวางไว้หน้าร้านเวลาหาจะได้หาง่ายๆ แม้ว่าการแบ่งแบบนี้อาจจะดูไม่ได้ต่างกันเท่าไหร่จาก v3 ต้นฉบับและในส่วนของ high frequency จะเป็น sorted array ส่วนใน normal frequency จะมีการใส่ subcategory เพิ่มไปอีกโดยอิงจากตัวอักษรตัวแรก

ด้านหน้าสุดตรงคือ high frequency หรือ sorted array ด้านหลังเป็น normal frequency โดยมีการแบ่งตาม alphabet อีกที dictionary อ่ะแหละ dict[str, list[Book]] ด้านในก็ sorted list นะ

2nd exercise

เอาเป็น B Tree ละกันครับ
มี operations หลักๆตามนี้ครับ

• Insertion: O(log n)
• Search: O(log n)
• Deletion: O(log n)

[chunrapeepat]

@sebsvt สุดมากครับ เขียนตามไม่ทันคนเรียนแล้วว 😂 ตอนนี้อัพ day 5 - graph theory ให้แล้วครับผม

ป.ล. อ่านเรื่องหนังสือแล้วนึกถึง LFU cache (least frequently used) ที่เก็บ cache based on frequency ส่วนถ้า overflow (แท่นวางหนังสือแนะนำเต็ม) ก็จะเอาหนังสือที่ frequency น้อย หรือหนังสือที่คนไม่ยืมออก

[thk354777]

1. แบ่งหมวดหมู่ย่อยจาก category เช่น ชื่อผู้แต่ง หรือลำดับฉบับที่ซ้ำกัน และใช้ graph เชื่อมความสัมพันธ์ระหว่างผู้เขียนและหนังสือ รวมถึง weighted Graph ใช้เก็บคะแนนความนิยมหรือคะแนนรีวิวของหนังสือ
2. B-tree แต่ละ node สามารถมี key ได้ > 1 และสามารถมี key ย่อยได้ > 2 [Insert: O(log n), Search: O(log n), Delete: O(log n)]

[keiseithunder]

1. ใช้วาง Layout ห้องสมุดให้เหมือนแผนที่ที่มี Location ชัดเจน เช่น ตู้ A ชั้น B ลำดับที่ C โดยใช้วิธีการจัดเก็บและหา แบบ map โดยใช้ ISBN เป็น Key แล้วเก็บ value เป็น location ข้างต้น โดยเราเอา space ไปแลก time ในการหา ส่วนการเพิ่มหนังสือใหม่จะเพิ่มต่อท้ายเท่านั้น ซึ่งทำให้เราได้ O(1) ในการหาหนังสือและเพิ่มหนังสือและเก็บหนังสือ
2. Hash map (assume no collision)

• Insertion: O(1)
• Search: O(1)
• Delete: O(1)
  use O(n) space for simple key-value map

[iakgoog]

1. นอกจากการแบ่งเป็น category แล้ว และยังทำ sorted array แล้ว การแบ่งตาม alphabet เพิ่มด้วย เช่น category - Business ก็จะมี part ย่อย
   Business ที่ขึ้นต้นด้วยตัวอักษร A, B, C เป็นต้น ก็จะทำให้ opeartion ต่างๆ มีประสิทธิภาพมากขึ้นเมื่อค่อยๆทำกับข้อมูลครั้งละน้อยๆ

2. Array
   Insertion: O(n)
   Deletion: O(n)
   Searching: O(n)

[NattapatKosa]

1. นอกจากแบ่งตาม category แล้ว ในแต่ละ category, เราสามารถที่จะเอากราฟมาเชื่อมชื่อกับหนังสือที่ถูกยืมบ่อยในแต่ละหมวดด้วย weight graph, หรือเราสามารถที่จะจัดคะแนนความนิยมาสำหรับหนังเป็น sort array ที่ถูกยืมย่อยในหมวดนั้นๆๆ
2. Trie (Prefix Tree)
   L - length of word

• Insertion: O(L)
• Search: O(L)
• Deletion: O(L)

[voratham]

1. ถ้าเป็น v4 คง improve โดยใช้ graph เอามาเชื่อมโยง ข้อมูล ผู้แต่ง เผื่อลิ้งไปหนังสือ ของผู้แต่ง ในแง่การค้นหา น่าจะหลากหลายขึ้นครับ , กับอีกอย่างที่คิดได้เอาทำ cache ในส่วนเล่มที่ถูกยืมไปแล้ว ถ้ามีคนมายืมซ้ำ จะได้ return ออกจาก flow ในการไปเดินหาหนังสือได้ระดับหนึ่งครับ 🥹

2. Set
   Space complexity = O(N)
   Insertion : Time complexity = O(1)
   Deletion : Time complexity = O(1)
   Searching : Time complexity = O(1)

[Top-Nuttawat]

1. ถ้าต่อยอดต่อจาก V3 อาจจะเปลี่ยนจากการใช้ชั้นหนังสือแบบ sorted array ไปเป็น ใช้ B-Tree หรือ B+Tree แทน sorted array เพราะว่า น่าจะหมาะสำหรับการจัดการข้อมูลที่มีจำนวนมาก เนื่องจากรองรับการเพิ่มและลบข้อมูลได้ดีกว่าโดย time complexity จะเป็น การค้นหา (Search) ใช้เวลา O(log n) และ การเพิ่ม หรือ ลบ ใช้เวลา O(log n) โดยแต่ละ node ในแต่ละ โหนดของ B-tree อาจเก็บหนังสือใน Category เดียวกัน และอาจจะมีการแยกเป็นโหนดย่อยๆเพื่อจะเก็บตามอักษรของชื่อหนังสือ ก็ได้ และอาจจะมีการใช้ Hash Table สำหรับการเข้าถึงหนังสือตามหมวดหมู่ โดย {key: value} โดยที่ key เป็นหมวดหมู่ และ value เป็นตำแหน่งของหมวดหมู่ในชั้นวาง ทำให้การค้นหาหนังสือตามหมวดหมู่สามารถทำได้ใน O(1)

2.AVL Tree (Adelson-Velsky and Landis Tree) คือ Self-Balancing Binary Search Tree ที่รักษาความสมดุลของต้นไม้โดยการตรวจสอบความสูงของ Subtree และทำให้แตกต่างไม่เกิน 1 เพื่อให้การค้นหาข้อมูลมีประสิทธิภาพสูงสุด
Search : O(logn)
Insert : O(logn)
Delete:O(logn)
Traversal (การเดินทางใน Tree): O(n)
Rebalancing (การปรับสมดุล):O(logn)

[Tan1pawat]

1. คิดว่าวิธีที่น่าจะ improve ระบบมากที่่สุดน่าจะการจัดเก็บหนังสือออกเป็นหมวดหมู่จากนั้น map หมวดหมู่ ทำให้จำนวนหนังสือที่เพิ่มเก็บแต่ละครั้งเหลือแค่ในหมวดหมู่นั้น จากเห็นด้วยกับหลายท่านว่าถ้านำ graph เขามาชื่อโยงในการจัดเก็บหนังสือหลังจากส่วนนี้จะทำให้การจัดการเชื่อมโยงถึงรายละเอียดของหนังสือได้มากขึ้น เพราะตอนนี้เราเเขาห้องสมุดไปแต่แรกเราอาจไม่ได้มีชื่อหนังสือที่อยากอ่านอยู่ในใจแต่มีแค่ ประเภทของหนังสือ,ความหนา,ผู้แต่ง
2. binary heap
   Search O(n)
   Insert O(log n)
   Delete O(log n)

[0xRuangsak]

1.อาจจะให้หนังสือทุกเล่มมีพื้นที่เฉพาะของตัวเอง โดยมีรหัสประจำหนังสือนั้นอยู่ ทีนี้ตอนค้นหา/ยืม/คืน เราสามารถทำได้ใน O(1) เลย แต่เมื่อห้องสมุดซื้อหนังสือเพิ่ม ต้องจัด order ใหม่ทั้งหมด ซึ่งใช้ Ω(n) ในการจัดการ แต่ process นี้จะเกิดขึ้นน้อยมากๆเทียบกับค้นหา/ยืม/คืน

2.Dynamic Array
Search O(n)
Insert O(n)
Delete O(n)

[SattraJoe]

1. ปรับปรุงโดยใช้ Balanced BST (เช่น AVL Tree, Red-Black Tree)
   Search: O(log n)
   Insertion (คืนหนังสือ): O(log n)
   Deletion (ยืมหนังสือ): O(log n)
   ข้อดี:
   - ลดเวลาในการจัดเรียงหนังสือใหม่ (Batch Processing เร็วขึ้น)
   - รองรับการขยายหนังสือจำนวนมากโดยไม่ทำให้ประสิทธิภาพลดลง

2. Skip List
   Search: O(log n)
   Insert: O(log n)
   Delete: O(log n)

[CaptainPMP]

1. ผมจะใช้วิธีเรียงตามประเภทของหนังสือ ตามด้วยเรียงตามความนิยมครับ แต่ผมจะให้คนคืนด้วยวิธีเดิมคือใส่ตะกร้าเอาไว้ ถ้านิยมเท่ากันเช่นไม่มีคนอ่านหมดเลย ก็เรียงตามตัวอักษรครับ

2. AVL Tree ครับ ที่เลือกเพราะชอบในความเจ๋งของมัน
   Search: O(log n)
   Insert: O(log n)
   Delete: O(log n)

[kankamol]

1. เพิ่ม sub-category
2. Segment tree: build tree O(n), range query O(log n), update O(log n)