على منحنيات بيزييه وسرعة اردوينو ، الجزء الثاني

سنمر - والمزيد

في مشاركتي السابقة ، أوضحت كيف يمكنك تحسين سرعة حساب النقاط على منحنى Bezier (KB) عن طريق:

1. تحويل صيغ الحساب - التسارع ~ 3 مرات.
2. لا يوجد تسارع تقريبًا من PT إلى FT - ولكنه يسمح بـ 3.
3. عملية استبدال القسمة عن طريق الضرب والتحول هي تسارع بنسبة 40 ٪ أخرى.

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

دعني أذكرك مرة أخرى بالصيغة التي تم الحصول عليها لحساب النقطة على KB

$$

$$P = (A1 * و + B1) * و + C (=> 2 * 2 +)$$

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

نعتبر الحالة P = A * و (=> 1 *) ، ونفترض أننا نعرف قيمة P0 مع بعض الوسيط u0. ثم يمكن حساب القيمة مع الوسيطة التالية u0 + 1 على النحو P = A * (u0 + 1) = A * u0 + A = P0 + A (=> 1+). بدون فقدان أي دقة ، تمكنا من استبدال عملية الضرب بعملية الإضافة ، وهي أسرع بكثير.

الآن مثال أكثر تعقيدًا P = A * و * و (=> 2 *) ، نعتبر بالقياس P = A * (و + 1) * (و + 1) = A * (و * و + 2 * و + 1) = A * و * و + 2 * A * و + A = P0 + 2 * A * و + A (=> 2 * 2 +). للوهلة الأولى ، لم نفز بأي شيء ، ولكن إذا قمنا بحساب A '= 2 * A مسبقًا ، نحصل على (=> 1 * 2 +) ، فإن الفوز ممكن جدًا. لكننا لن نتوقف على ما تم تحقيقه وعلى التعبير الذي تم الحصول عليه A '* ونطبق التقنية المعروفة لدينا بالفعل ، ثم سنحصل على عمليتين على متغيرين: P = P + A' + A ؛ A '= A' + A (=> 3+). إذا أخذنا في الاعتبار أن القيمة الأولية لـ A 'يمكن القيام بها أكثر من قبل A ، بشكل عام ، هناك فقط إضافتين بدلاً من مضاعفتين. نعم ، كان علينا الحصول على متغيرين إضافيين ، لكن هذا تبادل كلاسيكي - نحن ندفع بالذاكرة في ذلك الوقت.

يبقى فقط لحساب القيم الأولية الصحيحة ، ولكن يتم ذلك مرة واحدة فقط في بداية التكرار ، وإذا كانت القيمة الأولية للمعلمة هي u = 0 ، فهي بشكل عام تافهة P = 0 ، A '= A. سنقوم باختبار طريقتنا على العديد من التكرارات (هذا غير ضروري تمامًا ، فالرياضيات المطبقة بشكل صحيح لا يمكن أن تعطي إجابة خاطئة) ، ولكنها ستسمح لنا بفهم أفضل لما يحدث. لذا
التكرار 0: و = 0 ؛ P = 0 (صحيح) ؛ A '= A ؛ أ '' = 2 * أ ؛
التكرار 1: و = 1 ؛ P = 0 + A '= 0 + A = A (صحيح) ؛ A '= A' + A '' = A + 2 * A = 3 * أ ؛
التكرار 2: و = 2 ؛ P = A + 3 * A = 4 * A (صحيح) ؛ أ '= 3 * أ + 2 * أ = 5 * أ ؛
التكرار 3: و = 3 ؛ ع = 9 * أ (صحيح) ؛ A '= 7 * A وهكذا.

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

أعد كتابة تعبيرنا الأصلي عن KB في شكل موسع

$$

$$P = A1 * و * و + B1 * و + C$$

ثم للحسابات باستخدام هذه الطريقة ، نحتاج إلى 2+ للمصطلح الأول (ومتغيرين) ، 1+ للمصطلح الثاني (ومتغير واحد) و 2+ لإضافة كل شيء معًا (=> 5+). يمكن توقع أنه حتى هذا النهج (الخاطئ) سيعطي مكاسب مقارنة بـ 2 * 2 + ، ولكن كل شيء أفضل بكثير. من الواضح أن عملية الإضافة هي إضافة (شكرا كابتن) ، لذا يمكنك تجميع المصطلحات واستبدال المصطلحات الثابتة بتعبيرات جديدة ، والتي تعطي الخوارزمية التالية:

1. القيم الأولية ل P = C ؛ A '= A1 + B1 ؛ أ '' = 2 * A1 ؛
2. في الخطوة التالية P = P + A '؛ A '= A' + A '' (=> 2+) ، وهو بلا شك أسرع من مخطط هورنر.

ننفذ الخوارزمية الخاصة بنا في شكل برنامج (هذا ليس تافهاً كما قد يبدو ، لأن البساطة نسيت عن الحاجة إلى التحولات ، ولكن ليس من الصعب جدًا ... لمدة 20 دقيقة) ، نحصل على التعقيد الحسابي (=> 2 + 1 >>) ونقيس السرعة - تحولت إلى 140 دورة (زيادة في السرعة 3 مرات أخرى) لكل دورة ، ولكن هذه النتيجة مثالية تقريبًا. ما يتعين علينا القيام به للحصول على الخيار المثالي (بمعنى ما) هو الانتباه إلى أبعاد المعاملات في الصيغ. ننفذ الآن جميع العمليات على أعداد صحيحة طويلة (32 بت) ، وقد يكون هذا غير ضروري في بعض الأماكن. إذا قللنا من سعة المعاملات إلى الحد الأدنى الضروري ، فيمكننا الحصول على مكاسب بنسبة 20-25 في المائة ، ولكن هذا سيتطلب منا التبديل إلى المجمع (لا يمتلك C الوسائل المناسبة لمثل هذه العمليات) وتحليل بيانات المشكلة الأصلية بعناية. سواء كان الأمر متروكًا للقارئ ليقرر ما إذا كان سيفعل ذلك أم لا ، فقد قمنا بالفعل بتسريع الحسابات أكثر من 1900/140 = 13 مرة مقارنة بالنهج "الساذج".

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

ومع ذلك ، نشأت مشكلة واحدة بشكل غير متوقع تمامًا - نرى بوضوح عمليتين إضافيتين على أرقام 32 بت ، والتي يجب أن تستغرق 4 + 4 = 8 دورات ساعة ، ووضع 8 * 3 * 2 = 48 دورة ساعة أخرى لإرسال المعاملات ، 4 دورات ساعة لاستلام نتيجة التحول ، 4 دورة ساعة لاستدعاء إجراء الحساب والعودة ، و 4 دورات ساعة لتنظيم الدورة - حيث لا تكون 60 ساعة ساعة أخرى واضحة. في السابق ، لم نلاحظ ذلك ببساطة على خلفية مئات دورات الساعة ، ولكن الآن يمكنك الانتباه. تم العثور على المقاييس المفرطة بسهولة - في الدورة كانت هناك عمليات تصحيح غير ضرورية ، إذا قمت بتنظيف كل شيء بعناية ، فحينئذٍ لا يزال هناك 120 إجراء فقط ويكون الغرض من كل منها مفهومًا (حسنًا ، ليس بحيث يكون مفهوما تمامًا ، ولكن لا يزال). بعد ذلك ، نكتشف وقت تنفيذ الدورة الفارغة - 22 مقياسًا ، أتساءل ما الذي يفعلونه هناك طوال هذا الوقت ، ولكن حسنًا ، ونوضح وقت الحساب الفعلي ، والذي سيكون 98 دورة. لاحظ أن تقدير تغيرات تسريع العمل التي تم الحصول عليها: بدلاً من 1900/140 = 13 نحصل على (1900-50) / (140-40) = 19 مرة ، وهو ما لا معنى عملي له ، لأن الدورة لا تزال ضرورية ، ولكنها تتيح لك رفعها أكثر احترام الذات.

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

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