「凸頂点の数」の実装例と、若干の解説解題 - Qiita
問題 http://nabetani.sakura.ne.jp/hena/orde03nofconv/ 実装リンク集 http://qiita.com/Nabetani/items/b8bf742d278c6cf501aa です。 解題 今回は珍しく、問題を考える前に図を書いた。 図を眺めながらどんな問題にしようか考えて、この問題に至った。 要するに、行き当たりばったりである。 マス目を歩くのはやったし、辺の数を数える問題も出した。 頂点の数は辺の数と同じだし、どうしよう。 そうだ。凸頂点にしよう。という具合。 行き当たりばったりである。 実装１ 私が普通だと思っていた実装は def neibour?(a,b) a,b=[a,b].sort dy = (b[1]-a[1])%20 return [1,19].include? dy if a[0]==b[0] return [0,19].i
C++で様々なソートアルゴリズムを実装する - Qiita
STLにはstd::sortというソートアルゴリズムが用意されています。これはランダムアクセスイテレータ２つを入力とし、破壊的な操作をする関数ですね。これと同じシグニチャで色々なソートアルゴリズムを実装してみたいと思います。wikipediaを参考にしています。詳しい説明はwikipediaをご覧ください。 学校の課題とかで丸写ししちゃだめだよ。 ちなみにSTLを全力で使います。C++らしさを出すために基本的には添え字ではなくイテレータを操作するようにしています。 1/28/2016 追記; イテレータの情報をstd::iterator_traitsを使って取得するように記事を改めました。C++11までは推奨といったところですが、C++14からは必須だったと記憶しています。 また思いつきで書いていたコードを多少直しました。 iter_sorting_swap 最初に、あるヘルパ関数を紹介い
ズンドコキヨシ with C using 128bit XORshift(擬似乱数生成) - Qiita
#include <stdio.h> #include <stdint.h> // Thaks to http://d.hatena.ne.jp/jetbead uint32_t xor128(void){ static uint32_t x = 123456789; static uint32_t y = 362436069; static uint32_t z = 521288629; static uint32_t w = 88675123; uint32_t t; t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } int main(void) { int idx; uint32_t val; int zuncnt = 0; for(idx = 0; idx <
ナップサック問題 - Qiita
「重さが1,3,5,6,8 という5つの品物をいくつか選んで、最も10に近づけるにはどう組み合わせればいいか」 こういう問題のことをナップサック問題といいます。 今回は1,3,6と詰めれば、丁度10になりますが、どのように組みわせてもぴったりになることはない問題もあります ナップサック問題 一次元のタイルパズルという感じで簡単そうに見えますが、完全に求めるには総当りしかない、結構厄介な問題です 品物の候補が100個ある場合、2^100通りの選び方があるのでとてもまともには計算できません そこで、枝刈りポイントを探していきましょう 多くの場合は、100個の品物があっても、せいぜい入るのは10個前後でしょう ですので、全てをチェックする必要がないことがわかります 入るパターンを効率よく探すために、以下のアルゴリズムで探索していきます まず、メモを用意して、1個目の品物の重さを書きます 2個目は
A practical guide to SSE SIMD with C++
A practical guide to SSE SIMD with C++ First published 22. September 2009 This is a guide to Streaming SIMD Extensions with operation system independent C++. Also the details and troubles of SIMD designing with SSE will be addressed in detail. 1.0 Introduction 2.0 What is SIMD? 3.0 Effective use of SSE 4.0 Data structures with SSE 5.0 Mask operations 6.0 C++ SSE header Algorithm example 1 - Vector
なんでGCCはa*a*a*a*a*a を (a*a*a)*(a*a*a) に最適化できないの？っと
c - Why doesn't GCC optimize a*a*a*a*a*a to (a*a*a)*(a*a*a)? - Stack Overflow 俺は科学技術計算の数値計算の最適化をしてたんだけどさ。GCCはpow(a, 2)をa*aにしてくれるんだな。うん。で、pow(a, 6)は最適化されずに、ライブラリ関数であるpowを呼んじゃうんだ。パフォーマンス的に最悪。(Intel C++ Compilerはpow(a,6)のライブラリ関数呼び出しを消し去ってくれるんだけどな) どうもよくわからんのが、pow(a, 6)をa*a*a*a*a*aで置き換えて、GCC 4.5.1をオプション"-O3 -lm -funroll-loops -msse4"で使ったら、mulsd命令を5個使う。 movapd %xmm14, %xmm13 mulsd %xmm14, %xmm13 mulsd
トップページ | Programming Place Plus アルゴリズムとデータ構造編
トップページ ここは、Programming Place Plus の、アルゴリズムとデータ構造編のトップページです。 各種アルゴリズムとデータ構造に関して、詳細な解説や、Ｃ言語を使った具体的な実装例があります（Ｃ言語についての情報は、Ｃ言語編を参照してください）。 データ構造 整列アルゴリズム 探索アルゴリズム その他のアルゴリズム APPENDIX リンク集 参考書籍
軽量ハッシュアルゴリズム - Qiita
今回はハッシュアルゴリズムについて少し触れてみたいと思います。 既存のハッシュアルゴリズムはどういうものがあるでしょうか？ SHA-1, MD5等が浮かんだ方も多いと思います。 「じゃあそれでいいじゃん」 ・・・ちょっと待ってください。 SHA-1, MD5というものは、暗号化のためのハッシュアルゴリズムです。 もし用途が単純なファイル比較等であれば、ここまで大げさなハッシュは冗長で高負荷低速であると言えます。 適切なアルゴリズムは状況によって適切に選びたいところです。 そこで今回は単純なファイル比較等に使用できる、簡単＆軽量なハッシュアルゴリズムの FNV-1 というアルゴリズムを紹介します。 詳細はこちらへどうぞ http://wowdev.jp/?p=873 ソースはこちらです。 # include <stdio.h> # include <stdint.h> /** * FNV C
転置インデックスの圧縮 - tsubosakaの日記
Managing Gigabytes勉強会で転置インデックスの圧縮の話が出たので実際に圧縮を行った場合にどれくらいのサイズになるかを計測してみた。 利用したデータは英語版Wikidiaの全記事で 文書数 2,872,589 単語数 2,735,620 転置インデックスのポインタの数 397,603,176 ぐらいのサイズのデータです。 無圧縮の転置インデックスのフォーマットは 単語ID,文書数,文書1,....文書N, 単語ID,...で各項目4byteとなっており、1.5Gぐらいのサイズになっています。 これに対して各圧縮アルゴリズムを適用した結果は アルゴリズム 無圧縮 Variable Byte Code unary符号 γ符号 δ符号 Rice Coding pforDelta(仮) サイズ 1537MB 497MB 239475MB 474MB 407MB 367MB 455MB
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
はてなブログ | 無料ブログを作成しよう
