問題タブ [bisection]

リスト/タプルでバイナリ検索を実行し、見つかった場合はアイテムの位置を返し、そうでない場合は「False」(-1、なしなど) を返すライブラリ関数はありますか?

bisect モジュールで関数 bisect_left/right を見つけましたが、項目がリストにない場合でも位置を返します。それは意図した使用法ではまったく問題ありませんが、アイテムがリストにあるかどうかを知りたいだけです(何も挿入したくない)。

その位置にある項目が検索対象のものと等しいかどうかを使用しbisect_leftて確認することを考えましたが、それは面倒なようです (また、その数がリスト内の最大数よりも大きくなる可能性があるかどうかの境界チェックも行う必要があります)。もっと良い方法があれば、私はそれについて知りたいです。

編集これが必要な理由を明確にするために：辞書がこれに非常に適していることは承知していますが、メモリ消費をできるだけ低く抑えようとしています。私の意図する使用法は、一種の双方向ルックアップ テーブルです。テーブルに値のリストがあり、インデックスに基づいて値にアクセスできる必要があります。また、値がリストにない場合は、特定の値または None のインデックスを見つけられるようにしたいと考えています。

これには辞書を使用するのが最も速い方法ですが、メモリ要件が (約) 2 倍になります。

Python ライブラリで何かを見落としている可能性があると考えて、この質問をしていました。Moeが提案したように、私は自分のコードを書かなければならないようです。

Fluxboxウィンドウマネージャーのウィンドウ配置戦略をエミュレートする必要があります。

大まかなガイドとして、ランダムなサイズのウィンドウが一度に1つずつ画面に表示されることを視覚化します。各ウィンドウの大まかなサイズでは、ウィンドウが互いに重なることなく、画面上に平均80個のウィンドウが表示されます。

システムにFluxboxとXtermがインストールされている場合は、xwinmidiarptoy BASHスクリプトを試して、私が何をしたいかの大まかなプロトタイプを確認できます。それが何をするのか、そしてそれがどのように使われるべきかを説明する私がそれについて書いたxwinmidiarptoy.txtノートを見てください。

ウィンドウが閉じ、以前に閉じていたウィンドウが占めていたスペースが、新しいウィンドウの配置に再び使用できるようになることに注意することが重要です。

アルゴリズムは、「最初から入力全体を利用できるようにすることなく、入力がアルゴリズムに供給される順序で、シリアルに1つずつ」データを処理するオンラインアルゴリズムである必要があります。

Fluxboxウィンドウ配置戦略には、エミュレートしたい3つのバイナリオプションがあります。

• Windowsは水平行ま​​たは垂直列を作成します（潜在的に）

• ウィンドウは左から右または右から左に配置されます

• ウィンドウは上から下または下から上に配置されます

ターゲットアルゴリズムとウィンドウ配置アルゴリズムの違い

座標単位はピクセルではありません。ブロックが配置されるグリッドは128x128ユニットになります。さらに、配置領域は、グリッド内に配置された境界領域によってさらに縮小される場合があります。

なぜアルゴリズムが問題なのですか？

オーディオアプリケーションのリアルタイムスレッドの期限まで動作する必要があります。

現時点では、高速アルゴリズムの取得のみに関心があります。リアルタイムスレッドの影響と、それがもたらすプログラミングのすべてのハードルについては気にしないでください。

また、アルゴリズムが別のウィンドウと重なるウィンドウを配置することはありませんが、ユーザーは特定のタイプのブロックを配置および移動でき、重なるウィンドウが存在します。ウィンドウや空き領域を格納するために使用されるデータ構造は、この重複を処理できる必要があります。

これまでのところ、ルーズなプロトタイプを作成した2つの選択肢があります。

1）Fluxbox配置アルゴリズムのコードへの移植。

これに伴う問題は、アルゴリズムを使用して256ブロックの最悪のシナリオを配置しようとすると、クライアント（私のプログラム）がオーディオサーバー（ JACK ）から追い出されることです。このアルゴリズムは、256番目のウィンドウを配置するときにすでに配置されているブロックのリストの14000を超える完全な（線形）スキャンを実行します。

これをデモンストレーションするために、text_boxer-0.0.2.tar.bz2というプログラムを作成しました。このプログラムは、入力としてテキストファイルを受け取り、ASCIIボックス内に配置します。makeそれを構築するために発行します。コマンドラインオプションのリストには、少し不親切です--help（またはその他の無効なオプション）を使用してください。オプションを使用してテキストファイルを指定する必要があります。

2）私の代替アプローチ。

部分的にのみ実装されているこのアプローチでは、長方形の空き未使用スペースの各領域のデータ構造を使用します（ウィンドウのリストは完全に分離でき、このアルゴリズムのテストには必要ありません）。データ構造は、二重にリンクされたリスト（ソートされた挿入を含む）のノードとして機能し、左上隅の座標、および幅と高さを含みます。

さらに、各ブロックデータ構造には、4つの側面のそれぞれですぐ隣接する（接触する）各ブロックに接続する4つのリンクも含まれています。

重要なルール：各ブロックは、片側に1つのブロックのみと接触できます。これは、未使用の空きスペースを保存するアルゴリズムの方法に固有のルールであり、実際のウィンドウが互いに接触する可能性がある数には影響しません。

このアプローチの問題は、非常に複雑であるということです。1）ブロックの1つのコーナーからスペースを削除し、2）隣接するブロックを分割して、重要なルールを順守するという単純なケースを実装しました。

削除するスペースがボックスの列または行内でのみ検出される、それほど単純ではないケースは、部分的にしか実装されていません-削除するブロックの1つが幅（つまり列）または高さ（つまり行）その後、問題が発生します。また、これは幅1ボックスの列と、高さ1ボックスの行のみをチェックするという事実についても言及しないでください。

私はこのアルゴリズムをCで実装しました-このプロジェクトで使用している言語です（私は数年間C ++を使用しておらず、C開発にすべての注意を向けた後、それを使用するのは不快です、それは趣味です）。実装は700行以上のコードです（多くの空白行、中括弧行、コメントなどを含みます）。実装は、水平行+左右+上下配置戦略でのみ機能します。

したがって、この+700行のコードを他の7つの配置戦略オプションで機能させる方法を追加するか、これらの+700行のコードを他の7つのオプションで複製する必要があります。これらはどちらも魅力的ではありません。1つ目は既存のコードが十分に複雑であるため、2つ目は肥大化のためです。

機能が不足しているため、アルゴリズムはリアルタイムの最悪のシナリオで使用できる段階にさえありません。そのため、最初のアプローチよりも実際にパフォーマンスが良いか悪いかはわかりません。

このアルゴリズムのC実装の現在の状態はfreespace.cです。私はこれgcc -O0 -ggdb freespace.cをビルドして、少なくとも124x60文字のxtermサイズで実行するために使用します。

他には何があるの？

私はざっと目を通し、割引しました：

• ビンパッキングアルゴリズム：最適な適合に重点を置いているため、このアルゴリズムの要件と一致しません。

• 再帰的二分配置アルゴリズム：有望に聞こえますが、これらは回路設計用です。それらの重点は、最適なワイヤ長です。

これらの両方、特に後者では、アルゴリズムが開始する前に、配置/パックされるすべての要素がわかっています。

これについてどう思いますか？どのようにアプローチしますか？他にどのようなアルゴリズムを検討する必要がありますか？または、コンピュータサイエンス/ソフトウェアエンジニアリングを勉強したことがないので、どのような概念を調べればよいでしょうか。

さらに情報が必要な場合は、コメントで質問してください。

この質問をして以来、さらなるアイデアが生まれました

• 私の「代替アルゴリズム」と、配置する大きなウィンドウが空きスペースのいくつかのブロックをカバーするかどうかを識別するための空間ハッシュマップのいくつかの組み合わせ。

2x2の非線形問題を解くための2D二分法を実行するアルゴリズムが必要です。例：2つの方程式f(x,y)=0をg(x,y)=0同時に解きたい。私は1D二分法（および他の数値的方法）に非常に精通しています。解が境界x1 < x < x2との間にあることを私がすでに知っていると仮定しy1 < y < y2ます。

グリッドでは、開始境界は次のとおりです。

そして私は値f(A), f(B), f(C) and f(D)と同様に知っていますg(A), g(B), g(C) and g(D)。二等分線を開始するには、ポイントを中央だけでなくエッジに沿って分割する必要があると思います。

f(G)*f(M)<0 AND g(G)*g(M)<0今、圧倒されるかどうかをチェックするなどの組み合わせの可能性を検討しています。これを少し複雑にしすぎているかもしれませんが、ニュートンラプソン法を勾配演算子を使用して簡単に多次元化できるように、二等分線の多次元バージョンが必要だと思います。

手がかり、コメント、またはリンクを歓迎します。

二分法では、aとbの間の中点cを次のように計算する方がよいのはなぜですか。

単純なものの代わりに：

すべての変数は浮動小数点です。

特にPythonの場合、オンラインで見つけることができる二分法はありますか？

たとえば、これらの方程式が与えられた場合、二分法を使用してそれらをどのように解くことができますか？

どうすればいいのかわかりません。中点などを特定するループを作成する必要があることは理解しています

それから主に私はこれを持っています

Python では、並べ替えられたリストでしきい値を超える最初の値のインデックスをどのように見つけますか?

これを行う方法はいくつか考えられますが (線形検索、手書きの二分法など)、クリーンで合理的に効率的な方法を探しています。これはおそらくかなり一般的な問題なので、経験豊富な SO 担当者がお手伝いできると確信しています。

ありがとう！

以前はこれに問題がありましたが、今では何とか機能しています。

今、私は次の問題を抱えています。同じ関数で boost::bisect を呼び出す前に、メンバー関数に値をバインドする必要があります。かなり良いチュートリアルを見つけてそれに従いましたが、まだ何か間違っているようです。

最初に、次の作業を行うテストクラスを作成しました。

その後、「うまくいくと思ったのでその場で」バインディングを追加しました

その結果はエラーでした。エラー: 'boost::exception_detail::clone_impl >' のインスタンスをスローした後に終了が呼び出されました:bisect、検索するルートがないか、間隔に複数のルートがあります (f(min) = -0.0032916729090909091)。

とにかく、何らかの理由でバインディングを使用してメンバー関数として機能しない class::function があります。非メンバーとしてテストしましたが、動作します

平方根を見つけるための二分法アルゴリズムを考えてみましょう。すべてのステップは前のものに依存するため、私の意見では、それを並列化することはできません。私が間違っている？

二分探索のような同様のアルゴリズムも検討してください。

編集

私の問題は二等分ではありませんが、非常に似ています。私は単調関数を持っておりf(mu)、mu where を見つける必要がありf(mu)<alphaます。1 つのコアの計算f(mu)には 2 分かかり、非常に高い精度が必要です。約 100 コアのファームがあります。私の最初の試みは、コアを 1 つだけ使用してからf、 にどれだけ近づいたかに応じて、動的ステップで のすべての値をスキャンすることでしたalpha。今、私はファーム全体を使用したいのですが、私の唯一のアイデアは、f等間隔の点で 100 の値を計算することです。

二分法を使用して多項式の根を見つけている場合、場合によっては、多項式によっては、根が負または正になることがあります。

多項式の評価結果に基づいて、根が負になるか正になるかを判断できることは理解していますが、x として何を使用するかはわかりません。

誰かがここで洞察を与えることができますか?