Vergleich zweier Arrays

[Guest]

Hallo Leute,
ja, ich weiss, dass die Überschrift ein mit Sicherheit schon längst durchgekautes Thema ist, jedoch handelt es sich (meiner Meinung nach) bei meiner Frage um etwas Spezifischeres...

Ich habe zwei String[] - Arrays mit jeweils unterschiedlicher Länge und verschiedensten Wörtern als Objekte. Nun möchte ich jedoch schauen wie die Schnittmenge der zwei Arrays aussieht, d.h. wie viele Wörter sie gemeinsam haben. Die Wörter an sich brauche ich eigentlich nicht, sondern eher die Zahl als Ergebnis...

Und glaubt bitte nicht, dies wäre irgendeine Hausaufgabe oder wasauchimmer....ich bin lediglich total durcheinander nach verschiedensten Versuchen mit HashSets, etc.

Für Hilfe wäre ich dankbar!
MfG

 

[Marco13]

Ja, mit HashSets würde das gehen - so grob aus dem Kopf(!)

Set<String> s0 = new HashSet<String>(Arrays.asList(array0));
Set<String> s1 = new HashSet<String>(Arrays.asList(array1));
s1.retainAll(s0);
int common = s1.size();

oder eben zwei Schleifen (vmtl. deutlich effizienter)

int common = 0;
for (String s0 : array0)
{
    for (String s1 : array1)
    {
        if (s0.equals(s1)) common++;
    }
}

 

[Ebenius]

oder eben zwei Schleifen (vmtl. deutlich effizienter)

Nur bei kleinen Arrays. Wenn's größer wird, ist's mit Sets wahrscheinlich wesentlich schneller. Außerdem unterscheidet sich die Anzahl, sofern Worte mehrfach vorkommen. Schnittmenge heißt ja distinkt. Daher fällt die Array-Möglichkeit eigentlich weg.

Ich würde's wahrscheinlich so machen:

final Set<String> schnittMenge = new HashSet<String>(Arrays.asList(array0));
schnittMenge.retainAll(Arrays.asList(array1));

Test mit array0=4000, array1=10000 Zufalls-Strings, 900 überschneidungen:

First test: two loops
	... took 1158ms
Second test: HashSet retain all
	... took 450ms
Third test: TreeSet retain all
	... took 452ms

Ebenius

 

[Marco13]

oder eben zwei Schleifen (vmtl. deutlich effizienter)

Nur bei kleinen Arrays. Wenn's größer wird, ist's mit Sets wahrscheinlich wesentlich schneller.

Wär' nicht schlecht wenn mir jetzt spontan eine tolle Ausrede dafür einfallen würde, dass ich O(n^2) als potentiell effizienter als O(n) bezeichnet habe....

 

[0x7F800000]

aja, für alle n aus (0,1) trifft's schon zu^^

 

[Ebenius]

Wär' nicht schlecht wenn mir jetzt spontan eine tolle Ausrede dafür einfallen würde, dass ich O(n^2) als potentiell effizienter als O(n) bezeichnet habe....

Kein Problem, ich helf Dir! Effizienter... Mal sehen... Das ist doch abhängig von der Perspektive. Zum Beispiel ist der Schleifenansatz effizienter, weil er

• weniger API-Wissen voraussetzt, wodurch man kostbare Entwicklungszeit spart die man zum Lernen verbraten müsste,
• keinen weiteren Speicher auf dem Heap belegt und
• nicht so viele spitze Klammern verschwendet.

BTW: Wenn Du die Schleifen mit break aufbaust, dann sparst Du in meinem Test oben fast 300ms. Immerhin was:

int count = 0;
for (String s0 : array0) {
  for (String s1 : array1) {
    if (s0.equals(s1)) {
      count++;
      break;
    }
  }
}

Ebenius

 

[Ebenius]

In meinem Test oben... Wenn Du in die Schleifenlösung den Hash-Code einbeziehst, dann wird's rasant:

for (String s0 : array0) {
  for (String s1 : array1) {
    if (s0.hashCode() == s1.hashCode() && s0.equals(s1)) {
      count++;
      break;
    }
  }
}

Ergebnis:

First test: two loops
	... took 248ms
Second test: hash set retain all
	... took 539ms
Second test: tree set retain all
	... took 535ms

Ich hab die Testwerte verändert (von der Hälfte bis zum Achtfachen jedes oben angebenen Wertes hab ich getestet), das Verhältnis der Zeiten bleibt so ähnlich. Also - die Schleifen sind mit Hash-Code wesentlich schneller als die Sets, wenn man den Hash-Code in der Schleife nimmt. Hätte ich nicht mal ansatzweise gedacht...

// Nachtrag: Hängt allerdings arg von den Daten ab, die in den Arrays liegen. Komme auch öfter auf deutlich umgekehrte Ergebnisse. Ich würde noch immer die HashSet-Lösung nehmen. Wahrscheinlich müsste ich mich jetzt mit ner sinnvollen Belegung der Daten beschäftigen. Das lasse ich mal.

Ebenius

 

[Marco13]

Ja, bei kleinen Arrays ist die Array-Lösung effizienter weil eben keine neuen Objekte angelegt werden müssen (und die Daten nicht in die HashSet kopiert werden müssen). Bei größeren Arrays kehrt sich das sehr schnell um (deswegen ja auch immer die asymptotische Laufzeitangabe...).

Sieht man sehr schön bei diesem Programm: Das plottet mal die zeitlichen Verläufe für Arraygrößen 1 bis 50. Am Anfang sind die Loop-Lösungen schneller, aber weil die Set-Lösung nur O(n) ist, und die loop-Lösungen O(n^2), "überholt" die Set-Lösung (rot) die Loop-Lösungen schon bei Arrays der Größe 25...

import java.util.*;
import java.util.List;
import javax.swing.*;
import java.awt.*;

class TimePlot extends JPanel
{
    float max = -1;
    List<List<Float>> lists = null;

    public TimePlot(List<List<Float>> lists)
    {
        this.lists = lists;

        for (List<Float> list : lists)
        {
            for (Float n : list)
            {
                max = Math.max(max, n);
            }
        }
    }

    public void paintComponent(Graphics g)
    {
        super.paintComponent(g);

        for (int j=0; j<lists.size(); j++)
        {
            List<Float> list = lists.get(j);
            switch (j)
            {
                case 0: g.setColor(Color.RED); break;
                case 1: g.setColor(Color.GREEN); break;
                case 2: g.setColor(Color.BLUE); break;
            }
            for (int i=1; i<list.size(); i++)
            {
                float scaleX = (float)getWidth() / list.size();
                float scaleY = (float)getHeight() / max;
                int x0 = (int)((i-1) * scaleX);
                int y0 = (int)(list.get(i-1) * scaleY);
                int x1 = (int)(i * scaleX);
                int y1 = (int)(list.get(i) * scaleY);
                g.drawLine(x0, getHeight()-y0, x1, getHeight()-y1);

                System.out.println("list at "+i+" has "+list.get(i)+" y "+y1);
            }
        }
    }
}


class Plotter extends JFrame
{
    public Plotter(List<Float> ... lists)
    {
        setSize(500,500);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        getContentPane().add(new TimePlot(Arrays.asList(lists)));
    }
}



class ArrayIntersectionTest
{
    private static String array0[];
    private static String array1[];

    public static void main(String args[])
    {
        List<Float> timesS = new ArrayList<Float>();
        List<Float> timesL = new ArrayList<Float>();
        List<Float> timesH = new ArrayList<Float>();

        for (int size=1; size<=50; size+=1)
        {
            array0 = createInput(size, 50);
            array1 = createInput(size, 50);
            for (int i=0; i<100; i++)
            {
                int index = (int)(Math.random()*array0.length);
                array0[index] = array1[index];
            }
            int runs = 500000 / size;
            System.out.println("Size "+size);
            timesS.add((float)testSet(runs) / runs);
            timesL.add((float)testLoop(runs) / runs);
            timesH.add((float)testLoopWithHashCode(runs) / runs);
        }

        new Plotter(timesS, timesL, timesH).setVisible(true);
    }

    private static String[] createInput(int size, int len)
    {
        Set<String> s = new HashSet<String>();
        while (s.size() < size)
        {
            s.add(createRandomString(len));
        }
        return (String[])s.toArray(new String[s.size()]);
    }

    private static String createRandomString(int len)
    {
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<len; i++)
        {
            sb.append('A'+(char)(Math.random()*('Z'-'A')));
        }
        return sb.toString();
    }





    private static long testSet(int n)
    {
        long before = System.currentTimeMillis();
        int result = 0;
        for (int i=0; i<n; i++)
        {
            result += set();
        }
        long after = System.currentTimeMillis();
        System.out.println(result+" set              "+(after-before));
        return (after-before);
    }

    private static long testLoop(int n)
    {
        long before = System.currentTimeMillis();
        int result = 0;
        for (int i=0; i<n; i++)
        {
            result += loop();
        }
        long after = System.currentTimeMillis();
        System.out.println(result+" loop             "+(after-before));
        return (after-before);
    }

    private static long testLoopWithHashCode(int n)
    {
        long before = System.currentTimeMillis();
        int result = 0;
        for (int i=0; i<n; i++)
        {
            result += loopWithHashcode();
        }
        long after = System.currentTimeMillis();
        System.out.println(result+" loopWithHashcode "+(after-before));
        return (after-before);
    }


    private static int set()
    {
        Set<String> s0 = new HashSet<String>(Arrays.asList(array0));
        Set<String> s1 = new HashSet<String>(Arrays.asList(array1));
        s1.retainAll(s0);
        return s1.size();
    }

    private static int loopWithHashcode()
    {
        int count = 0;
        for (String s0 : array0)
        {
            for (String s1 : array1)
            {
                if (s0.hashCode() == s1.hashCode() && s0.equals(s1))
                {
                    count++;
                    break;
                }
            }
        }
        return count;
    }

    private static int loop()
    {
        int count = 0;
        for (String s0 : array0)
        {
            for (String s1 : array1)
            {
                if (s0.equals(s1))
                {
                    count++;
                    break;
                }
            }
        }
        return count;
    }


}

 

[André Uhres]

wie viele Wörter sie gemeinsam haben

Hier ist eine einfache "Merge" Lösung:

import java.util.*;
import javax.swing.*;
public class MergeDemo {
    String[] wordlistA = {"java", "is", "a", "good", "developing", "language", "is", "it", "not"};
    String[] wordlistB = {"java", "is", "a", "good", "programming", "language", "it", "is", "indeed"};
    private int indexA,  indexB,  count;
    private String wordA,  wordB,  word;
    private boolean countDuplicates;
    public MergeDemo() {
        int opt = JOptionPane.showConfirmDialog(null, "Count Duplicates?");
        countDuplicates = opt == JOptionPane.YES_OPTION ? true : false;
        Arrays.sort(wordlistA);
        Arrays.sort(wordlistB);
        indexA = -1;
        indexB = -1;
        wordA = nextA();
        wordB = nextB();
        while (wordA.startsWith("0") && wordB.startsWith("0")) {
            int compareValue = wordA.compareTo(wordB);
            if (compareValue == 0) {//equal
                word = wordA;
                count++;
                wordA = nextA();
                wordB = nextB();
                if (!countDuplicates) {
                    while (wordA.equals(word)) {
                        wordA = nextA();
                    }
                    while (wordB.equals(word)) {
                        wordB = nextB();
                    }
                }
            } else if (compareValue < 0) {
                wordA = nextA();
            } else {
                wordB = nextB();
            }
        }
        JOptionPane.showMessageDialog(null, "count: " + count);
    }
    private String nextA() {
        if (++indexA < wordlistA.length) {
            return "0" + wordlistA[indexA];
        }
        return "1";
    }
    private String nextB() {
        if (++indexB < wordlistB.length) {
            return "0" + wordlistB[indexB];
        }
        return "1";
    }
    public static void main(final String[] args) {
        new MergeDemo();
    }
}