確率的データ構造の比較：カッコウフィルタ対ブルームフィルタ | POSTD
確率的データ構造は少ないメモリでデータをコンパクトに保存し、保存されたデータに関するクエリに対し、おおよその答えを提供してくれます。クエリに対し空間効率の良い方法で答えるように設計されており、それはつまり、正確さを犠牲にするということにもなります。しかし、これらは一般的に、問われているデータ構造の仕様にもよりますが、誤差率の保証と境界を提供してくれます。メモリ使用量が少ないため、確率的データ構造はストリーミングや低出力の設定に特に有用なのです。ですから、動画の視聴回数を数えたり、過去に投稿された一意となるツイートのリストを維持したりするなど、ビッグデータの環境下では非常に有用です。例えば、 HyperLogLog++ 構造 は、2.56KBのメモリで最大790億の一意のアイテムを数えることができるのですが、誤差率はわずか1.65パーセントです。 Fast Forward Labsのチームは
さまざまなレート制限アルゴリズムをアニメーションでわかりやすく視覚化するとこんな感じ
スパム防止などのためのレート制限を行うアルゴリズムは多数存在しています。さまざまなアルゴリズムの特徴をアニメーションでわかりやすくまとめたブログ記事をChatGPT関連のサービスsmudge.aiが開発ブログにて公開しました。 rate limiter – smudge.ai blog https://smudge.ai/blog/ratelimit-algorithms 配信のチャット欄にスパムが出現するという状況において、レート制限がない場合にはスパマーは短時間のうちに多数の投稿を行ってチャット欄を一人で埋め尽くしてしまいます。 左上の「Enable rate limiting」にチェックを入れるとレート制限を加えた場合の挙動が確認できます。レート制限が加わったことで、スパマーの投稿のほとんどをブロックしてチャット欄に与える影響を下げることができました。このとき、状況に応じて適切なアル
The life and times of an Abstract Syntax Tree
You’ve reached computer programming nirvana. Your journey has led you down many paths, including believing that God wrote the universe in LISP, but now the truth is clear in your mind: every problem can be solved by writing one more compiler. It’s true. Even our soon-to-be artificially intelligent overlords are nothing but compilers, just as the legends foretold. That smart contract you’ve been wr
僕たちがグラフニューラルネットワークを学ぶ理由
グラフニューラルネットワーク - Forkwell Library #50 https://forkwell.connpass.com/event/315577/ での講演スライドです。 サポートサイト：https://github.com/joisino/gnnbook グラフニューラルネット…
『Winny』の金子勇さんの失われたED法を求めて - Qiita
結論から言うと、この記事を読んだ @pocokhc (ちぃがぅ)さんという方が金子勇さんが書いたED法のサンプルプログラムを見つけてくださいました。 ちぃがぅさんの記事はこちら 自分で解明したかったという気持ちも無いことは無いですが、バズった時点で誰かが実装してくれそうな気はしていました。新卒からIT業界に入って4年目が始まったところですが、業務以外で初めて業界にコントリビュートできた気がして嬉しいです！ 追記ついでに、謝罪します。初回公開時に記事タイトル含め本文中で何か所か「Winney」と書いてしまっていた箇所がありました。失礼いたしました。誤字修正してあります。指摘してくださった何人かの方に感謝申し上げます。 はじめに 今更ですが映画『winny』を見ました。 劇中で、金子勇さんのセリフにED法という聞いたことのないアルゴリズムが登場しました。 『このNekoFightにはAIを搭載
なぜUUIDはハイフンで8-4-4-4-12に区切られているか？ - Buri Memo:
ある特徴的な文字列がある。 11b484b6-cfeb-4730-8fba-467aee2d26ad 使ったことがあれば、恐らくすぐに UUID であると分かると思う。UUID は16進数がハイフンで分けられた特徴的なフォーマットをしている。その区切り方は、 8-4-4-4-12 となんだか不思議な感じだ。 そもそも、UUID は 128bit の数値であり、それを文字列で表現したものなのでハイフンが無くたって問題ない。にもかかわらずわざわざ覚えにくいケタで区切ることが多い。 その理由として、最初に思いつくのは人間が読みやすくするためだとは思うが、覚えやすく均等に区切ったり、左右対称の形にはできなかったのだろうか？ UUID の定義 生成した UUIDv1 を眺めてみる 元祖 UUID（Network Computer System の UUID） 形式の謎 RFC4122 で times
いろんなバンディットアルゴリズムを理解しよう - Qiita
今回は、何も知らないところからバンディットアルゴリズムを学びました。 シンプルなバンディットアルゴリズムから、各ユーザーごとに最適化するContextual Bandit、順序を最適化するCascading Banditまで解説します。 学んでいて疑問に思ったことを解消しつつ記載しています。 ソースコード https://github.com/birdwatcherYT/bandit 対象読者 バンディットアルゴリズムを理解して実装したい人 ユーザーごとにカスタマイズしたバンディットを理解して実装したい人（Contextual Bandit） 順序を最適化するバンディットを使いたい人（Cascading Bandit） バンディットアルゴリズム バンディットの問題設定を説明します。 スロットマシンN台がある スロットマシンの腕を引くと報酬がもらえる 累積報酬を最大化したい バンディットアル
LeetCode 150問を解いて起きた意外な変化
はじめに 年末に Twitter でこのツイートを見かけました。 もともとアルゴリズムの勉強に興味があり、一年ほど前に数ヶ月だけ AtCoder をやっていましたが、途中で挫折してしまった自分にとって、NeetCodeの勉強ロードマップは非常に魅力的に感じました。（転職意欲があったわけではないです） NeetCode のロードマップ そこで、このロードマップに従って LeetCode の問題を 150 問解くことを決意し、結果的におよそ1ヶ月半で全ての問題を解き切ることができました。 この過程で、様々なことを学ぶことができました。中には自分が予想していなかった学びも多くありましたので、同じくアルゴリズムに興味のあるエンジニアの方に役立てていただけるよう、記録として残しておきます。 ハードスキル 📗 データ構造への理解 頻出するデータ構造について、それぞれの長所/短所を理解し、主要な処理の
[2023年1月版]競技プログラミングを始めたばかりの人にオススメの問題集 - Qiita
最推し: アルゴ式 2023年1月現在、初心者向けの最初の問題集としてお勧めしたいのは アルゴ式 です。アルゴ式の特徴として次のようなものがあると思っていて、それが初心者が練習するうえで適した特徴だと考えるからです ジャンルごとに問題が分かれている 1ジャンルごとの問題数がそれなりにある ひとつひとつの問題の難易度が易しめ 興味の湧いた人は、とりあえずアカウントを作って問題を解いてみてください。 なお、「競技プログラミングを始めたばかりの人」と言っても、その人の経験によって最適なものは変わってくるとは思いますが、次のような人を想定したときに特にアルゴ式が適していると思います。 プログラミング自体の初心者ではない。 初歩的なプログラミングの概念は一通り把握しているくらいを想定。 過去問に取り組もうとしたけど、A問題やB問題でも結構難しいと感じる。 この想定にマッチしない人であれば、次節以降で
![[2023年1月版]競技プログラミングを始めたばかりの人にオススメの問題集 - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/b8b3353fe8c1703779f83fb6be4e3059086a0fe8/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fqiita-user-contents.imgix.net%252Fhttps%25253A%25252F%25252Fcdn.qiita.com%25252Fassets%25252Fpublic%25252Farticle-ogp-background-afbab5eb44e0b055cce1258705637a91.png%253Fixlib%253Drb-4.0.0%2526w%253D1200%2526blend64%253DaHR0cHM6Ly9xaWl0YS11c2VyLXByb2ZpbGUtaW1hZ2VzLmltZ2l4Lm5ldC9odHRwcyUzQSUyRiUyRnFpaXRhLWltYWdlLXN0b3JlLnMzLmFtYXpvbmF3cy5jb20lMkYwJTJGMTUzMjAlMkZwcm9maWxlLWltYWdlcyUyRjE0OTIwNzA1ODg_aXhsaWI9cmItNC4wLjAmYXI9MSUzQTEmZml0PWNyb3AmbWFzaz1lbGxpcHNlJmJnPUZGRkZGRiZmbT1wbmczMiZzPWMzMjdjMTVjMTYxNmNjZTc3N2VlNTkwODBmMGQxMDg4%2526blend-x%253D120%2526blend-y%253D467%2526blend-w%253D82%2526blend-h%253D82%2526blend-mode%253Dnormal%2526s%253D9e9cfd2652b6b236dd7e7eb013398aaf%3Fixlib%3Drb-4.0.0%26w%3D1200%26fm%3Djpg%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk2MCZoPTMyNCZ0eHQ9JTVCMjAyMyVFNSVCOSVCNDElRTYlOUMlODglRTclODklODglNUQlRTclQUIlQjYlRTYlOEElODAlRTMlODMlOTclRTMlODMlQUQlRTMlODIlQjAlRTMlODMlQTklRTMlODMlOUYlRTMlODMlQjMlRTMlODIlQjAlRTMlODIlOTIlRTUlQTclOEIlRTMlODIlODElRTMlODElOUYlRTMlODElQjAlRTMlODElOEIlRTMlODIlOEElRTMlODElQUUlRTQlQkElQkElRTMlODElQUIlRTMlODIlQUElRTMlODIlQjklRTMlODIlQjklRTMlODMlQTElRTMlODElQUUlRTUlOTUlOEYlRTklQTElOEMlRTklOUIlODYmdHh0LWFsaWduPWxlZnQlMkN0b3AmdHh0LWNvbG9yPSUyMzFFMjEyMSZ0eHQtZm9udD1IaXJhZ2lubyUyMFNhbnMlMjBXNiZ0eHQtc2l6ZT01NiZ0eHQtcGFkPTAmcz1kOTY3NDdjNDgzZjk4NzAxNDEyOTlkYjA0NGIzYjRmYQ%26mark-x%3D120%26mark-y%3D112%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTgzOCZoPTU4JnR4dD0lNDBrdGF0ZWlzaCZ0eHQtY29sb3I9JTIzMUUyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTM2JnR4dC1wYWQ9MCZzPTQ0NThlNjY4MjljZWM0OGY1NTI5Zjk3NjEyOWExZmVh%26blend-x%3D242%26blend-y%3D480%26blend-w%3D838%26blend-h%3D46%26blend-fit%3Dcrop%26blend-crop%3Dleft%252Cbottom%26blend-mode%3Dnormal%26s%3D57a6fb61ce7d89c7774ac51f4968f006)
みんな、とにかくオセロAIを作るんだ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? オセロAIってなんか難しそう？そんなことはありません。むしろゲームAIを学ぶ様々なレベルの人にこれ以上ないくらい最適です。この記事ではオセロAIを作ると何が良いのかをひたすら語っていきます。そしてオセロAIをこれから作る人のために参考になりそうな記事をいっぱい貼り付けていきます。 私自身はもうかれこれ1年以上オセロAIにどっぷりハマっています。詳細は以前書いた記事で。 オセロAIをおすすめする3つの理由 1. 原始的なゲーム木探索を学べる オセロは「二人零和有限確定完全情報ゲーム」と呼ばれる種類のゲームです。この名称を説明すると、 二人
ランダムを楽しもう / Algorithm with Randomness
本スライドでは、以下の２つの内容を紹介します。 １．乱択アルゴリズム（乱数を使って問題を解くアルゴリズム） ２．ランダムな入力に対するアルゴリズム
はじめに - アルゴリズムとデータ構造大全
はじめに このドキュメントは，主に競技プログラミングで出題される問題を解く際に利用できるアルゴリズムやデータ構造をまとめたものです．特定の問題にはあまりフォーカスしないため，問題を解く際の考察の仕方等の内容はありません．詳しく，正確に，分かりやすく書いていこうと思っています． このドキュメントは執筆途中です． 想定する読者 C++を用いたプログラミングに慣れている方を読者として想定しており，C++言語の仕様や，文法にはあまり触れません．また，計算量という用語についても説明しません．ただし，償却計算量など，計算量の見積もりが複雑なものについては必要に応じて説明します． コードについて このドキュメントで登場するコードは，可読性向上のため，以下のようなコードがファイルの先頭に記述してあることを前提としています．また，適切な問題を用いてコードの検証がなされている場合は，コード周辺にのように，検証
本当にtransactionは必要なのか？ - 急がば回れ、選ぶなら近道
前提 前提ですが。 transaction=Consistency/Isolationを担保する仕組みの話とする。 一般にtransactionが持つべき属性はACIDと言われる。C/Iに比べて、A/Dが“わかりやすい”のでAtomic/Durableの属性の方が人口に膾炙しているが、現在のtransactionではA/Dネタはあまり話題にならない。A/Dネタはローカルだけで見るのであれば普通にfile system /storageの話になる。元来Atomic/Durableはtransactionのコンテクストでは専らlogging / recoveryの話だった。そして、これは非同期のepoch-basedになるとそれ自体の取り扱い優先度が下がる。現代的なtransactionでは、「現時点ではread committedが保証されているFS/storageでA/Dの問題は(ある程度
正規表現が ReDoS 脆弱になる 3 つの経験則
はじめに 皆さんこんにちは．3回生のらん（@ran350jp）です． 文字列マッチングに便利な正規表現ですが，テキトーに書くと脆弱になり得るという情報を耳にしてから色々と原因や対策を調べていました． しかし，多くの記事で紹介されていた対策方法は，「独自の正規表現を使用しないー」とか「 * や + などの繰り返し表現はなるべく使わないー」とかいう なんともふわっとしたものでした．これでは「いやぁ確かにそうなんかもしれんけど…そうゆう訳にはいかんやんか…」と納得できません． つまり，「本質的に何が問題」で，「具体的にどんな特徴のある正規表現が脆弱になり得るのか」を知りたい訳です． そこで，様々な文献を調査してみました．本記事では調査して溜まった知見を紹介していきます． 本記事は， Purdue大学のJames Davis教授による “The Regular Expression Denial
Python言語による実務で使える100+の最適化問題 | opt100
はじめに 本書は，筆者が長年書き溜めた様々な実務的な最適化問題についてまとめたものである． 本書は，Jupyter Laboで記述されたものを自動的に変換したものであり，以下のサポートページで公開している． コードも一部公開しているが，ソースコードを保管した Github 自体はプライベートである． 本を購入した人は，サポートページで公開していないプログラムを 圧縮ファイル でダウンロードすることができる． ダウンロードしたファイルの解凍パスワードは<本に記述>である． 作者のページ My HP 本書のサポートページ Support Page 出版社のページ Pythonによる実務で役立つ最適化問題100+ (1) ―グラフ理論と組合せ最適化への招待― Pythonによる実務で役立つ最適化問題100+ (2) ―割当・施設配置・在庫最適化・巡回セールスマン― Pythonによる実務で役立つ
50分で学ぶアルゴリズム / Algorithms in 50 minutes
本スライドでは、有名なアルゴリズムを概観し、アルゴリズムに興味を持っていただくことを目標にします。 第 1 部：アルゴリズムとは 第 2 部：学年を当ててみよう 第 3 部：代表的なアルゴリズム問題 第 4 部：コンピュータとアルゴリズム
クリエイティブコーディングの教科書
ゲームエンジンや3Dソフトウェアを利用して高度な表現ができるこの時代でも、プリミティブな描画や動き、アルゴリズムから学べることは多い。それらをJavaScriptで書くクリエイティブコーディングという形で学べる手引書が本書となる。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
CS 1332 Data Structures and Algorithms Visualizations
プログラムを動かす時にメモリがどのように割り当て・解放されるのかをめちゃくちゃわかりやすいイメージ画像で解説してくれるサイト「Memory Allocation」
【JavaScript】AtCoder に登録したら次にやること ～これだけ解けば十分闘える！過去問精選 10 問～を解いた感想 - Qiita
