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

وفيما يلي ترجمة:

كنت مؤخرا قد وضعت دعا الشاعر (https://github.com/antlarr/bard) تطبيق سطر الأوامر، هو أن إدارة مكتبة الموسيقى المحلية مدير الموسيقى. وصوت الأغاني الشاعر بصمة إنشاء (استخدام acoustid //acoustid.org/ :: HTTPS)، وفقا لجميع الأغاني المخزنة الفوقية إلى قاعدة بيانات SQLite. لذلك يمكنك أن تجد بسهولة الاستعلام والأغاني المكررة، حتى لو كانت الأغنية لا يمكن العثور التسمية الصحيحة. في هذه الورقة المشتركة المؤلف خوارزمية للعثور على الأغاني مكررة، وذلك باستخدام بيثون وC ++ هو الأمثل 17 ضعف خوارزمية لاستكشاف كيفية جعل هذه الخوارزمية 8000 مرات أسرع من النسخة الأصلية.

خوارزمية

لتحديد الأغاني متشابهان، تحتاج أصواتهم لمقارنة بصمات الأصابع. يبدو سهلا (في الواقع، هو في الحقيقة ليس من الصعب)، ولكن بداية لا تبدو مباشرة بذلك. acoustid بصمة تحسب ليست الصوت الرقمي، ولكن مجموعة من الأرقام، على نحو أدق، مجموعة سلسلة من الأحرف. ولذلك لا يمكن المقارنة بين الأرقام في حد ذاتها، ولكن لمقارنة الأحرف الرقمية. وإذا كان كل الشخصيات بالضبط نفس الشيء، فإنه يمكن اعتبار أغنيتين هي نفسها. إذا 99 من نفس الطابع، فإنه يمكن اعتبار أن لديهم احتمال 99 من حد سواء هي نفسها، قد يكون سبب الفرق بين الاثنين بواسطة ترميز مشاكل (كما أغنية واحدة مع 192kbits / ق المشفرة الى mp3، أغنية أخرى مع 128kbits / ثانية ) وذلك بسبب.

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

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

لذا، إذا كنت تريد مقارنة جميع الأغاني في مكتبة الموسيقى للعثور على نسختين، ونحن في حاجة إلى المقارنة ID1 و 2، ومن ثم مقارنة مع 3 معرف ID 1 و ID 2، عموما يجب مقارنة كل أغنية لجميع الأغاني السابقة . وهكذا، إذا كان هناك 100 مكتبة الأغاني والموسيقى، وكنت في حاجة إلى المقارنة 1000 * 1001/2 = 500500 الأغاني (وهذا هو، لمقارنة 100100000 مرات بصمة).

تنفيذ بيثون الأصلي

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

count_bits_set صفر (ط):

 ط = ط - ((ط > >  1) و0x55555555)

 ط = (ط & 0x33333333) + ((ط > >  2) و0x33333333)

 عودة (((ط + (ط > >  4) و0xF0F0F0F) * 0x1010101) و0xffffffff) > >  24

يمكننا تحقيق هذه السرعة كقيمة مرجعية، ودعا الى سرعة.

تحسين الأول

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

هذا التحسن يجعل مقارنة زادت السرعة إلى سرعة تقريبا مزدوجة.

استخدام C ++ 17

في هذه المرحلة، وأعتقد لا يمكن بسهولة أن يمتد هذا الرمز إلى مكتبة الموسيقى بشكل اكبر، لذلك أعتقد أن الشاعر بحاجة التنفيذ الأفضل. تعديل الذاكرة بطيئة جدا، وC / C ++ يمكن أن يكون الأمثل لتحقيق المزيد من الحبيبات غرامة أسفل، ولكن لا أريد لإعادة كتابة التطبيقات كامل مع C ++، لذلك اعتمدت Boost.Python (https://www.boost.org/doc/libs /1_65_0/libs/python/doc/html/index.html)، فقط هذه الخوارزمية تدرك مع C ++، واستدعاء خوارزمية من التطبيقات بيثون. يجب أن أقول، لقد وجدت المتكاملة في بيثون، طريقة C ++ هو من السهل جدا، ولذا فإنني أوصي باستخدام Boost.Python.

في تطبيق جديد C ++، يمكنني استخدام ناقلات STL لبصمات الأصابع مخزن، وانضم في وقت سابق أكبر تعويض في خوارزمية لذلك ليس هناك حاجة لتعديل عناصر مكافحة ناقلات، يمكنك فقط النزوح على محاكاة. أنا أيضا استخدام خريطة STL، معرف أغنية للمؤشر لاحتواء كافة بصمات الأصابع. وأخيرا، أود أيضا أن أضيف على تدابير تحسين الهامة، من خلال __builtin_popcount دول مجلس التعاون الخليجي (https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fpopcount)، واستخدام وحدة المعالجة المركزية تعليمات لحساب حرفا.

أكبر ميزة من الخوارزمية هي مقارنة عملية لا تعديل أو نسخ أي بصمات، مما يجعل سرعة زادت 126.47 مرات. عند هذه النقطة والبدء في إجراء آخر: عدد من الأغاني في مقارنة الثاني (لا تنسى لمقارنة زوج واحد من كل أغنية 200 مرة للقيام مقارنة البصمات). متوسط سرعة الخوارزمية 580 / ثانية. أو بعبارة أخرى، من أجل مقارنة 1000 الأغاني، ويستغرق حوالي 14 دقيقة و 22 ثانية (علما بأن بيثون الأصلي حوالي ست ساعات في اليوم لتحقيق 16 دقيقة و 57 ثانية).

لأول مرة تحاول خوارزميات موازية

أركض براد هو CPU I7، وأنا دائما استخدام برنامجي فقط الأسف CPU واحد. كما مقارنة الخوارزمية أغنيتين لا يغير أي بيانات، وأعتقد أننا يمكن أن محاولة استخدام الخوارزميات المتوازية، بحيث يمكن تشغيلها معا في كل النوى الثمانية، ودمج النتائج في نهاية كل تكرار. لذلك بدأت في دراسة كيفية تحقيق، وجدت أن كل أغنية يؤديها مقارنة مع كل أغنية السابقة هي التي تحتوي وقد تمت معالجة جميع الأغاني الأمراض المنقولة جنسيا :: خريطة تعميم تحقيقه. لذا، إذا كان هناك مقابل كل حلقة يمكن تشغيل غرامة عادلة على كل تكرار لموضوع مختلف. والنتائج لها حقا! وC ++ 17 الأمراض المنقولة جنسيا :: for_each (https://en.cppreference.com/w/cpp/algorithm/for_each) يمكن تحديد ExecutionPolicy، التي يمكنك من خلالها جعل دورة تنفيذها على المواضيع المختلفة. ثم الأخبار السيئة: هذا المعيار لم يتم بدعم كامل من دول مجلس التعاون الخليجي.

لذلك أنا بحثت عن بعض التطبيقات for_each، وأخيرا في سؤال ستاكوفيرفلوو من (https://stackoverflow.com/questions/40805197/parallel-for-each-more-than-two-times-slower-than-stdfor-each ) وجدت واحدة. السؤال المشار إليها من برنامج "C ++ التزامن في العمل" لتحقيق الكتاب، وأنا لست متأكدا كيف المؤلف من هذا القانون لا يمكن نسخ مباشرة إلى براد ولكن يمكنني استخدامها للقيام ببعض الاختبارات لقياس .

وهذه الطريقة يمكن بسرعة تصل إلى 1897 مرة، أي حوالي 8700 أغنية / ثانية (1000 الأغاني في حاجة للتعامل مع حوالي 57 ثواني جيد جدا، أليس كذلك!)

محاولة موازية الثانية

ولست بحاجة للعثور على استخدامي لنص مواز من for_each. لحسن الحظ، وأخيرا وجدت دول مجلس التعاون الخليجي لديها التجريبي C ++ جزء مكتبة القياسية الخوارزمية تنفيذها في موازاة ذلك، والذي يحتوي على __gnu_parallel :: for_each (https://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode_using.html وصفحات الوثيقة هناك خوارزميات أكثر موازية). قانون الزواج تصل فقط مكتبة على ذلك.

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

لذلك أنا تعديل التعليمات البرمجية، بصمة من الأمراض المنقولة جنسيا :: خريطة < كثافة العمليات، الأمراض المنقولة جنسيا :: ناقلات < الباحث > >  نسخ إلى الأمراض المنقولة جنسيا:؛ ناقلات < الأمراض المنقولة جنسيا :: زوج < كثافة العمليات، الأمراض المنقولة جنسيا: ناقل < الباحث > > > حتى __gnu_parallel :: for_each تكون قادرة على استخدام ترابط التجمع 8 المواضيع لتشغيل.

دول مجلس التعاون الخليجي أسرع من تحقيق على ستاكوفيرفلوو، وسرعة 2442 مرة، حول 11،200 الأغاني / ثانية، 1000 الأغاني 44 ثانية فقط.

ومن الواضح أن أنسى تحسينات هامة

عند التدقيق مترجم بارد، وجدت أنني لم أكن استخدام مترجم لتحسين سرعة التبديل! حيث أعطى مترجم أضاف -Ofast-مسيرة = -mtune مواطن = الأم -funroll الحلقات، الامر بهذه البساطة. تخمين ما حدث ......

زيادة سرعة إلى 6552 أضعاف، من نحو 30050 الأغاني / ثانية، 1000 الأغاني فقط 16 ثانية.

التحسينات الناتجة خالية من Tumbleweed

أنا وضعت النظام المستخدم في تشغيل openSUSETumbleweed، يمكنك تقدير المعرفة، فمن السهل جدا للاستخدام المتداول إطلاق توزيعة لينكس. يوم واحد كنت اقوم به من الاختبار، Tumbleweed المترجم من دول مجلس التعاون الخليجي 7.3 التحديث لgcc8.1. لذلك أعتقد أنني يجب إعادة الاختبار.

فقط للترقية إلى أحدث إصدار من المترجم، وزيادة السرعة إلى 7714 أضعاف، 35380 الأغاني / ثانية، 1000 الأغاني فقط 14 ثانية.

التحسين النهائي

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

هذا التعديل إلى آخر مرة كنت وتسريع وزيادة السرعة إلى 7998 مرة، 36680 الأغاني / ثانية، وتجهيزها بالكامل 1000 مكتبة موسيقى أغنية فقط 13 ثانية.

استنتاج

بعض جديرة تسجيل الدروس المستفادة من هذه التجربة:

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

الأصل: الشبكي: //antlarr.io/2018/07/optimizing-a-python-application-with-c-code/

الكاتب: antlarr

الترجمة: الغضروف المفصلي، المحرر: تو مين

"أصدقاء دعوة للمشاركة"

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

إذا كان لديك أفكارا جديدة في المواد عالية الجودة أو صناعة الأحداث الساخنة والتكنولوجيا الاتجاهات رؤى أو التطبيق العملي لعمق برامج المشهد، يرجى الاتصال CSDN التقديم، الاتصال: مايكرو إلكتروني (guorui_1118، يرجى ملاحظة اسم مساهمة + + وظائف الشركات)، وصندوق البريد (guorui@csdn.net).