重複のない10桁の数字をIDとして採番するアルゴリズムを教えて下さい。


但し、下記の条件があります。

- 最低でも1億以上、採番可能なもの
- 時系列や連番など推測されやすいものはNG
- 基本的にデータベースを使用せずアルゴリズム内だけて採番(但しカウントアップ用で使うならOK)
- 数字が一意であると保証されていること

以上になります。

PHPのコードで書かれてると、なお有り難いです、
宜しくお願いします。

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2013/08/26 07:16:11
  • 終了:2013/08/27 10:56:22

ベストアンサー

id:Sampo No.4

Sampo回答回数556ベストアンサー獲得回数1042013/08/26 23:32:47

ポイント150pt

Lhankor_Mhyさんがコメントでご指摘の通り、どういう使い方をするスクランブル値なのかを考慮しないと的外れになりますよね。

質問文に使い方が書いていないので推測せざるを得ないのですがPHPを使っている以上Webアプリであり、「採番」というからには一度のアクセスで一気に1億個のユニークナンバーがほしいのではなくアクセスかなにかリクエストのたびにユニークナンバーを発生させたいことと推測します。

さて、カウントアップが利用できるならその連番数をスクランブルすることで予測の困難なユニーク値を生成できます。

以前書いたブログ記事ですが
http://cs.hatenablog.jp/entry/2013/06/19/135527
これはC言語版なのでPHP的に書き直すと

{
	// 奇数その1の乗算
	$v *= 0x1ca7bc5b;
	$v &= 0x7FFFFFFF; // 下位31ビットだけ残して正の数であることを保つ

	// ビット上下逆転
	$v = ($v >> 15) | (($v & 0x7FFF) << 16);

	// 奇数その2(奇数その1の逆数)の乗算
	$v *= 0x6b5f13d3;
	$v &= 0x7FFFFFFF; // 下位31ビットだけ残して正の数であることを保つ

	// ビット上下逆転
	$v = ($v >> 15) | (($v & 0x7FFF) << 16);

	// 奇数その1の乗算
	$v *= 0x1ca7bc5b;
	$v &= 0x7FFFFFFF; // 下位31ビットだけ残して正の数であることを保つ

	return $v;
}

ビット逆順の代わりにビット上下逆転を使っています。
奇数を3回かけていますが、スクランブルするだけならこの奇数にはどんな数字を使ってもかまいません。

他3件のコメントを見る
id:wankodon

ご指摘頂いた通り、リクエスト毎にIDを採番しておきたかったのです。
他の方には申し訳ないのですが、このような実装を望んでいました!
回答どうも有り難うございます。

2013/08/27 10:52:24
id:Sampo

数学的には
【コンピュータの扱う自然数(2のべき乗を位数とする巡回群)のそれぞれの元は奇数定数をかけると必ず相異なる結果になる】
のを利用しているわけですが、これはもう少し一般的な形で
【位数nの巡回群のそれぞれの元は、定数p(p<n, pとnは互いに素)をかけると必ず相異なる結果になる】
と言い換えましょうか。

このことは
【位数nの巡回群の元p(p<n, pとnは互いに素)には逆数が存在する】
という事実から導けると思います。

逆数が存在することが名前の付いた定理になっていたかどうかは忘れましたが、逆数そのものは拡張ユークリッド互除法という計算方法で機械的に求まります。

2013/08/27 11:48:12

その他の回答(3件)

id:taknt No.1

きゃづみぃ回答回数13537ベストアンサー獲得回数11982013/08/26 07:41:27

ポイント75pt

まず1億分の配列に連番で取得させます。

その後、配列をランダムにします。

あとは採番のときに 順に配列から値を取得すればいいです。

他1件のコメントを見る
id:taknt

連番にしないで たとえば 123ごとに 採番するようにするとかしたらいかがでしょうか?

また それをプラスではなく、マイナスさせていくとかすれば 推測しにくいと思われます。

2013/08/27 10:25:47
id:wankodon

お手軽に実装するにアリかも知れませんが、1億以上も配列を作成するのはちょっと、、
ともあれ回答有り難うございます。

2013/08/27 10:35:41
id:holoholobird No.2

holoholobird回答回数574ベストアンサー獲得回数1042013/08/26 09:41:51

ポイント75pt

idの重複を確実になくすならこれしか方法はないと思います。

<?php
$p=100;
$temp=range(1,$p);
shuffle($temp);
print_r($temp);
?>

たとえば上の例だと$p=100なので、$tempは1~100までの数字を重複なしにランダムに格納した、100の要素の配列になります。

$pの数字は適当にかえてください。

http://codepad.org/KfMrQ2u2
↑こういう結果になります。

id:wankodon

回答有り難うございます。参考にさせて頂きます。

2013/08/27 10:40:49
id:dawakaki No.3

だわかき回答回数797ベストアンサー獲得回数1222013/08/26 19:26:00

ポイント75pt

No.2の回答では連番生成されるので、簡単にIDが推測されてしまいます。
推測がしにくいユニークIDを発生させる方法としては、uniqid関数とmd5関数の組み合わせが考えられます。

以下のスクリプトは、ユニークIDを10進数10桁に変換し、配列$arrの添え字として1億個を発生させるものです。

$arr = array();
while (count($arr) <= 100000000) {
    $id = md5(uniqid(rand(),1));
    $id = substr(hexdec($id), 0, 10);

    $arr[$id] = TRUE;
}
他6件のコメントを見る
id:dawakaki

一気に1億個のユニークIDを発行するのではなく、その都度発行ということでしたら、以前のIDと重ならないように判断するために、以前のIDをすべてどこかに保存しておく必要があります。
ユーザーIDとして使っているなら、ユーザー管理DBがあるはずですから、それを使うのが妥当だと思います。

2013/08/27 06:52:45
id:wankodon

申し訳ありません。ご指摘通り都度発行でIDを採番したかったのです。
このようなやり方もあるんですね。回答有り難うございました。

2013/08/27 10:47:29
id:Sampo No.4

Sampo回答回数556ベストアンサー獲得回数1042013/08/26 23:32:47ここでベストアンサー

ポイント150pt

Lhankor_Mhyさんがコメントでご指摘の通り、どういう使い方をするスクランブル値なのかを考慮しないと的外れになりますよね。

質問文に使い方が書いていないので推測せざるを得ないのですがPHPを使っている以上Webアプリであり、「採番」というからには一度のアクセスで一気に1億個のユニークナンバーがほしいのではなくアクセスかなにかリクエストのたびにユニークナンバーを発生させたいことと推測します。

さて、カウントアップが利用できるならその連番数をスクランブルすることで予測の困難なユニーク値を生成できます。

以前書いたブログ記事ですが
http://cs.hatenablog.jp/entry/2013/06/19/135527
これはC言語版なのでPHP的に書き直すと

{
	// 奇数その1の乗算
	$v *= 0x1ca7bc5b;
	$v &= 0x7FFFFFFF; // 下位31ビットだけ残して正の数であることを保つ

	// ビット上下逆転
	$v = ($v >> 15) | (($v & 0x7FFF) << 16);

	// 奇数その2(奇数その1の逆数)の乗算
	$v *= 0x6b5f13d3;
	$v &= 0x7FFFFFFF; // 下位31ビットだけ残して正の数であることを保つ

	// ビット上下逆転
	$v = ($v >> 15) | (($v & 0x7FFF) << 16);

	// 奇数その1の乗算
	$v *= 0x1ca7bc5b;
	$v &= 0x7FFFFFFF; // 下位31ビットだけ残して正の数であることを保つ

	return $v;
}

ビット逆順の代わりにビット上下逆転を使っています。
奇数を3回かけていますが、スクランブルするだけならこの奇数にはどんな数字を使ってもかまいません。

他3件のコメントを見る
id:wankodon

ご指摘頂いた通り、リクエスト毎にIDを採番しておきたかったのです。
他の方には申し訳ないのですが、このような実装を望んでいました!
回答どうも有り難うございます。

2013/08/27 10:52:24
id:Sampo

数学的には
【コンピュータの扱う自然数(2のべき乗を位数とする巡回群)のそれぞれの元は奇数定数をかけると必ず相異なる結果になる】
のを利用しているわけですが、これはもう少し一般的な形で
【位数nの巡回群のそれぞれの元は、定数p(p<n, pとnは互いに素)をかけると必ず相異なる結果になる】
と言い換えましょうか。

このことは
【位数nの巡回群の元p(p<n, pとnは互いに素)には逆数が存在する】
という事実から導けると思います。

逆数が存在することが名前の付いた定理になっていたかどうかは忘れましたが、逆数そのものは拡張ユークリッド互除法という計算方法で機械的に求まります。

2013/08/27 11:48:12
  • id:Lhankor_Mhy
    回答No.1とNo.2は「基本的にデータベースを使用せず」って書いてあるの読んでから回答した方がいいと思うんだが。その1億件のIDをDBに入れずにどうするつもりでその回答なんだ?
  • id:standard_one
    M系列の疑似乱数なら同じ値の繰り返しになるので、適当なシード値とXORマスクを用意して
    乱数生成 → 1億未満または11桁以上なら乱数生成に戻る → 乱数取出し → 生成した乱数をシードにして先頭に戻る
    で目的達成ですね。
    10進数で10桁必要なら34ビットで乱数生成すればいいです。
    コード書こうかと思ったんですがダルいので他の人に譲ります。ということで回答ではなくコメントにしておきます。
    なぜこれで数字が一意であると保証されるかは…ビット演算の説明から入らないといけないので自習してみてください。
    当然一周したら(100億以上の値を出力したら)同じ値が出ます。
  • id:Lhankor_Mhy
    ↑横ですが勉強になりました。ありがとうございます。
    実装には「乱数生成→出力→シード保存」の間は排他処理しないといけないと思うので、質問者はその辺を気をつけたほうがいいでしょうね。
  • id:Lhankor_Mhy
    回答No.3もさあ……、なんで指摘済みのこと繰り返すかな。
     
    その要素数1億の配列をどうするつもりなんだってば。シリアライズしてテキストファイルにでも保存しておくの?
    つーかそもそも、「連番生成される」って指摘してるけどshuffle関数で破壊的に配列の順番を入れ替えてるじゃん。
     
    IT漫才という新ジャンルを見てる気分になってきたよw
  • id:dawakaki
    コメント欄で回答を批判している時間があるのでしたら、これが正解というものを回答されてはいかがですか?
  • id:wankodon
    色々実装があるものなんですね。うーん、勉強になります。
    これにて回答を締め切らせて頂きます。皆様有り難うございました。

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません