並べ替え
2008年07月19日06:01
もし「ゴルゴ１３」とか「こち亀」とかそういうマンガを渡されて、「２分以内にきちんと並べて本棚に入れておいて」って言われたら、どう作業したら手早く片付けられるだろう。 案外難しくないだろうか。 これは並べ替え、といわれて、古くから知られているアルゴリズムの一種だ...。
クイックソートという有名な高速並べ替えアルゴリズムがあるのだけど、これと格闘して５時間ぐらい立って、ようやく完成したので、寝ます。 おやすみなさい。
(-_-) zzzZZZ
クイックソートという有名な高速並べ替えアルゴリズムがあるのだけど、これと格闘して５時間ぐらい立って、ようやく完成したので、寝ます。 おやすみなさい。
(-_-) zzzZZZ
コメント一覧
ねこ☆ミ。 2008年07月19日 12:29
実装したことあります。
学校の授業でC言語で、、、ｗ
Wikiのクイックソートのページの右側のアニメーションをみて
アルゴリズムを思い出した。
http://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88
昔、教科書で見たときよりも簡単に知識が吸収できてしまう。
英語のWikiの方が内容が充実しているなぁ。
http://en.wikipedia.org/wiki/Quicksort
計算量（complexity?）の計算の仕方がのっているし。
学校の授業でC言語で、、、ｗ
Wikiのクイックソートのページの右側のアニメーションをみて
アルゴリズムを思い出した。
http://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88
昔、教科書で見たときよりも簡単に知識が吸収できてしまう。
英語のWikiの方が内容が充実しているなぁ。
http://en.wikipedia.org/wiki/Quicksort
計算量（complexity?）の計算の仕方がのっているし。
おかあつ 2008年07月19日 15:08
ここ１～２年のWIKI、ヤバイです。 下手に学校で勉強するよりよっぽどいいです。
配列上のクイックソートをするのは簡単だけど、線形リストをクイックソートするのって、意外や以外、難しい事がわかった...。 要素数がわかる双方向リストなら簡単なんだけど... 要素数を持ってない場合、カーソルが入れ違った事を判定できない...。 あえなく撃沈...。
配列上のクイックソートをするのは簡単だけど、線形リストをクイックソートするのって、意外や以外、難しい事がわかった...。 要素数がわかる双方向リストなら簡単なんだけど... 要素数を持ってない場合、カーソルが入れ違った事を判定できない...。 あえなく撃沈...。
おかあつ 2008年07月19日 15:27
... と思ったら、今出来ました。 やっぱり眠い時にやると、ダメです。
おかあつ 2008年07月19日 18:19
... と思ったら、やっぱりダメでした。 要素の入れ替えをポインタのつなぎ変えによって実現しようとしていたんですが、そうすると、３つ必要なイテレーターの参照している値も同時に入れ替える必要があることがわかりました。
この、要素の入れ替えが起こったとき、参照しているインデックスも入れ替えを追跡するようにするメカニズムって、SWING JTextArea の Element が持っていますが、とても複雑です。
なかなか一筋縄では行かないものです。
この、要素の入れ替えが起こったとき、参照しているインデックスも入れ替えを追跡するようにするメカニズムって、SWING JTextArea の Element が持っていますが、とても複雑です。
なかなか一筋縄では行かないものです。
おかあつ 2008年07月19日 22:04
ポインタの入れ替えが難しそうなので、ポインタの入れ替えじゃなくて、データ自体の入れ替えで実装したら、結構遅くなっちゃいました。
それで、「頑張ってポインタのつなぎかえ、参照追跡のメカニズム」を組み込んでみました。
そうしたら、なんと、データ転送によろ入れ替えルーチンよりも、ポインタのつなぎかえの方が１．５倍ぐらい遅かったのでした。
データ転送によろ入れ替えルーチンは、転送量は多いですが、２回だけの読み込み書き込みで処理が終わります。それに対して、ポインタの方は longの情報を２回読んで２回書き込みと言う処理を、更に２回繰り返すので、逆にオーバーヘッドがかかって、かえって遅くなるみたいです。
これはブロックのサイズが大きくても同じでした。 今時、コチョコチョと小技を使って転送データ量の節約に心がけるよりは、ドーンとまとめて一回だけで処理したほうが速いみたいです。
プログラミングって、何年やっても、なかなか一筋縄ではいきません。
それで、「頑張ってポインタのつなぎかえ、参照追跡のメカニズム」を組み込んでみました。
そうしたら、なんと、データ転送によろ入れ替えルーチンよりも、ポインタのつなぎかえの方が１．５倍ぐらい遅かったのでした。
データ転送によろ入れ替えルーチンは、転送量は多いですが、２回だけの読み込み書き込みで処理が終わります。それに対して、ポインタの方は longの情報を２回読んで２回書き込みと言う処理を、更に２回繰り返すので、逆にオーバーヘッドがかかって、かえって遅くなるみたいです。
これはブロックのサイズが大きくても同じでした。 今時、コチョコチョと小技を使って転送データ量の節約に心がけるよりは、ドーンとまとめて一回だけで処理したほうが速いみたいです。
プログラミングって、何年やっても、なかなか一筋縄ではいきません。
おかあつ 2008年07月19日 22:08
ちなみに、データ全体を一度メモリに取り込んでからソートして、またファイルに戻すというロジックにすると１００倍ぐらい速くなりました。 すごい差です。 でもあまり巨大なデータに対しては全てオンメモリにロードしてしまうのは、危険なので、様子を見ながらやる必要があります。
あとはメモリマップトファイルを使う方法もあるのですが、マップを明示的に解除する方法がないので、使えないっぽいです。
あとはメモリマップトファイルを使う方法もあるのですが、マップを明示的に解除する方法がないので、使えないっぽいです。
