高速な文字列探索：Daachorseの技術解説 - LegalOn Technologies Engineering Blog
こんにちは。LegalForce Researchで研究員をしている神田 (@kampersanda) です。 LegalForce Researchでは現在、高速なパターンマッチングマシン Daachorse（ダークホース）を開発・運用しています。文字列処理の基礎である複数パターン検索を提供するRust製ライブラリです。以下のレポジトリで公開されています。 github.com 本記事はDaachorseの技術仕様を解説します。具体的には、 複数パターン検索に関係する基礎技術（トライ木・Aho–Corasick法・ダブル配列） Daachorseの実装の工夫と性能 を解説します。 以下のような方を読者として想定します。 文字列処理アルゴリズムやデータ構造に興味のある方 自然言語処理の要素技術に興味のある方 Rustライブラリに興味がある方 Daachorseについて 複数パターン検索の基
オセロAI世界1位になってオセロAIをｶﾝｾﾞﾝﾆﾘｶｲｼﾀ話 - Qiita
オセロAIを作り始めた日のこと あれは2021年4月のこと、今思い返せば偶然が重なって起きた出来事でした。 第一の偶然は、ゲームAI(ゲームを自動プレイするAI)世界4連覇の方になぜかゲームAIの初歩的な話を30分程度教わっていたことです。 第二の偶然は、Twitterの知り合いが「オセロソフトRTA」なる競技をやっているのを目にしたことです。なんじゃそりゃ、と思った私はすぐに、その競技が 「オセロで遊ぶプラットフォームをどれだけ早く作るか」を競うものだとわかりました。 面白い、やってみよう。 YouTubeでライブ配信しながら、私はオセロソフトRTAをやってみました。その時のライブはこちら。3時間で完成できれば良いと思っていたのですが、思ったよりも早く終わってしまいました。 オセロAIでも作るか。 こうして私のオセロAI制作が開始しました。 何をしたら良いかわからなかった オセロAIを作
ハッシュ関数「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
atoi関数のかしこい実装 - yohhoyの日記
C標準ライブラリ Muslのatoi関数実装 では、符号付き整数オーバーフロー回避のため負数範囲で10進数値を減算してゆき最後に符号反転を行っている。 int atoi(const char *s) { int n=0, neg=0; while (isspace(*s)) s++; switch (*s) { case '-': neg=1; case '+': s++; } /* Compute n as a negative number to avoid overflow on INT_MIN */ while (isdigit(*s)) n = 10 * n - (*s++ - '0'); return neg ? n : -n; } C言語の符号付き整数型(int)では “2の補数” 表現が用いられるため*1、最大値INT_MAXより最小値INT_MINの絶対値が 1 だけ大き
アルゴリズムの世界地図 - Qiita
こんにちは、square1001 です。 現在は東京大学の学部 1 年生をしています。私は中学 1 年の頃からプログラミングをやっていて、特にアルゴリズムが大好きです。AtCoder をはじめとする 競技プログラミング にも取り組んでいて、中高生のときは 情報オリンピック にも参加していました。 本記事では、アルゴリズムや競技プログラミングに興味がある方、あるいはプログラミングをやっているけどアルゴリズムをよく知らない方に アルゴリズムはどんなもので アルゴリズムを使うとどんな問題が解けて アルゴリズムが地球のように広く、多様で、奥深く、そして楽しいこと を知ってもらおうと思っています。 アルゴリズムの世界へようこそ 時代は 2020 年代に突入し、急速に IT 化 や DX が進んでいく中で、問題を効率的に解くアルゴリズム技術の重要性が、ますます高まっています。そして、アルゴリズムは、世
1次元ランダムウォーク - ei1333の日記
初心者向け 1 次元ランダムウォーク 数直線があって、原点 に点 がある。 時刻が 進むごとに、点 の位置が確率 で 、確率 で 動く。 この確率モデルを (対称な) 次元ランダムウォークと呼ぶ。 パスの個数 横軸を時間軸、縦軸を点 の位置を表すこととすると、以下のような折れ線グラフで表すことができる。 を、原点から点 までのパスの個数（言い換えると、時刻 に位置 に至る経路数）とする。 と から、ランダムウォークで した回数 と した回数 をそれぞれ計算できる。 より、 となる。("45度回転"に相当する) したがって と の偶奇が一致しているとき と二項係数を用いて表せる。 auto L = [&](int t, int x) -> modint { if(t % 2 != abs(x) % 2) { return 0; } else { return beet.C(t, (t + x
Git を永続データ構造として見る - koyumeishiのブログ
競技プログラミングは役に立つ、 というかアルゴリズムとデータ構造は身の回りで役に立ってるよ案件なんですが、 バージョン管理システム Git のコア部分の仕組みは永続データ構造です。 ブラックボックスとして使うより簡単な仕組みを知ってる方が 親しみやすいと思うので雑に解説します。 "git データ構造" とかでググると同様の話結構出てくる N 番煎じです (というか公式ドキュメントに書いてあるまんまのことを競プロer的に見るとこうなっているよという話。 Git の使い方を解説する記事ではありませんし、まして GitHub は何の関係ありません)。 ソースコードや公式ドキュメントを読み込んだわけじゃないのでテキトーなことが書かれているかもしれません。 公式ドキュメントを読んでください。 ざっくり "commit" は登録したファイルを含むディレクトリツリーのスナップショットを保存している "c
50分で学ぶアルゴリズム / Algorithms in 50 minutes
本スライドでは、有名なアルゴリズムを概観し、アルゴリズムに興味を持っていただくことを目標にします。 第 1 部：アルゴリズムとは 第 2 部：学年を当ててみよう 第 3 部：代表的なアルゴリズム問題 第 4 部：コンピュータとアルゴリズム
人間には簡単だが機械には苦手なこと、その力を育むものこそ「数学」だ
＜どれだけ科学が進歩しても機械が苦手とし、いまだ人間にかなわずにいる能力こそ、数学によって育まれる「抽象性」の力だった＞ 数学とは、見えないものを見ようとする試みである。大切であるけれども理解できないことをなんとかして理解しようとする試みである――これは、『見えないときに、見る力。 視点が変わる打開の思考法』（CCCメディアハウス）の、著者・谷川祐基氏の言葉だ。 前著『賢さをつくる 頭はよくなる。よくなりたければ。』（CCCメディアハウス）が好評の谷川氏によると「数学を学ぶ目的は抽象性を育てること」である。新刊『見えないときに、見る力。』では、「数学は問題解決能力である」とか「数学は論理的思考力を養う」といった、よく言われる数学という教科の存在意義に対して、新たな見解を投げかけた。 ではなぜ、抽象性を育てることがそんなに大事なのか？ それは、この現実社会を生きていくうえで、ときに抽象性は論
d.y.d.
22:43 21/11/09 ヒープソートが好きである ranha さんが、 Approaching Heapsort via Lazy Mergesort という記事を公開していらして、 遅延評価の言語で書くマージソートの計算過程で何が起きているかを見ていくと、 だんだんヒープソートが見えてきた…！という大変面白い記事なのですが、 その話の枕に「稲葉さんというヒープソート大好き人間がいるがいったいどこが良いのか」 という形で私が登場していたので、 思わず何故私がヒープソートが好きであるかをしたためた長文をTwitterのDMで ranhaさんに送りつけてしまいましたという経緯があります。 元ネタの @pi8027 さんの発表 が公になったのに合わせてranhaさんの記事も公開されたみたいなので、 自分の脳内出力もついでにここに書き留めておこうかと思いました。 お二方のように技術的にしっか
ヒューリスティックコンテスト(マラソン)、ゲームAIコンテストで使う武器まとめ｜にゃにゃん(山名琢翔)
ものづくりとプログラミングとルービックキューブが大好きなにゃにゃんです。今回は競技プログラミングに関する内容です。 この記事の執筆時点ではもうすぐAHC002というヒューリスティックコンテストが開かれます。 これに向けて過去問を解いて準備をしていて、ヒューリスティックコンテストやゲームAIコンテスト(基本的にまとめて「ヒューリスティックコンテスト」と言うことにします)における様々な武器やTIPSがわかってきました。それを自分のメモも兼ねてまとめます。なお、深さ優先探索や幅優先探索など、アルゴリズムコンテストでもよく出てくるアルゴリズムについては省きました。ただでさえ記事の文字数が結構多くなってしまったので… この記事は私が今後精進していく中で新たな発見があったら随時追記していこうと思います。 ヒューリスティックコンテストとは ヒューリスティックコンテストは、ある問題が与えられて、それに対す
リトルの法則-待ち時間の推定－この行列は、あと何分、待たなくてはならないのか?
人気のあるものには、すぐに行列ができる。遊園地のアトラクション、有名なレストラン、駅の窓口、病院の受付、…と、至るところで行列ができる。ワクワクするような楽しいことを待つために、行列に並ぶのは、大して苦痛ではない。しかし、嫌なことを待つときや、急いでいるとき、待つ環境が厳しいときなどには、大変な苦しさを味わうこともある。 行列に並んでいると、誰もが考えるのは、「あと何分、待たなくてはならないのか?」ということだろう。待ち時間を知りたいという思いは、行列を待つ人に、つきものと言える。特に、待つことが苦痛に感じられる場合には、イライラ感も手伝って、その思いが強くなる。 行列の長さが比較的短ければ、待ち時間の推定はしやすい。例えば、ある駅の窓口で、自分の前に10人が並んでいて、1分間で1人ずつ窓口で用を済ませているとしよう。この場合は、待ち時間は10分と推定できる。ただし、窓口で1人にかかる時間
最小二乗法の学びなおし - Qiita
はじめに 今回は、私がツイログから最近掘り出してきて、勉強している黒木玄さんの最小二乗法についてのノートブックを紹介したいと思います。紹介といっても、私がこのノートブックを理解するのに使ったものを紹介するというほうが正しいですが、、、 線形代数をきちんと勉強している方は、黒木玄さんのノートブックだけで理解できるのだと思います（羨ましい）。数学的な解釈や間違い等あればお手数ですがどなたか指摘していただければと思います。 引用だけでは、私が記事を書く意味がないので最尤推定について少し触れておきます。最尤推定の特別な場合が最小二乗法にあたるということを簡単にですが示したいと思います。 最小二乗法は直交射影の言い換え 黒木玄さんの書いた丁寧な説明とJuliaの実装が以下から見れます。まずはこちらをご覧ください。今回触れるのは直交射影ですが、是非続きも読んでみてください。 こちらの画像は直交射影の説
数理最適化による問題解決の実践的なアプローチ
本稿はRAMP数理最適化シンポジウム(2020/10/26)の講演の一部をまとめたものです．研究者に向けた講演内容ですが，数理最適化を活用したいエンジニアやコンサルタントの皆様の参考になれば幸いです．また，数理最適化に関わらず，研究者との共同研究を検討している方も一読いただけると役に立つかも知れません． はじめに 数理最適化は現実社会における意思決定や問題解決を実現するための有用な手段です．数理最適化は，下図に示すように，(1)最適化問題のモデリング，(2)アルゴリズムによる求解，(3)結果の分析・検証，(4)最適化問題とアルゴリズムの再検討という一連の手続きからなります． 数理最適化を用いて現実問題を解決するためには，まず，代表的な最適化問題とそれらに対する効率的なアルゴリズムを良く知ることが必要です．しかし，数理最適化の理論やアルゴリズムの専門的な知識があれば，それだけで現実問題を上手
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
画力・博士号・油田 on Twitter: "まあまあスライドができてきております（まだまだ調整が必要） https://t.co/kPaOH518s3"
書泉グランデMATH【営業時間11時～20時】 on Twitter: "1月中旬新刊予定 『計算科学講座 20世紀のトップ10アルゴリズム 』 監修：金田 行雄/笹井 理生 編集：張 紹良（共立出版） 10個のアルゴリズムそれぞれの代表的な研究者に執筆を依頼し，その黎明から今日までの発展の歴史や理論の… https://t.co/6jrksJ2ajd"
™ on Twitter: "クイックソートの実装で，データを 1:1 に分けるのを目指すより 1:4 みたいに偏らせたほうが *分岐予測ミスが減るので* 早い，という話を聞いた（まじか）"
あるエンジニアの面接で、ソートについて聞かれたら
Ryo Suzuki on Twitter: "話題の「なぜかソートできる」ソートアルゴリズムを Siv3D でアニメーションにした。 https://t.co/qYmiVIdDsj https://t.co/liNSgo1XL9"
千葉の高専生、ハッカソンで最優秀賞 「量子コンピューターでお手軽機械学習」とは：朝日新聞GLOBE＋
