Scala لفهم كفاءة؟

Question

في كتاب "البرمجة في سكالا" ، الفصل 23 ، يقدم المؤلف مثالاً مثل:

case class Book(title: String, authors: String*)
val books: List[Book] = // list of books, omitted here
// find all authors who have published at least two books

for (b1 <- books; b2 <- books if b1 != b2;
    a1 <- b1.authors; a2 <- b2.authors if a1 == a2)
yield a1

قال المؤلف ، سيترجم هذا إلى:

books flatMap (b1 =>
   books filter (b2 => b1 != b2) flatMap (b2 =>
      b1.authors flatMap (a1 =>
        b2.authors filter (a2 => a1 == a2) map (a2 =>
           a1))))

ولكن إذا نظرت إلى تعريف طريقة الخريطة و Flatmap (TraversableLike.Scala) ، قد تجد ، يتم تعريفها كما للحلقات:

   def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
    val b = bf(repr)
    b.sizeHint(this) 
    for (x <- this) b += f(x)
    b.result
  }

  def flatMap[B, That](f: A => Traversable[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
    val b = bf(repr)
    for (x <- this) b ++= f(x)
    b.result
  }

حسنًا ، أعتقد أن هذا سيُترجم باستمرار إلى Foreach ثم يتم ترجمته إلى البيان الذي يعد عبارة عن بنية لا تعبير ، لا يوجد لدى Scala بناء ، لأنه يريد دائمًا العائد على شيء ما.

لذا ، ما الذي أريد مناقشته معك هو ، لماذا تفعل Scala هذا "للترجمة"؟ استخدم مثال المؤلف 4 مولدات ، والتي سيتم ترجمتها إلى 4 مستويات متداخلة للحلقة في النهاية ، وأعتقد أنه سيكون له أداء فظيع حقًا عندما يكون books هو كبير.

تشجع Scala الناس على استخدام هذا النوع من "السكر النحوي" ، يمكنك دائمًا رؤية الرموز التي تستفيد بشدة من المرشح والخريطة والخريطة المسطحة ، والتي يبدو أن المبرمجين ينسون ما يفعلونه حقًا هو تعشيش حلقة واحدة داخل آخر ، وما الذي حققه هو فقط لصنع الرموز تبدو أقصر قليلاً. ما هي فكرتك؟

Answer 1

بالنسبة إلى الشاملات هي السكر النحوي للتحول الأحادي ، وعلى هذا النحو ، مفيدة في جميع أنواع الأماكن. في ذلك ، فهي أكثر مطوّلة في Scala من بنية Haskell المكافئة (بالطبع ، Haskell غير متكافئ بشكل افتراضي ، لذلك لا يمكن للمرء التحدث عن أداء البناء كما في Scala).

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

فيما يتعلق بالنظر النهائي ، سواء كان ذلك يخفي التعقيد أم لا ، سأطرح هذا:

for {
  b1 <- books
  b2 <- books
  if b1 != b2
  a1 <- b1.authors
  a2 <- b2.authors 
  if a1 == a2
} yield a1

من السهل جدًا رؤية ما يجري ، والتعقيد واضح: B^2 * A^2 (فلتر لا يغير التعقيد) ، لعدد الكتب وعدد المؤلفين. الآن ، اكتب نفس الرمز في Java ، إما مع المسافة البادئة العميقة أو مع أساليب خاصة ، وحاول التأكد ، في نظرة سريعة ، ما هو تعقيد الكود.

لذلك ، IMHO ، هذا لا يخفي التعقيد ، ولكن ، على العكس من ذلك ، يوضح ذلك.

أما بالنسبة لل map/flatMap/filter التعاريف التي ذكرتها ، لا تنتمي إليها List أو أي فئة أخرى ، لذلك لن يتم تطبيقها. في الأساس،

for(x <- List(1, 2, 3)) yield x * 2

تترجم إلى

List(1, 2, 3) map (x => x * 2)

وهذا ليس نفس الشيء

map(List(1, 2, 3), ((x: Int) => x * 2)))

وهذا هو كيف سيتم استدعاء التعريف الذي مررت به. للسجل ، والتنفيذ الفعلي ل map تشغيل List هو:

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
  val b = bf(repr)
  b.sizeHint(this) 
  for (x <- this) b += f(x)
  b.result
}

Answer 2

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

Answer 3

هناك بالفعل 6 حلقات. حلقة واحدة لكل مرشح/خريطة مسطحة/خريطة

يمكن إجراء أزواج الخريطة المرشح في حلقة واحدة باستخدام وجهات نظر كسول للمجموعات (طريقة التكرار)

بشكل عام ، تقوم TT بتشغيل حلقتين متداخلتين للكتب للعثور على جميع أزواج الكتب ، ثم حلقتين متداخلين للعثور على ما إذا كان مؤلف كتاب واحد في قائمة مؤلفي الآخر.

باستخدام هياكل بيانات بسيطة ، ستفعل الشيء نفسه عند الترميز بشكل صريح.

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

for (b1 <- books; b2 <- books; a <- (b1.authors & b2.authors)) yield a

Answer 4

لاحظ أنه في 2.8 ، filter تم تغيير المكالمة إلى withFilter وهو كسول ويتجنب بناء بنية وسيطة. يرى دليل الانتقال من المرشح إلى WithFilter؟.

أعتقد أن السبب for ترجم إلى map, flatMap و withFilter (بالإضافة إلى تعريفات القيمة إذا كانت موجودة) هو جعل استخدام الموناد أسهل.

بشكل عام ، أعتقد أنه إذا كان الحساب الذي تقوم به ينطوي على حلقة 4 مرات ، فمن الجيد استخدام for عقدة. إذا كان من الممكن إجراء الحساب بشكل أكثر كفاءة وكان الأداء مهمًا ، فيجب عليك استخدام الخوارزمية الأكثر كفاءة.

Answer 5

متابعة واحدة لإجابة @ittayd على كفاءة الخوارزمية. تجدر الإشارة إلى أن الخوارزمية في المنشور الأصلي (وفي الكتاب) هي أ حلقة متداخلة الانضمام. في الممارسة العملية ، هذه ليست خوارزمية فعالة لمجموعات البيانات الكبيرة ، وستستخدم معظم قواعد البيانات أ تجميع التجميع هنا بدلا من ذلك. في Scala ، سيبدو تجميع التجزئة شيئًا مثل:

(for (book <- books;
      author <- book.authors) yield (book, author)
).groupBy(_._2).filter(_._2.size > 1).keys