Самый быстрый способ выбрать объекты, используя другую коллекцию в Smalltalk - PullRequest
Новая
       8

Самый быстрый способ выбрать объекты, используя другую коллекцию в Smalltalk

3 голосов
/ 31 июля 2011

Дано две коллекции: 

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. Приведенное ниже время указывается в миллисекундах с использованием [ 1000 timesRepeat: [ ... ] ] timeToRun в Pharo 1.2 с Stack VM и Windows XP с 2 ГБ памяти. Вот мои попытки: 

objCollection intersection: srcCollection
7537
7507

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

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

Есть ли более быстрый путь?

Ответы [ 3 ]

4 голосов
/ 31 июля 2011

Первые два делают то же самое: реализация Collection >> #intersection: равна self select: [:each | aCollection includes: each].

Collection >> #intersection: в конечном итоге использует self anySatisfy: [:x | x = mySearchObj ] для своей работы, которая перебирает коллекцию с использованием #do:. #detect: в конечном итоге делает то же самое.

Я подозреваю, что разница, которую вы видите, не в том, что какой-то из трех способов более эффективен, чем в другом, а скорее в результате таких вещей, как сборка мусора.

Учитывая это, я бы выбрал #intersection: из-за его семантической ясности. Он говорит о том, что вы хотите, а не о двух других, где вы видите только то, как вы получаете то, что хотите, и должны выводить / выводить намерение.

1 голос
/ 01 августа 2011

Если вы можете позволить себе добавить asSet к двум коллекциям, вы можете сделать это быстрее.Я прошел с 1480 до 197 мс.

0 голосов
/ 14 июня 2012

Обе коллекции имеют дубликаты. 

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

Если вы хотите обрабатывать дубликаты, предполагая, что у вас есть общий заказ, доступный через <другой вариант - использовать этот метод (стоимость n1 * log (n1) + n2 * log (n2) + n1 + n2 вместо n1 * n2 для наивного пересечения) </p> 

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]
...