WebGPUとRustでネコチャンを点描した話
はじめに 昨年１２月にこんなツイートを見かけました。 かわいいですね。幸いにして論文と実装が公開されていたので、自分でもやってみようと思って、その結果を書いたのが前回の記事です。 読んでいただければわかるとおり、前回の記事の中ではGPUを使わずにアルゴリズムやデータ構造を工夫して近似的に計算しています。結果の画像についてはそんなに悪くないと思っていますが、限界もありました。パーティクルの数も少ないし、一部の画像ではうまく行きませんでした。 やっぱり、もっとちゃんとネコチャンを点描してみたいですよね。 なので、今回の記事ではGPUを使ってアルゴリズムを再現し、よりヴィヴィッドなネコチャンの点描を作成しようと思います。GPUを使って計算するために、WebGPUのRust実装であるwgpuを使用します。ネコチャンの画像を点描にしたい人と、WebGPUに入門してcompute shaderで何か計
データ分散アルゴリズムASURAの実装
最近、 仕事がピリっとしないからか、 趣味で分散ストレージでも作ってみようかなぁと思って色々と思考を巡らしている。 分散ストレージには大きく分けて２つの実装がある（と思う）。 １つは、どのデータがどこにあるかなどのメタデータを持つメタデータサーバを 保持し、そのメタデータサーバを参照・更新しながらレプリケーションや、ピースの分散を行うというタイプのもの。 もしこれをやるのであれば、メタデータはTiKVを使おうかなと考えていた。 TiKVはRustで実装された分散KVSだが、 レプリケーションを行う単位をRaftグループとして、これを複数持つMulti-Raftという構成をとっている。 外にはプレースメントドライバというプロセスがデータや負荷の分散具合を監視し、 必要に応じてマイグレーションを行っているらしい。 Raftを使っていれば、マイグレーションは簡単だろうと想像する。 もう１つは、そ
Rendezvous Hashingについての雑感
先日、 Rendezvous Hashingというアルゴリズムを小耳に挟んだ。少し興味をひかれ、軽く調べつつ実装してみたので、その感想。 ※ 思いついたことをテキトウに書いているだけであり、間違っている情報を含んでいる可能性もあるので注意 RendezvousHashingアルゴリズム実装の参考にしたのはWikipediaの記事（ちゃんと知りたい人はリンク先を参照のこと）。Highest random weight (HRW) hashingとも呼ばれるらしい。 目的いわゆる分散ハッシュテーブル問題を解くためのアルゴリズムの一つ。 例えば「あるオブジェクトOを冗長度kで保存したい」として、そのために「格納先として、n個のサーバ群の中からk個を選択する」といったことを、各クライアントが独立して（ローカルな計算のみで）、かつ、一貫性を維持した形（i.e., クライアント間で選択結果に差がでない
PhobosLab
Introducing QOI — the Quite OK Image Format. It losslessly compresses RGB and RGBA images to a similar size of PNG, while offering a 20x-50x speedup in compression and 3x-4x speedup in decompression. All single-threaded, no SIMD. It's also stupidly simple. tl;dr: 300 lines of C, single header, source on github, benchmark results here. I want to preface this article by saying that I have no idea wh
輸送問題と More-for-Less パラドックス - 私と理論
皆さん，パラドックスは好きですか？僕は大好きです．高校生の時の愛読書の一つがウイリアム・パウンドストーンの「パラドックス大全」だったくらいです．パラドックスが提示する思考の迷路をうろうろして途方に暮れるのはとっても楽しいですね． 最近，ネットワークフロー（輸送問題）における More-for-Less パラドックスを知ったので紹介します． 注意として，パラドックスは妥当そうな仮定から「論理的な矛盾」を導くもの（ラッセルのパラドックスなど）と「直感的でない結論」を導くもの（誕生日のパラドックス，バナッハ・タルスキのパラドックスなど）の二種類に大別することができますが，More-for-Less パラドックスは後者に分類されるものです． 輸送問題 輸送問題とは以下のような問題です． 件の工場と 件の店舗からなる，ある商品の流通圏があるとする． 各工場 には 個の在庫がある.． 各店舗 では 個
FMA (fused multiply-add) の話 - Qiita
この記事では融合積和 (fused multiply-add; 以下もっぱら FMA) について扱います。 この記事は元々「その辺で提供されている fma 関数の実装が正しいかチェックしてみた」記事だったのがだんだん守備範囲を広げていったものなので、FMAを単に使うだけではなく、実装する側の視点が多く含まれています。 筆者が実装したHaskell向けのFMA関数はこちらにあります： haskell-floating-point/FMA.hs at master · minoki/haskell-floating-point FMAとは、FMAを含む規格 融合積和（fused multiply-add; FMA）とは、積と和が合体した演算です。数式で書けば $xy+z$ です。この際、丸め（浮動小数点数で正確に表せない数をそれに近い浮動小数点数で代用すること）を1回しか行わないため、「積→和
All Pairs Shortest Paths のアルゴリズムさんたち - koyumeishiのブログ
前書き 全点対最短経路問題 (APSP : All Pair Shortest Path) を解くアルゴリズムを 4 つ紹介します。 $V$ 頂点 $E$ 辺の非負重み有向グラフ $G$ を考えます。 負の重みがあるときは一回 Bellman-Ford か何かを使ってポテンシャルを計算すれば非負に直せると思います。 お品書き Warshall-Floyd 法 Dijkstra 法を $V$ 回 Hidden Path Algorithm SHORT Algorithm 1,2 はお馴染み。 3,4 は資料も全然ないし使われてない印象。 どちらも Dijkstra を何度も回すのは無駄が多いから使いまわせるところを使いまわそうって発想のアルゴリズム。 1,2 を押さえておけば大抵の場合 (特に競プロ(非マラソン)) は問題なくて、 3,4 は少しでもいいから高速化したいときに使う可能性がある
最適輸送の解き方
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https
二分探索よりお得なオンライン価格戦略 - 麻辣坊主
オンライン価格設定で面白いと思った結果を紹介します． 「適正価格を二分探索するとそこそこ良い方法になるが， 二分探索に少し手を加えるとさらに良い方法になる」という話です． 出典は R. Kleinberg and T. Leighton (FOCS 2003) の Theorem 2.1 です． この記事自体は Haifeng Xu 先生の講義スライド の第 1 回をかなり参考にしてます． ゲーム理論と機械学習の様々な興味深いトピックが網羅されていておすすめです． 問題設定 戦略の評価尺度：リグレット 自明な $\mathrm{O}(N)$ リグレット戦略 二分探索による $\mathrm{O}(\log N)$ リグレット戦略 二分探索を改良した $\mathrm{O}(\log\log N)$ リグレット戦略 まとめ 問題設定 あなたは A さんに $N$ 個のリンゴ を，$1$ 日
logsumexp は人類の黒歴史 - アスペ日記
あえて言い切る。 ここでは主に計算量について言っているので、スクリプト言語でデモ的なものを作るような場合は除く。この記事では C++ を使って書く。 logsumexp でどのように計算の量が増えるかはunnonouno: logsumexpとスケーリング法に詳しい。 ちょっと引用。 linear-chain CRFのパラメタ推定に必要なのは対数尤度関数の微分です．これの計算に必要なのが，前向き・後ろ向きのスコアαとβです．時刻t（系列上での位置）とラベルiに対する前向きスコアαは，以下の式で計算されます．fは特徴ベクトル，wは重みベクトルです． この後の話の流れは、 掛け算いっぱいで大変！ オーバー／アンダーフローしちゃうよ！ じゃあ log の世界で扱えばいいんじゃね？ 足し算もあるよ！ どうするの？ 「logsumexp〜」 すごい！ これでオーバーフローしないし安心だね！ でも重い
輸送問題を近似的に行列計算で解く（機械学習への応用つき） - 私と理論
輸送問題と呼ばれる問題があります． この問題は，普通は線形計画法やフローのアルゴリズムを使って解かれます． この記事では，この輸送問題を近似的に行列計算で解くアルゴリズム（エントロピー正則化 + Sinkhorn-Knopp アルゴリズム）を紹介します． 輸送問題とは アルゴリズム 得られる解の例 なぜこれで解けるのか？ 競プロの問題を解いてみる 機械学習界隈における流行 まとめ 輸送問題とは 輸送問題とは以下のような問題です． 件の工場と 件の店舗からなる，ある商品の流通圏があるとする． 各工場には 個の在庫がある.． 各店舗では 個の需要がある． 在庫の総和と需要の総和は等しいとする （すなわち ）． 工場 から店舗 に商品を一つ運ぶためには の輸送コストがかかる． 各工場 から各店舗 への輸送量 を適切に決めて，各店舗の需要を満たしつつ輸送コストの総和を最小化せよ． 輸送問題は最適化
線形漸化的数列のN項目の計算 - Qiita
この記事はデータ構造とアルゴリズム Advent Calendar 2020 18日目の記事です。 はじめに 与えられた線形漸化式を満たす数列の $N$ 項目を計算する問題は計算機科学において最も基本的な問題の一つである。この問題に対するアルゴリズムとして Fiduccia のアルゴリズム(1985) が知られている。Fiduccia のアルゴリズムは極めてシンプルかつ高速なアルゴリズムであり35年間最速のアルゴリズムであった。2021年に Bostan と Mori によって演算回数が Fiduccia のアルゴリズムのおよそ 2/3 であるアルゴリズムが発表された。本稿では Fiduccia のアルゴリズムと Bostan–Mori のアルゴリズムの解説をする。 また、Bostan–Mori のアルゴリズムを応用することで、多項式 $\Gamma(x)$ について $x^N\bmod\
GabowのEdmonds' Algorithm(一般マッチング O(VElogV))の解説と実装 - Qiita
これは「データ構造とアルゴリズム Advent Calendar 2018」14日目の記事です． この記事は, Gabowの論文をもとに書かせていただいています. こっちを読むと完全に理解できます. マッチング? けんちょんさんの記事から画像をお借りしました. マッチングは辺の集合であって, どの2辺も両端を共有しないようなものをマッチングといいます. その集合の中で, 一番辺の数が多いものを最大マッチングといいいます. 二部マッチング? こちらもけんちょんさんの記事 二部グラフ(グラフの頂点が２グループに分かれていて, グラフの辺がその２グループをまたぐものしか無いグラフ)での二部マッチングは最大フローに帰着して解くことが出来ます. 導入 二部マッチングの問題は最大フローで解けたりしますが, 一般マッチングはそうはいきません. また実装が難しいこと(Edmonds' Blossom De
ダイクストラ法のよくあるミスと落し方 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
ダイクストラ法、正しく書けてますか？ ダイクストラは少しのミスですぐ計算量が壊れたりするのですが、テストケースによっては意外に落ちにくく間違いに気づかないこともあります。 この記事では、よくあるミスとその撃墜ケースを紹介していきます。 この記事はどちらかと言うと問題準備をする方に読んでほしい記事です。 writerをする際は、ここで紹介する撃墜ケースをテストケースに入れるようにすると良いと思います。 SではなくTを始点にするという小手先技が考えられるので、逆向きバージョンも入れておくと尚良いでしょう。 ジェネレーターも置いておきます。 コード中の定数を書き換えたり入力で取れるようにしたり、出力形式を変えたりして使ってください。 念の為生成されたテストケースにもちゃんとvalidatorをかけて下さい。 目次 既に見た頂点のcontinue忘れ： 最大ヒープを使う： 負辺のあるグラフで使う：
『ゼルダの伝説 風のタクト』にて“運任せで極めて厄介”とされた海戦ゲームの仕組みは、どのように解かれたのか。執念が生み出した最適解 - AUTOMATON
RNG。もともとはRandom Number Generator、つまりは乱数を発生させる仕組みそのものを指していたこの略語は、転じてゲーマーにとっては「運要素」そのものを指す言葉となっている。RNGはスピードランナー達にとって最大の敵でもある。そして「いかにして自分の走るルートからRNGを排除するか」に心血を注ぐスピードランナー達、その一人が『ゼルダ』シリーズの走者として知られるLinkus7氏である。彼が今回RNGの魔の手から解放したタイトルは『ゼルダの伝説 風のタクト』（以下、『風のタクト』）、特にそのゲーム中に登場する「海戦ゲーム」だ。Linkus7氏はその戦いの軌跡を解説動画としてアップロードし、大きな反響を呼んだ。本記事では「我々がいかにしてゼルダシリーズ最悪のミニゲームに決着をつけたか」というタイトルのその動画の内容の、日本語での解説を試みる。なお解析が成功されたのは2020
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - catupper/RationalModConverter
An Optimal Choice Dictionary
Library Checker
割り当て問題（ハンガリアン法） - build error
[連載コラム]数理最適化：第４回 数理最適化とその歴史①｜貴社ビジネスのIT共創者、中央コンピューター株式会社