タグ

algorithmに関するkazutanakaのブックマーク (149)

  • 【#も読】n月刊ラムダノート、実用Raft(@yusuktan)

    「あの人も読んでる」略して「も読」。さまざまな寄稿者が最近気になった情報や話題をシェアする企画です。他のテックな人たちがどんな情報を追っているのか、ちょっと覗いてみませんか? みなさんこんにちは。 この度「あの人も読んでる」に寄稿させていただくことになったmaguro (X @yusuktan)です。 僕が読んで面白かった、記事、動画などのコンテンツを定期的にご紹介していければと思います。よろしくお願いします。 今回紹介するコンテンツ記念すべき第1回目にぜひ紹介したいのが、2025年3月1日に発売されたばかりのラムダノート社「n月刊ラムダノート Vol.5, No.1(2025)」です。ラムダノート社が不定期で発行している技術解説情報誌で、今号は以下の3の記事が掲載されています。 自然数を作って学ぶLean言語(井上亜星 著) Chromiumはテキストをどのように描画しているのか(佐

    【#も読】n月刊ラムダノート、実用Raft(@yusuktan)
  • malloc.c を読む (malloc / free)

    このシリーズではこれらの関数が内部でどのように処理されるのかを調べていきます。 malloc.c を読む (malloc / free) malloc.c を読む (bins) malloc.c を読む (arena) 今回は malloc() free() の全体像を紹介します。 注意としてここでの目的は全体を俯瞰して、詳細を詰めずとも各 bins の役割を理解し、攻撃手法を理解できるようにすることです。それに合わないマルチスレッドや最適化などにおける緻密なトリックやコーナーケースなどは暗黙的に実装されていると仮定します。その詳細についてはソースコードや他の資料を参考にしていただきたいです。 ここで扱う glibc のバージョンは v2.38 です。また glibc のソースコードはブラウザ上で読むことができます。 https://elixir.bootlin.com/glibc/lat

    malloc.c を読む (malloc / free)
  • Why UUID7 is better than UUID4 as clustered index in RDBMS

    In the Introduction To Database Indexing Article, We discussed database indexes, Their type, representations, and use cases. In this article, we will experiment to check which performs better as a clustered index. UUID version 4 vs UUID version 7 or 6. Then we will discuss why that happened. What is UUID version 4?UUID, an acronym for Universally Unique Identifier, is a 128-bit identifier represen

    Why UUID7 is better than UUID4 as clustered index in RDBMS
  • Othello is Solved 論文解説 (私見) - Qiita

    Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 今朝起きたら、とんでもない論文を見つけました。 Othello is Solved ゲームの オセロが"解かれた(弱解決)" というのです。飛び起きました。それで、16時まで二度寝してから読みました。 注意すべきは、この論文が査読を経て公開されているわけではないこと、つまり形式上特にチェックを受けたものではないことです。ただ、タイトルからして非常に衝撃的ですので、個人的に読んでみました。この記事では、私がこの論文(およびソースコード)を読んでわかったことを、なるべくわかりやすくまとめます。随時更新します。 余談ですが、このタイトルはどう

    Othello is Solved 論文解説 (私見) - Qiita
  • 徐々に高度になるリングバッファの話 - Software Transactional Memo

    リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit

    徐々に高度になるリングバッファの話 - Software Transactional Memo
  • Algorithm Design with Haskellでアルゴリズムを学ぶ - 朝日ネット 技術者ブログ

    はじめに 開発部のcbmkageです。 仕事でプログラムを書いていると、どうしたら期待通りに、かつ高速に動作するアルゴリズムが実装できるか、考えることがあります。 記事では、アルゴリズムについて新たな視点を与えてくれる「Algorithm Design with Haskell」を紹介します。 記事はHaskell中級者向けです。Haskellの文法や、代表的なリスト操作関数を知っていることを前提としています。 はじめに Algorithm Design with Haskellとは 準備: 関数の同値関係 貪欲アルゴリズムのPART紹介 貪欲アルゴリズムとは 候補の生成と選択 貪欲アルゴリズムへの改善 まとめ 採用情報 Algorithm Design with Haskellとは Algorithm Design with Haskell 作者:Bird, Richard,Gib

    Algorithm Design with Haskellでアルゴリズムを学ぶ - 朝日ネット 技術者ブログ
  • 試し割りによる素数列挙はエラトステネスの篩か? - Qiita

    背景 前回の記事 IchigoJamでエラトステネスの篩 - Qiita を受け、ツイート主さんから以下のページのURLが送られてきました。 エラトステネスの篩 [WildTree Wiki] 見ると、それぞれの奇数$T$について、$\sqrt{T}$以下の素数で割っていき、 全て割り切れなければ$T$は素数であると判定するアルゴリズムを使っているようです。 一方、エラトステネスの篩といえば、 確定した最小の素数の倍数を候補から外し、確定していない中で最小の候補を素数として確定させる、 という処理を繰り返すことで、効率よく素数のリストを求めることができるアルゴリズムのはずです。 今回送られたページにあるような、1個ずつ試し割りを行うアルゴリズムは、 果たしてエラトステネスの篩といえるのでしょうか? そこで、試し割りと一般的なエラトステネスの篩の時間コストを比較してみることにしました。 今回

    試し割りによる素数列挙はエラトステネスの篩か? - Qiita
  • 世界四連覇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エンジニアがゼロから教えるゲーム木探索入門 - Qiita
  • リアルタイム共同編集のアルゴリズム (Operational Transformation; OT) を理解する試み – RORO

    Google Docsのように文書を複数人でリアルタイムに共同編集できるアプリケーションがあります。あのような機能は、多かれ少なかれ、Operational Transformation (OT; 操作変換) という考え方を使って実現されているようです。興味があったので、このOTについて調べてみました。 (追記: これからは OT でなく CRDT だという話 → I was wrong. CRDTs are the future) なおGoogle Docsではいわゆる「リッチテキスト」を共同編集できますが、ここでは話を簡単にするために「プレーンテキスト」を共同編集することを想定します。 リアルタイム共同編集の流れ 共同編集システムの登場人物は次の通りです: サーバ x 1(各クライアントから届く編集操作をもとに、最新の文書を保持します) クライアント x N(文書を編集する側です) そ

  • Constraint Propagation and Backtracking-based Search

  • 情報基礎特論: 制約プログラミング入門

    CSP Cream Sugar Copris : 2011 6 6 2011 8 22 2012 6 24 2014 5 19 : CSP Cream Sugar Copris 1 2 3 Cream Java OpenOffice.org Calc 4 Sugar SAT Scala : CSP Cream Sugar Copris : CSP Cream Sugar Copris (CSP) (CSP; Constraint Satisfaction Problem) (X, D, C) X: (variable) D: x ∈ X (domain) ( : D(x) = {1, 2, 3}) D(x) C: X (constraint) X v x v(x) ∈ D(x) v (assignment) v C (satisfy) CSP (satisfiable) v (unsatisfia

  • M-Coloring Problem - GeeksforGeeks

  • クックパッドマートの配送ルートを自動生成している仕組み - クックパッド開発者ブログ

    こんにちは、クックパッドマート流通基盤アプリケーション開発グループのオサ(@s_osa_)です。 生鮮品の EC サービスであるクックパッドマートでは、「1品から送料無料」をはじめとするサービスの特徴を実現するために、商品の流通網を自分たちでつくっています。 このエントリでは、商品をユーザーに届けるための配送ルートを自動生成している仕組みについて紹介します。 解決したい問題 配送ルートとは クックパッドマートにはいくつかの流通方法がありますが、ここでは「ステーション便」と呼ばれるものについて解説します。他の流通方法などを含む全体像が気になる方は以下のエントリがオススメです。 クックパッド生鮮 EC お届けの裏側 2022 年版 - クックパッド開発者ブログ ステーション便では、ハブと呼ばれる流通拠点からユーザーが商品を受け取りに行く場所であるステーションへと商品を運びます。東京都、神奈川

    クックパッドマートの配送ルートを自動生成している仕組み - クックパッド開発者ブログ
  • しっかり学ぶ数理最適化 ヒューリスティック編 - Qiita

    これはどんな記事? 記事は、私がヒューリスティック関連の知識をまとめることになった際に作成したJupyter Notebookを、Qiitaの記事へと改変したものです。 前提としてこれは梅谷俊治先生の「しっかり学ぶ数理最適化 モデルからアルゴリズムまで」という(以下、教科書と表記)の内容に準拠しています。 そしてその内容の多くは、ありがたいことにネット上の様々な形で公開されており、梅谷先生によるスライド1やスライド2、日オペレーションズ・リサーチ学会(以下、ORと表記)での記事1や記事2、そしてORの他の方の記事1や記事2などでも類似した内容を見ることが可能です。 (そしてそれ故に、記事を公開させて頂いています。流石に家の方がネット上で公開されていない内容を書くのは、例え権利的に問題がないとしても気が引けるので……) また、この記事は、それらの内容を踏まえた上で、私がネット上の様

    しっかり学ぶ数理最適化 ヒューリスティック編 - Qiita
  • 数理最適化ことはじめ / Introduction to Mathematical Optimization

    スライドでは、数理最適化を概観し、基的な問題とその解き方を分かりやすく解説することを目標にしています。数理最適化に興味を持っていただければ嬉しいです。 【目次】 1 章 数理最適化とは(p.2~20) 2 章 連続最適化問題(p.21~133) 3 章 離散最適化問題(p.134~238…

    数理最適化ことはじめ / Introduction to Mathematical Optimization
  • 「ぷよぷよは計算困難」―パズル・ゲームと最適化アルゴリズム― – Ono Laboratory

    はじめに 最近,「一般化ぷよぷよのより強い計算困難性」なる研究を発表しました(東北大学の江藤宏先生,九州大学の木谷裕紀先生との共同研究.国内研究会であるゲームプログラミングワークショップで江藤先生による口頭発表.2021年12月30日現在,pdfはここから取れます). これは有名なビデオゲーム「ぷよぷよ」を一人用のパズルと見立てたとき,かつそれを一般化した場合,どの程度難しいものであるのかを(最適化)アルゴリズム論的に分析したものです.今回「最適化技術の応用・実践」に関する記事を集めよう,ということになりましたので,ちょうどよい題材ということで,この研究をより一般向けに解説してみようと思います.一般向けですので証明自体には踏み込まず,既存の定理と得られた定理の意義をおよそわかっていただくことをこの記事の目標とします.ただし「ぷよぷよ」について関してはおよそルール等がわかっている方を対象とし

  • Python言語による実務で使える100+の最適化問題 | opt100

    はじめに 書は,筆者が長年書き溜めた様々な実務的な最適化問題についてまとめたものである. 書は,Jupyter Laboで記述されたものを自動的に変換したものであり,以下のサポートページで公開している. コードも一部公開しているが,ソースコードを保管した Github 自体はプライベートである. を購入した人は,サポートページで公開していないプログラムを 圧縮ファイル でダウンロードすることができる. ダウンロードしたファイルの解凍パスワードは<に記述>である. 作者のページ My HP 書のサポートページ Support Page 出版社のページ Pythonによる実務で役立つ最適化問題100+ (1) ―グラフ理論と組合せ最適化への招待― Pythonによる実務で役立つ最適化問題100+ (2) ―割当・施設配置・在庫最適化・巡回セールスマン― Pythonによる実務で役立つ

  • GitHub - tayllan/awesome-algorithms: A curated list of awesome places to learn and/or practice algorithms.

    Websites you should use to learn classic algorithms A Visual Guide to Graph Traversal Algorithms - Interactive visualizations for learning how graph traversal algorithms work. W3School - Data Structures tutorial. CodeChef - Learning DSA by practice on Codechef Algorithm Visualizer - Dozens of animated algorithms (with code), and you can also create your own. Algorithms Visualization - A dense arti

    GitHub - tayllan/awesome-algorithms: A curated list of awesome places to learn and/or practice algorithms.
  • エラトステネスの篩の高速化 - Qiita

    世の中に多くあるエラトステネスの篩の実装、多くあるくせにちょっとしか高速化してないのが悲しいので高速化エラトステネスの篩を書いてみることにします。 エラトステネスの篩の高速化 (1) ← 今ココ エラトステネスの篩の高速化 (2) エラトステネスの篩の高速化 (3) エラトステネスの篩の高速化 (4) エラトステネスの篩の高速化 (5) エラトステネスの篩の高速化 (6) エラトステネスの篩の高速化 (7) 問題設定 とりあえず C++11 くらいで動く物を作りたいと思います。インラインアセンブラや SIMD、並列化は明示的には入れない方針です。あと、エラトステネスの篩自体の高速化を目指すので、結果は一部の具体的な素数の確認と $\pi(x)$ の値で確認することにしますし、その時間は考慮しないことにします。 また、ライブラリ的に使えるよう、将来的には区間篩 (大きな $x$ に対して $

    エラトステネスの篩の高速化 - Qiita
  • https://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf

    kazutanaka
    kazutanaka 2020/12/06
    chris okasaki, Optimal Purely Functional Priority Queues