How to sort an IntStream in reverse order

Question

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();

If you know you won't have any `Integer.MIN_VALUE` values, you can add a step to map `i -> (-i)`. (The `Integer.MIN_VALUE` qualification is important, since `Integer.MIN_VALUE == (- Integer.MIN_VALUE)`). — yshavit, Jun 09 '15 at 18:56
Also, do you know if the sort-limit combo is optimized? Because if not, there's a good chance that `sorted()` is anyway going to store them all in memory, in which case you may as well just get that array and read the N greatest elements. — yshavit, Jun 09 '15 at 19:00
@yshavit I think you're right about the sort-limit combo, it has to store it in some intermediate container — Aurumae, Jun 09 '15 at 19:13
It definitely has to store it in _some_ container. The question is, is the sort step smart enough to know that there's a limit step right after it? If so, the container could be only N-large, with each new element either getting dropped or pushing out a previously-existing element. If the stream is actually that smart, then doing something clever (as you're asking to do) could definitely be worth it. If not, then you're not really saving much. — yshavit, Jun 09 '15 at 19:17

score 25 · Answer 1 · answered Jan 29 '16 at 16:38

25

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();

answered Jan 29 '16 at 16:38

normanrz

371
3
4

5

Cool trick, though you will have problems if the input contains `Integer.MIN_VALUE`. – Tagir Valeev Jan 29 '16 at 16:48
4

@TagirValeev You can then just switch to `.map(i->~i)` instead of `.map(i->-i)`. – Olivier Grégoire Dec 28 '16 at 13:10
@OlivierGrégoire, yup, I know. I used this trick in [my library](https://github.com/amaembo/streamex/blob/3824b54b798e2af8751088bdfd2205e1782644df/src/main/java/one/util/streamex/IntStreamEx.java#L431) almost a year ago. – Tagir Valeev Dec 29 '16 at 04:42
it increases execution time. – Ulphat Jun 20 '23 at 13:33

score 14 · Answer 2 · answered Jun 09 '15 at 19:12

14

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();

answered Jun 09 '15 at 19:12

rgettman

176,041
30
275
357

2

I think `i -> i` could be `Integer::intValue`, right? – yshavit Jun 09 '15 at 19:14
1

@yshavit Yes, `Integer::intValue` can replace `i -> i` there. – rgettman Jun 09 '15 at 19:15

score 4 · Answer 3 · answered Apr 24 '19 at 10:21

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();

score 0 · Answer 4 · edited May 23 '17 at 12:08

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.

How to sort an IntStream in reverse order

4 Answers4

Linked