2で割ることと3で割ること - Qiita
この記事でお題にするのはCPUレジスタ上の整数除算です。以下、単に除算とも書きます。 除算は非常に高コストな演算なため、コンパイラは最適化によって、できるだけ整数除算を別の計算に置き換えようとします。 最適化ができる場合の一つとして、割る数が定数である場合があります。頭のいいコンパイラは、除算を乗算とビットシフト等を駆使した演算に置き換えます。この記事では、そういった最適化の背景にある理屈を部分的に解説します。 計算機環境としてはモダンなx86 CPUを仮定します。したがってレジスタは32/64ビットであり、負数は2の補数表現になっています。ある程度は他の命令セットでも通用する話になっているかもしれません。 そもそも整数の除算とは プログラミングにおける整数の除算の定義について確認します。整数$n$を整数$d$で割るとき $$ n = q \times d + r $$ が成り立つように除
Open-sourcing F14 for faster, more memory-efficient hash tables
Open-sourcing F14 for faster, more memory-efficient hash tables Hash tables provide a fast way to maintain a set of keys or map keys to values, even if the keys are objects, like strings. They are such a ubiquitous tool in computer science that even incremental improvements can have a large impact. The potential for optimization led to a proliferation of hash table implementations inside Facebook,
［改訂新版］C言語による標準アルゴリズム事典
この本の概要 コンピュータの算法に関わるアルゴリズムの定石，レトリックを可能な限り収録した定番の書。手元に置いておきたい実用的な本が30年弱の時を経て新装改訂版として登場です。 定評をいただいている基本的な内容はそのままに，時代にそぐわなくなっていた部分のみ改訂。これからも末長くご愛顧いただけるようにまとめ直しました。 ※本書は『C言語による最新アルゴリズム事典』の改訂版です。 こんな方におすすめ 仕事でC言語を使う方 知りたいアルゴリズムをさっと引きたい方 本書のサンプル 本書の一部ページを，PDFで確認することができます。 サンプルPDFファイル（739KB） 本書の紙面イメージは次のとおりです。画像をクリックすることで拡大して確認することができます。 値の交換 / 誤り検出符号 / アルゴリズム / 暗号 / 安定な結婚 / 石取りゲーム1 / 石取りゲーム2 / 異性体の問題 /
大量のテキストからランダムに少数の行を抽出したい - Reservoir Sampling - 唯物是真 @Scaled_Wurm
前に以下のような記事を書きましたが、大量のテキストではうまくいかなかったので新たに書きました ファイルからランダムにN行取り出す(shufコマンド) - 唯物是真 @Scaled_Wurm 上の記事ではテキストをランダムに\(k\)行取り出したい時"shuf -n k"コマンドでランダムにシャッフルした\(k\)行を取り出していました ところが非常に大きなテキストファイルに対して上のコマンドを実行すると、一度にデータを全部メモリに読み込み始めているのか、すごい勢いでメモリを消費していきました(sort -Rでも) そこでメモリをあまり使わずにランダムに\(k\)行取り出す方法について調べました まず基本的な非復元抽出のアルゴリズムは以下の記事の発展手法とか追記のあたりの話がわかりやすいと思います 非復元抽出の高速かつ実装が簡単な方法を考える - 睡眠不足？！ この記事の話も一度全部の要素を
観察日記 2018-02-14 - なるせにっき
配列の全ての要素が等しいか否か mrkn 配列の全ての要素が等しいことはどう確認したら良いんだろう。 `ary.all? {|e| e == ary[0] }` これかな usa ary.uniq.size == 1 mrkn なるほど > uniq usa all?でブロック引数より速そうな予感 いやでもaryがでかくてかつ全然要素が等しくなかったらそうでもないか。 mrkn `ary.all? {|e| e.foo == ary[0].foo }` の場合はどうでしょう。map.uniq.size がいいかな usa all?は全て等しい時に遅いが、序盤で違うとわかったら速い mrkn 確かに > 序盤で違うとわかったら速い usa この辺は予想される集合の傾向で判断するしかないですかねえ。 map.uniq.sizeはmapの結果としての一時配列を作らないようにするには、えーと En
計算機アーキテクチャを考慮した高能率画像処理プログラミング
3. ムーアの法則に従って集積回路のトランジス タ数は年々倍増 背景（1/4） 3 40th Anniversary of the Microprocessor https://newsroom.intel.com/press-kits/40th-anniversary-of-the-microprocessor/ 2011年：Core i7 3960X vs Intel 4004 35万倍 1971年：Intel 4004 トランジスタ2300個 5. 現在のコンシューマ向け最上位 Intel Core i9 7980XEは2.6 GHz，18コア，512ビットベ クトル演算器，FMAユニット２つ搭載 –単純：2.6 GFLOPS –理想：3.0 TFLOPS （倍精度：1.5TFLOPS） • 2.6*18*16*2*2 • ターボブーストや増加したL2キャッシュ，SMTを活 用す
HashDoS脆弱性との戦い！ Rubyコミッター・卜部昌平が明かすプログラム堅牢化のノウハウ - エンジニアHub｜若手Webエンジニアのキャリアを考える！
HashDoS脆弱性との戦い！ Rubyコミッター・卜部昌平が明かすプログラム堅牢化のノウハウ 過去、HashDosの影響を受けたRuby。言語開発者はいかにしてこうした問題に対応してきたのでしょうか。コミッターである卜部氏の貴重な記録を公開します。 2011年の末頃、HashDoSという脆弱性が公表され、Rubyもこの影響を受けた。本稿の筆者である卜部昌平（うらべ・しょうへい／@shyouhei／以下、卜部）は、報告当初からRuby側のチームメンバーとしてプログラム本体の修正を担当した。以下はその記録である。言語開発者たちが普段どのようなことを考え、どういった技術を用いて開発やバグフィックスを行っているのか。その概要を知ってもらえれば幸いだ。 オブジェクト指向スクリプト言語 Ruby HashDoSの概要 なぜ約6年後の今、修正内容を公開するに至ったか？ 前史：すでに内包されていたリスク
第一級ラベルを持たない言語におけるDirect Threaded VMの実装 | κeenのHappy Hacκing Blog
こんにちは。κeenです。このブログでちょくちょく出てくるDirect Threaded VMについて。 SMLのようにgotoがない言語だとDT VMの実装出来ないよなー、と思ってた所、ふとアイディアが浮かんだのでそれについて。 序論 DSL、例えば正規表現などの処理系を実装することを考えてみて下さい。 言語処理系において最も素朴な実装はインタプリタですが、速度面で不利なので一旦仮想命令にコンパイルして仮想命令実行器(VM)で実行することが一般的です。 コンパイラのように複雑な記号処理をするプログラムはCommon LispやMLのような記号処理に強い高級言語が得意とする分野です。 一方、ランタイムには低レベルなことが出来て処理速度の速いCommon LispやCを使いたくなるでしょう。 Common Lisp以外の言語ではコンパイラとランタイムを分離するのが妥当な選択肢のようですが、高
高速な復元抽出の直感的な説明
先日@niamさんと@tsubosakaさんのつぶやきを見てて，確率{pi}で復元抽出するWalker's alias methodというものを知りました．たまたま，今日，復元抽出する用事があったので，思い出して調べた次第．私も昔同じことをやろうとして，O(log n)でいけるからまぁいいやと思っていたのですが，このアルゴリズムだとO(1)でいけます． 解説はこのあたりのブログを参照． 比較的高速な復元抽出アルゴリズム高速に非復元抽出をするアルゴリズムはないだろうか？(2)さて，私は理解力が足りなくてこのあたりの説明を読んでもなんでこれでいいのかさっぱりわからなかったので，絵に描いて理解しました．確率{pi}で復元抽出するためには，piに比例した面積の図形を壁に貼ってダーツをすればいいのです．{0.1, 0.05, 0.3, 0.1, 0.45}だったとします．するとこんなの． まさか毎回
Word2Vec のニューラルネットワーク学習過程を理解する · けんごのお屋敷
Word2Vec というと、文字通り単語をベクトルとして表現することで単語の意味をとらえることができる手法として有名なものですが、最近だと Word2Vec を協調フィルタリングに応用する研究 (Item2Vec と呼ばれる) などもあるようで、この Word2Vec というツールは自然言語処理の分野の壁を超えて活躍しています。 実は Item2Vec を実装してみたくて Word2Vec の仕組みを理解しようとしていたのですが、Word2Vec の内部の詳細に踏み込んで解説した日本語記事を見かけることがなかったので、今更感はありますが自分の知識の整理のためにもブログに残しておきます。なお、この記事は Word2Vec のソースコードといくつかのペーパーを読んで自力で理解した内容になります。間違いが含まれている可能性もありますのでご了承ください。もし間違いを見つけた場合は指摘してもらえると
C++/Rubyで基数木をつかって高速なHTTPルーティングを実現する - Qiita
はじめに 数年にわたり、PadrinoやGrapeといったWebアプリケーションフレームワークのルーティングを改善してきた自分が、今年の11月頃から、従来とは異なるアプローチでHTTPルーティングの高速化について検証したので、その結果について解説する。 なおこの記事では、その過程でC++で基数木を実装し、それを用いることにより、Rubyで高速なHTTPルーティングを実現した事例について、順を追って解説する。 tl;dr C++で基数木(Radix Tree)を表現するr2reeというライブラリを書いた。 r2reeのRuby向けバインディングであるr2ree-rubyを書いた。 r2ree-rubyを用いてRuby上でHTTPルーティングを行う pendragon-radixを書いた。 多分、Rack準拠のルーティングライブラリでは最速。 結果、Sinatraなどで用いられる正規表現+線形
RubyからGoの関数をつかわなくても再帰をやめなくてもアルゴリズムを改善する→はやい - prime's diary
qiita.com mattn.kaoriya.net という記事を読んだのでアルゴリズムを改善して速くしました。 いわゆる行列累乗のテクニックを使うと（乗算部分を除けば）N番目のフィボナッチ数はで求まります。 実際にはフィボナッチ数は指数的に増大するので乗算にかかる時間が支配的になるのでもっと遅くなります(Karatsuba法なら、高速フーリエ変換を使えば)。 単純な足し算のループでは足し算の桁数を考えると なのでそれよりは随分と速くなります。 40番目ぐらいでは実行時間はほとんど0なので100万番目のフィボナッチ数を求めてみます。 こちらが元のソースコード def fib(n) f0, f1, v = 0, 1, 0 n.times do |x| if x <= 1 v = x else v = f0 + f1 f0, f1 = f1, v end end return f0 + f1
本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG
コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソート シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート 安定感のある隠れた実
How does Shazam work | Coding Geek
Have you ever wondered how Shazam works? I asked myself this question a few years ago and I read a research article written by Avery Li-Chun Wang, the confounder of Shazam, to understand the magic behind Shazam. The quick answer is audio fingerprinting, which leads to another question: what is audio fingerprinting? When I was student, I never took a course in signal processing. To really understan
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
かけ算の話 - ブログ | S2ファクトリー株式会社
ARROW-3404: [C++] Make CSV chunker faster by pitrou · Pull Request #2684 · apache/arrow![ARROW-3404: [C++] Make CSV chunker faster by pitrou · Pull Request #2684 · apache/arrow](https://cdn-ak-scissors.b.st-hatena.com/image/square/836f25008eac0b0809856b1cbf823667f2ec6fd3/height=288;version=1;width=512/https%3A%2F%2Fopengraph.githubassets.com%2Ff11ed910d7971c87cede950d7eaecd6a755320aa68260e784ef7699b2bf5c618%2Fapache%2Farrow%2Fpull%2F2684)
Arnoldi iteration - Wikipedia
Piece Chains | Catch22
(PDF) Fast high precision summation
Quanta Magazine