B+木入門：PHPで理解する データベースインデックスの仕組み/b-plus-tree-101
社内用語集を気軽に質問できるSlackBotを作ってみた (RAGの応用アプリ) - ABEJA Tech Blog
こんにちは！株式会社 ABEJA で ABEJA Platform 開発を行っている坂井（GitHub : @Yagami360）です。 LangChain を使用すれば、RAG [Retrieval Augment Generation] を使用した LLM アプリケーションを簡単に作成できるので便利ですよね。 今回 LangChain での RAG を使用して、LLM が学習に使用していない特定ドメインでの用語を応答する Slack ボットをさくっと作ってみたので共有します。 本コード一式は、以下の GitHub レポジトリに保管しています。 github.com 使い方 コード解説 アーキテクチャ RAG の仕組み ヒューマンインザループによる継続的品質改善 まとめ We Are Hiring! 使い方 事前準備として｛用語集スプレッドシートの作成・Slack アプリの初期設定・各種
Dynamic Programming is not Black Magic - Quentin Santos
This year’s Advent of Code has been brutal (compare the stats of 2023 with that of 2022, especially day 1 part 1 vs. day 1 part 2). It included a problem to solve with dynamic programming as soon as day 12, which discouraged some people I know. This specific problem was particularly gnarly for Advent of Code, with multiple special cases to take into account, making it basically intractable if you
入門 B-link tree
概要 DBMS で広く利用されている B+ tree には様々な variant が存在するが、B-link tree もその1つ。 シンプルなラッチプロトコルで並行アクセスをさばけるよう、リーフノード以外のノードにも右の隣接ノードへのポインタを持たせた構造となっており、PostgreSQL で使われていることでも有名。 この記事では主にこの B-link tree に焦点を当てる。 B+ tree 全般やその他インデックス技術自体に興味がある場合は「最強DB講義 #10 いまどきのデータベース索引技術（石川佳治 教授）」の講義資料を読むのがおすすめ。 B-link tree 理解する上で必須な知識「ラッチ」 「ラッチ」というのはいわゆるロックのことだが、DB においては「ロック」というとトランザクション分離のための高価な(数千CPUサイクルを要する)処理を指すことが多く、「ラッチ」という
MySQLのインデックスですが、B-treeではなくB+treeを使用するのはどうしてなのでしょうか？ | mond
MySQLのインデックスですが、B-treeではなくB+treeを使用するのはどうしてなのでしょうか？ 端的に言うと性能が良いからです。 これを理解するにはバッファプールへの理解が必要です。ディスク指向のデータベースの上では有限のメモリを最大限活用することでメモリに入り切らない巨大なデータ群に対して良好な参照性能を出す必要があります。バッファプールとはディスク上のデータの羅列を固定サイズのページ（InnoDBの場合16KB）の羅列であるとして読み書きに必要な分だけをメモリに移し取り複数の書き込みをできる限りメモリ内で受け止めて後でまとめてディスクに書き戻すという、ライトバック型のキャッシュのような機構です。 この中においてバッファプールは有限のサイズしか無いので適宜プール内のデータを書き戻して入れ替えながら上手くやっていく必要があります。 さてB+treeとB-treeの最大の違いは木のリ
spliceを使って高速・省メモリでGzipからZIPを作る - knqyf263's blog
良い話を含むので概要の最初だけでも読んでもらえると幸いです。この話が実用的かと言うと多分全然実用的ではないので理解しても仕方ないかなと言う気がします。 概要 ファイルフォーマット gzip 10-byteのヘッダ 拡張ヘッダ ファイル本体 フッタ（trailer） zip ローカルファイルヘッダ Data descriptor セントラルディレクトリエントリ セントラルディレクトリの終端レコード gzipからzipへの変換 gzipヘッダの処理 gzipファイル本体の処理 gzip trailerの処理 複数gzipファイルの連結 PoC まとめ 概要 先日Dirty PipeというLinuxカーネルの脆弱性が公表されました。 dirtypipe.cm4all.com この脆弱性の原理自体も面白いのですが、その前に報告者の組織で行っているGzipとZIPの処理で引っかかったのでまず先にそち
高速な文字列探索：Daachorseの技術解説 - LegalOn Technologies Engineering Blog
こんにちは。LegalForce Researchで研究員をしている神田 (@kampersanda) です。 LegalForce Researchでは現在、高速なパターンマッチングマシン Daachorse（ダークホース）を開発・運用しています。文字列処理の基礎である複数パターン検索を提供するRust製ライブラリです。以下のレポジトリで公開されています。 github.com 本記事はDaachorseの技術仕様を解説します。具体的には、 複数パターン検索に関係する基礎技術（トライ木・Aho–Corasick法・ダブル配列） Daachorseの実装の工夫と性能 を解説します。 以下のような方を読者として想定します。 文字列処理アルゴリズムやデータ構造に興味のある方 自然言語処理の要素技術に興味のある方 Rustライブラリに興味がある方 Daachorseについて 複数パターン検索の基
コーディングインタビューの対策とその意義 (1/2) - 16bitのメモランダム
１．コーディングインタビューとは何か コーディングインタビュー（Coding Interview、またはProgramming Interview）とは、1時間ほどの制限時間内に小さなプログラミング問題を解かせる面接形式のことをいう。プログラマー、またはデータサイエンティストなどの採用試験として、米国を含むいくつかの国で用いられている。「物理的なホワイトボード上にプログラムを書く」という形式で実施されることが多い。「オンライン上の共有エディタで書く」といった形式のこともある。Googleなどは自社のYoutubeチャンネル動画でも説明している。 出題される問題としては、例えば、「複数の数字numbersと整数kが与えられたとき、合計がkとなる数字の組を1つ出力せよ」といったものがある。この問題は有名なので通称が付いており、Two Sumと呼ばれる。 Two Sumの一例。与えられた数値の並
米不動産テック大手Zillowの大失敗に見るAI経営の教訓…｢予測モデルの過信｣｢目標設定のミス｣は他人事ではありません
こんにちは。パロアルトインサイトCEO・AIビジネスデザイナーの石角友愛です。 2021年最後の寄稿は、｢著名不動産テックの新事業“ZillowOffers”はなぜ大失敗したのか｣を考察します。 Zillowは、不動産情報サイト運営を手がける米国最大の不動産仲介マーケットプレイスです。2006年に創業して以降、米国の不動産情報に関するウェブ検索の約3割はZillowが持つとされ、取り扱う物件数は1億3500万件以上。2020年にはZillowウェブサイトに訪れる毎月のユニークビジター数が3600万人を記録しました（Zillowウェブサイトとアプリに関する統計はこちら）。 Zillowの従来のビジネスモデルは、家を売りたい人と買いたい人を集めるマーケットプレイスでした。主に、その仲介役の不動産エージェントに向けたビジネスモデルを特徴としています。賃貸用の不動産を管理している業者向けにリスティ
Rustで実装するmalloc - NTT Communications Engineers' Blog
この記事は、NTT Communications Advent Calendar 2021 21日目の記事です。 はじめに こんにちは、イノベーションセンターの鈴ヶ嶺(@suzu_3_14159265)です。普段は、クラウド・ハイブリッドクラウド・エッジデバイスなどを利用したAI/MLシステムに関する業務に従事しています。本日は、Rustで動的メモリ確保(dynamic memory allocation)のmallocを実装してPythonやvimを動かしてみようという内容をお届けします。 また、去年もRustネタのアドベントカレンダーを書いているのでぜひ見ていただけると嬉しいです！ NTTコミュニケーションズ Advent Calendar 2020 Rustで実装するNetflow Collector 実装するmallocのアルゴリズム 今回実装するmallocのアルゴリズムは小さな
Python言語による実務で使える100+の最適化問題 | opt100
はじめに 本書は，筆者が長年書き溜めた様々な実務的な最適化問題についてまとめたものである． 本書は，Jupyter Laboで記述されたものを自動的に変換したものであり，以下のサポートページで公開している． コードも一部公開しているが，ソースコードを保管した Github 自体はプライベートである． 本を購入した人は，サポートページで公開していないプログラムを 圧縮ファイル でダウンロードすることができる． ダウンロードしたファイルの解凍パスワードは<本に記述>である． 作者のページ My HP 本書のサポートページ Support Page 出版社のページ Pythonによる実務で役立つ最適化問題100+ (1) ―グラフ理論と組合せ最適化への招待― Pythonによる実務で役立つ最適化問題100+ (2) ―割当・施設配置・在庫最適化・巡回セールスマン― Pythonによる実務で役立つ
ハイパーパラメーター最適化フレームワークOptunaの実装解説 | | AI tech studio
AI Lab AutoMLチームの芝田です (GitHub: @c-bata)。 ハイパーパラメーター最適化は、機械学習モデルがその性能を発揮するために重要なプロセスの1つです。Pythonのハイパーパラメーター最適化ライブラリとして有名な Optuna [1] は、様々な最適化アルゴリズムに対応しつつも、使いやすく設計的にも優れたソフトウェアです。本記事ではOptunaの内部実装についてソフトウェア的な側面を中心に解説します。 Optunaの内部実装を理解するためには、主要コンポーネントの役割と全体の動作の流れを押さえる必要があります。しかしOptunaの開発は活発で、コード量も多くなり、全体の流れをコードから読み取ることは難しくなってきました。そこで今回Minitunaという小さなプログラムを用意しました。Minitunaには全部で3つのversionがあり、それぞれ100行、200行
意思決定の理由の可視化が可能なグラフ構造の学習アルゴリズムの紹介 - ZOZO TECH BLOG
ZOZO研究所の清水です。弊社の社会人ドクター制度を活用しながら、「社内外に蓄積されているデータからビジネスへの活用が可能な知見を獲得するための技術」の研究開発に取り組んでいます。 弊社の社会人ドクター制度に関しては、以下の記事をご覧ください。 technote.zozo.com 私が現在取り組んでいるテーマの1つに、「機械学習が導き出した意思決定の理由の可視化」があります。この分野は「Explainable Artificial Intelligence（XAI）」と呼ばれ、近年注目を集めています。 図．XAIに関連する文献数の推移（引用：https://arxiv.org/abs/1910.10045） その中でも今回はユーザに対するアイテムの推薦問題に焦点を当て、「なぜこのユーザに対して、このアイテムが推薦されたのか？」という推薦理由の可視化が可能なモデルを紹介します。 本記事の概要
50分で学ぶアルゴリズム / Algorithms in 50 minutes
本スライドでは、有名なアルゴリズムを概観し、アルゴリズムに興味を持っていただくことを目標にします。 第 1 部：アルゴリズムとは 第 2 部：学年を当ててみよう 第 3 部：代表的なアルゴリズム問題 第 4 部：コンピュータとアルゴリズム
巡回セールスマン問題(TSP)の基本的な解き方(ILS) | フューチャー技術ブログ
SAIGアルバイトの後藤です。業務では、アルゴリズムの知識を用いた既存処理の高速化やスケジュールの自動作成による業務の効率化を行っています。 配送計画問題など、最適化問題に属する社会課題は、部分問題に巡回セールスマン問題(TSP: Travelling Salesman Problem)を含むことが少なくありません。したがってTSPの基本的なアプローチを知っていることは重要です。TSPは組合せ最適化の代表的な問題として古くから様々なアプローチが試みられており、本記事は専門家の方にとっては既知の内容だと思いますが改めて紹介します。この記事では、2/3-optの焼きなまし法(SA: Simulated Annealing)より良い解法として2/3-optの反復局所探索法(ILS: Iterated Local Search)を紹介します(競技プログラマへ: TSPは焼きなましより山登り + K
アルゴリズムと数学の本を書きました - E869120's Blog
1. はじめに こんにちは、はじめまして。東京大学 1 年生の米田優峻（E869120）と申します。私は競技プログラミングが趣味で、AtCoder や国際情報オリンピックなどの大会に出場しています1。2021 年 11 月時点で、AtCoder では赤色（レッドコーダー）です。また、2020 年以降、アルゴリズムを学べる以下のようなコンテンツや資料を作成してきました。 レッドコーダーが教える、競プロ上達ガイドライン 競プロ典型 90 問 50 分で学ぶアルゴリズム さて、このたびは技術評論社から、書籍を出版させていただくことになりました2。アルゴリズムと数学が同時に学べる新しい入門書です。 「アルゴリズム×数学」が基礎からしっかり身につく本 - amazon 発売日は今年のクリスマス、2021/12/25 です。電子書籍版も同時期に出る予定です。本記事では、この本の内容と想定読者について、
こわくないbit全探索1 入門編: bit全探索ってなに？【競プロ解説】 - Qiita
競技プログラミング（AtCoder）初心者が、最初に突き当たる壁になることが多いアルゴリズムのひとつに『bit全探索』があります。 この記事では、その『bit全探索』についてできる限り丁寧に解説をしていきます。 記事リンク 1. 入門編 bit全探索ってなに？ : bit全探索はどんなことをするアルゴリズムなのか解説します。 2. 基本編1 簡単な例題でbit全探索をやってみよう！ : 簡単な例題（部分和問題）で実際にbit全探索を実装してみます。 3. 基本編2 2進法を使って実装してみよう！ : 2進法を使ったbit全探索の実装をしてみます。 4. 実践編 AtCoderの問題を解いてみよう！ : AtCoderのbit全探索を使う問題のヒントとコード（Python・C++）を載せています。 5. 応用編 3つ以上の選択肢は再帰関数で書こう！ : 再帰関数を使ってbit全探索に似た問題
「998244353 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
1. なぜ 998244353 で割るのか？ 最初はこのような設問を見るとぎょっとしてしまいますが、実はとても自然な問題設定です。 $998244353$ で割らないと、答えの桁数がとてつもなく大きくなってしまうことがあります。このとき以下のような問題が生じます: 多倍長整数がサポートされている言語とされていない言語とで有利不利が生じる 10000 桁にも及ぶような巨大な整数を扱うとなると計算時間が膨大にかかってしまう 1 番目の事情はプログラミングコンテストに特有のものと思えなくもないですが、2 番目の事情は切実です。整数の足し算や掛け算などを実施するとき、桁数があまりにも大きくなると桁数に応じた計算時間がかかってしまいます。実用的にもそのような巨大な整数を扱うときは、いくつかの素数で割ったあまりを計算しておいて、最後に中国剰余定理を適用して復元することも多いです。 なぜ 9982443
桁DPの痒いところに手が届く解説 - Qiita
はじめに 本記事は、アルゴリズムの一つである桁DPについて、入門者が疑問に感じる（というか筆者が実際疑問に感じた）ポイントに重点を置いて解説するものです。 筆者自身そこまで桁DPに詳しいわけではなく、むしろ最近覚えたぐらいなので、何かまずい部分があれば優しくご指摘いただけると嬉しいです。 この記事で特に重点を置くポイントは、次の通りです。 何故これでうまくいくのか 桁DPで数えているものは何か 初期条件はなぜこうなるのか 桁DPそのものの入門的解説としては、他にもけんちょんさん達の優れた記事がありますので、そちらも合わせてご覧ください。 http://torus711.hatenablog.com/entry/20150423/1429794075 http://drken1215.hatenablog.com/entry/2019/02/04/013700 https://pekempe
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
近似最近傍探索の最前線
