How to sort an IntStream in reverse order

22.3k views Asked by At

I'm reading in numbers from a .txt file using BufferedReader. I want to reverse the order of elements in this steam so that when they are collected they will be arranged from the highest to the lowest. I don't want to sort after the array has been built because I have no idea how many elements might be in it, I only need the highest N elements.

in = new BufferedReader(reader);
                int[] arr = in.lines()
                        .mapToInt(Integer::parseInt)
                        .sorted()
                        .limit((long) N)
                        .toArray();
4

There are 4 answers

2
rgettman On

Because the reverse order is not the natural order, sorted() can't be used to sort in reverse order. If you avoid the IntStream, using a Stream<Integer> instead, then you can use a Collections.reverseOrder() to sort the stream in a reverse to the natural order. Then you can call mapToInt and convert to int[] at the end.

int[] arr = in.lines()
            .map(Integer::valueOf)  // Extract Integer, not int
            .sorted(Collections.reverseOrder())  // On Stream<Integer>
            .limit(N)
            .mapToInt(i -> i)       // map Integer to int
            .toArray();
0
Holger On

It’s hard to say whether .sorted().limit((long) N).toArray() will get optimized in some cases (it’s implementation dependent but given Oracle’s current implementation, I wouldn’t expect it), but in this special case, the source stream is a stream of unknown size which makes optimizations even less likely.

If you want to be on the safe side, you may adapt this solution for getting the n maximum numbers of a stream efficiently. All you have to do is to reverse the order:

public static IntStream maxValuesDescending(IntStream source, int limit) {
    TreeMap<Integer,Integer> m=new TreeMap<>(Comparator.reverseOrder());
    source.forEachOrdered(new IntConsumer() {
        int size, min=Integer.MIN_VALUE;
        public void accept(int value) {
            if(value<min) return;
            m.merge(value, 1, Integer::sum);
            if(size<limit) size++;
            else m.compute(min=m.lastKey(), (k,count)->count==1? null: count-1);
        }
    });
    if(m.size()==limit)// no duplicates
        return m.keySet().stream().mapToInt(Integer::valueOf);
    return m.entrySet().stream().flatMapToInt(e->{
        int value = e.getKey(), count = e.getValue();
        return count==1? IntStream.of(value): IntStream.range(0, count).map(i->value);
    });
}

Then you can use it like

int[] arr = maxValuesDescending(in.lines().mapToInt(Integer::parseInt), N).toArray();

But you are not required to create an array as you can use arbitrary IntStream operations on the result. This solution will hold at most N values, even less if there are duplicates as it only holds distinct values and their count.

4
normanrz On

Try negating the values before sorting and negating (back to normal) after sorting:

in = new BufferedReader(reader);
int[] arr = in.lines()
              .mapToInt(Integer::parseInt)
              .map(i -> -i).sorted().map(i -> -i)
              .limit((long) N)
              .toArray();
0
Mr.Q On

when using Instream, you are actually dealing with primitive, and your hands are tight (you are limited to natural ordering and you can't define custom comparator. You have two solutions:

  • stick with the primitive stream and come up with hacks like the one proposed by @normanrz

  • or you can convert to Integer (box) and use variety of solution like the one bellow (but be advised this boxing and unboxing might cause performance problems).

    int[] sortedArray = IntStream.of(costs).boxed()
                                  .sorted(Collections.reverseOrder())
                                  .mapToInt(value -> value.intValue()).toArray();