Wie Listenabgleich auf zwei CPU Cores auslagern?

[newnoise]

Hallo,

ich habe leider keine andere Möglichkeit als an einer Stelle meines Programmes 2 Listen mit ca. 300.000 Objekten miteinander zu vergleichen. Das ergibt logischerweise 300.000^2 Vergleiche, was doch recht lang dauert Nun krebst meine Anwendung immer nur auf einem Core rum. Wie kriege ich es hin, dass sie beide Cores nutzt?

Danke
noise

 

[Zacherl]

Wenn du die zwei Listen in einem Thread vergleichst, gar nicht - du musst dazu mehrere Threads benutzen. Du müsstest also z. B. sowas machen wie

vergleicheListeTeil1();
vergleicheListeTeil2();
...

wobei du jedesmal einen Thread erzeugst. Das Beispiel von mir ist jetzt natürlich absolut nicht anwendbar und Stuss, du musst quasi als erstes hinkriegen, dass du deinen Vergleich in mehrere Teile, die unabhängig voneinander sind, aufteilst. Ich nehm an, du hast momentan einfach eine doppelte Schleife?

 

[newnoise]

ja genau.

aber es müsste eigentlich gehen, wenn ich die äußere schleife quasi teile, oder?

ah, das ist ja gar nicht so schwer wie ich dachte hoffe ich.

danke

 

[Zacherl]

Ganz genau, also in etwa so:

new Thread(new Runnable() {
   public void run() {
      for (int i = 0; i < (list1.length / 2); i++) {
         for (int j = 0; j < list2.length; j++) {
            list1[i].compareTo(list2[j]); //oder sonst ein vergleich
         }
      }
   }
}.start();
new Thread(new Runnable() {
   public void run() {
      for (int i = (list1.length / 2); i < list1.length; i++) {
         for (int j = 0; j < list2.length; j++) {
            list1[i].compareTo(list2[j]); //oder sonst ein vergleich
         }
      }
   }
}.start();

 

[Gast2]

Musst du wirklich jedes Objekt mit jedem 2mal vergleichen?
Also Objekt1 mit Objekt2 und Objekt2 mit Objekt1 dann auch noch?

sonst reichts nämlich wenn du j bei i starten lässt.

 

[SlaterB]

bist du sicher dass man das nicht optimieren kann?

schau dir folgendes Testprogramm an

public class Test
{
    final int k = 22000;
    List<String> l1 = new ArrayList<String>();
    List<String> l2 = new ArrayList<String>();

    public Test()
    {
        Random r = new Random(42);
        for (int i = 0; i < k; i++)
        {
            l1.add("String " + r.nextInt(k));
            l2.add("String " + r.nextInt(k));
        }
        compare1();
        compare2();
    }

    public void compare1()
    {
        long time = System.currentTimeMillis();
        int c = 0;
        for (int i = 0; i < k; i++)
        {
            String st1 = l1.get(i);
            for (int j = 0; j < k; j++)
            {
                String st2 = l2.get(j);
                if (st1.equals(st2))
                {
                    c++;
                }
            }
        }
        System.out.println("c1: " + c + ", time: " + (System.currentTimeMillis() - time));
    }

    public void compare2()
    {
        long time = System.currentTimeMillis();
        Map<String, Integer> mapL1 = new HashMap<String, Integer>();
        for (int i = 0; i < k; i++)
        {
            String st1 = l1.get(i);
            Integer old = mapL1.get(st1);
            int newC = (old == null ? 0 : old.intValue()) + 1;
            mapL1.put(st1, Integer.valueOf(newC));
        }

        int c = 0;
        for (int j = 0; j < k; j++)
        {
            String st2 = l2.get(j);
            Integer old = mapL1.get(st2);
            if (old != null)
            {
                c += old.intValue();
            }
        }
        System.out.println("c2: " + c + ", time: " + (System.currentTimeMillis() - time));
    }

    public static void main(String[] args)
    {
        new Test();
    }
}

die quaratische Suche dauert bei mir 15 sec, mit ner Map findet man genauso viele Treffer in kaum messbaren 15 ms

mit 300000 compare1() besser nicht laufen lassen, schätzungsweise ne Stunde, compare2() nur 0.2 sec

 

[Marco13]

Wenn man jetzt noch weiß, welche Art von "Vergleich" gemeint ist, kann man auch sagen, ob man da vielleicht durch eine Sortierung Zeit sparen könnte (so absurd es vielleicht im ersten Moment klingt)