Autor Beitrag
Bergmann89
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1742
Erhaltene Danke: 72

Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
BeitragVerfasst: Mi 20.10.10 22:05 
Hey,

ich hab zur Zeit ein Problem wo ich nicht so richtig weiter weiß. Es geht darum, das ich Strings in eine StringList schreiben will. Die Strings sind alle genau 13-Zeichen lang. Jetzt gibt es aber die Bedingung, das ein neuer String der in die Liste eingetragen werden soll mind. x unterscheidliche Zeichen zu allen anderen in der Liste gespeicherten Strings haben muss. Da aber ca. 1Mio Strings eingetragen werden müssen dauert das Ganze auch entsprechend lange. Jetzt hab ich mir überlegt, wie man das alles optimieren könnte und da scheiter ich grad dran. Mir ist die Idee gekommen eine Hashmap zu nutzen, aber ich bin mir nicht ganz sicher ob das mein Problem löst, und ich bin auch noch nicht so bewandert in der Benutzung von Hashmaps. Aus diesem Grund wollt ich hier erstmal fragen ob das der richtige Weg ist, oder ob es noch effektivere Möglichkeiten gibt.

MfG & Thx Bergmann

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mi 20.10.10 22:49 
Ich sehe jetzt nicht, wie da eine Hashmap helfen könnte :gruebel:

Was bedeutet denn genau "mind. x unterscheidliche Zeichen"? Meine Idee wäre, die eingefügten Strings zusätzlich in einer Art DAWG (directed acyclic word graph) zu speichern. Da sind die Knoten des Graphen Buchstaben, und Wege von der Wurzel des Graphen/Baumes naach unten bilden die Strings, die schon eingefügt sind. Bei einem neuen String kann man dann relativ schnell feststellen, ob das neue Wort schon drin ist oder nicht.
Aber wie das mit den unterschiedlichen Zeichen genau zu modifizieren ist, weiß ich auch noch nicht so genau...

_________________
We are, we were and will not be.
elundril
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 3747
Erhaltene Danke: 123

Windows Vista, Ubuntu
Delphi 7 PE "Codename: Aurora", Eclipse Ganymede
BeitragVerfasst: Mi 20.10.10 22:55 
user profile iconGausi hat folgendes geschrieben Zum zitierten Posting springen:
Ich sehe jetzt nicht, wie da eine Hashmap helfen könnte :gruebel:

Was bedeutet denn genau "mind. x unterscheidliche Zeichen"? Meine Idee wäre, die eingefügten Strings zusätzlich in einer Art DAWG ...


Yo Dawg, we heard you like Dawgs so we put a Dawg in a Dawg so you can look at Dawg while your looking at Dawg. :mrgreen:

SCNR.

lg elundril

_________________
This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

Für diesen Beitrag haben gedankt: der organist
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mi 20.10.10 23:01 
Also die Jugend von heute versteh ich nicht... :gruebel:

Ich meinte auf jeden Fall so einen DAWG.

_________________
We are, we were and will not be.
Bergmann89 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1742
Erhaltene Danke: 72

Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
BeitragVerfasst: Mi 20.10.10 23:17 
Hey,

so ne ähnliche Idee hatte ich auch, aber mein Gedankengang endete wie deiner dabei das ganze auf mein Problem zuzuschneidern. Hier nochma n kleines Beispiel (stark vereinfacht).
Strings die eingefügt werden sollen: (List1)
aaaaaa
aaaabb
abaabb
der unterschied muss mindestens 2 Zeichen betragen (also x = 2)
ausblenden Quelltext
1:
2:
3:
4:
5:
für alle Einträge in List1 (Schleife1)
  für alle Einträge in List2 (Schleife2)
    wenn unterschiedliche Zeichen < x, dann...
      beende Schleife2 und starte mit nächstem Eintrag in Schleife 1
  übernimm Eintrag in List2

List2 wäre dann wie folgt:
aaaaaa
aaaabb

als 1. kommt aaaaaa in die List2, is ja klar weil es keine Strings zum vergleich in der Liste gibt. Dann kommt auch aaaabb in List2, weil es mind. 2 Zeichen Unterscheid zu aaaaaa hat (nämlich die 2 b). Dann wird abaabb geprüft, hat mehr als 2 unterschiedliche Buchstaben zu aaaaaa also weiter. Beim Vergleich von abaabb mit aaaabb ist aber nur ein Zeichen anders, somit erfüllt abaabb die Bedingung nicht und kommt nicht in die List2...

ich schlaf erstma ne Runde dadrüber.

gn8 Bergmann

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Do 21.10.10 10:38 
Um mal bei der Idee zu bleiben: Du könntest den Dawg beim Einfügen aufbauen. Beim Einfügen des nächsten Strings startest du in dem Baum eine Tiefensuche. Dabei zählst du einen Zähler hoch, wenn du eine "falsche Kante" entlangläufst. Wenn der Zähler bei 2 ist, kannst du den Tiefensuchdurchlauf in diesem Teilbaum abbrechen - die Strings in diesem Teil des Baumes sind alle um mindestens 2 Zeichen verschieden. Dann gehst du in der Rekursion einen Schritt nach oben, verringerst dabei ggf. wieder den Zähler und machst in dem nächsten Ast weiter. Wenn du an einem Blatt in dem DAWG ankommst, und der Zähler ist kleiner als 2, dann hast du bereits ein ähnliches Wort in deiner Liste. Die Suche kann dann abgebrochen und das Wort verworfen werden.

_________________
We are, we were and will not be.
Bergmann89 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1742
Erhaltene Danke: 72

Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
BeitragVerfasst: Do 21.10.10 11:51 
Hey,

gut, das sollte funktionieren, ich werd das heute mal umsetzten. Bleibt dann nur zu hoffen, das diese Methode schneller ist als die jetzige... Ich halt euch auf dem laufenden.

MfG Bergmann

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^
Kha
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Do 21.10.10 13:39 
Ist "n unterschiedliche Zeichen" nun positionsunabhängig gemeint oder nicht :nixweiss: ?

_________________
>λ=
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Do 21.10.10 13:50 
So ganz sicher bin ich mir da auch noch nicht, für meine Idee bin ich einfach mal von der Hamming-Distanz ausgegangen. Wenn also an der x-ten Position in den beiden Strings zwei unterschiedliche Zeichen stehen, dann ist das "ein Unterschied".

Also
ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
abcdef
bcdefa
 Unterschied = 6

abcdef
abcfff
  Unterschied = 2

_________________
We are, we were and will not be.
Lemmy
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 792
Erhaltene Danke: 49

Windows 7 / 10; CentOS 7; LinuxMint
Delphi 7-XE10.1, VS 2015
BeitragVerfasst: Do 21.10.10 14:06 
Hi,

bevor du jetzt die Tastatur quälst: Delphi F1 und THashedStringList eingeben:

Zitat:

Beschreibung

Ein THashedStringList-Objekt ist eine Stringliste, die intern eine Hash-Tabelle verwendet, um die Suche nach Strings zu beschleunigen. Es wird intern von TMemIniFile verwendet, um die Strings in einer INI-Datei zu verwalten. Das Objekt kann jedoch wie jede andere Stringliste genutzt werden. Insbesondere bei Listen mit einer großen Anzahl von Strings kann die Leistung durch die Verwendung der Klasse THashedStringList anstelle von TStringList optimiert werden.


sprich tausch mal TStringList durch THashedStringlist aus und schau ob dir die Performance ausreicht....

cu
jaenicke
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 19314
Erhaltene Danke: 1747

W11 x64 (Chrome, Edge)
Delphi 11 Pro, Oxygene, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
BeitragVerfasst: Do 21.10.10 14:09 
Was soll die denn hier in diesem Fall für Geschwindigkeitsvorteile bringen? :gruebel:
Lemmy
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 792
Erhaltene Danke: 49

Windows 7 / 10; CentOS 7; LinuxMint
Delphi 7-XE10.1, VS 2015
BeitragVerfasst: Do 21.10.10 14:34 
Asche auf mein Haupt! Ich habe überlesen, dass sich die Strings in X Zeichen unterscheiden müssen und nicht nur einfach unterschiedlich sein müssen...

Grüße
Flamefire
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: Do 21.10.10 15:27 
In dem Fall würde ich sogar auf die Stringlist verzichten und ein ähnliches Control schreiben (vl von TList ableiten) dass intern NUR den Baum verwendet. Da ja schon alles drin.
Thorsten83
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 191
Erhaltene Danke: 1



BeitragVerfasst: Fr 22.10.10 10:42 
Darf man erfahren wie viel das gebracht hat? :)
Bergmann89 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1742
Erhaltene Danke: 72

Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
BeitragVerfasst: Fr 22.10.10 14:51 
Hey,

noch nix. Bin noch nich dazu gekommen. Werd ich heut abend/nacht machen oder morgen. Mal sehen. Aber auf alle Fälle dieses WE. Ich sag bescheid wenns funktioniert.

MfG Bergmann.

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^
Bergmann89 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1742
Erhaltene Danke: 72

Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
BeitragVerfasst: Sa 23.10.10 03:14 
Hey,

habs soweit fertig und der Unterschied zur normalen Liste ist seeeehr groß^^
Das neue läuft mit x = 4 (mind. 4 Zeichen Unterschied) mit knapp 19sec, das alte hat mehr als 100sec gebraucht!!!
Hier der Code, wenn sich jmd dafür interessiert:
ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//püft ob der String mind x unterschiednliche Zeichen zu allen anderen Strings im Baum hat
//x = fMinCharDif --> property MinCharDif
//@p: Zeiger auf den String, der geprüft werden soll;
//@result: TRUE, wenn Sring gültig ist und die Bedingungen erfüllt; 
function TStringTree.CheckCharCountDif(p: PAnsiString): Boolean;

  function Check(d, Count: Integer; Item: PStringTreeItem): Boolean;
  var
    c: Byte;
  begin
    result := True;
    if (d > 13or not Assigned(Item) then begin
      if d > 13 then
        result := False;
      exit;
    end;

    if (p^[d] <> Item^.Value) and (d > 0then
      inc(Count);

    if Count >= fMinCharDif then
      exit;

    if d = 0 then
      c := Ord(p^[d+1]) - $30
    else
      c := Ord(p^[d]) - $30;
    case c of
      1begin
        result := Check(d+1, Count, Item^.Children[0]);
        if result then
          result := Check(d+1, Count, Item^.Children[2]);
      end;
      0begin
        result := Check(d+1, Count, Item^.Children[1]);
        if result then
          result := Check(d+1, Count, Item^.Children[2]);
      end;
      2begin
        result := Check(d+1, Count, Item^.Children[0]);
        if result then
          result := Check(d+1, Count, Item^.Children[1]);
      end;
    end;
    if result then
      result := Check(d+1, Count, Item^.Children[c]);
  end;

begin
  result := Check(00, fValues);
end;
Das ist jetz natürlich auf mein Problem zugeschnitten (Stringlänge 13 Zeichen; Zeichen nur '1', '0' und '2'), sollte aber nich so schwer sein, das auch auf allgemeine Sachen zu übertragen.
Ich überleg auch schon die ganze Zeit, wie man das evtl auf mehrere Thread verteilen könnte, aber das wird wohl nich gehen, weil er ja dauernt auf den Baum zugreift. Oder hat jmd ne Idee dazu (so großartig hab ich mit Threads noch nich gearbeitet).

MfG & gn8 Bergmann.

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^
Kha
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Sa 23.10.10 15:40 
user profile iconBergmann89 hat folgendes geschrieben Zum zitierten Posting springen:
Ich überleg auch schon die ganze Zeit, wie man das evtl auf mehrere Thread verteilen könnte, aber das wird wohl nich gehen, weil er ja dauernt auf den Baum zugreift.
Gleichzeitiges Suchen im und Ändern des Graphen (kein Baum, falls du wirklich einen DAWG und keinen Trie benutzt ;) ) wird natürlich nicht funktionieren, das stimmt. Aber deine Check-Methode selbst lässt sich als Divide-and-Conquer-Algorithmus wunderbar parallelisieren, such einfach mal nach einem parallelen Quicksort als Beispiel.
Sollte sich herausstellen, dass dabei die einzelnen Aufgaben zu "fine-grained" sind, also der Thread-Overhead überwiegt, kannst du auch mehrere einzufügende Strings erst einmal in einem Batch sammeln. Für jeden String suchst du im alten DAWG, überprüfst dann noch die Ähnlichkeit zu den restlichen Strings im Batch und fügst am Ende alle (die den Test bestanden haben) auf einmal in den Graph ein. Die ersten beiden Schritte lassen sich dabei problemlos parallelisieren.

_________________
>λ=
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: So 31.10.10 02:36 
Die Sache bzgl. Sammeln mehrerer Strings dürfte sogar recht vorteilhaft sein, weil man dann wirklich schon mal vorfiltern kann und dadurch die wirklichen Schreiboperationen im DAWG/Trie stark verringern kann. Also in parallel X String vorfiltern und danach single-threaded die verbliebenen Kandidaten gegen die vorhandene Liste filtern und einfügen.

Die generalisierte Variante könnte für Multithread-Filtering auch einfach mit nem Task-Stack (oder Prio-Queue) arbeiten, bei dem die Rekursionsschritte auf dem Stack abgelegt werden. Hilfreich könnten hier theoretisch auch Fibers sein, weil dann das Switching zwischen den einzelnen Aufgaben um einiges beschleunigt wird. (Kleinerer Context Switch Overhead).

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
Tranx
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 648
Erhaltene Danke: 85

WIN 2000, WIN XP
D5 Prof
BeitragVerfasst: So 31.10.10 04:23 
user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Die Sache bzgl. Sammeln mehrerer Strings dürfte sogar recht vorteilhaft sein, weil man dann wirklich schon mal vorfiltern kann und dadurch die wirklichen Schreiboperationen im DAWG/Trie stark verringern kann. Also in parallel X String vorfiltern und danach single-threaded die verbliebenen Kandidaten gegen die vorhandene Liste filtern und einfügen.

Die generalisierte Variante könnte für Multithread-Filtering auch einfach mit nem Task-Stack (oder Prio-Queue) arbeiten, bei dem die Rekursionsschritte auf dem Stack abgelegt werden. Hilfreich könnten hier theoretisch auch Fibers sein, weil dann das Switching zwischen den einzelnen Aufgaben um einiges beschleunigt wird. (Kleinerer Context Switch Overhead).


Ist doch nett, was ich hier lesen kann, doch allein, mir fehlt der Sinn dessen, was der Autor mir sagen will.
jaenicke
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 19314
Erhaltene Danke: 1747

W11 x64 (Chrome, Edge)
Delphi 11 Pro, Oxygene, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
BeitragVerfasst: So 31.10.10 06:56 
user profile iconTranx hat folgendes geschrieben Zum zitierten Posting springen:
Ist doch nett, was ich hier lesen kann, doch allein, mir fehlt der Sinn dessen, was der Autor mir sagen will.
Solange es user profile iconBergmann89 weiß... :mrgreen: :P

Aber was fehlt dir denn? Die Priority Queue? Oder Fibers?