高性能キューの実現 – Elegant Queueライブラリ

概要

JavaScript や TypeScript では、配列がキューの実装に頻繁に使用されます。組み込みの shift() メソッドは、ゼロ番目のインデックスにある要素を削除し、残りの要素を下にシフトしますが、これは要素の再インデックス化が必要なため O(n) の時間計算量を持ちます。

サーキュラーバッファの利点

特に大規模なデータセットを扱う場合にキュー操作を最適化するために、サーキュラーバッファは非常に効果的なソリューションです。サーキュラーバッファは固定サイズの配列で要素を管理し、ラップすることで enqueue と dequeue 操作を O(1) の時間計算量で実行することができます。

主な利点:

• メモリ効率: サーキュラーバッファは固定サイズの配列を使用し、ラップすることで、サイズ変更の必要がなく、メモリオーバーヘッドを最小限に抑えます。
• 一貫した O(1) のパフォーマンス: 操作が一定の時間内で完了し、配列のサイズ変更やシフトによるパフォーマンスの低下を避けることができます。
• メモリ断片化の回避: 効率的なメモリ使用と動的なキューサイズに関する断片化のリスクの低減を実現します。

📚 はじめに

elegant-queue は CommonJS と ES モジュールの両方をサポートしています。

CommonJS

const { Queue } = require("elegant-queue");

ES モジュール

import { Queue } from "elegant-queue";

🔎 機能の紹介

constructor(array: T[])
コンストラクタは、提供された array から新しいキューを初期化します。

enqueue(value: T)
このメソッドは、キューの末尾に新しい要素を追加します。

dequeue()
このメソッドは、キューの先頭にある要素を削除して返します。キューが空の場合、EmptyQueueException がスローされます。

peek()
このメソッドは、キューの先頭にある要素を削除せずに返します。キューが空の場合、EmptyQueueException がスローされます。

clear()
このメソッドは、キューのすべての要素をクリアします（実質的にキューを初期状態にリセットします）。

size()
このメソッドは、現在キューに含まれている要素の数を返します。

isEmpty()
このメソッドは、キューが空かどうかをチェックします。 _head が _tail と等しい場合に true を返し、そうでない場合は false を返します。

🌈 使い方の例

使用例

import { Queue } from "elegant-queue";

const queue = new Queue([1, 2, 3, 4, 5]);
queue.enqueue(6); // [1, 2, 3, 4, 5, 6]

const item = queue.dequeue();
console.log(item); // 1 

console.log(queue); // [2, 3, 4, 5, 6]

例外処理の例

import { Queue, EmptyQueueException } from "elegant-queue";

try {
    const item = queue.dequeue(); // キューからアイテムを削除しようとします。
    console.log('Dequeued item:', item);
} catch (error) {
    if (error instanceof EmptyQueueException) {
        console.error('キューが空です。アイテムを削除できません。');
    } else {
        console.error('予期しないエラーが発生しました:', error);
    }
}

⚡️ 性能 (100万)

以下のベンチマークは、標準の配列ベースのキューと elegant-queue を比較しています。

配列キューのパフォーマンス:

console.time('ArrayQueue Enqueue Time');
const numbers: Array<number> = [];

for (let i = 0; i < LARGE_DATA_SIZE; i++) {
  arrayQueue.push(i);
}
console.timeEnd('ArrayQueue Enqueue Time');

console.time('ArrayQueue Dequeue Time');
while (arrayQueue.length > 0) {
  arrayQueue.shift();
}
console.timeEnd('ArrayQueue Dequeue Time');

配列キューのパフォーマンス結果:

  console.time
    ArrayQueue Dequeue Time: 109907 ms

Elegant Queue のパフォーマンス:

console.time('ElegantQueue Enqueue Time');
const numbers = new Array<number>();

for (let i = 0; i < LARGE_DATA_SIZE; i++) {
    numbers.push(i);
}

const elegantQueue = new Queue(numbers);
console.timeEnd('ElegantQueue Enqueue Time');

console.time('ElegantQueue Dequeue Time');
while (elegantQueue.size() > 0) {
  elegantQueue.dequeue();
}
console.timeEnd('ElegantQueue Dequeue Time');

Elegant Queue のパフォーマンス結果:

  console.time
    ElegantQueue Dequeue Time: 5 ms

参考までに: 配列の shift() メソッドは、削除後に要素の再インデックス化が必要なため、O(n) の時間計算量を持ちます。それに対して、elegant-queue はサーキュラーバッファ設計を利用することで、enqueue と dequeue 操作の両方を O(1) の時間計算量で提供し、大規模なデータセットでのパフォーマンスを大幅に向上させます。