線形探索を高速化する単純なアイデア
線形探索というアルゴリズムがあります。 これは、プログラムを勉強する上では避けて通れない基本的なアルゴリズムです。
線形探索とはなにかというと、 ある配列があったとき、その中身を先頭から最後尾にかけて順番に走査していこうという考え方のことです。 線形探索はこのように単純でわかりやすいので実装が簡単ですが、配列の要素数が大きくなるとそれだけ時間がかかるようになってしまいます。 これを解消するようなアルゴリズムとして2分探索がありますがその話はまた後日しますん。
今回はこの線形探索をどうしたら高速化できるかを思いついたので、実装して検証してみましょうという企画です。
さっそく本題に入りましょう。 今回、思いついたアイデアというのは線形探索のスレッド化です。
説明のために図を用意しました。(褒めて)
通常の線形探索では図のようにそれぞれの配列を一つずつ探索していきます。 それと比較して、スレッドを使用した線形探索では複数の要素を複数のスレッドにより一気に探索することができます。
線形探索はメモリ効率が最適です。 メモリ効率とは次に探索する要素がどれだけ近くにあるかを示す指標です。 メモリ効率がいい、すなわち、次に探索する要素が近くにあれば、探索の時間は短縮されます。 もし、次に探索する要素が遠くにあった場合には、それだけ探索に時間がかかるようになります。 線形探索では、常に隣の要素を探索するためメモリ効率は最適と言っても過言では無いでしょう。(間違ってたら助けて) スレッドを使用した線形探索においても、常に近いところを探索し続けるため、メモリ効率は良いといえます。
次に実装の話に移りましょう。
スレッドは共有メモリを使用しています。 説明がめんどくさいので適当ですが、1つのプログラムで走っているよ、だからどのすれっどからも1つのメモリ空間にアクセスできるよみたいなものです。
線形探索にスレッドを適用する場合、この共有メモリの概念が重要になります。 スレッドには関数のように返り値を返すといった仕様がありません。 そこでグローバル変数を使用して、返り値の代わりをしてもらいます。
というところで飽きてきたのでプログラムはこうなります。
逐次処理
#include <stdio.h> #include <stdlib.h> #include <time.h> #define SIZE 8192 int flg = 0; int* array; int main() { int i; clock_t start, end; array = (int*)calloc(sizeof(int),SIZE); array[SIZE-1] = 1; start = clock(); for (i=0; i<SIZE; i++) { if (array[i]) { flg = 1; break; } } end = clock(); if (flg) printf("みつけたぞ\n"); else printf("なんぞこれ\n"); printf("%lf秒もかかったぞ\n", (double)(end - start) / CLOCKS_PER_SEC); free(array); return 0; }
スレッドを使用
#include <stdio.h> #include <stdlib.h> #include <time.h> #include <thread> #include <vector> #define SIZE 8192 #define THREAD_NUM 32 int flg = 0; int* array; void func(int i) { if (array[i]) { flg = 1; return; } return; } int main() { int i, j; clock_t start, end; array = (int*)calloc(sizeof(int),SIZE); array[SIZE-1] = 1; std::vector<std::thread> th_group; start = clock(); for (i=0; i<SIZE; i+=THREAD_NUM) { for (j=0; j<THREAD_NUM; j++) { th_group.push_back(std::thread(func, i+j)); } for (auto itr=th_group.begin(); itr!=th_group.end(); ++itr) { itr->join(); } th_group.resize(0); if (flg) { break; } } end = clock(); if (flg) printf("みつけたぞ\n"); else printf("なんぞこれ\n"); printf("%lf秒もかかったぞ\n", (double)(end - start) / CLOCKS_PER_SEC); free(array); return 0; }
要素数8192で比較。
逐次処理
みつけたぞ 0.000000秒もかかったぞ
スレッドを使用した場合
みつけたぞ 0.859375秒もかかったぞ
あれれー、おかしいぞー? スレッド化のメリットよりもスレッド生成のコストが上回ったっていうことなのかー? そーなのかー。
といった話でした。
まとめ。
なんでもかんでもスレッド使えばいいってもんじゃないね。 はぁ…。
c++のスレッドで返り値が欲しいのならば
返り値に代わる変数を渡せばいいじゃない。
#include <thread> #include <stdio.h> int th(int* ret) { printf("1"); ret = 1; return 1; } int main() { int ret; std::thread th(th, &ret); th.join(); return 0; }
ね、簡単でしょ。
ラズベリーパイの固定IP覚え書き(ネットに繋がらない場合)
ラズパイを固定IPにするには以下の設定をする。
sudo nano /etc/network/interfaces
iface eth0 inet static address 192.168.1.* netmask 255.255.255.0 gateway 192.168.1.1
ラズパイを固定IPにしたらネットに繋がらなくなった。 (apt-getでエラーを吐く、Webページが表示されない)
原因は2つ。
まずひとつ目は、gatewayが正しく設定されていなかったから。 正しいgatewayはラズパイに直結しているルータのプライベートIPである。
二つ目は、DNSサーバの設定がうまくいっていないから。 DNSを設定するには/etc/resolv.confにIPアドレスを追加する。
sudo nano /etc/resolv.conf
nameserver *.*.*.*
resolv.confは再起動のときに追加した内容が削除されることがある。 解決するにはinterfacesにDNSのIPアドレスを設定すればいい。
sudo nano /etc/network/interfaces
dns-nameserver *.*.*.*
ということで時間を潰すことのないようにしたいものです。
「乙嫁語り」のパリヤさんがにんまり不器用可愛い
「乙嫁語り」8巻読みました 相変わらずの緻密な書き込みに圧倒されます。
8巻の主役は「まだあわてあわてあわわわわわ」と言い出しそうなこの女の子。 名前はパリヤさん。
8巻を読んで感動しました。 なにに感動したかって? パリヤさんの可愛さにですよ。
パリヤさんはね人付き合いが苦手なんです。 なかなか自分をうまく出せないのです。 赤面に沈黙を貫いた挙句、言っちゃいけないことも言っちゃう、良く言えば「本音」をぶつける、悪く言えば「面倒な」な女の子でした。 もっと明確に言えば「ツンデレ」な女の子でした。
「乙嫁語り」の舞台では、年頃の女の子を「嫁入り」に出すのが風習です。 お年頃のパリヤさんも「嫁入り」の準備を進めていました。 しかし、この地方の殿方には「ツンデレ」の良さがわからなかったのか、 パリヤさんは「嫁入り」を断られ続けるのです。 そんなパリヤさんも「女は強気の方がいい」というわかってるな感を出す男の子とようやく巡り合うのですが、 主人公を巡って起こった民族間紛争(6巻参照)により嫁入り道具の大半が焼失してしまうという不幸に見舞われます。
長い年月をかけて準備してきた嫁入り道具。 もう一度準備が整うまで早くても2、3年は必要だそうで。 一度「自分は結婚できないんですよ、そういう星の下に」的な一悶着もありながら、パリヤさん一同は「嫁入り」の準備に取り掛かります。
パリヤさん達の民族は刺繍にこだわりがあり、皆さん刺繍の入った華やかな衣装を着ています。 嫁入りの際には刺繍を入れた布製品をたくさん用意する習わしがあるようで、その準備が大変だとか。
パリヤさんは刺繍が苦手。パン作りは得意だけど刺繍は苦手。 族長の指導のもと、嫁入り修行の始まりです。 「誰かを思って縫いなさい」 族長からの言葉を聞いて刺繍に取り組むパリヤさん。 誰を思って縫ったのか。 答えは聞くまでもありませんが、「あれれーまったく検討もつかないな―」という方のためにここで大ヒント。
恋する乙女の顔ですよ、こいつぁ…。
ついにあらわになったパリヤさんの女子力。 その後のパリヤさんはひと針ごとに「未来のお婿さん」のことを思い浮かべるのでした 。
にやにやがとまらないよパリヤさん!!!
笑顔が不器用すぎるよパリヤさん!!!
私、わかりました。 女の子の可愛さは笑顔にあったんですね。
- 作者: 森薫
- 出版社/メーカー: KADOKAWA/エンターブレイン
- 発売日: 2015/12/14
- メディア: コミック
- この商品を含むブログ (30件) を見る
訳あって、各文字の出現回数を測定するプログラム(C)を書いた。
訳あって、各文字の出現回数を測定するプログラムをC言語で書きました。
(こういう処理ってどういう名前がついてるなの…? word countであってるなの…?)
プログラムを書くにあたって、二通りに場合分けをしました。 一つは0回以上出現した文字だけを測定して出力する場合、 もう一つは任意の文字だけを測定する場合。
まずは0回以上登場した文字だけを測定して出力するプログラム。
#include <stdio.h> #include <math.h> int main() { size_t size = pow(2, 8); // 1byte = 2^8bit int word_counts[size]; char c; int i; // 初期化 for (i=0; i<size; i++) { word_counts[i] = 0; } // 文字数をカウント while(scanf("%c", &c)!=EOF) { if (c == '\n') continue; // 改行は無視 if (c == ' ') continue; // スペースは無視 word_counts[c]++; } // カウントが1以上の文字のみ出力(文字 カウント) for(i=0; i<size; i++) { if(word_counts[i]==0) continue; printf("%c %d\n", (char)i, word_counts[i]); } return 1; }
次に任意の文字の出現回数を測定するプログラム。
#include <stdio.h> #include <string.h> #include <stdlib.h> char *template = "abcdefghijklmnopqrstuvwxyg0123456789" int main() { size_t size = strlen(template); // templateの文字数 int word_counts[size]; char c; char *str; int i; int index; // 初期化 for (i=0; i<size; i++) { word_counts[i] = 0; } // 文字数をカウント while(scanf("%c", &c)!=EOF) { str = strchr(template, c); if(str==NULL) continue; // cで指定した文字が見つからなかったら次の文字へ index = size - strlen(str); word_counts[index]++; } // templateとword_countsを対応付けて出力(文字 カウント) for(i=0; i<size; i++) { printf("%c %d\n", template[i], word_counts[i]); } return 1; }
前者は後者よりもメモリを多く使う代わりに高速。
後者は前者よりも遅いが、使用するメモリ領域が少ない。