問題タブ [non-deterministic]

決定論的である必要がある大規模で複雑な関数があります。これは当社の主力製品の 1 つであり、大量のコードをカバーしています。このコードは、Python の dict イテレータが原因で非決定論的になることがよくあります。これは何度も発生しており、追跡するのは非常に難しく、すぐに気付かないこともよくあります。非決定性を検出する自動テストを作成したいのですが、その方法がわかりません。

関数をループで実行してみましたが、テスト結果は常に同じですが、関数が非決定論的であっても、dict イテレータの順序が任意ではあるがある程度一貫しているため、関数がこのテストに合格する場合があります。

この種のバグをキャッチする自動テストを作成する方法はありますか?

おそらく、このテスト中に反復子が任意ではなくランダムになるように python の dict をハックする方法はありますか? そうすれば、関数を繰り返し呼び出すと発散する可能性が高くなりますか? これはかなり複雑な方法のように思えますが、他の方法は考えられません。

編集：

現在、Python 2.7 を使用しています。

さまざまなサブモジュールの単体テストがありますが、dict 順序の恣意的ではあるが一貫した性質のために、非決定性が明らかにならないことがよくあります。

また、おそらく非決定論的というのは、この問題を説明する正しい方法ではありません。この関数は {id : data} を取りますが、id の値はコードの結果に影響を与えるべきではありませんが、Python dict の順序付けにより、影響を受ける場合があります。おそらく、これをテストする最善の方法は、ID をランダムな値に置き換え、異なる ID で何度も実行した後に出力が同じかどうかを確認することです。

List モナドを使用して非決定論的計算を行う方法を理解するという困難を乗り越えました。しかし、私のアルゴリズムは List モナドから得られる深さ優先検索ではなく、幅優先検索の恩恵を受けると思います。

これは、私のアルゴリズムの興味深い部分を示す抜粋です。ロジックパズルあかりのソルバーです。

基本的に、いくつかの基本的な決定論的ルールを適用して、それが解決するかどうかを確認します。なければライトをいろいろなところに置いてみます。解決するために再帰した後、ライトがパズルを矛盾させる場合、ライトがあった場所に除外マークを配置して続行します。ライトの配置中に解決策が見つかった場合は、それらを解決策のリストに追加します。

これは問題なく動作しますが、多くの場合、推測する座標の明らかな選択があり、すぐに一貫性のないパズルになり、1 つ (または 2 つ) の検索レベルで x を配置できるようになるため、遅くなります。検索の途中までその座標を選択すると、最初に興味のないものをたくさん噛んでしまいます。したがって、幅優先検索のアイデアです。

「幅優先非決定性モナド」などをグーグルで検索したところ、次のような理解しにくい結果がいくつか得られました。

• Control.Monad.Omegaこれは、私には当てはまらない無限に発散する決定論を防ぐように見えるため、私が必要としているものにはやり過ぎのように思えますが、私はそれを完全には理解していません。

• Control.Monad.WeightedSearch Control.Monad.Omega のドキュメントでは、モナドとして使用する場合は代わりにこれを使用することを提案していますが、重み付けも私のニーズには少しやり過ぎだと思います。1 つは解決策のあるもの用で、もう 1 つは解決策がないもの用です。

• Control.Monad.Levelツリーの葉だけが値を持っているので、これが私が望むものに対してうまくいくとは思いません。

• Data.Treeこれは私が使いたいものかもしれないと思いますが、美しい方法があるように感じますが、それを使用するために List モナド コードを変換する方法がわかりません。

私の次の質問は、それを並列化する方法についてです:)

NDTM は初めてですが、チューリング マシンの概念は理解しています。NDTM に関しては少し混乱します。言語 {a,b,c} の NDTM を開発することになっており、

最初に知りたいのは、L の読み方、たとえば Ǝ の意味です。NDTM は、たとえば a のように、1 つの結果の 2 つの可能性を与えることを理解しています。

私はキャリパーベースのテンプレートhttps://github.com/dcsobral/scala-foreach-benchmarkを何年も喜んで使用してきました。ランダムに構築された問題を複数回実行し、平均消費時間を計算します。

今、私は非決定論的アルゴリズムに直面しています。そのため、実行時間と結果のフィットネスの両方を知る必要があります。平均的なシナリオと最悪のシナリオの両方の特性を測定できる Java/scala ベンチマーク フレームワークを探しています。

非決定論的とは、アルゴリズムが何らかの乱数発生器に依存して決定を行うことを意味します。以前は、最適に近いソリューションを見つけていましたが、最適なソリューションを検索するには多くのプロセッサ時間が必要でした。たとえば、TSP 問題の解決策。

適合度とは、最適化プロセスのコスト関数を意味します。異なる実行 (異なるランダム シードを使用) では、異なるコストが発生する場合があります。そのため、実行時間だけでなく、コスト値 (フィットネス) を安定させる必要があります。

実行時間の変動が許容範囲内であることを示すまで関数を繰り返し呼び出すことがベンチマーク フレームワークの一般的な機能であるかどうかはわかりませんが、キャリパーはそうです。より高度で、時間以外の適合性を処理できる同様のフレームワークを探します。

私が実装している検索アルゴリズム (単純な半順序プランナー) には、呼び出しごとにいくつかの選択肢しかありません。理想的には、可能性を遡って最初に見つかったソリューションを返すようにしたいと考えています。

次の Haskell コードを検討してください。

これにより、次の出力が生成されます。

ただし、代わりに次の出力を生成したいと思います。

これは、JavaScript のような非純粋な言語で簡単に実行できます。

Haskellで同じことをどのように行いますか?

muZ3 リレーション仕様で非決定論的に再帰呼び出しを実行する方法はありますか? 具体的には、次のような関数を翻訳したいと思います。

muZ3 ルール形式に。

暗号化されたクエリ パラメータを含むリンクをユーザーに提供する必要がある Groovy アプリケーションに取り組んでいます。現在、すべてのリンクに同じ IV を使用する AES 暗号化アルゴリズムを使用しています。これが悪いことであることはわかっています (したがって切り替えたい理由です) が、これが行われた理由は、クエリ パラメーターのサイズを制限するためでした (各クエリ パラメーターに base64 でエンコードされた 16 バイトの初期化ベクトルを含めると、リンクが非常に長くなります)。非決定論的アルゴリズムに切り替えて、クエリ データに必要なランダム性を持たせながら、クエリ パラメータに IV を格納する必要がないようにしたいと考えています。

Groovy を使用しているため、Java から何でも使用できます。暗号化作業はあまり行っていませんが、どのアルゴリズムを調べ始めればよいかわかりません。理想的には、Java SE で利用できるものか、自由に使用できる Java ライブラリが必要です。また、これらのアルゴリズムを実装する方法に関する詳細へのリンクも高く評価されています。