Best Practices for Performing Calculations on ArrayList With Million or More Elements

I was doing an interview test and had no real approach to solving the problem. I am hoping you guys can help me figure out what are the best methodologies for this sort of problem.

The question consisted of an ArrayList at max capacity, which is Integer.MAX_VALUE.

ArrayList<User> arr = new ArrayList<User>(Integer.MAX_VALUE);

This was hypothetical, they also mentioned

arr.ensureCapacity(Integer.MAX_VALUE); // shows no issues

The User object was said to contain Int values a and b.

The question was, what is the best way of calculating the value of c for every "User" where c is the result of multiplying a,b values.

My answer was to break up the list into smaller lists, and then iterate through all the smaller lists in parallel. As I make calculations I then add the result to a results list with the value of c. Something like this,

List<User> firstNElementsList = list.stream().limit(n).collect(Collectors.toList());

I did not know what would be a good size for N. I just said N can be arbitrary such as 1000 or 10000 or 100000. The ladder would be 10 lists to process.

I failed the test, so this answer was not sufficient enough. Any better ideas?

Use parallel stream processing, and to keep it lightweight, use an IntStream to collect the result as int[]:

int[] cs = arr.parallelStream().mapToInt(u -> u.getA() * u.getB()).toArray();

Note that when using parallel processing, the order of results may not align with the original order of the input, but this was not stated as a requirement, which was just to "collect all a * b"; it did not say you had to know which User each value of c came from.

Although not stated, or arbitrary values of a and b, u.getA() * u.getB() may result in arithmetic overflow, so the safer approach is to use long values for the result:

long[] cs = arr.parallelStream().mapToLong(u -> u.getA() * u.getB()).toArray();

As an interviewer, I would hope the candidate would ask for clarification on this point and offer the second option if the answer was "yes", and justify the slightly lighter weight first option if there was a guaranteee that a * b never overflows int.

The rough size of the data to be parsed is 2^31 * sizeof(User). Assuming only fields int A and int B, this is roughly 17.17GB. As noted by Bohemian, because integer multiplication may result in a long, the size of the output array c is also roughly the same size 2^31 * 8 bytes = 17.17GB.

Some notes which may be useful include:

1. Each User can be processed independently. Ex: the data can be split into 1GB chunks and processed on several machines then aggregated. Similarly, the data set on each machine can be processed in parallel.
2. The operation to calculate C is relatively inexpensive. An alternative to calculating C is dynamically resolving the value as needed (which will also save 17GB of space). Alternatively, if C is expensive to calculate it can be cached after calculating but only calculated as needed.

The question seems to ask how to best calculate the value of 'c' for every user rather than just asking for the calculated 'c' for every user. This suggests maybe the question is asking how to approach calculating derived fields in a large data-set. As such, a lazy approach may be acceptable and worth considering (time vs space trade-off).

With that said, if C needs to be pre-calculated all at once and there is only 1 machine, using a parallel stream is a reasonable approach. Behind the scenes, this will distribute the work across the number of cores on the machine and is well suited to computation operations.

In my opinion, your answer is not wrong, but has a couple of issues that might've led the interviewer to deny your answer:

1. You said you would iterate the different chunks of the list in parallel yet you provide sequential code instead List<User> firstNElementsList = list.stream().limit(n).collect(Collectors.toList());.
2. After calculating c you wanted to add the result into a results list. This will actually negate the benefits of the parallelization you did earlier. The reason for this is that parallel thread's execution order is unpredictable so these threads end up in a race condition trying to modify the same resource (the results list) potentially at the same time putting the resource in an inconsistent state. This means that to achieve what you described, you need to synchronize these parallel threads at the time of saving c into the results list. Effectively making the whole thing sequential again as each thread needs to wait for the previous thread to finish before modifying the results list.

In my opinion, a faster approach would be to reuse the the user object and have a place holder for c in it where you can store it after calculation. If that's not allowed, create the results list of objects that contain a placeholder for the future value of c. This way, after calculating each c, you can also (in parallel) retrieve the respective placeholder of c from the results list and store it there. No need to synchronize this as you are not making modifications to the results list itself but to the individual objects in it.