نوع البيانات الضخمة والبحث

Question

لدي ملفان من البيانات ، 100 خط تشار لكل منهما. ملف A: 10⁸ الخطوط ، الملف ب: 10⁶ خطوط. وأحتاج إلى العثور على جميع الأوتار من الملف B والتي ليست في الملف A.
في البداية كنت أفكر في تغذية كلا الملفين إلى MySQL ، لكن يبدو أنه لن ينتهي أبدًا من إنشاء مفتاح فريد على 10⁸ السجلات.

أنا في انتظار اقتراحاتك حول هذا.

Answer 1

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

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

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

Answer 2

يمكنك التحسن قليلاً على إجابة Michael-Goldshteyn (https://stackoverflow.com/a/3926745/179529). نظرًا لأنك تحتاج إلى العثور على جميع الأوتار في B التي ليست موجودة في A ، يمكنك إزالة أي عنصر من جدول التجزئة لعناصر B ، عندما تقارن وإيجاد تطابق مع العناصر في A. العناصر التي سوف تبقى في جدول التجزئة هي العناصر التي لم يتم العثور عليها في الملف A.

Answer 3

بالنسبة للأحجام التي ذكرتها ، يجب أن تكون قادرًا على الاحتفاظ بكل من B في الذاكرة في وقت واحد ، حتى تتمكن من عمل نسخة مبسطة من إجابة Goldshteyn ؛ شيء من هذا القبيل في بيثون:

#!/usr/bin/python3

import sys

if __name__=='__main__':
  b = open(sys.argv[2],'r')
  bs = set()
  for l in b:
    bs.add(l.strip())
  b.close()
  a = open(sys.argv[1],'r')
  for l in a:
    l = l.strip()
    if l in bs:
      bs.remove(l)
  for x in bs:
    print(x)

لقد اختبرت هذا على ملفين من 10^5 و 10^7 في الحجم مع ~ 8 chars لكل سطر على معالج الذرة. الإخراج من/usr/bin/الوقت:

25.15user 0.27system 0:25.80elapsed 98%CPU (0avgtext+0avgdata 56032maxresident)k
0inputs+0outputs (0major+3862minor)pagefaults 0swaps
  60298   60298  509244