ソートのテクニックについて

質問

お世話になります。
ソートのテクニックについて教えていただきたく質問しています。

ソートをするに、パタンが二つあると思います。

例示パタン１；
一人が５回の試技を行い、結果を記録したレコードがあり、
５回の試技を昇順に列べてからリストする。

レコード形式；名前、試技１、試技２、、、試技５、試技平均

例示パタン２；
一人が砲丸投げとやり投げを行い、結果を記録したレコードがあり、
砲丸投げと、やり投げ毎に記録の良い順にリストする。

レコード形式；名前、砲丸投げ記録、やり投げ記録

上記パタン１では、データを頭から読み出しながら試技をソートすれば良く、
ソートに要するスペース（メモリ？）は少なくて済む。

パタン２では、予め全レコードについてソートしてからリストする必要があるため、
スペースが要求されると思います。

ここで質問です。
パタン２のような場合、どのようなテクニックを使えばよいのでしょうか。
実際に動かしているのですが、パソコンでは問題なくても携帯電話で動かすと、
”上限サイズを超えたので云々”とのエラーになります。
（シュワルツ変換というテクニックでソートしています。）

　　@lines = map {$_->[0]}
　　　　　sort {$b->[11] <=> $a->[11] or $a->[1] <=> $b->[1]}
　　　　　map {[$_, split /<>/]} @lines;

上記の場合、メモリに蓄えられてソートがされると思います。
一度外に書き出すようなテクニックの方が良いのでしょうか。
時間も掛からず、メモリも食わない方法が理想ですが、
そうも行かないと思います。
メモリを食わずに済む方法を教えてください。

宜しくお願いします。

回答No.2

mtaka2 · ベストアンサー

携帯からのアクセスだからといって、CGIを動作するサーバ側の状況が変わるとは思えないあたりは、回答者1さんと同意見ですが、

とりあえず perl でのソートのメモリ消費量削減について。

Schwartzian transform は、記述はシンプルですが、
ソート中に全データのコピーが発生するため、メモリ効率はあまり高くありません。(回答1のように分けて書いてもメモリ消費は同じです)

配列のインデックスだけをソートする方がメモリ消費量は少なくなります。
それと、各行のsplit後は、ソートに不要なデータを保持しないようにした方がいいでしょう。
そうすると、
---
@key = map { [ (split(/<>/))[0,10] ] } @lines;
@lines = @lines[ sort { $key[$b]->[1] <=> $key[$a]->[1] or $key[$a]->[0] <=> $key[$b]->[0] } 0..$#lines ];
---
といったコードになります。
(このコードでも計算量的には Swartzian transformと変わりません)

お礼

早速有り難うございました。
分からないながらに、お示しいただいたコードを貼り付けてみましたが、
エラーで動きませんでした。
貼り付けミスはないと思います。

全体がよく分かっているわけではありませんが、
ｋｅｙだけソートするという主旨は分かったつもりです。

最後にある、 0..$#lines ];　の部分が分かりません。
（このまま貼り付けたのではいけないのでしょうか）

宜しくお願いします。

回答No.5

Tacosan

Perl のスクリプトとしてデバッグする気はありませんか?

参考URL：

http://www.tohoho-web.com/wwwcgi7.htm

お礼

スクリプトのデバッグ、読みました。
こんなモノがあるのですね、今度やってみます。

というのも、先ほど動かなかったまま全く何もせず、
マシンを代えてみたら動いてしまいました。
原因は分かりません。

ただ、動きはしましたが、やはり携帯電話では最大サイズを超えた旨のエラーで止まってしまいます。
途中までは出ますので、何とか使えます。
有り難うございました。

ということで、
今度動かないようなことが在ればスクリプトのデバッグをやってみたいと思います。

お世話になりました。

回答No.4

ralf124c

ご質問に対する回答とはちょっと異なると思いますがエラーとSortの処理とはなんの関係もないように思います。
問題点は処理終了後に出力されるデータ(HTMLでしょうか？)の量が携帯のメモリ容量を超えているためではないかと思います。
携帯のブラウザ表示は少し前までは２ｋの壁といわれ、コンテンツファイルそのものをトータルで２ｋバイト以下に抑えないと機種によってはご質問のようなエラーメッセージを吐いて終了という結果になります。
最近では携帯の容量も増えはしましたが、古い携帯を後生大事に使っているやつもいるという可能性と、表示画面の小ささの制約から、一般的に携帯コンテンツはおのずと小さなコードで作るようになっております。
PCで表示させたコンテンツを画像ともどもセーブして、そのファイル容量をチェックし、携帯の限界を確認してみてはどうでしょう。

ソートテクニックに関しては、ソートアルゴリズムが専門ではない(学問の一分野にもなっているくらいなので)のでコメントのしようもありませんが、プログラムは動いてなんぼのものです。　早い、小さい、リソースが少ない、(クールなプログラム)にこした事はありませんが、動かないプログラムはディスクのゴミでしかないのも事実です。　まずは動くものを完成させ、その後にテクを駆使してクールに育ててゆくことをお勧めします。

お礼

早速有り難うございます。
全く同じデータを使い、シュワルツ変換を使わないで、
かつこれ以上の項目を表示している別プログラムは問題なく動いています。
よって、シュワルツ変換でメモリを食っているのかなと判断したのですが。

回答No.3

Tacosan

その「貼り付けた」というのを, (できれば全部, できなければ関連部分だけでいいので) 示すことはできませんか? またと, 「エラーが出た」というなら「どの行に対しどのようなエラーが出たか」を書くようにしてください (もちろん「エラーが出た行」も示す). そうでないと, 「どこでどのようなエラーが出ているのかを推測する」必要があり, それは回答者に余計な負担を与えるものとなります.
@lines = @lines[ sort { $key[$b]->[1] <=> $key[$a]->[1] or $key[$a]->[0] <=> $key[$b]->[0] } 0..$#lines ];
はわけると
@sorted_indices = sort { $key[$b]->[1] <=> $key[$a]->[1] or $key[$a]->[0] <=> $key[$b]->[0] } 0..$#lines;
@lines = @lines[@sorted_indices];
となります.

お礼

早速有り難うございます。
質問に書いたとおりですが、

　　　　@lines = map {$_->[0]}
　　　　　　　sort {$b->[11] <=> $a->[11] or $a->[1] <=> $b->[1]}
　　　　　　　map {[$_, split /<>/]} @lines;

は問題なく動いていまして、
この部分を教えていただいた下記の分、

　　　　@key = map { [ (split(/<>/))[0,10] ] } @lines;
　　　　@lines = @lines[ sort { $key[$b]->[1] <=> $key[$a]->[1] or $key[$a]->[0] <=> $key[$b]->[0] } 0..$#lines ];

に置き換えました。

そうしたところ、
cgi自体がエラーとなって動かなかったということです。
中に入っていないので、どの行とかになりません。
この内容で答えになりますでしょうか。

宜しくお願いします。

回答No.1

zxcv0000

# split /<>/ と $a->[11] のからみが不明ですが、本題で無さそうなので気にしない事にします。

==============================
同じ CGI を同じ条件で閲覧したとき、PC と 携帯で CGI の正常/異常が変るのは考え難いと思います。
・使用したデータは同じですか？
・ブラウザ等の性質によって処理を振り分ける部分はありませんか？
・さらには、JavaScript では無く CGI のエラーってのは確かですか？

==============================
ご質問の件ですが、 map(sort(map())) とネストさせるとそれぞれの段階で無名配列がとられるかも知れません。 Perl が最適化で頑張ってくれれば良いのですが、そうで無ければ以下の様にステップを分けた方がメモリ使用は減ると思います。

@lines = map {[$_, split /<>/]} @lines;
@lines = sort {$b->[11] <=> $a->[11] or $a->[1] <=> $b->[1]} @lines;
@lines = map {$_->[0]} @lines;

まず sort の内部で split という高負荷処理をさせない、次にメモリ使用を減らすという考え方は、良いと思いますよ。

極めたいなら、Perl の sort() を使用せずに自分で書く手があります。 クイックソート・ラディックスソート・ヒストグラムソート とか、いろいろの手法からデータ傾向に合うものを選び、小メモリ化に腐心すれば良い結果が得られる*かも*知れません。

お礼

早速有り難うございます。
＞# split /<>/ と $a->[11] のからみが不明ですが、
済みません、私のコードをそのまま貼り付けました。

＞ CGI の正常/異常が変るのは考え難いと思います。
メモリ消費量等は変わらないかも知れませんが、
携帯電話では豊富にメモリが使えないのではと思っています。

お示しいただいたコーディングにしてみましたが、
（もちろん正しく動作しましたが）
携帯電話での結果は同じ、「上限サイズに云々」が出ました。

＞Perl の sort() を使用せずに自分で書く手があります。
全くの素人で、例示いただいたコードを何とかアレンジして
試行錯誤すると言ったレベルです。
今後、勉強が必要です。