- 1 名前：デフォルトの名無しさん [2008/05/31(土) 15:57:02 ]
- やばい！論文書きます
- 24 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 13:14:15 ]
- >>23 最適解じゃないし。そんなの解いたとは言わん
- 25 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 13:15:54 ]
- >>22
書き始めていいよ
埋まりそうになったら次スレ用意する
- 26 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 13:30:45 ]
- >>24
0-1でなきゃ、の意味も掴めないのか？一般化ナップサックの話だよ
- 27 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 13:41:20 ]
- suckと申したか
- 28 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 17:30:36 ]
- 卑猥だな
- 29 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 03:24:44 ]
- おまいら、コンビニの前でチンチンの(自己申告の)でかさを競い合ってるDQNとかわらんぞ。
- 30 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 15:55:20 ]
- >>26
おいおい、0-1でないと意味ないだろ。
お前、月に行くとして酸素ボンベ半分とか、拳銃0.8個とかナップザックに詰めて
持っていくのかよ。月 を な め る な
- 31 名前：デフォルトの名無しさん mailto:sage [2008/06/03(火) 23:20:58 ]
- 月に拳銃は要るのかどうかは知らんがﾜﾛﾀ
- 32 名前：デフォルトの名無しさん mailto:sage [2008/06/06(金) 01:40:47 ]
- >>22
フェルマー乙
- 33 名前：デフォルトの名無しさん mailto:sage [2008/06/30(月) 15:13:53 ]
- オレもありとあらゆるデータを1bitにするアルゴリズムを持ってるよ。
- 34 名前：デフォルトの名無しさん mailto:sage [2008/07/07(月) 01:06:52 ]
- 非可逆のハッシュなら俺も持ってる。
- 35 名前：デフォルトの名無しさん mailto:sage [2008/08/18(月) 00:53:00 ]
- >>20
ttp://www.geocities.jp/m_hiroi/light/pyalgo08.html
- 36 名前：デフォルトの名無しさん mailto:sage [2008/12/15(月) 07:17:28 ]
- >>35
xyzzyの人ですか
- 37 名前：デフォルトの名無しさん mailto:sage [2008/12/15(月) 22:47:57 ]
- >>35
別に普通にできるだろ？
ttp://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/8332.txt
- 38 名前：デフォルトの名無しさん mailto:sage [2008/12/16(火) 01:06:33 ]
- 要素数が少なくなったらO(N^2)に切り替えるというのも、
分割する際についでに数を数えておけば最初の１回以外は何とかなる。
std::list::sort にした方がノードの交換効率もいいし最初でもO(N^2)交換ができるが、
std::sort を使えなくする必要性はないと思われる。
- 39 名前：デフォルトの名無しさん mailto:sage [2008/12/16(火) 01:07:24 ]
- ×O(N^2)交換
○O(N^2)ソート
- 40 名前：デフォルトの名無しさん mailto:sage [2008/12/16(火) 01:11:06 ]
- カウントはO(N)だから最初にやってしまってもいいな
- 41 名前：デフォルトの名無しさん mailto:age [2008/12/16(火) 20:37:44 ]
- age
- 42 名前：デフォルトの名無しさん mailto:sage [2008/12/16(火) 21:15:02 ]
- >>38
std::sortはクイックソートである必要はないという建前だから。
例えば、最初はクイックソートするけど、
分割していって要素数が減ったら別のソートをやるということがあるでしょ。
- 43 名前：デフォルトの名無しさん mailto:sage [2008/12/16(火) 22:13:20 ]
- >>38 はまさにその話だろ？
リストは普通にO(N^2)ソートできるから問題ない。
std::sort では要素数少ない時は
交換回数の少ない選択ソートが使われる事が多いが、
別に双方向リストでも選択ソートは可能だ。
ttp://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/8359.txt
- 44 名前：デフォルトの名無しさん mailto:sage [2008/12/16(火) 22:50:06 ]
- std::sort は O(N logN) で余分なバッファを使わなければ何でもいいのだが、
まさにこれはその要件を満たしてる。
まあ、実際には pivot の扱いを変えないと std::sort としては使えないんだが、
そこは std::sort にするならそう実装すればいいってことで。
（昔書いたコードの使い回しなんで・・・）
当然 std::list::sort として実装した方が効率的なので
std::list::sort が存在することに何も問題は無いんだが、
std::sort を random access iterator に限定して
bidirectional iterator に対してわざわざ使えなくする必要性は無いよね。
- 45 名前：デフォルトの名無しさん mailto:sage [2008/12/17(水) 01:42:19 ]
- そんなことほかにも考えているやついるんじゃないかと思ってググってみたら案の定。
www.kmonos.net/wlog/68.html#_2116061224
この人の場合、クイックの後で併用するソートの計算量が良くないねという結論で終わっている。
- 46 名前：デフォルトの名無しさん mailto:sage [2008/12/17(水) 19:39:49 ]
- なるほど。ヒープソートも使ってんのか。
それじゃしかたないかもね・・・。
- 47 名前：デフォルトの名無しさん mailto:sage [2008/12/18(木) 00:24:05 ]
- そろそろだと思うんだ。
Big-O ショー タァーイム！！
Comb Sort11最高。
- 48 名前：デフォルトの名無しさん mailto:sage [2008/12/18(木) 00:33:45 ]
- gap ありだと bidirectional iterator に適用し辛いな。
余計なバッファを使う必要がある。
- 49 名前：デフォルトの名無しさん mailto:sage [2008/12/18(木) 00:38:10 ]
- シェルソートと似たようなアルゴリズムなのに
何でシェルソートより速いんだろうな。
- 50 名前：デフォルトの名無しさん mailto:sage [2008/12/18(木) 01:13:43 ]
- コムソートは平均でも最悪でもほぼO(n log n)でしょ？
理論的限界もO(n log n)じゃなかったっけ？
実装簡単だしメモリ食わないし好きだ。
- 51 名前：デフォルトの名無しさん mailto:sage [2008/12/18(木) 08:52:35 ]
- コムソートは欲しいときにすぐ書けるのがいい。
安定でないのが玉にキズだけど。
- 52 名前：デフォルトの名無しさん mailto:sage [2008/12/18(木) 14:29:09 ]
- ソートって、データの全てのペア(nC2)についての
比較情報だけ（少し無駄がある）あれば、理論的にはOKだよね？
- 53 名前：デフォルトの名無しさん mailto:sage [2008/12/18(木) 16:16:49 ]
- その比較演算が全順序関係になっていると保証できればOK
- 54 名前：デフォルトの名無しさん mailto:sage [2008/12/18(木) 19:10:45 ]
- じゃんけん風味だと終わんないもんな
- 55 名前：デフォルトの名無しさん mailto:sage [2008/12/18(木) 23:14:10 ]
- >>52
だから普通のソート法は最悪でもO(N^2)のオーダーなわけだ。
ボゴソートのような無茶苦茶なものは除いて・・・。
- 56 名前：デフォルトの名無しさん mailto:sage [2008/12/19(金) 00:24:14 ]
- bidirectional iterator に適用できる
メモリ使用量 O(lonN) 以下の
最悪計算時間が O(NlogN) のソート法ってないもんかねえ・・・。
ないことが証明されてたりするのかね。
- 57 名前：デフォルトの名無しさん mailto:sage [2008/12/19(金) 07:09:13 ]
- ボゴソートは要らない子
- 58 名前：デフォルトの名無しさん mailto:sage [2008/12/20(土) 03:55:59 ]
- >>57
そんな彼が好きなんです。
- 59 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 20:49:47 ]
- ソート済みのデータでも容量がGBやTBクラスだと
どうやって取り扱ったら良いのか分かりません＞＜
- 60 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 05:44:47 ]
- ISAMとか真似すれば？
- 61 名前：デフォルトの名無しさん mailto:sage [2009/01/31(土) 15:46:45 ]
- B木とかそういうので扱えばいいんじゃないかな
- 62 名前：デフォルトの名無しさん mailto:sage [2009/03/30(月) 17:19:20 ]
- shear sortって、wikipedia日本語版では「シェアソート」って紹介されてるのね。
どう聞いても「シア」にしか聞こえないんだけど、「シェアソート」になった由来は何かあるのかな?
# 最近話題の「ウィンド･シア」の方はシェアとは言わんよね。
## あっちの業界はあっちの業界で、「porpoise」を妙ちきりんな読み方しているけど。
- 63 名前：デフォルトの名無しさん mailto:sage [2009/03/30(月) 17:25:45 ]
- シェルソートにひきずられたかなぁ？
まぁ古いアルゴリズムとかは妙なカタカナが定着してたりすることは
よくあること...だけど、活字で残ってる用例あるかなぁ。あまり紹介
されないソートだし。てか今知った。
- 64 名前：デフォルトの名無しさん mailto:sage [2009/04/05(日) 21:41:56 ]
- 最初に訳した奴がバカだったんだろう
そういうのあるよね
- 65 名前：デフォルトの名無しさん mailto:sage [2009/04/05(日) 23:03:28 ]
- ねーよｗ
- 66 名前：デフォルトの名無しさん mailto:sage [2009/04/06(月) 09:28:09 ]
- ウィキペディアだとありそうだな。
どうもウィキペディアを勉強ノート代わりにしたっぽい奴が書いた項目を見つけて
頭が痛いところだったり。
- 67 名前：デフォルトの名無しさん mailto:sage [2009/04/06(月) 23:54:34 ]
- 直してあげな。
- 68 名前：62 mailto:sage [2009/04/07(火) 01:40:48 ]
- いやぁ、なんか理由があるのかと思って躊躇していたのさ。
誰も直さないようなら、今度暇なときにでも直しておくよ。
- 69 名前：デフォルトの名無しさん mailto:sage [2009/04/07(火) 08:53:42 ]
- Googleで検索する限りでは、シアソートって書いてるページ、ほとんどないぞ？
- 70 名前：デフォルトの名無しさん mailto:sage [2009/04/07(火) 09:04:19 ]
- シェアソートって書いてあるページも、多くはWikipediaを参照している罠。
- 71 名前：デフォルトの名無しさん mailto:sage [2009/04/07(火) 10:32:03 ]
- 『アルゴリズム辞典』に載ってればそれに従うところだが、載ってないんだよな。
TAOCPはどうだろう。
- 72 名前：デフォルトの名無しさん [2009/09/19(土) 16:19:09 ]
- あらかじめソートされた結果を知っていれば
たとえ
ボゴソートとかであっても恣意的な神の手を加えることにより
ものすごい低いオーダーを実現できるよねｗ
- 73 名前：デフォルトの名無しさん mailto:sage [2009/09/19(土) 20:26:46 ]
- 安定でマージソートより優秀なのは何？
- 74 名前：デフォルトの名無しさん mailto:sage [2009/09/19(土) 20:30:58 ]
- クレオソート
- 75 名前：デフォルトの名無しさん mailto:sage [2009/09/19(土) 20:34:53 ]
- バケツソート
- 76 名前：デフォルトの名無しさん mailto:sage [2009/09/19(土) 22:30:43 ]
- >>72
ソート済のデータを渡せばO(1)
- 77 名前：デフォルトの名無しさん mailto:sage [2009/09/19(土) 22:50:02 ]
- 汎用ソートの場合、ifを使わずにreturn a-bとかで直接返した方が効率いいんだろうな。
strcmpやmemcmpとかも使って。可読性は知らんが。
- 78 名前：デフォルトの名無しさん mailto:sage [2009/09/25(金) 13:43:12 ]
- >>77
例えばint型のときにreturn a-bなんてしたら、値域が限定されて汎用じゃなくなるよ。
- 79 名前：デフォルトの名無しさん [2009/09/26(土) 09:08:48 ]
- それはint型の比較関数としてreturn a-bがふさわしくないから。
ソートの汎用性とは関係ない。
比較関数は比較する型ごとに作るんだよ？わかる？
- 80 名前：デフォルトの名無しさん mailto:sage [2009/09/26(土) 09:21:19 ]
- こいつわかってないわ
- 81 名前：デフォルトの名無しさん mailto:sage [2009/09/26(土) 19:00:14 ]
- ∧＿∧ ／￣￣￣￣￣
（ ‘∀‘）＜ オマエガナー
（ ） ＼＿＿＿＿＿
｜ ｜ |
（_＿）＿）
- 82 名前：デフォルトの名無しさん mailto:sage [2009/09/28(月) 11:16:59 ]
- つまり、a-bって書くとunsigned同士は勿論、signed同士でも巧くないってことか。
- 83 名前：デフォルトの名無しさん mailto:sage [2009/09/28(月) 22:25:06 ]
- int全体の比較関数をa-bと書くのはアホだろ。
単なるバグだし。
- 84 名前：デフォルトの名無しさん mailto:sage [2009/09/29(火) 22:45:49 ]
- 20億近くまで数字が分布するようなアプリのが少ないから問題ないだろ。
お金周りのアプリなら8バイトなり古典小数点数ライブラリなり使うだろうし。
- 85 名前：デフォルトの名無しさん mailto:sage [2009/09/29(火) 22:46:36 ]
- ×古典 ○固定
- 86 名前：デフォルトの名無しさん mailto:sage [2009/09/29(火) 23:02:20 ]
- 会計処理で重要なのは、固定小数点ではなく、十進演算であること
- 87 名前：デフォルトの名無しさん mailto:sage [2009/09/29(火) 23:18:18 ]
- JavaのBigDecimalは十進演算だったのか。
言われてJavaDoc覗いて初めて気付いたｗ
- 88 名前：デフォルトの名無しさん mailto:sage [2009/09/29(火) 23:20:26 ]
- いや、Decimalって書いてるだろｗ
- 89 名前：デフォルトの名無しさん mailto:sage [2009/09/30(水) 09:51:14 ]
- >>84
問題は、その発想のままshort intにまで適用してしまう可能性があることだな。
- 90 名前：デフォルトの名無しさん mailto:sage [2009/11/05(木) 02:26:40 ]
- return (a>b)-(a<b);
- 91 名前：デフォルトの名無しさん mailto:sage [2009/11/05(木) 02:31:26 ]
- >>87-88
- 92 名前：デフォルトの名無しさん mailto:sage [2009/11/12(木) 19:54:04 ]
- 表示する時の演算コストを考えてんだろうね
- 93 名前：デフォルトの名無しさん mailto:sage [2009/11/26(木) 14:59:05 ]
- Ruby 1.9 And Rails 3.0
www.slideshare.net/arrrrcamp/ruby-19-and-rails-30
- 94 名前：デフォルトの名無しさん mailto:sage [2011/04/25(月) 16:06:08.96 ]
- なんでボゾソートがボゴソートより速いのか理解できない
- 95 名前：天使 ◆uL5esZLBSE mailto:sage [2011/07/05(火) 05:52:03.56 ]
- ∨
[[[[[[[ Ruby 1.9 And Rails 3.0 ]]]]]]]（キリ!!!!キリッッッキリッッッッ!!!!
∧∧∧∧∧∧∧(←きリッッ!!
- 96 名前：デフォルトの名無しさん [2011/07/09(土) 22:03:16.04 ]
- Sleep SortのスリープをCPUクロック数に置き換えたら凄いんじゃね？
しかも超マルチコア前提で
- 97 名前：デフォルトの名無しさん mailto:sage [2011/07/10(日) 10:36:53.31 ]
- よし、O(N)のアルゴを教えてやろう。
ソート前の全組み合わせの膨大なデータを分散ストレージに用意しておくんだ。
ソート処理ではハッシュを計算するだけ。
- 98 名前：デフォルトの名無しさん mailto:sage [2011/07/17(日) 22:33:02.74 ]
- >>97
それってビンソートとどこが違うの？
- 99 名前：デフォルトの名無しさん [2011/09/18(日) 22:54:53.45 ]
- クイックソートをマルチスレッド化したらどれくらい速くなるかなあ？
分割する度に片方の群を別スレッドに渡していくような処理を考えたんだけど
もちろん要素数が少ない時はスレッド分割なしにして
メモリアクセス性能次第かな
- 100 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 23:27:10.01 ]
- >>99
TSV DRAMが普及するまで待て
現在のDRAMの構造ではマルチコアの性能を最大限に発揮出来ない
- 101 名前：デフォルトの名無しさん mailto:sage [2011/09/25(日) 11:28:06.98 ]
- www.speedtest.net/result/1500561067.png
- 102 名前：デフォルトの名無しさん mailto:sage [2011/09/25(日) 11:30:29.92 ]
- www.speedtest.net/result/1500563768.png
- 103 名前：デフォルトの名無しさん mailto:sage [2011/09/25(日) 11:39:38.89 ]
- www.speedtest.net/result/1500570462.png
www.speedtest.net/result/1500563768.png
www.speedtest.net/result/1500561067.png
- 104 名前：デフォルトの名無しさん [2011/09/25(日) 11:59:07.68 ]
- www.speedtest.net/result/1500570462.png
www.speedtest.net/result/1500563768.png
www.speedtest.net/result/1500561067.png
www.speedtest.net/result/1326987708.png
- 105 名前：デフォルトの名無しさん mailto:sage [2011/09/25(日) 12:46:59.94 ]
- www.speedtest.net/result/1500619815.png
- 106 名前：デフォルトの名無しさん mailto:sage [2011/10/08(土) 11:45:01.88 ]
- 保守
- 107 名前：デフォルトの名無しさん [2011/10/18(火) 11:37:16.18 ]
- >>1
ソート対象の要素の序数が最初からわかっているという条件があって、ようやくO(n)となるのだが・・・
アカシックレコードでも発見したのか？
- 108 名前：デフォルトの名無しさん [2011/10/21(金) 09:36:49.33 ]
- timソート
- 109 名前：デフォルトの名無しさん mailto:sage [2011/10/25(火) 00:19:28.15 ]
- フリーの TBB でも使って組んでみたら？
- 110 名前：デフォルトの名無しさん [2011/11/29(火) 13:00:20.03 ]
- >>96
その実装が見てみたいわ
- 111 名前：デフォルトの名無しさん mailto:sage [2011/11/30(水) 12:57:12.94 ]
- >>99
粒度をどのくらいにするかだよね。マルチ化するために処理が増えるから
そのトレードオフを自動的に考えて判断させるような自動最適化ができた
上で最速を探すのって面白そうだけどな。前段階がちょっとおもそうだけど。
- 112 名前：デフォルトの名無しさん [2011/12/11(日) 08:17:05.88 ]
- >>96
クロック数とか持ち出す時点でオーダー記法の意味わかってなさすぎ
- 113 名前：デフォルトの名無しさん mailto:sage [2011/12/11(日) 11:21:38.41 ]
- お前>>96の意味わかってないだろ
- 114 名前：デフォルトの名無しさん mailto:sage [2011/12/11(日) 16:16:40.40 ]
- クロックに合わせたスリープソートでマルチコアってできなくね？
- 115 名前：デフォルトの名無しさん [2011/12/11(日) 21:40:13.84 ]
- nコアで値分だけnop発行とか?
- 116 名前：デフォルトの名無しさん mailto:sage [2011/12/11(日) 22:00:16.82 ]
- >>115
あ、なるほど。勉強になりました。
- 117 名前：デフォルトの名無しさん mailto:sage [2011/12/11(日) 23:19:42.22 ]
- 1クロックですべてのデータを投入することが出来れば
クロックに合わせたスリープソートは実現可能。
でなければデータ投入にかかるクロックを厳密に計算しなければならない。
- 118 名前：デフォルトの名無しさん mailto:sage [2011/12/12(月) 06:22:42.30 ]
- データ量に応じていろいろ考えないといけないね。
キャッシュミスしたら死ぬし。
- 119 名前：デフォルトの名無しさん [2011/12/12(月) 22:12:37.15 ]
- つまりあれだ、SIMD的な何かがあればいいのか
SSXとか
- 120 名前：デフォルトの名無しさん mailto:sage [2011/12/17(土) 00:23:05.91 ]
- このスレまだあったのｗｗｗ
俺が大学生の時に建てたスレだｗ
- 121 名前：デフォルトの名無しさん mailto:sage [2011/12/17(土) 03:57:54.28 ]
- >>120
なんだ、中退したのか?
- 122 名前：デフォルトの名無しさん [2011/12/24(土) 23:09:10.65 ]
- 今ならGPUでバイトニックソート使うのが速さ的には一番だろうな
- 123 名前：デフォルトの名無しさん mailto:sage [2011/12/31(土) 12:21:00.78 ]
- うんこぶりぶり。
精子ドピュッドピュ
- 124 名前：デフォルトの名無しさん [2012/01/06(金) 15:18:24.61 ]
- 中央値を高速に見つけたいんだけど、やっぱソートしなきゃダメかね
|
 |
