Home > Back-end >  What is more efficient than running two nested loops?
What is more efficient than running two nested loops?

Time:11-04

I have the following program written in java, but it occupies a lot CPU usage. What is the more efficient way to do the job this code is doing?

public static ArrayList sample() {
    ArrayList arr = new ArrayList();
    for (int out = 0; out  < 10000; out   )
    {
        for (int in = 0; in < 20000; in  ) {
            arr.add(out    in);
        }
    }
    return arr;
}

CodePudding user response:

Since the content of the list is trivially computed, it's better to just not keep it all in memory, but compute it on the fly. Implementing a dedicated List for this is actually fairly easy:

public class ComputedList extends AbstractList<Integer> {
  private final int maxOut;
  private final int maxIn;

  public ComputedList(int maxIn, int maxOut) {
    if (((long) maxIn) * maxOut > Integer.MAX_VALUE) {
      throw new IllegalArgumentException();
    }
    this.maxIn = maxIn;
    this.maxOut = maxOut;
  }

  @Override
  public Integer get(int index) {
    int out = index / maxIn;
    int in = index % maxIn;
    return out   in;
  }

  @Override
  public int size() {
    return maxIn * maxOut;
  }
}

Given this code a new ComputedList(20000, 10000) will return a List<Integer> with the exact same content as the one returned by your method, but requiring a significantly smaller amount of memory (i.e. a fixed amount independent of the input values).

The "drawback" would be that this list doesn't support editing (i.e. set, remove, clear will throw an UnsupportedOperationException), which may or may not be a problem.

CodePudding user response:

Heap space error means you don't have enough memory to store all those values.

If you need all of them the only solution you have is to increase the heap memory with the -Xmx switch.

CodePudding user response:

Loops are very efficient; the problem is that you are creating a huge list. If you need many items, you'll need more heap memory. Consider using something else, like an iterator.

You can slightly optimize this by:

  • Initializing ArrayList by passing it its final size. You will avoid some internal copying this way,
  • Using an array instead of ArrayList to avoid boxing.
  • Related