Multithreading while loop

Question

So guys, I have a while loop something like that

int counter=0;
ArrayList<String> array = new ArrayList<String>();
num=Math.pow(3,length);
while(counter != num)
{
    String temp = generateRandomStr(length);
    if(array.contains(temp)==false)
    {
        array.add(temp);
        counter++;
    }
}

To explain, I want an ArrayList with all possible String combinations of given length and 3 letters.

So if length=11 , num=177147 runtime is almost 11 minutes. With bigger length, runtime will take at least half an hour.

Is there a way to multithread this loop?

EDIT:

I've read all the responses and I thank each and every one of you. Yeah I know my code is trash and I will work on that. I do not have experience since I am a student but I will try my best to improve

I don't see how your current code does the job. Anyways, yes, you can multithread that. But please post a sequential, runnable example program first that does the job. — akuzminykh
– akuzminykh, Commented May 15, 2020 at 11:17
The problem is with your brute force approach. For a test, you should count amount of iteration for the loop. I bet it will be in millions. That just isn't a good solution and multithreading that won't solve the problem. — Amongalen
– Amongalen, Commented May 15, 2020 at 11:18
Your code is slow not just because it runs in a single thread, but because 1. the algorithm is terrible 2. you use a list when you need to check membership often instead of a set (preferrably) hashset. Producing all possible combination can easily be done without any randomness ... search SO, there are tons of examples for this. — Joachim Sauer
– Joachim Sauer, Commented May 15, 2020 at 11:20
Err hint: when you permute characters in a string, nothing in there needs random elements. As the others say: fix your algorithm, not waste your time parallelizing awful code. And even if this just practice, there are many more meaningful examples to practice concurrent programming. — GhostCat
– GhostCat, Commented May 15, 2020 at 11:26

Michael · Accepted Answer · 2020-05-15 11:32:20Z

2

The problem is that you are using a random approach rather than a systematic approach.

There is nothing to stop generateRandomStr from generating the same string over and over again. It's a waste of time.

Your algorithm's performance gets worse and worse as it approaches a solution because the more strings you've found, the more time you're wasting on results you already know about.

The most sensible brute force approach is to try each string in order

aaaa
aaab
aaac

answered May 15, 2020 at 11:32

Michael

44.5k12 gold badges97 silver badges143 bronze badges

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

Comments

Aditya Chandla · Accepted Answer · 2020-05-16 10:28:27Z

Well you can use fork join framework and do something like this:

import java.util.*;
import java.util.concurrent.*;

class Solver extends RecursiveTask<List<String>> {
    char characters[] = {'a','b','c'};
    int length;
    int idx;
    StringBuilder current;

    public Solver(int idx, int length, StringBuilder current) {
        this.length = length;
        this.idx = idx;
        this.current = current;
    }

    @Override
    public List<String> compute() {
        if(idx == length - 1){
            List<String> finalList = new ArrayList<>();
            finalList.add(current.toString());
            return finalList;
        }
        List<Solver> recursiveTasks = new ArrayList<>();
        for(int i = 0; i < 3; ++i) {
            current.append(characters[i]);
            recursiveTasks.add(new Solver(idx+1, length, new StringBuilder(current.toString())));
            current.deleteCharAt(idx);
        }
        recursiveTasks.forEach((task) -> task.fork());
        List<String> finalList = new ArrayList<>();
        recursiveTasks.forEach((task) -> finalList.addAll(task.join()));
        return finalList;
    }
}

public class Main
{
    public static void main(String[] args) {
        int length = 11;
        ForkJoinTask<List<String>> task = new Solver(0, length, new StringBuilder(""));
        new ForkJoinPool(4).invoke(task);
    }
}

In my opinion this is more memory intensive than a simple recursive implementation. For length = 11 it worked like a breeze. just beware this algorithm is inherently exponential so don't expect it to work for large numbers. But you wanted a recursive implementation. Well here it is

Maurice Perry · Accepted Answer · 2020-05-15 13:23:46Z

Yes. As others have said, it's the algorithm. This one will generate a list of 177147 strings of length 11 in less than 20ms:

List<String> array = generate(11, "abc");

 private static List<String> generate(int length, String chars) {
     List<String> list = new ArrayList<>();
     generate(new char[length], 0, length, chars.toCharArray(), list);
     return list;
 }

 private static void generate(char[] buf, int i, int len, char[] chars, List<String> list) {
     if (i >= len) {
         list.add(new String(buf));
     } else {
         for (int k = 0; k < chars.length; ++k) {
             buf[i] = chars[k];
             generate(buf, i+1, len, chars, list);
         }
     }
 }

Collectives™ on Stack Overflow

Multithreading while loop

3 Answers 3

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Related