アルゴリズムオタク

1 ：デフォルトの名無しさん：2006/03/07(火) 23:06:03

アルゴリズムを考えるのが好きな人、自分以外にいませんか？
エレベーターを待っているときは、動きを制御するアルゴリズムを考えたり
既存のサブルーチンのアルゴリズムを考えたり、ゲームをやってても敵の
動きのアルゴリズムを考え、ストーリーなどは全く頭に入らない
愛読書は「アルゴリズムとデータ構造？」
言語なんて関係ない！アルゴリズムが好き！

866 ：デフォルトの名無しさん：2008/02/27(水) 16:48:06

より速いの作ってやるぜ

867 ：デフォルトの名無しさん：2008/02/27(水) 16:50:16

貼っちゃった。
int a[size] = {1,2,3,4,5,...};と配列を宣言して、
mysort_bubble(a,size);
mysort_heap(a,size);
というように呼び出します。

void mysort_bubble(int* a, int SIZE)
{
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE-1-i; j++) {
if (a[j] > a[j+1]) {
swap(a[j], a[j+1]);
}
}
}
}

void mysort_heap(int* a, int size)
{
int max = size;
while (max > 0) {
make_heap(a, max, 0);
swap(a[0], a[max-1]);
max--;
}
return;
}

868 ：デフォルトの名無しさん：2008/02/27(水) 16:51:15

続きです。
void make_heap(int* a, int size, int idx)
{
int j = idx * 2 + 1;
int k = idx * 2 + 2;
if (j > size-1) {
return;
}
if (j == size-1) {
if (a[j] > a[idx]) {
swap(a[j], a[idx]);
}
return;
}
make_heap(a, size, j);
make_heap(a, size, k);
int l;
if (a[j] > a[k]) {
l = j;
}
else {
l = k;
}
if (a[idx] < a[l]) {
swap(a[idx], a[l]);
make_heap(a, size, l);
}
return;
}

869 ：866：2008/02/27(水) 17:03:03

#include<iostream>
#include<vector>
#include<time.h>
using namespace std;

#define size 3000000+1
#define rnd(n) ((rand()&255)<<(8*n))
bool comp(const unsigned int &a, const unsigned int &b){return a < b;}

main(){
cout<<size-1<<" 個の配列のソート\n\n";
vector<unsigned int> x(size);
for(int i=0;i<size;i++)x[i]=rnd(0)+rnd(1)+rnd(2)+rnd(3);
int cl=clock();
sort(x.begin(),x.end(),comp);
cl=clock()-cl;
cout<<(cl+0.0)/1000<<"sec\n";
cout<<"x[0]="<<x[0];
cout<<"\nx["<<size-1<<"]="<<x[size-1];
}

870 ：デフォルトの名無しさん：2008/02/27(水) 17:13:34

ありがとうございます。
-cout<<(cl+0.0)/1000<<"sec\n";
+cout<<(cl+0.0)/CLOCKS_PER_SEC<<"sec\n";
ですよね？
(自分の環境では、CLOCKS_PER_SECは1000000でした)。
たしかに、速いですね。

871 ：866：2008/02/27(水) 17:14:22

>>867
鈍すぎ

#include<iostream>
#include<vector>
#include<time.h>
using namespace std;

bool comp(const unsigned int &a, const unsigned int &b){return a < b;}

void mysort_bubble(int* a, int SIZE){
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE-1-i; j++) {
if (a[j] > a[j+1]) {swap(a[j], a[j+1]);}}}}

main(){
int SIZE=30000+1;
cout<<SIZE<<" 個の配列のソート\n\n";
int *a=new int [SIZE]; vector<int> x(SIZE);
for(int i=0;i<SIZE;i++)a[i]=x[i]=rand();
int cl=clock(); sort(x.begin(),x.end(),comp); cl=clock()-cl;
cout<<(cl+0.0)/1000<<"sec\n";cout<<"x[0]="<<x[0];cout<<"\nx["<<SIZE-1<<"]="<<x[SIZE-1]<<"\n\n";

cl=clock(); mysort_bubble(a,SIZE); cl=clock()-cl;
cout<<(cl+0.0)/1000<<"sec\n";cout<<"a[0]="<<a[0];cout<<"\na["<<SIZE-1<<"]="<<a[SIZE-1]<<endl;
}

872 ：デフォルトの名無しさん：2008/02/27(水) 17:23:20

>>864
ちゃんと見ていないけど、
mysort_heap, make_heap のところで 1 ベースの配列用と
0 ベースの配列用のコードが混じってるからおかしくなっているんじゃない？

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

>>863
自己レス。

右寄せってunko1024とunko256ってのがあったら
数字の部分の文字列を抜き出して
256
1024
という風に右寄せしてさらに比較って感じなのかな。

874 ：デフォルトの名無しさん：2008/02/27(水) 18:23:41

あ、スペース消えてる…。
...256
1024

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

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