Sum up List to a limit with streams

Question

How to get the records, which count sum should be in limit. In below example there is Records Object contains recordId and count, i wanted to fetch the records data based on the total sum of count should be less than or equal to my limit condition.

public class Records {
    private int recordID;
    private int count;

    public Records(int recordID, int count) {
        this.recordID = recordID;
        this.count = count;
    }

    public int getRecordID() {
        return recordID;
    }

    public void setRecordID(int recordID) {
        this.recordID = recordID;
    }

    public int getCount() {
        return count;
    }

    public void setCount(int count) {
        this.count = count;
    }
}


public static void main(String[] args) {
    
    final List<Records> recordList = new ArrayList<>();
    
    recordList.add(new Records(100, 10));
    recordList.add(new Records(501, 20));
    recordList.add(new Records(302, 5));
    recordList.add(new Records(405, 2));
    recordList.add(new Records(918, 8));
    int limit = 35;
}

Expected Result

recordList should have records objects : [100,10], [500,20], [302,5] records

I don’t think a stream operation is well suited for this. An old-fashioned `while` loop will do fine. — Ole V.V., Oct 21 '20 at 19:31
functions in functional programming (which is used by streams) are supposed to be stateless. Your task requires you to remember a state. Just use a regular loop, there is no benefit of streams here. — f1sh, Oct 21 '20 at 19:32
@f1sh In proper functional programming this would be a prefix scan operation, followed by a zip and a “take while”. The issue is that streams are read-once abstractions. *That’s* the issue here, not functional programming. That said, it can still be done as a reduction, or a collector. — Konrad Rudolph, Oct 21 '20 at 19:47
I learned a lot from this discussion! The following post may help as well (I don't think it is a duplicate, as it is more general) - https://stackoverflow.com/questions/33058670/in-which-cases-stream-operations-should-be-stateful — Michael Easter, Oct 21 '20 at 20:32

score 1 · Answer 1 · answered Oct 21 '20 at 19:39

The problems of solving this with Stream API is that you have to keep some information outside of the context of processing and read/update (depend) on it at the same time. These tasks are not suitable for Stream API.

Use a for-loop instead which is suitable and great for this:

int index = 0;                              // highest index possible
int sum = 0;                                // sum as a temporary variable
for (int i=0; i<recordList.size(); i++) {   // for each Record
    sum += recordList.get(i).getCount();    // ... add the 'count' to the 'sum'
    if (sum <= limit) {                     // ... until the sum is below the limit
        index = i;                          // ... move the pivot
    } else break;                           // ... or else stop processing
}

// here you need to get the list from 0 to index+1 
// as long as the 2nd parameter of subList(int, int) is exlcusive
List<Record> filteredRecords = recordList.subList(0, index + 1);

score 0 · Answer 2 · answered Oct 21 '20 at 20:32

This is the only thing I could come up with but it's not as efficient as a regular loop because it runs for each list entry it has. That also causes it to add other values further down. For example if limit was 46, third entry where count is 5 would be skipped but the next entry with count 2 would be still added. Don't know if this is desired behavior for you

    AtomicInteger count = new AtomicInteger();

    recordList = recordList.stream().filter(r -> {
        if(count.get() + r.count <= limit){
            count.addAndGet(r.count);
            return true;
        }
        return false;
    }).collect(Collectors.toList());

You might find this interesting :) https://stackoverflow.com/questions/50977793/is-use-of-atomicinteger-for-indexing-in-stream-a-legit-way — Nikolas Charalambidis, Oct 21 '20 at 20:45

score 0 · Answer 3 · answered Oct 21 '20 at 21:52

Adding the following toString to your class for printing you can do it as follows:

public String toString() {
    return String.format("[%s, %s]", recordID, count);
}

Allocate a List to store the results
initialize the sum
iterate thru the list, summing the count until the threshhold is reached.

List<Records> results = new ArrayList<>();
int sum = 0;
for (Records rec : recordList) {
     // sum the counts
     sum += rec.getCount();
     if (sum > limit) {
        // stop when limit exceeded
        break;
     }
     results.add(rec);
}
        
results.forEach(System.out::println);

Prints

[100, 10]
[501, 20]
[302, 5]

Shekhar Khairnar · Answer 4 · 2020-10-22T05:38:51.740

with java 8 you can do something like:

public static void main(String[] args) {
        int limit = 35;
        List<Records> recordList = new ArrayList<>();
        recordList.add(new Records(100, 10));
        recordList.add(new Records(501, 20));
        recordList.add(new Records(302, 5));
        recordList.add(new Records(405, 2));
        recordList.add(new Records(918, 8));

        List<Records> limitedResult = recordList.stream().filter(new Predicate<Records>() {
            int sum = 0;
            @Override
            public boolean test(Records records) {
                sum=sum+records.getCount();
                return sum <= limit;
            }
        }).collect(Collectors.toList());
        //do what do you want with limitedResult
        System.out.println(limitedResult);
    }

Edit:

Or you can make function which return Predicate which can be reuse as:

    //Reusable predicate
    public static Predicate<Records> limitRecordPredicate(int limit){
        return new Predicate<Records>() {
            int sum = 0;
            @Override
            public boolean test (Records records){
                sum = sum + records.getCount();
                return sum <= limit;
            }
        };
    }

and then used it like:

List<Records> limitedResult = recordList.stream().filter(limitRecordPredicate(limit)).collect(Collectors.toList());
        //do what do you want with limitedResult
        System.out.println(limitedResult);

Output:

[Records[recordID=100, count=10], Records[recordID=501, count=20], Records[recordID=302, count=5]]

This isn’t guaranteed to work since predicates etc. are, by contract, stateless. Streams might be consumed out of order etc. Only collectors are allowed to be stateful. — Konrad Rudolph, Oct 22 '20 at 09:57

Sum up List to a limit with streams

Expected Result

4 Answers4