写真提供:jimray
以前の awk の紹介記事で、awk は小さなワンライナーからいくつかの興味深いアプリケーションまで、あらゆるものに対して効果的なツールになり得ることを見てきました。状況に応じて、より複雑な言語を自由に使用できることは確かです。 perl と python が思い浮かびます。ネットワーク サポート、データベース アクセス、ユーザー インターフェイス、バイナリ データ、またはより広範なライブラリ サポートと複雑さを必要とするアプリケーションは、これらの分野でより優れたサポートを提供する他の言語に任せるのが最善です。
それにもかかわらず、awk は素晴らしい複雑なアルゴリズムとアプリケーションをテストするための言語 、特に問題がパイプの一部としてストリーミングできるチャンクに分割できる場合。ユビキタスであるため、シェルプログラミングの機能を拡張するための理想的なツールです。ほぼすべての Unix/Linux/BSD システムでなんらかの形で見られます。テキスト、ログ行、またはシンボル テーブルを扱う多くの問題は、UNIX/Linux システムにある他のツールと一緒に awk を使用して簡単に解決するか、少なくともプロトタイプを作成できます。
awk は、一度に 1 行ずつ入力を処理し、行ごとに出力を処理して送信するのに適していますが、すべての入力を読み取り、処理してから送信する従来のバッチ スタイルのアプリケーションでも使用できます。処理された出力以降。
さらに別の数独パズル ソルバー – Awk 用 YASPS
例として使用することを選択したアプリケーションは、「まだ別の数独パズルソルバー」です。最初に告白しなければならないのは、これらのパズルの 1 つを自分で解決するために腰を下ろしたことは一度もありませんでしたが、電車で通勤し、他の人が取り組んでいるのを見ながら、数日かけてこれをスケッチしたことです。実際にパズルを解くよりもはるかに楽しかったと思います..
Awk 用の YASPS プログラムをダウンロード:solve.awk
私が選択した入力形式は、awk で解析しやすく、Unix 環境ではかなり伝統的なものです。空白行とハッシュ (#) 文字で始まる行は無視されるため、コメントを簡単に挿入できます。読みやすくするために、列間に余分なスペースを使用できます。次の図に例を示します:
------------------------------------------------------------------------------- # I forget where I got this.. # this is one of the hardest ones I've found for this algorithm, although # after transposing the matrix it can be solved in a fraction of the time 2 0 0 6 7 0 0 0 0 0 0 6 0 0 0 2 0 1 4 0 0 0 0 0 8 0 0 5 0 0 0 0 9 3 0 0 0 3 0 0 0 0 0 5 0 0 0 2 8 0 0 0 0 7 0 0 1 0 0 0 0 0 4 7 0 8 0 0 0 6 0 0 0 0 0 0 5 3 0 0 8 -------------------------------------------------------------------------------
このプログラムにはエラー チェックはほとんどありませんが、前に、またはラッパー スクリプトの一部として簡単に追加できます。これは読者の演習として残しておきます。
このプログラムは、非常に単純な深さ優先の再帰バックトラッキング アルゴリズムを使用し、無効なエントリを事前に継続的に排除します。 awk には、perl や他の言語が持つ複雑なデータを表現する表現力がないかもしれませんが、注意すれば、中程度の大きさの問題やデータ セットを使用することができます。このアルゴリズムは最善のアルゴリズムではないかもしれませんが、ほとんどの問題に対して十分に高速であり、実装も簡単です。
どのような問題でも、データを効果的に表現すると、プログラムの設計作業がはるかに簡単になります。パズルの完成状態を「マスター」と呼ばれるマトリックスで表現しました。これは、何がどこにあるのかを記録し、最終的な出力を行う以外にはほとんど使用されません。
主な主力変数は、その他の 3 つの配列です。選択した再帰的な試行錯誤法から、試行回数の有効性を頻繁に確認する必要があることが直感的にわかります。そのプロセスを加速するために、行、列、および各領域の現在の状態を格納するための連想配列を維持しています (技術的には正しくありませんが、「象限」と呼びます)。これらは配列 R、C、および Q です (awk は大文字と小文字が区別されることに注意してください)。
ネストされた for ループや、頻繁に使用される事前計算値への再帰関数呼び出しから一般的な計算を除外しようとするときに役立つ場合があります。行、列の値を指定して象限番号を格納する「regmap」マトリックスでこれを試しましたが、この場合の時間の節約はあいまいであることがわかりました。コメントアウトしたままにしていますが、マイレージはさまざまで、この手法は非常に役立つことがよくあります。
多くの場合、再帰アルゴリズムは最適に設計されているため、トップダウン方式で記述されます。このプログラムの一番上の関数は「search()」と呼ばれ、問題データが配列に読み込まれた後、「END」パターンから呼び出されます。
大まかに言うと、search() は指定された行と列のパラメーターから開始し、チェックする次の空きスペースを探します。何もない場合、問題は解決されており、解決策が返されます。空のスペース (ゼロで表される) がある場合、mark() を使用して配列に数値を挿入し、呼び出して、使用可能な数値を (その行、列、または象限で使用されていない数値については inuse() 関数で) テストします。それ自体を再帰的に。再帰的 search() 関数がゼロを返す場合、それは失敗したことを意味するため、mark() 関数が再度呼び出されて試行番号のマークが解除されます。その後、可能性が尽きるか、search() 呼び出しが成功を返すまでループします。
多くの再帰アルゴリズムの美しさは、ソリューションに固有の優雅さと単純さです。それらは最速のアルゴリズムではない場合もありますが、多くの場合、「十分に高速」であり、設計が容易です。このプログラムは、ほとんどのパズルを数秒以内に解決します。このプログラムをさまざまなパズルで試しているときに気づいたことの 1 つは、問題が解決するのに長い時間がかかる場合 (数十秒)、単純に行列を転置すると、同じ解決策が数分の 1 秒で得られることが多いということです。今日のマルチコア CPU では、これは高速化の 1 つの可能性を示唆しています:行列の異なる転置でプログラムのいくつかのインスタンスを開始するラッパー スクリプトを記述します。上に示した前のパズルと、次の図の転置されたバージョンの例では、転置された問題が 4 倍速く解決されました。
------------------------------------------------------------------------------- marion:~/sudoku$ time awk -f solve.awk THE-HARDEST-SO-FAR.dat # Searches=134214 2 8 3 6 7 1 9 4 5 9 7 6 5 4 8 2 3 1 4 1 5 3 9 2 8 7 6 5 6 7 4 1 9 3 8 2 8 3 4 2 6 7 1 5 9 1 9 2 8 3 5 4 6 7 3 2 1 7 8 6 5 9 4 7 5 8 9 2 4 6 1 3 6 4 9 1 5 3 7 2 8 real 0m10.009s user 0m9.889s sys 0m0.024s marion:~/sudoku$ time awk -f solve.awk /tmp/transposed.dat # Searches=32253 8 3 4 7 9 2 6 1 5 2 1 9 6 5 8 7 3 4 7 6 5 4 1 3 8 2 9 3 4 6 5 7 9 2 8 1 5 2 8 3 6 1 9 4 7 1 9 7 8 2 4 3 5 6 9 8 1 2 4 7 5 6 3 4 5 2 9 3 6 1 7 8 6 7 3 1 8 5 4 9 2 real 0m2.487s user 0m2.456s sys 0m0.008s -------------------------------------------------------------------------------
さらに高速なものが必要な場合は、アルゴリズムを別の言語に翻訳して、データ セットをより直接的に表現することで実現できることがよくあります。このプログラムを一度 C に翻訳し、データの索引付けに興味深いひねりを加えました。このバージョンは、主にデータの表現方法により、おそらく数桁速く実行されます。おそらく、「C を使用したさらに別の数独パズル ソルバー」を別の記事としてリリースする予定です。
awk は、すべての人のツールキットに含まれるに値すると私は信じています。他の言語に比べて単純であることはおそらく弱点と見なされますが、私はそれを長所の 1 つと考えています。この言語は午後に学ぶことができ、日常の問題を解決するために参考書に頼ることなく使用できます。コマンドラインから、DSL (ドメイン固有言語) のコンパイラなどの実装まで、定期的に使用しています。
おすすめの Awk ブック
- Alfred V. Aho、Brian W. Kernighan、Peter J. Weinberger による AWK プログラミング言語。この言語の著者によるオリジナルの本には、適度に複雑なプログラムの優れた例がいくつかあり、今でも awk に関する私のお気に入りの本です。 Addison-Wesley 発行、1988 年。ISBN 020107981X。
- More Programming Pearls:Confessions of a Coder by Jon Bentley, AT&T Bell Labs, Murray Hill, NJ.アルゴリズムのプロトタイピング ツールとして awk を使用するための別の本は、More Pearls にあります。優れた読書。発行年:1988.ISBN:0201118890