Loop and comparison optimization

Question

I have the following code:

    ArrayList<Integer> count = new ArrayList<>();
    for(int i=0;i<l.size();i++)
        count.add(0);

    for(int i=0;i<list.size();i++)
    { 
        for(int j=0;j<l.size();j++)
        {
            if(list.get(i).equals(l.get(j)))
            {
                int val = count.get(j);
                count.set(j, val+1);
            }   
        }
    }

My problem is that when running the two for loops and comparison, it takes an extremely long time to run, since the loops I am iterating through have:

size > 150000, also both "list" and "l" are ArrayLists

Is there any way to optimize this so that the time taken to run the program decreases?

I have looked at this: for loop optimization and many more pages however the solutions don't help in my instance.

---------UPDATE----------

The comparison is for integer value, this if "list" contains the number 8 four times and "l" contains the number 8, the counter should increment to 4.

Similar to what a Hash Map does, however I personally do not like Hash Maps which is why I am not using them.

Any help would be greatly appreciated.

you might want to include an explenation what this loop is supposed to do. Also include a [MCVE](http://stackoverflow.com/help/mcve) with input and output. — SomeJavaGuy, Mar 29 '16 at 08:21
it looks like a naive occurrence counter. Cosider using `Map` for `count` instead of `List` — Alex Salauyou, Mar 29 '16 at 08:23
The nested loops will finally iterate 150000 x 150000 times if I do understand well. No wonder that it can take some time. Do you have any idea of how it would take? — C.Champagne, Mar 29 '16 at 08:26
@KevinEsche its meant to increment the counter variable if the elements in both arraylists match — Kyhle Ohlinger, Mar 29 '16 at 08:27
@C.Champagne its take a few minutes, that is why im asking what I can do in order to speed up the process, even if it is changing the loops into something else — Kyhle Ohlinger, Mar 29 '16 at 08:28
@KyhleOhlinger so if both `List` do contain the number `2` twice, the correct count result should be `4`? — SomeJavaGuy, Mar 29 '16 at 08:28
@KyhleOhlinger please update your question so we could exactly understand what you need--I bet there nice and effective O(N) solution for whatever you're trying to implement. Now your intention is not clear. Examples will help. — Alex Salauyou, Mar 29 '16 at 08:29
I don't get why don't you like `HashMap`s? They have specific purpose and could be very useful in cases like yours. — Konstantin Yovkov, Mar 29 '16 at 08:35
@KonstantinYovkov I am attempting to better a portion of someone elses code which is >1 million lines, in which they have used the results obtained from the for loops above, the loops are the only parts which are slowing the process down and as such I don't want to have to modify all the resulting code as well — Kyhle Ohlinger, Mar 29 '16 at 08:38

Konstantin Yovkov · Accepted Answer · 2016-03-29T08:48:21.363

4

From what I can see, you're trying to count how many times the elements from list appear in l.

And currently you've implemented a fairly naive solution that's of complexity O(n * m) (assuming that list has n elements and l has m elements).

In order to improve the performance, you need to improve the time complexity of your solution. You could create a HashMap<Integer, Integer> that will hold how many times a number is appearing in l and then use it while iterating through the elements of list.

Map<Integer, Integer> map = new HashMap<>();
for (Integer i : l) {
    map.put(i, map.getOrDefault(i, 0) + 1);
}

Then, for each element of list, you just need to check how many times its value appears in l. Again, I'll use a Map:

Map<Integer, Integer> count = new HashMap<>();
for (Integer value : list) {
    Integer temp = count.get(value);
    if (temp != null) {
        count.put(value, temp + 1);
    } else {
        count.put(value, map.getOrDefault(value, 0) + 1);
    }
}

Since querying a HashMap takes a constant time (O(1)), then this solution will work with a O(n + m) complexity, which is far much better from O(n * m).

However, since you didn't explain what exactly you're problem is, nor what is the content of the lists, I cannot guarantee that these snippets are exactly what you need, but you should be able to adjust this approach to your problem.

edited Mar 29 '16 at 08:48

answered Mar 29 '16 at 08:30

Konstantin Yovkov

62,134
8
100
147

2

you're the King of refactoring ) – Alex Salauyou Mar 29 '16 at 08:31
I am not quite sure if this is what OP wants, but if he wants to check how many times elements from `list` appear in `l` wont this create wrong results (as for count == 1) for non existing values?. (If that´s what he wants) – SomeJavaGuy Mar 29 '16 at 08:38
1

@KevinEsche, you're right. I supposed that if a number `x` appears in any of the lists, it should be counted once. But like I said, I cannot guarantee this is exactly what the OP needs, but they should be able to easily adjust this approach to their problem. :) – Konstantin Yovkov Mar 29 '16 at 08:40
It could happen than, for two different integer values, the hash function give the same position. It could be better to put an array. – Jose Luis Mar 29 '16 at 08:41
@JoseLuis, yup you're right. But in this case we need to know the maximal value in the lists, because we need to know the size of the array. :) And if it's something like `10^18`, then our solution will be of `O(10^18)` (because of the array initialization), which is not better than the naive `O(n * m)` approach. :) – Konstantin Yovkov Mar 29 '16 at 08:44
@KonstantinYovkov Thank you, I have managed to edit your solution and store the resulting Key Value Pairs into another ArrayList, which has sped up the time tremendously – Kyhle Ohlinger Mar 29 '16 at 09:00

Loop and comparison optimization

1 Answers1