【逐次更新】Heap や stack を filter して pop する実装を要求する問題リスト - ブログ名
逐次更新です。該当する問題を見つけたら @ngtkana_kyopro までお知らせいただけると幸いです。 問題リスト 問題 container description ARC 181 D - Prefix Bubble Sort heap pop_while ARC 001 D - レースゲーム stack これも pop_while 系ですがライブラリで対応するのはキビシそうです ライブラリ use std::collections::BinaryHeap; use std::iter::FusedIterator; pub trait Popmore: Sized { type Item; fn pop(&mut self) -> Option<Self::Item>; fn peek(&self) -> Option<&Self::Item>; fn pop_if(&mut sel
ハッシュ関数「SHA-256」の計算プロセスをわかりやすく視覚化してくれる「Sha256 Algorithm Explained」
アメリカの国家安全保障局(NSA)によって開発された「SHA-2」は電子署名やブロックチェーンに応用される暗号学的ハッシュ関数の1つです。そのSHA-2の中でも特に使われているSHA-256でハッシュを生成するための計算プロセスがよくわかるサイト「Sha256 Algorithm Explained」を、Domingo Martin氏が公開しています。 Sha256 Algorithm Explained https://sha256algorithm.com/ Sha256 Algorithm Explainedにアクセスするとこんな感じ。 上部にある入力欄に、好きな文字列を入力します。今回はGIGAZINEのURLである「https://gigazine.net/」を入力してみました。すると、入力したURLをバイナリに変換したメッセージブロックが表示されます。メッセージブロックは32b
Swisstable Hash に使われているビット演算の魔術 - methaneのブログ
Googleが開発したSwisstableと呼ばれるハッシュテーブル実装がAbseilとして公開されて、Rustの標準のHashMap実装にもその移植であるhashbrownが採用されました。 Swisstable の面白いところは、8または16要素をグループ化して、グループ内の各要素のハッシュ値のうち7bitをそれぞれ1byteに格納した8または16バイトの配列を作り、その配列に対して一気に並列でマッチングを行うことです。 この並列マッチングにはSSE2もしくはビット演算が使われます。この記事ではこの並列マッチング部分について解説します。 SSE2を使う場合 SSE2を使う場合は、グループのサイズは16になります。ハッシュ値を格納する配列のことを control と呼ぶことにすると、 control は char control[16] になります。control の各バイトの状態は次の
いろんなバンディットアルゴリズムを理解しよう - Qiita
今回は、何も知らないところからバンディットアルゴリズムを学びました。 シンプルなバンディットアルゴリズムから、各ユーザーごとに最適化するContextual Bandit、順序を最適化するCascading Banditまで解説します。 学んでいて疑問に思ったことを解消しつつ記載しています。 ソースコード https://github.com/birdwatcherYT/bandit 対象読者 バンディットアルゴリズムを理解して実装したい人 ユーザーごとにカスタマイズしたバンディットを理解して実装したい人（Contextual Bandit） 順序を最適化するバンディットを使いたい人（Cascading Bandit） バンディットアルゴリズム バンディットの問題設定を説明します。 スロットマシンN台がある スロットマシンの腕を引くと報酬がもらえる 累積報酬を最大化したい バンディットアル
徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
TLS 1.3 開発日記 その22 公開鍵暗号の動向 - あどけない話
P256とかX25519とかPSSとか聞いても、よくわからない人のための用語解説。 長い間TLSの世界では、鍵交換にも認証にもRSAが使われてきた。必要となる安全性が大きくなると、RSAの公開鍵は急激に大きくなり、したがって鍵交換や認証のコストが大きくなるという問題がある。 楕円曲線暗号(ECC: Elliptic Curve Cryptography)は、RSAやDiffie Hellmanに比べると、小さな公開鍵で同程度の安全性を実現するという特長を持つ。特許問題が不透明なせいで楕円曲線暗号は長年敬遠されてきたが、この数年で(少なくとも鍵交換に対しては)一気に普及してきた感じだ。 おおざっぱに言うと、楕円曲線暗号で実現できるのは、DH(Diffie Hellman)とDSA(Digital Signature Algorithm)であり、RSAは実現できない。 鍵交換のDHに関しては、
解説: Life Universe
公開からだいぶ時間が経ってしまいましたが、Life Universe の技術解説を書きます。 English version is here. Life Universe について その前に、いくつか知っておくとよい事柄があるので先に説明します。 OTCA Metapixel について ライフゲームの説明については割愛します。ライフゲームはチューリング完全なので様々なパターンが存在し、その中に OTCA Metapixel というものが存在します。OTCA Metapixel は（メタ）セルのオンとオフの状態が視覚的に分かる特殊なパターンで、ライフゲームのみならず outer totalistic なルール[1]で動く全ての[2]２次元セルオートマトンを再現できます。 つまり、ライフゲームの中で動くライフゲームを見ることができます。 こちらは有名な動画ですが、実際にこういう計算が可能になり
キャッシュアルゴリズムの比較 - falsandtruのメモ帳
アプリケーションなどOSより上に作られる高水準のプログラムではハードウェアの速度と容量を考慮しない数学的キャッシュアルゴリズムが使われ主にこれを本稿の対象とする。キー探索用マップと明示的キャッシュサイズ(対となる値が保持されているキーのサイズ)は計算量に含まれない。 LRU 最も単純かつ高性能な基礎的キャッシュアルゴリズム。そのため性能比較のベースラインとして常に使用される。逆に言えば実用最低水準の性能である。スキャン耐性皆無でスキャン一発でキャッシュとヒット率がリセットされゼロからやり直しになるため非常に脆く不確実な性能となりベンチマークにおける性能が表面上さほど悪くなく見えても実際の性能はこのような外乱により大きく低下しやすい。このためLRUより高度な主要アルゴリズムはすべて大なり小なりスキャン耐性を備えている。ちなみにプログラミング言語最大のパッケージマネージャであるJavaScri
積の和典型 - Shirotsume の日記
最近積の和典型が話題になっているので書きます。 N個のマス目が横一列に並んでいる状況を考えます。初め、全部のマスは白色です。このうち K 個のマスを選んで黒く塗った時にできるマスの状態は何通りでしょうか？ これを こうする これは 通りです。 これを応用すると、次のような問題が解けます。 長さが N であって、総和が M である非負整数列の個数を求めよ。 非負整数列というのは、各要素が負の数でない整数からなる数列です。[1, 2, 3, 4, 5] とか [0, 0, 1, 4, 3] とかです。これの個数を数えるのに、先ほどのマスの数え方を使うことができます。 まず、 M + N - 1 個の白いマス目を用意します。そのあと、そこから N - 1 マス選んで塗ります。こうしたとき、必ず M 個のマスが白いままで残っています。また、マスの両端や黒マスを境目として考えると、白いマスが連続する
テキストエディタで使われがちなデータ構造 Piece Table の概要と実装 - A Memorandum
テキストエディタのデータ構造 Gap method Piece Table method Piece Table の構造 Piece Table の実装 Piece Table のメソッド まとめ テキストエディタのデータ構造 テキストエディタで採用されているデータ構造にはいろいろあります。 こちらの論文 Data Structures for Text Sequences では各種データ構造について比較検討されています。 多くは、Gap method や Piece table method をベースにしたものが多いのではないでしょうか(図で言う最下部の中心の丸印に当たります)。最近では Rope なども有名ですね。 Gap method Gap method では、現在のカーソル位置で、テキストバッファを2つに分割し Gap を間に挟み、カーソル位置に対する編集(テキスト追加/削除)を
木構造の DnD に適した処理を考える
DnD は考えることが多い。大抵のライブラリは特定のユースケースにべったりで、毎回自分で書く羽目になる。 とくに、木構造の DnD をどう表現するかが難しい。特にWeb上でファイラーのようなUIを実装する頻度が高く、その求められる実装が毎回違うので、自分が考えていることを一般化してみる。 この記事はコードをコピペしたら使えるものではなく、あくまで考え方をコードに落としたもの、ということに注意。 今回は前提として、こういうものを作っていた。 DnD の要件 DOM ベースの sortable ライブラリはいっぱいあるが、DOMをマスターデータとして扱うタイプが多く、現代のフレームワークと噛み合わない。可能な限りデータを元に表現して、最後に変更したデータを render するだけとする。 フレームワーク非依存な処理を切り出して、UIを通さずにテストを書いたり、ポータブルに扱えるようにしたい。
Python言語による実務で使える100+の最適化問題 | opt100
指針 厳密解法に対しては、解ける問題例の規模の指針を与える。数理最適化ソルバーを使う場合には、Gurobi かmypulpを用い、それぞれの限界を調べる。動的最適化の場合には、メモリの限界について調べる。 近似解法に対しては、近似誤差の指針を与える。 複数の定式化を示し、どの定式化が実務的に良いかの指針を示す。 出来るだけベンチマーク問題例を用いる。OR-Libraryなどから問題例をダウンロードし、ディレクトリごとに保管しておく。 解説ビデオもYoutubeで公開する． 主要な問題に対してはアプリを作ってデモをする． 以下，デモビデオ： 注意 基本的には，コードも公開するが， github自体はプライベート そのうち本にするかもしれない（予約はしているが， 保証はない）． プロジェクトに参加したい人は，以下の技量が必要（github, nbdev, poetry, gurobi); ペー
高速逆平方根(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
最高にエッチな画像が遺伝的アルゴリズムで生み出される様子を見て反省する日々 - 本しゃぶり
「なぜ見抜けなかったのか」 画像の選択を迫られるたびに俺は自問する。 進化の筋道を正しく予測するのは難しい。 遺伝的アルゴリズムの活用 2021年から、新たに習慣となった行為はあるだろうか。俺はある。PCの前に座り、二つの画像のうち、どっちの方がエッチかを選ぶ。これがモーニングルーティンとなっている。もちろんこれの話だ。 遺伝的アルゴリズムで最高にエッチな画像を作ろう！ これまで何度も話題になっていたし、直近でも関連ツイートがバズっていたので、本記事を読む人の大半は知っているだろう。名前の通り、遺伝的アルゴリズムでエッチな画像を作るシステムである。人が画像を選択することで、よりエッチな画像が生き残り、高みへと一歩近づく。最初はノイズのようなモザイク画だったが、10,000世代を超えた現在では「女性の裸体」と認識できるものに仕上がっている。 0世代と10,000世代 現状について「最高にエッ
APIに利用制限をかけるとしたらどういうやりかたがあるのか - おもしろwebサービス開発日記
この記事はSmartHR Advent Calendar 2020 11日目の記事です。 僕のお手伝いしているSmartHRでは、毎週バックエンドエンジニアが集まり、技術的なトピックについて共有、相談しあうミーティングを開催しています。そのミーティングでは僕がTipsなどを共有するコーナーが常設されています*1。 このエントリでは、そのコーナーで共有した内容をひとつ紹介します。 APIに制限をかける方法について APIを外部に提供するとき、一定の制限をかけてユーザがAPIを乱用するのを防ぐことはよくあることではないでしょうか。素直に考えると「1時間に5000回までAPIを実行できる」のようなやり方を思いつきますね。GitHubのAPIもそのやり方ですし、SmartHRのAPIも同様です。 じゃあそれでいいのでは。となるかもしれませんが少し待ってください。いろんなクライアントがAPIを大量に
出、出～～ｗｗｗｗｗ銀行員待行列解説奴～ｗｗｗｗｗｗｗ - モナドとわたしとコモナド
銀行員待行列(Banker's deque)、二つのリストで構成奴～～ｗｗｗｗｗ 入奴と出奴～ｗｗｗｗｗｗｗｗｗ ↓入奴 三(^o^)ノ [(^o^)ノ, (^o^)ノ, (^o^)ノ] ヽ(^o^)三 [ヽ(^o^), ヽ(^o^), ヽ(^o^)] ↑出奴 追加は入奴にcons、取り出しは出奴にuncons奴～ｗｗｗリストなので基本定数時間奴～ｗｗｗｗｗｗ リスト枯渇防止の為、リストの長さに以下の条件課奴～～～ｗｗｗｗｗｗ length (入奴) <= length (出奴) * 3 + 1 length (出奴) <= length (入奴) * 3 + 1 条件充足不能場合、|length (入奴) - length (出奴)| <= 1なるよう余剰分反転後短い側の末尾に結合して調整奴～ｗｗｗｗｗ時間計算量O(length (入奴) + length (出奴))必要～～～～ｗｗｗｗ
我が国における超過死亡の推定（2020年4月までのデータ分析）
掲載日：2020年7月31日 要約 2012年～2020年の人口動態統計データを用いて、日本における新型コロナウイルス感染症流行期（2020年1月～4月末）の超過死亡を週別、都道府県別に推定した。欧米諸国と我が国における比較可能性を考慮し、米国疾病予防管理センター（Centers for Disease Control and Prevention：CDC）の用いるFarringtonアルゴリズム、および欧州死亡率モニター（EuroMOMO）の用いるFluMOMOモデルを用いた。結果、Farringtonアルゴリズムで超過死亡が検出されたのは、千葉県（47人：4月20日–26日、疫学週第17週）のみであった。またEuroMOMOアルゴリズムでは、栃木県（14人：2019年12月30日–2020年1月5日、疫学週第1週）、埼玉県（5人：4月13日–19日、疫学週第16週）、千葉県（61人：4
『みんなのデータ構造』でデータ構造の基礎を学んだ - valid,invalid
データ構造とアルゴリズムの学習の一環として『みんなのデータ構造』を読んだ。これまでで最も良いデータ構造の学習になった。 みんなのデータ構造 作者:Pat Morin発売日: 2018/07/20メディア: 単行本（ソフトカバー） 日本語訳がWebで公開されているので気になる方は無料で読める。が、著者や訳者や出版社応援の意味も込めて購入すると良いと思います。また、ラムダノート社のサイトから買うと紙書籍と電子書籍のセットがお得。 内容 データ構造とアルゴリズムに関連する本はアルゴリズム寄りのものが多いが、データ構造に焦点を当て続けていることが本書の特色。 内容の依存関係 p.21より 大学の教科書のように、正確性を優先したハードコアな内容。 アルゴリズムの内容も少しだがある。「11章 整列アルゴリズム」ではそれまでの章で学んだデータ構造がどのように使われるかを一瞥でき、「12章 グラフ」では深
アルゴリズムロジック
問題へのリンク 問題概要座標 \((0,0)\) からスタートして \(N\) 回の移動で \((X,Y)\) に到達する確率を求めたい。 1回の移動では、上下左右それぞれの方向に確率 \(\frac{1}{4}\ ...
競プロのアルゴリズム関連略称まとめ - noshi91のメモ
随時募集しています 略称 正称 APSP All Pairs Shortest Path BB Branch and bound BBST Balanced Binary Search Tree BFS Breadth First Search BIT Binary Indexed Tree BM Berlekamp-Massey BM Boyer-Moore BSGS Baby-Step Giant-Step CHT Convex Hull Trick CRT Chinese Remainder Theorem D&C Divide and Conquer DAG Directed Acyclic Graph DEPQ Double-ended priority queue DFS Depth First Search DP Dynamic Programming DST Disjoin
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
