CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。
![50年前に作られたメモリ管理アルゴリズム「Buddy memory allocation」](https://cdn-ak-scissors.b.st-hatena.com/image/square/143d333e266b349775b9c02ff88aa76f25bc6a3d/height=288;version=1;width=512/https%3A%2F%2Fcodezine.jp%2Fstatic%2Fimages%2Farticle%2F9325%2F9325_t.gif)
書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」が近日中に発売される予定です.会津大の渡部先生が著者で,Short Coding 本の Ozy さんと私が協力としての参加です.どうかよろしくお願いします. プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)出版社/メーカー: マイナビ発売日: 2015/01/30メディア: 単行本(ソフトカバー)この商品を含むブログ (4件) を見る 本書はアルゴリズムとデータ構造の入門書です.整列,探索,木構造などをはじめとする基礎的なアルゴリズムとデータ構造を初学者向けに説明します.前提とするのは基礎的なプログラミング能力のみです.コード例では C++ を用いています. これだけだと,よくある本のように思われるかもしれません.しかし,本書は非常にユニークな特徴として,オン
C++で全ての順列を作りたければ、STLにnext_permutation関数があり、以下のように簡単に作ることができる。 #include <iostream> #include <vector> #include <algorithm> int main(){ const int n = 3; std::vector<int> data; // [0, 1, 2, ....]というサイズnの配列を作成 for(int i=0; i<n; ++i){ data.push_back(i); } // 全ての順列を出力 do{ std::cout << "[ " << data[0]; for(unsigned int i=1; i<data.size(); ++i){ std::cout << ", " << data[i]; } std::cout << " ]" << std::end
ACM/ICPC(プログラミングコンテスト)系列の問題を解くことを目標にして,各種アルゴリズムを C++ で実装してみた.極めて意地が悪い類の問題には対応していないし,特定の入力に対して高速に動くということもない.計算量も最良とは限らない. これらを参考にする方への注意とお願い: これらの記述は正確とは限りません.参考文献を参照することを強く推奨します.間違っている場合は是非教えてください. これらのプログラムは間違っているかもしれません.各人で検証することを強く推奨します.バグがあれば是非教えてください. 分類が怪しいので,これはこっちだろう,ということがあればコメントを下さると助かります. 注意! 現在書き換え中 TODO 分類を正しく行う. 全体的に説明と使い方を詳しく. Verify していないものを Verify. ボロノイ図(いつになることやら……) 基本 テンプレート グラフ
概要 MSD Radix Sort による 文字列ソートを OpenMP を用いて並列化した実装です. const char* の配列か,std::string の配列をソートできます. 参考文献の論文に書かれている高速化手法である Loop Fission や Super-Alphabet 等のテクニックや, 配列のコピーを減らす工夫等が導入されています. 使い方 sample.cc や measure.cc を見ると大体分かると思います. コンパイル時に -fopenmp を付けないと並列化されないので注意してください. 逆に,-fopenmp を付けないで,並列化せずに使用することもできます. そのような状況でも std::sort より有意に高速だと思います. 性能 measure.cc で 3 千万個のランダム文字列 (const char*) のソートの時間を測ります. 文字列
Hello World, We Are Phusion. We provide amazing Ruby & Rails products and services to companies that shape our modern day culture. エンタープライズ向けの高速Ruby on Rails実行環境を提供しているPhusionがEfficient substring searching - Phusion Corporate Blogにおいて、特定の文字列からある文字列を検索をするためのアルゴリズムの比較と、その実装系(C++)の公開を実施している。文字列検索はプログラミングで頻出する処理のひとつであり、プログラミング上の参考になる。 文字列から特定の文字列を検出する場合、全体の文字列長(M)と一致させたい文字列の長さ(N)の積O(M*N)が計算量となる。O(M*N)
10:01 10/07/20 それでも2倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ: 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります(途中計算略)。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く