ปูสีส้มแดงต้นฉบับกำลังคลี่สายพานวงแหวนสองช่วงให้กลายเป็นแถวเดียวบนโต๊ะทำงานสีมิ้นต์
rustvecdequecollectionsmemorytutorial

Rust VecDeque::make_contiguous: เปิด ring buffer เป็น slice ก่อน sort

พี่โชว์Engineering

VecDeque เก่งงาน push/pop สองด้านเพราะเก็บข้อมูลแบบ ring buffer แต่ข้อมูลอาจแยกเป็นสองช่วงในหน่วยความจำครับ ถ้าต้อง sort ทั้งคิวหรือส่งให้ฟังก์ชันที่รับ &mut [T] เราใช้ make_contiguous จัดสมาชิกให้ต่อกันแล้วรับ mutable slice กลับมาได้

WHY: โครงสร้างเดียวมีสองหน้าที่

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

VecDeque::as_slices() เปิดให้เห็นสองช่วงโดยไม่ย้ายข้อมูล เหมาะกับงานอ่านที่รองรับ scatter/gather ส่วน make_contiguous() เลือกย้ายช่วงที่เหมาะสมภายใน buffer เพื่อให้ได้ slice เดียว โดยไม่ allocate และไม่เปลี่ยนลำดับทางตรรกะ

HOW: ทำให้ต่อเนื่องแล้ว sort ในที่เดิม

use std::collections::VecDeque;

#[test]
fn contiguous_slice_can_be_sorted() {
    let mut queue = VecDeque::with_capacity(8);
    queue.extend([30, 10, 40, 20]);
    assert_eq!(queue.pop_front(), Some(30));
    queue.extend([50, 5]);

    let slice = queue.make_contiguous();
    slice.sort_unstable();

    assert_eq!(queue.into_iter().collect::<Vec<_>>(), [5, 10, 20, 40, 50]);
}

borrow ของ slice ผูกกับ queue ดังนั้นระหว่างถือ slice เราจะเรียกเมธอดอื่นที่ยืม queue ซ้ำไม่ได้ กฎนี้ช่วยกัน reference ค้างหลังโครงสร้างย้ายข้อมูล

Trade-off ที่ควรเห็นก่อนเรียก

เมธอดนี้ไม่ allocate แต่ “ไม่ allocate” ไม่ได้แปลว่า “ฟรี” เพราะอาจต้องย้ายสมาชิกตามตำแหน่งหัวและพื้นที่ว่าง ถ้าเรียกทุกครั้งใน hot loop ต้นทุนการหมุน buffer อาจมากกว่าประโยชน์ของคิวสองด้าน ให้จัด phase งาน เช่น รับข้อมูลหลายรายการก่อน แล้วค่อยทำ contiguous ครั้งเดียวเพื่อ sort หรือ batch process

งานวิธี
อ่านข้อมูลโดยรองรับสองช่วงas_slices()
ต้องการ &mut [T], sort หรือ binary searchmake_contiguous()
push/pop เฉพาะท้ายเดียวและต้องใช้ slice บ่อยพิจารณา Vec<T>
ข้อมูลใหญ่มากและไม่อยากย้ายประมวลผลสอง slice แยกกัน

Recap

  • ใช้ VecDeque เมื่อมีงานสองด้านจริง
  • ใช้ as_slices สำหรับอ่านโดยไม่จัดรูปใหม่
  • เรียก make_contiguous เป็นจังหวะ ไม่ใช่ทุก iteration
  • จำว่าได้ mutable slice ที่แก้คิวเดิมโดยตรง