2019年新卒研修で使った資料です。 内部実装の雰囲気を感じとりながら、Redisについて理解を深める研修を行いました。 以下の内容について学びました。 1. Redisの概要 2. 社内での利用方法 3. 正しい用法用量 Redis についての前提知識は必要としていません。…
アルゴリズムとデータ構造から理解するRedis / Learn Redis from Internal Algorithms and Data Structures
2019年新卒研修で使った資料です。 内部実装の雰囲気を感じとりながら、Redisについて理解を深める研修を行いました。 以下の内容について学びました。 1. Redisの概要 2. 社内での利用方法 3. 正しい用法用量 Redis についての前提知識は必要としていません。…
TRIE-Optimized Regexp : 404 Blog Not Found
2005年09月11日07:06 カテゴリLightweight Languages TRIE-Optimized Regexp これをPerlで直接使えたらうれしいよね＞おおる きまぐれ日記: はてなキーワードを高速に付与 そこで、はてなキーワードを TRIE を使って付与するプログラムを作ってみました。 というわけで、やってみました。 最初はDartsのXSを作ろうとしたのだけど、どうもtemplateばりばりのC++コードとXSは相性が悪い。でもTrieを作るだけなら、Perlでもそこそこ出来るし、実際Regexp::OptimizerやRegexp::Assembleのようなモジュールもある。ただこれらはTrie以外のOptimizeもしてしまうので、ちょっと重たいというわけで、mk_trie_regexp.plというScriptをサクっと書いてみました。 使い方は簡単。/usr/
きまぐれ日記: Autolink: 前方最長一致ではなく最長キーワード優先一致を実現する
Hatena のキーワード置換アルゴリズムがTRIE ベースの手法に変更になったようです。以前に AC法でやる方法の記事を書いたのですが、それと似たことをやってるのでしょうか。 AC法のやり方は単純で、前方から最長一致でキーワードを見つけていきます。これまでは長いキーワードから順番に見つけていく方法(最長キーワード優先一致)だったそうですが、前方から見つけていく方法だと短いキーワードが優先される場合があります。 http://d.hatena.ne.jp/ita/20060119/p1 http://d.hatena.ne.jp/hatenadiary/20060119/1137667217 本文：あいうえおかきくけこさしすせそ KW1 いう KW2 うえおかき KW3 かきく KW4 きくけこさし という文でKW1-KW4のキーワードがマッチする場合、新しくなった方法では「いう」と「かき
二値文字列の転倒数が従う群構造 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 概要 二値文字列の転倒数が従う群構造を紹介します。これによって範囲転倒数クエリが、累積和やSegment Treeで計算できます。Segment Treeでできます、という言及は今までに見たことがありましたが、累積和もできるという話は聞いたことがなかったのでまとめます。 二値文字列の転倒数とは、0と1からなる二値文字列 $s$ が与えられて、$s$ をソートするために必要な隣り合った0と1のswap数 $f(s)$ のことです。例えば、$s=101011$ を $001111$ にソートするためには、 $3$ 回のswapが必要なので、
ブラックホール撮影にも使える「スパースモデリング」とは？【機械学習】 - ざるご博士になりたいブログ
この記事は移転しました。約2秒後に新記事へ移動します。移動しない場合はココをクリックしてください。 どうもざるご（@zalgo3）です． 世界初のブラックホール撮影の成功例が出たようです． ブラックホールの撮影に成功 世界初 一般相対性理論を証明 - 毎日新聞 今回のブラックホール撮影は，スパースモデリングという機械学習技術を取り入れたことによる貢献が大きいようです． 天文学に計算機科学の知識が取り入れられて，大きな成果が出たというのは，驚くべきことだと思います． 今回はそんな大成功を巻き起こした「スパースモデリング」について解説していきます． スパースモデリングとは スパースモデリングとは，誤解を恐れずにざっくりいうと解けない連立一次方程式を無理やり解くための仕組みです． 次のような連立一次方程式を考えます． この方程式は，が逆行列を持つときに解くことができて， となります．では，が逆行
Dijkstra法に関するn考察 〜前半〜 - Mister雑記
(思ったより長くなりそうだったので前半と後半に分けることにしました。 後半の投稿予定は未定です。) 競技プログラミングのグラフ問題でしばしば題材となるアルゴリズム「Dijkstra法」。 その名前のインパクトと汎用性から比較的知名度が高いアルゴリズムだが、実装がそこそこ重いため初心者の壁となることもある。 そんなDijkstra法について、私の持つ知識、イメージを適当に書き連ねていこうと思う。 目次 目次 Dijkstra法の概要 何をするアルゴリズムか 具体例 イメージ？ 実装方法 パターンA パターンB (PFS) 計算量の比較 問題例 後半について Dijkstra法の概要 何をするアルゴリズムか Dijkstra法を一言で説明するなら「重み付きグラフにおいて、ある頂点から他の全ての頂点までの最短距離を求める」アルゴリズムである。 一工夫すれば最短距離を実現する経路も同時に求められる
ダイクストラとポテンシャルのはなし - niuez’s diary
はじめまして, niuezといいます. 競プロを少ししています. 最近勉強したことのメモ書きをしておきます. ダイクストラ法 ダイクストラ法(Dijkstra)は負の長さの無いグラフで始点からの最短距離を求めるアルゴリズムです. 具体的には 距離が未確定の頂点の中で一番小さいものを選び, 距離を確定させる. 選んだ頂点から距離が未確定の頂点に伸びる辺で, 未確定な距離をより短いものに更新する. を繰り返します. これを実装すると $O(N)$ですが, よく知られるダイクストラの計算量は $O((E+ V) \log E)$ です(heapとかを使う). #include <set> #include <queue> #include <vector> struct edge { int u,v; int dist; }; std::vector<int> dijkstra(const st
CodeChef GPD Gotham PD - kazuma8128’s blog
問題文 https://www.codechef.com/problems/GPD 問題概要 頂点数 N の根付き木が与えられる. 各頂点には正整数のキーが付いている. 以下の二種類の Q 個のクエリをオンラインで処理せよ. クエリ１：頂点 v の子に, キー k の付いた新しい頂点 u を増やす クエリ２：頂点 v から根までのパスに含まれる頂点に付いたキーの中で, k でXORしたときの最大の値と最小の値を求める 制約：1 ≤ N ≤ 10^5, 1 ≤ Q ≤ 2*10^5, 1 ≤ (各キー) ≤ 2^31-1 解法 まず, トライ木を使うと, 要素の挿入 (insert) , 要素の削除 (erase) , ある値でXORしたときの最大値/最小値の取得が O(ビット数) でできます. 詳しくは以下のページなどを参照 www.geeksforgeeks.org これを使って根からD
非負整数値を扱う Trie について - kazuma8128’s blog
はじめに 非負整数を二分木のトライ木で管理するアレに関する日本語記事があんまり無いっぽいので雑にメモ. （というかそもそも専用の呼び名ないのかな？） とりあえずここでは Binary Trie って呼んどきます. Binary Trie とは 整数をビット列とみなしてトライ木っぽく持つ set 的なことができるデータ構造です. 正確には要素の重複を許す multiset っぽく実装することが多そう. 整数集合を管理できますが, 平衡二分木よりも実装が楽なので最高です. こんな感じ ノードに書いてある数字は部分木に含まれる要素の個数です. できること ビット長を B とすると, 以下の操作が全て O(B) でできます. insert(x) : 値 x を集合に（一つ）追加 erase(x) : 値 x を集合から（一つ）削除 max_element/min_elemet() : 集合内の最大
スライド区間に対するクエリのまとめ
スライド区間に対するクエリ処理の種類とそれに対するアルゴリズムをいくつか紹介します。まず、「スライド区間」の定義ですが、窓関数のようなものを想像してください。例えば、[2,5,10,-1,0,4,...]というデータに対してサイズ3の窓関数をスライドさせると、[2,5,10], [5,10,-1],[10,-1,0],.....と複数の連続する区間ができます。これらの区間に対して以下のようなクエリを考えます。 データサイズが小さい場合は愚直な方法で計算しても問題ありませんが、データサイズが大きい場合やオンライン処理で次々にデータが来る場合は高速な処理が求められます。天気予報システムや金融システムなどではこのような需要があると思います。例えば、ある時間幅内での最高気温・最低気温・平均気温を計算したり、リアルタイムに株価の高値・低値を計算するなどです。
アルゴリズムの勉強は必要か？不要である3つの理由
アルゴリズムとは？ アルゴリズムとは、ある問題を解く具体的な手順のことです。 プログラミングの世界では、効率的な解法のことを指すことがあります。 有名なアルゴリズムだと、クイックソートと呼ばれるものがあります。 これは、その名の通り、数列を効率的にならべるアルゴリズムです。 また、私が初心者のころ 優秀なプログラマーになるためにはアルゴリズムが必要 と思ってアルゴリズムを勉強した覚えがあります。 しかし、今思えば 学習コストのわりにあまり役立たない知識 だったなという印象です。 今回はその理由を説明します。 現在、プログラミングをはじめたてでアルゴリズムを勉強しようとしてる方は必見。 たいていのアルゴリズムは実装されている ほとんどのアルゴリズムは発見された時点で実装済です。 ましてや、本に載ってるようなアルゴリズムは、 どんな言語でも標準モジュールに実装されていることがほとんどです。 そ
unordered_map について - mayoko’s diary
unordered_map で辛い思いをしたので twitter でわーわー言ってたらいろいろ勉強になったのでメモします。 まとめ 基本的にチェイン法っていうのでやってるっぽい vector< list< T > > みたいのをイメージするとわかりやすい 詳細 まとめで書いたように, 基本的には vector< list< T > > というのが全部説明している気がします。 find() は平均計算量 O(1), 最悪計算量 O(n) find() は, 基本的にはハッシュ値で vector にランダムアクセスするだけで目的のものが見つかるので O(1) だが, ハッシュ値がかぶっているものがあると, vector の要素のリストを線形探索しないといけない。なので最悪 O(n) insert(), delete() も平均計算量 O(1), 最悪計算量 O(n) 結局消す, 入れる場所を探
ヤフーにおけるアルゴリズム教育の取り組み
ヤフー株式会社は、2023年10月1日にLINEヤフー株式会社になりました。LINEヤフー株式会社の新しいブログはこちらです。LINEヤフー Tech Blog こんにちは。サイエンス1本部の真鍋です。 私は博士後期課程を修了後、2016年の4月にヤフーに新卒入社し、約半年間の新卒研修を経て現在のチームに配属となりました。それ以来2年半ほど、キーワード検索エンジンの実装と、検索結果ランキングの改善に取り組んでいます。 より具体的には、ヤフーショッピングの商品検索に関わっています。検索結果ランキングは主に機械学習で生成されたモデルによっているのですが、このモデルに商品のどんな属性や、ユーザーの皆さんのどんな行動を入力したらいいかを考え、その実現に必要なコードを実装するのが主な仕事です。快適なサービスを提供するために計算コストを削減したり、これら全てのことがスムーズに進むように運用コストを削減
動的計画法入門(An introduction to Dynamic Programming)
Similar to 動的計画法入門(An introduction to Dynamic Programming) (20)
Optunaでハイパーパラメータチューニング - HELLO CYBERNETICS
はじめに：Optunaとは 使い方 インストール 最適化問題の例 問題設定 最適化 最適化の結果 ニューラルネットワークのハイパーパラメータチューニング 問題設定 実装 ハイパーパラメータを引数に取り、ニューラルネットワークを構成する関数 ハイパーパラメータを引数にとり、最適化手法を返す関数 ハイパーパラメータを引数に取り、学習済のモデルを返す関数 ハイパーパラメータを引数に取り、最小化したい値を返す目的関数 いざ最適化 はじめに：Optunaとは OptunaとはPFNが世に送り出した最適化枝刈りライブラリです。 Pythonのコードとして機械学習のコードのどこにでも入れることができ、非常に使いやすいAPIとなっています。大体、結構丁寧なサンプル・解説が公式ドキュメントに既にあるので、分かる方は此方を読むのが一番早いでしょう。 Welcome to Optuna’s documentat
もうひとつの全方位木DP - ei1333の日記
なにもかくことがないね（えーん） もうひとつの全方位木DPなんですが、任意の全方位木DPが記述できるかは確認してない(多分できないと思う(うく))ので期待はしないでね ゴメンネ この記事は Competitive Programming (2) Advent Calendar 2018 の20日目の記事です。 adventar.org ei1333.hateblo.jp ※ 辺視点のほうが考えやすいので、辺視点で考えます。 頂点1を根とする根付き木があって、各辺についてDPの計算に必要な値が求まっているとします（根に向かう辺の値だけあればよい）。 下図のように別の頂点（今回は頂点 ）に根をうつしたときの木について求めたい場合は、もともとの木の根から離れる辺の値についての値をトップダウンに求めていきます。 矢印の先が、それが指す頂点からみたときの辺の値を示すこととします。 この操作により、頂
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Animation of Aho-Corasick string matching algorithm
乱択アルゴリズム紹介(行列乗算の検査&多項式等価性の検査) - Preferred Networks Research & Development
数列の任意の範囲で大きいほうから任意の個数のsumをO(1)で求める（注：O(logワードサイズ)です） - 誤読
GitHub - liyin2015/python-coding-interview: A middle-to-high level open source algorithm book designed with coding interview at heart!
