UUID v6, v7, v8 : タイムスタンプでソートできる新しい UUID のドラフト仕様 - kakakakakku blog
ID を採番するときによく使われる UUID Version 4 の課題として「順序性がなくソートしにくい」という側面があり，ULID (Universally Unique Lexicographically Sortable Identifier) を使えばソートできるようになるという記事を前に書いた． kakakakakku.hatenablog.com 関連して調査をしていたら，標準化団体 IETF (Internet Engineering Task Force) によって，UUID Version 6, 7, 8 という新しい仕様が提案（ドラフト段階）されていることを発見した❗️UUID Version 6, 7, 8 の目的を簡単にまとめると「タイムスタンプ情報を使ってソートできる ID を採番できるようにする」となり，もしこの仕様が取り込まれると，UUID を活用する幅がさ
BloomFilterについて調べてみた - 逆さまにした
BloomFilterとは Wikipedia にも記載されていますが、ある要素が集合に属しているかを検査できるフィルタです。 一番最初に思いつく実装としては、こんな感じでしょうか。 集合の先頭から順に要素を比較していく 途中で見つかれば「属している」 最後まで見つからなければ「属していない」 この場合、要素数をNとして、O(N)の計算量が必要ですが、BloomFilterでは、BloomFilterで使用するハッシュ関数の個数をkとして、O(k)で計算ができます。 もちろん、これにはトレードオフがあり、「属している」と判断したものの、 実は「属していなかった」 という偽陽性を許容することで上記のような利点を実現しています。 ※ただしBloomFilterでは、原理的に偽陰性はありません。 詳細はこのあとみていきますが、実際に動かしてみるとわかりやすいので、体験したい方はGUIでポチポチで
50分で学ぶアルゴリズム / Algorithms in 50 minutes
本スライドでは、有名なアルゴリズムを概観し、アルゴリズムに興味を持っていただくことを目標にします。 第 1 部：アルゴリズムとは 第 2 部：学年を当ててみよう 第 3 部：代表的なアルゴリズム問題 第 4 部：コンピュータとアルゴリズム
Approaching Heapsort via Lazy Mergesort - HackMD
# Approaching Heapsort via Lazy Mergesort [toc] --- # はじめに: ヒープソート未だに良くわからん ヒープソートが分からずとも生きていけます
読書: 計算量とマスター定理 • masu-mi's blog(dirty pages)
読書: 計算量とマスター定理 マスター定理の意味を押さえたい。周辺を整理して押さえた上で漸近計算量の見積もりをやれるようになりたい。 マスター定理は分割統治法による時間計算量を求める定理です。分割統治法では下のような漸化式が出てくることがしばしばある。 T(n)={aT(n/b)+f(n)if n>n0cif otherwisefor ∃c,n0,a≥1,b>1 \begin{aligned} T(n) = & \begin{cases} aT(n/b) + f(n) &\text{if } n > n_0 \\ c &\text{if otherwise} \end{cases} \\ & \text{for } \exists c,n_0,a \ge 1, b \gt 1 \end{aligned} T(n)={aT(n/b)+f(n)cif n>n0if otherwisef
今更だけど、データ圧縮についてまとめてみたい | 株式会社PLAN-B
bz2, xz, Deflate, gzip, zip, snappy, …データ圧縮に関しての名前です。 なんとなく見覚えがあるだけのものから、普段使いしているものまで色々あって、なんとなく使ってはいるけれど、それぞれどのような意図を持って使い分けたら良いのでしょうか。そもそもどんな違いがあるのでしょうか。 この違いがちゃんとわかっていたら、なんとなくかっこいい気がしませんか？というわけで、今回は圧縮アルゴリズムの歴史と、特性を追っていきたいと思います。 可逆圧縮と非可逆圧縮の違い圧縮をまず大きく大別すると、可逆圧縮と非可逆圧縮に分けられます。その名の通り、元に戻せる圧縮方法と、元には戻せない圧縮方法です。非可逆圧縮の用途には音声、画像や動画などの圧縮があります。 データとしてはわざと欠落させるけれど、人間の認識には影響の少ないようにするものがあります。用途、画像でよく使われるJPEGや
超高速！多倍長整数の計算手法【後編：N! の計算から円周率 100 万桁の挑戦まで】 - Qiita
4-1. N! の高速な計算 $N! = 1 \times 2 \times 3 \times 4 \times \cdots \times N$ を計算してみましょう。 $N!$ は場合の数を求める問題でよく出てきて、こんな感じのものが求まります。 $1, 2, ..., N$ が書かれたトランプのカードが 1 枚ずつあるとき、これを一列に並べる順番は何通りあるか？ 例えば、$N = 13$ の場合 $13! = 6,227,020,800$ 通り、のように計算できます。 また、$N!$ は二項係数 $_NC_K$ を求めるのにも使われます。 $N!$ が求まれば、$_NC_K = N! \div K! \div (N-K)!$ で掛け算・割り算するだけで計算できますね。 $N$ 個の区別できるボールから $K$ 個を選ぶ方法は何通りか？ これが $_NC_K$ になります。例えば、$N
高速なハッシュテーブルを設計する | POSTD
(訳注：2016/9/28、頂きましたフィードバックを元に記事を修正いたしました。) はじめに 本稿では、高速で汎用的なハッシュテーブルを作るために行う、設計についての多くの意思決定事項を紹介します。最終的に、私の emilib::HashSet とC++11の std::unordered_set の間のベンチマークが出来上がりました。もし、ハッシュテーブルに興味があって、自分で設計したいなら（どのプログラミング言語かに関わらず）、本稿がヒントになるかもしれません。 ハッシュテーブル は、素晴らしい発明です。 ならし計算量O(1) ( O(√N)時間 )で、挿入、削除、検索を行うことができます。ならし計算量とは、ハッシュテーブルの計算に平均でO(1)の計算量がかかることを意味しますが、時々、これよりも多くの時間がかかる場合があります。具体的には、ハッシュテーブルに空きがない場合で、挿入の
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ReDoS 検出の最先端 recheck の紹介 / State of the Art of ReDoS Detection
TheAlgorithms/Python: All Algorithms implemented in Python
アルゴリズムビジュアル大事典