[Threads]: Mit mehreren Threads 1 ArrayList durchlaufen

[Guest]

Hallo,

ich habe derzeit teilweise recht große Listen die ich durchlaufe und einige Objekte entsprechend von verschiedenen Kriterien aus der Liste schmeisse. Ich würde das ganze gern ein wenig beschleunigen (bzw. schauen ob es schneller wird) in dem ich mit 2 oder mehreren (vllt. max. 5) Threads gleichzeitig eine Liste durchlaufe und wenn jeder Thread fertig ist diese dann an das Programm zurückgegeben wird.

Einfach ausgedrückt:

Gib Liste an Methode und warte => Durchlaufe Liste in X Threads => Wenn fertig durchlaufen, gebe Liste zurück und weiter

Hat da jmd. vllt mal ein Beispiel? I wie weiss ich nicht so recht wie das ganze aussehen muss wenn man mit mehreren Threads in einer Methode auf eine Liste zugreift :-(

Danke!

 

[maki]

Klar geht das, nur dürfen die Threads nicht die Liste ändern sonst gibt's Ärger.

 

[tfa]

Die sinnvolle maximale Anzahl Threads bekommst du mit Runtime.availableProcessors().

 

[Guest]

Klar geht das, nur dürfen die Threads nicht die Liste ändern sonst gibt's Ärger.

Öhh abe rich will ja Elemente entfernen ...

@tfa: Hmm okay ...

Jetzt müsste ich nur noch wissen wie das ganze auszusehen hat mit mehreren Threads auf eine Liste drauf zu gehen

 

[maki]

Öhh abe rich will ja Elemente entfernen ... icon_wink.gif

Das geht nicht.

Vielleicht gibt es noch eine andere Möglichekit die Sache zu beschleunigen.

Verwendest du LinkedList oder ArrayList?
Bei vielen remove/insert Operationen ist erstere um einiges schneller als letztere, allerdings solltest du nicht versuchen mit get(i) oder anderen Indexbasierten Operation auf eine LinkedList zuzugreifen, mit einem (List-)Iterator ist es am schnellsten.

 

[Guest]

Benutze ArrayList, werde es aber mal mit einer LinkedList ausprobieren.

Wenn das mit dem löschen nicht geht eben der andere Weg:
Ich durchlaufe eine Liste und immer wenn ein Element auf mein Kriterium passt bzw. eben nicht, stopfe ich es in eine neue Liste, das sollte doch eigtl. funktionieren oder?

 

[maki]

Wie gesagt, es kommt auf die Anwednung an...

Wie iterierst du über deine Liste?

 

[Guest]

Wie iterierst du über deine Liste?

for (Iterator lIterator = pList.iterator(); lIterator.hasNext()
{
// mache Kram
}

Eigtl. so ... Aber genau DAS ist mein Problem, ich weiss nicht wie ich mit mehreren Threads über eine Liste iterieren kann

 

[maki]

Wie gesagt, mehrere Threads helfen dir NICHT.

So wie du über die Liste iterierst ist es gut, wenn du deine Referenzen als List deklariert hast, zB:

List pList = new ArrayList();

Musst du nur noch ArrayList durch LinkedList austauschen und dann weisst du ob dir das hilft.

Wenn du allerdings (entgegen aller Empfehlungen) die Referenz mit der Implmentierung anstatt des Interfaces angelegt hast zB:

ArrayList pList = new ArrayList();

.. hast du natürlich mehr Aufwand, aber das sollte man sowieso nicht machen.

 

[Gast]

macht kaum einen merklichen unterschied wenn ich das ArrayList gegen LinkedList austausche.

Warum würde es nicht schneller gehen wen nich mit mehreren Threads über eine Liste iteriere OHNE etwas an der Liste zu ändern?

 

[maki]

Woher weisst du denn dass das iterieren solange dauert?
Schon mal einen Profiler angschmissen oder ist das deine Vermutung (=geraten)?

Denke an die 80/20 Regel.

 

[Guest]

Woher weisst du denn dass das iterieren solange dauert?
Schon mal einen Profiler angschmissen oder ist das deine Vermutung (=geraten)?

Denke an die 80/20 Regel.

das ist relativ einfach. wen nich die methode die durch die liste iteriert auskommentiere sehe ich meine daten sofort in der gui, wenn ich durchiteriere dauert es im moment ~10 sekunden ...

 

[maki]

Das ist geraten

Solltest schon rausfinden was genau so lange dauert (wirst ja mehr mehr machen als nur durchiterieren), diese Frage kann nur ein Profiler beantworten.

Alles andere wäre Quatsch.

 

[Guest]

(wirst ja mehr mehr machen als nur durchiterieren)

ich filtere die daten nach bestimmten werten und das ist logischerweise auch das was so lange dauert.
Aus diesem Grunde möchte ich ja diesen Teil in Threads auslagen um vllt. nochmal 3-4 Sekunden oder dergleichen gut zu machen.

Kann mir denn nun niemand sagen wie ich mit mehrerenb Threads auf eine Liste / einen Iterator zugreife?!

 

[Gast]

Hab jetzt gesehen, dass ein ListIterator auch Objekte löschen kann, soviel also dazu ...

Kann mir sonst allerdings niemand sagen wie ich mit mehreren Threads gleichzeitig auf einen Iterator gehen kann?

 

[maki]

Hab jetzt gesehen, dass ein ListIterator auch Objekte löschen kann, soviel also dazu ...

Dann lies mal genau was passiert wenn das mehrere Threads gleichzeitig machen...

 

[Guest]

Wenn ich endlich wissen würde wie 2 Threads gemeinsam auf einen Iterator zugreifen würd ichs wohl sogar sehen. Sorry fürs bisschen meckern, aber iwie vermiss ich immer noch eine Antowrt auf meine eigtl. Frage

 

[maki]

Was ist denn deine konkrete Frage?

Ansonsten kann man nur wage antworten:
2 Threads erstellen und beide auf einen Iterator losschicken, die ConcurrentModificationException sehen und eine andere Lösung suchen...

Wie weit hast du denn den Code schon geschrieben?

 

[SchonWiederFred]

Mehrere Threads, die auf dieselbe Datenstruktur zugreifen? Keine gute Idee. Du sagst, Du hast mehrere Listen. Lass doch jeden Thread seine eigene Liste bearbeiten, das könnte was bringen.

Vielleicht ist Dein Flaschenhals ja gar nicht das Iterieren an sich, sondern das Löschen? remove auf einer ArrayList ist ja nicht gerade schnell. Hast Du mal den Ansatz verfolgt, aus der alten Liste nur diejenigen Elemente in eine neue Liste zu übernehmen, die Deinen Kriterien entsprechen?

class Beispiel
{
	private static List<String> filter(List<String> list)
	{
		List<String> result = new ArrayList<String>();
		for (String s: list)
		{
			if (s.length() >= 5)
				result.add(s);
		}
		return result;
	}

	public static void main(String[] args)
	{
		List<String> list = new ArrayList<String>();
		list.add("1");
		list.add("12");
		list.add("123");
		list.add("1234");
		list.add("12345");
		list.add("123456");
		list.add("1234567");
		list.add("12345678");
		list.add("123456789");
		System.out.println(list.size());
		list = filter(list);
		System.out.println(list.size());
	}
}

 

[SchonWiederFred]

Das Filtern kann man natürlich auch schön generisch und wiederverwendbar machen:

interface Filter<E>
{
	boolean keep(E e);
}

class Beispiel
{
	public static <E> List<E> filter(List<? extends E> list, Filter<? super E> filter)
	{
		List<E> result = new ArrayList<E>();
		for (E e: list)
			if (filter.keep(e)) result.add(e);
		return result;
	}

	public static void main(String[] args)
	{
		List<String> list = new ArrayList<String>();
		list.add("1");
		list.add("12");
		list.add("123");
		list.add("1234");
		list.add("12345");
		list.add("123456");
		list.add("1234567");
		list.add("12345678");
		list.add("123456789");
		System.out.println(list.size());
		list = filter(list, new Filter<String>()
		{
			public boolean keep(String e)
			{
				return e.length() >= 5;
			}
		});
		System.out.println(list.size());
	}
}