Zenn
Open2

uuid58の可変長・固定長で実際にどれくらいサイズが削減されるのか調べる

UUID
Base58
Nakano as a ServiceNakano as a Service
1 - \frac{パディングなし文字数の合計}{パディングあり文字数の合計} = \ 1 - \frac{\sum^{1億} uuid58().length}{22 \times 1億}

実際に計測1億回計算してみると

import { uuid58 } from "./index.ts";

const hist = new Map<number, number>();

for (let i = 0; i < 100000000; i++) {
  const uuid = uuid58();
  const len = uuid.length;
  hist.set(len, (hist.get(len) ?? 0) + 1);
}

console.log(hist);

console.log(
  1 - hist.entries().map(([len, count]) => {
        return len * count;
      }).reduce((a, b) => a + b, 0) / (22 * 100000000),
);

 deno hist.ts
Map(5) {
  22 => 96835085,
  21 => 3110272,
  20 => 53680,
  19 => 949,
  18 => 14
}
0.0014638795454545717
0.14 \%
Nakano as a ServiceNakano as a Service

パディングなしのuuid58が22文字になる確率は、先頭に1という文字がいくつ続くかで決まる。
1が0個の確率は\frac{57}{58}。
1が1個の確率は\frac{1}{58} \frac{57}{58}。
1が2個の確率は(\frac{1}{58})^2 \frac{57}{58}。
...
1がn個の確率は(\frac{1}{58})^n \frac{57}{58}。

期待される文字数は

22 \frac{57}{58} + 21\frac{1}{58} \frac{57}{58} + 20(\frac{1}{58})^2 \frac{57}{58} \dots = \sum_{k=0}^{22} (22 - k)(\frac{1}{58})^k(\frac{57}{58})

一方パディングありのuuid58の期待される文字数は常に22文字なので、

\frac{パディングなし文字数}{パディングあり文字数} = \frac{\sum_{k=0}^{22} (22 - k)(\frac{1}{58})^k(\frac{57}{58})}{22}

よって削減率は

1 - \frac{\sum_{k=0}^{22} (22 - k)(\frac{1}{58})^k(\frac{57}{58})}{22} \approx 0.0007974481658692185 \approx 0.0797\%

実測値の半分くらいなのは、22桁の58進数で表現できる情報量がUUIDの128bitよりも若干多く、先頭にパディングの1が来る確率が完全なランダムよりも若干高いため。