إنشاء uid نمط Tinyurl الخاص بك

https://stackoverflow.com/questions/190701

07-07-2019
|

سؤال

أنا أكتب مقالًا صغيرًا عن البدائل التي يمكن قراءتها بشريًا للمرشدين/معرفات المستخدم، على سبيل المثال تلك المستخدمة في TinyURL لتجزئة عنوان url (والتي غالبًا ما تُطبع في المجلات، لذا يجب أن تكون قصيرة).

المعرف البسيط الذي أقوم بإنشائه هو - 6 أحرف:إما حرف صغير (a-z) أو 0-9.

"وفقًا لقائد حساباتي"، فإن هذه 6 أحداث متنافية، على الرغم من أن حساب احتمالية الاصطدام يصبح أصعب قليلاً من P(A أو B) = P(A) + P(B)، لأنه من الواضح أنه يتضمن أرقامًا ومن الرمز أدناه، يمكنك أن ترى أنه يعمل على استخدام رقم أو حرف باستخدام 50/50.

أنا مهتم بمعدل الصدام وإذا كان الكود أدناه عبارة عن محاكاة واقعية لمعدل الصدام المتوقع الذي ستحصل عليه من إنشاء علامة التجزئة.في المتوسط، أحصل على 40-50 اشتباكًا لكل مليون، ولكن ضع في اعتبارك أن المعرف لن يتم إنشاؤه مليون مرة في وقت واحد، ولكن ربما حوالي 10-1000 مرة في الدقيقة فقط.

ما هو احتمال حدوث تصادم في كل مرة، وهل يمكن لأي شخص أن يقترح طريقة أفضل للقيام بذلك؟

static Random _random = new Random();

public static void main()
{
    // Size of the key, 6
    HashSet<string> set = new HashSet<string>();
    int clashes = 0;
    for (int n=0;n < 1000000;n++)
    {
        StringBuilder builder = new StringBuilder();

        for (int i =0;i < 7;i++)
        {
            if (_random.NextDouble() > 0.5)
            {
                builder.Append((char)_random.Next(97,123));
            }
            else
            {
                builder.Append(_random.Next(0,9).ToString());
            }
        }

        if (set.Contains(builder.ToString()))
        {
            clashes++;
            Console.WriteLine("clash: (" +n+ ")" +builder.ToString());
        }

        set.Add(builder.ToString());
        _random.Next();
        //Console.Write(builder.ToString());
    }

    Console.WriteLine("Clashes: " +clashes);
    Console.ReadLine();
}

تحديث: وهنا المادة الناتجة من هذا السؤال

لقد طرحت سؤالين هنا حقًا لذلك كنت أغش.الإجابة التي كنت أبحث عنها كانت rcar، ولكن Sklivvz هي أيضًا الإجابة على الجزء الثاني (بديل).هل من الممكن إنشاء منشئ معرف فريد مخصص في قاعدة بيانات، أم أنه من جانب العميل (أيهما قد يكون قراءتين محتملتين أولاً)؟

الفكرة العامة التي كنت أسعى إليها هي استخدام المعرفات في قواعد البيانات أو المتاجر الأخرى التي يمكن استخدامها عن طريق الهاتف أو المواد المطبوعة، وليس دليلًا عملاقًا مكونًا من 16 بايت.

التحديث 2: لقد وضعت صيغة حدثين متنافيين أعلاه بدلاً من حدثين مستقلين (حيث أن الحصول على "a" في المرة الأولى لا يعني أنه لا يمكنك الحصول على "a" في المرة الثانية).كان ينبغي أن يكون P(A وB) = P(A) × P(B)

المحلول

احتمال الاصطدام بمعرف واحد محدد هو:

p = ( 0.5 * ( (0.5*1/10) + (0.5*1/26) ) )^6

وهو حوالي 1.7×10^-9.

احتمال حدوث تصادم بعد إنشاء معرفات n هو 1-p^n، لذلك سيكون لديك تقريبًا فرصة تصادم بنسبة 0.17% لكل إدخال جديد بعد إدراج مليون معرف، وحوالي 1.7% بعد 10 ملايين معرف، و حوالي 16% بعد 100 مليون.

1000 معرف في الدقيقة يصل إلى حوالي 43 مليونًا في الشهر، لذا كما أشار Sklivvz، فإن استخدام بعض المعرفات المتزايدة ربما يكون طريقة أفضل في هذه الحالة.

يحرر:

لشرح العملية الحسابية، يقوم أساسًا بقلب العملة ثم اختيار رقم أو حرف 6 مرات.هناك احتمال 0.5 أن تتطابق العملة المعدنية، وبعد ذلك في 50% من الوقت يكون هناك احتمال 1/10 للمطابقة وفرصة 50% لاحتمال 1/26 للمطابقة.ويحدث ذلك 6 مرات بشكل مستقل، لذا يمكنك مضاعفة هذه الاحتمالات معًا.

نصائح أخرى

لماذا تريد استخدام وظيفة عشوائية؟لقد افترضت دائمًا أن tinyurl يستخدم تمثيلًا أساسيًا 62 (0-9A-Za-z) لمعرف متسلسل.لا توجد اشتباكات وعناوين URL تكون دائمًا قصيرة قدر الإمكان.

سيكون لديك جدول DB مثل

Id  URL
 1  http://google.com
 2  ...
... ...
156 ...
... ...

وستكون عناوين URL المقابلة هي:

http://example.com/1
http://example.com/2
...
http://example.com/2W
...

ابحث عن مفارقة عيد الميلاد, ، إنها المشكلة التي تواجهها بالضبط.

السؤال هو:كم عدد الأشخاص الذين تحتاجهم للاجتماع في غرفة واحدة، بحيث يكون لديك فرصة بنسبة 50% لوجود شخصين لهما نفس تاريخ الميلاد؟الجواب قد يفاجئك.

لقد فعلت هذا بالضبط منذ بعض الوقت، واتبعت الطريقة التي ذكرها Sklivvz.تم تطوير المنطق بأكمله باستخدام إجراء مخزن لخادم SQL واثنين من UDF (وظائف يحددها المستخدم).الخطوات كانت:

لنفترض أنك تريد تقصير عنوان URL هذا: إنشاء uid نمط Tinyurl الخاص بك
أدخل عنوان URL في جدول
الحصول على قيمة @@identity للإدراج الأخير (معرف رقمي)
قم بتحويل المعرف إلى قيمة أبجدية رقمية مقابلة، بناءً على "مجال" من الحروف والأرقام (لقد استخدمت هذه المجموعة بالفعل:"0123456789abcdefghijklmnopqrstuvwxyz")
قم بإرجاع هذه القيمة مرة أخرى، مثل "cc0"

تم التحويل من خلال بضع UDF قصير جدًا.

إن إجراء تحويلين يتم استدعاؤهما واحدًا تلو الآخر سيُرجع قيمًا "متسلسلة" مثل هذه:

select dbo.FX_CONV (123456) -- returns "1f5n"

select dbo.FX_CONV (123457) -- returns "1f5o"

إذا كنت مهتمًا فيمكنني مشاركة رمز UDF.

لماذا لا تستخدم فقط خوارزمية التجزئة؟واستخدام تجزئة عنوان url؟

إذا كنت تستخدم أرقامًا عشوائية، فمن المحتمل أن تحصل على اشتباكات لأنها غير محددة.

التجزئة ليست فريدة بشكل يمكن إثباته، ولكن هناك فرصة جيدة إلى حد ما لأن تكون تجزئة السلسلة فريدة.

تصحيح

في الواقع انتظر إذا كنت تريد أن تكون قابلة للقراءة إنسانيًا ...إذا وضعتها في الشكل السداسي فهي قابلة للقراءة من الناحية الفنية.

أو يمكنك استخدام خوارزمية تقوم بتحويل التجزئة إلى سلسلة يمكن قراءتها بواسطة الإنسان.إذا كانت السلسلة القابلة للقراءة بشريًا تمثل تمثيلًا مختلفًا للتجزئة، فيجب أيضًا أن تكون "فريدة" مثل التجزئة، أي الأساس 36 للتجزئة الأصلية.

سأقوم بإنشاء قيمة عشوائية تمثل البيانات التي ستقوم بتجزئتها، ثم قم بتجزئة ذلك والتحقق من clahses بدلاً من محاولة المحاكاة باستخدام تجزئات عشوائية مصنوعة يدويًا.هذا سوف يعطيك مؤشر أفضل.وسيكون لديك المزيد من العشوائية لأنه سيكون لديك المزيد من العشوائية (بافتراض أن بياناتك التي سيتم تجزئتها أكبر :)).

إذا كنت تستخدم 6 أحرف، a-z و0-9، فسيكون إجمالي 36 حرفًا.وبالتالي فإن عدد التباديل هو 36^6 وهو 2176782336..لذلك يجب أن يتعارض فقط 1/2176782336 مرة.

من ويكيبيديا:

عند الرغبة في طباعة عدد أقل من الأحرف، يتم أحيانًا ترميز المعرفات الفريدة العمومية (GUIDs) في سلسلة base64 أو Ascii85.يتكون المعرف الفريد العمومي (GUID) المشفر باستخدام Base64 من 22 إلى 24 حرفًا (اعتمادًا على المساحة المتروكة)، على سبيل المثال:

7QDBkvCA1+B9K/U0vrQx1A
7QDBkvCA1+B9K/U0vrQx1A==

وترميز Ascii85 يعطي 20 حرفًا فقط، على سبيل المثال.ز.:

5:$Hj:Pf\4RLB9%kU\Lj

لذلك، إذا كنت مهتمًا بالتفرد، فإن المعرف الفريد العمومي (GUID) المشفر باستخدام Base64 يجعلك أقرب إلى ما تريده، على الرغم من أنه لا يتكون من 6 أحرف.

من الأفضل العمل بالبايت أولاً، ثم ترجمة تلك البايتات إلى نظام سداسي عشري للعرض، بدلاً من العمل مع الأحرف مباشرةً.

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow