collection型のクラスであるlinkedListに関するランダムアクセスの遅さという課題への取り組み

JavaでよくつかうCollection実装クラスの仕組みと特性という記事を読んだ上で、自分が作ろうとしている仕組みを実装するのにarrayListとlinkedListのどっちがいいのかなぁって迷ったので、計算時間を確認してみた結果を書きます。

作ろうとした仕組み

自分が作ろうとしたのは、「経路配列」です。

2以上の自然数に対して定義されている関数fに対し、
自然数n₁を用いてn₂をn₂=f(n₁)と定義する。
これをn_mがfの定義域から外れるまで繰り返す。
その際のn_k(1<=k<=m)を配列として記録したい、という試みです。

配列確保後に、経路内の要素を検索し、条件に合う範囲(例えば配列の真ん中の10個の数字、といった、配列全体が決まらなければ確定されない範囲)の中から最小の値を抽出することを目的としています。

collection型を使うべき理由

普通の配列でなくcollection型を使うべき理由は、***配列の長さが未確定である***という点です。 この点を考えれば配列の付け足しが容易であるlinkedlistの方が良いと思います。 一方で最小値検出のために配列の要素アクセスが必要になるため、linkedlistだと計算速度が遅いのではないかという懸念点が存在します。

行動指針

以上を踏まえた点で、使うべきclassを考えます。

・配列作成後のlinkedListの要素検索の速さをみる。
・計算速度が遅いのであれば、arraylistの配列付け足し速度との比較をおこなう。
・計算速度が耐えられるものであるならば、そのままlinkedlistを用いて実装する。

実計算開始

linkedListの要素検索が遅い理由は、linkedlistは要素全体のindexを持たず、前後の要素の情報のみを有しているため、どの位置にある要素を抜き取るにも、最初からもしくは最後から順に要素を辿っていく必要があるためです。 そのため、要素全体のindexを持つarraylistに比べ、ランダムアクセスの速度が落ちます。しかしながら、今回私が行おうとしているのは、ある要素からある数の要素を抜き出し、その中の最小値を求める、というもの。これならば、要素の値を取得すると同時に次の要素への情報を入手できれば、速度ロスは起きないのでしょうか。

そこで、for文と拡張for文を用いて比較を行ったのが、以下のコードだ。

test.java

Copied!

import java.util.LinkedList;
import java.util.Iterator;

public class test {
    static final int LIMIT = 100_000;
    static LinkedList<Integer> array =  new LinkedList<Integer>();
    static long sum = 0;

    static {
        for (int i = 0; i < LIMIT; i++) {
            array.addLast(i);
        }
    }

    static void addArrayNumbersWithFor() {
        sum = 0L;
        for (int i = 0; i < LIMIT; i++) {
           sum += array.get(i);
        }
        
    }

    static void addArrayNumbersWithAppliedFor() {
        sum = 0L;
        for (int value : array) {
           sum += value;
        }
        
    }

    static double measureCalculationTimeWithFor() {
        // 開始時間をミリ秒で取得
        long ts1 = System.currentTimeMillis();
        // 処理実行
        addArrayNumbersWithFor();
        // 終了時間をミリ秒で取得
        long te1 = System.currentTimeMillis();
        // 処理時間 ミリ秒
        long tmsec1 = te1 - ts1;
        // 処理時間 秒
        double tsec1 = (double) tmsec1 / 1000.0;

        System.out.println(sum);

        return tsec1;
    }

    static double measureCalculationTimeWithAppliedFor() {
        // 開始時間をミリ秒で取得
        long ts1 = System.currentTimeMillis();
        // 処理実行
        addArrayNumbersWithAppliedFor();
        // 終了時間をミリ秒で取得
        long te1 = System.currentTimeMillis();
        // 処理時間 ミリ秒
        long tmsec1 = te1 - ts1;
        // 処理時間 秒
        double tsec1 = (double) tmsec1 / 1000.0;

        System.out.println(sum);

        return tsec1;
    }

    public static void main(String[] args) {
        System.out.println(test.measureCalculationTimeWithAppliedFor());
        System.out.println(test.measureCalculationTimeWithFor());
  }
}

結果は、 for文　　：4.943秒 拡張for文 : 0.008秒

この結果から、ただのfor文を用いた場合はloop内で常に最初の要素から順番に要素を取得しているのに対し、拡張for文の場合は、前の要素から次の要素の情報を取得して次の要素を取得していることがわかる。

まとめ

配列に要素を順々に付け足していく場合かつ付け足す個数がわからない場合は、linkedlistを使いたくなる。
そのネックはランダムアクセスの速度の遅さであるが、拡張for文を用いることで頭から順に要素を取得していく分には、速度の遅さはないことがわかる。
普通の配列との比較はしてないが、collection型を使う、という前提の元での話なので。