|
Re: 9Live Buchstaben Salat-Spiel
Zitat:
|
Re: 9Live Buchstaben Salat-Spiel
So
ich habe sowas vor wenigen Wochen für sowas ähnliches gemacht. Und zwar habe ich ein Array mit 150k Wörtern die im Deutschen gebräuchlich sind und habe anschließend die Wörter verglichen Sodass es schnell geht habe ich alle "a" im eingabe-wort gezählt alle b usw dann das gleiche bei den Wörtern im array und wo eine übereinstimmung war, wurde es ausgegeben das ganze war in php, wird in Delphi aber bestimmt auch ganz gut gehen |
Re: 9Live Buchstaben Salat-Spiel
@vlees: Sowas macht das klar schneller. Um zu testen, ob ein Wort mit einem Buchstabensalat übereinstimmt, muß man nicht tausende Permutationen bilden. Bei mir mach ich es einfach so, das ich pro Buchstabe einen Flag setze, wenn alle gesetzt sind, passt es :)
|
Re: 9Live Buchstaben Salat-Spiel
Meine Funktion in einem lahmen PHP (XAMPP), der auf einem Intel Pentium III 933Mhz läuft, der irgendwie gaaaaaanz langsam ist, brauche ich 5 Sekunden um alle Wörter durchzugehen. Also wie auch der Jan sagte: es ist schnell! ;)
Hier mal mein Code: (Die Funktion um die Buchstaben zu zählen ist von PHP (ich glaube das ist schneller für PHP als eine eigene Schleife), aber es wäre sehr einfach sowas selber zu machen)
Code:
EDIT: in der list.php steht <? $wordlist = array(.......); ?>
<html>
<head> <title>Char-Sorter</title> <style type="text/css"> <!-- body { font-family: Tahoma; } --> </style> </head> <body> <?php $word = trim($_GET['word']); $word2 = count_chars($word, 1); include 'list.php'; echo 'Es sind [b]'. count($wordlist) .'[/b] Wörter in der Liste vorhanden. '; $possible = array(); $i = 0; while ($i < count($wordlist)) { if ($word2 == count_chars($wordlist[$i], 1)) { $possible[] = $wordlist[$i]; } $i++; } if (count($possible)) { echo 'Möglichkeiten: '; $i = 0; while ($i < count($possible)) { echo ($i + 1) .': [b]'. $possible[$i] .'[/b] '; $i++; } } $word2 = count_chars(strtolower($word), 1); $possible = array(); $i = 0; while ($i < count($wordlist)) { if ($word2 == count_chars($wordlist[$i], 1)) { $possible[] = $wordlist[$i]; } $i++; } if (count($possible)) { echo 'Möglichkeiten (kleingeschrieben): '; $i = 0; while ($i < count($possible)) { echo ($i + 1) .': [b]'. $possible[$i] .'[/b] '; $i++; } } $possible = array(); $i = 0; while ($i < count($wordlist)) { if ($word2 == count_chars(strtolower($wordlist[$i]), 1)) { $possible[] = $wordlist[$i]; } $i++; } if (count($possible)) { echo 'Möglichkeiten (verglichen mit kleingeschriebener Wortliste): '; $i = 0; while ($i < count($possible)) { echo ($i + 1) .': [b]'. $possible[$i] .'[/b] '; $i++; } } ?> </body> </html> |
Re: 9Live Buchstaben Salat-Spiel
zu Hagen: ist das ein DWAG oder ein DAWG
zur anfänglichen Frage: Du kannste jetzt z.B. den Code von mir nehmen und eine Wortliste aus dem Internet (ich habe eine die frei verfügbar ist, und eigentlich als Wörterbuch dient, ich habe sie aber missbracuht ;)) oder Hagens aus dem DAWG oder dem DWAG (wer weiß) Dann wartest du, bis 9Live/DSF/etc. wieder losgeht und dann rufst du da ann und nennst denen 50 Wörter! :P |
Re: 9Live Buchstaben Salat-Spiel
DAWG ist richtig, heist ja auch Directed Acyclic Word Graph -> gerichteter azyklischer Wörter Baum.
Übrigens enthält mein mitgeliefertes DAWG 200000 Wörter und alle diese Wörter zu durchsuchen, sprich die Suchmaske '*' zb. dauert 250 Millisekunden. Das ist aber der absolute Worstcase denn wer sucht schon ALLE Wörter auf einmal. Und so ergibt sich zb. bei der Suche aller Wörter die mit A anfangen eine Zeit von ca. 14 Millisekunden und er findet 21493 Wörter dabei. Das DAWG wird nun deutlich schneller je mehr man die Suchmaske einschränkt. Bei der Kombinatorischen Suche heist dies, das zb. bei 7 Buchstaben die gesucht werden sollen, im Durchschnitt weniger als 1 Millisekunde benötigt wird, es sind sogar meistens so um die 0,02 Millisekunden, sprich ca. 20 Mikrosekunden. 20 Mikrosekunden zu 5 Sekunden ist ein sehr deutlicher Unterschied in der Effizienz. In einigen Fällen benötigt man eine so enorme Performance, zb. wenn man Millionen von möglichen Kombinationen in einem Kreuzworträtzel oder bei einem Scrabble-Computer-Gegner pro Sekunde durchrechnen möchte. Also quasi in einer KI eines Wortbasierten Spieles. In Falle des Problemes hier dürfte aber das nicht so entscheidend sein. Ich möchte halt nur betonen das ein Vergleich zwischen meinem DAWG und einer simplen PHP Lösung ein Vergleich zwischen Äpfeln und Birnen sein muß, auch wenn beide Algorithmen im Endeffekt das gleiche Resultat liefern. Gruß Hagen |
Re: 9Live Buchstaben Salat-Spiel
dein programm ist bei mir langsamer dann deine werte. naja. mein php-server läuft ja auch nicht optimal
|
Re: 9Live Buchstaben Salat-Spiel
... langsamer sicher nur, weil der Hagen einen total schnieken und neuen Multiprozessor-Compi mit superviel RAM und einem getunten Betriebssystem hat - du aber nur eine 386er-Möhre mit 64MB RAM :mrgreen:
Fragt mich nicht woher ich es weiß, ich sage nur: Telepathie Was wir oft vergessen ist, daß die Laufzeit eines Programms zu einem nicht geringen Teil von der Prozessorleistung abhängt. |
Re: 9Live Buchstaben Salat-Spiel
Das ist schon richtig, bezieht sich aber NICHT auf die Komplexität eines Algorithmus ansich.
Das mein DAWG Algo. langsammer als eine Scriptsprache wie PHP sein soll die dann sogar noch einen Algo benutzt der von seiner Komplexität wesentlich schlechter sein muß, halte ich für ein Gerücht. Sorry das ich das so deutlich sagen muß, das hat nichts mit einem persönlichen Angriff zu tuen. Du sagst das du mit einem sortierten Array arbeitest. Gut, denn die Suchkomplexität in einem solchen Array ist O(ln n). Das ist defakto die gleiche Komplexität wie in einem Baum auf eine Node bezogen. Mit dem Unterschied das das Array[] als solches ja linear alle Einträge enthält der Baum aber linear alle Einträge zu einem Buchstaben. Somit ist die Gesamtkomplexität eines Suchbaumes abhängig von dem Alphabeth mit 256 Elementen mindestens 256 mal schneller als ein solches Array ! Das ist aber der Worstcase, denn in einer Wortliste werden ja nur 26+10 Buchstaben des Alphabeths tatsächlich benutzt. Wenn also bei einer Patternsuche oder kombinatorischen Suche in einem solchen Baum die Entscheidung für einen gefundenen Buchstaben gefallen ist so heist dies das alle nachfolgenden Kombinationen von vornherein 255/256'tel==99.6% aller Wörter ausgeschließen. Bei einem simplen sortierten Array ist dies nicht zwangsläufig der Fall. Nun das DAWG ist ein solcher Suchbaum, aber mit der besonderen Eigenschaft der zusätzlich hohen Komprimierung im Vergleich zu einem Array[]. Wie gesagt ich kann es mir nicht vorstellen das eine Scriptsprache wie PHP mit einem schlechteren Algorithmus schneller sein sollte als eine nativ kompilierte Anwendung die einen mathematisch besseren Algo verwendet. Sollte das tatsächlich der Fall sein so gibt es ein gewaltig großes Beben in meinem Glauben ;) Gruß Hagen |
Re: 9Live Buchstaben Salat-Spiel
Sag mal, ich bin ja nicht sooo fit in PHP, aber kann es sein das dein Code nur alle Wörter raussucht die zb. 7 Buchstaben enthalten ? Also wir haben 7 Buchstaben wie "AACDHIK" und suchen nun alle Wörter die exakt aus diesen 7 Buchstaben bestehen. Kann es sein das es deinem PHP Code schnuppe ist welche 7 Buchstaben gesucht werden und einfach alle Wörter mit 7 Buchstaben raussucht ??
Wenn ja, sind das Äpfel mit Birnen verglichen, denn meine kombinatorische DAWG Suche findet nur die Wörter die sich aus diesen 7 Buchstaben bilden lassen, also gültige Wörter ! Für eine Suche wie die deinige wäre es angebrachter einfach eine Listenstruktur zu benutzen die nach Anzahl der Buchstaben im Wort sortiert ist. Klar das der einfachste Fall eine Liste aus allen Wörtern mit zb. 7 Buchstaben wäre. In diesem Falle muß man garnichts mehr suchen sondern nur diese Liste komplett laden und als reguläre Antwort zählen. Gruß Hagen |
| Alle Zeitangaben in WEZ +1. Es ist jetzt 13:41 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz