時間順にソート可能なUUIDv6, UUIDv7, UUIDv8の提案仕様 - ASnoKaze blog
IETFに「New UUID Formats」という提案仕様が提出されています。 これは、時系列順にソート可能なUUID version 6, UUID version 7, UUID version 8を新しく定義するものです。 詳しい背景は提案仕様にゆずりますが、ULIDを始めとして、時系列順にソート可能な一意な識別子を利用したいというユースケースがあります。例えば、データベースのキーとして使えば、ソートせずとも順番に並びますし、書き込む際も順々に書き込めるのでデータアクセスが局所的になります。 今回は簡単に、それぞれのUUIDのフォーマットを眺めていきます。なお、フォーマットは異なりますが、バージョンを示す値は同じ位置にあります。 UUIDv6 UUIDv6は128bit長で、UUIDv1と似てるフォーマットを取ります。 1582年10月15日(グレゴリオ暦)からの100ナノ秒単位で
数としての赤黒木 - エムスリーテックブログ
エンジニアリンググループの高島（@rst76）です。 社内の勉強会で、計算機科学の有名な教科書、アルゴリズムイントロダクション（Introduction to Algorithms）を輪読しています。 ちょうど赤黒木の章を私が担当したので、要点をかいつまんでご紹介したいと思います。 今回お話したいのは「ある条件の下で、赤黒木は記数法表現と見ることができる」という話です。 赤黒木の例 赤黒木 二分木というデータ構造があります。 計算機科学では一般的なデータ構造で、ランダムなデータであれば、検索や挿入などの操作を で実現できます。 ただ、データの与え方によっては偏った木ができてしまうことがあり、そうすると各操作の性能が に落ちてしまうので、どうやって木の平衡性を維持するかが課題です。 赤黒木は二分木の一種で、ノード（節点）を赤と黒に塗り分けて、赤と黒の組み合わせによって平衡性を保つための調整を
簡潔ビットベクトルでRubyをlog N倍速くした - クックパッド開発者ブログ
技術部のフルタイムRubyコミッタの遠藤（@mametter）です。昨日の Hackarade #04 の開催報告に続き、2日連続で記事を投稿します。 今回は、ある条件下でのRubyの実行速度を高速化した話を紹介します。この改善はすでにMRIの先端にコミットされていて*1、年末リリース予定のRuby 2.6に含まれる予定です。 ひとことで言うと、「簡潔ビットベクトルを索引に使うことで、プログラムカウンタから行番号を計算するアルゴリズムをO(log N)からO(1)に改善した。これにより、TracePoint有効時やコードカバレッジ測定下で、長さ N のメソッドの実行が O(N log N) から O(N) に高速化される」ということです。順に説明します。 背景：Rubyのバイトコードの構造 この最適化を理解するにはまず、Rubyのバイトコードのある特徴を知る必要があります。 たとえば x
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
