التعقيد الخوارزمي لموزعي/مدققي XML

Question

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

تحديث

في مقال في مجلة IEEE للكمبيوتر، المجلد 41 العدد 9، سبتمبر 2008، قام المؤلفون بمسح أربعة نماذج شائعة لتحليل XML (DOM، SAX، StAX وVTD).يقومون بإجراء بعض اختبارات الأداء الأساسية للغاية والتي توضح أن محلل DOM سينخفض ​​إنتاجيته إلى النصف عند زيادة حجم ملف الإدخال من 1-15 كيلو بايت إلى 1-15 ميجابايت، أو أكبر بحوالي 1000 مرة.لا يتأثر إنتاجية النماذج الأخرى بشكل كبير.

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

المقال هو هنا.

تحديث

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

يوضح الرسم البياني أدناه العلاقة بين الحجم بالبايت وعدد العقد (والتي يجب أن تكون متناسبة مع مساحة ذاكرة المستند ضمن نموذج DOM).تتوافق الألوان المختلفة مع أنواع مختلفة من المستندات.المقياس هو سجل/سجل.الخط الأسود هو الأنسب للنقاط الزرقاء.من المثير للاهتمام ملاحظة أنه بالنسبة لجميع أنواع المستندات، تكون العلاقة بين حجم البايت وحجم العقدة خطية، لكن معامل التناسب يمكن أن يكون مختلفًا تمامًا.

Answer 1

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

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

• http://www.xml.com/pub/a/Benchmark/exec.html
• http://www.devx.com/xml/Article/16922
• http://xerces.apache.org/xerces2-j/faq-performance.html

Answer 2

أعتقد أن هناك الكثير من المتغيرات المعنية للتوصل إلى مقياس تعقيد بسيط ما لم تقم بالكثير من الافتراضات.

يجب أن يكون المحلل اللغوي البسيط لنمط SAX خطيًا من حيث حجم المستند ومسطحًا للذاكرة.

سيكون من المستحيل وصف شيء مثل XPath فيما يتعلق بمستند الإدخال فقط نظرًا لأن تعقيد تعبير XPath يلعب دورًا كبيرًا.

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

كما هو الحال مع معظم الأسئلة المتعلقة بالأداء، فإن الطريقة الوحيدة للحصول على إجابات دقيقة هي قياسها ومعرفة ما سيحدث!

Answer 3

روب ووكر على حق:لم يتم تحديد المشكلة بتفاصيل كافية.بالنظر إلى المحللين اللغويين فقط (وتجاهل مسألة ما إذا كانوا يقومون بالتحقق من الصحة)، هناك نوعان رئيسيان:فكر على أساس الشجرة - فكر في DOM - وفكر على أساس البث/الحدث ساكس (ادفع) و ستاكس (يحذب).إذا تحدثنا بشكل عام، فإن الأساليب المستندة إلى الشجرة تستهلك ذاكرة أكبر وتكون أبطأ (لأنك تحتاج إلى إنهاء تحليل المستند بأكمله)، بينما تستهلك الأساليب المستندة إلى البث/الأحداث ذاكرة أقل وتكون أسرع.تعتبر المحللات اللغوية المستندة إلى الشجرة بشكل عام أسهل في الاستخدام، على الرغم من أن StAX تم الإعلان عنه باعتباره تحسنًا كبيرًا (في سهولة الاستخدام) مقارنة بـ SAX.

Answer 4

كنت أخطط لتحميل ملفات XML كبيرة جدًا في طلبي.لقد طرحت السؤال هنا على Stack Overflow: أسرع معالجة ممكنة لملفات XML للمستندات الكبيرة جدًا.

ونعم، لقد كان الجزء المخصص للتحليل هو عنق الزجاجة.

انتهى بي الأمر بعدم استخدام موزعي XML على الإطلاق.وبدلاً من ذلك، قمت بتحليل الأحرف واحدًا تلو الآخر بأكبر قدر ممكن من الكفاءة لتحسين السرعة.أدى ذلك إلى سرعات تصل إلى 40 ميجابايت في الثانية على جهاز كمبيوتر يعمل بنظام Windows بسرعة 3 جيجاهرتز لقراءة بنية البيانات الداخلية وتحليلها وتحميلها.

سأكون مهتمًا جدًا بسماع كيفية مقارنة أوضاع تحليل XML المختلفة بهذا.