आवंटन और वर्र्स से बचते समय स्कैला में सूची को फोल्ड करने का कुशल तरीका

Question

मेरे पास सूची में आइटम का एक गुच्छा है, और मुझे यह पता लगाने के लिए सामग्री का विश्लेषण करने की आवश्यकता है कि उनमें से कितने "पूर्ण" हैं। मैं विभाजन के साथ बाहर शुरू कर दिया है, लेकिन फिर एहसास हुआ कि मैं दो सूचियों वापस की जरूरत नहीं थी, इसलिए मैं एक गुना में स्विच:

val counts = groupRows.foldLeft((0,0))((pair, row) => 
    if(row.time == 0) (pair._1+1,pair._2) 
    else (pair._1, pair._2+1) 
    ) 

लेकिन मैं पंक्तियों का एक बहुत कुछ है समानांतर उपयोगकर्ताओं का एक बहुत के लिए के माध्यम से जाना , और यह बहुत सी जीसी गतिविधि (मेरे हिस्से पर धारणा पैदा कर रहा है ... जीसी अन्य चीजों से हो सकता है, लेकिन मुझे यह संदेह है क्योंकि मुझे लगता है कि यह हर आइटम को एक नया टुपल आवंटित करेगा)।

समय के लिए

जा रहा है, मैं के रूप में

var complete = 0 
var incomplete = 0 
list.foreach(row => if(row.time != 0) complete += 1 else incomplete += 1) 

जो जीसी ठीक करता है, लेकिन वार्स का परिचय इस फिर से लिख दिया।

मैं सोच रहा था कि क्या जीसी का दुरुपयोग नहीं करते हुए वर्र्स का उपयोग किए बिना ऐसा करने का कोई तरीका था?

संपादित करें:

जवाब मैं प्राप्त हो गया है पर मुश्किल कॉल। एक पूंछ-पुनरावर्ती अनुकूलित संस्करण की तुलना में बड़ी सूचियों (जैसे 40%) पर एक var कार्यान्वयन काफी तेजी से प्रतीत होता है जो अधिक कार्यात्मक है लेकिन समकक्ष होना चाहिए।

डीएचजी का पहला जवाब पूंछ-पुनरावर्ती व्यक्ति के प्रदर्शन के साथ-साथ लगता है, जिसका मतलब है कि आकार पास सुपर-कुशल है ... असल में, अनुकूलित होने पर यह पूंछ की तुलना में बहुत तेज गति से चलता है मेरे हार्डवेयर पर एक-एक है।

Answer 1

मुझे लगता है कि आप पहले ही एक उत्तर स्वीकार कर चुके हैं, लेकिन आप सही मायने में उल्लेख करते हैं कि वह समाधान दो बार सूची को पार करेगा। इसे कुशलतापूर्वक करने का तरीका रिकर्सन के साथ है।

def counts(xs: List[...], complete: Int = 0, incomplete: Int = 0): (Int,Int) = 
    xs match { 
    case Nil => (complete, incomplete) 
    case row :: tail => 
     if (row.time == 0) counts(tail, complete + 1, incomplete) 
     else    counts(tail, complete, incomplete + 1) 
    } 

यह प्रभावी रूप से सिर्फ एक स्वनिर्धारित fold है, सिवाय इसके कि हम 2 एक्युमुलेटरों जो सिर्फ Int रों (पुरातन) के बजाय tuples (संदर्भ प्रकार) का उपयोग करें। यह वर्स के साथ थोड़ी-थोड़ी कुशल भी होनी चाहिए - वास्तव में, बाइटकोड समान होना चाहिए।

Answer 2

यह बहुत की तरह एक परिवर्तनशील संचायक पैटर्न का उपयोग करने के लिए, आप विशेष रूप से अगर आपके संचायक फिर से उपयोग कर सकते हैं थोड़ा tidier है:

case class Accum(var complete = 0, var incomplete = 0) { 
    def inc(compl: Boolean): this.type = { 
    if (compl) complete += 1 else incomplete += 1 
    this 
    } 
} 
val counts = groupRows.foldLeft(Accum()){ (a, row) => a.inc(row.time == 0) } 

तुम सच में करने के लिए, आप निजी रूप में अपने वार्स छिपा कर सकते हैं चाहते हैं; यदि नहीं, तो आप अभी भी युद्धों के पैटर्न के मुकाबले बहुत अधिक आत्मनिर्भर हैं।

Answer 3

तुम बस इतना की तरह अंतर का उपयोग कर इसे गणना कर सकते हैं:

def counts(groupRows: List[Row]) = { 
    val complete = groupRows.foldLeft(0){ (pair, row) => 
    if(row.time == 0) pair + 1 else pair 
    } 
    (complete, groupRows.length - complete) 
} 

Answer 4

साफ दो-पास समाधान शायद सिर्फ निर्मित count विधि का उपयोग करने के लिए:

val complete = groupRows.count(_.time == 0) 
val counts = (complete, groupRows.size - complete) 

लेकिन आप कर सकते हैं एक पास में यह कर यदि आप पुनरावर्तक पर partition का उपयोग करें:

val (complete, incomplete) = groupRows.iterator.partition(_.time == 0) 
val counts = (complete.size, incomplete.size) 

यह काम करता है क्योंकि नए लौटाए गए इटरेटर्स दृश्यों के पीछे जुड़े हुए हैं और next पर कॉल करने से इसे मूल इटरेटर आगे बढ़ने का कारण बनता है जब तक कि यह एक मिलान तत्व नहीं पाता है, लेकिन यह अन्य पुनरावर्तक के लिए गैर-मिलान तत्वों को याद करता है ताकि वे डॉन न करें पुन: संकुचित होने की आवश्यकता नहीं है। एक-पास समाधान के

---

उदाहरण:

scala> val groupRows = List(Row(0), Row(1), Row(1), Row(0), Row(0)).view.map{x => println(x); x} 
scala> val (complete, incomplete) = groupRows.iterator.partition(_.time == 0) 
Row(0) 
Row(1) 
complete: Iterator[Row] = non-empty iterator 
incomplete: Iterator[Row] = non-empty iterator 
scala> val counts = (complete.size, incomplete.size) 
Row(1) 
Row(0) 
Row(0) 
counts: (Int, Int) = (3,2) 

Answer 5

शायद यह मेरे बस है, लेकिन मैं विभिन्न विशेष परतों (.size, .exists, .sum, .product) अगर वे का उपयोग करना पसंद उपलब्ध हैं।मुझे सामान्य फ़ोल्डरों की भारी-ड्यूटी पावर की तुलना में यह स्पष्ट और कम त्रुटि-प्रवण लगता है।

val complete = groupRows.view.filter(_.time==0).size 
(complete, groupRows.length - complete) 

Answer 6

ठीक है, जवाब ऊपर, लेकिन वास्तव में चाहते हैं से प्रेरित केवल एक बार सूची के ऊपर से गुजरती है और जीसी बचने के लिए, मैंने तय कर लिया है कि, प्रत्यक्ष API समर्थन की कमी का सामना करने में, मैं करने के लिए इस जोड़ना होगा मेरी केन्द्रीय पुस्तकालय कोड:

class RichList[T](private val theList: List[T]) { 
    def partitionCount(f: T => Boolean): (Int, Int) = { 
    var matched = 0 
    var unmatched = 0 
    theList.foreach(r => { if (f(r)) matched += 1 else unmatched += 1 }) 
    (matched, unmatched) 
    } 
} 

object RichList { 
    implicit def apply[T](list: List[T]): RichList[T] = new RichList(list) 
} 

फिर अपने आवेदन कोड में

(अगर मैं आयात करने के बाद छुपा हुआ), मैं वर मुक्त भाव लिख सकते हैं:

val (complete, incomplete) = groupRows.partitionCount(_.time != 0) 

और मैं क्या चाहते: एक अनुकूलित जीसी मित्रतापूर्ण दिन था टी मुझे बाकी कार्यक्रमों को वार्स के साथ प्रदूषित करने से रोकता है।

हालांकि, मैं तो लुइगी के बेंचमार्क को देखा, और करने के लिए इसे अद्यतन:

• एक लंबी सूची का उपयोग करें ताकि सूची पर कई गुजरता सभी मामलों में एक बूलियन समारोह संख्या
• उपयोग में और अधिक स्पष्ट थे तो यह है कि हम चीजों काफी

http://pastebin.com/2XmrnrrB

तुलना कर रहे हैं वर कार्यान्वयन निश्चित रूप से, काफी तेज है और भी यद्यपि लुइगी का दिनचर्या समान होना चाहिए (जैसा कि एक अनुकूलित पूंछ रिकर्सन के साथ उम्मीद करेगा)। हैरानी की बात है कि, डीएचजी का ड्यूल-पास मूल उतना तेज़ है (अगर कंपाइलर ऑप्टिमाइज़ेशन चालू होता है तो थोड़ा तेज होता है) पूंछ-रिकर्सिव एक के रूप में। मुझे समझ नहीं आता क्यों।

Answer 7

इस बारे में कैसे? कोई आयात कर नहीं।

import scala.collection.generic.CanBuildFrom 
import scala.collection.Traversable 
import scala.collection.mutable.Builder 

case class Count(n: Int, total: Int) { 
    def not = total - n 
} 
object Count { 
    implicit def cbf[A]: CanBuildFrom[Traversable[A], Boolean, Count] = new CanBuildFrom[Traversable[A], Boolean, Count] { 
    def apply(): Builder[Boolean, Count] = new Counter 
    def apply(from: Traversable[A]): Builder[Boolean, Count] = apply() 
    } 
} 
class Counter extends Builder[Boolean, Count] { 
    var n = 0 
    var ttl = 0 
    override def +=(b: Boolean) = { if (b) n += 1; ttl += 1; this } 
    override def clear() { n = 0 ; ttl = 0 } 
    override def result = Count(n, ttl) 
} 

object Counting extends App { 
    val vs = List(4, 17, 12, 21, 9, 24, 11) 
    val res: Count = vs map (_ % 2 == 0) 
    Console println s"${vs} have ${res.n} evens out of ${res.total}; ${res.not} were odd." 
    val res2: Count = vs collect { case i if i % 2 == 0 => i > 10 } 
    Console println s"${vs} have ${res2.n} evens over 10 out of ${res2.total}; ${res2.not} were smaller." 
}