Java ArrayList performance

Question

public static ArrayList<Double> Cast(double angle,double step,ArrayList<Double> list){
    double x = px + Math.sin(angle/180*Math.PI)*step;
    double z = pz + Math.cos(angle/180*Math.PI)*step;

    if((int)x<0||(int)x>mapWidth-1||(int)z<0||(int)z>mapHeight-1){
        return list;
    }else{
        step+=quality;
        list.add(getHeight(x,z));
        return Cast(angle,step,list);
    } 
}

I am making a raycaster and this function return height of (direction,distance). As I need to cast almost fov/screenWidth times, this is very expensive for my application. How can I make dynamic array faster with recursion function?

If you cannot estimate an upper bound M of the size of the array prior to recursion, a LinkedList will give you O(1) append versus amortized O(1) for an ArrayList. But with a linked list, you will not benefit of O(1) for accessing a random element in the list. If you can provide such an estimate M, simply pass it as the initialCapacity to the constructor of ArrayList. — Alexandre Dupriez
– Alexandre Dupriez, Commented Mar 22, 2019 at 9:17
@AlexandreDupriez I'm now using for-iterator in order to get all heights of list. Initializing ArrayList with initial capacity will return odd size which will lead a strange output. — ProJs er
– ProJs er, Commented Mar 22, 2019 at 9:36

noiaverbale · Accepted Answer · 2019-03-22 10:02:27Z

2

Recursion functions aren't efficient, althought they resolve difficult problems in an easy way.

When you need to improve performance of a recursion function you'll probably get the best result implementing it iteratively (if possible).

Hope this piece of code helps you!

public static List<Double> cast(double angle, double step, List<Double> list) {
    while(true) {
        double x = px + Math.sin(angle / 180 * Math.PI) * step;
        double z = pz + Math.cos(angle / 180 * Math.PI) * step;

        if ((int) x < 0 || (int) x > mapWidth - 1 || (int) z < 0 || (int) z > mapHeight - 1) {
            break;
        }

        list.add(getHeight(x,z));
        step += quality;
    }

    return list;
}

edited Mar 22, 2019 at 10:02

answered Mar 22, 2019 at 8:40

noiaverbale

1,7081 gold badge14 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

ProJs er Over a year ago

Does "List" which you wrote mean ArrayList?

noiaverbale Over a year ago

List is just the interface implemented by ArrayList. Since in this method you aren't using any ArrayList specific method, but only add, which is defined in Collection interface, there is no difference at runtime in defining the param as ArrayList, List or Collection. What you get using interfaces against concrete classes is flexibility. If one day you decide that list will be a LinkedList you don't need to change every method where you pass that variable.

Collectives™ on Stack Overflow

Java ArrayList performance

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related