Ein String im String suchen.

[Xin]

Ich habe hier eine einfache Implementierung des Algorithmus.

Falscher Wettbewerb... wir suchen Strings, nicht die Anzahl der Wörter. ^^

Bitte pack' Deine Algorithmen in eine Klasse, die Du von SearchBase (die Deklaration findest Du weiter oben im Thread) ableitest. Ein Testprojekt gibt's ja auch schon (was ich mich allerdings noch nicht angeguckt habe und daher nicht weiß, ob es von Searchbase abgeleitet ist).

Wenn Du Hilfe dabei brauchst, kein Problem.
Wenn ich Deine Arbeit machen soll, keine Chance.

Tut mir Leid für die schlechte Variablenbenamsung

Sowas kann passieren, wenn Dinge terminkritisch werden.

Hier ist nix terminkritisch, also tut's Dir nicht leid, sondern Du (Einzahl) hast nur keinen Bock, es besser zu machen und es damit den Lesern (Mehrzahl), denen Du den Quelltext vorsetzt, einfacher zu machen?

Sorry, wenn ich so vermutlich nervig rüberkomme, es soll nur zum Nachdenken anregen.

Weiterhin werde ich den Ablauf der Tests etwas erweitern, so dass ich nachdem die Texte bekannt gegeben sind eine zusätzliche Zwischenzeit nehmen werde.

Die Frage ist nur wie aussagekräftig das mit Verwendung von Threads ist. Am Besten wäre es wohl Threads zu verbieten. Da kommt es dann mehr auf die Algorithmen und nicht die Threadsicherheit an Ist eigentlich auch die Verwendung von C++0x erlaubt (Auch wenn dein Compiler etwas alt ist^^).

Ich habe nichts gegen Threads. Den Vergleich mit Algorithmen ohne Threads kann man leisten, indem ich nur eine CPU zur Verfügung stelle.

C++0x... hmm... erlaubt. Notfalls muss ich halt einen aktuelleren Compiler ranschaffen.

[fat-lobyte]

Ich habe nichts gegen Threads. Den Vergleich mit Algorithmen ohne Threads kann man leisten, indem ich nur eine CPU zur Verfügung stelle.

Ich im Prinzip auch nicht, aber ich glaube das kickt effektiv alle Anfänger aus dem Wettbewerb. Wenn jemand nen guten Scheduler und ein gutes Arbeitsaufteilungsdings schreibt, haben die Threadleute auf deinen Cores einen bis zu achtfachen Vorteil. Deswegen hab ich ja auch so gefragt "Ich nehme an Threads sind nicht erlaubt", weil ich eben dachte du willst den Fokus eher auf algorithmen legen.

[Xin]

Ich habe nichts gegen Threads. Den Vergleich mit Algorithmen ohne Threads kann man leisten, indem ich nur eine CPU zur Verfügung stelle.

Ich im Prinzip auch nicht, aber ich glaube das kickt effektiv alle Anfänger aus dem Wettbewerb. Wenn jemand nen guten Scheduler und ein gutes Arbeitsaufteilungsdings schreibt, haben die Threadleute auf deinen Cores einen bis zu achtfachen Vorteil. Deswegen hab ich ja auch so gefragt "Ich nehme an Threads sind nicht erlaubt", weil ich eben dachte du willst den Fokus eher auf algorithmen legen.

Gute Algorithmen nutzen die vorhandene Hardware optimal aus. Der Wettbewerb wird auf einem i7 ausgetragen.
Es wurde die Frage gestellt, ob man die Hardware komplett nutzen darf und ich sehe keinen Grund jemandem, der das kann, das zu verbieten. Es kann kein Wettbewerb sein, wenn ich Leuten, die etwas können, verbiete schneller zu sein, als Leute, die etwas nicht können.

Wenn ich die Anzahl der CPUs auf 1 runtersetze - weil so eine CPU ja auch anderwertig beschäftigt sein kann - dann müssen die Nicht-Anfänger eher aufpassen, dass ihr theoretisch 8facher Vorteil sich nicht zu einem Nachteil entwickelt.

Die erste Version meiner Suche habe ich am Samstag geschrieben und sie läuft. Ich bin sicher, sie ist vergleichsweise schnell. Ich habe sie noch nicht mit der strtok-Implementierung verglichen, das Testprogramm werde ich wohl am Wochenende schreiben.
Aber meine Suche ist auch erst in der ersten Version und ich habe noch einiges zu tun, bevor sich mir die Frage nach Parallelität überhaupt stellt.

Als mir beim Worterzählen einige zu nah kamen, musste ich mich mit Assembler behaupten. Ich hatte 12 Jahre vorher zuletzt ein paar Stunden Assembler auf einem 286er geschrieben und noch nie auf Linux irgendwas mit Assembler gemacht. Ich habe beim Wortzählen was gelernt.

Mein Problem ist, dass ich zwar hervorragend Algorithmen schreiben kann, dass ich grundsätzlich auch über Parallelität, Mutexe, Semaphoren und Nebenläufigkeit Bescheid weiß, und trotzdem über keine nennenswerte Erfahrung mit Threads verfüge. Ein fork hier und da und das war's auch schon. Und das geht mir gegen den Strich.

Damit will ich schon seit längerem beschäftigen. Bekämpft meine Algorithmen, dann muss ich mich mit Threads behaupten. Momentan gehe ich davon aus, dass ich bei der Suche auch ohne Threads vorne mitspielen kann.

Das ganze ist eine Herausforderung für alle, um auszuprobieren und um besser zu werden.
Ihr seid meine. ^^

[nufan]

Hm... und welche Grafikkarte hast du? ^^

[fat-lobyte]

Ich habe sie noch nicht mit der strtok-Implementierung verglichen,

Du meinst strstr? Strtok sucht nach einzelnen Zeichen.

Als mir beim Worterzählen einige zu nah kamen, musste ich mich mit Assembler behaupten.

Das wäre meine nächste Frage, Assembler erlaubt? Ich hab da nämlich so ne idee, aber ich weiß noch nicht wie ich sie meinem Compiler beibringen soll.

Bekämpft meine Algorithmen, dann muss ich mich mit Threads behaupten. Momentan gehe ich davon aus, dass ich bei der Suche auch ohne Threads vorne mitspielen kann.

Challange accepted

Hm... und welche Grafikkarte hast du? ^^

Hehehe... Ich glaube das wird ein lustiger Wettbewerb

[fat-lobyte]

Aber das mit dem '\0'-Byte statt der String größe ist schon ein bisschen ein killer :-/ Absicht?

[Panke]

Es wid nur nach Wörtern gesucht, Zeichen wie \n oder änliches werden übersprungen.

Wenn mein Text also "Bin auf dem Schiff, fahrt ihr morgen zur Nordsee?" ist, müsste ich einen Treffer erhalten, wenn ich nach Schifffahrt suche?

[Xin]

Ich habe sie noch nicht mit der strtok-Implementierung verglichen,

Du meinst strstr? Strtok sucht nach einzelnen Zeichen.

<regex>str???</regex>

Wie auch immer ;-D

Als mir beim Worterzählen einige zu nah kamen, musste ich mich mit Assembler behaupten.

Das wäre meine nächste Frage, Assembler erlaubt? Ich hab da nämlich so ne idee, aber ich weiß noch nicht wie ich sie meinem Compiler beibringen soll.

Grundsätzlich ist jeder fiese Trick erlaubt. Das ist zwar jetzt weniger eine Frage des Algorithmus' als eine Frage der Implementierung, aber im Prinzip messen wir mehr die Geschwindigkeit des kompilierten Codes als die Qualität (Wartbarkeit/Lesbarkeit) des Quelltextes.

Das wäre dann gewissermaßen eine eigene Liga, wie wir ja bereits die Ligen der SingleCore und MultiCore-Implementierungen haben.

Bekämpft meine Algorithmen, dann muss ich mich mit Threads behaupten. Momentan gehe ich davon aus, dass ich bei der Suche auch ohne Threads vorne mitspielen kann.

Challange accepted

Hm... und welche Grafikkarte hast du? ^^

Hehehe... Ich glaube das wird ein lustiger Wettbewerb

Hehehe... ich will hier nichts ausschließen, aber wenn Du hier wirklich eine Idee hast, dann würde mich das sicherlich inspirieren.

Welche brauchst Du?

Eingebaut ist eine GeForce G210. Bei Bedarf kann ich eine zweite G210 dazustecken.
Falls erforderlich habe ich noch eine Radeon X1650 hier rumfliegen.

[Panke]

Da Xin das wohl für seine Arbeit braucht, nehm ich mir mal einen eventuellen Vorteil und
weise auf diesen Vergleich von 83 entsprechenden Algorithmen hin.

[Xin]

Da Xin das wohl für seine Arbeit braucht, nehm ich mir mal einen eventuellen Vorteil und
weise auf diesen Vergleich von 83 entsprechenden Algorithmen hin.

Für meine Arbeit brauche ich das nicht, da mache ich 3D-Modellierung und Visualisierung.

Ich habe ein privates, großes C++-Framework mit dem ich arbeite - privat. Darin sind viele Themen abgedeckt, angefangen von Netzwerkprotokollen, 3D-Modellierung (das mache ich auch auf der Arbeit und programmiere es gelegentlich zu Hause nach, wie ich mir das vorstelle) und halt meine eigene Programmiersprache. Inzwischen ist dabei auch eine String-Klasse, die natürlich auch einen String im String suchen kann.
Ich habe hier neben der BruteForce-Implementation auch den Knutt-Morris-Pratt-Algorithmus implementiert.

Da wir hier aber uns auf die Suche nach Wörter in einem Text festgelegt haben, benutze ich diese Suche aber nicht, sondern habe etwas anderes implementiert.
Trotzdem werde ich mir die Arbeit beizeiten mal genauer angucken.