アニメーションをスムーズに見せるためのテクニック「指数平滑法」とはどんなものなのか？
グラフィック系の開発者であるニキータ・リシッツァ氏が、「自身のプロダクトのあらゆる場所で使用している」と述べるお気に入りのテクニックである「指数平滑法」について解説を投稿しました。 My favourite animation trick: exponential smoothing | lisyarus blog https://lisyarus.github.io/blog/programming/2023/02/21/exponential-smoothing.html リシッツァ氏は下図のようなトグルボタンを例に解説を行っています。クリックすると「オン」「オフ」が切り替わります。まだアニメーションを何も設置しておらず、トグルボタンは左端と右端を瞬間移動しています。 機能的にはアニメーションが設定されていなくとも問題はないのですが、アニメーションを設定することでユーザーは何が起こって
タイムスタンプの精度を落とすときは切り捨てろ - methaneのブログ
とあるプロジェクトでナノ秒からミリ秒への変換で四捨五入してきた人がいて、時刻を扱うときは保存精度未満は切り捨てるべきというのが常識になっていないなーと思ったので。 2023-10-01 を、何年か表示する時に、2024年に丸める人はいないだろう。 13:45 が何時か表示する時も、13時と表示するだろう。（口頭で何時？と聞かれたら14時と答えるかもしれないけれど） つまり、ある精度で表した時刻は、実際には次のような半開区間を示しているのである。 2023-01-01 00:00:00 <= 2023年 < 2024-01-01 00:00:00 13:45:00.000 <= 13:45 < 13:46:00.000 そして、そう決めたからには一貫して同じように、指定精度未満は切り捨てというルールを維持しなければならない。秒以下は四捨五入で、とかやってはいけないのだ。 一貫しないと何が問題
MySQLのインデックスですが、B-treeではなくB+treeを使用するのはどうしてなのでしょうか？ | mond
MySQLのインデックスですが、B-treeではなくB+treeを使用するのはどうしてなのでしょうか？ 端的に言うと性能が良いからです。 これを理解するにはバッファプールへの理解が必要です。ディスク指向のデータベースの上では有限のメモリを最大限活用することでメモリに入り切らない巨大なデータ群に対して良好な参照性能を出す必要があります。バッファプールとはディスク上のデータの羅列を固定サイズのページ（InnoDBの場合16KB）の羅列であるとして読み書きに必要な分だけをメモリに移し取り複数の書き込みをできる限りメモリ内で受け止めて後でまとめてディスクに書き戻すという、ライトバック型のキャッシュのような機構です。 この中においてバッファプールは有限のサイズしか無いので適宜プール内のデータを書き戻して入れ替えながら上手くやっていく必要があります。 さてB+treeとB-treeの最大の違いは木のリ
strlen() の深淵 - Qiita
あらまし strlen() という関数がある。御存知の通り、文字列の長さを算出する標準 C ライブラリの関数だ。 やってることは単純で、例えば以下のように実装できる。 size_t strlen_simple(const char* str) { const char* p = str; while (*p) ++p; return size_t(p - str); } '\0' が見つかるまでポインタを進め、初期位置との差分を返すだけだ。これで機能的には std::strlen() と同等である。 では、速度的にはどうだろう？適当にベンチマークを書いて MSVC 2022 でコンパイル＆実行するとこうなった。
徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
レトロゲームのドット絵の拡大表示と EOTF/OETF の関係
この文書では、 レトロゲームを最新の PC やコンソールに移植するような場合に必要となる、 低解像度のドット絵をドット感を残しつつ高解像度ディスプレイに拡大表示する処理についてまとめます。 そして、拡大処理で見落としがちな問題とその解決方法、および改良と高速化について触れます。 この文書では、ごく基本的なバイリニアフィルタによる拡大処理のみを取り扱います。 高解像度化技術周辺や、CRT のスキャンラインや画素の再現は、この文書で取り扱う範囲外なので一切触れません。 また、 話を簡単にするため、拡大結果を sRGB 規格のディスプレイに表示するケースのみを考えます。 筆者はディスプレイの規格が専門分野ではないので、 色の定義などの理解が甘い箇所があるかもしれません。あらかじめご了承ください。 何か間違いがありましたら、ご指摘いただければ幸いです。 ドット絵の滲みを再現したい 当時のドット絵は
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は火星探査などのミッションで現地の様子を撮影した画像データを地球へ送信しています。異なる場所へデータを送信する際は、地球上での通信であってもデータの損失が発生しているのですが、地球と火星などの宇宙規模の通信ではデータの損失は非常に大き
キャッシュアルゴリズムの比較 - falsandtruのメモ帳
アプリケーションなどOSより上に作られる高水準のプログラムではハードウェアの速度と容量を考慮しない数学的キャッシュアルゴリズムが使われ主にこれを本稿の対象とする。キー探索用マップと明示的キャッシュサイズ(対となる値が保持されているキーのサイズ)は計算量に含まれない。 LRU 最も単純かつ高性能な基礎的キャッシュアルゴリズム。そのため性能比較のベースラインとして常に使用される。逆に言えば実用最低水準の性能である。スキャン耐性皆無でスキャン一発でキャッシュとヒット率がリセットされゼロからやり直しになるため非常に脆く不確実な性能となりベンチマークにおける性能が表面上さほど悪くなく見えても実際の性能はこのような外乱により大きく低下しやすい。このためLRUより高度な主要アルゴリズムはすべて大なり小なりスキャン耐性を備えている。ちなみにプログラミング言語最大のパッケージマネージャであるJavaScri
暗号アルゴリズム「SHA-1」の廃止を発表、NIST
米国国立標準技術研究所(NIST: National Institute of Standards and Technology)は12月15日(米国時間)、「NIST Retires SHA-1 Cryptographic Algorithm｜NIST」において、暗号アルゴリズム「SHA-1」を廃止すると伝えた。SHA-1の暗号ハッシュ関数はすでに脆弱と評価されており米国政府機関での利用廃止が発表されている。 電子情報を保護するために初期に広く使われた手法の一つであるSHA-1アルゴリズムは、耐用年数が終了しているとして廃止が決定されている。SHA-1がまだ使用されているという現状から、より安全性の高い新しいアルゴリズムに置き換えることが推奨されている。 SHA-1という名称は「Secure Hash Algorithm」の頭文字からきており、1995年から連邦情報処理規格(FIPS:
キャッシュによるRubyの正規表現のマッチングの高速化の紹介 - クックパッド開発者ブログ
9月からRuby開発チームにインターンシップとして参加している@makenowjustです。 総合研究大学院大学の学生で、普段は情報セキュリティに関する研究をしています。 インターンシップでは、キャッシュ (メモ化) を利用したRubyの正規表現の高速化を行いました。 ReDoSと呼ばれる、バックトラックが爆発することでマッチング時間が膨大になる脆弱性があります (ReDoSについては、拙作ですがWEB+DB PRESSに掲載された記事があります)。 近年、ReDoSは多く報告されており、Rubyもその例外ではありません (参考1、参考2)。 今回実装した最適化は、ReDoSを防ぐことを目的としたもので、多くの正規表現のマッチング時間が文字列の長さに対して線形となります。 ReDoSが起こる正規表現の例として、/^(a|a)*$/が挙げられます。 今回の修正の前後での実行時間を比較すると、
Facebookが開発した圧縮アルゴリズムZstandardについて調べた(非常に高速)(今日から使えます) - Lambdaカクテル
Common Lispの処理系であるSBCLをインストールしようとしたら、追加でlibzstd-develというのを新たに要求されるようになっていた。見るからに圧縮系のライブラリだけれど聞き慣れないのでちょっと調べてみた。 ちょろっと調べたところ、以下のことが分かった: Zstandard(ゼットスタンダード？)というのが正式な名前。 Facebookが開発した。 Deflateよりも速いことを主眼においている。 BSDライセンス。 Linuxカーネルまわりで使えるようになっているほか、一部のディストロではパッケージの圧縮フォーマットとして使われているようだ。 Webというよりはどちらかといえばバックエンド的な箇所で使われている印象がある。 facebook.github.io zstd コマンド使ってみた 他の名だたる圧縮アルゴリズム同様、Linuxで直接ファイルに対してこれを実行して圧
図解Stable Diffusion
ジェイ・アラマールのブログより。 AIによる画像生成は、(私を含めて)人々の度肝をぬく最新のAIの能力です。テキストの説明から印象的なビジュアルを作り出す能力は、魔法のような品質を持ち、人間がアートを創造する方法の変化を明確に指し示しています。Stable Diffusionのリリースは、高性能(画質だけでなく、速度や比較的低いリソース/メモリ要件という意味での性能)なモデルを一般の人々に提供することになったのは、この開発における明確なマイルストーンです。 AI画像生成を試してみて、その仕組みが気になり始めた方も多いのではないでしょうか。 ここでは、Stable Diffusionの仕組みについて優しく紹介します。 Stable Diffusionは、様々な使い方ができる汎用性の高いものです。まず、テキストのみからの画像生成(text2img)に焦点を当てます。上の画像は、テキスト入力と生
テキストエディタで使われがちなデータ構造 Piece Table の概要と実装 - A Memorandum
テキストエディタのデータ構造 Gap method Piece Table method Piece Table の構造 Piece Table の実装 Piece Table のメソッド まとめ テキストエディタのデータ構造 テキストエディタで採用されているデータ構造にはいろいろあります。 こちらの論文 Data Structures for Text Sequences では各種データ構造について比較検討されています。 多くは、Gap method や Piece table method をベースにしたものが多いのではないでしょうか(図で言う最下部の中心の丸印に当たります)。最近では Rope なども有名ですね。 Gap method Gap method では、現在のカーソル位置で、テキストバッファを2つに分割し Gap を間に挟み、カーソル位置に対する編集(テキスト追加/削除)を
ネットワークの輻輳は避けられない — 数学で証明
IEEE Spectrumより。 トラフィック問題を「解決」することが事態が悪化させることもある BY チャールズ・Q・チョイ 高速道路網が交通渋滞に悩まされるように、コンピュータ・ネットワークも輻輳(混雑)に直面することがある。この度の新しい研究で、コンピュータ・ネットワークの遅延を制御するために設計された多くの主要なアルゴリズムが、一部のユーザにすべての帯域を占有させ、他のユーザには実質的に何も提供しないという、極めて不公平なものであることが判明した。 インターネット上でデータを送信するコンピュータやその他の機器は、データを小さなパケットに分割し、特殊なアルゴリズムを用いて、これらのパケットを送信する速度を決定している。これらの輻輳制御アルゴリズムは、同じネットワーク上の他のユーザと共有しながら、利用可能なすべてのネットワーク容量を発見し、利用することを目的としている。 過去10年間、
基本に立ち返る: 動画圧縮の裏側で使われる仕組み | Amazon Web Services
Amazon Web Services ブログ 基本に立ち返る: 動画圧縮の裏側で使われる仕組み 動画エンコーディング この Blog では、動画エンコーディング処理（圧縮）の基本について、簡単な言葉で説明していきます。 圧縮・エンコーディングの主な目的は、動画の記録、保存および伝送するのに必要となるデータの量を削減することです。これは、ストレージハードウェア、データ伝送時間、必要となる配信帯域幅の削減に繋がります。 動画をエンコードするための多くの異なるアルゴリズム（例えば、MPEG-2、H.264/AVC、H.265/HEVC、VP9、AV1 など）が存在しますが、今日使われている一般的なコーデックのほとんどは、このブログ記事で紹介する共通の原理に従います。 Joint Photographic Experts Group もしくは JPEG 圧縮 デジタル画像を圧縮するために最も一般
ネットワークの混雑を制御するアルゴリズムに「公平な通信を提供しきれない」という問題があることが判明
2022年7月2日に発生したKDDIの通信障害では、多数の端末からアクセスが集中したためにネットワークで輻輳(ふくそう)が発生し、KDDIのモバイル通信などを利用しづらい状況が長時間にわたり続きました。輻輳について行われた新たな海外研究で、本来あらゆるユーザーが公平にネットワークへアクセスできるよう管理するアルゴリズムに偏りがある可能性が指摘されました。 Researchers discover major roadblock in alleviating network congestion | MIT News | Massachusetts Institute of Technology https://news.mit.edu/2022/algorithm-computer-network-bandwidth-0804 マサチューセッツ工科大学の研究者らによると、Googleが開発
Film Grain Synthesis in AV1
Film grain synthesis in AV1 Published Nov. 3, 2019, updated Dec. 18, 2019. This page describes the film grain synthesis as defined in the AV1 film grain tool. Recently, there have been a lot of question on the film grain in AV1. Hopefully, this page can answer some of them. If you would like to get more information, you can follow links on this page or contact me directly. Motivation to preserve f
リアルタイム共同編集のアルゴリズム (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（文書を編集する側です） そ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Collision with v4 uuid · Issue #546 · uuidjs/uuid
Go1.19で採用された Pattern-defeating Quicksort の紹介
