java - 比较 : Runtime of LinkedList addFirst() vs. ArrayList add(0, item)

Question

我和我的搭档正在尝试编写 LinkedList 数据结构。我们已经完成了数据结构，并且它可以使用所有必需的方法正常运行。我们需要对 LinkedList 类中的 addFirst() 方法与 Java 的 ArrayList 结构的 add(0, item) 方法的运行时间进行比较测试。我们的 LinkedList 数据结构的 addFirst() 方法的预期复杂度是 O(1) 常量。这在我们的测试中成立。在计时 ArrayList add() 方法时，我们期望复杂度为 O(N)，但我们再次收到大约为 O(1) 常数的复杂度。这似乎是一个奇怪的差异，因为我们正在使用 Java 的 ArrayList。我们认为我们的时间结构可能存在问题，如果有人能帮助我们找出问题，我们将不胜感激。下面列出了我们用于这两种方法计时的 Java 代码:

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);
    }

}

Answer 1

您想测试不同的inputSize，但您执行操作以测试timesToLoop 次，这是常量。所以当然，它需要相同的时间。你应该使用:

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