1

私のパートナーと私は LinkedList データ構造をプログラムしようとしています。データ構造が完成し、必要なすべてのメソッドで適切に機能します。LinkedList クラスの addFirst() メソッドと Java の ArrayList 構造の add(0, item) メソッドのランタイムの比較テストを実行する必要があります。LinkedList データ構造の addFirst() メソッドの予想される複雑さは、O(1) 定数です。これは、私たちのテストでも当てはまりました。ArrayList add() メソッドのタイミングでは、O(N) の複雑さを予想していましたが、約 O(1) 定数の複雑さを再び受け取りました。Java の ArrayList を使用しているため、これは奇妙な不一致のように見えます。タイミング構造に問題がある可能性があると考えました。問題を特定するのに誰かが助けてくれれば、非常にありがたいです.

public class timingAnalysis {

public static void main(String[] args) {

    //timeAddFirst();
    timeAddArray();

}

public static void timeAddFirst()
{
    long startTime, midTime, endTime;
    long timesToLoop = 10000;
    int inputSize = 20000;

    MyLinkedList<Long> linkedList = new MyLinkedList<Long>();

    for (; inputSize <= 1000000; inputSize = inputSize + 20000)
    {
        // Clear the collection so we can add new random
        // values.
        linkedList.clear();

        // Let some time pass to stabilize the thread.
        startTime = System.nanoTime();

        while (System.nanoTime() - startTime < 1000000000)
        {   }

        // Start timing.
        startTime = System.nanoTime();

        for (long i = 0; i < timesToLoop; i++)
            linkedList.addFirst(i);

        midTime = System.nanoTime();

        // Run an empty loop to capture the cost of running the loop.
        for (long i = 0; i < timesToLoop; i++) 
        {} // empty block

        endTime = System.nanoTime();

        // Compute the time, subtract the cost of running the loop from 
        // the cost of running the loop and computing the removeAll method.
        // Average it over the number of runs.
        double averageTime = ((midTime - startTime) - (endTime - midTime)) / timesToLoop;

        System.out.println(inputSize + " " + averageTime);
    }

}

public static void timeAddArray()
{
    long startTime, midTime, endTime;
    long timesToLoop = 10000;
    int inputSize = 20000;

    ArrayList<Long> testList = new ArrayList<Long>();

    for (; inputSize <= 1000000; inputSize = inputSize + 20000)
    {
        // Clear the collection so we can add new random
        // values.
        testList.clear();

        // Let some time pass to stabilize the thread.
        startTime = System.nanoTime();

        while (System.nanoTime() - startTime < 1000000000)
        {   }

        // Start timing.
        startTime = System.nanoTime();

        for (long i = 0; i < timesToLoop; i++)
            testList.add(0, i);

        midTime = System.nanoTime();

        // Run an empty loop to capture the cost of running the loop.
        for (long i = 0; i < timesToLoop; i++) 
        {} // empty block

        endTime = System.nanoTime();

        // Compute the time, subtract the cost of running the loop from 
        // the cost of running the loop and computing the removeAll method.
        // Average it over the number of runs.
        double averageTime = ((midTime - startTime) - (endTime - midTime)) / timesToLoop;

        System.out.println(inputSize + " " + averageTime);
    }

}

}

4

2 に答える 2

2

異なる をテストしたいのですが、一定の時間inputSizeをテストする操作を実行します。timesToLoopもちろん、同じくらい時間がかかります。以下を使用する必要があります。

for (long i = 0; i < inputSize; i++)
    testList.add(0, i);
于 2013-06-20T01:21:01.060 に答える
-1

私の知る限り、Arraylist add 操作は O(1) 時間で実行されるため、実験の結果は正しいです。arrayList add メソッドの定数時間は償却定数時間だと思います。

Java doc に従って: n 個の要素を追加するには O(N) 時間が必要なため、追加のための償却された一定の時間が必要です。

于 2013-06-20T01:18:05.913 に答える