How to compare pairs of elements in an ArrayList using for each loop?

Question

I have an object vector, and I need to compare it 1 to 1. That is:

for (Object o1 : list) { for (Object o2 : list) { //Do something with o1 and o2 } } 

In any case, using this approach, I will compare a couple of times! Using a “C” style approach, I would do the following:

 for (i=0; i<n-1; i++) { for (j=i+1; j<n; j++) { //Do something with list[i] and list[j] } } 

where n is the length of the list.

Is there a way to do this using for each loop?

Adding

Using a for-each loop is optional. In any case, I am disturbed by problems with performances. Is a for-each loop faster than a simple index direct access?

Answer 1

Explicitly, it’s clear what your intention is with C-like for loop-loop loops over each pair exactly once, so the same pair with reverse members, for example. (a, b) and (b, a) are not re-processed. This is what I would recommend; It also works in Java.

However, if you absolutely need to have an extended for loop, you can get the inner loop to work on the sublist using the List subList method, starting with the next element.

 for (Object o1 : list) { List<Object> subList = list.subList(list.indexOf(o1) + 1, list.size()); for (Object o2 : subList) { //Do something with o1 and o2 } } 

Answer 2

Assuming list declared as List<Whatever> , you can achieve this behavior properly using ListIterator and not for every loop

 ListIterator<Whatever> iteratorI = list.listIterator(); if (iteratorI.hasNext()) { for (Whatever whateverI = iteratorI.next(); iteratorI.hasNext(); whateverI = iteratorI.next()) { ListIterator<Whatever> iteratorJ = list.listIterator(iteratorI.nextIndex()); for (Whatever whateverJ = iteratorJ.next(); iteratorj.hasNext(); whateverJ = iteratorJ.next()) { //do the comparison here... } } } 

Answer 3

Comments suggest that you do this c-style or track an explicit index. These are good suggestions. But if you insist on doing this with a new style for the loop, there is a way:

 for (Object o1 : list ) { final int o1Index = list.indexOf(o1); final int listSize = list.size(); for (Object o2 : list.subList(o1Index + 1, listSize)) { //Do something with o1 and o2 } } 

The idea is that any o2 that precedes o1 in the list is already processed, and you do not need to process o1 against yourself. This way you get a sublist consisting only of elements following o1 and extract o2 from this subscriptions.

This will fail if any items appear more than once in the list.

I did a breakdown of o1Index and listSize for clarity, but in practice you would probably include them.

Another option is to copy the source list and, before starting the inner loop, delete the front element each time. This correctly takes into account repeating elements, but takes up more space.

 final List<Object> newList = new ArrayList<>(list); for (Object o1 : list) { newList.remove(0); for (Object o2 : newList) { // Do something } } 

Answer 4

The improved for loop is not suitable in all situations. If you avoid using an index, just use indexOf in a loop, your code will be less efficient ( indexOf is a linear search) and non-idiomatic.

In my opinion, the best answer is to use explicit indexes.

 for (i=0; i<n-1; i++) { for (j=i+1; j<n; j++) { // do something with list.get(i) and list.get(j) } } 

One of the situations when you should avoid using get is that List is a LinkedList , because get for a LinkedList not a constant time operation. In this case, I would do

 List<Object> copy = new ArrayList<>(linkedList); for (i=0; i<n-1; i++) { for (j=i+1; j<n; j++) { // do something with copy.get(i) and copy.get(j) } } 

Answer 5

Do you need performance? Here you go!

Using a for loop for each loop is optional.

 int s = list.size(); for(int i = 0; i < s-1; i++){ for(int n = i+1; n< s;n++){ if(list.get(i).equals(list.get(n))){ System.out.println("Duplicate"); } } } 

You will never compare a combination twice.

Also, to fully answer your question: foreach requires more resources and reduces performance

To achieve the same result using the foreach statement, you would create a large heap and slow down the application, and also more instructions are processed by the processor so that you not only lose memory, but also calculate performance. Also, try to avoid calling the size () method more than once, so your list will not be changed in this procedure. It also reduces CPU usage, but requires very little more RAM (int s).

Thus, your approach to "C" is almost optimal.

For convenience, I used java api calls, it should also be easy to use this example in your target structure.

EDIT: Improve performance even further by preserving the size of the list to reduce method calls.

Answer 6

This is a very specific case, a comparison is just an operation of infinity of other operations, other non-commutative operations make sense for all combinations (this is just an example).

Thus, for such a case there is no improved cycle.