Multithreading calculations

[Sot Nikele]

Hello,

I am writing a programm working with lists and I just want to make it faster.
I am having  a List of List, where each List holds integer numbers.
Let's have List list1 = {1,2,3,4}, list2 = {1,2,3,4), list3 = {1,2,3,4}. Then I make a combination by taking one integer from each list. All 3 list combinations are 4*4*4 = 64 combinations.
The combinations are {1,1,1}, {1,1,2}, {1,1,3} etc. Then I accept or reject the combinations based on some conditions. For instance, return all combinations that sum is over 5.
So {1,1,1}=3 is not accepted, {1,1,2}=4 is not accepted, {1,1,4}=6 is accepted. At the end I get the sum of accepted combinations as an integer.
How can I do these calculations using multithread? I have to add that I don't want to save the combinations in a new List, because there are millions of combinations. Just need to iterate through all combinations very fast.

Thanks in advance.

[Stephan van Hulst]

Welcome to CodeRanch!

You can generate combinations lazily using streams relatively easily, assuming that your list of lists is not too long.

Does your list of lists always have a fixed length (meaning, are the resulting combinations a fixed length) or is the length determined dynamically?

[Sot Nikele]

Stephan van Hulst wrote:Welcome to CodeRanch!

You can generate combinations lazily using streams relatively easily, assuming that your list of lists is not too long.

Does your list of lists always have a fixed length (meaning, are the resulting combinations a fixed length) or is the length determined dynamically?

Thank you for your answer.

Yes, the user desides about its size.

Usually the list has a size of 10-15 and each list has 2 to 4 integers. In my case they are objects, but I have written an example of integers to be more clear and easy. That means that I usually have 10-40 millions of combinations.

[Campbell Ritchie]

Please explain more. What sort of objects do you mean? What does it mean that you are using Integers instead?

[Sot Nikele]

Campbell Ritchie wrote:Please explain more. What sort of objects do you mean? What does it mean that you are using Integers instead?

I showed an example here with integer numbers, just to be easier to understand.

The problem still is that I have to iterate and filter the combinations fast.

[Campbell Ritchie]

That is the Cartesian product of the three sets.

[Piet Souris]

A possibility is to use the Fork-Join framework, where you split your lists until you have one or two lists left. What then to do depends on the task at hand.

[Stephan van Hulst]

import java.util.*;
import java.util.function.*;

import static java.util.Collections.emptyList;
import static java.util.Collections.unmodifiableList;

import static java.util.stream.Collectors.summingLong;

final class Combination<E> {

  private final List<E> elements;

  private Combination(List<E> elements) {
    this.elements = unmodifiableList(elements);
  }

  Combination(Collection<? extends E> elements) {
    this(new ArrayList<>(elements));
  }

  List<E> elements() {
    return elements;
  }

  @Override
  public boolean equals(Object object) {
    return object instanceof Combination<?> other && this.elements.equals(other.elements);
  }

  @Override
  public int hashCode() {
    return elements.hashCode();
  }

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

  Combination<E> prependedWith(E element) {
    var elements = new ArrayList<>(this.elements);
    elements.add(0, element);
    return new Combination<>(elements);
  }

  static <E> Combination<E> emptyCombination() {
    return new Combination<>(emptyList());
  }

  static long sum(Combination<Integer> combination) {
    return combination.elements.stream().collect(summingLong(Integer::longValue));
  }

  static Predicate<Combination<Integer>> hasSumGreaterThan(long value) {
    return combination -> sum(combination) > value;
  }
}

import java.util.*;
import java.util.stream.*;

final class CartesianProduct<E> {

  private final List<List<E>> collections;

  private CartesianProduct(Stream<List<E>> collections) {
    this.collections = collections.toList();
  }

  CartesianProduct(Collection<? extends Collection<? extends E>> collections) {
    this(collections.stream().map(ArrayList<E>::new));
  }

  Stream<Combination<E>> streamCombinations(boolean parallel) {
    if (collections.isEmpty())
      return Stream.of(Combination.emptyCombination());

    var subproduct = new CartesianProduct<>(collections.stream().skip(1));

    var stream = collections.get(0).stream()
      .flatMap(element -> subproduct.streamCombinations(parallel)
        .map(combination -> combination.prependedWith(element)));

    if (parallel) {
      stream = stream.parallel();
    }

    return stream;
  }

  public static void main(String... args) {
    var product = new CartesianProduct<>(List.of(
      List.of(1, 2, 3, 4),
      List.of(1, 2, 3, 4),
      List.of(1, 2, 3, 4)
    ));

    product.streamCombinations(true)
      .filter(Combination.hasSumGreaterThan(5))
      .forEach(System.out::println);
  }
}

[Piet Souris]

No multithreading, no streams, no generics, but pretty fast anyway (I got up to a maximum of 12 lists of size 4)

public class CartProd {
   
    public static void main(String... args) {
        
        var listlist = IntStream.rangeClosed(1, 12)
            .mapToObj(i -> List.of(1, 2, 3, 4))
            .toList()
        ;
        Predicate<List<Integer>> pred = list -> list.stream().mapToInt(i -> i).sum() > 30;
        long start = System.currentTimeMillis();
        var result = test(listlist, pred);
        long end = System.currentTimeMillis();
        System.out.format("#%d , took: %.3f seconds%n", result.size(), (end - start) / 1000.);
    }
    
     public static List<List<Integer>> test(List<List<Integer>> source, Predicate<List<Integer>> pred) {
        var listlist = new ArrayList<List<Integer>>();
        testHelper(listlist, new ArrayList<>(), 0, source, pred);
        return listlist;
    }
    
    private static void testHelper(List<List<Integer>> result, List<Integer> currentList, int index, List<List<Integer>> source, Predicate<List<Integer>> pred) {
        if (index == source.size()) {
            if (pred.test(currentList)) result.add(new ArrayList<>(currentList));
            return;
        }
        var list = source.get(index);
        for (int i = 0; i < list.size(); i++) {
            currentList.add(list.get(i));
            testHelper(result, currentList, index + 1, source, pred);
            currentList.remove(currentList.size() - 1);
        }
    }
}

[Piet Souris]

By splitting the first list into its seperate elements and using Callables, I got 14 lists of 4 elements processed in around 5 to 10 seconds on my PC.

[Campbell Ritchie]

Unfortunately that sort of program is going to run in exponential time complexity whatever you do with it.

[Piet Souris]

OP mentioned 10 to 15 lists each with 2 to 4 elements, and so it is very doable. There is no mentioning of what the objects are and what tests should be done, so there might be other optimizations as well.

Anyway, always nice to get the opportunity to practise some stuff that you are not doing very often.

[Tim Moores]

Piet Souris wrote:No multithreading

For this kind of problem, and given the small data volume involved, I doubt that using multithreading would provide a noticeable speedup anyway.

[Piet Souris]

Well, 14 lists of 4 elements each make 4^14 or > 250M combinations to investigate, so any bit of speed up is welcome, if you got nothing better than brute force.

[Stephan van Hulst]

Tim Moores wrote:For this kind of problem, and given the small data volume involved, I doubt that using multithreading would provide a noticeable speedup anyway.

I don't know. Combinations and permutations often blow up in factorial time, so a small increase in the number of input lists may cause an explosion in execution time. The generation of combinations can easily be parallelized (as I've done in my code example), so theoretically you can make the process 8 times as fast if you have 8 processor cores.

[Mike Simmons]

Sot Nikele wrote: I have to add that I don't want to save the combinations in a new List, because there are millions of combinations. Just need to iterate through all combinations very fast.

I understand this concern.  In a single-threaded application, you could perhaps be using a single array to store the current combination, and to change combinations, you just change one element of the array.  That's fast and efficient.  However, it doesn't work well for multithreading - you can't share mutable data among different threads, because when they try to access and modify the data simultaneously, they will interfere with each other.  Generally, each thread will need a separate copy of data to operate on.

You can, however, use a hybrid approach.  You can use parallel threads to handle some of the element lists, and single threads to handle the remaining elements.  For the parallel threads, you need to create a separate List for each possible combination of elements, so that each combination can be handled by separate threads. But for the remaining lists, you can use an int[] array to quickly build each possible combination in a sequential fashion.

E.g., the following code takes five lists, and uses parallel threads to handle the first two lists of elements, building a Stream<List<Integer>> that will include all combinations of the first two lists.  Each combination is called a prefix.  Then each of these is passed to single-threaded code that, starting with a given prefix, will then go through all combinations of the remaining three lists, and call handleCombo() on that combination.  What you do in handleCombination() is up to you - this code just prints each one and counts them.

public class StreamCombos {
  private final List<List<Integer>> prefixChoiceLists; // handled in parallel
  private final List<List<Integer>> suffixChoiceLists; // handled in single threads

  public StreamCombos(List<List<Integer>> choiceLists, int numParallelChoices) {
    this.prefixChoiceLists = choiceLists.subList(0, numParallelChoices);
    this.suffixChoiceLists = choiceLists.subList(numParallelChoices, choiceLists.size());
  }

  public void processAll() {
    parallelCombos(List.of(), 0).forEach(this::singleThreadCombos);
  }

  private Stream<List<Integer>> parallelCombos(List<Integer> prefix,  int parallelChoiceIdx) {
    var stream = prefixChoiceLists.get(parallelChoiceIdx).parallelStream();
    return parallelChoiceIdx + 1 == prefixChoiceLists.size()
      ? stream.map(n -> concat(prefix, n))
      : stream.flatMap(n -> parallelCombos(concat(prefix, n), parallelChoiceIdx + 1));
  }

  private static List<Integer> concat(List<Integer> list, Integer n) {
    var newList = new ArrayList<>(list);
    newList.add(n);
    return newList;
  }

  private void singleThreadCombos(List<Integer> prefix) {
    int[] array = new int[prefix.size() + suffixChoiceLists.size()];
    int arrIdx = 0;
    for (var n : prefix) array[arrIdx++] = n;
    singleThreadCombos(array, prefix.size(), 0);
  }

  private void singleThreadCombos(int[] array, int arrIdx, int suffixChoiceIdx) {
    if (suffixChoiceIdx < suffixChoiceLists.size()) {
      for (var n : suffixChoiceLists.get(suffixChoiceIdx)) {
        array[arrIdx] = n;
        singleThreadCombos(array, arrIdx + 1, suffixChoiceIdx + 1);
      }
    } else {
      handleCombo(array);
    }
  }


  private final AtomicInteger count = new AtomicInteger();
  private void handleCombo(int[] array) {
    System.out.println(Arrays.toString(array) + ": " + count.incrementAndGet());
  }

  public static void main(String[] args) {
    var lists = List.of(
      List.of(1,2,3),
      List.of(1,2),
      List.of(1,2,3),
      List.of(1,2,3,4),
      List.of(1,2,3)
    );
    new StreamCombos(lists, 2).processAll();
  }
}

[Sot Nikele]

First of all, I would like to thank all of you answering my question.

I am posting my code that I was using till now, to create all combinations of the lists. I used the library Apache Commons-Math3:

	import java.util.ArrayList;
	import java.util.Iterator;


	public class Combination implements Iterator<ArrayList<Integer>> {

	    final ArrayList<ArrayList<Integer>> elements;
	    final int[] indices;

	    public Combination(ArrayList<ArrayList<Integer>> elements) {
	        this.elements = elements;
	        this.indices = new int[elements.size()];
	    }

	    @Override
	    public boolean hasNext() {
	        // has first index not yet reached max position?
	        return indices[0] < elements.get(0).size();
	    }

	    @Override
	    public ArrayList<Integer> next() {
	        // get next
	    	ArrayList<Integer> result = new ArrayList<Integer>(indices.length);
	        for (int i = 0; i < indices.length; i++) {
	            result.add(elements.get(i).get(indices[i]));
	        }
	        // increase indices
	        for (int i = indices.length - 1; i >= 0; i--) {
	            indices[i]++;
	            if (indices[i] >= elements.get(i).size() && i > 0) {
	                indices[i] %= elements.get(i).size();
	            } else {
	                break;
	            }
	        }
	        return result;
	    }
	
	}

import java.util.ArrayList;
import java.util.Iterator;
import org.apache.commons.math3.util.CombinatoricsUtils;

public class CombinationsForJava {

	public static void main(String[] args) {
		
		ArrayList<ArrayList<Integer>> myLists = new ArrayList<ArrayList<Integer>>();
		
		ArrayList<Integer> list = new ArrayList<>();
		list.add(1);
		list.add(2);
		list.add(3);
		
		int sizeOfList = 17;

		for(int i=0; i<sizeOfList; i++)
			myLists.add(list);
		
		Iterator<int[]> iterator = CombinatoricsUtils.combinationsIterator(myLists.size(), myLists.size());
		
		int sum = 0;

               Long start = System.currentTimeMillis();
		
		while (iterator.hasNext()) {
			
			   int[] combination = iterator.next();

			    ArrayList<ArrayList<Integer>> helper = new ArrayList<ArrayList<Integer>>();
			    
				for (int i = 0; i < combination.length; i++)
					helper.add(myLists.get(combination[i]));
				
				Combination combinations = new Combination(helper);

				while (combinations.hasNext()) {
					 
					//System.out.println(combinations.next().toString());
					
					combinations.next();
					
					sum++;
					
				}

			
		}
		
		System.out.println("Sum of combs " + sum + " in " + (System.currentTimeMillis()-start) + " ms");

	}

}

All 3 pieces of code are faster than mine, but I needed something fast without making use of ram memory. First two pieces of code posted, need about 1gb of ram on my machine.
Last piece of code by  @Mike Simmons is the fastest and it utilizes no memory. It is really impressive.

[Piet Souris]

In your opening post you mentioned an example, where you investigated combinations of a few lists where a combination had to meet a certain criterium. Now, if all that you want to know is how many combinations pass that test, then no memory is required. However, if you want to save these combinations, then that will require a lot of memory.

In that last case, an idea to save a lot of space is not to store a succesful combination, but an integer that denotes that combination. For instance, if we have the lists {(1, 2), (a, b, c)} then (1, a) has index 0, (1, b) has index 1, (1, c) 2, and (2, c) has index 5.

In my current code, 17 lists of (1, 2, 3), with the predicate that the sum of the elements of a combination must be > 40, gives me 3,3M combinations in about 3 seconds, and the list of indices takes up about 15MB memory. (my hardware is an 8GB pc with an I5 7500 processor, on win 10).

[Sot Nikele]

Piet Souris wrote:
In that last case, an idea to save a lot of space is not to store a succesful combination, but an integer that denotes that combination. For instance, if we have the lists {(1, 2), (a, b, c)} then (1, a) has index 0, (1, b) has index 1, (1, c) 2, and (2, c) has index 5.

Very interesting. And how will I be able to retrieve the combination back?

[Piet Souris]

I have a class that does all of this work, with a Constructor that takes a List<List<E>> as parameter. Then I have a member, a List<Integer> (an int[] would also do), that does the following:

say, the Lists have sizes 2, 3, 4, 5. Then I create a List with elements 60 (= 3 x 4 x 5), 20 (= 4 x 5) and 5.

Now, if I have, say, index 117, then it goes as follows:

117 / 60 = 1, remainder 57
57 / 20 = 2, remainder 17
17 /  5 = 3, remainder  2.

And so the corresponding result-list = list(0).get(1), list(1).get(2), list(2).get(3), list(3).get(2)

In fact, this is the exact same procedure as transforming a decimal number into a number from some other N-ary system. This is the routine I use:

public List<E> getList(int index) {
    var result = new ArrayList<E>();
    for (int i = 0; i < borders.size(); i++) {   // borders is the list I was talking about, with elements 60, 20, 5
        result.add(source.get(i).get(index / borders.get(i)));
        index %= borders.get(i);
    }
    result.add(source.get(source.size() - 1).get(index));
    return result;
}

[Piet Souris]

Final remark:

having this method 'getList', a simple routine to get a List of indices of all successful combinations is:

public List<Integer> process() {
    var totalNumberOfCombinations = source.stream().reduce(1, (number, list) -> number * list.size(), Integer::sum);
    var result = IntStream.range(0, totalNumberOfCombinations) 
        .parallel()
        .filter(i -> predicate.test(getList(i)))
        .boxed()
        .toList()
    ;
    return result;
}

However, this is about 4 times as slow as what I have.

[Sot Nikele]

I would like to thank all of you for your posts, they were really helpful.
A last question : I am trying to implement Mike Simmons's code as a class extending SwingWorker so that I can update a JProgressbar, showing the whole procedure and a JLabel showing the combination that pass the predicate, but I am getting a mess on my screen. I have added in the class a progressbar and a label and then I try to access them.
What should I put in the doInBackground() and process() functions?

[Stephan van Hulst]

The doInBackground() method is where you do all your background processing (the stuff that shouldn't block the user interface). You may not perform any operations on the user interface here.

To update the user interface while you're performing background processing, you may call publish() and setProgress() from inside doInBackground().

Calling publish() will cause Swing to call the process() method on the Event Dispatch Thread. So you can override the process() method to do any custom UI updates using information that you published from the background thread.

If you only want to update a progress bar, you don't need publish() and process(). You can just call setProgress() from your background thread, and use a listener that calls getProgress() to update the progress bar.

[ran kum]

test

[ran kum]

Done

[Carey Brown]

Ran Kum, please UseCodeTags (<-- read this link). Go back and edit your last post and add code tags.