スラッシュドットに聞け：物理的にモノや人をソートするときはどうしてる？ 40
ストーリー by hylom
クイックソートをリアルで実行できる気がしない 部門より
クイックソートをリアルで実行できる気がしない 部門より
あるAnonymous Coward 曰く、
slashdot「Ask Slashdot: How Do You Sort?」より。
先日領収書の束やその他の書類を日付順に分類していたのだが、書類ソーターの類を使わずにソートしていたところ小分けの山がたくさんできあがってしまい、しまいにはどの山が何だったか分からなくなってしまった。
ふとコンピュータサイエンスの授業で習ったソートアルゴリズムを使えばいいのではと思い立ち、紙の山をすべて元に戻し基数ソートをかけたところすんなりと作業を終えることができた。その後別の作業でクイックソートやマージソートも試すことができた。
そこで質問なのだが/.erの皆は物理的にソートする際どんなアルゴリズムを使っているだろうか？
根性で力まかせ (スコア:4, おもしろおかしい)
ソートにはそうとう時間をかけます
Re:根性で力まかせ (スコア:2, おもしろおかしい)
（プシュー）ガミラスに下品な男は不要だ
Re:根性で力まかせ (スコア:1)
そうとう閣下～ああぁぁぁ。。。...（堕ちながら
Re:根性で力まかせ (スコア:1)
ソートに時間をかけるならアルゴリズムを選ぶ必要ないじゃんｗ
それはそーと、ダジャレを言う人はそーっとしてあげましょう
Re: (スコア:0)
ボゴソートですね
バケットソートかなぁ (スコア:2, 参考になる)
バケットソートをよく使っています。http://ja.wikipedia.org/wiki/%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%82%BD%E3%83%BC%E3%83%88
Re:バケットソートかなぁ (スコア:3)
まあ、単純に物を捨てるときとかに
「絶対に置いておく物」
「必要かもしれない物」
「すぐに必要なわけではない物」
「必要ではないというわけではない物」
「必要になることはないと思うけど捨てるに忍びない物」
「置いておかないといけないと一瞬でも思う物」
「どうしても必要な理由は思いつかないけど保留」
とかに分けることもバケツソートですよね。
＃ゴミ屋敷生成法。
Re:バケットソートかなぁ (スコア:2)
新しいフォルダ
最新のフォルダ
親しいフォルダ
古いフォルダ
少し古いフォルダ
最新のフォルダ（２）
みたいなやつだな。
#どこかで画像を拾ったけど、すぐに出てこないほど混沌としているMy Pictures...
Re: (スコア:0)
ここ [movapic.com]ですね
Re: (スコア:0)
私もバケツソートが多いです。ソートすべき値の要素数が多い場合は、大まかなカテゴリでバケツソートしてから、各バケツの中を再帰的にソートします。
物理的なモノの場合、一列に並べて自由にアクセスしたり交換したりできる数に限りがあり、積み上げておくと途中から取り出したり途中に挿入する操作が面倒、という性質があるので、「ランダムアクセスではなく、限られたスタックとキューだけが使える」という制約の上での適したアルゴリズムを考える必要がありますよね。クイックソートもキューだけでできますが、手数を考えるとバケツソートの方が楽なような。制約つきで最適なアルゴリズムの考察ってどこかにないかなあ。
人間の場合、各要素がある程度自律的に動けるのでなるべく並列にできるアルゴリズムが良いですが、これもぱっと考えるとバケツソート(必要なら多段で)がベストのように思えます。より良い方法はあるでしょうか。
Re:バケットソートかなぁ (スコア:1)
私も普段は主にバケットソートでやってますが、
バケットソートを再帰的にやるぐらいなら、タレコミにも挙げられてる基数ソート [wikipedia.org]を使うべきですね。
バケットソートを再帰的にやってると各桁毎にバケツを並べる必要があるので、作業面積がどんどん増えていきます。
基数ソートの場合、全データに対し桁毎バケットソートを繰り返すだけですので、作業領域が一定で済みます。
#最大の難点は、ちょっと直感的ではないってことですかね。
先に下の位からソートを始めるので、作業途中は、一見「順番がバラバラ」で「部分的にソートされた小領域」が存在しません。「最後の最後でやっと完全にソートされた列がいきなり現れる」ので、一度基数ソートを始めたら他の方法に変えるのは無理で、基数ソートを最後までやりとげる必要があります。
Re:バケットソートかなぁ (スコア:1)
あっと、書き忘れてた。
基数ソートは「安定なソート」じゃないとダメというのが、物理ソートしてるときのネックです。
「1の位は昇順になっている(10の位の順番はてんでばらばら)」の列を、10の位だけを見て「安定なソート」をすれば、「10の位が等しいものは元の順番のまま=1の位の昇順に並ぶ=10の位とと1の位の二桁で昇順に並ぶ」というのが基数ソートのキモなわけですが、
人が手で仕分けするバケツソートは、単純に「元の山の上から1枚取って、該当する桁の山の上に置く」という操作になると、上下の並びが入れ替わるんですよね。
基数ソートするためには、安定なソートにするために、「元の山の上から1枚取って、該当する桁の山の上に、ひっくり返して置く」必要があります。このひっくり返す手間が意外とバカにならないというか頭を真っ白にした単純作業の妨げになったりします。
#手順としては下から1枚取って山の上に置く、でもいいんだけど、下から取ると取り出すまで画像認識できないのでタイムラグが発生してさらに遅くなったりします。
Re: (スコア:0)
抽象化して考えるとそうなんですが、現実だと山の大きさと扱いやすさにトレードオフがあるので、「そこそこの数に山が分割された状態」を保つ方がやりやすかったりします。
例えば数年分の月刊雑誌をソートするとき、年度でバケツソートすると、各バケツの山は物理挿入ソートが可能なくらいの大きさになるとか。
大量のカードのスタック、とかになればそれはまた別ですね。
現場の都合・事務の都合 (スコア:1)
現場は商品番号など関係なく同じ系統の製品をまとめてサイズ・色などで順序よく並べたがる。
事務員は系統など関係なく1品目ごとにかためて商品番号順に並べたがる。
ψアレゲな事を真面目にやることこそアレゲだと思う。
日時順 (スコア:1)
自分の仕事の資料を自分用に整理する（必ずしも辞書順に並べる必要はない）という事なら
プロジェクトごとにファイリングした上で、
その中のオブジェクトは作成日時順（ほいほい並び替えない）
プロジェクト単位では最終参照日時順（手にとったら常に先頭に戻す）
で徹底してます。
Re: (スコア:0)
在庫管理は先入れ先出しが常識。
やってみれば此の当たり前の困難な事、得てしてスタック処理に堕してしまう。
しめじソート (スコア:1)
うちの嫁は靴下の整頓をしめじソートで実施してる…
～パタポン教徒～
自分でやってるわけじゃないけど (スコア:0)
つーか最近リアルでものを並べ替えた記憶がないけど、図書館ソートとか。
(配列要素の移動を抑えるためあらかじめギャップを設けることで効率をO(n log n)に高めた挿入ソート)
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.3758 [psu.edu]
Re: (スコア:0)
昔、図書館バイトをしてたときは、返却された本を分類記号でクイックソートしてから配架してました。
順番ぐちゃぐちゃなまま配架する人よりは、ソートする時間がかかっても大分早く終わってましたよ。
何も考えずに (スコア:0)
バブルソートを始めていて時間切れでさらに混乱。
Re:何も考えずに (スコア:2)
割と考えていないと、挿入ソートになりそうな気がする。
Re:何も考えずに (スコア:2)
「既刊のこち亀単行本全巻がバラバラ順になっているので、巻数順に列べる」ようなケースであれば、通常は挿入ソートですよね。
「領収書を発行日順に列べる」ような場合は、重ねると発行日がぱっと判らなくなるので、ある程度の単位（月単位とか）で分割した山を作ったほうが捗りそうに思えるので、時々やってます（本当に早いかは未検証）。
クイックソートは、以下の3条件が揃っていればありかも。リアルでやったことはありませんが。
A. 目視でおおよそ、ソート対象群の中央値あたりの要素を取り出せる
B. 厳密に比較するには、2つを取り出して比べないといけない（横に並べて長さを比べないといけない、など）
C. ソート済みの群を、分離しておけるだけの作業スペースがある
Re: (スコア:0)
リアルだと、メモリと違って移動が楽にできることが結構多いのは注目すべきポイントかも。
Re: (スコア:0)
何も考えずに「1から順番に並べる」と選択ソートになると思う。
Re:何も考えずに (スコア:2)
そういう特殊な条件なら、そうかもね。
ソート済みを左側に、その他を右側に置き、右側から一つずつ取り出して左側に入れてソートを進めていく(挿入ソート)というのは、有りがち。
ソート済みの方の値と位置を、ある程度覚えていたりするから、意外に速かったりする。
Re: (スコア:0)
リアルでバブルソートなんかやる？
挿入ソートじゃなくて？
Re: (スコア:0)
子供が一列に並べた何かのカードを、好きなキャラクタ順にソートしているのを見たら
特別に大好きなキャラクタ以外は、隣と比べて好き嫌いを判断する必要があって、
結果的にバブルソートになっていた。ちょっと感心したのを覚えている。
Re: (スコア:0)
人をソートする時ってバブルソートになってるね。
各々が自主的に前後の人と比較して前後交換していく。超並列動作のバブルソート。
マージソート (スコア:0)
アルゴリズム本来の性質と違って、定番の「10枚ごとにバケツソートからのそれぞれを挿入ソート」よりも、「空間計算量」が小さくて済むし。
ソートが終わったつもりでどこか間違ったままで次の作業に移っちゃうような事故も少ないし。
人間の画像把握能力なら (スコア:0)
同時に二つ以上の比較ができるでしょ？
それを前提にしたソートアルゴリズムを使うと、ものすごくはかどる。
ってのは郵便局のバイト時代に役に立ったなぁ
短期記憶の存在を使うとさらに速度が上がるはずだか、これはアルゴリズム化できなかった。
それよりは物理的な物の移動を最小にする改良のほうが早い。
Re:人間の画像把握能力なら (スコア:1)
全て記憶容量に収まるなら脳内でヒープを構築して、あとはそのとおりに選択するだけ。
ですがそれは一般には適用不可能…
脳内のキャッシュシステム（マジックナンバー？）と相性のいいソートアルゴリズムは、たしかに興味深い。
Re: (スコア:0)
具体的にはどのアルゴリズムが有効だった？
とりあえず分割数を4つくらいに増やしたマージソートが思いついたけど。
マージソートですね (スコア:0)
手元に近いところから部分的に取り掛かれるのでモノを動かす必要がある場合にも実用的ですし、
そのわりに計算量のオーダーが理論的に最速です（ビンソート除く）。
http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%8... [wikipedia.org]
割と意識してやってますね。
システム要件 (スコア:0)
日本の住宅は物理的なメモリが少ないという要件が加わると思います。
オブジェクト指向 (スコア:0)
前後の方と番号を確認してお並びください。100番ごとに目安の看板があります。
# って、あらかじめ整理券配ってたらソートではないのか。
そういや (スコア:0)
去年の正月にやっていた大人のピタゴラスイッチで
ジャガイモを使って各種ソートの説明をしていた。
# 今年の正月にもやったようだが見損ねた。
Amazonソート (スコア:0)
空いてるところに突っ込んでいき、その場所を覚えておく。
あえてソートじゃないこと言ってみる (スコア:0)
物を分類したいのであればソートではなくタグであるべきだ。
しかし物理的にタグをつけたところで目的のものを探すのが面倒だ。
そこで。洗濯バサミ。
1. 意味を書いた紙を洗濯バサミで止めます。
2. その意味を持つ書類等にも洗濯バサミを止めます。
3. (1)と(2)を糸で結びます。
※ 複数の糸の前後関係でソートっぽいこともできなくもないかもしれなくもないやもしれん。
え？ イグノーベルで証明されたように、糸が自然に絡まるだろうって？
書類を上に、タグ紙を下にすれば常に引っ張られて絡みませんよ。
※ 高さどれだけ必要だろう…。
件数が少ないのでソートしない。 (スコア:0)
毎回フルスキャンです。
小須田部長 (スコア:0)
単純にいるもの箱といらないもの箱だけでいい
（結局いらないもの箱にしか物が入らないし最後は精神ダメージを負う）