قائمة تخطي متزامنة وظيفية بحتة

Question

تخطي القوائم (بوغ ، 1990) توفير قواميس مصنفة مع عمليات لوجاريتمية مثل أشجار البحث ولكن القوائم تخطي أكثر قابلية للتحديثات المتزامنة.

هل من الممكن إنشاء قائمة تخطي متزامنة فعالة فعالة؟ إذا لم يكن الأمر كذلك ، فهل من الممكن إنشاء أي نوع من القاموس المتزامن الوظيفي الفعال؟

Answer 1

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

على وجه التحديد ، تتكون قوائم SKIP من الهياكل التي تبدو كذلك:

NODE1 ---------------------> NODE2 ---------...
  |                           |
  V                           V
NODE1a --> NODE1b ---------> NODE2a --> NODE2b --> NODE2c --- ...

الآن ، إذا كان لديك تحديث ، على سبيل المثال ، يحذف NODE2b أو NODE1b, ، يمكنك الاعتناء بها محليًا للغاية: أنت فقط تشير 2a إلى 2c أو 1a إلى 2a على التوالي وأنت تنتهي. لسوء الحظ ، نظرًا لأن العقد الورقية كلها تشير إلى بعضها البعض ، فهي ليست بنية جيدة لتحديث وظيفي (غير قابل للتغيير).

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

التحديثات المتزامنة لا تعمل بشكل جيد مع هياكل البيانات غير القابلة للتغيير. إذا كنت تفكر في ذلك ، فإن أي حل وظيفي لديه تحديث A كما f(A). إذا كنت تريد تحديثين ، يتم تقديمه f وواحد قدمه g, ، عليك أن تفعل f(g(A)) أو g(f(A)), أو عليك اعتراض الطلبات وإنشاء عملية جديدة h = f,g يمكنك تطبيق كل شيء دفعة واحدة (أو عليك القيام بأشياء أخرى ذكية للغاية).

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

وبالتالي ، من المحتمل أن يتم تنفيذ هياكل البيانات ذات الكتابة الثقيلة بشكل أفضل بشكل أفضل (وبشكل مثل قائمة تخطي حيث تحتاج فقط إلى القفل محليًا) ، بينما من المحتمل أن يتم تنفيذ هياكل البيانات الثقيلة بشكل أفضل (حيث تكون الشجرة هي بنية بيانات طبيعية أكثر ).

Answer 2

حل Andrew McKinlay هو الحل الوظيفي "الحقيقي" الحقيقي لقائمة تخطي حقيقية هنا ، ولكنه يحتوي على جانب سلبي. أنت تدفع وقت لوغاريتمي للوصول إلى عنصر ، ولكن الآن يصبح الطفرة خارج عنصر الرأس ميؤوسًا منها. يتم دفن الإجابة التي تريدها في عدد لا يحصى من السير!

هل يمكننا أن نفعل ما هو أفضل؟

جزء من المشكلة هو أن هناك مسارات متعددة من -infinity إلى العنصر الخاص بك.

ولكن إذا كنت تفكر في الخوارزميات للبحث في قائمة Skiplist ، فلن تستخدم هذه الحقيقة أبدًا.

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

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

الآن يمكننا أن نبدأ بقائمة تخطي بسيطة

-inf-------------------> 16
-inf ------> 8 --------> 16
-inf -> 4 -> 8 -> 12 --> 16

توسيعه حسب المستوى:

-inf-------------------> 16
  |                       |
  v                       v
-inf ------> 8 --------> 16
  |          |            |
  v          v            v
-inf -> 4 -> 8 -> 12 --> 16

قم بتجريد كل المؤشرات المفضلة:

-inf-------------------> 16
  |                       |
  v                       v
-inf ------> 8           16
  |          |            |
  v          v            v
-inf -> 4    8 -> 12     16

بعد ذلك ، يمكنك تحريك "إصبع" إلى وضع 8 من خلال تتبع جميع المؤشرات التي يجب أن تقلبها للوصول إلى هناك.

-inf ------------------> 16
   ^                      |
   |                      v
-inf <------ 8           16
   |         |            |
   v         v            v
-inf -> 4    8 -> 12     16

من هناك ، من الممكن حذف 8 ، ودفع الإصبع في مكان آخر ، ويمكنك الاستمرار في التنقل عبر الهيكل بالإصبع.

نظرت إلى هذه الطريقة ، يمكننا أن نرى أن المسارات المميزة في قائمة تخطي تشكل شجرة تمتد!

إن نقل خطوة واحدة مع الإصبع هو عملية O (1) إذا كان لديك مؤشرات متميزة فقط في الشجرة واستخدام "العقد النحيفة" مثل هذا. إذا كنت تستخدم العقد الدهنية ، فإن حركة الإصبع اليسرى/اليمين ستكون أكثر تكلفة.

تبقى جميع العمليات o (log n) ويمكنك استخدام بنية قائمة تخطي عشوائية أو واحدة حتمية كالمعتاد.

ومع ذلك ، عندما نقوم بفك قائمة Skiplist إلى فكرة مسار مفضل ، فإننا نحصل على أن قائمة التخطي هي مجرد شجرة مع بعض الروابط غير المسبقة الزائدة التي لا نحتاجها لإدراج/بحث/حذف طول كل من هذه المسارات من أعلى اليمين هو o (log n) إما مع احتمال كبير أو مضمون اعتمادًا على استراتيجية التحديث الخاصة بك.

حتى بدون الإصبع ، يمكنك الحفاظ على الوقت المتوقع O (سجل n) لكل إدراج/حذف/تحديث في شجرة مع هذا النموذج.

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

Answer 3

ليست قائمة تخطي ، ولكن يبدو أنها تتطابق مع وصف المشكلة: أشجار Clojure الحمراء السوداء المستمرة (انظر ProsistiveTreemap.Java). المصدر يحتوي على هذا الإشعار:

/**
 * Persistent Red Black Tree
 * Note that instances of this class are constant values
 * i.e. add/remove etc return new values
 * <p/>
 * See Okasaki, Kahrs, Larsen et al
 */

تحافظ هذه الأشجار على ترتيب العناصر و "ثابتة" بالمعنى الذي يستخدم به Rich Hickey الكلمة (غير قابلة للتغيير وقادرة على الحفاظ على ضمانات أدائها عند إنشاء الإصدارات المحدثة).

في حال كنت ترغب في اللعب معهم ، يمكنك بناء مثيلات في رمز clojure مع الوظيفة sorted-map.

Answer 4

إذا كنت بحاجة فقط إلى سلبيات في مقدمة قائمة التخطي ، فيجب أن يكون من الممكن إنشاء نسخة ثابتة ثابتة.

ميزة هذا النوع من قائمة التخطي ستكون "الوصول العشوائي". على سبيل المثال ، يمكنك الوصول إلى العنصر n'th بشكل أسرع مما تستطيع في قائمة واحدة مرتبطة بمنفردة.