問題タブ [algorithm]

私たちが取り組んでいるプロジェクトには、SO のものと同様の「評価」システムが必要です。ただし、私たちの場合、賛成票で「タグ付け」する必要がある複数のエンティティがあります（増分のように、賛成票のみで、反対票を投じることはありません）。エンティティの種類に関係なく、評価の高い順にすべてのエンティティを表示する必要がある場合があり、基本的には結果セットを混ぜ合わせていると思います。柔軟でスケーラブルであるように、これを実装するためにどのデータ構造/アルゴリズムを使用していますか?

他のすべての数字が正確に 2 回出現するリストで、1 回だけ出現する数字を見つけるための最適なアルゴリズムは何でしょうか。

したがって、整数のリスト (配列として取りましょう) では、各整数が 1 回を除いて正確に 2 回繰り返されます。それを見つけるには、最適なアルゴリズムは何ですか。

グラフィックスやオーディオの編集および処理ソフトウェアには、「ハイパス フィルター」および「ローパス フィルター」と呼ばれる機能が含まれていることがよくあります。これらは正確に何をし、それらを実装するためのアルゴリズムは何ですか?

例として次の文字列を取り上げます。

「クイックブラウンフォックス」

現在、quickのqは文字列のインデックス4（0から開始）にあり、foxのfはインデックス16にあります。ここで、ユーザーがこの文字列にさらにテキストを入力するとします。

「非常に速いダークブラウンのキツネ」

ここで、qはインデックス9にあり、fはインデックス26にあります。

ユーザーが追加した文字数に関係なく、元のqのインデックスをquickで、fをfoxで追跡する最も効率的な方法は何ですか？

言語は私には関係ありません。これは何よりも理論上の質問なので、一般的に人気のある現在の言語を維持するために、必要な言語を使用してください。

私が提供したサンプル文字列は短いですが、任意のサイズの文字列を効率的に処理できる方法を望んでいます。したがって、オフセットを使用して配列を更新すると、短い文字列で機能しますが、多くの文字に行き詰まります。

この例では、文字列内の一意の文字のインデックスを探していましたが、茶色のoや狐のoなど、さまざまな場所で同じ文字のインデックスを追跡できるようにする必要もあります。したがって、検索は問題外です。

時間とメモリの両方で効率的な答えが得られることを望んでいましたが、1つだけを選択する必要がある場合は、パフォーマンスの速度を重視します。

最小スパニング ツリー問題は、接続された重み付きグラフを取得し、グラフを接続したまま (結果として非循環グラフが生成される) で、合計重みが最小のエッジのサブセットを見つけることです。

私が検討しているアルゴリズムは次のとおりです。

• すべてのサイクルを見つけます。
• 各サイクルから最大のエッジを削除します。

このバージョンの推進力は、反復的な構造を持たない「ルールの満足」に制限された環境です。また、非常に並列なハードウェア (つまり、サイクル数より数倍の並列度が期待されるシステム) にも適用できる場合があります。

編集:

上記はステートレスな方法で行われます (どのサイクルでも最大のエッジではないすべてのエッジが選択/保持/無視され、その他はすべて削除されます)。

Perl スクリプトを作成していて、n 分木のデータ構造を使用したいと考えています。

(Perl ライブラリの一部ではなく) ソース コードとして利用できる優れた実装はありますか?

これは「本当の」質問ではないことを申し訳ありませんが、疑似ランダムだけでなく、真の乱数を生成するためにランダマイザーをランダムにランダム化することについての投稿をここで見たことを覚えています。探しても見当たりません。

その記事について知っている人はいますか？

N x Mグリッド上に、1つのパスがあり、行き止まりがたくさんある単純な迷路が必要だとしますが、それは「正しい」ように見えます（つまり、小さな行き止まりがあまり多くなく、誰かが手作業で作ったように見えます。 ）。これを行うための既知の方法はありますか？

実験するために、私は（ずっと前に）コンウェイのライフゲームを実装しました（そして、この関連する質問を知っています！）。

私の実装は、「最後の状態」と「更新中の状態」を表す2つのブール値の配列を保持することで機能しました（2つの配列は各反復で交換されます）。これはかなり高速ですが、これを最適化する方法についてよく疑問に思います。

たとえば、1 つのアイデアは、反復 (N+1) で変更できるゾーンを反復 N で事前計算することです (そのため、セルがそのようなゾーンに属していない場合、そのセルは変更の対象とは見なされません)。反復 (N+1))。これが非常に漠然としていることは承知しており、詳細に入る時間はありませんでした...

Game of Life のイテレーションを (速度のために) 最適化する方法についてのアイデア (または経験!) はありますか?

ステートマシンが最も適しているプログラミングの問題は何ですか?

ステート マシンを使用して実装されているパーサーについて読んだことがありますが、ステート マシンとして実装することを叫んでいる問題について知りたいと思います。