Help us understand the problem. What is going on with this article?

生成した複数件のランダムな文字列において重複が発生しない確率は□%

はじめに

2019新卒 エンジニア Advent Calendar 2019 19 日目の記事です。

ソフトウエア開発において、ランダムな文字列を生成することがあります。例えば、アカウントの識別子(ID)という役割で利用されます。具体例としてTwitterでは、ユーザがアカウントを作成すると、長さ15のランダムな文字列をIDとして付与します。しかし、このような役割があるがゆえに、ランダムな文字列は重複してはいけません。それゆえ、万が一重複が発生したときに実行する相応の処理などもあるかと思います。

新卒として入社して以降、このような重複のないランダムな文字列を必要とするテストデータを作成する機会がありました。その時の興味として抱いていた、そもそもどれだけの確率で重複が発生するのか(上記、それ相応の処理が実行されることはあるのか)を明らかにしたいと思います。

※タイトルはトリビアの種のオマージュです。懐かしい番組ですね。🧠

実験

計算式

結果は以下の計算式で算出できます。

P = \prod_{k = 0}^{n} \frac{(c^l)-k}{c^l}

上記に示した計算式の各変数は以下の通りです。

  • c ・・・ランダムな文字列を構成する文字の種類
  • n ・・・ランダムな文字列の件数
  • l ・・・ランダムな文字列の長さ
  • P ・・・重複が発生しない確率

実数による確率の算出

今回の実験におけるランダムな文字列は、数字と英字(小文字)の合計36種の文字から構成されるものと定義します。(例:長さ10の場合、yttrj4ca8n)この場合、以下の計算式によって重複が発生しない確率が算出できます。

P = \prod_{k = 0}^{n} \frac{(36^l)-k}{36^l}

また今回の実験における他変数の値は以下とします。

  • n ・・・100,10000,1000000
  • l ・・・5,10,15

はじめに、以下の実数を当てはめます。Pythonのプログラムで計算します。

n = 100, 
l = 5
c = 36
n = 100
l = 5
P = 1

for k in range( n ):
    P = P * ((c ** l) - k) / (c ** l)

print(P)
0.999918139356006

重複が発生しない確率は99%以上ですね。

まとめて算出し、比較してみます。

  • 行:文字数
  • 列:件数
5 10 15
100 0.999918139356006 0.9999999999986461 1.0
10000 0.4374156133080636 0.9999999863258114 1.0
1000000 1.5e-322 0.9998632539253056 1.0

文字数10や15の場合ほとんど重複は発生しないようです。特に15は自分の環境におけるpythonによる計算ではわからない確率なんですね。

おわりに

ソフトウエア開発において、生成することもあろうランダムな文字列の生成について、重複が発生しない確率を算出しました。文字数が5だと少々怪しいですが、10や15の場合、100万件のランダムな文字列を精製したとしても、重複はほとんど発生しないことがわかりました。しかし、念には念をということで対応する処理の準備は必要ですね。

しかし、ここで強運を使ってしまうことだけは避けたいな…

(2019年12月20日追記)
以下の記事に掲載していただきました!ありがとうございます!

daikikatsuragawa
見習い。基本、自分のための備忘録を書きます。コードの指摘に喜びます。
https://qiita.com/daikikatsuragawa
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした