Lazy sorted() in Java8 Streams, need for resorting at each iteration

Question

I'm looking for a way to emulate the following behavior with Java 8 streams. Given a stream of years,sort them so the top 10 values are outputed, such that after outputing a year, that is decreased and the iteration restarts resorting again:

If I input years 2005, 2020, 2000, 1967 and 2018 I expect the following results for a limit of 10:

2020
2019
2018 2018  
2017 2017
2016 2016 2016
2015 ...

The test I am using is:

public class LazyTest {

    public static void main(String[] args) {
        Stream.of(2005,2020,2000,1967,2018)
              .map(YearWrapper::new)
              .sorted()
              .limit(10)
              .peek(year -> year.decreaseYear())
              .forEach(System.out::println);
    }

    public static class YearWrapper implements Comparable<YearWrapper>{
        private int currentYear;

        public YearWrapper(int year){
            this.currentYear=year;
        }
        public void decreaseYear(){
            currentYear--;
        }
        @Override
        public int compareTo(YearWrapper yearsToCompare) {
            return Integer.compare(yearsToCompare.currentYear, this.currentYear);
        }

        @Override
        public String toString(){
            return String.valueOf(currentYear);
        }
    }
}

But it seems sorted() is not lazy at all. The whole sorting is done once at the beggining so the order is calculated before any further operation and therefore, the 5 values of the example are passed ordered one by one, so decrease() have no real effect on the iteration.

Is there any way to make sorted() lazy and being applied again to the remaining elements before streaming the next one?

Any other close approach would be much appreciated!!

I don't get the output. Why is 2018 printed twice and 2016 three times? — a better oliver
– a better oliver, Commented Mar 23, 2015 at 8:00
because I expected sorted to operate on after any filtered element has changed its state, so 2020 is decreased and prrinted alone until it's the turn of 2018 — Whimusical
– Whimusical, Commented Mar 23, 2015 at 8:37
So you want to decrease a value until it's equal to the next value, then you decrease both values until they are equal to the third and so on? And during each iteration you print out the values that are being decreased? Does the limit affect the source or the target values? — a better oliver
– a better oliver, Commented Mar 23, 2015 at 10:03
Misha's answer is what I am behind, just that I would like to not readding the object but changing it's state so the queue resorts in behind — Whimusical
– Whimusical, Commented Mar 23, 2015 at 10:59

Holger · Accepted Answer · 2015-03-23 12:04:43Z

5

The documentation of Stream.sorted() says:

This is a stateful intermediate operation.

which is in turn described as

Stateful operations may need to process the entire input before producing a result. For example, one cannot produce any results from sorting a stream until one has seen all elements of the stream.

This documents the non-lazy nature of sorting, however, this has nothing to do with your problem. Even if sorting was lazy, it didn’t change the fundamental principle of streams that each item is streamed to the terminal operation at most once.

You said that you expected the sorting “to be lazy” but what you actually expected is the sorting to happen again for each item after consumption which would imply that sorting a stream of n elements means actually sorting n items n times which no-one else would expect, especially as peek is not meant to have a side effect that affects the ongoing operation.

answered Mar 23, 2015 at 12:04

Holger

301k43 gold badges481 silver badges827 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Holger Over a year ago

You already have a working solution but I wanted to explain the background of your failed first attempt…

Misha · Accepted Answer · 2015-03-23 01:47:53Z

4

Do I understand you correctly that you want to take the largest number from the list, decrement it, put it back into the list, repeat 10 times?

If so, then this is a job for PriorityQueue:

PriorityQueue<Integer> queue = Stream.of(2005,2020,2000,1967,2018)
        .collect(toCollection(() -> new PriorityQueue(reverseOrder())));

Stream.generate(() -> {
    Integer year = queue.poll();
    queue.add(year - 1);
    return year;
}).limit(10).forEach(System.out::println);

answered Mar 23, 2015 at 1:47

Misha

28.3k7 gold badges66 silver badges83 bronze badges

3 Comments

Whimusical Over a year ago

Awesome answer. It pointed me in the perfect solution. I tried with peek() instead of poll and changing the state of the object, and it works more likely I was expecting, but now it never returns duplicates. I mean, if at some time max values are 2020 decreased as 2018 and the original 2018, it should return twice that value as in 2020,2019,2018,2018,2017,2017,2016...

Whimusical Over a year ago

Ok I see, when peeking, the queue does not resort, so this behavior is expected and optimized for poll and re-add

Misha Over a year ago

@user1352530 That is correct. PriorityQueue has no way of knowing that you messed with the object's state. And even if it could detect the change, the way it would "resort" the queue is by removing and re-adding the object. It doesn't really sort the list every time. Rather it stores it in a very clever way ( en.wikipedia.org/wiki/Heap_%28data_structure%29 ) that allows for efficient insertion and priority retrieval.

Collectives™ on Stack Overflow

Lazy sorted() in Java8 Streams, need for resorting at each iteration

2 Answers 2

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related