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

sirbender

Top Contributor
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.

Java:
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;
    }
}
 
Zuletzt bearbeitet:

Thallius

Top Contributor
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

Top Contributor
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

Super-Moderator
Mitarbeiter
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

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

Java:
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

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

sirbender

Top Contributor
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.


Java:
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

Bekanntes Mitglied
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:

Java:
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.
 

sirbender

Top Contributor
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:
Java:
            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

Top Contributor
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

Top Contributor
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.
Java:
    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.

Java:
    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();
        }
    }
 

sirbender

Top Contributor
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

Bekanntes Mitglied
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

Super-Moderator
Mitarbeiter
X

Xyz1

Gast
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.
 

DrZoidberg

Top Contributor
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.
Java:
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");
  }
}
 
Zuletzt bearbeitet:
Ähnliche Java Themen
  Titel Forum Antworten Datum
J Eine kleine Aufnahme mit Java Allgemeine Java-Themen 3
D Hat Java eine Library um JavaScript auszuwerten? Allgemeine Java-Themen 2
dokan wie kann ich eine funktionierende Suchleiste erstellen Allgemeine Java-Themen 1
B Wie erstelle ich dazu eine Abfrage ob der Button gedrückt wurde? Allgemeine Java-Themen 8
J Integration pay Pale in eine JavaFx Desktop Application Allgemeine Java-Themen 1
berserkerdq2 Wenn ich einfach eine GIF in den Scenebuilder als Bild reinpacke, wird das dann asl Gif angezeigt Allgemeine Java-Themen 1
8u3631984 Strukturiertes Logging : Jedes Feld in eine seperate Zeile - aber wie ? Allgemeine Java-Themen 2
berserkerdq2 Gibt es eine saubere Dokumentation von Jfoenix? Allgemeine Java-Themen 1
M Eigene Datenstruktur um eine Menge zu speichern Allgemeine Java-Themen 3
A Wie schreibe ich eine For-Schleife in ein Stream API um? Allgemeine Java-Themen 12
E Es ist nicht möglich, eine Batch-Anweisung auszuführen. Allgemeine Java-Themen 9
T Eine Frage des Designs Allgemeine Java-Themen 2
R Best Practice Erfahrungswerte für eine Migration von JSF nach Angular (oder anderes JS-Framework) Allgemeine Java-Themen 1
H Eine Linie verkürzen Allgemeine Java-Themen 5
N rekursion mehrfach eine Methode Öffnen Allgemeine Java-Themen 4
berserkerdq2 Wenn ich eine Methode nur jede 50ms ausführen will, wie mach ich das? Allgemeine Java-Themen 4
berserkerdq2 Wie synchronisiere ich eine for-Schleife Allgemeine Java-Themen 12
berserkerdq2 Wie mache ich in IJVM eine if verzweigung? Allgemeine Java-Themen 27
F Gibt es mittlerweile eine Alternative zu DaisyDiff Allgemeine Java-Themen 2
_user_q Was brauche ich, um eine eigene "Search for updates"-Funktion einzubauen? Allgemeine Java-Themen 1
E Eine Methode einer extendeten Klasse deakitivieren Allgemeine Java-Themen 12
LimDul Kam eine java.net.URL zu einer HashMap und ging als DNS Anfrage wieder heraus Allgemeine Java-Themen 18
pizza_dox_9999 Wie füge ich eine "eigene" ScriptEngine dem ScriptEngineManager? Allgemeine Java-Themen 3
F Kennt ihr eine Library um 2 HTML Seiten zu diffen? Allgemeine Java-Themen 8
Y ImagePanel von anderer Klasse in eine MainFrame Klasse hinzufügen. Allgemeine Java-Themen 1
OnDemand Anzeigen was eine Applikation macht Allgemeine Java-Themen 1
T Problem beim Umwandeln in eine Jar-Datei Allgemeine Java-Themen 3
J Eine Frage zu den Threads und Task Allgemeine Java-Themen 1
Tobero Wie bekomme ich in welchem Quadrat sich eine Position in einem Grid befindet Allgemeine Java-Themen 11
Tobero Wie kann man eine Poisson Disc Sampler? Allgemeine Java-Themen 7
M Openjdk - gibt es auch eine Openjre? Allgemeine Java-Themen 7
R Lambda Expression in einer Methode execute() aufrufen (execute() ist eine Methode aus dem funktionalen Interface Command) Allgemeine Java-Themen 5
S Noch eine Design-Frage zu Setter Allgemeine Java-Themen 6
N Arrayliste in eine Datei speichern Allgemeine Java-Themen 4
J Öffnen eine jar-Datei Allgemeine Java-Themen 11
Zrebna Gibt es eine Möglichkeit eine NPE zu vermeiden, wenn null returned wird? Allgemeine Java-Themen 3
S Klassen Einfügen von unbekannter menge an Variablen in eine Klasse mithilfe von ASM Allgemeine Java-Themen 5
R Wo müsste ich im Code eine Änderung vornehmen? Allgemeine Java-Themen 6
S Rückgabe einer HttpURLConnection für eine Seite einlesen bei der man eingeloggt ist..? Allgemeine Java-Themen 5
S Gibt es eine Moeglichkeit die Runtime Ausführung zu analysieren..? Allgemeine Java-Themen 7
S Habt ihr eine Idee wie man Serializierung testen kann..? Allgemeine Java-Themen 6
S Wenn eine Klasse zwei Interfaces mit derselben Methodensignatur implementiert: welche wird aufgerufen? Allgemeine Java-Themen 15
Drachenbauer warum bekomme ich hier eine NullPointerException Allgemeine Java-Themen 6
M Gibt es eine API die den aktuellen Wert eines Indikators beim Trading zurückgibt? Allgemeine Java-Themen 7
X Collections Gibt es eine Klasse welche die Vorteile von List und HashMap vereint, aber konstante Laufzeit (O(1)) hat in Java? Allgemeine Java-Themen 4
N Eine stelle der Fibonacci-Zahlenfolge ausgeben. Allgemeine Java-Themen 4
E Hat der Compiler einen Fehler oder warumbeendet return nicht eine Methode ? Allgemeine Java-Themen 7
W Collections Suche etwas Sorted-List-Artiges...hat jemand eine Idee? Allgemeine Java-Themen 13
L Methoden Über Reflections eine Methode mit aufrufen Allgemeine Java-Themen 3
S Kann ich eine Methode schreiben die alle Arten von funktionalen Interfaces akzeptiert..? Allgemeine Java-Themen 21
Drachenbauer Wie kann eine vorgegebene Farbe über einen String erkannt werden? Allgemeine Java-Themen 11
J Datenstruktur für eine Map erstellen Allgemeine Java-Themen 2
sascha-sphw Java 9 module Zugriff auf eine resource einer anderen JAR Allgemeine Java-Themen 0
pkm Kann eine ServerSocket-Klasse nicht stateful sein? Allgemeine Java-Themen 4
B Aufruf der Methode ergibt eine Exception Allgemeine Java-Themen 13
I Eine Anwendung so gut wie möglich beschützen Allgemeine Java-Themen 9
M Wie kann man eine void Methode mit Variablen von zwei verschiedenen Objekten ausführen? Allgemeine Java-Themen 15
X Wie mache ich hier eine Rekursion rein ? Allgemeine Java-Themen 7
K OOP Suche Hilfe + Erklärung für eine Hausaufgabe Allgemeine Java-Themen 1
N Über einen Button in JavaFX ein Event über eine Pipeline schicken(Netty) Allgemeine Java-Themen 1
M Login in eine Webseite mit Java Allgemeine Java-Themen 3
A NetBeans Suche Programmierer für eine Belegarbeit Allgemeine Java-Themen 11
D Warum kann ich eine (deflaut) Klasse aus einer Libary in einem anderen Projekt benutzen? Allgemeine Java-Themen 3
L Übergabe an eine eher einfache Java- Applikation wegen Kündigung Allgemeine Java-Themen 1
C Ein Iterator ist eine Implementierung des Interface Iterable? Allgemeine Java-Themen 2
M Schlüsselworte Was ist eine Java Spezifikation + JSR? Allgemeine Java-Themen 11
E RMI NULL-Pointer-Exeception wenn der RMI-Proxy eine Methode deligiert Allgemeine Java-Themen 2
E RMI FWH: RMI- Wie erstelle ich stubs dynamisch, bzw. unterdrücke eine Statisch-Warnung? Allgemeine Java-Themen 0
J Eine bestimmte Zahl im Integer ändern Allgemeine Java-Themen 9
Q-bert Strings aus der JList in eine Datenbank speichern Allgemeine Java-Themen 1
D Möglichkeit mit GAE eine Table auszulesen und eine csv zu schreiben Allgemeine Java-Themen 22
S Korrekte Pfadangaben damit eine .jar Datei unter Windwos läuft. Allgemeine Java-Themen 24
D Eine Forschleife mit Threads abarbeiten um es zu schneller zu machen. Ist das möglich? Allgemeine Java-Themen 20
B Gibt es eine Funktion die den Datentyp einer Variablen ermittelt? Allgemeine Java-Themen 8
R bei eclipse von java in eine andere programmiersprache wechseln? Allgemeine Java-Themen 2
D Pivot-Wahl beim QuickSort steigert die Effizienz, eine Lüge??? Allgemeine Java-Themen 17
C Eclipse einstellen, dass eine bestimmte JDK benutzt werden soll Allgemeine Java-Themen 3
M Klassen Eine Klasse in mehreren Klassen einbinden Allgemeine Java-Themen 11
A Best Practice Java - eine Art Plugin-Struktur Allgemeine Java-Themen 3
S wie rufe ich mit .jar datei eine .bat auf? Allgemeine Java-Themen 15
R Signatur von Methoden in eine Datei schreiben? Allgemeine Java-Themen 4
perlenfischer1984 Functionsparameter prüfen und eine Exception werfen !? Allgemeine Java-Themen 11
J Mehrere Wörter getrennt in eine Array einlesen, wie ? Allgemeine Java-Themen 7
E Methoden Hat jemand eine gute Lösung? Allgemeine Java-Themen 5
Z NullPointerException beim Schreiben einer ArrayList in eine Datei Allgemeine Java-Themen 6
Exdroid BlueJ Wie bekomme ich die Ausgabe in eine TXT Datei? Allgemeine Java-Themen 2
G Methoden Aus einem Event, wo ich weiß, dass es ausgeführt werden wird, eine Get-Methode basteln Allgemeine Java-Themen 8
F Wie kann ich auf einem System prüfen, ob eine lib verfügbar ist? Allgemeine Java-Themen 2
Tausendsassa Interface Eine Gui von einer anderen schließen lassen Allgemeine Java-Themen 3
S Threads Kann mir jemand helfen eine parallele Hilfsklasse zu implementieren..? Allgemeine Java-Themen 3
S Best Practice Brauche eine Idee für eine Java Projekt! Allgemeine Java-Themen 11
P Zwei ArrayLists: Ohne die eine überhaupt anzurühren, wird sie verändert Allgemeine Java-Themen 2
M Eine Datei im Speicher erneut laden(?) Allgemeine Java-Themen 1
V Gibt es eine Möglichkeit die Internet auslastung mit Java auszulesen Allgemeine Java-Themen 11
L Drop Emails von Outlook in eine JList Allgemeine Java-Themen 5
P Wie funktioniert das Feedback eines Klicks auf eine Java GUI Allgemeine Java-Themen 10
P Dezimalzahl in eine Binärzahl umrechnen Allgemeine Java-Themen 12
M Eine static-Methode verlassen Allgemeine Java-Themen 2
X HTTP Auslesen der Ergebnisse von einer Webseite und in eine Liste packen Allgemeine Java-Themen 1
T Input/Output Daten in eine Datei schreiben Allgemeine Java-Themen 4

Ähnliche Java Themen

Neue Themen


Oben