Scala: قابل للتغيير مقابل أداء كائن ثابت - OutofMemoryError

Question

كنت أرغب في مقارنة خصائص الأداء من غير قابل للتغيير. Map وقابلة للتغيير. Map في Scala للحصول على عملية مماثلة (وهي دمج العديد من الخرائط في واحدة. انظر هذا السؤال). لدي ما يبدو أنه تطبيقات مماثلة لكل من الخرائط القابلة للتغيير والقابلة للتغيير (انظر أدناه).

كاختبار، قمت بإنشاء قائمة تحتوي على 1،000،000 خريطة عنصر واحد [int، int] وانتقلت هذه القائمة إلى الوظائف التي كنت اختبرها. مع ذاكرة كافية، كانت النتائج غير متأكدة منها: ~ 1200ms للحصول على قابلة للتغيير. map، ~ 1800ms للحصول على غير قابل للتغيير. التعليق على ذلك أيضا.

ماذا مفاجأة لي قليلا، ربما لأنني كنت سميكا بعض الشيء، هو أنه مع تكوين التشغيل الافتراضي في Intellij 8.1، فإن كلا من التطبيقات القابلة للتغيير ضربت OutofmemoryError، لكن المجموعة غير القابلة للتغيير لم تفعل ذلك. تم تشغيل الاختبار الثابت إلى الانتهاء، لكنه فعلت ببطء شديد - يستغرق حوالي 28 ثانية. عندما قمت بزيادة ذاكرة Max JVM (إلى حوالي 200 ميجابايت، لست متأكدا من أين العتبة)، حصلت على النتائج أعلاه.

على أي حال، إليك ما أريد أن أعرفه حقا:

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

التنفيذ أدناه. (ملاحظة: لا أدعي أن هذه هي أفضل تطبيقات ممكنة. لا تتردد في اقتراح التحسينات.)

  def mergeMaps[A,B](func: (B,B) => B)(listOfMaps: List[Map[A,B]]): Map[A,B] =
    (Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv)) { (acc, kv) =>
      acc + (if (acc.contains(kv._1)) kv._1 -> func(acc(kv._1), kv._2) else kv)
    }

  def mergeMutableMaps[A,B](func: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A,B] =
    (mutable.Map[A,B]() /: (for (m <- listOfMaps; kv <- m) yield kv)) { (acc, kv) =>
      acc + (if (acc.contains(kv._1)) kv._1 -> func(acc(kv._1), kv._2) else kv)
    }

  def mergeMutableImperative[A,B](func: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A,B] = {
    val toReturn = mutable.Map[A,B]()
    for (m <- listOfMaps; kv <- m) {
      if (toReturn contains kv._1) {
        toReturn(kv._1) = func(toReturn(kv._1), kv._2)
      } else {
        toReturn(kv._1) = kv._2
      }
    }
    toReturn
  }

Answer 1

حسنا، هذا يعتمد حقا على ما هو نوع الخريطة الفعلي الذي تستخدمه. من المحتمل HashMap. وبعد الآن، هياكل قابلة للتغيير مثل هذا الاستفادة من الأداء من خلال الذاكرة المسبقة التي تتوقع استخدامها. أنت تنضم إلى مليون خرائط، لذلك لا بد أن تكون الخريطة النهائية كبيرة إلى حد ما. دعونا نرى كيف يتم إضافة هذه القيم / القيم هذه:

protected def addEntry(e: Entry) { 
  val h = index(elemHashCode(e.key)) 
  e.next = table(h).asInstanceOf[Entry] 
  table(h) = e 
  tableSize = tableSize + 1 
  if (tableSize > threshold) 
    resize(2 * table.length) 
} 

انظر 2 * في ال resize خط؟ قابلة للتغيير HashMap ينمو من خلال مضاعفة كل مرة ينفد من المساحة، في حين أن المرء غير القابل للتغيير هو محافظ جدا في استخدام الذاكرة (على الرغم من أن المفاتيح الحالية ستشغل عادة المساحة عند تحديثها).

الآن، بالنسبة لمشاكل الأداء الأخرى، تقوم بإنشاء قائمة بالمفاتيح والقيم في الإصدارين الأولين. هذا يعني أنه قبل الانضمام إلى أي خرائط، لديك بالفعل كل Tuple2 (أزواج المفتاح / القيمة) في الذاكرة مرتين! بالإضافة إلى النفقات العامة List, ، وهو صغير، لكننا نتحدث عن أكثر من مليون عنصر تايمز النفقات العامة.

قد ترغب في استخدام إسقاط، مما يتجنب ذلك. لسوء الحظ، ويستند الإسقاط Stream, ، والتي ليست موثوقة للغاية لأغراضنا على Scala 2.7.x. لا يزال، جرب هذا بدلا من ذلك:

for (m <- listOfMaps.projection; kv <- m) yield kv

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

تعديل

الاستكمال، يأخذ الفهم من أجل / العائد مجموعة واحدة أو أكثر وإرجاع مجموعة جديدة. كلما كان ذلك منطقي، فإن مجموعة العودة هي نفس النوع مثل المجموعة الأصلية. لذلك، على سبيل المثال، في التعليمة البرمجية التالية، ينشئ For-Fullsion قائمة جديدة، ثم يتم تخزينها بعد ذلك l2. وبعد ليس val l2 = الذي يخلق القائمة الجديدة، ولكن من أجل الفهم.

val l = List(1,2,3)
val l2 = for (e <- l) yield e*2

الآن، دعونا نلقي نظرة على الكود المستخدم في الخوارزمتين الأولى (ناقص mutable الكلمة الرئيسية):

(Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv)) 

ال foldLeft المشغل، هنا مكتوب مع /: مرادف، سيتم الاحتجاج به على الكائن الذي تم إرجاعه من قبل الفهم. تذكر أن أ : في نهاية المشغل عكس ترتيب الكائن والمعلمات.

الآن، دعونا نفكر في هذا الكائن هذا، الذي foldLeft يتم استدعاء. المولد الأول في هذا للفهم هو m <- listOfMaps. وبعد نحن نعرف ذلك listOfMaps هي مجموعة من قائمة أنواع [X]، حيث X غير ذي صلة حقا هنا. نتيجة لفهم على List هو دائما آخر List. وبعد المولدات الأخرى ليست ذات صلة.

لذلك، أنت تأخذ هذا List, ، الحصول على كل مفتاح / القيم داخل كل Map وهو مكون من هذا List, ، وجعل جديد List مع كل ذلك. لهذا السبب أنت تكرار كل ما لديك.

(في الواقع، الأمر أسوأ من ذلك، لأن كل مولد يخلق مجموعة جديدة؛ المجموعات التي تم إنشاؤها بواسطة المولد الثاني هي مجرد حجم كل عنصر listOfMaps رغم ذلك، ويتم تجاهلها على الفور بعد الاستخدام)

السؤال التالي - في الواقع، أول واحد، لكن كان من الأسهل عكس الإجابة - هو كيفية استخدام projection يساعد.

عندما تتصل projection على List, ، يعيد كائن جديد، من النوع Stream (على scala 2.7.x). في البداية، قد تعتقد أن هذا سيجعل الأمور أسوأ فقط، لأن لديك الآن ثلاث نسخ من List, ، بدلا من واحد واحد. لكن Stream ليست محسوبة مسبقا. أنه لازيلي محسوب.

ما يعني ذلك هو أن الكائن الناتج، Stream, ليست نسخة من List, ولكن، بدلا من ذلك، وظيفة يمكن استخدامها لحساب Stream عند الاقتضاء. بمجرد حساب الحساب، سيتم الاحتفاظ بالنتيجة بحيث لا يحتاج إلى حسابها مرة أخرى.

ايضا، map, flatMap و filter من أ Stream جميع إرجاع جديد Stream, ، مما يعني أنه يمكنك سلسلة منهم معا دون إجراء نسخة واحدة من List التي أنشأتها. منذ لفهم مع yield استخدم هذه الوظائف ذاتها، واستخدام Stream داخل منع نسخ غير ضرورية من البيانات.

الآن، لنفترض أنك كتبت شيئا مثل هذا:

val kvs = for (m <- listOfMaps.projection; kv <-m) yield kv
(Map[A,B]() /: kvs) { ... }

في هذه الحالة، لا تكتسب أي شيء. بعد تعيين Stream ل kvs, ، لم يتم نسخ البيانات بعد. بمجرد تنفيذ السطر الثاني، على الرغم من أن KVS ستحسب كل من عناصرها، وبالتالي، ستعقد نسخة كاملة من البيانات.

الآن النظر في النموذج الأصلي ::

(Map[A,B]() /: (for (m <- listOfMaps.projection; kv <-m) yield kv)) 

في هذه الحالة، Stream يستخدم في نفس الوقت يتم حسابه. دعونا ننظر لفترة وجيزة كيف foldLeft ل Stream ويعرف:

override final def foldLeft[B](z: B)(f: (B, A) => B): B = { 
  if (isEmpty) z 
  else tail.foldLeft(f(z, head))(f) 
} 

إذا كان Stream فارغة، فقط إرجاع تراكم. خلاف ذلك، حساب تراكم جديد (f(z, head)) ثم اجتيازها والوظيفة إلى tail التابع Stream.

مرة واحدة f(z, head) نفذت، على الرغم من أنه لن يكون هناك إشارة متبقية إلى head. وبعد أو، وبعبارة أخرى، لن يشير أي شيء في أي مكان في البرنامج إلى head التابع Stream, وهذا يعني أن جامع القمامة يمكنه جمعها، وبالتالي تحرير الذاكرة.

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

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