ビットマップ(ラスタとも呼ばれる)で描かれた図形を長方形の領域に隙間なく詰込む最適化問題に対して効率的なアルゴリズムの提案する.Read less
![ラスタ図形詰込み問題に対する局所探索法の特徴点抽出を用いた効率化](https://cdn-ak-scissors.b.st-hatena.com/image/square/8d54b9629320e53ac5c43534124770f3f89045db/height=288;version=1;width=512/https%3A%2F%2Fcdn.slidesharecdn.com%2Fss_thumbnails%2Fslide20160916-160908060559-thumbnail.jpg%3Fwidth%3D640%26height%3D640%26fit%3Dbounds)
プロダクションEXPO2015でRapidCopyの展示員をしているのですが、当然暇なので xxHashの紹介をしたいと思います。 xxhashってなに? xxhashはyann Collet氏が開発したファイルチェックサム専用の軽量ハッシュライブラリ(正確に言うとアルゴリズム)です。 実装はc++用が作者自身によって公開されていて、BSDライセンスなおかげもあって様々な言語で実装されてます。 github.com 今どきの主要言語はほぼ全てサポートされているので、是非コピペ実装してみてください。 で、このxxhash何が優れているか?って話になるのですが。まとめると以下のようになります。 低いCPU使用率 優れたハッシュ衝突率耐性 例えばみなさんおなじみのMD5なんかと比べると、ハッシュ生成速度はおよそ15倍。 CPU使用率は僕の開発マシンのSandyBridgeベースのCore i7
マラソンマッチって? 競技プログラミングのうち、「より良い解を求める」ことを競うコンテストをマラソン形式と呼びます。 例えば厳密解を求めることができない問題について、近似解のスコアを競ったりします。 マラソンでよく使われるアルゴリズム マラソンで頻出なのは「ビームサーチ」と「焼きなまし法」です。 この記事ではナップサック問題を例にしてこの2つのアルゴリズムを解説します。 もちろん、この2つのアルゴリズムはどちらも近似アルゴリズムなので最適解は求められません。 ビームサーチ まずは順番にナップサックに入るだけ入れるコードを書いてみます。 #include <iostream> using namespace std; int main() { // 個数 const int N = 100000; // ナップサックの大きさ const int W = 100000; // 重さ・価値 in
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く