アルゴリズムオタク

875 ：デフォルトの名無しさん：2008/02/27(水) 19:52:46

>>864
ja.wikipedia 見た．なんだこのクソ実装．

きちんと解析する気も起きんが，このヒープソートは
どれだけよく見積もっても O(n^2) はかかってる，

具体的には make_heap 1 回が，最後の再帰を止めても
O(n) かかり，これを sort_heap で n 回繰り返すので，
最後の再帰が一回も実行されないとして O(n^2)．

876 ：デフォルトの名無しさん：2008/02/27(水) 20:18:05

STLのsortに対抗できないないなら初めからやる意味無し

877 ：デフォルトの名無しさん：2008/03/19(水) 02:28:32

ていうかアルゴリズムの話になるとなんでいつもソートの話にばっかり収斂していくんだろう。
いまさらソートなんてそうとう早くない(ry

878 ：デフォルトの名無しさん：2008/03/19(水) 04:48:20

ネタ振り
ソートと同じでこれまた定番な話題に文字列検索がありますが、
文字列中で、複数の単語の中から最初に現れるものを検索
する場合はどうするのが良いでしょうか？

例
検索対象の文字列 abcdefg
単語 ac bc bd bcd

この場合だと検索結果は bc bcd の2つになる。

879 ：デフォルトの名無しさん：2008/03/19(水) 05:14:01

適当に単語の木を組めばいいんじゃね

880 ：デフォルトの名無しさん：2008/03/19(水) 05:22:02

>>875
ここまで糞なヒープソートも珍しいw
全く理解してないくせによくwikipedia書けるな…

>>864
http://www.sci.csuhayward.edu/~billard/cs3240/node33.html

881 ：デフォルトの名無しさん：2008/03/19(水) 07:07:18

>>878
「最初に現れるものを検索」ってのが理解できない
文字列 abcdefg で単語 bc, de だったら bc だけになるの？

なんにせよ Aho-Corasick の変形でいけそうだけど

882 ：デフォルトの名無しさん：2008/03/19(水) 07:09:57

>>878
ac|bc|bd|bcdを正規表現で検索

883 ：デフォルトの名無しさん：2008/03/19(水) 07:14:43

速度が大事なんだろ
一桁目の、ビットORをとって、対象文字とANDを取り一致すれば調べていけば

884 ：デフォルトの名無しさん：2008/03/19(水) 08:19:57

間違いに気付いたら誰か直して欲しいなあ>>ウィキペ

885 ：デフォルトの名無しさん：2008/03/19(水) 08:50:11

どの記事？

886 ：デフォルトの名無しさん：2008/03/19(水) 08:53:39

http://ja.wikipedia.org/wiki/%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88
これかな

887 ：デフォルトの名無しさん：2008/04/08(火) 21:40:54

アルゴリズムを通信授業で勉強してるんですが
かなりちんぷんかんぷんです
何故5→Aになるのかも意味が分かりません
アルファベットだったら代入するのは何でもいいんでしょうか？
それとも決まってますか？
後アルゴリズムの効率のいい勉強の仕方も教えてくださいｍ＿　＿ｍ

888 ：デフォルトの名無しさん：2008/04/08(火) 21:46:17

>>887
俺にはお前の質問がちんぷんかんぷんだ

889 ：デフォルトの名無しさん：2008/04/08(火) 21:48:34

> 後アルゴリズムの効率のいい勉強の仕方も教えてください

こんなこと言うやつは勉強しても身に付かず、結局
「効率のいいアルゴリズム教えてください」
って言うだけになるんだろうな。

890 ：デフォルトの名無しさん：2008/04/08(火) 21:49:09

＞効率のいい勉強の仕方も教えてくださいｍ＿　＿ｍ

まず国語の勉強。

891 ：デフォルトの名無しさん：2008/04/08(火) 21:56:05

お願いします。教えてください
文章が変なのはリアル厨房なので大目に見てくださいm（＿　＿）m
はじめはアルゴリズムの何を勉強したらいいんでしょうか？

892 ：デフォルトの名無しさん：2008/04/08(火) 22:03:04

「アルゴリズムを勉強する」ためのアルゴリズムを考えてみよう。

893 ：デフォルトの名無しさん：2008/04/08(火) 22:16:48

>>891
コミュニケーションに不自由しない程度の日本語力と
高校程度の数学の能力を身に着けることが先決．

たとえば、
　自然数に対して定義された関数 T(n) に関する漸化式
　T(n) = 2 T([n/2]) + c n, T(1) = c' を考える（c, c' は定数、[ ] は切り上げ）．
　この漸化式の解 T(n) が次の性質を持つことを証明せよ：
　「ある自然数 N と実数 C が存在して任意の n ≧ N に対して T(n) ≦ C n log n」
と言われて自力で証明できないようでは、アルゴリズム論を勉強しても
結局何も身につかない。

894 ：デフォルトの名無しさん：2008/04/08(火) 22:55:18

>>887
本を買え。推薦図書スレで推されている本格的なのを。

895 ：デフォルトの名無しさん：2008/04/08(火) 23:22:08

> 何故5→Aになるのかも意味が分かりません

ああ、まったく意味が分からん。

896 ：デフォルトの名無しさん：2008/04/09(水) 02:18:30

>>887
通信授業でアルゴリズムを勉強していますがかなりチンプンカンプンな状態です。
Ａに５を代入するにはＡ＝５と記述すると習いましたが理解できていません。代入するとはどういう意味なのでしょうか？
またＡ以外のアルファベットにも５を代入できるのでしょうか？それとも代入可能なアルファベットはＡだけなのでしょうか？
あと効率のいい勉強法をお知りでしたらそちらについてもアドバイスお願いいたします。ｍ＿　＿ｍ

897 ：デフォルトの名無しさん：2008/04/09(水) 03:14:11

>>896
代入ってのは変数に値を入れるという意味。
変数ってのは何らかの値を入れるための箱だと思っておけばいい。
そしてここではAってのが箱の名前で、５ってのが箱に入れる値。
ある種のプログラミング言語においてA=5という表現は、
Aという箱に5という値を入れる操作をコンピュータに行わせるという意味であって、
数学における同様の表現とは全く別の意味。
あと箱にAと名付ける事は代入ではないし、箱の名前はAじゃなくてもいい。

898 ：デフォルトの名無しさん：2008/04/09(水) 05:37:03

>>896
普通の（手続き型の）プログラム言語を一つ触ってみるといいんじゃないかな．
Java とか Ruby とか何でもいいから．
そうするとだいぶイメージがわくし，今後のためになるはずよ．

899 ：デフォルトの名無しさん：2008/04/09(水) 08:04:05

その通信授業で、わからないことをとことん聞くことは出来ないのか？
2chで通信授業するのはやめとけ。

900 ：デフォルトの名無しさん：2008/04/09(水) 12:11:16

ガキとオタクと田舎者はネットやんな

901 ：デフォルトの名無しさん：2008/04/09(水) 14:01:06

オタクに教えを請うことがいかに愚かなことか勉強になったな。

どんなことでも、勉強する時は、同じ分野の本を三冊以上読むんだ。
分からないことをスルーしながら、とにかく沢山読む。
すると、何が分からないのかが分かり、何を調べればよいのかがわかるようになるから、それまでに読んだ本から適切な部分を読んで調べることができるようになる。
とにかく沢山読め。

902 ：デフォルトの名無しさん：2008/04/09(水) 21:54:33

オタクってのは自分で勉強したり調べたりってことをしないのかね

903 ：デフォルトの名無しさん：2008/04/09(水) 22:42:35

いや自分で調べるくらい出来ないとオタクにはなれないだろ

904 ：デフォルトの名無しさん：2008/04/09(水) 23:08:16

昔のオタクはそうだったかもしれないが
今のオタクは・・・

905 ：デフォルトの名無しさん：2008/04/10(木) 03:30:22

>>902,903
オタクは自分で調べるが、他人に教えることは不得手。と思う。

906 ：デフォルトの名無しさん：2008/04/10(木) 07:08:41

>>905
オタクってのは自己満足のオナニスト。
知識の切り売りをしているような軽薄な連中とは違うのだよ。

907 ：デフォルトの名無しさん：2008/04/12(土) 12:20:22

>>1きもすぎｗｗｗ
まさかエレベータに乗ってるとき隣の奴がアルゴリズム考えてるとは思わないわ
きもいから死んでくれ

908 ：デフォルトの名無しさん：2008/04/12(土) 14:55:18

まさか、エレベータで隣り合わせた奴に「隣の奴がアルゴリズムを考えている」かどうか意識されているなんて思わないよ。

909 ：デフォルトの名無しさん：2008/04/13(日) 02:44:50

>>907
お前の方がキモイから

910 ：デフォルトの名無しさん：2008/05/06(火) 07:36:00

ｵﾚは小学校のときからﾊﾟﾁﾝｺ屋のﾈｵﾝがどうやって動いてるように見せているのかとか
信号で歩道用と車道用の切り替わりﾀｲﾐﾝｸﾞとかずっと考えてたけどな
そんで周囲からいつもボーっとしてるって言われてた
ココ居るやつらってみんなそんな感じじゃねーの？

911 ：デフォルトの名無しさん：2008/05/06(火) 08:23:00

>>910
あー、なんか判るわ。
私もエレベータの操作パネル見ながら点字を自力解釈したりしてたしね。

912 ：デフォルトの名無しさん：2008/05/06(火) 08:32:23

人工物全般から製作者の意図を考えたりする。

913 ：デフォルトの名無しさん：2008/05/06(火) 09:40:46

>>910
俺は、そういうのはプログラミングを始めてからだな。
ただ、ボーっとしてると言われたっていうのはよくわかるｗ
まさか小学生の子供がそんなこと考えてるとか大人は思いもしないんだよな。

914 ：デフォルトの名無しさん：2008/05/06(火) 18:46:02

点字は自分も考えたわ
ローマ字を習う前だったけど
50音表と睨めっこして
子音＋母音のパターンは見つけた
（母音や子音なんて言葉は知らなかったけど）
その時はボーッとしてるなんて言われてたけど
今は研究職やってます。脳味噌の構造はそのまま

915 ：デフォルトの名無しさん：2008/05/15(木) 04:11:56

過集中って奴じゃないですか。
ボーッとしているように見えるほど没頭するのは。

916 ：デフォルトの名無しさん：2008/05/26(月) 23:16:42

ソートのアルゴリズムなんだけど

　１．ランダムなプログラムをいくつか生成する。
　２．データをプログラムに通す。
　３．出力結果を評価する。
　　　満足のいく速度でデータがソートされれば、終了する。
　　　ダメなプログラムに対しては悪い評価を与える。あるいは破棄する。
　　　それなりに有望なプログラムについては、良い評価を与える。
　４．現在存在するプログラムをもとに、少し違ったプログラムを生み出す。
　５．２へ

これってボゴソートとは違うよね？
時間計算量はどのくらいになるんだろ？
実際、わりと優秀なプログラムが生き残ったっていう話を聞いたけど。

917 ：デフォルトの名無しさん：2008/05/27(火) 00:53:03

それはソートのアルゴリズムってより、遺伝的プログラミングだと思う。

918 ：デフォルトの名無しさん：2008/05/27(火) 01:23:50

>>916
たぶん、本当にそのとおりに実行したら、
現実的な時間ではソートプログラムは作れないと思う。

919 ：デフォルトの名無しさん：2008/05/27(火) 02:31:24

>>916
ソートのアルゴリズムではなくて、個数が20個とかに限定されているときに
最小回数の比較でソートするには何番目と何番目をどの順番で
比較して交換いけばいいか？っていう問題だったと思う。

具体的な実装は>>917。

920 ：デフォルトの名無しさん：2008/05/27(火) 11:41:32

Core2Quad Q9450でPS2エミュをやると、実機と違い処理オチせず、激ムズになることが判明
http://namidame.2ch.net/test/read.cgi/news/1211740649/l50

921 ：デフォルトの名無しさん：2008/06/12(木) 22:56:25

赤黒木を1次元配列で実装したサンプルないですか？

922 ：デフォルトの名無しさん：2008/06/14(土) 11:55:28

>>921
あるよ

923 ：デフォルトの名無しさん：2008/06/15(日) 10:51:10

じゃあ教えて

924 ：デフォルトの名無しさん：2008/06/15(日) 22:49:45

見つかりました。ありがとう。

925 ：デフォルトの名無しさん：2008/06/16(月) 07:44:21

ねーよｗ

926 ：デフォルトの名無しさん：2008/06/16(月) 13:37:39

自己解決しました

927 ：デフォルトの名無しさん：2008/06/16(月) 14:20:28

なかったので自分で作りました。

928 ：デフォルトの名無しさん：2008/06/16(月) 20:45:58

ぐぐっても出てこないので、存在しません

929 ：デフォルトの名無しさん：2008/06/16(月) 21:06:02

ヤフったら出てきたので、存在します

930 ：デフォルトの名無しさん：2008/06/16(月) 22:41:46

まずさ、赤いのか黒いのか、どっちかはっきりしてくれないとわからないだろ？

931 ：デフォルトの名無しさん：2008/06/16(月) 23:51:53

ねーよｗ
はよだせコラ

932 ：デフォルトの名無しさん：2008/06/18(水) 22:11:51

と思ったらあった。すまんw

933 ：デフォルトの名無しさん：2008/06/18(水) 23:09:33

いや、やっぱりこれじゃなかったｗ

934 ：デフォルトの名無しさん：2008/06/19(木) 15:07:20

解決しました。

935 ：デフォルトの名無しさん：2008/06/19(木) 15:11:03

騙るなバカｗ

936 ：デフォルトの名無しさん：2008/06/19(木) 20:52:13

お前らが全然役に立たんので、自力で考えた。
もちろん、教えてなどやらんがなw

937 ：デフォルトの名無しさん：2008/06/19(木) 20:53:46

じゃあ俺も自力で考えたｗ

938 ：デフォルトの名無しさん：2008/06/23(月) 01:03:02

4ビットの値

0000から1111の完全ハッシュ求める式
教えてください

939 ：デフォルトの名無しさん：2008/06/23(月) 01:08:29

>>938
大きさ16のテーブル

940 ：デフォルトの名無しさん：2008/06/23(月) 01:33:56

>>938
0000から1111までの数の全部を対象に完全ハッシュ値を求めたいの？

941 ：デフォルトの名無しさん：2008/06/23(月) 01:38:48

>>938

f(x) = x

942 ：デフォルトの名無しさん：2008/06/24(火) 00:08:53

>>940
部分集合の場合もありえます。

943 ：デフォルトの名無しさん：2008/06/24(火) 00:14:27

だったらその部分集合の性質を知ってないと作れないよ

944 ：デフォルトの名無しさん：2008/06/24(火) 00:25:31

答え知ってると思ってて聞いたけど
オタクとか言うほどレベル高くないんですね

海外じゃ論文とかで有名なネタなのに

945 ：デフォルトの名無しさん：2008/06/24(火) 00:52:37

へぇ
論文見せて

946 ：デフォルトの名無しさん：2008/06/25(水) 12:28:42

>>938が勘違いしてるに1カノッサ

947 ：デフォルトの名無しさん：2008/06/25(水) 23:18:18

ネタ振ったつもりになってるに２ゴールド

948 ：デフォルトの名無しさん：2008/06/26(木) 01:02:59

で、論文は？

949 ：デフォルトの名無しさん：2008/06/26(木) 08:48:35

つ www.google.co.jp

950 ：デフォルトの名無しさん：2008/06/26(木) 08:51:50

アホ？ｗ

951 ：デフォルトの名無しさん：2008/06/26(木) 09:00:41

「ただいま執筆中です」

952 ：デフォルトの名無しさん：2008/07/01(火) 21:31:45

結局出せなかったか
ゴミめ

953 ：デフォルトの名無しさん：2008/08/03(日) 09:51:46

再帰が好きな人います？

954 ：デフォルトの名無しさん：2008/08/03(日) 13:19:42

好きというより得意

955 ：デフォルトの名無しさん：2008/08/03(日) 16:39:00

>>953
昔 LISP 触ってたから、今でも好きだよ。

956 ：デフォルトの名無しさん：2008/08/03(日) 21:23:51

Ｃでも再帰は普通に使うが

957 ：デフォルトの名無しさん：2008/08/04(月) 08:13:09

loop で考えるよりも再帰の方が考えやすい問題もあるわな

958 ：デフォルトの名無しさん：2008/08/04(月) 08:20:33

例えばフィボナッチ数を求める関数を作るときなんかそうだね。
先ずシンプルな再帰版を作って、次に結果を保存する版を作りたくなる。
その辺りで、どうせ組み込み型の整数では実現できる数が少ないことに気付いてテーブル作って終了w

959 ：デフォルトの名無しさん：2008/08/04(月) 08:36:48

n から m まで加算しろ
と, 言われた場合はループも再帰も不可

960 ：デフォルトの名無しさん：2008/08/04(月) 08:59:07

>>958
フィボナッチって、まずループで作っちゃうけどな。

961 ：デフォルトの名無しさん：2008/08/04(月) 09:11:16

ループも再帰も、単なる実装の問題だからどうでもいい。

962 ：デフォルトの名無しさん：2008/08/04(月) 09:22:54

#if 0 // 再帰
int addFromNtoM(int n, int m)
{
if (n < m) return addFromNtoM(n + 1, m) + n;
return m;
}
#elif 0 // 末尾再帰
int addFromNtoM(int n, int m, int s = 0)
{
if (n < m) return addFromNtoM(n + 1, m, s + n);
return s + m;
}
#elif 0 // ループ
int addFromNtoM(int n, int m)
{
int s = m;
for (; n < m; ++n) s += n;
return s;
}
#else // 要はこれになるからループも再帰も不可と言いたいのかな?
int addFromNtoM(int n, int m)
{
return (m + n) * (m - n + 1) / 2;
}
#endif

963 ：デフォルトの名無しさん：2008/08/04(月) 20:02:57

>>960
そもそもフィボナッチを作ろうと思ったことがない。
再帰の例で使われてるのしか見たことない。

964 ：デフォルトの名無しさん：2008/08/04(月) 23:23:48

>>963
つ 木構造
フィボナッチと置換すれ

965 ：デフォルトの名無しさん：2008/08/18(月) 00:54:15

O(1) (笑)

966 ：デフォルトの名無しさん：2008/08/18(月) 01:27:24

STLのpartial_sortの計算時間って、要素数N、ソートする要素数をKとするとNlogKらしいんだけどなんでそうなるの？
http://stdcxx.apache.org/doc/stdlibref/partial-sort.html

967 ：デフォルトの名無しさん：2008/08/18(月) 01:37:51

std::partial_sortって確か内部的にヒープソートを使ってたはず。

968 ：デフォルトの名無しさん：2008/08/18(月) 01:40:14

要素数kのheap作成がO(K)で、その後(N-K)要素をpush/popするのに
一回あたりO(logK)というだけ？

969 ：デフォルトの名無しさん：2008/08/18(月) 01:43:49

最悪の場合な。だから保証されている。
heap木を壊さないために必要。

970 ：デフォルトの名無しさん：2008/08/18(月) 01:44:00

Wikipediaのselection algorithmsのとこに載ってる、O(N+klogk)の変形quicksortの方が速そうだけど、
わざわざヒープを使ってるのには何か理由があるのかなぁ？
http://en.wikipedia.org/wiki/Selection_algorithm#Optimised_sorting_algorithms

971 ：デフォルトの名無しさん：2008/08/18(月) 01:46:18

> heap木を壊さないため

どういうこと?

972 ：デフォルトの名無しさん：2008/08/18(月) 01:47:38

理由はよくわからないが歴史的な経緯により
sort()はクイックソート、stable_sort()にはマージソート、
partial_sortにはヒープソートを使っていると「C++標準ライブラリ」には書いてある。

973 ：デフォルトの名無しさん：2008/08/18(月) 01:48:27

>>971
ヒープソートについてぐぐってみ。
正確にはO(log2N)必要。O記法によりO(logN)になってるだけ。

974 ：デフォルトの名無しさん：2008/08/18(月) 01:51:38

調べてみたらpartial_sort()の目的にヒープソートが合っているかららしい。
クイックソートは途中でソート処理を打ち切るのは困難であるが、
ヒープソートは容易であるのでpartial_sort()の用途に合っている。

975 ：デフォルトの名無しさん：2008/08/18(月) 01:53:03

stable_sortにquickやheapが使えないのはアルゴリズムの性質上そのとおりだと思うけど、安定であることが求められて以内partial_sortにquickが使えないのは納得できないなー。

976 ：デフォルトの名無しさん：2008/08/18(月) 01:55:11

>>974
資料希望。>>970には真逆のことが書いてあるわけで。

977 ：デフォルトの名無しさん：2008/08/18(月) 01:59:42

悔しければC++標準化委員会に入れば？

978 ：デフォルトの名無しさん：2008/08/18(月) 02:03:47

そうする。

979 ：デフォルトの名無しさん：2008/08/18(月) 02:05:08

まあ無理だと思うけど。

980 ：デフォルトの名無しさん：2008/08/18(月) 02:14:42

Wikipediaに書いてあるアルゴリズムは、STLのnth_elementとsortを組み合わせれば、自分でコード書かなくても使えることが分かった。
http://wordaligned.org/articles/top-ten-percent

この記事と同じように速度測ってみて、使い分けることにするわ。スレ違いっぽいのでこのへんで。

981 ：デフォルトの名無しさん：2008/08/20(水) 03:25:02

次スレは？

982 ：デフォルトの名無しさん：2008/08/20(水) 09:59:55

/* ギャップバッファ
http://haiku.mine.nu/gapbuffer.zip
これの、GapBuffer_GetRealPosition()関数の戻り値が何を意味しているのかわかりません。

983 ：デフォルトの名無しさん：2008/08/20(水) 11:01:12

age

984 ：デフォルトの名無しさん：2008/08/20(水) 11:47:53

ギャップバッファー上のバイト位置から、
データとしての先頭からのバイト位置を計算。

return i - (this->end - this->start);
あたりの間違いだろうな。

985 ：デフォルトの名無しさん：2008/08/20(水) 22:42:01

>>384
すみませんが、よくわかりません。
if(i < this->gap_start)
return i - (this->gap_end - this->gap_start)
else
って事ですか？

986 ：デフォルトの名無しさん：2008/08/20(水) 22:51:02

初心者スレ行け