การใช้งาน JavaScript Priority Queue โดยใช้ไบนารีฮีป

Question

ฉันกำลังอ่านหนังสือAlgorithms ของ Robert Sedgewick สำหรับการนำคิวลำดับความสำคัญไปใช้งานโดยใช้ไบนารีฮีปฉันติดตั้งโค้ดโดยใช้ ES6 ฉันเชื่อว่าจะมีประสบการณ์กับ Ruby มากขึ้น แต่ฉันก็สนุกกับการทำงานกับ ES-6 โดยใช้คลาส

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

 class Heap {
      constructor() {
        this.n = 0;
        this.pq = [];
      }
    
      size() {
        return this.n;
      }
    
      isEmpty() {
        this.n === 0;
      }
    
      swim(k) {
        while(k > 1 && this.less(Math.floor(k / 2), k)){
          this.exch(Math.floor(k / 2), k);
          k = Math.floor(k / 2)
        }
      }
    
      sink(k) {
        while(2 * k <= this.n) {
          let j = 2 * k;
    
          if(this.pq[j + 1] != null) {
            if(k > 1 && this.less(j, j + 1)){
              j++;
            }
          }
    
          if(this.pq[k] > this.pq[j]) {
            break;
          }
          this.exch(k, j)
          k = j
        }
      }
    
      insert(v) {
        this.pq[++this.n] = v;
        this.swim(this.n);
      }
    
      delMax() {
        let max = this.pq[1];
        this.exch(1, this.n--);
        this.pq[this.n + 1] = null;
        this.sink(1);
        return max;
      }
    
      less(i, j) {
        return this.pq[i] < this.pq[j];
      }
    
      exch(i, j) {
        let temp = this.pq[i];
        this.pq[i] = this.pq[j];
        this.pq[j] = temp;
      }
    }

นี่คือการทดสอบบางส่วน:

let heap = new Heap();
heap.insert("t")
heap.insert("p")
heap.insert("r")
heap.insert("n")
heap.insert("h")
heap.insert("o")
heap.insert("a")
heap.insert("e")
heap.insert("i")
heap.insert("g")
heap.insert("s")

console.log(heap.isEmpty())
console.log(heap.size())
heap.delMax()
console.log(heap.pq)

Answer 1

การตั้งชื่อ

ชื่อHeapนี้ทำให้สับสนเนื่องจากนี่เป็นคิวลำดับความสำคัญไม่ใช่ฮีป ฮีปเป็นเพียงรายละเอียดการใช้งานส่วนตัวภายในที่ไม่ควรเปิดเผยต่อโลกภายนอก PriorityQueueเพียงแค่เรียกมันว่ามันคืออะไรก

heapเช่นเดียวกับ อันนี้เป็นตัวแปรท้องถิ่นที่มีขอบเขต จำกัด และมีความหมายชัดเจนดังนั้นฉันจะใช้pqเป็นชื่อในกรณีนี้

ตรงกันข้ามสนามจริงดูเหมือนจะเป็นกองไม่ได้เป็นคิวลำดับความสำคัญดังนั้นจึงควรอาจจะตั้งชื่อpqheap

delMax ดูเหมือนว่าเมธอดกำลังลบองค์ประกอบที่มีลำดับความสำคัญสูงสุด แต่จริงๆแล้วมันกำลังโผล่องค์ประกอบที่มีลำดับความสำคัญสูงสุดนั่นคือกำลังส่งคืนมัน pull, poll, pop, getMax, dequeueมีทั้งหมดชื่อที่นิยมสำหรับการดำเนินการนี้

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

บั๊ก

isEmpty()วิธีการของคุณไม่ส่งกลับอะไรเลย เป็นการประเมินนิพจน์แล้วทิ้งผลลัพธ์ไป ควรเป็นแบบนี้แทน:

isEmpty() {
    return this.n === 0;
}

การทดสอบ

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

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

จุดบกพร่องที่อาจเกิดขึ้น?

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

สามเท่าเท่ากับ

มีสถานที่หนึ่งที่คุณใช้เป็นนามธรรมความเท่าเทียมกันเปรียบเทียบ Operator หรือปฏิเสธมัน== !=โดยทั่วไปแล้วจะดีที่สุดหากคุณลืมเกี่ยวกับการมีอยู่ของมันและไม่เคยใช้มันเลย

ใช้ตัวดำเนินการเปรียบเทียบความเสมอภาคอย่างเข้มงวด ===หรือการปฏิเสธ!==แทนเสมอ

ความสม่ำเสมอ

บางครั้งคุณใช้ตัวดำเนินการเปรียบเทียบความเท่าเทียมเชิงนามธรรมและบางครั้งก็เป็นตัวดำเนินการเปรียบเทียบความเสมอภาคอย่างเข้มงวด บางครั้งคุณใช้ช่องว่าง 4 ช่องสำหรับการเยื้องบางครั้ง 2 บางครั้งคุณใช้คำว่าheapและบางครั้งลำดับความสำคัญคิว (หรือpq) เพื่ออ้างถึงคิวลำดับความสำคัญ

Getters

isEmptyและsizeน่าจะเป็น getters แทนวิธีการปกติ:

get size() {
    return this.n;
}

get isEmpty() {
    return this.n === 0;
}

และการทดสอบก็ต้องเปลี่ยนตามเช่นกัน:

console.log(pq.isEmpty);
console.log(pq.size);

ใช้นามธรรมเป็นการภายใน

ฉันเป็นแฟนตัวยงของการใช้นามธรรมสาธารณะภายในเช่นกัน ไม่ใช่ทุกคนที่เห็นด้วยกับเรื่องนี้

โดยส่วนตัวแล้วฉันจะใช้sizegetter in isEmptyแทนการเข้าถึงnฟิลด์ภายใน:

get isEmpty() {
    return this.size === 0;
}

ด้วยวิธีนี้หากมีคนขยายชั้นเรียนของคุณและแทนที่บางส่วนของชั้นเรียนด้วยการนำไปใช้งานอื่นที่ไม่ใช้nฟิลด์isEmptyจะยังคงทำงานได้ไม่เปลี่ยนแปลง

const เกิน let

เมื่อ ECMAScript 2015 เปิดตัวletและconstความเชื่อมั่นทั่วไปletเป็นสิ่งใหม่varคุณควรใช้let. ส่วนตัวผมไม่เห็นด้วยและผมคิดว่าconstควรจะเป็นใหม่varและคุณควรเสมอconst เว้นแต่คุณจริงๆจริงๆจริงๆต้องอีกครั้งกำหนดและไม่สามารถหาวิธีรอบ จากนั้นใช้let.

ในรหัสของคุณheap, maxและtempไม่เคยมีพระราชเสาวนีย์ให้คุณสามารถใช้constสำหรับพวกเขาแทน

ฟิลด์คลาส

nและpqอาจจะเป็นเขตชั้น โปรดทราบว่าเขตชั้นขณะนี้ข้อเสนอขั้นที่ 3 ซึ่งหมายความว่าในขณะที่มันเป็นอย่างสูงว่าพวกเขาจะจบลงด้วยการเปลี่ยนแปลงในรายละเอียดภาษา ECMAScript พวกเขายังไม่ได้รับการยอมรับเลยและไม่ได้รับหน้าต่างสำหรับ 2020 การเปิดตัวแน่นอน

class PriorityQueue {
    n = 0;
    pq = [];

    // no constructor needed, all fields already initialized
}

วิธีการและฟิลด์ส่วนตัว

swim, sink, lessและexchควรจะมีวิธีการส่วนตัวที่พวกเขาไม่ควรจะเป็นส่วนหนึ่งของประชาชน API nเดียวกันสำหรับเขตข้อมูลชั้นเรียน

pq(หรือheap) ควรเป็นแบบส่วนตัวด้วย คุณกำลังใช้มันภายนอกในการทดสอบ แต่ฉันไม่คิดว่านี่เป็นสิ่งที่ควรเปิดเผยกับโลกภายนอก

class PriorityQueue {
    #n = 0;
    #heap = [];

    get size() {
        return this.#n;
    }

    get isEmpty() {
        return this.size === 0;
    }

    #swim(k) {
        while (k > 1 && this.#less(Math.floor(k / 2), k)) {
            this.#exch(Math.floor(k / 2), k);
            k = Math.floor(k / 2);
        }
    }

    #sink(k) {
        while (2 * k <= this.#n) {
            let j = 2 * k;

            if (this.#heap[j + 1] !== null) {
                if (k > 1 && this.#less(j, j + 1)) {
                    j++;
                }
            }

            if (this.#heap[k] > this.#heap[j]) {
                break;
            }
            this.#exch(k, j);
            k = j;
        }
    }

    insert(v) {
        this.#heap[++this.#n] = v;
        this.#swim(this.#n);
    }

    getMax() {
        const max = this.#heap[1];
        this.#exch(1, this.#n--);
        this.#heap[this.#n + 1] = null;
        this.#sink(1);
        return max;
    }

    #less(i, j) {
        return this.#heap[i] < this.#heap[j];
    }

    #exch(i, j) {
        const temp = this.#heap[i];
        this.#heap[i] = this.#heap[j];
        this.#heap[j] = temp;
    }
}

โปรดทราบว่าเมธอดส่วนตัวยังอยู่ในขั้นตอนที่ 3

ข้อ จำกัด ของ API

ตามที่ใช้ในปัจจุบันค่าที่จัดเก็บในคิวลำดับความสำคัญของคุณและลำดับความสำคัญที่กำหนดให้กับค่านั้นเป็นสิ่งเดียวกัน สิ่งนี้ จำกัด มาก:

• คุณไม่สามารถจัดลำดับความสำคัญที่แตกต่างจากการจัดลำดับตามธรรมชาติของค่าได้ ตัวอย่างเช่นคุณไม่สามารถมีลำดับความสำคัญได้โดยลำดับความสำคัญจะขึ้นอยู่กับความยาวของสตริงแทนที่จะเป็นลำดับความสำคัญของพจนานุกรม
• คุณสามารถจัดเก็บเฉพาะค่าในคิวลำดับความสำคัญของคุณที่มีการสั่งซื้อทั้งหมด โปรดทราบว่าใน ECMAScript นี่เป็นเรื่องจริงเล็กน้อยเนื่องจากวัตถุทั้งหมดเรียงลำดับกันโดยสิ้นเชิง แต่การจัดลำดับไม่ได้ใช้งานง่ายเสมอไปหรือคุณรู้หรือไม่ว่าผลลัพธ์ของ{ b: "a", a: "b" } < ["a", 2]มันคืออะไร?

โดยทั่วไปการใช้งานลำดับความสำคัญของคิวจะแก้ไขปัญหานี้ได้ด้วยวิธีใดวิธีหนึ่ง:

1. แต่ละค่ามีความเกี่ยวข้องกับลำดับความสำคัญที่เป็นตัวเลข
2. ลำดับความสำคัญถูกสร้างอินสแตนซ์ด้วยฟังก์ชันการเปรียบเทียบที่แสดงความสัมพันธ์การสั่งซื้อทั้งหมดระหว่างค่า

โซลูชัน # 1 หมายความว่าคุณเปลี่ยนลายเซ็นหรือinsertวิธีการของคุณเป็นดังนี้:

insert(v, p)

จากนั้นใช้pเป็นคีย์สำหรับฮีป

โซลูชัน # 2 หมายความว่าคุณเปลี่ยนลายเซ็นของตัวสร้างเป็นแบบนี้:

constructor(f)

และจากนั้นใช้fภายในเป็นฟังก์ชั่นการเปรียบเทียบแทนless<

นี่คือภาพร่างคร่าวๆของสิ่งที่จะมีลักษณะเหมือนตัวเลือก # 1 เฉพาะการเปลี่ยนแปลงที่อยู่ในinsertและless:

insert(v, p) {
    this.#heap[++this.#n] = { element: v, priority: p };
    this.#swim(this.#n);
}

#less(i, j) {
    return this.#heap[i].priority < this.#heap[j].priority;
}

การใช้งานจะมีลักษณะดังนี้:

pq.insert("tally", 2);
pq.insert("plus", 1);
pq.insert("rust", 8);
pq.insert("no", 127);

เวอร์ชันสำหรับตัวเลือก # 2 จะมีลักษณะดังนี้:

#comparator;

constructor(f) {
    this.#comparator = f;
}

#less(i, j) {
    return this.#comparator(this.#heap[i], this.#heap[j]);
}

และการใช้งานเช่นนี้:

const pq = new PriorityQueue((a, b) => a.length < b.length);

เพิ่มเติม API

เป็นคอลเลกชัน, คิวลำดับความสำคัญของคุณควรใช้Iterableอินเตอร์เฟซ

ทั้งหมดโครงสร้างข้อมูลที่สำคัญในห้องสมุดมาตรฐาน ECMAScript มีวิธีการentries, และkeys valuesมันสมเหตุสมผลที่จะสอดคล้องกับอินเทอร์เฟซนั้นเช่นกัน

Answer 2

การจัดรูปแบบ

การจัดรูปแบบรหัสเป็นธรรมที่สอดคล้องกันในแง่ของจุดสิ้นสุดบรรทัดแม้ว่าจะมีเส้นคู่หายไปจุดคู่กึ่ง - เช่นในและswim() sink()แม้ว่าพวกเขาจะไม่จำเป็นเสมอไป แต่ก็ควรมีความสม่ำเสมอ

วิธีที่ไม่มีค่าส่งคืน

isEmptyวิธีไม่มีreturnคำหลักหรือผลข้างเคียงใด ๆ

isEmpty() {
  this.n === 0;
}

สันนิษฐานว่าควรเป็นreturnค่าบูลีน

การประกาศตัวแปร

constสามารถใช้งานได้maxเนื่องจากไม่เคยได้รับมอบหมายใหม่ แนวทางปฏิบัติที่แนะนำคือการใช้ค่าเริ่มต้นconstจากนั้นเมื่อเห็นว่าจำเป็นต้องมอบหมายใหม่ให้เปลี่ยนไปletใช้ วิธีนี้ช่วยหลีกเลี่ยงการมอบหมายงานซ้ำโดยไม่ได้ตั้งใจ

การสลับค่าโดยไม่มีตัวแปรชั่วคราว

สามารถใช้การกำหนด Destructuringเพื่อสลับตัวแปร

exch(i, j) {
  [this.pq[i], this.pq[j]] = [this.pq[j], this.pq[i]];
}

อย่างไรก็ตามดูเหมือนว่าอาจช้ากว่าเทคนิคอื่น ๆ แม้ว่าบล็อก V8 จะอ้างว่า " เมื่อเรายกเลิกการปิดกั้นการวิเคราะห์การหลีกเลี่ยงเพื่อกำจัดการจัดสรรชั่วคราวทั้งหมดการทำลายโครงสร้างอาร์เรย์ด้วยอาร์เรย์ชั่วคราวจะเร็วเท่ากับลำดับการมอบหมายงาน " ¹ . มี "แฮ็ก" ที่แนะนำในคำตอบ SO นี้โดย showdevซึ่งดูเหมือนจะเป็นวิธีที่เร็วที่สุดในการสลับตัวแปร :

this.pq[i] = [this.pq[j], (this.pq[j] = this.pq[i])][0];

ใช้ความยาวอาร์เรย์แทนตัวแปร n

ฉันอาจผิด แต่อาจเป็นไปได้ที่จะกำจัดnตัวแปรและใช้ประโยชน์this.pq.length- อาจต้องมีการปรับเปลี่ยนสิ่งต่าง ๆ (เช่นการแทรกด้วยตนเองundefinedที่จุดเริ่มต้นของอาร์เรย์เป็นต้น)