キャッシュアルゴリズムの比較 - falsandtruのメモ帳
アプリケーションなどOSより上に作られる高水準のプログラムではハードウェアの速度と容量を考慮しない数学的キャッシュアルゴリズムが使われ主にこれを本稿の対象とする。キー探索用マップと明示的キャッシュサイズ(対となる値が保持されているキーのサイズ)は計算量に含まれない。 LRU 最も単純かつ高性能な基礎的キャッシュアルゴリズム。そのため性能比較のベースラインとして常に使用される。逆に言えば実用最低水準の性能である。スキャン耐性皆無でスキャン一発でキャッシュとヒット率がリセットされゼロからやり直しになるため非常に脆く不確実な性能となりベンチマークにおける性能が表面上さほど悪くなく見えても実際の性能はこのような外乱により大きく低下しやすい。このためLRUより高度な主要アルゴリズムはすべて大なり小なりスキャン耐性を備えている。ちなみにプログラミング言語最大のパッケージマネージャであるJavaScri
RSAに対するフェルマー攻撃 - Qiita
はじめに（Introduction） RSAの鍵ペアの生成方法にミスがあり脆弱性となってしまった実装例があったようです。 元の文献を機械翻訳（ちょっと修正）してみます。 原文のデモをやってみたところ、案外動いたので先にデモを記します。 デモ（Demo） まずは、素数$p$と$q$を生成して$N$を求めるところです。 ※：鍵長が2048bitなので多少時間がかかります。 問題となったライブラリがこのようなロジックであったかは不明ですが、翻訳した資料を参考に作成しています。 import random as rnd import sympy key_length = 2048 distance = 10000 p = 0 q = 0 # 乱数Xを生成する。 X = rnd.randrange(2, pow(2, key_length)) for i in range(distance): #
高速逆平方根(fast inverse square root)のアルゴリズム解説 - 滴了庵日録
高速逆平方根とは？ C言語のコード 検証 アルゴリズムの要点 [1] 逆平方根の計算を対数・指数の計算に置き換える [2] 浮動小数点型の内部表現を利用した対数・指数の近似計算 [2.1] 対数の近似 [2.2] σの最適値 [2.3] 整数型での解釈 [2.4] 逆平方根の計算とマジックナンバー0x5F3759DF [3] ニュートン法による収束で精度アップ 感想 高速逆平方根とは？ 高速逆平方根(fast inverse square root)とは、平方根の逆数 を高速に計算するアルゴリズムです。平方根の逆数は逆平方根とも呼ばれます。逆平方根はベクトルの正規化などに用いられるので、これを高速に計算できるアルゴリズムには大きなご利益があります。 参照： Fast inverse square root - Wikipedia C言語のコード 高速逆平方根の関数を示します。0x5F375
様々なrate limitアルゴリズム - Carpe Diem
概要 インターネットに晒されているWebサービスでは TV等で紹介されたことによる大量流入 悪意ある人物からの攻撃 クライアントのバグに依る大量リクエスト など、本来想定していた以上のトラフィックが来ることはよくあります。 単純にシステムを構築すると大規模トラフィックに対応できずシステムがスローダウンしてしまうため、何かしらrate limitをかけておいた方が良いです。 ただしrate limitと一口に入っても色々あるため、今回は主なrate limitアルゴリズムを紹介します。 Leaky bucket Leaky bucketはデータ転送レートを一定にする（＝上限を設定する）アルゴリズムです。 下の図のように、様々な流量の水流がそのバケツに流れ込んでも小さな穴からは一定の水流が流れ出す仕組みです。 ref: What is the difference between token
計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。 0. はじめに 世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います: アルゴリズムとは何か ～ 文系理系問わず楽しめる精選 6 問 ～ アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると
ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜 - Qiita
はじめに はじめまして。 NTTデータ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 C や C++ を使用しているとしばしばビット演算を行う場面が出て来ます。 計算機リソースが限られている状況では、ビットを用いることでデータ量を少なく済ませたり、計算コストを小さく抑えたりすることができるメリットがあります。 本記事では、ビット演算を用いて実現できる処理について、簡単なものから高度なものまで集大成します。極力わかりやすく頑張って執筆しました。特に前半 4 つはビットの説明の中でもかなりわかりやすい方だと思います。後半の 7 つのテーマは比較的高度なアルゴリズムの話題ですので、フラグ管理やマスクビットについて詳しく学びたい方は前半 4 つを中心に読んでいただいて、後半 6 つは必要に応じて読んでいただければと思います。反対にビットの知識はあってビットを用いたアルゴリズ
Amazonの推薦システムの20年
IEEE Internet Computingの2017年5・6月号に "Two Decades of Recommender Systems at Amazon.com" という記事が掲載された。 2003年に同誌に掲載されたレポート "Amazon.com Recommendations: Item-to-Item Collaborative Filtering" が Test of Time、つまり『時代が証明したで賞』を受賞したことをうけての特別記事らしい 1。 「この商品を買った人はこんな商品も買っています」という推薦で有名なAmazonが1998年にその土台となるアルゴリズムの特許を出願してから20年、彼らが 推薦アルゴリズムをどのような視点で改良してきたのか 今、どのような未来を想像するのか その一端を知ることができる記事だった。 アイテムベース協調フィルタリング 20年前も
Scalable Bloom Filtersとは一体....？ - Qiita
Wikipediaを漁っていたところScalable Bloom Filters(SBF)というデータ構造を発見してしまったので紹介します1。 参照した論文 http://haslab.uminho.pt/cbm/publications/scalable-bloom-filters Bloom Filter SBFの説明に入る前に、Bloom Filterについて簡単に紹介します。もっとも、日本語のWikipediaでも十分詳しい説明が載っていたりするのですが……。 ささっと説明 Bloom Filterはちょっと不思議な性質を持つデータ構造の一種です2。 いわゆるSetと同じ操作を提供する 要素を入れる操作と、ある要素が入っているかを調べる操作 どちらも時間計算量O(1)で実現できる ハッシュテーブルなどを用いて実装される同種のデータ型と比して、とても空間効率が良い その代わりに、ある
PrestoとHyperLogLogで、大量ログからユニークユーザー数を高速に推定する（理論編） - Platinum Data Blog by BrainPad
本記事は、当社オウンドメディア「Doors」に移転しました。 約5秒後に自動的にリダイレクトします。 皆さん、こんにちは。マーケティングプラットフォーム本部で広告系製品の開発を担当している田頭です。 現在、ブレインパッドでは、DMP（※1）に蓄積されたさまざまなデータをもとに、ユーザー数を確認しながら直感的にセグメントを作成できる「DeltaCube（デルタキューブ）」という製品を提供しています。 ユーザーのセグメントを作成する際、担当者がストレスなくインタラクティブにセグメントの条件を設定しユーザー数を確認するためには、蓄積された大規模なデータの中から「高速に」ユニークユーザーの数を数えなければなりません。 このため、DeltaCubeでは、集計処理にPrestoと呼ばれる分散処理ミドルウェアを利用しています。 今回、このPrestoを利用したユニークユーザー集計の更なる高速化について検
2016年のOSS圧縮ツール選択カタログ - Qiita
まだgzipで消耗し（略） 2016年、人類が待ち望んでいた、gzipを圧倒するOSS圧縮ツールzstd(Zstandard)がリリースされたにも関わらず、なんかあんまり話題になっていなくて寂しいので、ちょろいかんじの賑やかし比較記事を書きました。圧縮ツールのカタログ的に眺めていただけるかと思います。 はじめに （この記事で言う）圧縮ツールとは何か 圧縮ツールという呼び名は正確ではない（はず）です。平たく言えば、gzipやbzip2、xz、lz4などですが、人によっては、tarの裏側としてしか使ってなくて、聞いたこともないかもしれませんね。そういうときはまずgzipのmanpageとか読んでください。 しかし、そういうツールを何と呼べばいいのかわからないので、ここでは圧縮ツールと呼んでいます。 ややこしいですが、アーカイバではありません。アーカイブとは実態が一つのファイルになっているフォル
Linuxカーネルのコードを読んで勉強になったこと - φ(・・*)ゞ ｳｰﾝ カーネルとか弄ったりのメモ
Linuxカーネルのコードを読んでて、なるほど〜と思うことはよくあるけど、その中でも特に今までの考え方をぶち壊してくれたのはなんだっけと思ったところ、やっぱりリスト構造かなと言うところ。 c言語でリスト構造を作る場合、一般的な教科書方式だと↓のようにデータとnextポインタは密結合になってると思います。これの場合、struct foobarのポインタをnext要素に使っているので、他の構造体（例えば、struct hogehoge）で同じことをしようとすると、その構造体ではstruct hogehoge *nextというメンバ変数を持つ必要があります。 ヘッド要素はstruct foobarです。 struct foobar { int n; char s[64]; struct foobar *next; }; struct foobar head; Linuxカーネルの場合、データとリ
ITエンジニアなら知っておきたい、今更聞けないアルゴリズムの種類一覧 - paiza times
Photo by Oferico 皆さんはアルゴリズムやデータ構造について勉強したことはありますか？そして、基本的なアルゴリズムについて、どのようなものがあって、どのようなときに使うとよいかといったことを説明することができますか？ 仕事をしていると、プログラミング言語等の勉強や業務に忙しくて、正直アルゴリズムどころではないという場合がほとんどでしょう。しかし、いつか勉強しようと思っていたけど、基本的なアルゴリズムにどんなものがあるのかなんて今更聞けないな……ということもあるかと思います。 今回はそんな方に向けて、基本的なアルゴリズムの一部の概要に加え、アルゴリズムの勉強に役立つサイト、書籍をご紹介したいと思います。 ■アルゴリズムを学ぶ意味 例えば、ソート等については、通常はすでにソート関数があるので、自分で作らなくても済む＝アルゴリズムも勉強しなくていいと思ってしまうかもしれません。しか
本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG
コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソート シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート 安定感のある隠れた実
GPUとセルオートマトンで経路探索問題を解いてみる | POSTD
前回は、グラフィックカード上だけで コンウェイのライフゲームを実行するアイデアを説明しました 。このアイデアは、3つ以上の状態を有するオートマトンを含め、 どのような セルオートマトンにも当てはめることができます。今回の投稿では、二次元グリッドの 最短経路問題 をGPUだけで解決するのに、このアイデアを活用してみたいと思います。CPUによる従来の検索と比べても、その速さは遜色ありません。 JavaScript側の状態は基本的に以前と同様なので（2つのテクスチャと、それらを繋いでオートマトンを次のステップに進めるフラグメントシェーダ）、ここでは説明は割愛します。変更したのは次の2点、（オートマトンの全ての状態を表現する）セルの状態のエンコーディングと（新しいルールをプログラムする）フラグメントシェーダです。 オンラインデモ （ ソース ） デバッグや実験のために使ったセルオートマトンの純粋な
ハクビシンにもわかる全文検索 - Qiita
高速な全文検索アルゴリズムであるFM-indexについて解説する。理解しがたい点や間違っている点があれば是非コメントで指摘してほしい。 概要 FM-indexはリニアな文字列に対して検索をするアルゴリズムで、主に簡潔データ構造とBWT(およびLF mapping)という二つのアイデアから成り立っている。BWTはBurrows-Wheeler変換のことで、文字列を特殊な並び順に変換するという可逆関数である。BWTされた文字列を簡潔データ構造固有の操作をすることで、クエリ文字列の長さに比例した短い時間で文字列を探し出すのがFM-indexだ。 簡潔データ構造 簡潔データ構造に関してはFM-indexで必要となる二つの関数だけ説明して、詳細は次の機会に譲るとする。さて、二つの関数はともに文字列のある位置より前の部分に含まれている文字の数を数え上げるというものでrank()とrankLessTha
機械学習アルゴリズムへの招待 | POSTD
機械学習の問題 については以前に紹介したので、次はどんなデータを収集し、どんな機械学習アルゴリズムを使うことができるのかを見ていきましょう。本投稿では、現在よく使用されている代表的なアルゴリズムを紹介します。代表的なアルゴリズムを知ることで、どんな技法が使えるかという全体的なイメージもきっとつかめてくるはずですよ。 アルゴリズムには多くの種類があります。難しいのは、技法にも分類があり拡張性があるため、規範的なアルゴリズムを構成するものが何なのか判別するのが難しいということですね。ここでは、実際の現場でも目にする機会の多いアルゴリズムを例にとって、それらを検討して分類する2つの方法をご紹介したいと思います。 まず1つ目は、学習のスタイルによってアルゴリズムを分ける方法。そして2つ目は、形態や機能の類似性によって（例えば似た動物をまとめるように）分ける方法です。どちらのアプローチも非常に実用的
ウェーブレット木を試す - Negative/Positive Thinking
はじめに 巨大な文字列でも高速にクエリ処理できる噂の木を、挙動を確認するため作ってみた。 コード アルファベット(a〜z)の文字列を扱う場合 完備辞書の操作が愚直、ビット列がvector 本を参考にしたけど、2か所間違ってる？ #include <iostream> #include <vector> #include <queue> #include <cmath> //top_kのためのタプル struct ST { int t; size_t st, en; ST(int t, size_t st, size_t en):t(t),st(st),en(en){} }; bool operator<(const ST& a, const ST& b){ return (a.en-a.st) < (b.en-b.st); } //アルファベット([a-z]+)用のウェーブレット木 cla
おねえさんを組み合わせ爆発から救う：完結編おねえさんは星になった - きしだのHatena
おねえさんを組み合わせ爆発から救うために、経路をZDDとして表したら、すっきりと経路情報が扱えました。 http://d.hatena.ne.jp/nowokay/20121018#1350528607 あとは、このZDDを効率よく構築できれば、おねえさんを救えそうです。このZDDの構築には、クヌース先生の開発したSimpathアルゴリズムを使うと非常に効率よく構築できます。 前回生成したZDDを見ると、同じノードにまとまっているものがいくつかあることがわかります。特に後半になるとどんどん同じパターンになるものがまとめられていきます。 つまり、この経路問題のZDDを構築するときには、いかに同じパターンになるものをまとめるかが鍵になるということです。 Simpathでは、辺の端だけに注目して、同じパターンになっていればそれ以降のノードを使いまわすという考え方で、ノードをまとめていきます。 つ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
30 分でわかるAdam
