Ein String im String suchen.

[fat-lobyte]

Sind die "Konkurrenten" eigentlich Multithreaded?
Mein Kandidat würde ziemlich von Multithreading profitieren, und das einzubauen wäre auch nicht allzu schwierig, Bock hab ich nur gerade keinen.

[nufan]

Sind die "Konkurrenten" eigentlich Multithreaded?

Mein Code nicht. Ich könnte das Hashing parallelisieren, das würde schon noch einiges bringen schätze ich. Wir könnten ja mal alle Single-Thread-Algorithmen vergleichen und dann auf mehrere Threads umsteigen.

[Xin]

Sind die "Konkurrenten" eigentlich Multithreaded?
Mein Kandidat würde ziemlich von Multithreading profitieren, und das einzubauen wäre auch nicht allzu schwierig, Bock hab ich nur gerade keinen.

Ich bin SingleThreaded, würde von Multi-Threading vermutlich nahezu 1:1 profitieren. Wenn Du besser bist als ich, baue ich es ein

Aber erstmal muss ich rausfinden, ob mein Code vom letzten Jahr überhaupt noch funktioniert, da es einige Umbauten im Framework gegeben hat und mein Test vor ein paar Tagen... ähh... nicht auf einwandfreie Funktion hindeutete...

EDIT: Ich werde es einbauen, ich habe zuwenig Erfahrung mit Multi-Theading, also wird das wohl kaum schaden.

[fat-lobyte]

EDIT: Ich werde es einbauen, ich habe zuwenig Erfahrung mit Multi-Theading, also wird das wohl kaum schaden.

Das große Wettrüsten...

Ich mach erstmal nicht mit. Miss mal, dann kucken wir weiter. Ich hoffe doch, du veröffentlichst deinen Algorithmus auch?

[fat-lobyte]

So, habe zumindest mal Dani's Kandidaten getestet.

Texte:

Code: Alles auswählen

            {"Shakespeare - Macbeth", "txt/en-macbeth.txt"},
            {"Kafka - Die Verwandlung", "txt/ger-dieverwandlung.txt"},
            {"Goethe - Faust", "txt/ger-faust.txt"},
            {"Goethe - Iphigenie auf Tauris", "txt/ger-iphigenie.txt"}

Pattern:

Code: Alles auswählen

            {"test_output1.txt", {"Hallo", "Welt", "Du" } },
            {"test_output2.txt", {"Hello", "World", "You", "Me"} }

2 Problemchen:

1. Der Speicher: 520 MB ist schon verdammt viel Ich wollte ja noch einen Text hinzufügen, aber dann is mein PC fast abgeschmiert
2. Vielleicht mach ich was falsch, aber ich glaube er findet nix. Zumindest sind die Dateien danach Leer.

Performance:

Code: Alles auswählen

Experiment Adding Texts with N = 30:
	Min / Max: 1.24 s / 1.87 s
	Average: 1.36 s.
	Standard deviation: 638 ms.
	Relat. standard deviation: 46.7%
Experiment Searching with N = 30:
	Min / Max: 375 μs / 5.39 ms
	Average: 676 μs.
	Standard deviation: 4.89 ms.
	Relat. standard deviation: 724%

Dazu im Vergleich:

Suche mit std::strstr()

Code: Alles auswählen

Experiment Adding Texts with N = 30:
	Min / Max: 0 μs / 2 μs
	Average: 0.9 μs.
	Standard deviation: 2.95 μs.
	Relat. standard deviation: 328%
Experiment Searching with N = 30:
	Min / Max: 49.2 ms / 59.4 ms
	Average: 51.7 ms.
	Standard deviation: 18.1 ms.
	Relat. standard deviation: 35.1%

"Straightforward"-Suche:

Code: Alles auswählen

Experiment Adding Texts with N = 30:
	Min / Max: 1 μs / 2 μs
	Average: 1.07 μs.
	Standard deviation: 1.37 μs.
	Relat. standard deviation: 128%
Experiment Searching with N = 30:
	Min / Max: 11.6 ms / 17.5 ms
	Average: 12.8 ms.
	Standard deviation: 8.01 ms.
	Relat. standard deviation: 62.6%

Mein Kanidat:

Code: Alles auswählen

Experiment Adding Texts with N = 30:
	Min / Max: 256 ms / 315 ms
	Average: 279 ms.
	Standard deviation: 111 ms.
	Relat. standard deviation: 39.9%
Experiment Searching with N = 30:
	Min / Max: 527 μs / 1.11 ms
	Average: 696 μs.
	Standard deviation: 696 μs.
	Relat. standard deviation: 99.9%

Das sagt noch nicht viel aus, wenn keine Hits gefunden werden. Könntest du dir das eventuell nochmal ankucken?

Ich entschuldige mich für die furchtbare Standardabweichung, aber ich krieg sie echt nicht runter. Ich glaube, der Minimalwert sollte informativer als der Mittelwert sein.
Hat jemand ne Idee, warum die Zeiten so unglaublich schwanken??

Hier mein Test-Framework, falls du nachmessen willst:

proggen_searchwords.zip

Meine CPU:

Code: Alles auswählen

processor	: 0
vendor_id	: GenuineIntel
cpu family	: 15
model		: 6
model name	: Intel(R) Pentium(R) D CPU 3.00GHz
stepping	: 4
microcode	: 0x4
cpu MHz		: 2400.000
cache size	: 2048 KB
physical id	: 0
siblings	: 2
core id		: 0
cpu cores	: 2
apicid		: 0
initial apicid	: 0
fpu		: yes
fpu_exception	: yes
cpuid level	: 6
wp		: yes
flags		: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx lm constant_tsc pebs bts nopl pni dtes64 monitor ds_cpl vmx est cid cx16 xtpr pdcm lahf_lm tpr_shadow
bogomips	: 6021.29
clflush size	: 64
cache_alignment	: 128
address sizes	: 36 bits physical, 48 bits virtual
power management:

processor	: 1
vendor_id	: GenuineIntel
cpu family	: 15
model		: 6
model name	: Intel(R) Pentium(R) D CPU 3.00GHz
stepping	: 4
microcode	: 0x4
cpu MHz		: 2400.000
cache size	: 2048 KB
physical id	: 0
siblings	: 2
core id		: 1
cpu cores	: 2
apicid		: 1
initial apicid	: 1
fpu		: yes
fpu_exception	: yes
cpuid level	: 6
wp		: yes
flags		: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx lm constant_tsc pebs bts nopl pni dtes64 monitor ds_cpl vmx est cid cx16 xtpr pdcm lahf_lm tpr_shadow
bogomips	: 6021.29
clflush size	: 64
cache_alignment	: 128
address sizes	: 36 bits physical, 48 bits virtual
power management:

Mein compiler:

Code: Alles auswählen

g++ (GCC) 4.7.2 20120921 (Red Hat 4.7.2-2)
Copyright (C) 2012 Free Software Foundation, Inc.
Dies ist freie Software; die Kopierbedingungen stehen in den Quellen. Es
gibt KEINE Garantie; auch nicht für MARKTGÄNGIGKEIT oder FÜR SPEZIELLE ZWECKE.

[Xin]

Grundsatzdiskussion mit fatlobyte nach hier abgetrennt.

[nufan]

1. Der Speicher: 520 MB ist schon verdammt viel Ich wollte ja noch einen Text hinzufügen, aber dann is mein PC fast abgeschmiert

Das war irgendwie zu erwarten... habs jetzt zumindest auf 344MB runter bekommen, weniger geht aber leider nicht.

Performance:

Sehr schön... mein Algorithmus ist schnell, ich hab die benötigte Zeit grade nochmal auf ein Drittel vermindert. Jetzt brauch ich nur mehr richtige Ergebnisse ^^

2. Vielleicht mach ich was falsch, aber ich glaube er findet nix. Zumindest sind die Dateien danach Leer.

Das ist mit den großen Texten schwer zu debuggen, ich hänge mal ein Archiv mit meinem aktuellen Code und kleinen Testdaten dran. Nur bekomme ich da durchwegs korrekte Ergebnisse?! Mach ich in main irgendwas anders als du?

[nufan]

Bin grade draufgekommen, dass man die von mir "erfundene" Struktur "Trie" oder "Prefix-Tree" nennt ^^
http://en.wikipedia.org/wiki/Trie

[Xin]

Bin grade draufgekommen, dass man die von mir "erfundene" Struktur "Trie" oder "Prefix-Tree" nennt ^^
http://en.wikipedia.org/wiki/Trie

Hab Deinen Code noch nicht gesehen, aber diese "Trie"-Struktur hatte ich auch mal "erfunden" für ein Syntax-Highlighting in einem selbstgeschriebenen Texteditor.
Das erklärt nun auch, weswegen Du viel Speicher für Dich beanspruchst. *lach*

Ich arbeite mit Hashs.
Ich bin gespannt.