問題タブ [algorithm]

• モデル チェックを使用したアプリケーションの種類は何ですか?
• どのモデル チェック ツールを使用しましたか?
• この手法を使用した経験、特に高品質のソフトウェアを提供する上での有効性を評価した経験をどのように要約しますか?

研究の過程で、 Spinを使用する機会があり、実際のモデル チェックがどの程度行われているか、組織がそれからどれだけの価値を得ているかについて興味をそそられました。私の実務経験では、ロジックに正式な検証を適用することは (当然のことながら) 考慮されていないビジネス アプリケーションに取り組んできました。SO の人々のモデル チェックの経験と、この件に関する考えについて本当に知りたいです。モデル チェックは、ツールキットに含める必要がある、より広く使用される開発プラクティスになるのでしょうか?

1 つのアプリケーション (Web ページの可能性があります) のスクリーンショットと以前に撮影したスクリーンショットを比較して、アプリケーションが正しく表示されているかどうかを判断したいと考えています。アスペクトが少し異なる可能性があるため (Web アプリの場合、ブラウザーによっては、一部の要素がわずかに異なる場所にある可能性があります)、完全一致の比較はしたくありません。スクリーンショットがどの程度似ているかを測定する必要があります。

すでにそれを行うライブラリ/ツールはありますか? どのように実装しますか？

プログラミングや特定の言語機能について、最も多く学んだアルゴリズムは何ですか?

私たちは皆、進化のはしごを数段上ったプログラマーによって書かれたアルゴリズムを最終的に理解することに基づいて、将来のための重要な教訓を突然知った、ただ知っている、という瞬間を経験したことがあります。誰のアイデアとコードがあなたに魔法のような影響を与えましたか?

緯度と経度で指定された 2 点間の距離を計算するにはどうすればよいですか?

明確にするために、距離をキロメートルでお願いします。ポイントは WGS84 システムを使用しており、利用可能なアプローチの相対的な精度を理解したいと思います。

バイナリ (+、-、​​|、&、*、/ など) 演算子、単項 (!) 演算子、および括弧を処理する単純なスタック アルゴリズムを使用して、方程式パーサーを開発しました。

ただし、この方法を使用すると、すべての優先順位が同じになります。演算子に関係なく左から右に評価されますが、括弧を使用して優先順位を強制できます。

したがって、現在 "1+11*5" は 60 を返します。予想される 56 ではありません。

これは現在のプロジェクトに適していますが、後のプロジェクトで使用できる汎用ルーチンが必要です。

明確にするために編集：

優先順位を付けて方程式を解析するための優れたアルゴリズムは何ですか?

実装が簡単で、利用可能なコードのライセンスの問題を回避するために自分でコーディングできることを理解することに興味があります。

文法：

文法の質問がわかりません - これは手書きで書いたものです。YACC や Bison を必要としないほど単純です。「2+3 * (42/13)」などの式で文字列を計算するだけです。

言語：

私はこれを C で行っていますが、言語固有のソリューションではなく、アルゴリズムに興味があります。C は低レベルなので、必要に応じて別の言語に簡単に変換できます。

コード例

上記で説明した単純な式パーサーのテスト コードを投稿しました。プロジェクトの要件が変更されたため、プロジェクトに組み込まれていないため、パフォーマンスやスペースのためにコードを最適化する必要はありませんでした。これは元の詳細な形式であり、容易に理解できるはずです。演算子の優先順位に関してさらに何かを行う場合は、プログラムの残りの部分と単純に一致するため、おそらくマクロ ハックを選択します。ただし、これを実際のプロジェクトで使用する場合は、よりコンパクトで高速なパーサーを使用します。

関連する質問

数学パーサーのスマートな設計?

-アダム

次のコードが Comparator の Javadoc で指定されたすべての条件を保証するかどうかはわかりません。

上記のコードは、そのクラスが Comparable を実装していない場合でも、クラスのすべてのインスタンスに完全な順序付けを課しますか?

私は実際に私の質問に対する答えを持っていますが、それは並列化されていないので、アルゴリズムを改善する方法に興味があります. とにかく、一部の人にとってはそのままで役立つかもしれません。

複数BitArrayの s とBitArray.And()を一緒に使用できますか?

2D 環境での衝突検出に使用するアルゴリズムまたは技術を説明している最良のリソース (書籍または Web ページ) は何だと思いますか?

より洗練された効率的なゲームを作成するためのさまざまなテクニックを学びたいと思っています。

単純な連絡先データベースがありますが、ユーザーが重複データを入力する際に​​問題が発生します。簡単なデータ比較を実装しましたが、残念ながら、入力されている重複データは完全に同じではありません。たとえば、名前のつづりが間違っているか、同じ人の1人が「BillSmith」を入力し、別の人が「WilliamSmith」を入力します。

それで、エントリが別のエントリにどれほど類似しているかのパーセンテージを与えることができるある種のアルゴリズムはありますか？

さまざまな XML ツール (パーサー、バリデーター、XPath 式エバリュエーターなど) のパフォーマンスが、入力ドキュメントのサイズと複雑さによってどのように影響を受けるかを知る必要があります。CPU 時間とメモリ使用量がどのように影響を受けるかを文書化したリソースはありますか? ドキュメントのサイズはバイトですか? ノード数？また、その関係は線形、多項式、またはそれより悪いものですか?

アップデート

IEEE Computer Magazine vol 41 nr 9、2008 年 9 月の記事で、著者は 4 つの一般的な XML 解析モデル (DOM、SAX、StAX、および VTD) を調査しています。彼らはいくつかの非常に基本的なパフォーマンス テストを実行し、入力ファイルのサイズが 1 ～ 15 KB から 1 ～ 15 MB に、または約 1000 倍大きくなると、DOM パーサーのスループットが半分になることを示しています。他のモデルのスループットには大きな影響はありません。

残念ながら、ノード数/サイズの関数としてのスループット/メモリ使用量など、より詳細な調査は行われませんでした。

記事はこちら。

アップデート

この問題の正式な扱いを見つけることができませんでした。参考までに、XML ドキュメント内のノード数をドキュメントのサイズ (バイト単位) の関数として測定する実験をいくつか行いました。私は倉庫管理システムに取り組んでおり、XML ドキュメントは典型的な倉庫ドキュメント (事前出荷通知など) です。

以下のグラフは、バイト単位のサイズとノード数の関係を示しています (これは、DOM モデルでのドキュメントのメモリ フットプリントに比例するはずです)。さまざまな色は、さまざまな種類のドキュメントに対応しています。スケールは log/log です。黒い線は青い点に最適です。興味深いことに、すべての種類のドキュメントで、バイト サイズとノード サイズの関係は直線的ですが、比例係数は大きく異なる可能性があります。

_{(ソース: flickr.com )}