SuchEngine verschnellern

The_S · 16. Sep 2005

Hi,

ich programmiere gerade für mein Programm eine Suche. Meine Frage ist jetzt: wie kann ich die suche noch ein stückchen schneller machen? Zur Zeit brauche ich für 891 Dateien und 155 Ordner mit insgesamt 256 MB ca. zwischen 780 und 860 Millisekunden.

Code:

	void search(final File dir, final String search) {
		
		new Thread(new Runnable() {
			public void run() {
				File[] files = dir.listFiles();
				for (File file : files) {
					if (file.getName().equalsIgnoreCase(search)) {
						treffer.addElement(file); // treffer ist ein Vector
					}
					if (file.isDirectory()) {
						search(file, search);
					}
				}
				end = new GregorianCalendar();
			}
		}).start();
	}

Bleiglanz · 16. Sep 2005

allzuviel dürfte da nicht drin sein, du könntest von vektor auf ArrayList umsteigen und diese durchschleifen, so dass zu den Zugriff nicht synchronisieren musst (bringt aber wahrscheinlich nix)

und

das starten von threads kostet i.A. viel zeit, und du schmeisst für jedes Directory einen neuen thread an; vielleicht ist es schneller du startest nur einen, und in diesem dann eine rekursive funktion

The_S · 16. Sep 2005

Das mit den Threads hatte ich zu beginn auch nicht so, also alles in einem. Nur war es dann ein bisschen arg langsam! Zum vergleich

mit Threads durchschnittlich 810 Millisekunden

ohne Threads durchschnittlich 9500 Millisekunden

ich frag mich aber auch, warum das so viel langsamer ist. Die Arraylist werde ich ausprobieren, aber jetzt ist erstmal Frühstückspause :wink:

[edit]

Nein, eine ArrayList verlangsamt das ganze auch so um die 100 Millisekunden. Kann man vielleicht bei den if-Abfragen nochma an der Performance kitzeln?

AlArenal · 16. Sep 2005

Könnte es sein, dass es nunmal ne Weile dauert bis das Betriebssystem die entsprechenden Daten ausgelesen und an die VM übergeben hat? Große Verzeichnisse zu Öffnen dauert ja auch schonmal nen Moment... Roundabout 900 Dateien und 155 Ordner - da braucht der Explorer von Windows auch nen Moment für.

The_S · 16. Sep 2005

Hab grad ma ausprobiert, und ich bin (arbeite hier mit Windows 2000) schneller als die Suche von Windows 2000

. Kann ja aber sein, dass es ne Möglichkeit gibt, das Ding nochmal ein wenig zu tunen (z. B. mit anderen, schnelleren Datentypen, ...)

AlArenal · 16. Sep 2005

Der Pferdefuß dürfte die Geschwindiogkeit sein, in der das OS die Daten liefert, da wirst du schon MS bitten müssen, zu optimieren

The_S · 16. Sep 2005

OK, werd aber trotzdem noch ein wenig rumprobieren, ob ich noch ein paar Millisekunden schneller bekomm :wink: .

Mir kommt da gerade ein anderes Problem, wie stelle ich fest, dass die Suche fertig ist, also das kein Thread mehr läuft?

Bleiglanz · 16. Sep 2005

Hobbit_Im_Blutrausch hat gesagt.:
OK, werd aber trotzdem noch ein wenig rumprobieren, ob ich noch ein paar Millisekunden schneller bekomm :wink: .

Mir kommt da gerade ein anderes Problem, wie stelle ich fest, dass die Suche fertig ist, also das kein Thread mehr läuft?

schwierig, hab mich auch schon gefragt wie du überhaupt auf deine Zeiten kommst?

kann mir eigentlich nicht vorstellen, dass die ThreadVariante wirklich so viel schneller ist

The_S · 16. Sep 2005

@ bleiglanz

auf was war dein post bezogen? Darauf, dass es schwierig ist, da noch was an geschwindigkeit rauszukitzeln oder dass es schwierig ist festzustellen, ob die Suche noch läuft?

Code is ja da, kannst ja mal ausprobieren, wenns dir schwer fällt zu glauben, dass der Unterschied so trastisch ist (konnts ja auch kaum glauben)

Hab grad nochman größer Angelegten Vergleich zwischen der Win 2000 Suche und meiner Suche gestartet. Ergebnis: bei 233328 Dateien und 28957 Ordner

Windows 2000: 3 Minuten 34 Sekunden

ich: genau 102428 Millisekunden => 1 Minute 42 sec.

Was macht Windows 2000 so lange?

Trotzdem bleib immernoch mein anderes Problem: Wie stelle ich fest, dass die Suche beendet ist?

Bleiglanz · 16. Sep 2005

ich habs mal in eine main gepackt und mit einem shutdownHook das ende ermittelt

unter Linux ist die "single-thread" variante auf jeden Fall schneller!

dass du Windows schlägst wundert mich nicht wirklich, die Suche hat ja wesentlich mehr features

aber die Frage bleibt: wie stellst du eigentlich fest dass du fertig bist?

The_S · 16. Sep 2005

komisch, dass bei dir single-thread schneller ist ???:L .

Wie du sicher bemerkt hast, habe ich am ende meiner Methode ein

Code:

end = new GregorianCalendar()

ich hab auch ein start, was die Zeit zu beginn speichert. Wenn ich jetzt insgesamt fertig bin, vergleiche ich die beiden Daten und bekomme so die Zeit raus.

[edit] kA, was da jetzt gerade gelaufen ist, aber jetzt ist die single-Thread Suche nur noch halb so langsam wie die Multi-Thread Lösung

AlArenal · 16. Sep 2005

Hobbit_Im_Blutrausch hat gesagt.:
komisch, dass bei dir single-thread schneller ist ???:L .

Warum? Mehr Threads bedeuten mehr Verwaltungsaufwand für die VM, also mehr Performance, die nicht deinem Programm zugute kommt. Und wenn ich mein Betriebssystem gleichzeitig 30 Anfragen für unterschiedliche Verzeichnisse stelle, wirds vermutlich auch nicht schneller, als wenn ich es nacheinander mache, weil meine Platte nicht an 30 Stellen gleichzeitig die Informationen lesen kann

AlArenal · 16. Sep 2005

Hobbit_Im_Blutrausch hat gesagt.:
[edit] kA, was da jetzt gerade gelaufen ist, aber jetzt ist die single-Thread Suche nur noch halb so langsam wie die Multi-Thread Lösung

Alte Weisheit: Wer misst, misst Mist.

The_S · 16. Sep 2005

AlArenal hat gesagt.:
Hobbit_Im_Blutrausch hat gesagt.:

komisch, dass bei dir single-thread schneller ist ???:L .

Zum Vergrößern anklicken....

Warum? Mehr Threads bedeuten mehr Verwaltungsaufwand für die VM, also mehr Performance, die nicht deinem Programm zugute kommt. Und wenn ich mein Betriebssystem gleichzeitig 30 Anfragen für unterschiedliche Verzeichnisse stelle, wirds vermutlich auch nicht schneller, als wenn ich es nacheinander mache, weil meine Platte nicht an 30 Stellen gleichzeitig die Informationen lesen kann

Ja, is mir scho klar, nur warum isses unter windows schneller mit Multithreads zu arbeiten und unter linux net?

AlArenal · 16. Sep 2005

P.S.:
Aus eigenrer Erfahrung dürften die meisten auch wissen, das parallele Vorgänge auf Datenträgern, unverhältnismäßig länger dauern als sequenzielle. Beim Versuch des Betriebssystems alle Anfragen per Mutlitaksing quasi-gleichzeitig zu erledigen, entsteht ne Menge Overhead durch zusätzliche Positionierung des Schreib-/Lesekopfs, die bei sequenzieller Abarbeitung nicht notwendig wäre.

AlArenal · 16. Sep 2005

Hobbit_Im_Blutrausch hat gesagt.:
Ja, is mir scho klar, nur warum isses unter windows schneller mit Multithreads zu arbeiten und unter linux net?

Warum hatte mein Ex-Wagen bei 1.8 Litern 116 PS, der davor 136 PS und der aktuelle nur 90 PS? Und warum hängt der neue VW mit 1.4 Litern alle ab?

Rückfrage: Was soll eigentlich "halb so langsam" bedeuten? LOL

The_S · 16. Sep 2005

Hast du Windows? Währst du so net und würdest beide varianten mal testen?

[edit] halb so langsam *g* heißt, dass ich für das auslesen der großen Festplatte (2. Vergleich) mit Multi-Threading genau 102428 Millisekunden benötige und mit Single-Threading 195080 Millisekunden. Also ungefähr das doppelte an Zeit vom Multithreading! :wink:

AlArenal · 16. Sep 2005

Hobbit_Im_Blutrausch hat gesagt.:
Hast du Windows? Währst du so net und würdest beide varianten mal testen?

Yo, XP.
Wärst du so nett mir beide zuzuschicken?

The_S · 16. Sep 2005

Will da selbstverständlich noch ne GUI drumbauen, also net wundern 8) .

Multithreading

Code:

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.io.*;
import java.util.*;

public class Search extends JFrame implements ActionListener {
	
	Vector treffer = new Vector();
	GregorianCalendar start = new GregorianCalendar();
	GregorianCalendar end = new GregorianCalendar();
	
	public Search() {
		
		search(new File("Z:/"), "hilfe.txt"); // Verzeichnis + das wonach du suchen willst
		try {
			Thread.sleep(1000); // Bitte eine Zeit eintragen in der die Suche abgeschlossen sein sollte, hatte noch keine Zeit mir dafür was anderes zu überlegen
		}
		catch (Exception e) {
		}
		for (int i = 0; i < treffer.size(); i++) {
			System.out.println(treffer.elementAt(i));
		}
		System.out.println(end.getTimeInMillis() - start.getTimeInMillis());
	}
	
	void search(final File dir, final String search) {
		
		new Thread(new Runnable() {
			public void run() {
				File[] files = dir.listFiles();
				for (File file : files) {
					if (file.getName().equalsIgnoreCase(search)) {
						treffer.addElement(file);
					}
					if (file.isDirectory()) {
						search(file, search);
					}
				}
				end = new GregorianCalendar();
			}
		}).start();
	}
		
	public static void main(String[] args) {
		
		Search sc = new Search();
		sc.setVisible(true);
	}
	
	public void actionPerformed(ActionEvent evt) {
	}
}

Single-Threading

Code:

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.io.*;
import java.util.*;

public class Search extends JFrame implements ActionListener {
	
	Vector treffer = new Vector();
	GregorianCalendar start = new GregorianCalendar();
	GregorianCalendar end = new GregorianCalendar();
	
	public Search() {
		
		search(new File("Z:/"), "hilfe.txt"); // Verzeichnis + Suchbegriff
		end = new GregorianCalendar();
		for (int i = 0; i < treffer.size(); i++) {
			System.out.println(treffer.elementAt(i));
		}
		System.out.println(end.getTimeInMillis() - start.getTimeInMillis());
	}
	
	void search(final File dir, final String search) {
		
//		new Thread(new Runnable() {
//			public void run() {
				File[] files = dir.listFiles();
				for (File file : files) {
					if (file.getName().equalsIgnoreCase(search)) {
						treffer.addElement(file);
					}
					if (file.isDirectory()) {
						search(file, search);
					}
				}
//			}
//		}).start();
	}
		
	public static void main(String[] args) {
		
		Search sc = new Search();
		sc.setVisible(true);
	}
	
	public void actionPerformed(ActionEvent evt) {
	}
}

Bleiglanz · 16. Sep 2005

wie gross stellst du Thread.sleep denn ein?

bei mir ist auch unter windows die SingleThread Variante schneller (getestet in einer reinen main mit shutdownhook)

The_S · 16. Sep 2005

Also das verwirrt mich jetzt ... moment, da kommt mir eine Idee!!! Ich glaube (kanns net nachgucken, auf der Arbeit is immer alles mögliche gesperrt) dass ich nen Prozessor mit HT Technologie hab von Intel. Kanns sein, dass es daran liegt?

Also für den 1. Versuch reichen die 1000 Millisekunden, man kann ja auch als spaß an der Freude mal 10 Minuten angeben, ändert aber auch nichts am ergebnis. Nur zu wenig darf man nicht angeben, aber das merkt man dann, wenn man als ergebnis bekommt, dass über den angegebenen Millisekunden liegt. Für meinen 1. Versuch (auslesen von Laufwerk Z, das kleine Laufwerk mit den 256 MB) die 1000 Millisekunden.

AlArenal · 16. Sep 2005

Macht nicht viel Sinn die Zeit zwischen der Erzeugung zweier Kalender-Instanzen zu ermitteln

The_S · 16. Sep 2005

AlArenal hat gesagt.:
Macht nicht viel Sinn die Zeit zwischen der Erzeugung zweier Kalender-Instanzen zu ermitteln

???

AlArenal · 16. Sep 2005

Die Multi-threaded Variante liefert ne Zeit, aber listet keine Treffer...

AlArenal · 16. Sep 2005

GregorianCalendar start = new GregorianCalendar();
GregorianCalendar end = new GregorianCalendar();
System.out.println(end.getTimeInMillis() - start.getTimeInMillis());

The_S · 16. Sep 2005

Doch, musst wie gesagt momentan noch die Zeit erhöhen, die der Thread schlafen soll. Bin noch auf der Suche, wie ich das am besten mach, damit ich weiß, wann die Suche beendet ist ohne viel Performanceeinbusen zu haben.

The_S · 16. Sep 2005

AlArenal hat gesagt.:
GregorianCalendar start = new GregorianCalendar();
GregorianCalendar end = new GregorianCalendar();
System.out.println(end.getTimeInMillis() - start.getTimeInMillis());

Und was willst du mir damit sagen? Du weißt scho, dass dazwischen meine suchmethode ist und end darin abgedatet wird!?

AlArenal · 16. Sep 2005

Hobbit_Im_Blutrausch hat gesagt.:
Und was willst du mir damit sagen? Du weißt scho, dass dazwischen meine suchmethode ist und end darin abgedatet wird!?

Ach, wo in deinem Code soll dieses Update denn stattfinden?

Bleiglanz · 16. Sep 2005

Hobbit_Im_Blutrausch hat gesagt.:
Also das verwirrt mich jetzt ... moment, da kommt mir eine Idee!!! Ich glaube (kanns net nachgucken, auf der Arbeit is immer alles mögliche gesperrt) dass ich nen Prozessor mit HT Technologie hab von Intel. Kanns sein, dass es daran liegt?

ja, könnte sein

es heisst ja eh immer, dass das Threading unter Windows bei Java wesentlich besser ist

The_S · 16. Sep 2005

AlArenal hat gesagt.:
Hobbit_Im_Blutrausch hat gesagt.:

Und was willst du mir damit sagen? Du weißt scho, dass dazwischen meine suchmethode ist und end darin abgedatet wird!?

Zum Vergrößern anklicken....

Ach, wo in deinem Code soll dieses Update denn stattfinden?

Multi-Threading:

Code:

      new Thread(new Runnable() { 
         public void run() { 
            File[] files = dir.listFiles(); 
            for (File file : files) { 
               if (file.getName().equalsIgnoreCase(search)) { 
                  treffer.addElement(file); 
               } 
               if (file.isDirectory()) { 
                  search(file, search); 
               } 
            } 
            end = new GregorianCalendar(); // hier!!!
         } 
      }).start();

Single-Threading:

Code:

      search(new File("Z:/"), "hilfe.txt"); // Verzeichnis + Suchbegriff 
      end = new GregorianCalendar(); // hier

Hast dus jetzt mal ausprobiert wenn du den Thread länger schlafen lässt?

@ Bleiglanz

ich werds daheim ma unter XP und 100pro sicher ohne HT Prozessor :wink: ausprobieren

Guest · 16. Sep 2005

Verwende noch folgendes statt listFiles()

Code:

String fileNames[] =  dir.list();
for(String fileName : fileNames) {
  File file = new File(dir, fileName);
  if (fileName.equalsIgnoreCase(search)) { 
    treffer.addElement(file); 
  } 
  if (file.isDirectory()) { 
    search(file, search); 
  }
}

In listFiles() wird immer ein File-Array mit gleicher Länge wie der String-Array erzeugt.
Dadurch sparst Du bei jedem Aufruf

- das Erzeugen dieses Arrays in listFiles()
- die Schleife in listFiles()
- den Methodenaufruf von file.getName()

The_S · 16. Sep 2005

Hilft leider nicht ...

, aber trotzdem danke!

The_S · 17. Sep 2005

OK, bei mir daheim, ohne HT ist Singlethreading schneller. Dann werd ich wohl zwei Suchmöglichkeiten einbauen!

Wikinator · 17. Sep 2005

Hallo,

ich habe eine kleine Frage nebenbei:
Wie misst du so genau die Performance?

byte · 18. Sep 2005

ich weiss nicht wie er es macht, aber eine einfache möglichkeit ist:

Code:

long start = System.currentTimeMillis();

//... der zu messende Code

System.out.println("Vergangene Zeit: "+(System.currentTimeMillis()-start));

The_S · 19. Sep 2005

Wikinator hat gesagt.:
Hallo,

ich habe eine kleine Frage nebenbei:
Wie misst du so genau die Performance?

Ich erstelle zwei Variablen des Typs GregorianCalendar, die 1. Wird beim Starten des Suchvorgangs erstellt, die 2. bei beenden. Beide voneinader abgezogen = Performance :wink:

The_S · 19. Sep 2005

Was ist eigentlich schneller und warum?

Code:

for (int i = 0; i < files.length; i++)

oder

Code:

for (File file : files)

AlArenal · 19. Sep 2005

Du bist doch der große Performance-Messer, sag du es uns!

Bleiglanz · 19. Sep 2005

beide absolut völlig gleich - unterschied ist unmessbar -, das zweite wird ja intern zum ersten, sowas wie

Code:

for (int i = 0, len=files.length; i < len; i++){
    File file = files[i];
...
}

allerdings kannst du beim ersten den Zugriff auf files weglassen wenn du ihn nicht brauchst, während beim zweiten immer eine lokale Variable file erzeugt wird (und beim zweiten kannst du das array nicht verändern...)

The_S · 19. Sep 2005

AlArenal hat gesagt.:
Du bist doch der große Performance-Messer, sag du es uns!

Das ist ja gerade das komische ... Manchmal habe ich bei methode 1 extrem mehr Zeit verbraucht, als bei Methode 2, aber meistens ist beides gleich. Deswegen meine Verwirrung.

@ bleiglanz danke!

Bleiglanz · 19. Sep 2005

Manchmal habe ich bei methode 1 extrem mehr Zeit verbraucht, als bei Methode 2

unmöglich!

The_S · 19. Sep 2005

Ist aber so, hab mir dafür extra nen Testcode geschrieben. Ich mache sonst nichts und es scheint auch nur dann zu sein, wenn der Code frisch compiliert ist. Könnte auch sein, dass es an der IDE (JCreator) liegt ...

The_S · 20. Sep 2005

So, bin jetzt gerade dabei, dass man auch nach Dateien/Ordner suchen kann, dessen Namen man nicht genau kennt. Was ist da jetzt schneller? indexOf() oder contains()?

bygones · 20. Sep 2005

is voellig egal.

intern ist beides die gleiche Methode !

Unterschied ist nur - indexOf hat einen String als Parameter, contains eine CharSequence

The_S · 20. Sep 2005

Danke, dann nehme ich indexOf, damit ich net erst in ne CharSequence wandeln muss. Woher weißt du das eigentlich oder besser gefragt, kann man das irgendwo nachlesen? Dann müsst ich nämlich net immer fragen :wink:

na-oma · 20. Sep 2005

steht zum einen in der Java-Doku, gibts von sun.
Zum andern in jeder Datei die du benutzt z.b. in diesem Fall java/lang/String.class in deinem jdk.

da steht:

Code:

    public boolean contains(CharSequence s) {
        return indexOf(s.toString()) > -1;
    }

und

Code:

    public int indexOf(int ch) {
	return indexOf(ch, 0);
    }

da kann man immer toll nachschaun, wie das ganze eigentlich arbeitet und was es so alles für methoden gibt.

wenn du mit eclipse arbeitest (geht sicher auch in anderen editoren ähnlich) gehst du mit der Maus über den Methodennamen in deinem Quelltext, drückst Strg und die Linke Maustaste. Damit gelangst du in der Datei wo die Klasse (in dem Fall String) definiert ist an die Stelle, wo die angeklickte methode definiert ist. dort steht im KOmmentar auch noch allerhand anderes nützliches

oder halt gleich die doku. so isses aber spannender

The_S · 20. Sep 2005

Hm, danke! Benutze kein Eclipse und mein JDK zu durchsuchen hab ich keine lust ... :wink:

bygones · 22. Sep 2005

Hobbit_Im_Blutrausch hat gesagt.:
Danke, dann nehme ich indexOf, damit ich net erst in ne CharSequence wandeln muss.

schau dir mal die APi an... CharSequence ist das Oberinterface von String / StringBuffer usw... ergo String = CharSequence...

The_S · 22. Sep 2005

deathbyaclown hat gesagt.:
Hobbit_Im_Blutrausch hat gesagt.:

Danke, dann nehme ich indexOf, damit ich net erst in ne CharSequence wandeln muss.

Zum Vergrößern anklicken....

schau dir mal die APi an... CharSequence ist das Oberinterface von String / StringBuffer usw... ergo String = CharSequence...

Also langsam wirds peinlich ... ich sollte mittlerweile doch die API nutzen können

. Danke!

Bennidi · 18. Jan 2006

hey blutender Hobbit,

multithreading lohnt sich nur bei sehr häufigen kontextwechseln (ip und register auf stack sichern usw.). [bei HT Technologie sind die wichtigsten "geshadowed", d.h. doppelt vorhanden]. Jetzt zu dem code:
wenn ein rechenintensiver thread (z.B. eine Suche)ansteht erkennt ein intelligenter time-scheduling algorithmus das eigentlich und räumt dementsprechen mehr Zeit dafür ein. Somit sollte deine suche single-threaded schneller laufen, da es (wie schon von einigen erwähnt) weniger overhead gibt.
ich frage mich übrigens, ob du mit deiner messung nicht nur das ende des ersten threads misst (oberste verzeichnisstufe) und in wirklich die anderen noch laufen. Bin aber kein kenner was threads angeht. hab es nur ein bisschen in der Theorie kennen gelernt.

SuchEngine verschnellern

Top Contributor

Gesperrter Benutzer

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Gesperrter Benutzer

Top Contributor

Gesperrter Benutzer

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Gesperrter Benutzer

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Gesperrter Benutzer

Top Contributor

Guest

Gast

Top Contributor

Top Contributor

Aktives Mitglied

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Gesperrter Benutzer

Top Contributor

Gesperrter Benutzer

Top Contributor

Top Contributor

bygones

Gast

Top Contributor

na-oma

Gast

Top Contributor

bygones

Gast

Top Contributor

Bennidi

Gast

Ähnliche Java Themen