「最短経路問題」の新アルゴリズム。数十年来の“理論的限界”破ったと発表【研究紹介】 レバテックラボ（レバテックLAB）
中国の清華大学、米国のスタンフォード大学、ドイツのMax Planck Instituteに所属する研究者らが発表した論文「Breaking the Sorting Barrier for Directed Single-Source Shortest Paths」は、グラフ理論の最短経路問題において、長年の理論的限界を打ち破るアルゴリズムを発見したとする研究報告である。 ▲論文のトップページ グラフ理論における単一始点最短経路問題（Single Source Shortest Path Problem）は、ある地点から他のすべての地点への最短ルートを見つける問題で、カーナビのルート検索やネットワーク設計など、幅広い応用を持つ。 コンピュータサイエンスの基礎的な問題のひとつであり、この問題を解く最も有名な方法が、1959年に考案されたダイクストラ法である。ダイクストラ法は、出発点から波紋が
なっとく！アルゴリズム 第2版 | 翔泳社
人探し、バスの乗り継ぎ、お買いもの…… 半径3メートルの身近なアルゴリズムはこんなにわかりやすい！ さまざまなアルゴリズムの背後で使われる≪木構造≫の解説を増補した第2版！ プログラミングにおいてアルゴリズムの知識は欠かせません。しかし、いざアルゴリズムの学習をはじめると、理屈の山と数式の谷間で迷子になることが少なくありません。 そんなときにおすすめなのがこの一冊。本書は、人探しやバスの乗り継ぎなど身近な例を通して、イラストとサンプルプログラムを援用しながらアルゴリズムについて平易に解説してくれます。 読み進めるには、中学レベルの代数の基礎を知っていれば大丈夫。プログラミング言語をどれか1つ知っていれば、さらに理解が深まります。 最後まで読めば、応用範囲の広い重要なアルゴリズムの数々をしっかり理解できます。 ［本書は、"Grokking Algorithms, Second Edition
高速で頑健なシェーダー乱数の比較と提案 - 屋根裏工房改
はじめに シェーダー (HLSL) で乱数を発生させたくなることがしばしばあります。 直接的にはホワイトノイズ、間接的にはパーリンノイズなどが挙げられます。 そういうシェーダーを書いたことがある方は、 frac(sin(...)) みたいな擬似乱数生成器を目にしていることでしょう。 ですが、乱数を発生させる手法は星の数ほど存在します。品質や速度もそれぞれ異なる擬似乱数生成器がたくさんあります。 本稿ではそれらのシェーダー乱数の性能比較を行っていきたいと思います。 シェーダー乱数の定義 さて、乱数とはいっても、シェーダーでよく使われる乱数は CPU ベースの (メルセンヌツイスタ とかの) 擬似乱数生成器とは設計レベルで異なることが多いです。 まず、状態を持たない、ある種のハッシュ関数のような実装をすることがほとんどです。 大抵の場合、座標を引数にとることになるでしょう。毎フレーム変化する乱
CRDTs go brrr
5000x faster CRDTs: An Adventure in Optimization July 31 2021 A few years ago I was really bothered by an academic paper. Some researchers in France put together a comparison showing lots of ways you could implement realtime collaborative editing (like Google Docs). They implemented lots of algorithms - CRDTs and OT algorithms and stuff. And they benchmarked them all to see how they perform. (Cool
世界1位取った後3年間オセロAIを作り続けたらﾅﾆﾓﾜｶﾗﾅｸなってﾁｮｯﾄﾀﾞｹﾃﾞｷﾙようになった話 - Qiita
2021年、ふとしたきっかけでオセロAIを作り始め、オセロAIコンテストに作ったAIを提出し、なんやかんやあって半年かけてそのコンテストで世界1位になりました。 それで満足…？と思いきや、全然満足せず、コンテスト関係なしにオセロAIを作って早3年。この記事ではオセロAIが色々なところに私を連れて行ってくれた話と、オセロAIが深いという話をします。 この記事は2年ほど前に書いていっぱい読んでいただけた以下の記事「ｶﾝｾﾞﾝﾆﾘｶｲｼﾀ話」の続編、みたいな立ち位置です。単体で読んでも、以下の記事と合わせて読んでも楽しめます。 世界1位からさらに高みを目指す 私が参加したオセロAIのコンテスト(CodinGame Othello)は、コンテストという特性上、かなり厳しい制約が設けられていました。例えば着手する時間です。これは1手あたり0.15秒以下でないといけません。また、コード長にも制限があり
Bloom Filters
This page makes heavy use of JavaScript to visualise the concepts discussed. Viewing it without JavaScript will be a strange experience, as the text talks about the visualisations. I strongly recommend either enabling JavaScript, or not wasting your time. Everyone has a set of tools they use to solve problems. Growing this set helps you to solve ever more difficult problems. In this post, I'm goin
The Myers diff algorithm: part 1 – The If Works
If you enjoy this article, I have published a book explaining the internals of Git through implementation: Building Git. — As a programmer, you probably use a version control system such as Git, and spend an awful lot of your time looking at diffs. You use them to check over your uncommitted work in progress, to look at what changed in a single commit, to compare two branches before performing a m
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時まで二度寝してから読みました。 注意すべきは、この論文が査読を経て公開されているわけではないこと、つまり形式上特にチェックを受けたものではないことです。ただ、タイトルからして非常に衝撃的ですので、個人的に読んでみました。この記事では、私がこの論文(およびソースコード)を読んでわかったことを、なるべくわかりやすくまとめます。随時更新します。 余談ですが、このタイトルはどう
DeepMindが深層強化学習を利用してアルゴリズムを改善するAI「AlphaDev」を発表、すでにソートアルゴリズムやハッシュ関数の高速化に成功
AlphaGoの開発元として有名なGoogle DeepMind社が深層強化学習を応用してさまざまなコンピューティングアルゴリズムを改善するAI「AlphaDev」を発表しました。同時に、AlphaDevを利用してソートアルゴリズムを高速化できたという論文がNatureに掲載されています。 AlphaDev discovers faster sorting algorithms https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms Faster sorting algorithms discovered using deep reinforcement learning | Nature https://doi.org/10.1038/s41586-023-06004-9 ソートアルゴリズムとは
Beautiful Branchless Binary Search
I read a blog post by Alex Muscar, “Beautiful Binary Search in D“. It describes a binary search called “Shar’s algorithm”. I’d never heard of it and it’s impossible to google, but looking at the algorithm I couldn’t help but think “this is branchless.” And who knew that there could be a branchless binary search? So I did the work to translate it into a algorithm for C++ iterators, no longer requir
NASAが宇宙規模の通信などで発生する損失にも耐えられるよう作った画像圧縮アルゴリズム「ICER」が誰でも利用可能に
NASAは、「宇宙から地球に無線で画像を転送する」といったデータ損失の大きな状況に最適化した画像圧縮アルゴリズム「ICER」を開発しています。そんなICERをC言語のライブラリとして実装したものがGitHubで無料公開されています。 GitHub - TheRealOrange/icer_compression: Progressive, error tolerant, wavelet-based image compression algorithm https://github.com/TheRealOrange/icer_compression NASAは火星探査などのミッションで現地の様子を撮影した画像データを地球へ送信しています。異なる場所へデータを送信する際は、地球上での通信であってもデータの損失が発生しているのですが、地球と火星などの宇宙規模の通信ではデータの損失は非常に大き
優先度付きキューにも使われる二分ヒープ構造をRubyで実装してみる - $shibayu36->blog;
アルゴリズム図鑑 絵で見てわかる26のアルゴリズム 作者:石田保輝,宮崎修一翔泳社Amazon アルゴリズム図鑑を眺めていて、二分ヒープ構造は優先度付きキューに使われることを知った。面白いなーと思うと同時に、そういえば二分ヒープ構造の実装をしたことがなく、あまり理解できていないことに気づいた。そこで簡単にRubyで実装をしてみたのでメモ。簡単なテストケースを作ったので多分合ってると思うけど、もしかしたらバグっているかも... 二分ヒープの詳細は二分ヒープ - Wikipediaも参考。 【2023/01/03 14:01追記】要素数が1の時に要素が空にならないバグがあったので修正しました。コメントありがとうございます。https://github.com/shibayu36/algorithms/commit/6c2ce588f7bc7fb890c6a560c7ab062c6f531a9a
ヒープについてわかりやすく解説してみた – Yasufumi Taniguchi – Medium
基本的なデータ構造であるヒープについて、概要、計算量と実装、そして最もシンプルな応用であるヒープソートを紹介します。MITが講義や資料を公開しているMIT OpenCourseWareのアルゴリズムとデータ構造の講義 が非常にわかりやすかったので、その内容に沿ってまとめました。この記事ではHeaps and Heap Sortの内容を以下の順序で解説します。 ヒープの概要ヒープの表現ヒープの構築ヒープの計算量ヒープの実装ヒープソート1. ヒープの概要ヒープ (heap) は優先度付きキュー (priority queue) の実装の1つです。優先度付きキューは集合 (set) を扱うデータ型で、集合に含まれる要素が何らかの優先度 (priority) 順に取り出されるという特徴を持っています。学会のポスター発表を回るときや、旅行先での観光地巡りでは、優先度に基づいて要素を取り出すことが重要
キャッシュアルゴリズムの比較 - falsandtruのメモ帳
アプリケーションなどOSより上に作られる高水準のプログラムではハードウェアの速度と容量を考慮しない数学的キャッシュアルゴリズムが使われ主にこれを本稿の対象とする。キー探索用マップと明示的キャッシュサイズ(対となる値が保持されているキーのサイズ)は計算量に含まれない。 LRU 最も単純かつ高性能な基礎的キャッシュアルゴリズム。そのため性能比較のベースラインとして常に使用される。逆に言えば実用最低水準の性能である。スキャン耐性皆無でスキャン一発でキャッシュとヒット率がリセットされゼロからやり直しになるため非常に脆く不確実な性能となりベンチマークにおける性能が表面上さほど悪くなく見えても実際の性能はこのような外乱により大きく低下しやすい。このためLRUより高度な主要アルゴリズムはすべて大なり小なりスキャン耐性を備えている。ちなみにプログラミング言語最大のパッケージマネージャであるJavaScri
アルゴリズムイントロダクション 第3版 総合版：世界標準MIT教科書
アルゴリズムイントロダクション 第3版 総合版：世界標準MIT教科書 T. コルメン, C. ライザーソン, R. リベスト, C. シュタイン(著), 浅野哲夫, 岩野和生, 梅尾博司, 山下雅史, 和田幸一(訳) 近代科学社 15,400円 (14,000円+税) 計算機科学の基礎分野で世界的に著名な4人の専門家がMITでの教育用に著した計算機アルゴリズム論の包括的テキスト．前版までで既にアルゴリズムとデータ構造に関する世界標準教科書としての地位を確立しているが，より良い教科書を目指して再び全面的な記述の見直しがなされている． 関連サイト本書の関連ページが用意されています。 アルゴリズムイントロダクション 第3版 総合版（近代科学社ウェブサイト）内容紹介世界標準 MIT 教科書!! 原著は，計算機科学の基礎分野で世界的に著名な4人の専門家がMITでの教育用に著した計算機アルゴリズム論の
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
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
【実践】エンジニアの基礎教養-アルゴリズムを学べる本
Raft(分散合意アルゴリズム)について
CPU/GPU高速化セミナー 浮動小数点から文字列への高速変換の論文を読んでみた / cpugpu acceleration seminar 20230201
GitHub - twitter/the-algorithm: Source code for Twitter's Recommendation Algorithm
