問題タブ [in-place]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
ruby-on-rails - Railsでのリッチテキスト編集に最適なオプションは何ですか?
管理者が指示を変更できるように、フォームでリッチ テキスト編集を使用したいと考えています。これを行うための最良のオプションは何ですか?
[より明確に言うと、管理者は技術者ではありませんが、マークアップを使用せずに、またはできるだけ少ないマークアップで書式設定を制御したい場合があります。私が望むのは、いくつかの書式設定コントロールを備えた RTE を使用してすべての AJAXy をインラインで編集し、送信して、ページを変更せずにエンド ユーザーに指示がどのように表示されるかを確認できるようにすることです。
特にプラグインに関しては、どの Rich Test Editing プラグインが Rails での使用に最適かを知りたいです。最も簡単に実装でき、最も明確な API、最も使いやすいインラインなど...]
c++ - char* の配列をソートする簡単な方法はありますか? C++
ファイルに の配列がchar*あります。私が働いている会社では、データをフラット ファイルに保存しています。データが並べ替えられている場合もあれば、そうでない場合もあります。ファイル内のデータを並べ替えたい。
これで、これを行うコードを最初から書くことができました。もっと簡単な方法はありますか？
もちろん、その場での並べ替えが最適なオプションです。私は大きなファイルを扱っていて、RAM がほとんどありません。しかし、私はすべてのオプションを検討します。
すべての文字列は同じ長さです。
これはいくつかのサンプルデータです:
これは、長さ 28 の 3 つのレコードを表します。アプリは長さを認識しています。各レコードは CRLF ( \r\n) で終わりますが、この並べ替えには関係ありません。
algorithm - インプレース基数ソート
これは長文です。我慢してください。要約すると、問題は次のとおりです。実行可能なインプレース基数ソートアルゴリズムはありますか?
予備
文字「A」、「C」、「G」、「T」のみを使用する小さな固定長の文字列が大量にあり(そう、ご想像のとおり: DNA )、それらを並べ替えます。
現時点では、 STLのすべての一般的な実装で、std::sortwhich uses introsortを使用しています。これは非常にうまく機能します。しかし、基数ソートは問題セットに完全に適合し、実際にははるかにうまく機能するはずだと確信しています。
詳細
私はこの仮定を非常に単純な実装でテストしましたが、比較的小さな入力 (10,000 のオーダー) の場合、これは真実でした (まあ、少なくとも 2 倍以上高速でした)。ただし、問題のサイズが大きくなると ( N > 5,000,000)、実行時間は大幅に低下します。
その理由は明らかです。基数ソートでは、データ全体をコピーする必要があります (実際には、私の単純な実装では複数回)。これは、メイン メモリに最大 4 GiB を入れたことを意味し、明らかにパフォーマンスが低下します。そうでなかったとしても、実際には問題のサイズがさらに大きくなるため、これほど多くのメモリを使用する余裕はありません。
ユースケース
理想的には、このアルゴリズムは、DNA と DNA5 (追加のワイルドカード文字「N」を許可する)、またはIUPAC 曖昧コードを含む DNA (結果として 16 の異なる値) に対して、2 から 100 の間の任意の文字列長で動作する必要があります。ただし、これらすべてのケースをカバーすることはできないことを認識しているため、速度が向上したことに満足しています。コードは、どのアルゴリズムにディスパッチするかを動的に決定できます。
リサーチ
残念ながら、基数ソートに関するウィキペディアの記事は役に立ちません。インプレース バリアントに関するセクションは完全にゴミです。基数ソートに関するNIST-DADS セクションはほとんど存在しません。アルゴリズム「MSL」を説明するEfficient Adaptive In-Place Radix Sortingという有望な論文があります。残念ながら、この論文も残念です。
具体的には、次のようなものがあります。
まず、アルゴリズムにはいくつかの誤りがあり、多くのことが説明されていません。特に、再帰呼び出しについては詳しく説明していません (現在のシフト値とマスク値を計算するために、ポインターをインクリメントまたは削減すると仮定しています)。また、関数dest_groupanddest_addressを定義せずに使用します。これらを効率的に実装する方法がわかりません (つまり、O(1) では、少なくともdest_address自明ではありません)。
最後になりましたが、このアルゴリズムは、配列インデックスを入力配列内の要素と交換することにより、インプレース性を実現します。これは明らかに数値配列でのみ機能します。文字列で使用する必要があります。もちろん、強力な型付けを台無しにして、インデックスが属していない場所にインデックスを格納することをメモリが許容できると仮定して先に進むこともできます。しかし、これは、文字列を 32 ビットのメモリに圧縮できる場合にのみ機能します (32 ビット整数を想定)。それはわずか 16 文字です (16 > log(5,000,000) であることは今のところ無視しましょう)。
著者の 1 人による別の論文では、正確な説明がまったく提供されていませんが、MSL のランタイムがサブリニアであり、完全に間違っています。
要約すると、動作する参照実装、または少なくとも DNA 文字列で動作する動作中の基数ソートの適切な疑似コード/説明を見つける希望はありますか?
java - インプレイスマージソートが安定していないのはなぜですか?
以下の実装は、XXX とマークされた行<=の代わりに使用されているため、安定しています。<これにより、効率も向上します。この行で<はなく、使用する理由はありますか?<=
python - リストの一部をその場で並べ替える
リストがあるとしましょう：
これで、 a.sort() はリストをその場でソートします。リストの一部だけを並べ替えたい場合はどうすればよいでしょうか? C++ では、次のように記述できます。
Pythonにも同様の方法はありますか?
arrays - マージソートアルゴリズムを使用してその場でソートする方法は?
質問が具体的すぎないことはわかっています。
私が望むのは、通常のマージ ソートをインプレース マージ ソート (または一定の余分なスペース オーバーヘッドを伴うマージ ソート) に変換する方法を教えてくれる人だけです。
私が（ネット上で）見つけることができるのは、「複雑すぎる」または「このテキストの範囲外」というページだけです。
インプレース (余分なスペースなし) をマージする既知の唯一の方法は、複雑すぎて実用的なプログラムにはなりません。（ここから撮影）
複雑すぎるとはいえ、マージソートをその場で行う方法の基本的な概念は何ですか?
jquery - HTML ドキュメント全体をインプレースで置換
生成されたドキュメントをブラウザの履歴に保存したくないので、データ URI の使用を避けようとしています。HTML ドキュメント全体をその場で置き換えることは可能ですか?
を試しjQuery("html").html("<html>....</html>")ましたが、style情報が保存されません。
algorithm - 配列内の2つのクラスの要素の安定した分離
次の問題を考えてみましょう。
赤または青の2つのクラスに属する要素の配列が与えられます。すべての青い要素が最初に来るように（そしてすべての赤い要素が後に続くように）、配列の要素を再配置する必要があります。再配置は安定した方法で行う必要があります。つまり、青い要素の相対的な順序を維持する必要があります（赤い要素でも同じです）。
上記の再配置をインプレースで実行する巧妙なアルゴリズムはありますか？
もちろん、インプレースではないソリューションは簡単です。
明らかなインプレースソリューションは、安定したソートアルゴリズムをアレイに適用することです。ただし、配列で本格的な並べ替えアルゴリズムを使用することは、特に2つのクラスの要素しか扱っていないという事実を考慮すると、直感的にやり過ぎのように感じます。
どんなアイデアでも大歓迎です。