Alias method - Wikipedia
A diagram of an alias table that represents the probability distribution〈0.25, 0.3, 0.1, 0.2, 0.15〉 In computing, the alias method is a family of efficient algorithms for sampling from a discrete probability distribution, published in 1974 by Alastair J. Walker.[1][2] That is, it returns integer values 1 ≤ i ≤ n according to some arbitrary discrete probability distribution pi. The algorithms typic
Walker's Alias Methodの箱の作り方のわかりやすい説明 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに 指定された重みに従って離散的な値を確率的に選択したい、ということがよくある。例えば[1,4,5]という配列が与えられた時、確率10%で0、40%で1、50%で2というインデックスを返すような関数が欲しい。 普通に考えると部分和をとって乱数を一度振り、どの場所が選択されたか二分探索で調べる、というアルゴリズムが思いつくが、これは要素数Nに対して$O(\log(N))$の手間がかかる。logの手間というのは無視できることが多いが、この関数呼び出しが頻繁にある場合には無視できないコストになる。 さて、こんな用途のためにWalker'
find + mkdir はチューリング完全 - Qiita
英語版 (English version) 更新履歴 2024-08-02 初版に存在した証明のミスを修正しました。初版では Rule 110 を実装することでチューリング完全性を示したと主張していましたが、状態の幅が固定になってしまっているという問題がありました。現在のバージョンでは、Rule 110 でなく Tag system を実装し、問題を解消できていると思います 概要 GNU の find と mkdir コマンドのみを使えるシステムはチューリング完全であることを示します。 sed や awk コマンドが単体でチューリング完全であることはよく知られていますが、find + mkdir がチューリング完全になるという言及は探した限りでは見つからなかったので、ここに報告します。 証明は、タグシステム を実装することによって行います。 完成形のコードは下の方にありますが、順を追って、
燃やす埋める問題とProject Selection Problemの整理 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 2021年3月から毎日問題が公開されている「競プロ典型90問」、皆さま解いていらっしゃいますでしょうか？ 一昨日、第40問として公開された「Get More Money」が解説を読み、その後いろいろな記事を見ても理解が難しかったので整理してみました。 当然のことながらこの問題の解法に触れますので、問題に挑戦したい方はこの記事は後からお読みいただくことをお勧めします。 AtCoder常設ジャッジ 問題画像 公式解説 何が理解できなかったのか 公式解説にもある通り、この問題はいわゆる「燃やす埋める問題」というタイプの問題です。公式解説は紙面
この木なんの木？ モンテカルロ木と最良優先MiniMax木の"間"に存在する名もなき木々 - ヴァルの開発記
概要 この記事ではまだ名前が無いと思われるゲーム探索木をいくつか紹介します。この記事では具体的な実装は示さず、概念の紹介にとどめます。 この記事を読むために必要な知識は以下です。 ・モンテカルロ木探索＋UCB1 ・MiniMax探索 ・ボンバーマンの基本的なルール 名のある木々 名もなき木々を紹介する前に、まずは名のある木々を紹介します。 MCTS モンテカルロ木探索。簡単に言えば、評価関数を使わず、ランダム試行を繰り返して勝率の平均が高い手を調べる手法です。 有名な木なので、検索するとたくさん解説がヒットするのでこの記事では説明を割愛します。 一応参考として、私が初めてMCTSを実装したときに参考にした論文を載せておきます。 →A Survey of Monte Carlo Tree Search Methods 最良優先MiniMax 最良優先MiniMax探索についてはこちらの論文が
IEEE浮動小数点数における平方根演算の精度に関する覚書 - よーる
IEEE浮動小数点数における演算では、丸め誤差が不可避です。特に、複数回の演算を繰り返すと丸め誤差が積もっていき、正確な値と大きく離れた答えを得てしまうことがあります。しかし、次の演算については、（数学的に）正確な値を求めた後、一回だけの丸めが発生することが、IEEE標準で規定されています。 四則演算 積和演算 Fused multiply add (FMA) 平方根演算（正の平方根を求める*1） 浮動小数点数演算のできるCPUであれば、普通、四則演算や積和演算を行う命令を持っています。 しかし、平方根を正確に計算する命令を持たない命令セットも存在します。 そのような場合、平方根関数はライブラリ実装となるわけですが、どのように実装すれば要求を満たせるのでしょうか？ C++のstd::sqrtは正確に計算しているのか？ 結論 しています。 標準の丸めモード、つまり最近接丸め（ぴったり半分なら
Potato paradox - Wikipedia
For the economic effect sometimes called the potato effect or potato paradox, see Giffen good. This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Potato paradox" – news · newspapers · books · scholar · JSTOR (January 2021) (Learn how and when to remove t
How to shuffle songs? - Spotify Engineering
At Spotify we take user feedback seriously. We noticed some users complaining about our shuffling algorithm playing a few songs from the same artist right after each other. The users were asking \”Why isn\’t your shuffling random?\”. We responded \”Hey! Our shuffling is random!\” So who was right? As it turns out, both we and the users were right but it\’s a bit more complicated than that. It also
転置インデックスの圧縮技法
転置インデックスは、検索エンジンの実装において、中心的な役割を果たすデータ構造である。 転置インデックスのデータ構造とアルゴリズムは、クエリ処理アルゴリズムとともに、検索エンジンの性能に直結する。とくに大規模な検索エンジンにおいては、キャッシュ効率を高めてクエリ処理を高速化するために、転置インデックスの圧縮は必要不可欠となっている。 この記事では、転置インデックス、とくにポスティングリストの圧縮について、近年の手法を簡単にまとめる。 目次 転置インデックスの基本 転置インデックスのデータ構造と特性 転置インデックスのアクセスパターン 近年のインデックス圧縮技法 Variable-Byte Family VByte Varint-GB Varint-G8IU Masked-VByte Stream-VByte Opt-VByte Simple Family Simple9 Simple16
地球の自転が高速化して｢負のうるう秒｣が来そう。Google、Amazon、Metaは猛反対
地球の自転が高速化して｢負のうるう秒｣が来そう。Google、Amazon、Metaは猛反対2022.08.03 23:0066,023 satomi なんせ1秒減らす｢負のうるう年｣は初めて。やれる気がしません。 年末カウントダウンで午前零時を2回カウントすることで1秒加え、自転速度と協定世界時（UTC）の誤差を埋めてきた｢うるう秒｣に異変が生じ、地球自転が高速化に一転。午前零時をスキップして1秒引く調整が叫ばれるなか、｢1秒足すだけでも世界中のシステムがパニックだったのに、1秒引いたらどうなっちゃうの⁉｣という不安がIT業界に広まり、Google、Amazonに次いでMeta（メタ、旧Facebook）も｢うるう秒やめようぜ｣と言い出しています。 うるう秒は1972年以降27回行なわれていますが、地球の自転スピードが遅くなるのに合わせて毎回1秒ずつ足すのが常でした。マイナスにすると、プ
高速なビームサーチが欲しい!!! - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? この記事はアルゴリズム強化月間の一環として書かれた記事です。 はじめに こんにちは！ rhooというアカウント名で競技プログラミングをやっている者です。 半年ほど前からヒューリスティック系のコンテストにも手を出し始めました。 この記事では私がゲーム実況者xの挑戦という過去問を解くときに使った手法の解説記事となります。 要約 ビームサーチの状態の管理を差分を持った木構造で管理するとコピーコストが発生しなくなり高速になります。 前提知識 ビームサーチについての基礎的な知識と参照カウントベースのスマートポインタ(c++でのshared_ptr
メルカリを退職してロンドンのMetaに転職します 〜 外資Big Tech転職活動体験記｜松岡玲音｜note
この度、3年半に渡って勤めたメルカリを2022年5月に退職し、この夏からロンドンのMetaにSenior Machine Learning Engineerとして転職することが決まりました！わいわい✌('ω')。その過程で、東京およびロンドンのBig Tech合計5社を数ヶ月かけて対策をし面接に臨んだので、そこで得たノウハウをここで共有できたらと思います。面接を受ける際にNDA（Non Disclosure Agreement）にサインするので具体的な面接の詳細には触れられませんが、伝えられる範囲でできる限り記述しています。 また、Metaから最終的に提示されたオファー条件を最後に記載してあります。なにぶん日本においては給与の話は燃えやすいということもあり、その部分だけ某日本の有名エンジニアに倣って有料にしてあるのですが、ご興味のある方は是非ご購入いただければと思います（1コイン分の金額で
みんな、とにかくオセロ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. 原始的なゲーム木探索を学べる オセロは「二人零和有限確定完全情報ゲーム」と呼ばれる種類のゲームです。この名称を説明すると、 二人
周波数分析からみた近年の耐久財消費の動向
2017年1月 日本銀行調査統計局 東 将人 河田 皓史 本稿の内容について、商用目的で転載・複製を行う場合は、予め日本銀行調査統計局ま でご相談ください。 転載・複製を行う場合は、出所を明記してください。 周波数分析からみた近年の耐久財消費の動向 1 2017 年 1 月 日本銀行調査統計局 東 将人* 河田 皓史† 周波数分析からみた近年の耐久財消費の動向‡ ■要 旨■ 個人消費は、2014 年 4 月の消費税率引き上げ以降、全体として底堅さを維持 しているものの、力強さに欠ける状態が長引いてきた。これには、様々な要因 が指摘されてきたが、本稿では、2009 年以降の耐久財消費を促進する各種の政 策や消費税率の引き上げに伴う駆け込み購入など、耐久消費財の買替えを促進 する政策や制度の影響に注目した。 本稿では、 「周波数分析」を用いて、耐久財消費を買替えサイクルに基づく複 数の周期変動
中日新聞:自動車工場のガロア体 ＱＲコードはどう動くか
その誕生を地元新聞も経済新聞も記事にしなかった。２年後、『コードの情報を白黒の点の組み合わせに置き換える』と最下段のベタ記事で初めて紹介された時、その形を思い浮かべることができる読者はいなかった。いま、説明の必要すらない。ＱＲコードはなぜ開発され、どう動くのだろうか。 ＱＲコードは、自動車生産ラインの切実な要請と非自動車部門の技術者の「世界標準の発明をしたい」という野心の微妙な混交の下、1990年代前半の日本電装（現デンソー）で開発された。 トヨタグループの生産現場では、部品名と数量の記された物理的なカンバンが発注書、納品書として行き来することで在庫を管理する。そのデータ入力を自動化するバーコード（ＮＤコード）を開発したのがデンソーだ。 バブル全盛の1990年ごろ、空前の生産台数、多様な車種・オプションに応えるため、部品も納入業者も急激に増え、ＮＤコードが限界を迎えていた。63桁の数字しか
ビームスタックサーチ（Beam-Stack Search）の解説 - Qiita
はじめに ビームサーチ（Beam Search）は貪欲法の高速性と全探索の正確性にトレードオフを持たせたヒューリスティック探索手法としてよく知られています。主に文章生成や機械翻訳の分野で活躍している他、私の所属する競技プログラミングの界隈においてもヒューリスティック系コンテストでよく利用されます。一方で、探索アルゴリズムの研究分野においては、ビームサーチの探索方法を変換してより高性能な探索アルゴリズムを生み出そうとする動きも見られます。本記事では、ビームサーチを変換したアルゴリズムの1つであるビームスタックサーチ（Beam-Stack Search）を解説します。ビームスタックサーチとは何者かを簡単に言うとビームサーチを最適解の発見を保証できる形に変換したものと言えます。以下では、まずビームサーチの提案論文を紹介し、当論文を読んでの私見を述べ、最後にビームスタックサーチのアルゴリズムを解説
Xorshift を用いた Zobrist hashing を衝突させる方法 - noshi91のメモ
概要 Xorshift によって生成された乱数列について、いくつかの場所の xor を取ると seed に依存せずに になる。 Xorshift Xorshift - Wikipedia 説明は Wikipedia に丸投げする。 本記事では簡略化のため、実装例の一番上にある周期 の実装について議論する。 Zobrist hashing 個の要素があるとして、要素 に乱数 を割り当てる。 このとき、集合 の hash を で定める。 ただし は bitwise xor とする。 この hashing の方法を Zobrist hashing と呼ぶ。 hash の衝突 異なる集合 について となることを衝突と呼ぶ。 Zobrist hashing の場合 であるから、 かつ となるような が分かれば衝突を引き起こすことができる。 結論から言うと、 を Xorshift が 番目に出力した値
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
構造を持った言語データと最適輸送
Home — Memory Management Reference 4.0 documentation
円周率.jp - FFT と乗算