Seite 1 von 7
Ein String im String suchen.
Verfasst: Do Jun 23, 2011 5:36 pm
von canlot
Hallo zusammen.
Als ich heute am proggen war, ist mir eine Idee gekommen.
Wie wäre es nochmal mit einem kleinen Algorithmus Wettkampf wie der von Wordcount?
Ich wäre für: siehe Überschrift.
Ich hab den Algorithmus fertig und würde gerne wissen wie andere den programmieren würden, und dementsprechend wie schnell sie sind
Wenn Xin Zeit und Lust hat die Sachen auszuwerten sowie andere mitzumachen wäre das echt cool
Was sagt ihr dazu?
Re: Ein String im String suchen.
Verfasst: Do Jun 23, 2011 7:12 pm
von fat-lobyte
canlot hat geschrieben:Hallo zusammen.
Als ich heute am proggen war, ist mir eine Idee gekommen.
Wie wäre es nochmal mit einem kleinen Algorithmus Wettkampf wie der von Wordcount?
Ich wäre für: siehe Überschrift.
Ich hab den Algorithmus fertig und würde gerne wissen wie andere den programmieren würden, und dementsprechend wie schnell sie sind
Wenn Xin Zeit und Lust hat die Sachen auszuwerten sowie andere mitzumachen wäre das echt cool
Was sagt ihr dazu?
Wie sind denn die Strings gegeben? Ist der Anfang und das Ende gegeben? Oder nur der Anfang und die länge? Oder nur der Anfang, das Ende ist mit '\0' begrenzt?
Was soll passieren wenn ein String länger als der ander ist?
Was soll passieren wenn der String nicht gefunden wurde?
Wie soll man mit mehreren Treffern umgehen?
Was soll überhaupt zurückgegeben werden?
Bitte etwas präzisieren
Re: Ein String im String suchen.
Verfasst: Do Jun 23, 2011 7:42 pm
von canlot
fat-lobyte hat geschrieben:Wie sind denn die Strings gegeben? Ist der Anfang und das Ende gegeben? Oder nur der Anfang und die länge? Oder nur der Anfang, das Ende ist mit '\0' begrenzt?
Der Anfang ist gegeben und das Ende ist halt mit '\0' gekennzeichnet.
fat-lobyte hat geschrieben:Was soll passieren wenn ein String länger als der ander ist?
Habe ich nicht berücksichtigt.
fat-lobyte hat geschrieben:Was soll passieren wenn der String nicht gefunden wurde?
return 1;
fat-lobyte hat geschrieben:Wie soll man mit mehreren Treffern umgehen?
Habe ich ebenfalls nicht berücksichtigt.
fat-lobyte hat geschrieben:Was soll überhaupt zurückgegeben werden?
return 0 für gefundenen String und return 1 für nicht gefundenen String.
Bei mir sucht er den Text nach den String ab und wen er ihn gefunden hat den beendet er sich mit return 0.
Was meint ihr dazu?
Re: Ein String im String suchen.
Verfasst: Do Jun 23, 2011 8:11 pm
von Xin
Grundsätzlich kann man das gerne machen.
Aber bei der Suche gibt es viele Fragen. Ist zum Beispiel wichtig, wo er gefunden wurde? Wie oft? Und wenn wie oft, wird soll dann "greedy" gesucht werden?
Greedy bedeutet, dass der String "ana" in "Banana" zweimal vorkommt, nämlich "bANAna" und "banANA". Dabei wird ein 'A' für zwei Ergebnisse genutzt. Man kann natürlich auch den gefundenen String nicht weiter prüfen, dann findet man nur "bANAna" und das wars.
Wie lang soll der gesuchte, bzw. der zu durchsuchende String sein? Bei einem kurzem zu durchsuchendem String, lohnt keine Untersuchung des Suchmusters.
Wieviele Strings werden in dem Text gesucht? Bei nur einem String, lohnt sich keine Untersuchung des zu durchsuchenden Strings?
Ich finde das Thema interessant, denn je nach Aufgabenstellung muss ich mich eh mit dem Thema noch für die
Suchmaschine beschäftigen, die ja genau das zum Thema hat. ^^
Re: Ein String im String suchen.
Verfasst: Do Jun 23, 2011 8:24 pm
von cloidnerux
Mich Interessiert es auch.
Ich würde selber folgende Parameter nehmen:
Es soll zurückgegeben werden wie viele Vorkommen es gibt, wird der zu suchende Text nicht gefunden soll 0 zurückgegeben werden.
Es wird nicht greedy gesucht.
Der zu Durchsuchende text wird wieder groß, wie beim WordCount test, damit man gute Zeitwerte hat.
Gesucht wird nach einem Wort bzw einem Fragment.
Das Ende ist mit \0 gekennzeichnet, das gibt jedem die Möglichkeit den String selber irgendwie zu bemessen.
Das würde für mich folgende Funktionsdeklaration geben:
int SearchForString(char* base, char* target)
Re: Ein String im String suchen.
Verfasst: Do Jun 23, 2011 8:31 pm
von Xin
cloidnerux hat geschrieben:int SearchForString(char* base, char* target)
Ich möchte eine Festlegung wieviele unterschiedliche Worte im gleichen Text gesucht werden sollen, bzw. wieviele gleiche Worte in unterschiedlichen Texten gesucht werden sollen.
Und ich möchte eine Information, ob der zu durchsuchenden Texte kurz (bis 1KB) oder lang (>1 GB) groß ist. Also grundsätzlich jetzt im Testaufbau, damit jeder von gleichen Konditionen ausgehen kann.
Falls verfügbar, hätte ich die Längen-Information auch gerne als Parameter. Das kann man natürlich auch ablehnen, was dann bedeutet, dass das Nullbyte selbst erkannt werden muss, was allerdings die Optimierungsmöglichkeiten stark einschränkt.
Code: Alles auswählen
unsigned int SearchForString(char* base, unsigned int baseLength, char* target, unsigned int targetLength)
Re: Ein String im String suchen.
Verfasst: Do Jun 23, 2011 9:44 pm
von canlot
Ist greedy jetzt wenn man im gleichen wort 2 mal suchen darf?
Ich bin für den Nullbyte und die Textgröße soll auch möglichst groß sein.
Re: Ein String im String suchen.
Verfasst: Fr Jun 24, 2011 7:54 am
von Xin
canlot hat geschrieben:Ist greedy jetzt wenn man im gleichen wort 2 mal suchen darf?
Wie beschrieben: Das nächste gefundene Wort darf im bereits gefundenen Wort beginnen.
Ein nicht gieriger Algorithmus würde das gefundene Wort überspringen und dahinter weitersuchen.
Re: Ein String im String suchen.
Verfasst: Fr Jul 01, 2011 3:15 pm
von Xin
Ich push das hier nochmal... das Wetter ist immernoch zu gut, als das viele Leute aktiv würden, wie mir scheint.
canlot: Du legst die Bedingungen fest, dann kann's losgehen!
Re: Ein String im String suchen.
Verfasst: Mo Jul 04, 2011 6:40 pm
von nufan
Xin hat geschrieben:canlot: Du legst die Bedingungen fest, dann kann's losgehen!
Push ^^