3

I have a list of Integer List, like list1=(1,2,3) and list2 = (0,1).

my list of lists contains list1 and list2. It could contains more but for the example i took only two lists.

The question is to get the index of the list with minimum size using java stream.

Here is my program and it work using only the for loop method.

import java.util.ArrayList;

public class Example {

     public static void main( String[] args ) {


         ArrayList<Integer> list1 = new ArrayList<>();
         list1.add(1);list1.add(2);list1.add(3);

         ArrayList<Integer> list2 = new ArrayList<>();
         list2.add(0);list2.add(1);

         ArrayList<ArrayList<Integer>> listOLists = new ArrayList<>();
         listOLists.add(list1);
         listOLists.add(list2);
         printTheIndexOfTheListWithTheMinSize(listOLists);
     }

    private static void printTheIndexOfTheListWithTheMinSize( ArrayList<ArrayList<Integer>> listOLists ) {
        int minSize  = listOLists.get(0).size();
        int minIndex = 0;
        int i=0;
        for ( ArrayList<Integer> list:  listOLists ) {

            if (list.size()<minSize)
            {
                minSize = list.size();
                minIndex=i;
            }
            i++;

        }
        System.out.println(minIndex);
    }
}

Could you please give me a hint how to do that using Java stream API.

Note that i'm calling this method many times in a heavy calcul, so the awnser should take that in consideration.

Improve this question
1
  • 1
    After list2 is declared and initialized no elements are added to it. In the next line 0 and 1 are added to list1. A typo? Commented Nov 29, 2018 at 10:12

5 Answers 5

Reset to default
6

Not really elegant, because it requires boxing and unboxing, but...

Optional<Integer> minIndex = 
    IntStream.range(0, list.size())
             .boxed()
             .min(Comparator.comparingInt(i -> list.get(i).size()));
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

This boxing overhead is far less overhead than the indexOf operations of other answers…
Alternatively, without boxing IntStream.range(0, list.size()) .reduce((a, b) -> list.get(a).size() <= list.get(b).size()? a: b)
3

One way to possibly do that would be using indexOf and Collections.min with a comparator as:

int minIndex = listOLists.indexOf(Collections.min(listOLists, 
                                   Comparator.comparingInt(List::size)));
Improve this answer

Comments

3

Stay away from solutions using indexOf. While they may allow to write rather short code, this indexOf operation bears a content-based linear search operation, invoking equals on the list elements until a match is found.

While it might look like a trivial thing, as all sub-lists differ in size, except for the matching element, most of Java 8’s List implementations do not use the size to short-cut the comparison.

To illustrate the issue,

use the following helper class

class Counter {
  int count;
  @Override
  public boolean equals(Object obj) {
    count++;
    return super.equals(obj);
  }
  @Override
  public int hashCode() {
    return super.hashCode();
  }
  @Override
  public String toString() {
    return "equals invoked "+count+" times";
  }
}

and

Counter c = new Counter();
List<List<Counter>> list = Arrays.asList(
  new ArrayList<>(Collections.nCopies(10, c)),
  new ArrayList<>(Collections.nCopies(15, c)),
  new ArrayList<>(Collections.nCopies(7, c)),
  new ArrayList<>(Collections.nCopies(10, c))
  );

Comparator<List<?>> cmp = Comparator.comparingInt(List::size);

System.out.println("using IntStream.range(0, list.size()).boxed()\r\n" + 
  "               .min(Comparator.comparing(list::get, cmp))");
int minIndex = 
  IntStream.range(0, list.size()).boxed()
           .min(Comparator.comparing(list::get, cmp)).orElse(-1);
System.out.println("result "+minIndex+", "+c);
c.count = 0;

System.out.println("\nusing list.indexOf(Collections.min(list, cmp))");
minIndex = list.indexOf(Collections.min(list, cmp));
System.out.println("result "+minIndex+", "+c);
c.count = 0;

System.out.println("\nusing list.indexOf(list.stream().min(cmp).get())");
minIndex = list.indexOf(list.stream().min(cmp).get());
System.out.println("result "+minIndex+", "+c);

it will print

using IntStream.range(0, list.size()).boxed()
               .min(Comparator.comparing(list::get, cmp))
result 2, equals invoked 0 times

using list.indexOf(Collections.min(list, cmp))
result 2, equals invoked 14 times

using list.indexOf(list.stream().min(cmp).get())
result 2, equals invoked 14 times

in Java 8, showing that calling equals on any contained element is an unnecessary operation (see the first variant, derived from this answer), but performed multiple times for the other variants. Now imagine what happens if we use larger lists and/or a larger number of lists and have an element type with a rather expensive equality test.

Note that for ArrayList, this has been solved in JDK 11, but there are still list implementations left, like the ones returned by Collections.nCopies or Arrays.asList, which do not short circuit, so it’s generally preferable not to do an entirely obsolete content based linear search operation.

Improve this answer

3 Comments

Nice answer as always. The equals implementation was added only in JDK11 to the ArrayList class. But I don't quite understand the shortcircuiting part. Wouldn't the equals in the AbstractList (or in other words equals of ArrayList pre Java 11) also shortcirucit?
I think I got it. They have a different/special method (equalsArrayList) when the other object is an ArrayList and they will not even do the traversal of the two lists if the sizes are unequal. Am I right?
@user7 exactly, the difference lies in the size check. AbstractList.equals does not check the size; since it doesn’t know the actual implementation logic, determining the size could be an expensive operation, so it doesn’t use it. So all list implementations with a cheap size operation (almost all of them) should insert such a check, as a different size precludes equality.
2

Here's one way to go about it:

int index = listOLists.indexOf(listOLists.stream()
                .min(Comparator.comparingInt(List::size))
                .orElseGet(ArrayList::new));

or if you want to avoid the creation of an ArrayList when the source is empty then you could do:

int index = listOLists.isEmpty() ? -1 : listOLists.indexOf(listOLists.stream()
                  .min(Comparator.comparingInt(List::size)).get());
Improve this answer

4 Comments

When passed an empty list, this will return -1 which is better than the OP's current code which will fail with a NPE
is this solution better than the for loop way in question of performance
@zakzak You need to measure it (Note: Streams have some overhead)
@zakzak it’s likely much worse than the loop equivalent, as this solution (exactly like the accept answer) first searches for the minimum element, but then performs an additional expensive linear search for its index via indexOf which involves comparing all elements of the list (and you would be surprised, how many List implementations do not short-cut when the size differs or when compared with itself). That content comparison is orders of magnitude more expensive than comparing list by their size.
0

An alternative that creates index/size arrays and finds the min by size:

IntStream.range(0, listOLists.size())
         .mapToObj(i -> new int[] { i, listOLists.get(i).size() })
         .min(Comparator.comparingInt(arr -> arr[1]))
         .map(arr -> arr[0])
         .ifPresent(System.out::println);

This will print the index of min-sized list in listOLists

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.