programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Tim Cooke
• Campbell Ritchie
• Ron McLeod
• Junilu Lacar
• Liutauras Vilda
Sheriffs:
• Paul Clapham
• Jeanne Boyarsky
• Henry Wong
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Stephan van Hulst
• Piet Souris
• Carey Brown
Bartenders:
• Jesse Duncan
• Frits Walraven
• Mikalai Zaikin

Greenhorn
Posts: 6
• Number of slices to send:
Optional 'thank-you' note:
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.

Saloon Keeper
Posts: 14010
315
• Number of slices to send:
Optional 'thank-you' note:
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
Greenhorn
Posts: 6
• Number of slices to send:
Optional 'thank-you' note:

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?

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.

Marshal
Posts: 75874
361
• Number of slices to send:
Optional 'thank-you' note:
Please explain more. What sort of objects do you mean? What does it mean that you are using Integers instead?

Sot Nikele
Greenhorn
Posts: 6
• Number of slices to send:
Optional 'thank-you' note:

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
Marshal
Posts: 75874
361
• Number of slices to send:
Optional 'thank-you' note:
That is the Cartesian product of the three sets.

Saloon Keeper
Posts: 4994
186
• Number of slices to send:
Optional 'thank-you' note:
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
Saloon Keeper
Posts: 14010
315
• 1
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris
Saloon Keeper
Posts: 4994
186
• 1
• Number of slices to send:
Optional 'thank-you' note:
No multithreading, no streams, no generics, but pretty fast anyway (I got up to a maximum of 12 lists of size 4)

Piet Souris
Saloon Keeper
Posts: 4994
186
• Number of slices to send:
Optional 'thank-you' note:
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
Marshal
Posts: 75874
361
• Number of slices to send:
Optional 'thank-you' note:
Unfortunately that sort of program is going to run in exponential time complexity whatever you do with it.

Piet Souris
Saloon Keeper
Posts: 4994
186
• Number of slices to send:
Optional 'thank-you' note:
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.

Saloon Keeper
Posts: 7355
170
• Number of slices to send:
Optional 'thank-you' note:

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
Saloon Keeper
Posts: 4994
186
• Number of slices to send:
Optional 'thank-you' note:
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
Saloon Keeper
Posts: 14010
315
• Number of slices to send:
Optional 'thank-you' note:

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.

Master Rancher
Posts: 4225
57
• 1
• Number of slices to send:
Optional 'thank-you' note:

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.

Sot Nikele
Greenhorn
Posts: 6
• Number of slices to send:
Optional 'thank-you' note:
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:

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
Saloon Keeper
Posts: 4994
186
• 1
• Number of slices to send:
Optional 'thank-you' note:
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
Greenhorn
Posts: 6
• Number of slices to send:
Optional 'thank-you' note:

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
Saloon Keeper
Posts: 4994
186
• 1
• Number of slices to send:
Optional 'thank-you' note:
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:

Piet Souris
Saloon Keeper
Posts: 4994
186
• 1
• Number of slices to send:
Optional 'thank-you' note:
Final remark:

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

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

Sot Nikele
Greenhorn
Posts: 6
• Number of slices to send:
Optional 'thank-you' note:
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
Saloon Keeper
Posts: 14010
315
• Number of slices to send:
Optional 'thank-you' note:
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.

Greenhorn
Posts: 2
• Number of slices to send:
Optional 'thank-you' note:
test

ran kum
Greenhorn
Posts: 2
• Number of slices to send:
Optional 'thank-you' note:
Done

Saloon Keeper
Posts: 9348
78
• Number of slices to send:
Optional 'thank-you' note:
Ran Kum, please UseCodeTags (<-- read this link). Go back and edit your last post and add code tags.

 With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.