Get best of the week

PHP: يبحث array_key_exists أسرع 500 مرة من in_array

في عام 2014 ، كتبوا بالفعل عن البحث عن المصفوفة ، ولكن بالكاد فهمها.

منذ ذلك الحين ، تم إصدار العديد من إصدارات PHP ولم يتم إصلاحها ، مما يعني أن الملاحظات سيئة وقلة من الناس يعرفون عنها. على الثعبان هو نفسه ، وفي 3 * أسوأ من 2.7.

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

يظهر اختبار بسيط:

يبحث in_array عن ideone.com/Yb1mDa 6600msفي غضون 6-9 ثوانٍ ويبحث المصفوفة_الصريحة
عن نفس الشيء ، ولكن أسرع من 250 (php5.6 / py3. *) 400+ مرات (php7.3 / py2.7) ideone .com / gwSmFc(زادت الدورة 100 مرة) 12 مللي ثانية (6600/12 = 550 مرة + -10٪ انتشار بسبب الحمل وذاكرة التخزين المؤقت)

لماذا يحدث ذلك؟ تأمل بالتفصيل:

1) البحث عن سلاسل في مجمّع / تجميعات نقية يقوم بفرز مجموعة من السلاسل (سريعة أو فقاعية) ، ثم البحث الثنائي.

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

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

افتراضيًا ، يحدث التصنيف في كل مرة مرة أخرى ، على الرغم من أنهم كتبوا أنهم تحسنوا في 7.2 in_array من خلال التجزئة ، ولكن ليس كثيرًا.

2) فهرس / مفتاح البحث (كسلسلة) في الاقتران. مصفوفة / قاموس يحدث عن طريق تجزئة السلاسل ومعالجة التصادم. (أخطاء بحث التجزئة). التجزئة هي الفهرس الرقمي للصفيف وجلبه كـ (عنوان العنصر صفر) + إزاحة * حجم المؤشر إلى صفيف السلاسل باستخدام هذا التجزئة) في خطوتين. + تصادم القوة الغاشمة ، خطوات في المتوسط ​​أقل من البحث الثنائي.
يتم تجزئة الفهرس تلقائيًا مرة واحدة مقدمًا عند إنشاء عنصر القاموس $ m [key] = val ويتم تخزينه مؤقتًا.

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

لا يمكنك قراءة المزيد ، قم بتغيير in_array إلى array_combine + array_key_exists وهذا كل شيء.

يعتمد عدد الخطوات عند البحث باستخدام التجزئة على عدد التصادمات وعدد الأسطر التي لها نفس التجزئة. يجب أن يتم فرزها أو فرزها أيضًا والبحث الثنائي.

للحد من التصادمات ، يمكنك تخصيص المزيد من الذاكرة ، إذا كان من الممكن ألا تكون هذه المشكلة الآن مثل 50 عامًا عندما تكلف 1 كيلو بايت من الذاكرة على الملفات المغناطيسية مثل الطائرة. ثم تم اختراع جميع الخوارزميات الأساسية: Sort / zip / gif / jpg / etc. - فهي لا تحتاج إلى الكثير من الذاكرة ، ولكنها سيئة ، والآن هي أفضل بكثير ، لكنها تحتاج إلى الكثير من الذاكرة 1-16 MB. نعم ، هناك خوادم بسعة 256 ميجا بايت ولكل منها دفق منفصل و 16 ميجا بايت بالفعل الكثير ، ولكن على جهاز المستخدم العادي 1 جيجا بايت على الأقل و 16 ميجا بايت هو انخفاض في المجموعة.

يمكنك الحصول على مزيد من التأثير إذا قمت باستبدال استدعاء دالة array_key_exists ببنية isset ($ m [key]) ، ولا يمسح قائمة انتظار الأوامر وذاكرة التخزين المؤقت ، ولا يستخدم المكدس ، وهو أسرع بحوالي 20٪.

يمكنك أيضًا تسريعها إذا قمت بإنشاء مصفوفة من الحرفين الأولين - 4 * 16 كيلو بايت ونظرت أولاً في الإزاحة (فهرس = رمز الحرف الأول + الثاني * 256) مؤشرًا إلى مجموعة التجزئة لبقية السطر ، ثم ابحث عن مجموعة صغيرة من "ذيول" السلاسل والتصادمات أصغر بكثير.

يتطلب المزيد من الذاكرة والخوارزمية أكثر تعقيدًا ، ولكن البحث أسرع 30 مرة. ولكن هذا لم يتم تنفيذه في php ، يمكنك كتابة مكتبة so / dll الخاصة بك والاتصال بها ، أو اطلب من المطورين إضافتها في 7.5.

يمكنك البحث عبر mySQL ، لكنك بحاجة إلى تجميع الاستعلامات وستظل أبطأ.

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

More articles:


All Articles