上記の質問に具体的な数値を追加するために、質問に記載されている行に沿って ID を生成する小さなプログラムを実装しました。これらは、試用実行の 1 つの結果でした。
Length Count MD5 Base 62
4 400 3d0e 446
5 925 4fc04 1Myi
6 2434 0e9368 40V6
7 29155 e406d96 GBFiA
8 130615 7ba787c8 2GOiCm
9 403040 75525d163 YNKjL9
10 1302992 e1b3581f52 H47JAIs
Total: 1869561
ハッシュの長さが増加するたびに衝突が発生したため、この例では 6 回の衝突が発生しました。カウントは、衝突の前に生成された特定の長さのキーの数です。MD5 列には、重複キー エラーが発生する前に正常に追加された最後の切り詰められたキーが表示されます。右端の列には、ベース 62 のキーが表示されます (変換が正しく行われた場合)。
文字が追加されるたびに、ますます多くのキーが生成されているように見えますが、これはご想像のとおりです。このアプローチがユーザー生成コンテンツに合わせて拡張されることを願っています。
興味のある方のために、最後の列のベース 62 表現を取得する方法を次に示します。
def base_62_encode(input):
"Inspired by code at http://en.wikipedia.org/wiki/Base_36."
CLIST="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
rv = ""
while input != 0:
rv = CLIST[input % 62] + str(rv)
input /= 62
return rv
base62_id = base_62_encode(long(truncated_hash, 16))
(後で追加:)
これは、Google App Engine のコンテキストでこれらの ID の生成に関連するいくつかの処理を行うクラスです。デフォルトでは、GAE キー名の最初の文字はアルファベットでなければならないため、このクラスによって生成されるキーは純粋なベース 62 ではありません。ここでは、最初の文字に base 52 を使用することで、この要件に対応しています。
コンストラクターに渡された (またはコンストラクターから省略された) "clist" 値を変更することにより、プライマリ ベースを 62 以外の値に変更できます。たとえば、「1」、「l」、「i」など、混同しやすい文字を削除したい場合があります。
使用法：
keygen = LengthBackoffIdGenerator(SomeClass, initial_length=5)
small_id, modified = keygen.small_id(seed_value_from_sharded_counter)
クラスは次のとおりです。
class LengthBackoffIdGenerator(object):
"""Class to generate ids along the lines of tinyurl.
By default, ids begin with a alphabetic character. Each id that is created is checked against previous ones
to ensure uniqueness. When a duplicate is generated, the length of the seed value used is increased by one
character.
Ids become gradually longer over time while remaining relatively short, and there are very few retries in
relation to the number of keys generated.
"""
ids = set()
def __init__(self, cls, clist='0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', alpha_first=False,
initial_length=5, check_db=False):
self.clist = clist
self.alpha_first = alpha_first
if self.alpha_first:
import re
alpha_list = re.sub(r'\d', '', clist)
if len(alpha_list) < 1:
raise Exception, 'At least one non-numeric character is required.'
self.alpha_list = alpha_list
self.cls = cls
self.length = initial_length
self.check_db = check_db
def divide_long_and_convert(self, radix, clist, input, rv):
"Inspired by code at http://en.wikipedia.org/wiki/Base_36."
rv += clist[input % radix]
input /= radix
return (input, rv)
def convert_long(self, input):
rv = ""
if self.alpha_first:
input, rv = self.divide_long_and_convert(len(self.alpha_list), self.alpha_list, input, rv)
while input != 0:
input, rv = self.divide_long_and_convert(len(self.clist), self.clist, input, rv)
return rv
def hash_truncate_and_binify(self, input, length):
"""Compute the MD5 hash of an input string, truncate it and convert it to a long.
input - A seed value.
length - The length to truncate the MD5 hash to.
"""
from assessment.core.functions import md5_hash
input = md5_hash(input)[0:length]
return long(input, 16)
def _small_id(self, input):
"""Create an ID that looks similar to a tinyurl ID.
The first letter of the ID will be non-numeric by default.
"""
return self.convert_long(self.hash_truncate_and_binify(input, self.length))
def small_id(self, seed):
key_name = self._small_id(seed)
increased_length = False
if self.check_db and not self.cls.get_by_key_name(key_name) is None:
self.ids.add(key_name)
if key_name in self.ids:
self.length += 1
increased_length = True
key_name = self._small_id(seed)
self.ids.add(key_name)
return (key_name, increased_length)