最快的方式在Smalltalk

Question

給定兩個集合中進行選擇使用其他的收集對象：

srcCollection := #('Lorem' 'ipsum' 'dolor' 'sit' 'amet,' 'consectetur' 'adipisicing' 'elit,' 'sed' 'do' 'eiusmod' 'tempor' 'incididunt' 'ut' 'labore' 'et' 'dolore' 'magna' 'aliqua.' 'Ut' 'enim' 'ad' 'minim' 'veniam,' 'quis' 'nostrud' 'exercitation' 'ullamco' 'laboris' 'nisi' 'ut' 'aliquip' 'ex' 'ea' 'commodo' 'consequat.' 'Duis' 'aute' 'irure' 'dolor' 'in' 'reprehenderit' 'in' 'voluptate' 'velit' 'esse' 'cillum' 'dolore' 'eu' 'fugiat' 'nulla' 'pariatur.' 'Excepteur' 'sint' 'occaecat' 'cupidatat' 'non' 'proident,' 'sunt' 'in' 'culpa' 'qui' 'officia' 'deserunt' 'mollit' 'anim' 'id' 'est' 'laborum').  
objCollection := #('Lorem' 'numquam' 'eius' 'modi' 'tempora' 'incidunt' 'ut' 'labore' 'et' 'dolore' 'magnam' 'aliquam' 'ipsum' 'dolor' 'ex' 'ea' 'commodo' 'consequat.' 'Duis' 'aute' 'irure' 'dolor' 'in' 'reprehenderit' 'in' 'voluptate' 'velit' 'esse' 'cillum' 'dolore' 'eu' 'fugiat' 'nulla' 'pariatur.' 'Excepteur' 'sint' 'occaecat' 'cupidatat' 'non' 'proident,' 'sunt' 'in' 'culpa' 'qui' 'officia' 'deserunt' 'mollit' 'anim' 'id' 'est' 'laborum' 'Sed' 'ut' 'perspiciatis' 'unde' 'omnis' 'iste' 'natus' 'error' 'sit' 'voluptatem' 'accusantium' 'doloremque' 'laudantium,' 'totam' 'rem' 'aperiam,' 'eaque' 'ipsa' 'quae' 'ab' 'illo' 'inventore' 'veritatis' 'et' 'quasi' 'architecto' 'sit' 'amet,' 'consectetur' 'adipisicing' 'elit,' 'sed' 'do' 'eiusmod' 'tempor' 'incididunt' 'ut' 'labore' 'et' 'dolore' 'magna' 'aliqua.' 'Ut' 'enim' 'ad' 'minim' 'veniam,' 'quis' 'nostrud' 'exercitation' 'ullamco' 'laboris' 'nisi' 'ut' 'aliquip' 'beatae' 'vitae' 'dicta' 'sunt' 'explicabo.' 'Nemo' 'enim' 'ipsam' 'voluptatem' 'quia' 'voluptas' 'sit' 'aspernatur' 'aut' 'odit' 'aut' 'fugit,' 'sed' 'quia' 'consequuntur' 'magni' 'dolores' 'eos' 'qui' 'ratione' 'voluptatem' 'sequi' 'nesciunt.' 'Neque' 'porro' 'quisquam' 'est,' 'qui' 'dolorem' 'ipsum' 'quia' 'dolor' 'sit' 'amet,' 'consectetur,' 'adipisci' 'velit,' 'sed' 'quia' 'non' 'quaerat' 'voluptatem.' 'Ut' 'enim' 'ad' 'minima' 'veniam,' 'quis' 'nostrum' 'exercitationem' 'ullam' 'corporis' 'suscipit' 'laboriosam,' 'nisi' 'ut' 'aliquid' 'ex' 'ea' 'commodi' 'consequatur?' 'Quis' 'autem' 'vel' 'eum' 'iure' 'reprehenderit' 'qui' 'in' 'ea' 'voluptate' 'velit' 'esse' 'quam' 'nihil' 'molestiae' 'consequatur,' 'vel' 'illum' 'qui' 'dolorem' 'eum' 'fugiat' 'quo' 'voluptas' 'nulla' 'pariatur?'). 

其中objCollection保證包含在srcCollection所有元素。注意：在我的應用程序中，objCollection實際上是包含這些字符串作爲標識符而不重複的複雜對象。

我一直在測量並試圖優化選擇objCollection中也在srcCollection中的所有對象。下面的時間以毫秒爲單位，使用Pharo 1.2中的[ 1000 timesRepeat: [ ... ] ] timeToRun，Stack VM和Windows XP與2Gb內存。這些是我的嘗試：

objCollection intersection: srcCollection 
7537 
7507 

objCollection select: [: str | srcCollection includes: str ] 
7471 
7507 

srcCollection collect: [: str | objCollection detect: [: obj | obj = str ] ] 
4227 
4323 

有沒有更快的方法？

Answer 1

如果您有能力將asSet添加到這兩個收藏中，您可能會做得更快。我從1480年到197毫秒。

Answer 2

前兩個做同樣的事情：Collection >> #intersection:的執行是self select: [:each | aCollection includes: each]。

Collection >> #intersection:最終使用self anySatisfy: [:x | x = mySearchObj ]來完成它的工作，它使用#do:遍歷集合。 #detect:最終做同樣的事情。

我懷疑你看到的區別並不是因爲三者中的任何一個比另一個更有效，而是垃圾收集等產品。由於其語義清晰，我選擇#intersection:。它說你想要什麼，而不是另外兩個，你只看到你如何得到你想要的，並且必須推斷/推斷意圖。

Answer 3

這兩個集合都有重複。

srcCollection size ~= srcCollection asSet size. 
objCollection size ~= objCollection asSet size. 

如果你要處理重複，假設你有一個可用的總訂單通過<另一種可能就是用這種方法（成本N1 *日誌（N1）+ N2 *日誌（N2）+ N1 + N2代替n1 * n2爲天真的交集）

Collection>>sortedIntersection: aCollection 
    "Answer the intersection of two collections, sorted by < and accounting duplicates." 
    | intersection obj objStream src srcStream | 
    srcStream := self sorted readStream. 
    objStream := aCollection sorted readStream. 
    intersection := (Array new: self size) writeStream. 
    [srcStream atEnd | objStream atEnd] whileFalse: 
     [src := srcStream next. 
     obj := objStream next. 
     [src = obj] whileFalse: 
      [[src < obj] whileTrue: [srcStream atEnd ifTrue: [^intersection contents]. src := srcStream next]. 
      [obj < src] whileTrue: [objStream atEnd ifTrue: [^intersection contents]. obj := objStream next]]. 
     intersection nextPut: src]. 
    ^intersection contents 

這也將使用堆，並刪除第一個元素，但緩慢。

heapSortedIntersection: aCollection 
    "Answer the intersection of two collections, sorted by < and accounting duplicates." 

    | intersection obj src objHeap srcHeap | 
    srcHeap := Heap withAll: self. 
    objHeap := Heap withAll: aCollection. 
    intersection := (Array new: self size) writeStream. 
    [srcHeap isEmpty | objHeap isEmpty] whileFalse: 
     [src := srcHeap removeFirst. 
     obj := objHeap removeFirst. 
     [src = obj] whileFalse: 
      [[src < obj] whileTrue: [srcHeap isEmpty ifTrue: [^intersection contents]. src := srcHeap removeFirst]. 
      [obj < src] whileTrue: [objHeap isEmpty ifTrue: [^intersection contents]. obj := objHeap removeFirst]]. 
     intersection nextPut: src]. 
    ^intersection contents 

最後，如果你還沒有獲得一個總訂單，你可以簡單地用一個袋子，仍然佔重複

bagIntersection: aCollection 
    "Answer the intersection of two collections, accounting duplicates." 

    | objBag absentTag | 
    objBag := Bag withAll: aCollection. 
    absentTag := Object new. 
    ^self reject: [:each | (objBag remove: each ifAbsent: [absentTag]) == absentTag]