CODEWITHSUNDEEP
javaarraysalgorithm
user3083022
user3083022

Reputation: 569

Evenly distribute lists into sublists in Java

I want to evenly distribute a list into a given number of sublists. For example, I have a list with elements 1 to 10 and I want 3 lists. These should look like:

SL1 -> {1, 2, 3, 4}
SL2 -> {5, 6, 7}
SL3 -> {8, 9, 10}

Important: What each list contains is not relevant, i.e. SL1 could have {1, 5, 7, 10}. The most important thing is that there are 2 lists with size 3 and 1 list with size 4.

I have tried several things, including the Iterables.partition but that won't help.

The only thing I've come up with that works is:

public Iterable<List<Integer>> distributeEvenlyQueryListIntoLists(final LinkedList<Integer> bigList, final Integer numberOfSublists) {
    List<List<Integer>> result = new ArrayList<>();

    // Creates as many lists as needed
    for (int i = 0; i < numberOfSublists; i++) {
        result.add(new ArrayList<>());
    }

    while (bigList.iterator().hasNext()) {
        for (int i = 0; i < numberOfSublists; i++) {
            if (!bigList.iterator().hasNext()) {
                break;
            }
            result.get(i).add(bigList.poll());
        }
    }
    return result;
}

The passed bigList does not have to be a LinkedList, it can be any Iterable.

I especially hate the first loop where I create the sublists.

Thanks!

Upvotes: 4

Views: 2921

Answers (4)

Manish
Manish

Reputation: 1

If you want to preserve the order while also distributing the tasks evenly then refer the following code:

public static List<List<Long>> splitList(List<Long> inputList, int parts){
    int len = inputList.size();
    int elementSize = len/parts;
    int largerParts = len%parts; //len%parts is number of sublists that will have one element more than the other sublists
    int index =0;
    List<List<Long>> result = new ArrayList<>();
    for(int sublist=0; sublist<parts; sublist++){
        if (sublist<largerParts){ //split larger portions first
            result.add(inputList.subList(index, index+=elementSize+1));
        }
        else{ //rest portions should have len/parts elements
            result.add(inputList.subList(index, index+=elementSize));
        }
    }
    return result;
}

(remember in java assignbment operator '=' returns the assigned value, making assignments like 'sum=c=a+b' possible. I used this to get rid of two extra lines that would be used to update the index value)

[P.S: I implemented the algorithm for Long type. just change the function to your desired datatype or generics before using it 😉]

Upvotes: 0

Ayush Walekar
Ayush Walekar

Reputation: 66

You can use org.apache.commons.collections4.ListUtils to create equal size sublists.

List<String> bigList = ...
int batchSize = 1000;
List<List<String>> smallerLists = ListUtils.partition(bigList, batchSize);

Upvotes: 0

Paul Brinkley
Paul Brinkley

Reputation: 6353

If you hate creating sublists, that implies you're looking for a fast solution. If you have the original List, and you plan on not altering the original List, consider List.subList().

int subSize = bigList.length() / numSubs;
int numBigSubs = 0; // # of subs that need to be one bigger
if (bigList.length() % numSubs > 0) {
     subSize++;
     numBigSubs = bigList.length() % numSubs;
}
int from = 0;
int to  = subSize;
List<List<Integer>> subList = new ArrayList<List<Integer>>(numSubs);
for (int i = 0; i < numSubs; i++) {
    List<Integer> newSub = bigList.subList(from, to);
    subList.add (newSub);
    from = to;
    to += subSize;
    if (i >= numBigSubs && numBigSubs > 0) to--; 
}

Note: I wrote this without testing - if it fails, I apologize, and hope someone will edit it to work.

Again, the big upside to this is that it should be wicked fast - all the sublists are simply views into the larger one. The downside is that if you change the list, all bets are off.

Upvotes: 2

user4668606
user4668606

Reputation:

Just distribute them in a round-robin pattern:

public <T> List<List<T>> partition(Iterable<T> iterable, int partitions){
    List<List<T>> result = new ArrayList<>(partitions);
    for(int i = 0; i < partitions; i++)
        result.add(new ArrayList<>());

    Iterator<T> iterator = iterable.iterator()
    for(int i = 0; iterator.hasNext(); i++)
        result.get(i % partitions).add(iterator.next());

    return result;
}

A sample run with this code:

List<String> l = Stream.iterate(0, i->i + 1).limit(25).map(i->Integer.toString(i)).collect(Collectors.toList());
System.out.println(partition(l, 4).toString());

Produces

[[0, 4, 8, 12, 16, 20, 24], [1, 5, 9, 13, 17, 21], [2, 6, 10, 14, 18, 22], [3, 7, 11, 15, 19, 23]]

The basic idea is to add a single element to each list in the result set roundwise. This way it's guaranteed that the difference in the number of elements between two lists never exceeds 1.

As an alternative you could use guavas implementation of Iterables.partition, which takes a slightly different approach.

Upvotes: 6

Related Questions