[JAVA] Addressing the issue of slow random access for linkedList, a collection type class

After reading the article Mechanism and characteristics of Collection implementation class often used in Java, I used arrayList to implement the mechanism I am trying to create. I was wondering which of the linkedList is better, so I will write the result of checking the calculation time.

The mechanism I tried to make

What I tried to make was a "route array". For the function f defined for natural numbers greater than or equal to 2 We define n 2 </ sub> as n 2 </ sub> = f (n 1 </ sub>) using the natural number n 1 </ sub>. This is repeated until n m </ sub> is out of the domain of f. It is an attempt to record n k (1 <= k <= m) </ sub> at that time as an array.

After securing the array, search for the elements in the path and extract the smallest value from the range that meets the conditions (for example, the range that cannot be determined unless the entire array is determined, such as the 10 numbers in the middle of the array). I am aiming for it.

Why you should use the collection type

The reason you should use the collection type instead of a regular array is that *** the length of the array is indeterminate ***. Considering this point, I think that linked list is better because it is easy to add arrays. On the other hand, there is a concern that the calculation speed may be slow if it is a linked list because the element access of the array is required to detect the minimum value.

Behavioral guidelines

Based on the above, consider the class to use.

-Check the speed of element search of linkedList after creating an array. -If the calculation speed is slow, compare it with the array addition speed of arraylist. -If the calculation speed can be tolerated, implement it using the linked list as it is.

Start actual calculation

The reason why the element search of the linkedList is slow is that the linkedlist does not have the index of the entire element, but only the information of the elements before and after it. Because we need to follow. As a result, random access is slower than arraylist, which has an index for the entire element. However, what I am trying to do this time is to extract a certain number of elements from a certain element and find the minimum value among them. In this case, if we can get the value of the element and the information to the next element at the same time, will there be no speed loss?

Therefore, the following code is used for comparison using the for statement and the extended for statement.

test.java


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() {
        //Get start time in milliseconds
        long ts1 = System.currentTimeMillis();
        //Processing execution
        addArrayNumbersWithFor();
        //Get end time in milliseconds
        long te1 = System.currentTimeMillis();
        //Processing time milliseconds
        long tmsec1 = te1 - ts1;
        //Processing time seconds
        double tsec1 = (double) tmsec1 / 1000.0;

        System.out.println(sum);

        return tsec1;
    }

    static double measureCalculationTimeWithAppliedFor() {
        //Get start time in milliseconds
        long ts1 = System.currentTimeMillis();
        //Processing execution
        addArrayNumbersWithAppliedFor();
        //Get end time in milliseconds
        long te1 = System.currentTimeMillis();
        //Processing time milliseconds
        long tmsec1 = te1 - ts1;
        //Processing time seconds
        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());
  }
}
Result is, for sentence: 4.943 seconds Extended for statement: 0.008 seconds

From this result, when a simple for statement is used, the elements are always acquired in order from the first element in the loop, whereas in the case of the extended for statement, the information of the next element is obtained from the previous element. You can see that it gets and gets the next element.

Summary

If you want to add elements to an array one after another and you don't know how many to add, you'll want to use linkedlist. The bottleneck is the slow speed of random access, but it can be seen that there is no slow speed as the elements are acquired in order from the beginning by using the extended for statement. I haven't compared it with an ordinary array, but it's based on the premise that the collection type is used.