أسرع طريقة لتشغيل بحث ثنائي على ملف في لغة C؟

Question

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

هل هناك طريقة أسرع للقيام بذلك؟هل يوجد شيء مثل lseek يعمل مع الخطوط بدلاً من البايتات؟

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

Answer 1

لا يمكنك البحث عن طريق الخط.إنه أمر واضح جدًا بمجرد التفكير فيه.

ولكن يمكنك إجراء نوع من البحث الثنائي على ملف نصي.

ما تفعله هو:

• قم بإحصاء الملف للحصول على الطول أو السعي إلى النهاية والحصول على الموضع.
• خريطة الذاكرة الملف.
  (أعتقد أن هذا هو الأفضل، ولكن يمكنك استخدام lseek وread إذا لزم الأمر.)
• ابحث عن منتصف الملف، مطروحًا منه متوسط ​​طول الخط.مجرد تخمين.
• قم بالمسح للأمام بحثًا عن سطر جديد، إلا إذا كنت في الموضع 0.
• اقرأ خطك وقارن.
• كرر ذلك لـ 1/4 أو 3/4، 1/8، 1/16، إلخ.

Answer 2

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

العديد من الطرق التي يمكنها استخدام هذا الوعي حول خصائص القرص I / O:

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

Answer 3

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

ما لم يكن كل الخطوط نفس الطول، أو لديك طول يمكن التنبؤ به للغاية، فلا توجد طريقة سهلة للبحث عن #N. ولكن، لأداء بحث ثنائي، كنت أعمل مع إزاحة البايت في البحث الثنائي وقراءة، قل 100 بايت (إذا كانت الكلمات أقل من 100 حرف) قبل وبعد الإزاحة - ما مجموعه 200 بايت. ثم قم بالمسح للحصول على NewLine قبل وبعد منتصفها لاستخراج الكلمة.

Answer 4

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

Answer 5

لن تكون هناك وظيفة "LSEEK"، لأن أوامر الملفات لا تحتوي على مفهوم "سطر" هذا المفهوم موجود في طبقة مختلفة من التجريد ثم أوامر الملف الخام.

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

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

Answer 6

كما ذكر أعلاه، نظرا لأن الملف هو ملف نصي، يمكن التنبؤ ب البايت الذي يبدأ فيه خط معين داخل الملف بشكل موثوق. فكرة البحث الثنائية ERSATZ هي فكرة جيدة جدا. لكنه حقا لن ينقذك طن ما لم يكن الملف ضخم، بالنظر إلى مدى سرعة I / O المتسلسل في الوقت الحاضر وكيف بطيء عشوائي I / O هو.

كما ذكرت، إذا كنت ستقرأها، فقد تبحث عنه بشكل خطي كما تذهب إليه. لذلك قم بذلك، استخدم بحثا عددا من Boyer-Moore كما تقرأه وستفعل جيدا.

Answer 7

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

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

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

خيار آخر يجب أن تفكر فيه هو Boyer-Moore String Starch. هذا هو البحث عن الوقت الخطي الفرعي واعتمادا على حجم نمط البحث، قد يكون أسرع من البحث الثنائي اللوغاريتمي. بوير مور جيد بشكل خاص مع سلاسل البحث الطويلة.

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

أشعر بالراحة في إجراء تنبؤ واحد فقط: إنه بالتأكيد يستحق تجنب القراءة في سطر واحد في وقت واحد مع شيء مثل readline() أو fgets(), ، لأن هذه الاستراتيجية تنطوي دائما على الاتصال malloc() لعقد محتويات الخط. تكلفة الاتصال malloc() على كل سطر من المرجح أن يسهل أي تكلفة بحث أو مقارنة.