Hallo zusammen,
da ich aktuell C lernen möchte habe ich versucht ein Programm zu
schreiben das mich bei dem Spiel 4Bilder1Wort "unterstützt".
Zunächst werden alle vorgeschlagenen Zeichen eingelesen und in einem
Array gespeichert. Anschließend wird die Länge des Lösungswortes
abgefragt und gespeichert um die möglichen Lösungen einzugrenzen. Der
eigentliche Algorithmus prüft zunächst ob, das aus einem Wörterbuch
geholte Wort, der gewünschten länge entspricht. Ist dies der Fall wird
geprüft ob das Wort mit den vorhandenen Zeichen dargestellt werden kann.
Sind beide Bedingungen (Länge und mögliche Zeichen) erfüllt wird das
Wort als möglicher Lösungsvorschalg ausgegben.
Mein Problem ist, das mein Wörterbuch mit knapp 30000 Worten zu
umfangreich ist. So werden z.b bei einem Alphabet [snmnzenluyie] 59
mögliche Lösungen bei einer Wortlänge von 5 Zeichen gefunden. Das ist
zwar nicht sooo viel, aber ich würde das dennoch gerne optimieren, da
bei größerer Wortlänge auch die Anzahl möglicher Lösungen steigt.
Eventuell findet sich jemand der das Projekt interessant findet und es
weiter entwickeln möchte bzw. eine, für das Spiel optimierte Wortliste
hat.
Hat das Wort 5 Buchstaben, müssen die Stellen 0..4 getestet werden. Du
testest aber auf 6 Zeichen, nämlich 0..5. Das geht hier nur
zufälligerweise gut, da natürlich jeder C-String auch einen Terminator
'\0' hat. Der Test darauf ist aber überflüssig und kann in einem anderen
Kontext sogar problematisch werden.
Schreibe daher:
1
for(i=0;i<strlen(string);i=i+1){
Also < statt <=. Außerdem kannst Du i = i + 1 bei der Gelegenheit zu i++
vereinfachen.
Merke: Immer wenn Du einen Index von 0 an laufen lässt, musst Du
anschließend zu 95% auf < und nicht <= testen. Wenn ich so eine Zeile
sehe, geht da automatisch der Alarmknopf im Kopf an. Solche
Programmstellen sind meist Kandidaten für Buffer-Overflows.
Ich habe da aber noch ein Verständnisproblem. Nehmen wir mal an, das
eingegebene Wort wäre:
aeeef
Nach der Programmlogik würde das Programm auch das Wort
aaaef
im Wörterbuch finden. Ist das so richtig? Das Programm testet nämlich
nicht die Anzahl gleicher Buchstaben.
EDIT:
Hier ist noch ein dicker Programmfehler in:
1
char*cleanString(charstring[]){
2
chartemp[MAXLEN];
3
...
4
returntemp;
5
}
Das Array temp ist eine Autovariable und wird mit dem Verlassen der
Funktion zerstört. Ein Pointer darauf zurückzugeben ist höchst
fahrlässig, da er auf einen nicht definierten Speicherbereich zeigt.
Spätestens dann, wenn anschließend weitere Funktionen mit Autovariablen
aufgerufen werden, bekommst Du undefinierte Zeichen zurück.
Schreibe also:
1
staticchartemp[MAXLEN];
Dann lebt die Variable über die ganze Programmlebenszeit. Beachte aber,
dass nach einem weiteren Aufruf von cleanString() Du den vorherigen
Inhalt verlierst.
Warum machst Du nicht den toupper-Call und das Abschneiden von CR und LF
nicht direkt im übergebenen Array string[]? Das spart auch den
anschließenden strcpy().
Also so:
1
voidcleanString(charstring[])
2
{
3
inti;
4
5
for(i=0;string[i];i++)
6
{
7
if(string[i]=='\n'||string[i]=='\r')
8
{
9
break;
10
}
11
string[i]=toupper(string[i]);
12
}
13
14
string[i]='\0';
15
}
Aufruf ohne strcpy:
1
cleanString(string);
P.S. Die Variable i bei der Definition mit 0 zu initialisieren und
anschließend in der for-Schleife nochmals auf 0 zu setzen ist
überflüssig. Ebenso kann man den Vergleich string[i] != '\0'
vereinfachen, siehe oben.
Die Funktion ist nun vom Typ void, da sie keinen Zeiger mehr
zurückliefern muss. Der anschließende strcpy-Aufruf entfällt.
Die gleiche Aufgabe habe ich auch schon einmal in Python umgesetzt.
Dabei hatte sich bei mir bewährt das Wörterbuch aufzuteilen um die zu
untersuchende Datenmenge zu reduzieren.
Konkret bedeutet dies alle Wörter mit der Länge n in der Datei WB-n.txt
abzuspeichern. Da die Länge deines Lösungswortes bekannt ist, kannst du
direkt die richtige Teilmenge durchsuchen.
Noch eine Bemerkung zu cleanString(). Wenn man mit Pointern arbeitet
statt der Array-Schreibweise, spart man auch noch die Variable i ein.
Außerdem kann der mehrmalige Speicherzugriff schneller werden, wenn der
Compiler das nicht ohnehin optimiert.
Daher Vorschlag:
Hallo und danke erstmal für die Verbesserungsvorschläge.
@Frank M.
1
for(i=0;i<=strlen(string);i=i+1)
+-1 Fehler passieren mir immer mal wieder
>Außerdem kannst Du i = i + 1 bei der Gelegenheit zu i++ vereinfachen.
Ich persönlich finde es einfacher lesbar i = i + 1; zu schreiben. Klar
muss man mehr tippen aber ich finds schöner ist halt geschmackssache.
Oder bringt i++; noch andere Vorteile?
>Ich habe da aber noch ein Verständnisproblem. Nehmen wir mal an, das>eingegebene Wort wäre:>aeeef>Nach der Programmlogik würde das Programm auch das Wort>aaaef>im Wörterbuch finden. Ist das so richtig? Das Programm testet nämlich>nicht die Anzahl gleicher Buchstaben.
Ja das stimmt, ich habs behoben indem ich das Zeichen (wenn es gefunden
wurde) durch eine '0' ersetzte. Die kann in keinem Wort vorkommen also
kann auch kein Buchstabe mehr doppelt verwendet werden.
1
char*cleanString(charstring[]){
2
chartemp[MAXLEN];
3
...
4
returntemp;
5
}
für mich als Anfänger unmöglich selbst zu erkennen, danke für den
Hinweis
>Warum machst Du nicht den toupper-Call und das Abschneiden von CR und LF>nicht direkt im übergebenen Array string[]? Das spart auch den>anschließenden strcpy().
Sehr guter Punkt, hab ich einfach nicht bedacht bzw. zu wenig drüber
nachgedacht und zu viel gefreut das es einfach funktioniert hat ;-)
>P.S. Die Variable i bei der Definition mit 0 zu initialisieren und>anschließend in der for-Schleife nochmals auf 0 zu setzen ist>überflüssig.
ja das ist richtig, aber ich hab mir angewöhnt Variablen bereits bei der
deklaration zu initialisieren und mal abgesehen von ein paar wenigen
Prozessortakten die verloren gehen gibts ja keinen Nachteil oder?
1
voidcleanString(char*string)
2
{
3
while(*string)
4
{
5
if(*string=='\n'||*string=='\r')
6
{
7
break;
8
}
9
10
*string=toupper(*string);
11
string++;
12
}
13
14
*string='\0';
15
}
Hab deine Funktion mal zusätzlich eingefügt. Als Anfänger drückt man
sich halt gern um Pointer zumindest da wo mans selber erkennt ;-)
@NoName
Auch eine gute Idee, das Problem ist aber nicht die Laufzeit, sondern
das die Wortliste nicht auf 4Bilder1Wort optimiert ist und man so sehr
viele Lösungsmöglichkeiten bekommt.
student schrieb:>>Außerdem kannst Du i = i + 1 bei der Gelegenheit zu i++ vereinfachen.>> Ich persönlich finde es einfacher lesbar i = i + 1; zu schreiben. Klar> muss man mehr tippen aber ich finds schöner ist halt geschmackssache.> Oder bringt i++; noch andere Vorteile?
Ja, es ist lesbarer, da du nicht schauen must, ob da noch ein j oder l
(kleines L) oder Fliegendreck im Spiel ist.
Den Rest macht der Compiler.
student schrieb:> ja das ist richtig, aber ich hab mir angewöhnt Variablen bereits bei der> deklaration zu initialisieren und mal abgesehen von ein paar wenigen> Prozessortakten die verloren gehen gibts ja keinen Nachteil oder?
Das ist zum einen eine Definition und Prozessortakte gehen auch nicht
verloren, wenn der Compiler optimieren darf.
student schrieb:> Ich persönlich finde es einfacher lesbar i = i + 1; zu schreiben. Klar> muss man mehr tippen aber ich finds schöner ist halt geschmackssache.> Oder bringt i++; noch andere Vorteile?
Ja, du machst es nicht anders wie 99% aller erfahrener Programmierer.
Der resultierende Code dürfte bei modernen Compilern ziemlich der
gleiche werden.
'++' ist ein unärer Operator, ein '+' und das '=' ist ein binärer
Operator und eine Zuweisung und damit ein deutlich komplexerer Ausdruck.
Benutze die Operatoren die die Programmiersprache dir bietet.
student schrieb:> +-1 Fehler passieren mir immer mal wieder
Die Fehler, die Du gemacht hast, sind eigentlich typische
Anfängerfehler. Da sind die meisten schon reingetappt. Trotzdem ist eine
gewisse Selbstdisziplin bei C unumgänglich, denn durch die vielen
"Freiheiten", die C bietet, kann man auch schnell Murks programmieren.
Das rächt sich dann irgendwann.
> Ich persönlich finde es einfacher lesbar i = i + 1; zu schreiben. Klar> muss man mehr tippen aber ich finds schöner ist halt geschmackssache.
Heutzutage ist das wirklich Geschmackssache. Vor 30 Jahren war das noch
anders. Da optimierten die Compiler nicht so gut und ein i++ verstand
man damals als Tipp an den Compiler: "Benutze das Increment des
Prozessors!". Mittlerweile macht das keinen Unterschied. Beide Varianten
ergeben denselben Maschinencode.
> Ja das stimmt, ich habs behoben indem ich das Zeichen (wenn es gefunden> wurde) durch eine '0' ersetzte.
Gute Lösung!
> für mich als Anfänger unmöglich selbst zu erkennen, danke für den> Hinweis
Auch das ist ein typischer Anfängerfehler. Erst bemerkt man den Fehler
nicht (es läuft ja!), aber wenn das Programm dann größer ist, bekommt
man Murks aus dem Speicher geliefert. Das Problem: Man sucht dann den
Fehler in den letzten Änderungen... und sucht sich dann einen Wolf, weil
der Fehler eigentlich schon immer im Programm war. Bei Dir trat das
Problem nicht auf, weil Du den strcpy() jedesmal unmittelbar nach dem
cleanString-Call aufgerufen hast. Sobald da nur eine Funktion mit
Autovariablen durch eine spätere Änderung dazwischen aufgerufen worden
wäre, wäre der Speicherbereich, auf den der Pointer zeigte, vollkommen
undefiniert.
> Sehr guter Punkt, hab ich einfach nicht bedacht bzw. zu wenig drüber> nachgedacht und zu viel gefreut das es einfach funktioniert hat ;-)
Es gibt sehr oft einen kürzeren Weg ;-)
Aber Kompliment: Als Anfänger schlägst Du Dich schon ganz gut.
> ja das ist richtig, aber ich hab mir angewöhnt Variablen bereits bei der> deklaration zu initialisieren und mal abgesehen von ein paar wenigen> Prozessortakten die verloren gehen gibts ja keinen Nachteil oder?
Es ist sicher nicht verkehrt, Autovariablen auch direkt mit einem
vernünftigen Wert zu initialisieren.
Solche Doppelzuweisungen:
1
inti=0;
2
for(i=0;...)
optimieren moderne Compiler auch locker weg. Daher ist es nicht falsch,
so vorzugehen. Denn damit stehst Du auf der sicheren Seite.
Ich sehe das mittlerweile nach über 30 Jahren C-Programmierung aber
anders: Ich initialisiere nur Variablen, die auch initialisiert werden
müssen. Ich will damit nicht Prozessortakte einsparen, sondern klar
zum Ausdruck bringen, dass diese Variable erst später im Verlauf auf
einen definierten Wert gesetzt wird, wobei dieser u.U. erst später durch
den Kontext bekannt wird. Dasselbe mache ich mit solchen
Scratch-Variablen wie z.B. dieses i. Das erscheint auf den ersten Blick
fehleranfälliger, ist bei diszipliniertem Programmieren aber kein
Problem.
Bei der Gelegenheit: Benutze besser Variablennamen, die mindestens 3
Buchstaben lang sind. Bekommt eine Variable wie "i" mal später eine
andere Bedeutung und möchtest Du sie umbenennen, ist es so gut wie
unmöglich, diese Variable durch Replace-Global-Befehl im Editor
umzubenennen. Hieße die Variable eher "idx", wäre das weniger ein
Problem.
> Hab deine Funktion mal zusätzlich eingefügt. Als Anfänger drückt man> sich halt gern um Pointer zumindest da wo mans selber erkennt ;-)
Ja, kann ich verstehen. Man sollte sich trotzdem möglichst früh an
Pointer gewöhnen - auch wenn diese eher nur früher, als die Compiler
noch nicht so gut optimierten, einen Geschwindigkeitsgewinn brachten.
Das ganze erscheint einem (nach Gewöhnung an die vielen Sternchen) doch
irgendwann lesbarer. Ausserdem läuft man so weniger Gefahr, zwei
Indexvariablen innerhalb einer Funktion mal zu velwechsern.
Weiterhin viel Spaß mit C!
student schrieb:> Ich persönlich finde es einfacher lesbar i = i + 1; zu schreiben. Klar> muss man mehr tippen aber ich finds schöner ist halt geschmackssache.> Oder bringt i++; noch andere Vorteile?
Es ist, insbesondere in Schleifen, einfach ein "C(C++, Java, C#,
...)-Idiom". D.h., fast jeder, der sich seit zumindest ein paar Tagen
mit einer dieser Programmiersprachen beschäftigt hat, wird i++ oder ++i
schreiben und bei "i = i + 1" u.U. zweimal hinsehen. Ich persönlich
benutze in solchen Fällen die "übliche" Variante, falls es keinen
triftigen Grund dagegen gibt.
Außerdem muss man sich bei ++i nicht umgewöhnen, wenn man eine der
Sprachen verwendet, in denen es tatsächlich einen Unterschied machen
kann, ob man "x = x + 1" bzw. x++ oder ++x schreibt (wenn auch nicht bei
ints und anderen primitiven Typen).