ソートされた整数列(転置インデックスのポジションリストとか)の圧縮に elias-fano-encoding という手法があることを知った。Quasi-succinct で、試したところ、ありがちな手製圧縮をはるかに凌駕する。 https://t.co/f32s48zQHn
Taku Kudo on Twitter: "ソートされた整数列(転置インデックスのポジションリストとか)の圧縮に elias-fano-encoding という手法があることを知った。Quasi-succinct で、試したところ、ありがちな手製圧縮をはるかに凌駕する。 https://t.co/f32s48zQHn"
ソートされた整数列(転置インデックスのポジションリストとか)の圧縮に elias-fano-encoding という手法があることを知った。Quasi-succinct で、試したところ、ありがちな手製圧縮をはるかに凌駕する。 https://t.co/f32s48zQHn
アムダールの法則 - Wikipedia
複数のプロセッサを使って並列計算してプログラムの高速化を図る場合、そのプログラムの逐次的部分は、制限を受ける。例えば、仮にプログラムの95%を並列化できたとしても、残りの部分である5%は並列処理ができないため、どれだけプロセッサ数を増やしたとしても、図で示したように20倍以上には高速化しない。 アムダールの法則（アムダールのほうそく、英語: Amdahl's law）は、ある計算機システムとその対象とする計算についてのモデルにおいて、その計算機の並列度を上げた場合に、並列化できない部分の存在、特にその割合が「ボトルネック」となることを示した法則である。コンピュータ・アーキテクトのジーン・アムダールが主張したものであり、アムダールの主張（アムダールのしゅちょう、英語: Amdahl's argument）という呼称もある[1]。 複数のプロセッサを使い並列計算によってプログラムの高速化を図る
競プロでよくある「バランスのとれた括弧列」の定義が壊れがちな話 - notブログ
「空文字列でない」を入れることにしたみたいです（今日のABC-Fもそうでした）。 PAST中めちゃくちゃ考えましたが、確かにこれで一意になりそうです。https://t.co/Aykgtguv14— きり (@kiri8128) May 10, 2020 なるほどなぁと思ったし周知しておくべきだと思ったので記事にしました。 よくある間違った定義 - 1 バランスのとれた括弧列は以下のいずれかの条件を満たす。 空文字列 バランスのとれた括弧列が存在し、'(',,')'をこの順に結合した文字列 バランスのとれた括弧列,が存在し、,をこの順に結合した文字列 E - Parentheses C - 部分文字列と括弧 よくある間違った定義 - 2 バランスのとれた括弧列は以下のいずれかの条件を満たす。 '()' バランスのとれた括弧列が存在し、'(',,')'をこの順に結合した文字列 バランスのとれ
SQL実行時のブルームフィルタ(Bloom Filter)アルゴリズム | フューチャー技術ブログ
1. 初めにDBにおける処理はSQLによって記述しますが、データの取得するために具体的にどのような内部処理を行うかという点までは記述しません。 ここでいう内部処理とは「SQLの書き換え」「インデックスの使用」「結合アルゴリズムの選択」などがDBMSのオプティマイザによって選択されて実施されることを指します。 SQLのパフォーマンスを見るにあたっては上記の内部処理について正しく理解する必要があります。 本Blogでは、重要なアルゴリズムであるにもかかわらず、まとまった情報が少ないSQL実行時におけるブルームフィルタ(Bloom Filter)についてOracleをもとに紹介を行います。 Bloom Filterは結合処理を効率化するために、結合の前段階で利用される技術になります。 公式なドキュメントとしては以下になります。 Oracle Database SQLチューニング・ガイド 12cリ
確率的データ構造の比較：カッコウフィルタ対ブルームフィルタ | POSTD
確率的データ構造は少ないメモリでデータをコンパクトに保存し、保存されたデータに関するクエリに対し、おおよその答えを提供してくれます。クエリに対し空間効率の良い方法で答えるように設計されており、それはつまり、正確さを犠牲にするということにもなります。しかし、これらは一般的に、問われているデータ構造の仕様にもよりますが、誤差率の保証と境界を提供してくれます。メモリ使用量が少ないため、確率的データ構造はストリーミングや低出力の設定に特に有用なのです。ですから、動画の視聴回数を数えたり、過去に投稿された一意となるツイートのリストを維持したりするなど、ビッグデータの環境下では非常に有用です。例えば、 HyperLogLog++ 構造 は、2.56KBのメモリで最大790億の一意のアイテムを数えることができるのですが、誤差率はわずか1.65パーセントです。 Fast Forward Labsのチームは
CHAGEの裏側: ブルームフィルタとISONの逆引き高速化 | IIJ Engineers Blog
セキュリティ本部 セキュリティ情報統括室に所属 システム開発者。2000年問題で「2038年問題は定年で対応しなくていい！」とフラグを...。 CHAGE開発者のヒラマツです。 前回（CHAGEの裏側: D3.jsの紹介）同様、CHAGEの紹介と並行して、CHAGEの中が気になる人に、CHAGEで使われている技術をちょっと濃い目に解説するという企画です。 今回は、本編（CHAGE の動き）がISONネタなので、こちらもISONに関係ある話として、ブルームフィルタについて書きます。 ブルームフィルタをざっくり解説してから、ブルームフィルタの具体的な使用例としてISONでの逆引き高速化の方法を紹介していきたいと思います。 目指すのは、ちゃんとした理解ではなく、「ブルームフィルタの雰囲気を知って、利用価値をなんとなく判断できる」ところです。 今回は、以下の知識を前提にしているので、そこはご了承く
意外と簡単!1vs1の総当りリーグ戦のスケジュール - Korokorotuneのブログ
この記事はNCC Advent Calendar 2015の23日目の記事です。 昨日はtkdくんによる"あなたの知らないSurfaceの闇"でした。 前回、私が書いた記事はなんか堅苦しい感じになってしまったので、今回はゆるふわな感じでいきたいと思います。 ちなみに、NCC Advent Calendar 2015も残すところあと2日ですが、この記事は例によって技術的な話はまったくないです。(ｽﾝﾏｾﾝ 今回は、1vs1の総当りリーグ戦のスケジュールを組むアルゴリズムについて話そうと思います。 Chapter 1. 1vs1の総当りリーグ戦とは 1vs1の総当りリーグ戦とは野球やサッカーなどの1対1で試合をする競技の総当りリーグ戦のことを指します。日本のプロ野球やJリーグもこの総当りリーグ戦が行われています。 わかりやすくJリーグの例で説明しましょう。 J1リーグの試合は、すべてのチーム対
線分集合の交点列挙： Bentley-Ottmann のやり方
今回は、線分集合の交点列挙について Bentley-Ottmann のやり方を調べたので、そのメモです。よろしくお願いします。 現在、気が向いたときに平面性テストのデバッグをしているのですけど、ある平面描画に対して、辺対の交差チェックができたら良いなぁって思っていました。そもそも、いまのところ、ちっちゃいグラフが対象なので、\(O(n^2)\) で良いし、無理する必要なかったのですけど、軽い気持ちで Bentley-Ottmann のやり方に着手してしまいました。 まだ、きちんとテストしきれてないので、バグバグだと思いますけど、際どい境界条件とかじゃない限り動いていそうなので「モウイヤニナッタヨ」で切り上げました。よろしくお願いします。 python コード 今回のもやっぱり未完成で暫定的なものですけど、github に置きました。参考になるとは思いませんけど、もし腹が立ったら、ごめんあそ
組合せ最適化における最先端アルゴリズムと機械学習
30分程度の動画なので夕食を見ながら食べるのに最適です。 ================================================ Vertex Coverと巡回セールスマン問題はどちらも非常に研究の歴史が長いNP-hard問題です。 これらの問題には多項式時間アルゴリズムが存在しないと考えられているにも関わらず、最先端のソルバは数万頂点のインスタンスにさえ、厳密解を与えることがあります。 それとは別に、近年、機械学習によってこうした離散最適化問題を解こうとする試みが生まれています。機械学習によるアプローチの難しさはどうしたところから生まれるのかを皆さんにも考えていただきたいです。
xoshiro/xoroshiro generators and the PRNG shootout
Introduction This page describes some new pseudorandom number generators (PRNGs) we (David Blackman and I) have been working on recently, and a shootout comparing them with other generators. Details about the generators can be found in our paper. Information about my previous xorshift-based generators can be found here, but they have been entirely superseded by the new ones, which are faster and b
Dinic法について - TAISA_'s blog
理解にかなり手間取った&面白かったのでメモ。 アルゴリズム やっていることは、「長さが短い順に増加路を使っていく」というだけ。 以下、頂点数 、辺数 、始点 、終点 のネットワークを考える。 残余グラフを構築しておく。 増加路がなくなるまで、以下を繰り返す。この一回の繰り返しを「1ステップ」とする。 BFSで、「容量正の辺のみを使った時の、 から までの最短路長」 を求める。 長さ の増加路がなくなるまで、DFSで増加路を選び、フローを増やす。 なる辺 以外はないものとして扱えば、増加路は全て長さ になる。 DFSの際には、「その辺を使ったフローがこれ以上流せない」状態になった辺を記録し、以降の探索では無視するようにする。つまり、その辺を使おうとしたが、 に辿り着けなかった時と、容量が0になった時、辺は死ぬ。 なお、辺が死んでも1回のステップが終わったら復活する。 計算量(一般のグラフの場
量子フーリエ変換を「位相差に情報を埋め込む」という視点で理解してみる - めもめも
enakai00.hatenablog.com 何の話かと言うと 上記の記事で説明した量子フーリエ変換は、本質的には、 --- (1) という線形変換（ユニタリ変換）を量子回路で実装しただけのことですが、「なぜ (1) の表式が量子回路と相性がよいのか？」という部分を踏み込んで考えてみます。 位相差情報の抽出機としての（逆）フーリエ変換 もともとの話の流れでは、数学的に知られていたフーリエ変換 を量子ビットで表現したら、なんとも不思議な (1) の表式が得られた・・・・という事になりますが、実は、(1) はアダマール変換 の自然な拡張と見なすことができます。 どいういうことかと言うと、容易に分かるように、アダマール変換 は次のように表すことができます。 これは、1量子ビットの生の値を同じ量子ビットの位相差に変換する。つまり、位相差に情報を埋め込む演算とみなすことができます。 実は (1)
スキップリストで区間を管理するやつ - shibh308’s diary
はじめに スキップリストで区間の管理をする方法が載ってそうな記事があまりなかったので書きました(雑記事です) できること スキップリストは insert erase access lower_bound split concatenate 区間和 区間更新 とかができます。あと永続化もできるっぽいんですが僕はやってません・・・ スキップリスト自体の概要 Wikipediaに載ってます ランダムアクセスの方法 Wikipediaに載ってます 区間管理の方法 下のようなスキップリストに区間minの情報を持たせる事を考えます。 スキップリストの例 このリストからノード部分だけを切り出すとこんな感じにかけて、 ノード部分を切り出したやつ 空いてる部分を横に伸ばすとこんな感じになります。 区間を持たせたやつ 各ノードごとに下の段の値の最小値を持たせると、こうなります。 区間minを持たせたやつ こう
Rolling Hashについて（survey + 研究） | maspyのHP
新しい数値設定や実装方法を提案するものではありません。 衝突確率の下からの評価に対して、見たことがない考察を行ったので、記しておきます。 前提知識 本記事では簡単のため、アルファベットの集合を $\Sigma = \{0,1,\ldots,\sigma-1\}$ とします。英子文字であれば、ASCII コードによりアルファベットを $128$ 未満の整数に対応させたり、それをずらして $26$ 未満の整数に対応させることで、アルファベットを整数と見なせます。 Rolling Hash とは Rolling Hash は、文字列 $S = S_0,S_1,S_2,\ldots$ を次のようにHash化する手法です： 【Rolling Hash】 法 $m$, 基数 $r$ を何らかの方法でとる。 文字列 $S = S_0,S_1,S_2,\ldots$ の Hash値 を$\mathrm{h
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
浮動小数点数オタクが AtCoder Beginner Contest 169 のC問題をガチで解説してみる - Qiita
ꑄ꒖ꐇꌅꏂ🐾 on Twitter: "なんかニコニコ大百科にマルコフアルゴリズムの記事が出来たらしく、読んでみたらめちゃ秀逸だった。ありがとうございます。 https://t.co/6A1hkN9AYT #MarkovAO"
GitHub - Reputeless/Xoshiro-cpp: Header-only Xoshiro/Xoroshiro PRNG wrapper library for modern C++ (C++17/C++20)
Ryo Suzuki on Twitter: "疑似乱数生成器 Xorshift の現代版、「Xoshiro」シリーズの C++ ラッパーライブラリのプロジェクトを公開しました。C++20 の標準乱数生成インタフェースに対応、ゲーム開発や研究プロジェクトに便利です (MIT ラ… https://t.co/JqzFiwvvVy"
講談社サイエンティフィク on Twitter: "＼50周年！／『データサイエンス入門シリーズ』新刊2冊を抽選で3名に同時プレゼント。応募締切4/21(火) 23:59 『モンテカルロ統計計算』 https://t.co/gpURfqNqME 『データサイエンスのためのデータベ… https://t.co/NGXLQeSRT0"
Yuki Yoshida on Twitter: "【朗報】どうぶつの森の住人(NPC)は「迷路」を解けることが判明(動画は一度も迷うことなく釣りをしに行くおさいの様子です) #どうぶつの森 #AnimalCrossing #ACNH #NintendoSwitch https://t.co/DoBg0SbOTF"
