O（n)のソートアルゴリズムを発見した

1 ：08/05/31 〜 最終レス ：12/01/26

やばい！論文書きます

2 ：

>>3-
そーっとしておいてあげてください

3 ：

O(1)のソートアルゴリズムがある件

4 ：

バケツソートとか普通にあるだろ。

5 ：

対象データに仮定が必要ないんだぜ

6 ：

特許とれ。

7 ：

こういう単純な処理は標準ライブラリに限る。
ただ、自前で実装しないといけない場合がよくある。
そういう用途のソートアルゴリズムがほしいわけです。(簡単で高速で特に欠点ないやつ)

8 ：

夏だなあ・・・

9 ：

もうネタ出尽してるのに人気あるよなソート

10 ：

たまに思い出したように湧いてくるよね。
とっとと駆除しないと。

11 ：

いや待て、古典アルゴリズムなら無理だが、
量子アルゴリズムなら可能かもしれないだろ？
>>1 は古典アルゴリズムと明言していない。
ならまだ可能性はあるんじゃないのか？

12 ：

量子アルゴリズムが効果的に使えてその辺で買えるコンピュータがあればくれ。

13 ：

>>12
http://music8.2ch.net/test/read.cgi/classical/1211529290/

14 ：

listコンテナにもつかえるsortアルゴリズムというと
バブルソートだけですか？

15 ：

古典コンピュータ以外でのO(n)のアルゴリズムが発見されたとしても、lg(n)時間減るだけじゃなあ。
元々多項式時間なだけに価値があるかどうか。

16 ：

>>14
マージソートとか

17 ：

O(n)のソートを開発したぜ。ただしある特定の配列のみ適用可能。
def sort(arr)
    for i in 0..arr.length-2
        if arr[i] > arr[i+1]
            raise "not sorted!"
        end
    end
    return arr
end
sort [1,2,3]

18 ：

それなら、
def sort(arr)
  [1,2,3]
end
でよくね？

19 ：

ソート対象のデータに全順序以外の仮定がない場合，
ソートの計算時間の下限がO(NlogN)なのはすでに証明済みだったような？

20 ：

双方向リストってクイックソート使えても良さそうだと思うんだけど、
何で使えないのん？

21 ：

作ってないから。

22 ：

>>1しょぼいな
俺なんかナップサック問題を多項式時間で解くアルゴリズムを発見したぞ。
でもそれを記述するにはこの余白はあまりにも少なすぎ

23 ：

0-1でなきゃ貪欲法で元々多項式時間じゃないか。

24 ：

>>23 最適解じゃないし。そんなの解いたとは言わん

25 ：

>>22
書き始めていいよ
埋まりそうになったら次スレ用意する

26 ：

>>24
0-1でなきゃ、の意味も掴めないのか？一般化ナップサックの話だよ

27 ：

suckと申したか

28 ：

卑猥だな

29 ：

おまいら、コンビニの前での(自己申告の)でかさを競い合ってるDQNとかわらんぞ。

30 ：

>>26
おいおい、0-1でないと意味ないだろ。
お前、月に行くとして酸素ボンベ半分とか、拳銃0.8個とかナップザックに詰めて
持っていくのかよ。月　を　な　め　る　な

31 ：

月に拳銃は要るのかどうかは知らんがﾜﾛﾀ

32 ：

>>22
フェルマー乙

33 ：

オレもありとあらゆるデータを1bitにするアルゴリズムを持ってるよ。

34 ：

非可逆のハッシュなら俺も持ってる。

35 ：

>>20
ttp://www.geocities.jp/m_hiroi/light/pyalgo08.html

36 ：

>>35
xyzzyの人ですか

37 ：

>>35
別に普通にできるだろ？
ttp://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/8332.txt

38 ：

要素数が少なくなったらO(N^2)に切り替えるというのも、
分割する際についでに数を数えておけば最初の１回以外は何とかなる。
std::list::sort にした方がノードの交換効率もいいし最初でもO(N^2)交換ができるが、
std::sort を使えなくする必要性はないと思われる。

39 ：

×O(N^2)交換
○O(N^2)ソート

40 ：

カウントはO(N)だから最初にやってしまってもいいな

41 ：

age

42 ：

>>38
std::sortはクイックソートである必要はないという建前だから。
例えば、最初はクイックソートするけど、
分割していって要素数が減ったら別のソートをやるということがあるでしょ。

43 ：

>>38 はまさにその話だろ？
リストは普通にO(N^2)ソートできるから問題ない。
std::sort では要素数少ない時は
交換回数の少ない選択ソートが使われる事が多いが、
別に双方向リストでも選択ソートは可能だ。
ttp://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/8359.txt

44 ：

std::sort は O(N logN) で余分なバッファを使わなければ何でもいいのだが、
まさにこれはその要件を満たしてる。
まあ、実際には pivot の扱いを変えないと std::sort としては使えないんだが、
そこは std::sort にするならそう実装すればいいってことで。
（昔書いたコードの使い回しなんで・・・）
当然 std::list::sort として実装した方が効率的なので
std::list::sort が存在することに何も問題は無いんだが、
std::sort を random access iterator に限定して
bidirectional iterator に対してわざわざ使えなくする必要性は無いよね。

45 ：

そんなことほかにも考えているやついるんじゃないかと思ってググってみたら案の定。
http://www.kmonos.net/wlog/68.html#_2116061224
この人の場合、クイックの後で併用するソートの計算量が良くないねという結論で終わっている。

46 ：

なるほど。ヒープソートも使ってんのか。
それじゃしかたないかもね・・・。

47 ：

そろそろだと思うんだ。
Big-O　ショー　タァーイム！！
Comb Sort11最高。

48 ：

gap ありだと bidirectional iterator に適用し辛いな。
余計なバッファを使う必要がある。

49 ：

シェルソートと似たようなアルゴリズムなのに
何でシェルソートより速いんだろうな。

50 ：

コムソートは平均でも最悪でもほぼO(n log n)でしょ？
理論的限界もO(n log n)じゃなかったっけ？
実装簡単だしメモリ食わないし好きだ。

51 ：

コムソートは欲しいときにすぐ書けるのがいい。
安定でないのが玉にキズだけど。

52 ：

ソートって、データの全てのペア(nC2)についての
比較情報だけ（少し無駄がある）あれば、理論的にはOKだよね？

53 ：

その比較演算が全順序関係になっていると保証できればOK

54 ：

じゃんけん風味だと終わんないもんな

55 ：

>>52
だから普通のソート法は最悪でもO(N^2)のオーダーなわけだ。
ボゴソートのような無茶苦茶なものは除いて・・・。

56 ：

bidirectional iterator に適用できる
メモリ使用量 O(lonN) 以下の
最悪計算時間が O(NlogN) のソート法ってないもんかねえ・・・。
ないことが証明されてたりするのかね。

57 ：

ボゴソートは要らない子

58 ：

>>57
そんな彼が好きなんです。

59 ：

ソート済みのデータでも容量がGBやTBクラスだと
どうやって取り扱ったら良いのか分かりません＞＜

60 ：

ISAMとか真似すれば？

61 ：

B木とかそういうので扱えばいいんじゃないかな

62 ：

shear sortって、wikipedia日本語版では「シェアソート」って紹介されてるのね。
どう聞いても「シア」にしか聞こえないんだけど、「シェアソート」になった由来は何かあるのかな?
# 最近話題の「ウィンド･シア」の方はシェアとは言わんよね。
## あっちの業界はあっちの業界で、「porpoise」を妙ちきりんな読み方しているけど。

63 ：

シェルソートにひきずられたかなぁ？
まぁ古いアルゴリズムとかは妙なカタカナが定着してたりすることは
よくあること...だけど、活字で残ってる用例あるかなぁ。あまり紹介
されないソートだし。てか今知った。

64 ：

最初に訳した奴がバカだったんだろう
そういうのあるよね

65 ：

ねーよｗ

66 ：

ウィキペディアだとありそうだな。
どうもウィキペディアを勉強ノート代わりにしたっぽい奴が書いた項目を見つけて
頭が痛いところだったり。

67 ：

直してあげな。

68 ：

いやぁ、なんか理由があるのかと思って躊躇していたのさ。
誰も直さないようなら、今度暇なときにでも直しておくよ。

69 ：

Googleで検索する限りでは、シアソートって書いてるページ、ほとんどないぞ？

70 ：

シェアソートって書いてあるページも、多くはWikipediaを参照している罠。

71 ：

『アルゴリズム辞典』に載ってればそれに従うところだが、載ってないんだよな。
TAOCPはどうだろう。

72 ：

あらかじめソートされた結果を知っていれば
たとえ
ボゴソートとかであっても恣意的な神の手を加えることにより
ものすごい低いオーダーを実現できるよねｗ

73 ：

安定でマージソートより優秀なのは何？

74 ：

クレオソート

75 ：

バケツソート

76 ：

>>72
ソート済のデータを渡せばO(1)

77 ：

汎用ソートの場合、ifを使わずにreturn a-bとかで直接返した方が効率いいんだろうな。
strcmpやmemcmpとかも使って。可読性は知らんが。

78 ：

>>77
例えばint型のときにreturn a-bなんてしたら、値域が限定されて汎用じゃなくなるよ。

79 ：

それはint型の比較関数としてreturn a-bがふさわしくないから。
ソートの汎用性とは関係ない。
比較関数は比較する型ごとに作るんだよ？わかる？

80 ：

こいつわかってないわ

81 ：

　　 ∧＿∧　　／￣￣￣￣￣
　　（　‘∀‘）＜　オマエガナー
　　（　　　　） 　＼＿＿＿＿＿
　　｜ ｜　|
　　（_＿）＿）

82 ：

つまり、a-bって書くとunsigned同士は勿論、signed同士でも巧くないってことか。

83 ：

int全体の比較関数をa-bと書くのはアホだろ。
単なるバグだし。

84 ：

20億近くまで数字が分布するようなアプリのが少ないから問題ないだろ。
お金周りのアプリなら8バイトなり古典小数点数ライブラリなり使うだろうし。

85 ：

×古典 ○固定

86 ：

会計処理で重要なのは、固定小数点ではなく、十進演算であること

87 ：

JavaのBigDecimalは十進演算だったのか。
言われてJavaDoc覗いて初めて気付いたｗ

88 ：

いや、Decimalって書いてるだろｗ

89 ：

>>84
問題は、その発想のままshort intにまで適用してしまう可能性があることだな。

90 ：

return (a>b)-(a<b);

91 ：

>>87-88

92 ：

表示する時の演算コストを考えてんだろうね

93 ：

Ruby 1.9 And Rails 3.0
http://www.slideshare.net/arrrrcamp/ruby-19-and-rails-30

94 ：

なんでボゾソートがボゴソートより速いのか理解できない

95 ：

∨
[[[[[[[ Ruby 1.9 And Rails 3.0 ]]]]]]]（キリ!!!!キリッッッキリッッッッ!!!!
∧∧∧∧∧∧∧(←きリッッ!!

96 ：

Sleep SortのスリープをCPUクロック数に置き換えたら凄いんじゃね？
しかも超マルチコア前提で

97 ：

よし、O(N)のアルゴを教えてやろう。
ソート前の全組み合わせの膨大なデータを分散ストレージに用意しておくんだ。
ソート処理ではハッシュを計算するだけ。

98 ：

>>97
それってビンソートとどこが違うの？

99 ：

クイックソートをマルチスレッド化したらどれくらい速くなるかなあ？
分割する度に片方の群を別スレッドに渡していくような処理を考えたんだけど
もちろん要素数が少ない時はスレッド分割なしにして
メモリアクセス性能次第かな

100read 1read

1read 100read

TOP カテ一覧 スレ一覧 2ch元 削除依頼 ▲
・　次のスレ
80: Rubyについて（アンチ専用） Part00４ (640)
81: NullPointerExceptionを「ぬるぽ」と呼ぶスレ6 (262)
3: proce55ing　プログラミングアート全般 (569)
4: 関数型プログラミング言語Haskell Part17 (395)