Zwei gleiche Eintraege in ArrayList finden

[mindjo]

Hallo!

Also ich lese in meinem Programm eine Datei ein, welche pro Zeile 1 Buchstabe und 3 Zahlen enthaelt, jeweils abgetrennt von einem \t (tab), also z.B.

A 1 3 4
B 2 5 2
A 4 0 9
........

So ich muss nun in meinem Programm jede A und jede B Zeile zusammenfuegen, wenn die erste Zahl uebereinstimmt, also wuerde z.B. sowas zusammgengefuegt werden:

A 1 3 5
B 2 2 1
B 1 9 6

--> gemerged wird (A 1 3 5) und (B 1 9 6) zu: AB 1 3 5 9 6

Also ich lese erst mal die zeilen ein, und teile diese in zweii Arraylists
--> ArrayLists sind aber Laufzeit ineffizient, was kann ich da sonst benutzen? Oder irgendwas statt dem array int[]?

 BufferedReader read = new BufferedReader(new FileReader(filePath));
ArrayList<int[]> allA = new ArrayList<int[]>();
ArrayList<int[]> allB = new ArrayList<int[]>();

String s = null;

                while ((s = read.readLine()) != null) {

                    if (s.contains("A")) {
                 String[] part = s.split("\t");

                        int[] line = new int[3];
//parts[0] ist ja das A oder B
                        line[0] = Integer.parseInt(parts[1]); 
                        line[1] = Integer.parseInt(parts[2]); 
                        line[2] = Integer.parseInt(parts[3]); 
allA.add(line);

                    } else if (s.contains("B")) {

int[] line = new int[3];
//parts[0] ist ja das A oder B
                        line[0] = Integer.parseInt(parts[1]); 
                        line[1] = Integer.parseInt(parts[2]); 
                        line[2] = Integer.parseInt(parts[3]); 
allB.add(line);


                   }
                }

So und nun muss ich ja gleiche eintraege finden, hier habe ich jedoch gar keine idee :S. Das einzige, was mir spontan eingefallen ist, ist eine zweifache Schleife und alles miteinander zu vergleichen, also quasi:

for (int i =0; i < allA.size();i++) {

for (int j =0; j < allB.size();j++) {

 if (allA.get(i)[0] == allB.get(j)[0]) {

//merge them
// und jetzt aus array loeschen :S
}


}

}

jedoch ist das ja sehr ineffizient, vorallem dass ich dann einen Eintrag im array ersetzen muesste, und dann aus dem ASrray was loeschen waehrend ich noch darueber iteriere :S

aber das groesste problem ist die ineffizienz, alles miteinander zu vergleichen

 

[geqoo]

Ich frage mich dabei erstmal: Was genau willst du finden?
Geht es etwa nur darum, gleiche Zeilen zu finden?

 

[Gucky]

Da ja erstmal keine weiteren Einträge hinzukommen könntest du entweder erst alle A und B Zeilen in je eine ArrayList einlesen und danach das Ganze in je ein Array verwandeln oder du iterierst erst einmal über die Datei und zählst die A und B Zeilen und machst dann anhand des Ergebnisses die Arrays.

Aber Das Ganze mit int zu machen halte ich für unnötig schwer. Viel einfacher wäre es das Ganze mit Strings zu machen und dann die

[URL="http://openbook.galileocomputing.de/javainsel9/javainsel_04_002.htm#mj5ee730cda1f64998edf27bd440d36bf1"]startsWith()[/URL]

-Methode zu nehmen.

Gruß
Gucky

 

[mindjo]

Hmm oke, also sind Arrays doch effizienter als arraylists?

Und das mit dem Strings es zu machen, da verstehe ich dich nicht :S

Wenn ich die Zeile als String speicher, habe iich ja sowas wie

A 1 3 4 5;

Aber ich muss ja ueber die erste Zahl mergen... also startsWith hilft mir nur bei dem Anfang ob da ein A oder B steht

 

[mindjo]

@gegoo

Nicht genau zwei zeilen, sondern zeilen mit jeweils einen gleichen eintrag. aber ich denke, dass ich dass anhand meines beispiels schon anschaulich erklaert habe was ich will

 

[Gucky]

Du kannst auch

startsWith("A 1")

schreiben. Oder die ersten beiden Indizes entfernen mit der

[URL="http://openbook.galileocomputing.de/javainsel9/javainsel_04_002.htm#mjc6bf6272c679c8daa6715a7e8985f1c6"]substring()[/URL]

-Methode-Methode.

 

[kaoZ]

schon mal mit

.equals()

versucht ?

natürlich auf Strings, aber das sollte ja eigentlich kein problem sein.

 

[hacke78]

int[] a1 = {4,2,3};
		int[] a2 = {1,2,3};
		ArrayList<int[]> allA = new ArrayList<int[]>();
		allA.add(a1);
		allA.add(a2);
		System.out.println(allA.get(0)[0]);
		Collections.sort(allA, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});
		System.out.println(allA.get(0)[0]);

Das angewendet auf deine beiden Listen sortiert dir in nlogn beide.
Dann solltest du in linearer Laufzeit deine Listen durchiterieren:

int i = 0;
int j = 0;

Sry muss weg, Kollgin steht vor der Tür, kann dir das iterieren nicht präsentieren. Aber Idee noch kurz:
mit i durch allA, mit j durch allB, wenn allA(i).get(0)<allB(j).get(0) i++, bei > j++ und bei gleichheit denke ich i++ und j++ und einen Merge... irgendwie so, die Richtung stimmt, obiges Sortieren funktioniert auf jeden Fall.
Beim Merge willst du glaube ich wie du gepostet hast, keine doppelten Elemente:

HashSet hs = new HashSet();
hs.addall(allA);
hs.addall(allb);
ArrayList result = new ArrayList();
result.addAll(hs);

Tut mir echt leid fürs geschlampe hier unten, aber ich bin überfällig und muss weg

 

[kaoZ]

Sowas in der Art , zumindest schonmal als Lösungsansatz:

package versuche;

import java.util.ArrayList;

public class Check {

	ArrayList<String> listA;
	ArrayList<String> listB;
	
	public static void main(String[] args) {
	
		new Check().create();
		

	}
	public void create()
	{
		listA = new ArrayList<String>();
		listB = new ArrayList<String>();
		
		listA.add("eins");
		listB.add("zwei");
		check();
	}
	public void check()
	{
		 for (int x = 0; x < listA.size(); x++ )
         {
             for (int y = 0; y < listB.size(); y++)
             {
                 if (listA.get(x).equalsIgnoreCase(listB.get(y)))
                 {
                	 System.out.println("Bedingung ist wahr"); // oder dein Code
                 }
                 else
                 {

                	 System.out.println("Bedingung ist falsch"); // oder dein Code
                 }
             }
         }
	}
	
}

[EDIT]
Da in diesem Fall die Einträge der listeA nicht mit dem der ListeB übereinstimmen ergibt es false

hätte man jetzt

listA.add("eins");
listB.add("eins");

wäre der test der Strings true
[/EDIT]

 

[mindjo]

@kaoZ

Das ist genau die Loesung, die ich auch hatte, jedoch wegen angegeben Gruenden lieber umgehen wollte.

@hacke78

Ich verstehe nur hier nicht, wieso du erst ein sortieren machst, bevor das mergen kommt?


Und das verwenden vom HashSet hier ist mir auch iwie unklar :S

 

[kaoZ]

ahh, mein Fehler hatte ich überlesen :rtfm:

 

[stg]

@hacke78

Ich verstehe nur hier nicht, wieso du erst ein sortieren machst, bevor das mergen kommt?

Und das verwenden vom HashSet hier ist mir auch iwie unklar

Er sortiert in quasi-linearer Zeit, damit du anschließend in linearer Zeit alle Einträge vergleichen kannst (du musst du einmal durch die Liste laufen und jeweils benachbarte Paare vergleichen). Der Gesamtaufwand bleibt damit quasi-linear (die Hauptarbeit ist das Sortieren). Bei dem anderen Ansatz hast du bereits quadratische Laufzeit, wenn du naiv jedes Element mit jedem anderen vergleichst.

Über den Umweg über das HashSet werden doppelte Einträge rausgeschmissen.

Zum Problem selbst will ich gar nichts weiter sagen, da mir ehrlich gesagt viel zu unklar bleibt, was du tatsächlich _genau_ machen willst.

 

[DrZoidberg]

Sollst du jeweils zwei Zeilen mergen?

Wie würde das Resultat für dieses Beispiel aussehen?

A 1 3 5
B 2 2 1
B 1 9 6
A 1 8 9
B 3 5 6
B 1 5 2

So?
AB 1 3 5 6 9
AB 1 2 5 8 9
B 2 2 1
B 3 5 6

Oder so?
AB 1 2 3 5 6 8 9
B 2 2 1
B 3 5 6

 

[mindjo]

Ah okeeee.. jetzt verstehe ich was du meinst.

Ja ich denke, dass mir das auf jeden Fall weiterhilft. Vielen Dank

 

[hacke78]

Ich sortiere aus folgenden Grund:
Dein "Bruteforceansatz" hat eine assymtotische Laufzeit von n^2.
Du hast schon richtig erkannt, dass hier (je nach Größe deiner Listen) Performanceproblem vorliegt.

Wenn du sortierst, Sortieralgorthmen haben im Regelfall eine Laufzeit von nLogn, kannst du danach in linearer Zeit megen und damit ist deine Gesamtlaufzeit durch nLogn begrenzt. Das ist im Nano/Millisekundenbereich schon bemerkbar bei n=1000, und bei Miogröße von n schon richtig deftig.

Edit : wurde auch schon so beantwortet von stg, wobei ich meines Wissenstandes bei Quasilinearer Laufzeit durch Sortieren wiedersprechen muss. Hier sollte die untere Grenze doch bei nLogn liegen.

 

[stg]

Edit : wurde auch schon so beantwortet von stg, wobei ich meines Wissenstandes bei Quasilinearer Laufzeit durch Sortieren wiedersprechen muss. Hier sollte die untere Grenze doch bei nLogn liegen.

Das liegt wohl nur daran, dass dir die bedeutung von "quasilinear" im Zusammenhang mit der Zeitkomplexität nicht geläufig ist. Natürlich ist nlog(n) untere Schranke für jeden Sortieralgorithmus, aber genau das wird damit bezeichnet. Sogar noch ein bisschen allgemeiner all solche Algorithmen, die in n(log(n)^k) laufen. Quasilinear deshalb, weil n(log(n)^k) immer noch schneller ist, als jedes Polynom in n mit Exponent größer als 1.

Nachzulesen z.B. hier Time complexity - Wikipedia, the free encyclopedia