👰🏽 🤙 🚴🏿 يحتاج المبرمجون إلى الرياضيات ، أو مشكلة كان علي حلها 👄 🏆 ⤵️

مرحبا!

أنا أعمل على WebRTC - إطار عمل لعقد المؤتمرات الصوتية والمرئية (أو المكالمات؟ وبعبارة أخرى - الاتصال في الوقت الفعلي). في هذا المقال أريد أن أصف مشكلة مثيرة للاهتمام وكيف تم حلها. في هذه المشكلة ، في الواقع ، كان مطلوبًا تقليل lcm للعديد من الأرقام الحقيقية مع قيود إضافية. اضطررت إلى تطبيق قدر كبير من نظرية الأعداد أو على الأقل المنطق.

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

المقدمة

يمكن للعملاء تكوين WebRTC لتشفير الدفق الوارد بدقة متعددة في وقت واحد. على سبيل المثال ، يمكن أن يكون هذا مفيدًا في مؤتمرات الفيديو: يرسل كل عميل عدة تدفقات إلى الخادم بدقة ومعدلات بت مختلفة ، ويرسل الخادم إلى كل شخص آخر الدفق الذي يناسب النطاق الترددي للعميل فقط.

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

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

أنجع وسيلة لتحقيق ذلك هي بحاجة إلى مصدر للسماح مقسمة إلى عدد محدد: alignment. على سبيل المثال ، بالنسبة إلى النسب القياسية {1.0 ، 2.0 ، 4.0} ومتطلبات التكافؤ لبرنامج التشفير ، يمكنك أن تسأل المصدر بسهولة alignment=8. المصدر سيقطع الصور قليلا. سيؤدي هذا إلى تشويه بسيط في نسبة العرض إلى الارتفاع للفيديو ، ولكنه سيجعل التبديل بين التدفقات غير مرئي. نتيجة لذلك ، يمكن تقسيم الدقة الواردة ، مضاعفات 8 ، بسهولة إلى 1 أو 2 أو 4 مرات والحصول على دقة متساوية ، والتي سوف ترميز المشفر بسعادة.

, {1, 1.7, 2.3}? , "" - 391. , 782. , , 782. , VGA (640x480) . - , , , -, , -, .

, , , ? , {1, 1.6, 2.4} {1, 1.7, 2.3} 48 ( 782). , .

: $d \ in \ mathbb {N} ، \ S_i \ ge 1 ، S_i \ in \ mathbb {R} ، i = 1..n$

: $A \ in \ mathbb {N} ، \ A \ le MaxA ، \ S'_i \ in \ mathbb {R} ، \ S'_i \ ge 1 ، \ i = 1..n$

$\ sum_ {i = 1} ^ n \ left (S_i -S'_i \ right) ^ 2 \ rightarrow min$ $\ frac {A} {S'_i \ cdot d} \ in \ mathbb {N} ، i = 1..n \ \ \ \ \ \ \ \ \ (1)$

: - , , .

, - -. . ماكس ( 16). - , .

- , (1), . i- .

$A / (S'_i \ cdot d) ، A ، d \ in \ mathbb {N}$ , , $S'_i \ in \ mathbb {Q}$ S'_i = N_i / D_i . .

, : GCD (N_i، D_i) = 1

(1) $\ frac {A \ cdot D_i} {N_i \ cdot d} \ in \ mathbb {N}$ ,

$N_i \ cdot d \ vert A \ cdot D_i \ \ \ \ \ \ \ (2)$

( : ).

. N_i د_أ , . N_i $N_i \ vert أ$ ,

$A = N_i \ cdot f ، \ f \ in \ mathbb {N} \ \ \ \ \ \ (3)$

, (2) :

$f \ cdot N_i \ cdot d \ vert f \ cdot A \ cdot D_i$

(3) :

$A \ cdot d \ vert f \ cdot A \ cdot D_i$

$d \ vert f \ cdot D_i$

, :

$f \ cdot D_i = k \ cdot d، k \ in \ mathbb {N} \ \ \ \ \ \ \ \ \ \ (4)$

S'_i (3) (4):

$S'_i = \ frac {N_i \ cdot f} {D_i \ cdot f} = \ frac {A} {f \ cdot D_i} = \ frac {A} {k \ cdot d} ، \ \ k \ in \ mathbb {N} \ \ \ \ \ \ \ \ (5)$

, S'_i 1 ( ) :

$ك \ لو \ فارك {A} {d} \ \ \ \ \ \ \ (6)$

, (1) (5) (6), , , . . (6) , .

. , , 0, $ك ^ * = \ frac {A} {S_i \ cdot d}$ . , 2 $k = min \ {\ lfloor k ^ * \ rfloor، \ \ lceil k ^ * \ rceil \}$ . , - , . . , (6).

, ( ):

const int kMaxAlignment = 16;

//    scale_factor (S_i)   
//   (d)     (A).
//     error_acc.
float GetApprox(int encoder_alignment, int requested_alignment, 
                float scale_factor, float *error_acc) {
  int k = static_cast<int> ((requested_alignment + 0.0) / 
                            (encoder_alignment * scale_factor));
  float best_error = 1e90;
  float best_approx = 1.0;
  for (int i = 0; i < 2; i++, k++) {
    if (k == 0 || k * encoder_alignment > requested_alignment) continue;
    float approx = (requested_alignment +0.0) / (k * encoder_alignment);
    float error = (approx - scale_factor) * (approx - scale_factor);
    if (error < best_error) {
      best_error = error;
      best_approx = approx;
    }
  }
  *error_acc += best_error;
  return best_approx;
}

//  .    (S'_i)
//    (A)   requested_alignment.
std::vector<float> CalulateAlignmentAndScaleFactors(
    int encoder_alignment, std::vector<float> scale_factors, 
    int *requested_alignment) {
  float best_error = 1e90;
  int best_alignment = 1;
  std::vector<float> best_factors;
  std::vector<float> cur_factors;
  
  for (int a = 1; a <= kMaxAlignment; ++a) {
    float cur_error = 0;
    cur_factors.clear();
    for (float factor: scale_factors) {
      float approx = GetApprox(encoder_alignment, a, factor, &cur_error);
      cur_factors.push_back(approx);
    }
    if (cur_error < best_error) {
      best_error = cur_error;
      best_factors = cur_factors;
      best_alignment = a;
    }
  }
  *requested_alignment = best_alignment;
  return best_factors;
}

, , . , . , .

نعم ، بدون الرياضيات ، لا يزال بإمكانك إقناع نفسك بأن المعامِلات الصادرة عن هذا الكود ستلائم حالة المشكلة (يقسم البسط المحاذاة المحسوبة ، لذا شارك كل شيء بالكامل ، ويعطي المقام القسمة بالمحاذاة اللازمة للمشفّر). لكن بدون سلسلة التفكير (1) => (4) ، (5) من غير الواضح بشكل عام كيف يجد هذا الرمز الحل الأمثل.

يحتاج المبرمجون إلى الرياضيات ، أو مشكلة كان علي حلها

المقدمة

More articles: