كيفية تحديد الاختلافات في قائمتين من البيانات

Question

هذا تمرين لرجال CS للتألق بالنظرية.

تخيل أن لديك حاويتين تحتويان على عناصر.المجلدات وعناوين URL والملفات والسلاسل، لا يهم حقًا.

ما هي الخوارزمية لحساب المضاف والمحذوف؟

يلاحظ:إذا كان هناك العديد من الطرق لحل هذه المشكلة، يرجى نشر واحدة لكل إجابة حتى يمكن تحليلها والتصويت عليها.

يحرر:جميع الإجابات تحل المسألة بأربع حاويات.هل من الممكن استخدام الرقم 2 الأولي فقط؟

Answer 1

بافتراض أن لديك قائمتين من العناصر الفريدة، والترتيب لا يهم، يمكنك التفكير فيهما كمجموعات بدلاً من قوائم

إذا كنت تفكر في مخطط فين، حيث تكون القائمة A كدائرة واحدة والقائمة B كالدائرة الأخرى، فإن تقاطع هاتين الدائرتين هو التجمع الثابت.

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

لذلك، قم بالتكرار من خلال A للبحث عن كل عنصر في B.إذا وجدته، قم بإزالته من كل من A وB

ثم A هي قائمة بالأشياء التي تم حذفها، وB هي قائمة بالأشياء التي تمت إضافتها

أظن...

[عدل] حسنًا، مع تقييد "حاويتين فقط" الجديد، لا يزال الأمر نفسه قائمًا:

foreach( A ) { 
  if( eleA NOT IN B ) {
    DELETED
  }
}
foreach( B ) {
  if( eleB NOT IN A ) {
    ADDED
  }
}

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

أود أن أزعم أن الحل الأول الخاص بي لم يستخدم 4 حاويات، بل دمر اثنتين فقط ؛-)

Answer 2

لم أفعل هذا منذ فترة ولكني أعتقد أن الخوارزمية تسير على هذا النحو ...

sort left-list and right-list
adds = {}
deletes = {}
get first right-item from right-list
get first left-item from left-list
while (either list has items)
  if left-item < right-item or right-list is empty
    add left-item to deletes
    get new left-item from left-list
  else if left-item > right-item or left-list is empty
    add right-item to adds
    get new right-item from right-list
  else
    get new right-item from right-list
    get new left-item from left-list

فيما يتعلق بعلاقة القائمة اليمنى بالقائمة اليسرى، يحذف يحتوي على العناصر التي تمت إزالتها و يضيف يحتوي الآن على عناصر جديدة.

Answer 3

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

Answer 4

معلومات مفقودة:كيف يمكنك تحديد المضافة/المحذوفة؟على سبيل المثالإذا كانت القائمتان (A وB) تعرضان نفس الدليل على الخادم A والخادم B، فهذا يعني أنهما متزامنان.إذا انتظرت الآن لمدة 10 أيام، وقمت بإنشاء القوائم مرة أخرى ومقارنتها، فكيف يمكنني معرفة ما إذا تمت إزالة شيء ما؟انا لااستطيع.لا يمكنني إلا أن أقول أن هناك ملفات على الخادم "أ" غير موجودة على الخادم "ب" و/أو العكس.سواء كان ذلك بسبب إضافة ملف إلى الخادم أ (وبالتالي لم يتم العثور على الملف على الخادم ب) أو أنه تم حذف ملف على الخادم ب (وبالتالي لم يتم العثور على الملف على الخادم ب) أي أكثر من ذلك) هو شيء لا يمكنني تحديده بمجرد وجود قائمة بأسماء الملفات.

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

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

في هذه الحالة، الحل الأبسط (وليس بالضرورة الأفضل) هو:

1. فرز القوائم القديمة.على سبيل المثالإذا كانت القائمة تتكون من سلاسل، قم بفرزها أبجديًا.يعد الفرز ضروريًا، لأنه يعني أنه يمكنني استخدام البحث الثنائي للعثور بسرعة على كائن في القائمة، على افتراض أنه موجود هناك (أو لتحديده بسرعة، فهو غير موجود في القائمة على الإطلاق).إذا لم يتم فرز القائمة، فإن العثور على الكائن له درجة تعقيد O(n) (أحتاج إلى إلقاء نظرة على كل عنصر في القائمة).إذا تم فرز القائمة، فسيكون التعقيد هو O(log n) فقط، لأنه بعد كل محاولة لمطابقة عنصر في القائمة، يمكنني دائمًا استبعاد 50٪ من العناصر الموجودة في القائمة غير متطابقة.حتى لو كانت القائمة تحتوي على 100 عنصر، فإن العثور على عنصر (أو اكتشاف أن العنصر غير موجود في القائمة) يستغرق 7 اختبارات على الأكثر (أم أنها 8؟على أية حال، أقل بكثير من 100). لا يلزم فرز القائمة الجديدة.

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

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

Answer 5

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

map1
map2
removedElements
addedElements

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}
list2.each |item|
{
    addedElements.add(item) unless map1.contains?(item)
}

نأسف للخلط الرهيب بين اللغات الوصفية بين Ruby وJava :-P

في النهاية تمت إزالة العناصر سيحتوي على العناصر التي تنتمي إلى القائمة 1، ولكن ليس إلى القائمة 2، و addElements سيحتوي على العناصر التي تنتمي إلى القائمة 2.

تكلفة العملية بأكملها هي O(4*N) نظرًا لأن البحث في الخريطة/القاموس قد يعتبر ثابتًا.من ناحية أخرى، سيؤدي البحث الخطي/الثنائي عن كل عنصر في القوائم إلى إنشاء O(N^2).

يحرر:بعد التفكير مرة أخرى، عند نقل الشيك الأخير إلى الحلقة الثانية، يمكنك إزالة إحدى الحلقات...لكن هذا قبيح...:)

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
    addedElements.add(item) unless map1.contains?(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}