حتمية التعامل مع خوارزمية تخصيص

Question

أنا أحاول العثور على كفاءة القطعية طريقة تخصيص 32 بت التعامل في مثل هذه الطريقة أنها سوف تعمل لأجل غير مسمى.بسيطة تزايد العداد لا يعمل لأنه في نهاية المطاف حلقة حولها.وتمتد إلى 64-بت غير ممكن لأن القيم التي سيتم استخدامها في شبكة بروتوكول تتوقع قيمة 32 بت.

إنه في الوقت الحقيقي النظام لذا يجب أن يكون محددا و سريعة.على الرغم من أنه سوف ينتهي في قاعدة بيانات SQLite لا أستطيع القوة الغاشمة اختبار كل مفتاح بعد حلقة حول على سبيل المثال...

أعتقد أن ما أريد هو نوع من مجموعة شجرة أن يعرف عن كل المخصصة سابقا مقابض (ملء هذا في البدء على ما يرام).يبدو أن هذا المشتركة(العش) نوع من المشكلة ولكن ليس هذا هو حلها عن طريق زيادة أو المحكمة الخاصة بلبنان.

أي نصائح ؟

تحرير:بعض توضيحات إضافية.أتطلع أن يكون شيء من أجل من 200 ألف النشطة يعالج في النظام في أي وقت واحد.مقابض يتم حذف على أساس عشوائي.

Answer 1

وأنت لا يمكن تخصيص أكثر من 2 ^ 32. ولكن يمكنك تخصيص مقابض المستخدمة إذا كان يتم اطلاق سراحهم والمشكلة لتتبع مقابض الحرة.

والشجرة هو وسيلة جيدة لتخزين مقابض الحرة. كل عقدة لديه أدنى وأعلى المقبض، والشجرة الفرعية ترك تحتوي على مقابض التي هي أقل من أدنى والشجرة الفرعية الصحيحة تحتوي على مقابض التي هي أكبر من أعلى.

مثال:

            6-9
            / \
           2   15
          / \
         0   4

إذا يتم تحريرها مقبض، يتم تخزينه في الشجرة. على سبيل المثال، إذا تم الإفراج عن 10، وشجرة تبدو مثل:

            6-10
            / \
           2   15
          / \
         0   4

إذا يتم تحريرها مقبض 5، يمكنك اختيار لتحسين شجرة ل4 يمكن إضافتها إلى العقدة 5-10 وأهلا وسهلا:

            5-10
            / \
           2   15
          / \
         0   4

ل:

            4-10
            / \
           2   15
          / 
         0  

وتخصيص مقبض، يبحث عن عقدة ورقة مع 1 مقبض ويزيل فإنه من شجرة. إذا لم تكن هناك أوراق مع 1 مقبض، ومجرد استخدام ورقة وإنقاص الجانب غير متصل إلى الأصل:

         4-10
        /
      1-2

في المثال أعلاه يمكننا تخصيص 1 و 2 لا لأنه إذا كان يتم تحريرها 3، يمكنك الجمع بين ذلك مع 4 وتريد للحفاظ على عدد العقد عند أدنى مستوى ممكن.

وفيما يلي خوارزمية شبة الكود. يتم ترك بعض أجزاء للقارئ:

Node = ( int lowest, highest; [Node] left, right)


Node.Allocate() 
  if TryFindLonelyLeaf(handle)    return handle;
  else
    return FindLeafHandle(NULL);

Node.TryFindLonelyLeaf(handle)
  if (left == NULL & right == NULL) 
    if (lowest == highest)
      handle == lowest;
      return TRUE;
    else
      return FALSE;
  if (left != NULL & left.TryFindLonelyLeaf(handle))
    if (left.lowest == handle) 
      left == NULL; // Free node
    return TRUE;
  elsif (right != NULL & right.TryFindLonelyLeaf(handle))
    if (right.lowest == handle)
       right = NULL; // Free node
    return TRUE;
  else
    return FALSE;

Node.FindLeafHhandle(parent)
  if (left == NULL & right == NULL) 
    if (parent == NULL | parent.right == this) 
      handle = lowest;
      lowest++;
    else
      handle = highest;
      highest--;
    return handle;
  else if (left != NULL) 
    return left.FindLeafHandle();
  else // right != NULL
    return right.FindLeafHandle();

Node.DeAllocate(handle) 
  Assert(handle<lowest or handle>highest);
  if (handle == lowest-1)
    lowest = CompactLeft(handle);
  elsif (handle == lowest+1)
    highest = CompactRight(handle); 
  elsif (handle<lowest)          
    if (left == NULL)
      left = (handle, handle, NULL, NULL);
    else
      left.DeAllocate(handle);
  elsif (handle>highest)
    if (right == NULL)
      right = (handle, handle, NULL, NULL);
    else
      right.DeAllocate(handle);
  else ERROR           

Node.CompactLeft(handle)
  if (highest == handle-1) 
    handle = lowest;
    // deallocate node and replace with left subtree
    return handle;
  elsif (right != NULL) 
    return right.CompactLeft(handle)
  else
    return handle;

Node.CompactRight(handle)
  if (lowest == handle+1) 
    handle = highest;
    // deallocate node and replace with right subtree
    return handle;
  elsif (left != NULL) 
    return left.CompactRight(handle)
  else
    return handle;

Answer 2

إذا الذاكرة ليست قضية، ثم هل يمكن الحفاظ على قائمة مقابض الحرة. عندما يتم تحريرها واحدة، يمكنك إضافته إلى نهاية القائمة الحرة.

في البداية، يمكن إضافة كافة id لقائمة حرة، لكنها ستكون غير فعالة.

ووالأمثل يمكن القيام به هو أن تحافظ على قيمة الحد الأدنى للهوية المتاحة، فضلا عن قائمة حرة. وذلك عندما القائمة فارغة، يمكنك إضافة عدد من هويات (بدءا من قيمة id الدنيا كنت الحفاظ على) إلى قائمة حرة وتحديث الحد الأدنى لقيمة id.

Answer 3

إذا كان هذا السؤال هو "كيف يمكنني بسرعة وأمان ، وحساب فريدة من نوعها, غير المستخدمة حاليا ، رقم" ، ثم قليلا-الجدول أن أعطيك هذا.

من أجل 200 ألف أرقام 200.000 / 8 = عدد وحدات البايت المطلوبة = 25000 الذي هو مجرد خجولة من 25كيلو بايت من الذاكرة لتعقب.

بالطبع, إذا كنت بحاجة إلى تتبع البيانات المرتبطة في استخدام مقابض, في الذاكرة, ثم كنت بحاجة إلى شيء آخر.

حل آخر ، من الممكن أن يكون أسرع للحصول على التعامل مع الجديد من خلال سيكون للحفاظ على كومة من غير مستخدمة مقابض.في كل مرة كنت بحاجة إلى التعامل معها ، البوب واحد من المكدس.

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

منذ كنت سوف يكون حوالي 200 ألف مقابض يعيش في أي وقت, هذا المكدس يجب أبدا أن تنمو أكبر من عقد أن العديد من عدد المقابض ، لذلك يمكن بسهولة التعامل مع هذا مع صفيف.200 دولار 32 بت كومة سوف تستهلك 800.000 بايت, حول 781KB من الذاكرة.