Wie kann ich eine kleine Stelle in meinem Code mit multiplen Threads abarbeiten..?

[sirbender]

Hallo,
ich habe ein recht komplexes Programm, bei dem ich einen kleinen Bereich mit mehreren Threads ausfuehren will.

Ich habe mal ein minimales Beispiel geschrieben, damit man ungefaehr sieht was ich nebenlaeufig ausfuehren will.

Ich hab den Bereich der durch mehrere Threads ausgefuehrt werden soll mit // mehrere Threads markiert. Im Beispiel werden zufaellig 1000 Quadrate erzeugt mit der Kantenlaenge 10. Die Position x,y der Quadrate ist zufaellig. Einige Quadrate ueberlappen und dies ist nicht erlaubt. Im Rechenschritt der parallelisiert werden soll, werden die Quadrate durchlaufen und geschaut ob sie mit einem Quadrat in der "output" Liste ueberlappen. Wenn ja, bekommt das Quadrat eine neue Position bis keinen Konflikt mehr gibt und es dann der "output" Liste hinzugefuegt wird.

public class MultiThreadedAccess {

    public static void main(String[] args) {
        int n = 1000;
        Random ran = new Random();
        int w = 10, h = w;
        List<Rectangle> input = new ArrayList<Rectangle>(n);
        for (int i = 0; i < n; i++) {
            input.add(new Rectangle(ran.nextInt(n), ran.nextInt(n), w, h));
        }

        List<Rectangle> output = new ArrayList<Rectangle>(n);

        // mehrere Threads
        for (Rectangle r : input) {
            expensiveCalc(r);
            while (conflicts(r, output)) {
                Point p = expensiveCalc(r);
                r.setLocation(p.x, p.y);
            }
            output.add(r);
        }
        // mehrere Threads
    }

    private static boolean conflicts(Rectangle r, List<Rectangle> output) {
        for (Rectangle fixed : output) {
            if (r.intersects(fixed)) {
                // System.out.println(r + " conflicts " + fixed);
                return true;
            }
        }
        return false;
    }
}

 

[Thallius]

Eine parallelisierung wird hier wenig Sinn machen denn die Threads müssten sich ja gegenseitig blockieren. Sonst könnten ja zwei Threads gleichzeitig die gleiche Position testen und für leer befinden und dann das rechteck dort platzieren. Schon hast du zwei Rechtecke übereinander.

Gruß

Claus

 

[sirbender]

Das ist leider nur ein Minimalbeispiel. Der conflicts() Test dauert nur sehr kurz und davor gibt es immer einen Aufruf von "expensiveCalc()".

Ich hab mal das Beispiel gefixt. Der "conflicts()" Test haengt von den anderen Quadraten ab, die "expensiveCalc()" nicht.

D.h. es ist sehr wahrscheinlich, dass einige Threads gerade mit der expensiveCalc() beschaeftigt sind waehrend nur 1-2 Threads den conflicts() Test machen wollen.

 

[mrBrown]

Das dürfte eigentlich recht simple sein, im Wesentlichen musst du nur das innere der forEach parallel, laufen lassen, zB mit Streams oder händisch mit ExecutorService, und die Aufrufe von conflicts und add synchronisieren.

 

[JCODA]

Wäre das folgende eine "richtige" Lösung?

import java.awt.Point;
import java.awt.Rectangle;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class MultiThreadedAccess {
   
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int n = 100;
        Random ran = new Random();
        int w = 10, h = w;
        List<Rectangle> input = new ArrayList<Rectangle>(n);
        for (int i = 0; i < n; i++) {
            input.add(new Rectangle(ran.nextInt(n), ran.nextInt(n), w, h));
        }

        List<Rectangle> output = new ArrayList<Rectangle>(n);
        input.stream().parallel().forEach(r -> loopFor(r,output));       
        long mid = System.currentTimeMillis();       
        System.out.println("finished parallel: "+ (start-mid));
       
       
        List<Rectangle> output2 = new ArrayList<Rectangle>(n);
        input.stream().forEach(r -> loopFor(r,output2));
        long end = System.currentTimeMillis();       
        System.out.println("finished non-parallel: "+ (mid-end));
       
    }

    private static void loopFor(Rectangle r, List<Rectangle> output){
        expensiveCalc(r);
        while (conflicts(r, output)) {
            Point p = expensiveCalc(r);
            r.setLocation(p.x, p.y);
        }
        synchronized(output){
            output.add(r);
        }           
    }
   
    private static Point expensiveCalc(Rectangle r) {
        try {
            Thread.sleep(50);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }       
        return new Point((int)(Math.random()*10000),(int)(Math.random()*10000));
    }

    private static boolean conflicts(Rectangle r, List<Rectangle> output) {
        synchronized(output){
            for (Rectangle fixed : output) {
                if (r.intersects(fixed)) {
                    // System.out.println(r + " conflicts " + fixed);
                    return true;
                }
            }
       
            return false;
        }
    }
}

 

[sirbender]

Vielen Dank. Puhhh...ich glaube ich muss mich erstmal in Streams einlesen bevor ich es wirklich kapiere. Normalerweise parallelisiere ich mit ExecutorService 😉

 

[sirbender]

Hi,
ich hab mir noch ein paar mehr Gedanken gemacht. Anbei der Code. Irgendwie passiert es manchmal, dass "output" nicht alle alle "Rectangles" aus Input hinzugefuegt bekommen hat. Und ich kann mir beim besten Willen nicht erklaeren woran das liegen kann. Hat irgendwer eine Idee?

Meistens rechnet das Programm richtig, aber manchmal eben nicht, dann spuckt es sowas aus: WTF! Only: 997. In output sind also 997 und nicht 1000 wie erwartet.

Ich habe den Code so abgeaendert, dass er alle Rectangle-Intersections durchgefuehrt hat und den "synchronized" Block erst betritt wenn er sich relativ sicher ist, dass er jetzt das Rechteck hinzufuegen darf. Klappt auch meistens.

public class MultiThreadedAccess4 {

    final static boolean DEBUG = false;
    final static int n = 1000;
    final static int w = 10, h = w;
    final static Random ran = new Random();
    static Lock lock = new ReentrantLock();
    static int syncCount = 0;
    static int intersectCount = 0;

    public static void main(String[] args) throws Exception {
        final int repeats = 100;
        for (int i = 0; i < repeats ; i++) {
            final List<Rectangle> input = getRandomInput();
            final List<Rectangle> output = new CopyOnWriteArrayList<Rectangle>();

            final List<Callable<Rectangle>> taskList = new ArrayList<Callable<Rectangle>>();
            for (final Rectangle r : input) {
                taskList.add(new Callable<Rectangle>() {
                    @Override
                    public Rectangle call() throws Exception {
                        return calc(r, output, true);
                    }
                });
            }

            final ExecutorService service = Executors.newFixedThreadPool(4);

            final long start = System.currentTimeMillis();
            service.invokeAll(taskList);
            final long end = System.currentTimeMillis();
            System.out.println("finished parallel: " + (end - start));

            fullConflictsCheck(output);
            System.out.println("SyncCount: " + syncCount);
            System.out.println("intersectCount: " + intersectCount);

            service.shutdown();
            syncCount = 0;

            if (output.size() != input.size()) {
                System.err.println("WTF! Only: " + output.size());
            }
            System.out.println();
        }
    }

    private static Rectangle calc(Rectangle r, List<Rectangle> output, boolean firstRun) {
        int conflictfreeIndex = resolveConflicts(r, output, firstRun);
        while (true) {
            final int newIndex = output.size(); // check if other threads added new rectangles to output
            final int diff = newIndex - conflictfreeIndex;
            if (DEBUG && diff != 0) System.err.println(Thread.currentThread().getName() + " Added after last Check: " + diff + " [" + conflictfreeIndex + "," + newIndex + "]");
            if (diff != 0) {
                // check if the new rectangles in output conflict with the current Rectangle
                for (Rectangle rx : output.subList(conflictfreeIndex, newIndex)) {
                    // System.err.println(r.getLocation() + " -> " + rx.getLocation());
                    if (r.intersects(rx)) return calc(r, output, false); // if yes, start over by calling this method again
                }
            }

            conflictfreeIndex = newIndex;
           
            // last test before entering the costly synchronized to increase chances that r can be added to output
            if (conflictfreeIndex == output.size()) { // check if other threads added new rectangles to output
                synchronized (output) {
                    syncCount++;
                    if (conflictfreeIndex == output.size()) { // last check if other threads added new rectangles to output
                        output.add(r);
                        return r;
                    }
                    if (DEBUG) System.err.println(Thread.currentThread().getName() + " Unsuccessful Sync: " + (output.size()-conflictfreeIndex) + " [" + conflictfreeIndex + "," + output.size() + "]");
                }
            }
            else if (DEBUG) System.err.println(Thread.currentThread().getName() + " Unsuccessful Pre-Sync: " + (output.size()-conflictfreeIndex) + " [" + conflictfreeIndex + "," + output.size() + "]");

        }
    }

    private static int resolveConflicts(Rectangle r, List<Rectangle> output, boolean firstRun) {
        if (firstRun == false) {
            r.setLocation(expensiveCalc(r));
        }
        int size = output.size();
        while (conflicts(r, output)) {
            r.setLocation(expensiveCalc(r));
            size = output.size();
        }
        return size;
    }

    private static boolean conflicts(Rectangle r, List<Rectangle> output) {
        for (Rectangle fixed : output) {
            if (r.intersects(fixed)) {
                intersectCount++;
                return true;
            }
        }
        return false;
    }

    private static Point expensiveCalc(Rectangle r) {
        try {
            Thread.sleep(5);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        return randomPoint();
    }

    private static Point randomPoint() {
        return new Point(ran.nextInt(n), ran.nextInt(n));
    }

    private static List<Rectangle> getRandomInput() {
        List<Rectangle> input = new ArrayList<Rectangle>(n);
        for (int i = 0; i < n; i++) {
            input.add(new Rectangle(randomPoint(), new Dimension(w, h)));
        }
        return Collections.unmodifiableList(input);
    }

    private static boolean fullConflictsCheck(List<Rectangle> output) {
        int n = output.size();
        int totalCombinations = n * (n - 1) / 2;
        System.out.println("Total Combinations: " + totalCombinations);
        int tests = 0;
        int index = 0;
        for (Rectangle r : output) {
            index++;
            for (int i = index; i < output.size(); i++) {
                tests++;
                if (r.intersects(output.get(i)))
                    return true;
            }
        }
        System.out.println("No. of Conflict Tests: " + tests);
        return false;
    }
}

 

[TheWhiteShadow]

Der Ansatz ist gut, nur...
Du greift ständig auf dein output-array zu, ohne es zu synchronisieren. Dann führt deine calc-Methode eine rekursion innerhalb einer Schleife aus. Entscheide dich mal für eins davon. Beides ist hier überflüssig. Außerdem wartest du nicht, bis dein Executor-Service fertig ist, damit ist das Benchmarking an der Stelle sinnlos.

Ich habs mal ein bischen umgestrickt und so müsste es gehen:

public class AlternativResult
{
    final static boolean DEBUG = true;
    final static int n = 1000;
    final static int w = 10, h = w;
    final static Random ran = new Random();
//    static Lock lock = new ReentrantLock();
   
    static volatile int syncCounts = 0;
    static volatile int intersectCount = 0;
    static volatile int outputSize = 0;
    static volatile int doubleChecks;
   
    static final List<Rectangle> output = new ArrayList<Rectangle>(n);
   
    public static void main(String[] args) throws Exception
    {
        final int repeats = 10;
        for (int i = 0; i < repeats; i++)
        {
            output.clear();
            outputSize = 0;
            doubleChecks = 0;
            syncCounts = 0;
            intersectCount = 0;
           
            final List<Rectangle> input = getRandomInput();
           
            final ExecutorService calculator = Executors.newFixedThreadPool(4);
           
            final List<Runnable> taskList = new ArrayList<Runnable>();
            for (final Rectangle r : input)
            {
                taskList.add(new Runnable()
                {
                    @Override
                    public void run()
                    {
                        calc(r);
                    }
                });
            }
   
            final long start = System.currentTimeMillis();
           
            for (Runnable task : taskList)
            {
                calculator.execute(task);
            }
   
            calculator.shutdown();
            if (!calculator.awaitTermination(20, TimeUnit.SECONDS))
            {
                System.out.println("Timeout!!!!!");
            }
            final long end = System.currentTimeMillis();
            System.out.println("finished parallel: " + (end - start));
           
            System.out.println("outputSize:     " + outputSize);
            System.out.println("doubleChecks:   " + doubleChecks);
           
            if (fullConflictsCheck())
            {
                System.out.println("Konflikt!");
            }
           
            System.out.println("syncCounts:     " + syncCounts);
            System.out.println("intersectCount: " + intersectCount);
           
            if (output.size() != input.size())
            {
                System.err.println("WTF! Only: " + output.size());
            }
            System.out.println();
        }
    }
   
    private static void calc(Rectangle r)
    {
        CALC:
        while(true)
        {
            r.setLocation( expensiveCalc(r) );
            final int lastIndex;
            lastIndex = output.size()-1;
           
            for(int i = 0; i <= lastIndex; i++)
            {
                if ( r.intersects(output.get(i)) )
                {
                    continue CALC;
                }
            }
           
            final int newLastIndex;
            newLastIndex = output.size()-1;
           
            if (lastIndex != newLastIndex)
            {
                doubleChecks++;
                for(int i = lastIndex+1; i <= newLastIndex; i++)
                {
                    if ( r.intersects(output.get(i)) )
                    {
                        continue CALC;
                    }
                }
            }
           
            synchronized (output)
            {
                syncCounts++;
                for(int i = newLastIndex+1; i < output.size(); i++)
                {
                    if ( r.intersects(output.get(i)) )
                    {
                        intersectCount++;
                        continue CALC;
                    }
                }
                output.add(r);
                outputSize++;
                return;
            }
        }
    }
   
//    private static boolean conflicts(Rectangle r, List<Rectangle> output)
//    {
//        for (Rectangle fixed : output)
//        {
//            if (r.intersects(fixed))
//            {
//                intersectCount++;
//                return true;
//            }
//        }
//        return false;
//    }
   
    private static Point expensiveCalc(Rectangle r)
    {
        try
        {
            Thread.sleep(5);
        }
        catch (InterruptedException e)
        {
            e.printStackTrace();
        }
        return randomPoint();
    }

    private static Point randomPoint()
    {
        return new Point(ran.nextInt(n), ran.nextInt(n));
    }

    private static List<Rectangle> getRandomInput()
    {
        List<Rectangle> input = new ArrayList<Rectangle>(n);
        for (int i = 0; i < n; i++)
        {
            input.add(new Rectangle(randomPoint(), new Dimension(w, h)));
        }
        return Collections.unmodifiableList(input);
    }
   
    private static boolean fullConflictsCheck()
    {
        int n = output.size();
        int totalCombinations = n * (n - 1) / 2;
        System.out.println("Total Combinations: " + totalCombinations);
        int tests = 0;
        int index = 0;
        for (Rectangle r : output)
        {
            index++;
            for (int i = index; i < output.size(); i++)
            {
                tests++;
                if (r.intersects(output.get(i)))
                    return true;
            }
        }
        System.out.println("No. of Conflict Tests: " + tests);
        return false;
    }
}

Die zweite Prüfung in der calc-Methode hab ich eingebaut, um mal zu testen, wie oft die Liste während der ersten Prüfung weiter wächst. <10% der Fälle - Somit überflüssig.
Außerdem hab ich die Callable mal in Runnable umgeändert, weil es mich verwirrt hat, dass der Rückgabewert nirgens benutzt wurde.

 

[mrBrown]

Du greift ständig auf dein output-array zu, ohne es zu synchronisieren

In den meisten Fällen ist das egal, da es eine CopyOnWriteArrayList ist (und lernt doch mal den Unterschied zwischen Array und Liste 😉 )

Aber für Nutzung von Labels gehört man gesteinigt 😉

 

[sirbender]

Die zweite Prüfung in der calc-Methode hab ich eingebaut, um mal zu testen, wie oft die Liste während der ersten Prüfung weiter wächst. <10% der Fälle - Somit überflüssig.
Außerdem hab ich die Callable mal in Runnable umgeändert, weil es mich verwirrt hat, dass der Rückgabewert nirgens benutzt wurde.

Vielen Dank. Die Labels sind zwar nicht huebsch, aber es ist ja eh nur Experimentiercode und es bleibt ja recht ueberschaubar.

Ich hab mal spasseshalber die Executor-Thread-Anzahl auf 16, 32, 64 erhoeht und manchmal wirft es dann im ersten Run eine Exception. Je hoeher die Thread-Anzahl desto wahrscheinlicher. Bei 4 oder 8 Threads hab ich die Exception nie gesehen. Auch wird sie wirklich nur im ersten Run geworfen, bis die VM warmgelaufen ist scheinbar.

Passieren sollte sowas aber trotzdem nicht. Irgendwie kapier ich auch immer noch nicht wo mein Sync-Problem war, da ich eben wie erwaehnt CopyOnWriteArrayList nutze und alle Schreibvorgaenge per 'synchronized' auf die CopyOnWriteArrayList-Instanz zusaetzlich beschraenkt habe. Aber vielleicht klaert sich das ja auf, wenn wir rausfinden warum dein Code eine Exception wirft?

Die Exception wird uebrigens beim intersects-Test geworfen. r oder output.get(i) scheinen Null zu sein. Komisch:

            if (lastIndex != newLastIndex) {
                doubleChecks++;
                for (int i = lastIndex + 1; i <= newLastIndex; i++) {
                    if (r.intersects(output.get(i))) {
                        continue CALC;
                    }
                }
            }

Exception in thread "pool-1-thread-4" java.lang.NullPointerException
at java.awt.Rectangle.intersects(Rectangle.java:786)
at exp.AlternativResult.calc(AlternativResult.java:104)
at exp.AlternativResult.access$0(AlternativResult.java:86)
at exp.AlternativResult$1.run(AlternativResult.java:50)
at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
at java.lang.Thread.run(Thread.java:748)
finished parallel: 306
syncTime: 174
outputSize: 999
doubleChecks: 346
Total Combinations: 498501
No. of Conflict Tests: 498501
syncCounts: 1000
intersectCount: 1
WTF! Only: 999

und lernt doch mal den Unterschied zwischen Array und Liste 😉

Wie meinst du das genau bezogen auf den Code von TheWhiteShadow oder meinen Code oder bezogen auf CopyOnWriteArrayList?

 

[sirbender]

Ich hab mal den Debugger angeschmissen und nach 10 Versuchen konnte ich die NullpointerException reproduzieren. Wie zu erwarten ist output.get(i) das Problem.

 

[sirbender]

Ich denke das Problem bei dir ist ArrayList. Der synchronized-Block verhindert nicht, dass andere Threads die ArrayList lesen, sondern nur, dass sie den Block betreten wenn sich gerade ein Thread darin befindet. Der Thread der gerade schreibt erhoeht den internen index (also die Size der Liste) BEVOR er den Wert von Null auf Rectangle aendert. Ein lesender Thread kann deswegen Null bekommen. Passiert nur sauselten...so selten, dass man extrem viele Threads nutzen muss, damit man es ueberhaupt mal sieht.

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

Bei CopyOnWirteArrayList wird erst eine Kopie des Arrays gemacht bevor das Rectangle hinzugefuegt wird. Alle lesenden Threads die output.get(i) aufrufen bekommen noch den alten Array zu sehen. Auch ist der array volatile, sodass wenn der schreibende Thread die Arrays mal austauscht die lesenden Threads nun sofort den neuen Array sehen.

    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

 

[mrBrown]

Wie meinst du das genau bezogen auf den Code von TheWhiteShadow oder meinen Code oder bezogen auf CopyOnWriteArrayList?

Auf seine Erklärung:

output-array

^^

 

[sirbender]

Uebrigens finde ich interessant, dass bei vielen Threads (z.B. 32), die doubleChecks eben doch wichtig werden. In dem Output unten sieht man beim zweiten Run, das es 353 doubleChecks gab. Ohne die haette es potentiell zu 353 zusaetzlichen syncCounts kommen koennen.

Finde die Parallelisierungsmethode richtig toll. Ich hab nur Mist beim ExecutorService gebaut indem ich nicht darauf gewartet hab, dass die Threads alle erfolgreich durchlaufen. Glaube das war mein einziger Fehler - werde das aber nochmal checken.

finished parallel: 237
syncTime: 77
outputSize: 1000
doubleChecks: 234
Total Combinations: 499500
No. of Conflict Tests: 499500
syncCounts: 1002
intersectCount: 2

finished parallel: 221
syncTime: 144
outputSize: 1000
doubleChecks: 353
Total Combinations: 499500
No. of Conflict Tests: 499500
syncCounts: 1001
intersectCount: 1

finished parallel: 216
syncTime: 9
outputSize: 1000
doubleChecks: 312
Total Combinations: 499500
No. of Conflict Tests: 499500
syncCounts: 1000
intersectCount: 0

finished parallel: 211
syncTime: 5
outputSize: 1000
doubleChecks: 152
Total Combinations: 499500
No. of Conflict Tests: 499500
syncCounts: 1000
intersectCount: 0

finished parallel: 221
syncTime: 10
outputSize: 1000
doubleChecks: 195
Total Combinations: 499500
No. of Conflict Tests: 499500
syncCounts: 1000
intersectCount: 0

finished parallel: 209
syncTime: 11
outputSize: 1000
doubleChecks: 95
Total Combinations: 499500
No. of Conflict Tests: 499500
syncCounts: 1000
intersectCount: 0

finished parallel: 212
syncTime: 11
outputSize: 1000
doubleChecks: 460
Total Combinations: 499500
No. of Conflict Tests: 499500
syncCounts: 1000
intersectCount: 0

finished parallel: 217
syncTime: 4
outputSize: 1000
doubleChecks: 311
Total Combinations: 499500
No. of Conflict Tests: 499500
syncCounts: 1000
intersectCount: 0

finished parallel: 211
syncTime: 8
outputSize: 1000
doubleChecks: 199
Total Combinations: 499500
No. of Conflict Tests: 499500
syncCounts: 1000
intersectCount: 0

finished parallel: 209
syncTime: 10
outputSize: 1000
doubleChecks: 243
Total Combinations: 499500
No. of Conflict Tests: 499500
syncCounts: 1000
intersectCount: 0

 

[TheWhiteShadow]

Der Thread der gerade schreibt erhoeht den internen index (also die Size der Liste) BEVOR er den Wert von Null auf Rectangle aendert.

ok, ich hätte mir die add-methode von der ArrayList mal anschauen sollen.^^
synchronisiert man alle "output.size()"-Zeilen gehts. Verwendet man einfach die Variable outputSize gehts auch.

und lernt doch mal den Unterschied zwischen Array und Liste

output-array ist doch nur die Kurzform von output-arraylist 😉

Und Labels sind cool.

 

[mrBrown]

output-array ist doch nur die Kurzform von output-arraylist 😉

Allerdings ist array das Gegenteil von list

Und Labels sind cool.

Dafür gehört man vor'm steinigen noch geteert und gefedert...
Label zeugen eigentlich nur von einem: unglaublich schlechtem Code, den man am besten mit strg+A & Entf. refactored.

 

[Meniskusschaden]

Ach, was hätten wir damals für Label gegeben, als wir in alten BASIC-Tagen noch mit GOTO zeilennummerarbeiten mussten?😉

 

[sirbender]

10 Home
20 Sweet
30 GOTO 10

 

[Xyz1]

Hier geht's anscheinend um Bashing.
Labels sind per se nicht evil.
Und "goto" hat man sich auch vorbehalten, wie sicherlich jeder weiß.

Dann zum eigentlichen Thema. Hat das Verfahren einen Namen? Dann wärn wir schonmal Schritt weiter. "Parallelisierung" gibts dann noch einiges zu beachten. Wisst ihr aber auch.

 

[mrBrown]

Labels sind per se nicht evil.
Und "goto" hat man sich auch vorbehalten, wie sicherlich jeder weiß.

Man kann sich auch mit der Schrotflinte in den Fuß schießen, ist auch nicht per se evil und hat man nicht verboten.

 

[DrZoidberg]

Hier mal eine andere Lösung mit Streams. Ohne irgendwelche Locks. Solange die Worker-Threads laufen wird input nicht verändert, daher sollte keine zusätzliche Synchronisierung nötig sein.

import java.util.List;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import java.util.stream.IntStream;
import java.awt.Rectangle;
import java.awt.Point;

public class RecTest {
  private static Random ran = new Random();

  private static Rectangle randRect(int max) {
    return new Rectangle(ran.nextInt(max), ran.nextInt(max), 10, 10);
  }

  private static Point randPoint(int max) {
    return new Point(ran.nextInt(max), ran.nextInt(max));
  }

  private static BitSet getConflictingRectangleIdxs(List<Rectangle> input) {
    return IntStream.range(0, input.size()).parallel().mapToObj(idx -> {
      BitSet set = new BitSet(input.size());
      Rectangle r = input.get(idx);
      for(int i = idx + 1; i < input.size(); i++) {
        if(r.intersects(input.get(i))) {
          set.set(i);
        }
      }
      return set;
    }).reduce(new BitSet(input.size()), (bs1, bs2) -> {
      bs1.or(bs2);
      return bs1;
    });
  }

  static List<Rectangle> genNewList(List<Rectangle> input, int max, BitSet conflictingRectanglesIdx) {
    return IntStream.range(0, input.size()).parallel().mapToObj(idx -> {
      if(conflictingRectanglesIdx.get(idx)) return randRect(max);
      else return input.get(idx);
    }).collect(Collectors.toList());
  }

  public static void main(String[] args) throws Exception {
    int n = 20000;
    List<Rectangle> input = new ArrayList<Rectangle>(n);
    for(int i = 0; i < n; i++) input.add(randRect(n));

    long start = System.nanoTime();

    BitSet conflictingRectanglesIdx = getConflictingRectangleIdxs(input);

    while(conflictingRectanglesIdx.cardinality() > 0) {
      System.out.println("Anzahl ueberlappender Rechtecke = " + conflictingRectanglesIdx.cardinality());
      input = genNewList(input, n, conflictingRectanglesIdx);
      conflictingRectanglesIdx = getConflictingRectangleIdxs(input);
    }

    long end = System.nanoTime();
    double time = (end - start)/1e9;
    System.out.println("Anzahl ueberlappender Rechtecke = " + conflictingRectanglesIdx.cardinality());
    System.out.println("time = " + time +"s");
  }
}