作者ホームページサービス（hp.vector）は終了いたしました。 長らくのご利用、ありがとうございます。 ご不明な点があれば、お問い合わせページをご覧の上、お問い合わせください。 ※15秒後にトップページに戻ります。 (c) Vector HOLDINGS Inc.All Rights Reserved.
終了いたしました。
作者ホームページサービス（hp.vector）は終了いたしました。 長らくのご利用、ありがとうございます。 ご不明な点があれば、お問い合わせページをご覧の上、お問い合わせください。 ※15秒後にトップページに戻ります。 (c) Vector HOLDINGS Inc.All Rights Reserved.
C++でニュートン法を美しく書く その２（再帰処理で書く） - Qiita
# include <iostream> auto solve_by_newton_method = []( auto func , double x ,double error , double delta ) { double x1 = x; double x2 = x1 + delta; double y1 = func(x1); double y2 = func(x2); double diff_x = (y2 - y1) / (x2 - x1); double next_x = x1 - y1 / diff_x; if (fabs(y1 - 0) < error) { return x1; } double answer = solve_by_newton_method(func, next_x, error , delta); return answer; }; int mai
ページランクのアルゴリズムをC++で試してみる
前回Google Mockを紹介したこともあって、Googleがらみのトピックを探していたところ、"How Google Finds Your Needle in the Web's Haystack：GoogleはどうやってWebの干草の山から針を見つけ出すのか"というタイトルの解説記事に辿り着きました。Googleでの検索結果は有用な（あるいは人気のある）ページが検索リストの上位に並びます（広告云々は別として）。各ページの有用さの度合いを計算し、それをキーに並び替えを行っているのでしょう。この記事では"有用さの度合い"をどうやって算出しているのかを解説していました。今回はこの記事をさらに噛み砕き、C++コードで実際に算出しながらの解説を試みます。 前回の記事『Google Mock：はじめの一歩』 『How Google Finds Your Needle in the Web's H
C++/Rubyで基数木をつかって高速なHTTPルーティングを実現する - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに 数年にわたり、PadrinoやGrapeといったWebアプリケーションフレームワークのルーティングを改善してきた自分が、今年の11月頃から、従来とは異なるアプローチでHTTPルーティングの高速化について検証したので、その結果について解説する。 なおこの記事では、その過程でC++で基数木を実装し、それを用いることにより、Rubyで高速なHTTPルーティングを実現した事例について、順を追って解説する。 tl;dr C++で基数木(Radix Tree)を表現するr2reeというライブラリを書いた。 r2reeのRuby向けバインデ
３次スプライン補間の概要とC++, Pythonサンプルコード - MyEnigma
3Dグラフィックスのための数学入門 クォータニオン・スプライン曲線の基礎posted with カエレバ郡山 彬,峯崎 俊哉,原 正雄 森北出版 2015-10-27 Amazonで探す楽天市場で探すYahooショッピングで探す 目次 目次 はじめに 各種スプラインにおける連続性 ３次スプライン補間とは？ 条件1 条件2 条件3 条件4 条件5 3次スプライン補間を手計算+pythonで解く 入力データ数が不定な場合の3次Spline補間 Pythonサンプルコード C++サンプルコード 3次スプラインにおける曲率の計算方法 x-y座標系における点群のスプライン補間 方位の計算方法 曲率の計算方法 参考資料 MyEnigma Supporters はじめに 3次スプライン補間は、 計算がそこまで複雑ではなく、 また二次微分までの連続性が担保されているため、 様々な用途に利用されています。
c > Damerau–Levenshtein distance 実装 > 特定の文字列に対するコストに緩急つける > v0.2 - Qiita
c > Damerau–Levenshtein distance 実装 > 特定の文字列に対するコストに緩急つける > v0.2algorithmLevenshtein#migrated /* v0.2 2016 Oct. 21 - use cost from functions given below - add calc_cost_transposition() - add calc_cost_substitution() - add calc_cost_deletion() - add calc_cost_insertion() - increase size of DA[] for 128x128 v0.1 2016 Oct. 19 - branched from stackoverflow post(*1) [*1] http://stackoverflow.com/questi
高速な文字列検索 Crit-Bit Tree コンテナ（C++） - Qiita
Crit-Bit Tree をご存知でしょうか。 基数木 (Radix tree) は知っている人が多いかもしれません。 Crit-Bit Tree は基数木をさらに発展させたもので、 基数木同様、高速な検索が可能な木構造です。 基数木はハッシュマップのようなハッシュ値の衝突が発生しないため hashdos1 対策として有効な手段ですが、メモリ消費量が大きい問題がありました。 Crit-Bit Tree ではハッシュ値の衝突は発生しない上に、 基数木に比べてメモリ消費量を抑えることができます。 アルゴリズム 基数木では、文字列を文字ごとに扱っていました。 例えば "AAA" "AAB" "ABC" というキー値があるとき、 以下のようなツリーが構築されます。 基数木のメモリ消費量が大きい問題は、この黒丸の部分、分岐にあります。 各分岐点では、複数の子ノードを保持する必要がありますが、 1バ
C++: マルチコアCPUを利用した並列化による高速な階層的クラスタリング
比較的データ数の多い階層的クラスタリングを行う必要があり、手元にあるRで処理を始めたのだが思ったよりも遅かった。そこで、マルチコアCPUを利用した並列化で高速化することにした。RでもGPGPUを使って高速化したプログラムがあるようなのだが、すぐに使える高性能GPUを用意できなかったし、それに、TBBライブラリを使った並列化は手間も時間も掛からないので作ってしまった方が良いと判断した。 尚、このプログラムで作成したクラスタデータのデンドログラム描画や閾値による区分けについては一つの記事で書くには大きすぎるので、記事を分けて、「Python: 階層的クラスタリングのデンドログラム描画と閾値による区分け」に回すことにする。 まずは、「集合知プログラミング」にPythonによる階層的クラスタリングのソースコードが載っていたのでそれをC++で書き直した。アルゴリズム自体はそれほど複雑なものではないの
MiniSAT を mac で動かしたメモ - Qiita
はじめに こんにちわ、ユニバの MJ です。 普段はフロントエンドをしているんですが、社内の動きもありそろそろ C++ に手を出したいと思っていた時の話です。 SAT と SAT solver この話はカナーーーーリ長くなるので割愛。でもここら辺を読んでくれれば嬉しい。 充足可能性問題 高速SATソルバーの原理 MiniSAT コンペティション かくいう私も山がいっぱいある中の大学でSATを学んでいた一人です。 SAT というのは充足可能性問題のことで、それを解くのが SAT Solver です。 SAT は NP完全な問題として知られています。つまり数ある NP な問題でもっとも難しく解き方によっては指数的に時間がかかってしまう問題(こんな言い方であっているのかとても不安！) ともあれ、Solver は この問題を効率良く解くための施策がいくつもされていて、それがとっても C++ の勉強
オフラインリアルタイムどう書くE04 をビット演算で解いた・その２ - Qiita
#include <iostream> #include <string> #include <numeric> struct Roll { unsigned int rock; Roll(unsigned int rock) : rock(rock) {} unsigned int operator () (unsigned int death_route, char b) { const unsigned int branch = (0x181u >> (8 - (b - '0'))) & 0xff; if(rock & branch) { rock ^= branch; return death_route | branch; } if(((death_route ^ branch) & branch) * (death_route & branch)) { return death
明日使えないすごいビット演算
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https
AtCoder Beginner Contest 037に挑戦した話 - Qiita
きっかけ 就職して、スキルアップのためにと思いプログラミングコンテストに参加しています。今回はその１つである「AtCoder Beginner Contest (ABC) 037」に参加してみました。 自分の肌で感じた難易度としては |問題|難易度| |:--:|:--:|:--:| |A|易| |B|やや易| |C|やや難| |D|難| という感じでした。Dは時間内に終えることができませんでした。。。しかしなんとか終了後１時間ほどで正解できました。ちかれた。。。。 一応手元の環境で動くものができても、TLE(実行時間制限超過)などへの対処を考えるのが難しかったです。 なお、使用言語はC++です。 # 自分の解法 [ABC#037 コンテストページ]http://abc037.contest.atcoder.jp/ 問題はこちら。問題概要はこのページの問題の要約です。 A問題 問題概要 １
Sublime Textの「あいまい一致」をリバースエンジニアリング | POSTD
Sublime Text は、私のお気に入りのプログラミング用テキストエディタです。 Sublime Textで気に入っている特徴の1つは、あいまい検索アルゴリズムです。ファイルや関数の検索が超高速なのです。これまで多くの人が、インターネット上で、この仕組みについて質問していましたが、満足の行く回答はありませんでした。そこで、私が自らこれを解明することにしました。 全部読むのが面倒な方へ 本文を読まずに最終結果だけ知りたいですか？ 了解！ 私は、あなたを責めたりしませんよ。 インタラクティブなデモ： こちらをクリック ソースコード： C++ 、 JavaScript Sublime Textの仕組み Sublime Textのあいまい一致とは何でしょうか。そして、なぜそれはそんなに賢いのでしょうか。聞いてくれてうれしいです。 Sublime Textには、2つの非常に便利なナビゲーション関
コンピュータサイエンティストはソートアルゴリズムの中身を知るべきか
講義でソートアルゴリズムを教えることになったので，改めてソートアルゴリズムの勉強をしなおした．僕がソートアルゴリズムをちゃんと勉強したのは1990年代前半で，教科書はニクラウス・ヴィルト「アルゴリズムとデータ構造」（第2版）だった．サンプルコードがModula-2で書かれているアレだ． N. ヴィルト「アルゴリズムとデータ構造」C++ STL の解説を読むなどしてソートアルゴリズムの改良が進んでいるのは知っていたが，再勉強してはじめて，未だに新発明があることを知った．例えば図書館ソートなど，恥ずかしながら名前さえ知らなかった．勉強は大事だ． とは言え，そもそもソートアルゴリズムの中身をどのぐらいまで知っておけば，コンピュータサイエンティストとして十分なのだろう，あるいはエンジニアとして十分なのだろうという疑問は残る． 例えば，超優秀なC++プログラマでもGNUの std::sort の中身
popcount
ちょっとわけあってpopcountを調べてた。 以前から、ビットを数える・探すアルゴリズムを参考に int numofbits5(long bits) { bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333); bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f); bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff); return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff); } とかやってたわけです。この計算の意味は、 1行目で、2ビットずつを足しこみ2ビット単位で1
Binary Hacks と 64bit popCount 問題 | TAKESAKO @ Yet another Cybozu Labs
高林さん、オライリーさん、ありがとうございます。 ちなみにetoさん情報によると、明日11/10は「いいバイナリの日」らしいです。 11 → いい 10 → バイナリ Binary Hacks の発売日は 11/11 で、ビットが全部立っている非常に縁起の良い日です。 縁起を担ぐためにも、いいバイナリの日に Binary Hacks を注文して、発売日に書店に行って本を見かけたら 11 冊買いましょう。 x86 パフォーマンスチューニング さて、最後の HACK #100「文献案内」でマイクロプロセッサアーキテクチャマニュアルが紹介されていましたが、 x86のパフォーマンスチューニングつながりということで、 ちょうど今日ラボの社内掲示板で盛り上がった話題をこちらでも共有したいと思います。 * popCount 問題 64bitの数値の中で1になっているビット数を数える popCount64
C#はunsafeの方が速いという幻想 - aokomoriuta's blog
数日前に話題になったこの辺の話。 espresso3389.hatenablog.com qiita.com C++よりC#が速いかどうかというのはとりあえず置いておきましょう。 しかし、大元ネタが「unsafe使うと1.2倍速くなります！」と言ってますね。 よく聞きますよ、「C#で速度出したかったらunsafeにしなさい」って。 しかし本当にそうなのでしょうか？その謎を解明するため、我々探検隊はジャングルの奥地へ（ｒｙ なおこの記事のタイトルは以前の『OpenCLやる前にSIMD使い切れっていう幻想』と合わせています。興味がある方はそちらもどうぞ。 結論 unsafeにしなくても速くできる！！ コードと環境は以下の通り。 コード testManagedBitmap testManagedOpt test1 test2 環境 (Surface Pro 3 Windows10 Pro 64b
C++でブルームフィルタを実装する方法 | POSTD
ブルームフィルタとは、「ある要素が集合のメンバである可能性があるか、それとも確実に集合のメンバではないか」を効果的に確認することのできるデータ構造です。この記事では、C++でブルームフィルタを実装する簡単な方法をご紹介します。 ブルームフィルタとは何なのか 、また、 その背後にある多くの数学的要素 については紹介していませんので、ご了承ください。これらのトピックに関しては、素晴らしいリソースがあるので、そちらを参考にしてください。 インターフェイス まずは、ブルームフィルタを定義していきましょう。ここでは、3つのパブリック関数を定義していきます。 コンストラクタ ブルームフィルタにアイテムを追加する関数 アイテムがブルームフィルタにある可能性を確認するためのクエリを行う関数 また、フィルタの状態を保持するビットの配列を含んだ、メンバ変数についても定義します。 #include <vecto
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ページランクのアルゴリズムをC++で試してみる
x86x64 SSE4.2 POPCNT
