2

標準英語アルファベットのすべての単語を含む MySQL データベースがあり、これを使用して単純な Scrabble 単語ジェネレーターを作成しています。データベースは 26 のテーブルに分かれています: アルファベットの各文字に 1 つずつ。各テーブルには次の 2 つの列が含まれます。

  • "Word" 列: この列は主キーであり、char(12) 型であり、null 値を受け入れません。
  • 「長さ」列: この列には符号なしの tinyint 値が含まれ、null 値は受け入れられません。

私のアプリケーションでは、ユーザーが任意の数の文字をテキスト ボックス (タイルを示す) に入力し、次のコードを使用してデータベースにクエリを実行します。

// this is looped over 26 times, and $char is a letter between 'A' and 'Z'
// check if the user entered in character $char or a blank tile (signified by ? in app)
// this check prevents me from having to query useless tables
if (in_array($char, $lettersArray) || $blanks)
{
    // if so, select all words that have a length that's possible to make
    $query = 'SELECT Word FROM '.$char.'Words WHERE Length <= '.strlen($letters);
    $result = $db->query($query);
    $num_results = $result->num_rows;

    for ($j = 0; $j < $num_results; $j++)
    {
        // determine if it's possible to create word based on letters input
        // if so, perform appropriate code
    }
}

すべてが機能していますが、私のアプリケーションは競合他社 (理論的な競合、つまり、これは私が自分で作成した学習プロジェクトであり、インターネット上でリリースすることはないと思います) に比べて時間がかかります。アプリケーションはローカル コンピューターにあります。phpMyAdmin の自動最適化機能を使ってみましたが、目立った速度向上は見られませんでした。

4

3 に答える 3

3

パフォーマンスの問題は実際にはデータベースではないと思います。データ ストアの構造は、アルゴリズムのパフォーマンスに最も大きな影響を与えます。

この問題に対するかなりわかりやすいアプローチの 1 つは、問題をアナグラムとして扱うことです。各単語のすべての文字をアルファベット順に並べ、それをインデックス付きの列として保存できます。

word      dorw
--------  -------
DALE      ADEL
LEAD      ADEL
LED       DEL
HELLO     EHLLO
HELP      EHLP

次に、一連の文字を指定して、一致するすべてのアナグラムをデータベースに照会できます。渡された一連の文字をアルファベット順に並べて、クエリを実行するだけです。

SELECT word FROM dictionary WHERE dorw = 'AERT'

RATE
TARE
TEAR

次に、文字のサブセットを照会できます。

SELECT word FROM dictionary WHERE dorw IN ('AER','AET','ART','ERT')

このアプローチでは、最も長い単語が最初に返されます。

これは最も効率的な方法ではありませんが、実行可能です。

「空白」のタイルを処理するのはより多くの作業になります。可能な文字を置き換える必要があり、1 つのクエリで 26 個すべての可能性のチェックを行うことができます。

たとえば、ABCDの文字と空白のタイルがある場合...

SELECT word FROM dictionary WHERE dorw IN ('AABCD','ABBCD', 'ABCCD'
 , 'ABCDD', 'ABCDE', 'ABCDE', 'ABCDF', ..., 'ABCDZ')

サブセットを扱い始めると、それはさらに苦痛になります...

(クロスワードパズルとジャンブルパズルでは、空白のタイルはありません)

したがって、これは Scrabble に最適なアルゴリズムではない可能性があります。

特に短い単語を最初に返す場合は、より効率的なアルゴリズムが他にもあります。

1 つのアプローチは、ツリーを構築することです。

ルート ノードは「ゼロ」文字の単語です。ルート ノードの子として、すべての 1 文字の単語のノードになります。各ノードは、それが有効な単語を表しているかどうかにかかわらずマークされます。これらのノードの子として、可能なすべての 3 文字の単語があり、有効かどうかが再度マークされます。

それは多くのノードになります。長さが 12 文字までの単語の場合、可能な合計スペースは1 + 26 + 26**2 + 26**3 + 26**4 + ...

ただし、可能なすべてのノードを保存する必要はありません。有効な単語になるブランチのみを保存します。以下にブランチはありません ->Z->Z または ->X->Q

ただし、->X->Y->L の下に分岐があります。XYL は単語ではありませんが、「XYLOPHONE」につながる分岐の始まりになります。

しかし、これはツリー トラバーサル アルゴリズムであり、根本的に異なります。

于 2012-07-07T04:55:16.040 に答える
2

indexについて学ぶ必要があるようです。データベースにインデックスを作成した場合、すべてのデータが 1 つのテーブルに含まれていたとしても、「無駄な文字」をクエリすることはありません。

ただし、mysql コンソールから実行した場合にクエリが結果を返すのにかかる時間、その結果をデータベースから PHP エンジンに移動するのにかかる時間など、さらに情報を提供する必要があります。たとえば、実行中の各クエリで 100 MB の結果セットを返す場合があります。その場合は、結果を最初の結果または可能な結果の数に制限します。

返されるデータの量を確認するには、コンソールでクエリの 1 つを手動で実行し、返されるレコードの数を確認します。数値が高い場合、データが PHP に渡されるのに時間がかかりますが、コードがより多くの結果を反復処理する必要があることも意味します。for受け入れることができる最初の単語を見つけたら、ループの削除を検討することをお勧めします。少なくとも 1 つの単語が可能な場合は、別の文字が配置されるまで再度チェックしないでください。

于 2012-07-07T04:15:19.703 に答える
1

この質問はデータベースの最適化に関するものですが、これを行う場合は、データベースに継続的にクエリを実行する代わりに、データベースから単語を1回だけ読み取り、データ構造を初期化してその構造を検索します。

これが完全に無関係だった場合は申し訳ありません。

于 2012-07-07T04:21:14.917 に答える