Sortieren von Liste zu unperformant

Don83

Bekanntes Mitglied
Hallo liebe Leut,

ich möchte gerne zwei Listen paralell Sortieren. Die Listen beinhalten Werte und IDs(Strings). Die Werte sollen numerisch Sortiert werden, und die IDs die im Index übereinstimmen sollen sozusagen so sortiert werden dass nach sortieren der Werte die Indexe von IDs und Werten immernoch übereinstimmen.

Ich habe das ganze wie folgend über den bubblesort gemacht:
Java:
// BUBBLESORT
		boolean unsortiert = true;
		double temp;
		String temp2;
		System.out.print("Sorting Weights ...");
		while (unsortiert) {
			unsortiert = false;
			for (int i = 0; i < values.size() - 1; i++)
				if (values.get(i) < values.get(i + 1)) {
					temp = values.get(i);
					values.set(i, values.get(i + 1));
					values.set(i + 1, temp);

					temp2 = keys.get(i);
					keys.set(i, keys.get(i + 1));
					keys.set(i + 1, temp2);
					unsortiert = true;
				}
		}
		System.out.println("Done!");
Auf 50000 Listeneinträgen dauert dass schon eine Weile. Ca. 2-3 Minnuten. Allerdings will ich eine Liste von 3Mio Einträgen sortieren. Dort habe ich nach ca. 8 Stunden sortieren abgebrochen. Gibt es da eventuell in Java vorgefertigte Performante Lösungen die Listen sortieren können. Ich kenne Collections.sort(Liste), aber das funktioniert ja leider nur auf einer Liste und nicht auf zwei Listen paralell.

Zudem, gibt es eine Möglichkeit über VM Kommandos mehr als nur einen Kern zu nutzen? Im Moment verwendet das Programm nur einen Kern.
 

Landei

Top Contributor
Dann würde ich dir vorschlagen, auch eine Liste zu nehmen. Schreibe dir eine kleine Wrapper-Klasse, die ID und Wert aufnimmt, schreibe dir einen Comparator für diesen Wrapper, und benutze Collections.sort(list, comparator). Wenn die beiden Listen sowieso immer "parallel" geändert werden sollen, wirst du sonst nicht glücklich.

Als Alternative könnte man bei solchen Größenordnungen auch eine Datenbank (eventuell in-memory) ins Auge fassen.
 

kaetzacoatl

Bekanntes Mitglied
Eine Klasse programmieren die beide Attribut enthält und dann sortieren.
z.B.:
Java:
import java.util.ArrayList;
import java.util.Collections;

public class E implements Comparable<E>  {
	
	double d;
	String str;

	public E(double d, String str) {
		this.d = d;
		this.str = str;
	}

	@Override
	public int compareTo(E arg0) {
		return Double.valueOf(d).compareTo(arg0.d);
	}
	
	public static void sort(ArrayList<Double> ds, ArrayList<String> strs){
		ArrayList<E> list = new ArrayList<E>();
		for(int i = 0;i < ds.size();i++){
			list.add(new E(ds.get(i),strs.get(i)));
		}
		Collections.sort(list);
		ds.clear();
		strs.clear();
		for(int i = 0;i < list.size();i++){
			ds.add(list.get(i).d);
			strs.add(list.get(i).str);
		}
	}

}
EDIT: Da war wohl einer schneller:(
 

ARadauer

Top Contributor
die IDs die im Index übereinstimmen sollen sozusagen so sortiert werden dass nach sortieren der Werte die Indexe von IDs und Werten immernoch übereinstimmen.
versteh ich nicht...

man kann sich ja auch eine eigenschaft ins objekt (oder in einen wrapper) geben zu welcher liste das objekt gehört und nachher wieder trennen...
 

JCODA

Top Contributor
Ich kann zwar nicht sagen, ob das der richtige Weg ist um 3 Mio Einträge zu sortieren, aber generell würde ich so etwas mit einem Hilfsobjekt machen:


Java:
public class Pair implements Comparable<Pair> {

	private Key key;
	private Value value;
	
	public Pair(Key key, Value value) {
		this.key = key;
		this.value = value;
	}

	

	@Override
	public int compareTo(Pair oth) {
		return this.value.compareTo(oth.value);
	}

}

Schon dran gedacht, das Sortieren einer Datenbank zu überlassen?
 

Fant

Bekanntes Mitglied
Mal ganz unabhängig von den bisherigen Antworten ist Bubblesort auch einfach ungeeignet um solch große Datenmengen zu sortieren. Da solltest du besser einen Quicksort durchführen.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
L allgemein Strings händisch in Liste sortieren Allgemeine Java-Themen 47
Curtis_MC Collections Liste anhand mehrere Kriterien sortieren Allgemeine Java-Themen 6
G Liste (UsageStats) sortieren (Android) Allgemeine Java-Themen 5
S Verkettete (Teil)Liste sortieren ( rekursiv bis n) Allgemeine Java-Themen 2
H Liste sortieren anhand optionalem Property Allgemeine Java-Themen 3
H Liste von Objekten generisch sortieren Allgemeine Java-Themen 0
Gossi Collections (Unbekannte) Liste Sortieren Allgemeine Java-Themen 10
T Liste mit GregorianCalendar-Objekten in List einlesen, mit Collection sortieren und ausgeben Allgemeine Java-Themen 3
T Liste sortieren Allgemeine Java-Themen 6
F Doppelt verkettete Liste sortieren? Allgemeine Java-Themen 8
B Sortieren einer Liste Allgemeine Java-Themen 5
C Sortieren und Selektieren einer ArrayList<Point3D> Allgemeine Java-Themen 6
K Verbesserung der Laufzeit beim Sortieren von Einwohnern nach ihrem Geburtsjahr Allgemeine Java-Themen 0
Willi.We Array sortieren Allgemeine Java-Themen 5
L ArrayList sortieren Allgemeine Java-Themen 2
Monokuma String List nach Zahlen und Worten sortieren Allgemeine Java-Themen 9
MiMa ArrayList sortieren?? Allgemeine Java-Themen 5
C MySQL Tabellen sortieren. Allgemeine Java-Themen 33
B Java Mail: Emails sortieren? Allgemeine Java-Themen 5
FRI3ND Datentypen Date-Array sortieren - Text mitnehmen? Allgemeine Java-Themen 7
P Wertepaare sortieren Allgemeine Java-Themen 3
MiMa Sortieren nach Stellenangaben Allgemeine Java-Themen 7
T Collections ArrayList Sortieren Allgemeine Java-Themen 4
P Listen sortieren Allgemeine Java-Themen 1
U Methoden Algorithmus MergeSort String [ ] array sortieren programmieren Allgemeine Java-Themen 17
K Strings sortieren: 2 Kritieren Allgemeine Java-Themen 5
B Algortihmus zum linearen Sortieren Allgemeine Java-Themen 1
K ArrayList sortieren Allgemeine Java-Themen 16
heyluigi Random Integer Array Ausgabe nach Größe sortieren Allgemeine Java-Themen 6
2 Mehrere Uhrzeiten Sortieren Allgemeine Java-Themen 2
B Counting Sort (Sortieren durch Zählen) Allgemeine Java-Themen 13
Bluedaishi String Array mit Datum und Uhrzeit String sortieren Allgemeine Java-Themen 6
K Sortieren nach Vorgabe Allgemeine Java-Themen 6
S Erste Schritte Arrayliste alphabetisch sortieren mit Eingabe Allgemeine Java-Themen 9
L Sortieren von "Map<String, Object>" Allgemeine Java-Themen 2
M Sortieren und Leerzeichen Allgemeine Java-Themen 11
W Array Indizes sortieren Allgemeine Java-Themen 16
E Array alphabetisch sortieren Allgemeine Java-Themen 1
5 Objekte Sortieren lassen Allgemeine Java-Themen 7
P Beim sortieren nullpointerexception Allgemeine Java-Themen 12
G Map nach key sortieren Allgemeine Java-Themen 14
T Array Sortieren (null Werte ans Ende) Allgemeine Java-Themen 2
S Int Values sortieren Allgemeine Java-Themen 7
S Sortieren nach Objekten Allgemeine Java-Themen 13
A 2D-array problem (sortieren) Allgemeine Java-Themen 6
D priority queue sortieren Allgemeine Java-Themen 10
G List<Person> sortieren Allgemeine Java-Themen 6
K Hashmap sortieren Allgemeine Java-Themen 6
H Problem beim Sortieren einer HashMap mit TreeSet Allgemeine Java-Themen 4
M ArrayList<String>, String häufigkeit sortieren Allgemeine Java-Themen 4
J Wie sortieren? Allgemeine Java-Themen 11
K Strings sortieren (knifflig) Allgemeine Java-Themen 7
B JTable nach Icon sortieren Allgemeine Java-Themen 6
C ArrayList (mit Objekten) sortieren Allgemeine Java-Themen 12
J Map nach value sortieren Allgemeine Java-Themen 14
N Zahlen in Strings einer ArrayList sortieren Allgemeine Java-Themen 14
V ArrayList sortieren Allgemeine Java-Themen 7
S String-Array nach Datum sortieren Allgemeine Java-Themen 10
Developer_X Ein Array nach einem bestimmten Attribut sortieren Allgemeine Java-Themen 3
B Sortieren mit generischen Datentypen Allgemeine Java-Themen 3
C ArrayList anhand von zwei Attributen sortieren Allgemeine Java-Themen 4
O Sortieren von Telefonnummern Allgemeine Java-Themen 8
D JTabel sortieren nach mehreren kriterien Allgemeine Java-Themen 3
G Verschachtelte Treemaps, nach Value sortieren Allgemeine Java-Themen 11
K ArrayList nach bestimmtem Muster sortieren Allgemeine Java-Themen 3
I Vector mit Objekten sortieren,Videos mit JMF wiedergeben Allgemeine Java-Themen 6
S Koordinatentupel-Map sortieren?? Allgemeine Java-Themen 16
C ArrayList sortieren (mehrere Kriterien) Allgemeine Java-Themen 6
G ArrayList mit quicksort sortieren Allgemeine Java-Themen 9
Spot84 Vector nach Ressourcetyp sortieren Allgemeine Java-Themen 4
G sortieren von generics Allgemeine Java-Themen 10
Z Als Final deklarierte Klasse im Array sortieren Allgemeine Java-Themen 2
C ArrayList nach Datum sortieren Allgemeine Java-Themen 7
O ArrayList sortieren Allgemeine Java-Themen 8
G ArrayList mit Indices parallel sortieren Allgemeine Java-Themen 8
D HashMap sortieren Allgemeine Java-Themen 2
C Sortieren File[] Allgemeine Java-Themen 5
W [solved] Vector sortieren (Collection / Comparable?) Allgemeine Java-Themen 7
D LinkedList anhand einer long-Variable der Objekte sortieren Allgemeine Java-Themen 5
O Vektoren in Vektor sortieren aber mit Java 1.4 (!) Allgemeine Java-Themen 4
T TreeMap durch Comparator mit Generics sortieren Allgemeine Java-Themen 9
M ArrayList sortieren - HashMap mit sort_id vorhanden Allgemeine Java-Themen 2
A Sortieren mit Java Allgemeine Java-Themen 3
J Properties sortieren Allgemeine Java-Themen 6
T HashMap (String, Object(String , int)) nach int sortieren Allgemeine Java-Themen 7
E Bitte um Rat: Sortieren mit ArrayList Allgemeine Java-Themen 2
G Strings die Zahlen enthalten sinnvoll sortieren (A2 < A10 Allgemeine Java-Themen 4
G List mit selbstdefinierten Objekten sortieren Allgemeine Java-Themen 2
S ArrayList nach mehreren Spalten sortieren? Allgemeine Java-Themen 13
G Set absteigend Sortieren Allgemeine Java-Themen 6
B ein spezielles Byte-Array sortieren Allgemeine Java-Themen 11
D Sortieren? Allgemeine Java-Themen 13
N ArrayList sortieren Allgemeine Java-Themen 10
L Nach Häufigkeit sortieren Allgemeine Java-Themen 6
S Dten im Excel sortieren Allgemeine Java-Themen 5
Z Elemente in Vector nach Häufigkeit sortieren. Allgemeine Java-Themen 13
H Objekte Sortieren Allgemeine Java-Themen 4
F Kann man String[] sortieren? Allgemeine Java-Themen 2
H will einfach nicht sortieren! Allgemeine Java-Themen 23
T Collections/Arrays sortieren => ä, ö, ü, ß Groß/klein Allgemeine Java-Themen 3

Ähnliche Java Themen

Neue Themen


Oben