2010年7月29日
#
横浜勉強会、今年で３回目になります。
なんか知らんうちに横浜勉強会のディレクタはデフォルトで僕なんだそうで。
TechEdで横浜に来てるミナサマにもう一泊してもらって
勉強会にお誘いしちゃおうぜ! が当初の目論見だったと記憶しておりますが。
# てゆっか、三年前「いっぺん横浜でやりたいよねー」って
# ぼそっと漏らしたら即ディレクタ拝命。以後なしくずしに...
参加募集はコチラ。
今回けっこーおっきなハコです。スカスカだと寂しいのでみんな遊びにきてください。
こゆーいC++ネタで染めました。僕のはそんなにこゆくないケド。
懇親会は当然横浜中華街。テーブルくるくる回したい方いらっしゃいませ。
# 勉強会キャパに比べ懇親会キャパが小っさいです。
# 早いとこツバつけといてもらわんとあぶれっかもです。
2010年7月25日
#
ドミニオン、ボーズが持ち込んだわけですが。
僕もカミさんもハマっちゃってさ、
陰謀 /
海辺 /
錬金術 も揃えちゃいましたですよ。
こともあろうに
へそくり までも。...あかんなー、陰謀セットだと勝てない orz
きっと魅力的なアクション満載なもんだから財宝を買いそびれ、
資金難に陥っている模様。
ネタ元 → 無駄に並列化してみる
まけるもんかぁ! なTBB版。
#include <iostream>
#include <tbb/tbb.h>
int main() {
const int N = 1000;
std::cout
<< tbb::parallel_reduce(tbb::blocked_range<int>(0,N+1), 0,
// 部分的に積算
[](tbb::blocked_range<int>& range, int count) -> int {
for ( int i = range.begin(); i != range.end(); ++i ) {
int n = i;
do {
if ( n % 10 == 0 ) ++count;
n /= 10;
} while ( n > 0 );
}
return count;
},
// んでもってreduce
[](int x, int y) { return x+y; })
<< std::endl;
}
祭りらしいですのつづき：
文字列に変換して'0'を勘定すんじゃなく、まぢめに各桁の0を勘定するます。
// Radix進数での'桁'
template<unsigned Radix>
class Digit {
private:
unsigned value_; // 値
Digit* next_; // 次の桁
public:
Digit() : value_(), next_(nullptr) { clear(); }
~Digit() { delete next_; }
// increment
void inc() {
// +1して桁あふれコいちまったら
if ( ++value_ == Radix ) {
value_ = 0; // 0に戻して
if ( !next_ ) next_ = new Digit(); // ひとつ上の桁を
next_->inc(); // +1する。
}
}
// n の個数を返す
unsigned count(unsigned n) const
{ return (value_ == n ? 1 : 0) + ( next_ ? next_->count(n) : 0 ); }
void clear() { value_ = 0; if ( next_ ) next_->clear(); }
};
#include <iostream>
int main() {
Digit<10> counter;
unsigned sum = 0;
for ( int i = 0; i < 1001; ++i ) {
sum += counter.count(0); // 0の個数を積算しつつ
counter.inc(); // +1をくりかえす
}
std::cout << sum << std::endl;
}
2010年7月22日
#
ネタ元 → 0から1000までの0の数を数える / 前フリチックにGo-Lang、片桐風味を添えて、~その3~
んではハッタリ臭のぷんぷんするヤツを。C++0Xをテキトーに混ぜて。
#include <iostream>
#include <sstream>
#include <string>
#include <array>
#include <algorithm>
#include <numeric>
int main() {
const int N = 1000;
std::array<int,N+1> ary;
std::iota(ary.begin(),ary.end(),0);
std::ostringstream strm;
std::for_each(ary.begin(),ary.end(),[&](int n) { strm << n; });
std::string str = strm.str();
std::cout << std::count(str.begin(), str.end(), '0') << std::endl;
}
2010年7月17日
#
ネタ元 → [勉強会]セッション資料公開
かたっぱしからportしていただきました。ありがとさんすー
本業でJava漬けなもんだから休日はC++、TBBのthreadとtaskで遊ぶよ♪
インテルTBBによる選択ソートの高速化 では tbb::parallel_invoke で
ソート範囲の前半部/後半部を同時並行実行したです。
これを フツーにスレッド使ってやってみる。 つまりこの:
ソートする(こっから, ここまで) {
こっから と ここまで を前半部[こっから..まんなか] と [まんなか..ここまで] に分割する。
スレッド起こして ソートする(こっから, まんなか)
スレッド起こして ソートする(まんなか, ここまで)
スレッドの完了を待つ
}
なんてな。
TBBには parallel_なんとか 関数が提供されてて、大抵の用途にはこいつらで事足ります。
が、parallel_なんとか では済まないケースもございます。TBBにはstd::threadコンパチのthread
があるんで、(この例ではparallel_invokeで書けるんだけども)thread使うとこんなコードになるです。
/*
* 前半部/後半部に分け、それぞれをthreadでsortする
*/
void sort_thread_entry(vector<string>::iterator first, vector<string>::iterator last) {
typedef vector<string>::difference_type difference_type;
difference_type size = distance(first,last);
// 要素数が cutoff 未満なら素直にselection_sort
if ( size < cutoff ) {
selection_sort(first, last);
} // さもなくば
else {
vector<string>::iterator mid = first;
advance(mid, size/2);
// [first,mid) : 小さい要素群 と [mid,last) : 大きい要素群 に振り分けて
nth_element(first, mid, last);
// それぞれをソートするthreadを作り
thread lo(&sort_thread_entry, first, mid);
thread hi(&sort_thread_entry, mid, last);
// 双方の完了を待つ
lo.join();
hi.join();
}
}
...あのね、こんなことやっちゃダメですよ。
いやダメってことはないけど何事も限度てーもんがあって、こんなことしたら山ほどスレッド起こすことになります。
僕の環境では8!(40320)個の要素をソートしようとしたらば 32bit ではリソース枯渇して落ちてしまいました。
加えてこのコード、決して性能よくないんです。std::sortと比べてみたらば:
quick sort ... 0.130405 [sec]
sort_thread ... 0.63766 [sec]
2コア使ってるクセしてstd::sortに負けてます。
たくさんのスレッドを起こすことになり、
スレッドの切り替えにかかるオーバヘッドがバカにならんのでしょう。
実際TBBのマニュアルには:
Threads are heavy weight entities on most systems, and running too many threads on
a system can seriously degrade performance. Consider using a task based solution
instead if practical.
ぶっちゃけthreadは重いしさ、よぉけthread起こすとパフォーマンス低下がシャレならんのよ。
んだから実務ではtask-baseにしとき。悪いこと言わんから。
と明記されちょるです。
parallel_なんとかが使えないなら次善の策はtask使え。万策尽きたらthreadに手を伸ばしてもいい、と。
んじゃそのtask-baseゆーのんを使ってみると、だ。
quick sort ... 0.130405 [sec]
selection_sort ... 39.5528 [sec]
sort_thread ... 0.63766 [sec]
sort_task ... 0.0860738 [sec]
ってことで std::sort に勝つるです。4コア/8コアならもっと速くなるはずっす。
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <functional>
#include <cassert>
#include <tbb/tbb.h>
#include <tbb/compat/thread> // std::thread の TBBによる実装
using namespace std;
// 単純選択ソート
template<typename InputIterator>
void selection_sort(InputIterator first, InputIterator last) {
while ( first != last ) {
iter_swap(first, min_element(first,last));
++first;
}
}
static const int cutoff = 30;
/*
* 前半部/後半部に分け、それぞれをthreadでsortする
*/
void sort_thread_entry(vector<string>::iterator first, vector<string>::iterator last) {
typedef vector<string>::difference_type difference_type;
difference_type size = distance(first,last);
// 要素数が cutoff 未満なら素直にselection_sort
if ( size < cutoff ) {
selection_sort(first, last);
} // さもなくば
else {
vector<string>::iterator mid = first;
advance(mid, size/2);
// [first,mid) : 小さい要素群 と [mid,last) : 大きい要素群 に振り分けて
nth_element(first, mid, last);
// それぞれをソートするthreadを作り
thread lo(&sort_thread_entry, first, mid);
thread hi(&sort_thread_entry, mid, last);
// 双方の完了を待つ
lo.join();
hi.join();
}
}
/*
* 前半部/後半部に分け、それぞれをtaskでsortする
*/
class sort_task : public tbb::task {
public:
typedef vector<string>::iterator iterator;
typedef vector<string>::difference_type difference_type;
protected:
iterator first;
iterator last;
public:
sort_task(iterator f, iterator l) : first(f), last(l) {}
task* execute() {
difference_type size = distance(first,last);
// 要素数が cutoff 未満なら素直にselection_sort
if ( size < cutoff ) {
selection_sort(first, last);
} // さもなくば
else {
iterator mid = first;
advance(mid, size/2);
// [first,mid) : 小さい要素群 と [mid,last) : 大きい要素群 に振り分けて
nth_element(first, mid, last);
// それぞれをソートするtaskを作り
task* left_task = new( allocate_child() ) sort_task(first, mid);
task* right_task = new( allocate_child() ) sort_task(mid, last);
// 双方を起動して完了を待つ
set_ref_count(3);
spawn(*left_task);
spawn_and_wait_for_all(*right_task);
}
return 0;
}
};
int main() {
vector<string> source;
{
string value = "ABCDEFGH";
do {
source.push_back(value);
} while ( next_permutation(value.begin(), value.end()) );
assert( is_sorted(source.begin(), source.end()) );
random_shuffle(source.begin(), source.end());
}
{
cout << "quick sort ... " << flush;
vector<string> input = source;
tbb::tick_count t = tbb::tick_count::now();
sort(input.begin(), input.end());
cout << (tbb::tick_count::now() - t).seconds() << " [sec]\n";
assert( is_sorted(input.begin(), input.end()) );
}
{
cout << "selection_sort ... " << flush;
vector<string> input = source;
tbb::tick_count t = tbb::tick_count::now();
selection_sort( input.begin(), input.end());
cout << (tbb::tick_count::now() - t).seconds() << " [sec]\n";
assert( is_sorted(input.begin(), input.end()) );
}
{
cout << "sort_thread ... " << flush;
vector<string> input = source;
tbb::tick_count t = tbb::tick_count::now();
thread sort_th(&sort_thread_entry, input.begin(), input.end());
sort_th.join();
cout << (tbb::tick_count::now() - t).seconds() << " [sec]\n";
assert( is_sorted(input.begin(), input.end()) );
}
{
cout << "sort_task ... " << flush;
vector<string> input = source;
tbb::task* tsk = new(tbb::task::allocate_root()) sort_task(input.begin(), input.end());
tbb::tick_count t = tbb::tick_count::now();
tbb::task::spawn_root_and_wait(*tsk);
cout << (tbb::tick_count::now() - t).seconds() << " [sec]\n";
assert( is_sorted(input.begin(), input.end()) );
}
}
ここんとと三か月あまり、ずっとJavaばっかやってます＠本業。
Web-pageの自動運転を頼まれたのをきっかけに、Excel帳票を食わせて
Web-formに転記するだとか、<table>よんでExcelに書き戻せとか。
人様が操作するのを前提としたWeb-pageを機械にいぢらせるのは
めんどっちーったらありゃしねぇっす。 Web-serviceを提供してくれたら
それで全部解決すんだけどそれがままならんってことらしっす。
そんなこんなであちこちからライブラリやらツールやらをかき集めて
実装しておるわけですが(このテのリサーチが主業務なんすけどね)、
Javaも慣れるといいもんですねぇ。
でね、Web-form上にtextboxと"参照..."ボタンを並べた「UPLOAD」あるや
ないですか。こいつを機械でいぢれとの依頼がありまして、
ここで"参照..."押しちゃうわけにいかんのです。textboxにupload対象である
ファイルのpathを打ち込みたいんだけどここってread-onlyになってるポ。
困ったねー... textboxのread-only属性の裏をかきたいんだけども。
# なんぞ心当たりございましたらご一報くださいまし。 > だれぞ
2010年7月2日
#
ここんとこ毎日、晩飯おわるとやってます、ドミニオン(ついでに海辺も)。
おもしろいねー、毎回変わる戦略と駆け引き、公領一枚の攻防に呪いの応酬。
改築と研究所と礼拝堂が大好きです♪
2010年6月23日
#
Visual C++ 2010に追加されたSTLアルゴリズム@CodeZine で忘れてたのがありました。
■ minmax_element
template<class Iterator, class Predicate>
std::pair<Iterator,Iterator>
minmax_element(Iterator first, Iterator last, Predicate pred);
シーケンス[first,last)から、最初に見つけた最小要素 と 最後に見つけた最大要素 を指すイテレータをペアにして返します。
最小/最大要素を見つけてくれるアルゴリズムはそれぞれmin_element/max_elementがあるんだけど、minmax_elementはそいつらの合わせ技。
大きなメリットはmin_element,max_elementを一度ずつ呼び出すより速いす。要素数Nに対し3/2N程度だそうで、前者の2Nに比べて25%ほどの時短となるます。
コレ使って単純選択ソートをちょびっと速くします。単純選択ソートのアルゴリズムはめっちゃ単純:
「i=0..N-1に対し、data[i]～data[N-1]中の最少要素とdata[i]を交換する」こんだけ。コード書けば:
while ( first != last ) {
iter_swap(first, min_element(first,last));
++first;
}
loop回るたんびに未ソートな要素がいっこずつ減ってくんだから、minmax_elementならふたっつずつ減ってくれんでないのん? と。
ってなわけで書いてみた。ソート対象は挿入/削除がチョー速いlist<T>で。
#include <iostream>
#include <array>
#include <list>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <windows.h>
using namespace std;
// フツーの単純選択ソート
DWORD min_selection_sort(list<int>& data) {
DWORD t = GetTickCount();
for ( auto first = data.begin(); first != data.end(); ++first ) {
iter_swap(first,min_element(first,data.end()));
}
return GetTickCount() - t;
}
// ヒネクレた単純選択ソート
DWORD minmax_selection_sort(list<int>& data) {
DWORD t = GetTickCount();
list<int> smaller, bigger;
while ( !data.empty() ) {
auto mm_pair = minmax_element(data.begin(),data.end());
smaller.splice(smaller.end(), data, mm_pair.first);
if ( mm_pair.first != mm_pair.second ) {
bigger.splice(bigger.begin(), data, mm_pair.second);
}
}
data.splice(data.begin(),bigger);
data.splice(data.begin(),smaller);
return GetTickCount() - t;
}
int main() {
const int N = 20000;
array<int,N> src;
iota(src.begin(),src.end(),0);
random_shuffle(src.begin(),src.end());
DWORD t;
list<int> data;
data.assign(src.begin(),src.end());
t = min_selection_sort(data);
assert( is_sorted(data.begin(), data.end()));
cout << t << endl;
data.assign(src.begin(),src.end());
t = minmax_selection_sort(data);
assert( is_sorted(data.begin(), data.end()));
cout << t << endl;
}
実行結果:
1092 (min_selection)
967 (minmax_selection)
一割ちょいかー、けっこーややこしくなってっから、こんなもんかなー
もっとエレガントな実装がありそな希ガス。
2010年6月22日
#
ネタ元 →
Multi-Core と Multi-Thread のコメント:
どこまでをバブルソートと呼ぶかにもよるけど、交換の仕方を調整すると並列にできますよ、という例。
http://ja.wikipedia.org/wiki/奇偶転置ソート
ただ並列にする処理の1つ1つがとても小さいので、有意な差は出るかどうかは謎。
やってみよぉぢゃありませんか。
# いやさとっちゃんが急遽倍尺でやらんならんそぉなので、ネタ出しに協力的意味でｗｗｗ
1 7 6 5 8 2 4 3 があったとき、
[1] ふたつずつのペアをつくる。1 7 6 5 8 2 4 3
[2] それぞれのペアについて必要なら入れ替え 1 7 5 6 2 8 3 4
[3] ひとつずらしてペアをつくる 1 7 5 6 2 8 3 4
[4] それぞれのペアについて必要なら入れ替え1 5 7 2 6 3 8 4
[5] [1]～[4] をくりかえし。
[2],[4] の際、ペアの入れ替えは互いに独立だから並行処理できんぢゃん、と。
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <ppl.h>
#include <Windows.h>
using namespace std;
using namespace Concurrency;
// 単スレッドで地道にソート
void single_bubble_sort(int* data, int N) {
bool swapped;
auto swapper = [&](int i) {
if ( data[i] > data[i+1] ) {
iter_swap(data+i,data+i+1);
swapped = true;
}
};
do {
swapped = false;
for ( int i = 0; i < N-1; i += 2 ) { swapper(i); }
for ( int i = 1; i < N-1; i += 2 ) { swapper(i); }
} while ( swapped );
}
// PPLで並行処理
void multi_bubble_sort(int* data, int N) {
bool swapped;
auto swapper = [&](int i) {
if ( data[i] > data[i+1] ) {
iter_swap(data+i,data+i+1);
swapped = true;
}
};
do {
swapped = false;
parallel_for(0,N-1,2,swapper); // へーこー
parallel_for(1,N-1,2,swapper); // しょり
} while ( swapped );
}
int main() {
const int N = 10000;
int* src = new int[N];
iota(src, src+N, 10);
random_shuffle(src,src+N);
int* data = new int[N];
DWORD t0, t1;
copy(src,src+N,data);
t0 = GetTickCount();
single_bubble_sort(data,N);
t1 = GetTickCount();
assert( is_sorted(data,data+N) );
cout << (t1 - t0) << endl;
copy(src,src+N,data);
t0 = GetTickCount();
multi_bubble_sort(data,N);
t1 = GetTickCount();
assert( is_sorted(data,data+N) );
cout << (t1 - t0) << endl;
delete[] data;
delete[] src;
}
こいつを実行するとですね:
171 (single)
2855 (multi)
なんともトホホな結果です。処理単位があまりにちんこいために、
スレッド/タスクこしらえたり切り替えたりのコストをペイできんのですな。
# dual-coreでの結果です。octa-coreくらいになればちっとはマシかも。
2010年6月19日
#
片桐姐さんから頂戴したマザボにRadeon HD5450グラボ挿した愛機、
そーいやindex見てなかったなーと。
グラフィック性能にがっかり感が漂ってます。もちーとマシなの載せてあげたい。
ってんでアキバのつくもﾀﾝに相談しに行ったの。
バッキバキにゴキゲンなグラボ載せるのも酔狂で面白くはあるのだけども、
電源余裕しゃくしゃくってーほどでもない(いやむしろカツカツに近い)ので
マザボ給電だけで済む省電力グラボを見繕ってまいりました。
左:現行機Radeon HD5450 / 右:期待の新人Radeon HD5670 (どっちもSapphire製)
下:とっちゃんにもらったハコ / ずっと奥:片桐姐さんにもらった母板
下左: 400W(peak-450W)ちとショボめの電源@グラボ用6/8-pinがなぁいｗｗ
...で、結果です。
あの……がっかり感が増大しているのは気のせいですか?
2010年6月16日
#
VC++2010に追加されたアルゴリズム、まとめて紹介しましたー@CodeZine
Visual C++ 2010に追加されたSTLアルゴリズム
こんなもんアキラくんトコとか御本家とかいけばころがってんだけどもさ。
2010年6月12日
#
ネタ元 →
JAVAでCSV読み込み
CSVファイルとして
testd,10,20,30,40,50
test1,60,70,80,90,100
test2,110,120,130,140,150
などがあり一番初めの列と与えられた引数と一致するキーの行を取得しして、Listに格納したいです。
たとえば与えられた引数がtest1だとしたら
Listに60,70,80,90,100をaddしたいんです。
更に機能として与えられた引数がtest3とかで
CSVファイルに存在しない場合はtestdという行を
Listに10,20,30,40,50をaddできたらと考えております。
ふむ。
import java.io.*;
import java.util.*;
public class foo {
public static void main(String[] args) throws Exception {
FileInputStream fistream = new FileInputStream("trial.csv");
InputStreamReader sreader = new InputStreamReader(fistream);
BufferedReader reader = new BufferedReader(sreader);
String line;
String target = "test1";
boolean found = false;
List<Integer> default_result = new ArrayList<Integer>();
List<Integer> result = new ArrayList<Integer>();
while ( (line = reader.readLine()) != null ) {
StringTokenizer tokenizer = new StringTokenizer(line,",");
if ( tokenizer.hasMoreTokens() ) {
String key = tokenizer.nextToken();
if ( key.equals("testd") ) {
while ( tokenizer.hasMoreTokens() ) {
default_result.add(Integer.parseInt(tokenizer.nextToken()));
}
}
else if ( key.equals(target) ) {
found = true;
while ( tokenizer.hasMoreTokens() ) {
result.add(Integer.parseInt(tokenizer.nextToken()));
}
}
}
}
reader.close();
if ( !found ) result = default_result;
for ( int n : result ) {
System.out.println(n);
}
}
}
テキストファイルの読み込み / 文字列のカンマによる分割 / 数字→数値変換
のみっつを
組み合わせるだけなんだけども、それぞれを組み合わせるっちゅーのが
ビギナには難しいんかな。んでもそこんとこが
キモなのね。
それができんといつまでたっても犬小屋は作れても一戸建ては作れない。
どんなにデカくややこしいコードであれど、シンプルな部品の組み合わせでしかないわけで。
2010年6月9日
#
先日からどーもかんばしくなかったのね、DVDドライブ。
読みはいいんだけども書き損じが目立ってきてたし、
P-ATAのケーブルはいーかげんウザいし。
会社帰りにアキバ行ってきたです。
毎度お馴染みツクモの一階でバッファローのが2,980円即買い。
# ナカミはSONY-optiarc製らしい。
んでもってついでにDVDメディア50枚スピンドル買ったらばおマケがついてました。
つくもﾀﾝ と らびﾀﾝ のﾊﾝﾄﾞﾀｵﾙっすー
えーとしコいたおっさんがポケットから出すにはいささか躊躇しま...せんっ!
# どのコがお好みでしょうか? > ﾐﾅｻﾏ
またしてもTBBネタ。
TBB3.0が早々とVisual C++ 2010に対応してくれたので、
VS2010リリースのご祝儀かたがたCodeZineに書きました。
インテルTBB3.0によるパイプライン処理
よーするにマルチスレッドで「流れ作業」をやらせようって魂胆です。
いやもー早速とっちゃんにパクっていただき光栄のいったりきたりですわ。