Autor Beitrag
ggehrma
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 111

WinXP
D2005 Pers.
BeitragVerfasst: So 25.12.05 15:23 
Hallo,

Ich habe eine StringList, die ich über zwei Schleifen mit ca. 60.000 Einträgen fülle. Während des Füllvorgangs werden der Reihe nach alle bisher eingetragenen Strings erweitert und mit IndexOf() getestet ob der so neu entstandene String bereits in der Liste enthalten ist. Ist er nicht enthalten, wird er der Liste mit Add hinzugefügt.
Laufen tut das auch alles problemlos. Das dumme ist nur, dass der dafür ca. 1,5 Stunden benötigt. Kann man das irgendwie beschleunigen?

Bin für Vorschläge dankbar.

mfg, ggehrma


Moderiert von user profile iconraziel: Topic aus VCL (Visual Component Library) verschoben am So 25.12.2005 um 15:51

_________________
"...To boldly go where no one has gone before."
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: So 25.12.05 16:22 
Kann man bestimmt. Pauschal kann ich dazu jetzt aber nichts sagen. Erläutere mal genauer, was das für Strings sind, und warum müssen nach jedem Einfügen alle bereits eingefügten verändert werden? (Hab ich zumindest so verstanden.)

Das Problem ist, dass IndexOf bei unsortierten Listen recht lange dauern kann, weil unter Umständen alle Listeneinträge durchgegangen werden müssen.
Bei sortierten Listen dauert das Einfügen sehr lange, da unter Umständen alle bereits eingefügten Elemente verschoben werden müssen. (Ich gehe von den Delphi-Listen aus, die ja eine Array-Struktur haben und keine wirklichen Listen sind).

In beiden Fällen benötigt das Füllen der Liste ca 1.800.000.000 Schritte (ein Schritt ist hier ein Stringvergleich), und das dauert halt etwas.

Von daher muss man das Verfahren generell ändern, und das Füllen der Liste etwas anders angehen.

_________________
We are, we were and will not be.
matze
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 4613
Erhaltene Danke: 24

XP home, prof
Delphi 2009 Prof,
BeitragVerfasst: So 25.12.05 17:50 
schau dir mal von der StringList die eigenschaften Duplicates und Sorted an !

_________________
In the beginning was the word.
And the word was content-type: text/plain.
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: So 25.12.05 17:55 
Das bringt auch nicht wirklich was, würde ich sagen, wenn er die Liste komplett von Anfang an aufbauen möchte.

Bei sortierten Listen dauert das Einfügen genauso lange, wie bei unsortierten. Bei ersterem muss (möglicherweise) die ganze Liste durchgegangen werden, um das neue Element zu suchen, bei sortierten muss (möglicherweise) die ganze Liste durchgegangen werden, um sie neu zu ordnen.

Oder habe ich da jetzt ne Denkblockade? :gruebel:

_________________
We are, we were and will not be.
ggehrma Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 111

WinXP
D2005 Pers.
BeitragVerfasst: So 25.12.05 17:57 
Nein, es müssen nicht nach jedem Einfügen alle Strings verändert werden.
Die StringList ist so aufgebaut, dass sie vor den drei (nicht zwei, sorry) Schleifen bereits ein paar Einträge besitzt. Und nun werden alle Einträge so lange durchlaufen und durch ein weiteres Zeichen ergänzt, bis der aktuell neu entstandene String eine bestimmte Länge hat. Sagen wir also, die Liste besteht aus drei Einträgen mit jeweils einem Zeichen und die zu ereichende Länge beträgt 3 Zeichen. Dann wird Eintrag eins um ein Zeichen erweitert, hat nun also zwei Zeichen und wird hinten an die Liste angehängt und ist nun Eintrag vier. So wird das auch mit Eintrag 2 und 3 gemacht. Ist er nun bei Eintrag 4 angekommen wird diesem auch wieder ein Zeichen angehängt welcher nun 3 Zeichen hat und damit die Endbedingung erfüllt ist.

Ich hoffe es ist jetzt etwas klarer, denn noch genauer kann ich es leider nicht beschreiben.

_________________
"...To boldly go where no one has gone before."
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: So 25.12.05 18:04 
Kann es denn überhaupt passieren, dass ein neu generierter String (also "alter String + ein Zeichen") schon in der Liste drin ist? Und wenn ja, wäre das so schlimm, wenn de eine oder andere String doppelt vorkommt? Dann könnte man sich die Überprüfung mit IndexOf() nämlich sparen...

_________________
We are, we were and will not be.
ggehrma Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 111

WinXP
D2005 Pers.
BeitragVerfasst: So 25.12.05 18:09 
Ja, es kann vorkommen, dass so entstehende Strings doppelt vorkommen und ja, das ist schlimm, wenn die doppelt in der StringList enthalten sind, da ich wissen möchte, wie viele verschiedene Strings so entstehen.

_________________
"...To boldly go where no one has gone before."
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: So 25.12.05 18:17 
Ich sehe immer noch nicht den tieferen Sinn dahinter, vielleicht kannst du mal ein komkretes Beispiel geben, was du für Strings in der Liste hast, und welche Zeichen angehängt werden.

Ich gehe einfach mal davon aus, dass es relativ selten vorkommt, dass ein String doppelt generiert wird. Man könnte dann im ersten Durchlauf die Strings ohne überprüfung einfügen, anschließend die Liste sortieren, und dann doppelte Einträge durch Vergleich benachbarter Elemente finden und entfernen.
Hört sich nach mehr Arbeit an, dürfte aber um einen Faktor 1000 bis 10000 schneller gehen (wenn wenige Duplikate vorhanden sind).

_________________
We are, we were and will not be.