連結リストの速度をTypeScriptで検証してみた

連結リストと配列における処理速度の違いについて検証してみたのでまとめます。

連結リストとは？

一言で言うと「配列の亜種」です。できることは大体同じです。（すごくまさかりが飛んできそうなので話半分に聞いて下さい。）

違いを人で例えるならば、配列は人が一列に並んだ状態です。逆に連結リストでは人は並んでおらず、各々が「自分の次は○○さんで、あそこにいます」と覚えている状態です。この違いで、その人達に対して何かを行いたい時にかかる労力が変わります。

「30番目の人の名前を聞きたい！」という時、人が一列に並んでいれば30人目にはすぐに会えますが、散らばっている場合（連結リスト）は30人目にたどり着くまでに29人に会い、次の人の場所を聞かなくてはいけません。

29~30番目の間に人を入れたい時、配列の場合は30人目以降の全員が一歩後ろに下がる必要がありますが、連結リストの場合は29人目の人が次の人を覚え直すだけで済みます。

下記に軽く得意な処理をまとめてみました。

	連結リスト	配列
挿入	○
削除	○
n番目へのアクセス		○
要素数のカウント		○

検証

今回は挿入の処理を例にとり、JavaScript（書くのはTypeScript）で検証してみます。

ライブラリ

TypeScriptおよびJavaScriptでは標準で連結リストはサポートされていないため、Buckets-JSというライブラリを使いました。連結リストの他にもスタックやキューなど、さまざまなデータ構造を扱えます。

https://github.com/mauriciosantos/Buckets-JS

挿入の速度比較

1~Nの要素が入ったデータを用意し、適当な場所に挿入するプログラムを組みました。

import * as BucketsJs from 'buckets-js'

// 要素数を指定
const SIZE: number = 100000;

let linkedList = new BucketsJs.LinkedList();
let array = [];

// 乱数生成用のメソッド定義
const getRandom = ( min, max ) => {
    var random = Math.floor( Math.random() * (max + 1 - min) ) + min;
    return random;
}

// 初期の配列・連結リストを作る
for(let i = 1; i <= SIZE; i++) {
    linkedList.add(i);
    array.push(i);
}

// 連結リストの場合の計測
console.time("linkedList")
for(let i = 1; i <= 1000; i++) {
    linkedList.add(9999, getRandom(0, SIZE - 1)); // 挿入場所はランダム
}
console.timeEnd("linkedList");

// 配列の場合の計測
console.time("array")
for(let i = 1; i <= 1000; i++) {
    array.splice(1000, 0, getRandom(0, SIZE - 1)); // 挿入場所はランダム
}
console.timeEnd("array");

結果は以下のようになりました

linkedList: 1365.697ms
array: 929.606ms

普通の配列のほうが速い ですね。どうしてこうなった。

考察

今回はC言語で見られるポインタの指定ではなく、「n番目の要素に追加」という処理だったため、連結リストの苦手な「n番目へのアクセス」の処理も走るので遅かったと見られます。毎回人を間に入れるために場所を人に聞き回ってる状態です。

上記の例では乱数を生成し、適当な位置に挿入していましたが、0番目に挿入するように変更すると連結リストがめっちゃ速くなります。逆に配列は全員が一歩後ろに下がる必要があるため遅いです。

console.time("linkedList")
for(let i = 1; i <= 1000; i++) {
    linkedList.add(9999, 0); // 0番目に挿入
}
console.timeEnd("linkedList");

console.time("array")
for(let i = 1; i <= 1000; i++) {
    array.splice(1000, 0, 0); // 0番目に挿入
}
console.timeEnd("array");

linkedList: 0.485ms
array: 947.992ms

なので挿入の処理自体は得意であることが確認できました。 （※：0番目の挿入のみなら、キューでも良い気がしますがここでは割愛）

同時にn番目へのアクセスがとても苦手であることがわかりました。

まとめ

JavaScriptで連結リストと配列の速度の違いについて検証しました。

他にも配列に存在する要素数の上限が連結リストにはなかったり、メモリの使用量が違ったりと違いが多くあります。wikipediaに詳しく載っていたので興味のある人はぜひ見てみてください。

https://ja.wikipedia.org/wiki/%E9%80%A3%E7%B5%90%E3%83%AA%E3%82%B9%E3%83%88

富豪的プログラミングという言葉もありますが、時にはキューやスタックなどを使ってPCに優しいコードを書けると良いなーと思いました。では。

コーディングを支える技術 ~成り立ちから学ぶプログラミング作法 (WEB+DB PRESS plus)