Hi everyone,

just another idea for your consideration:

merging3: listOfRects
    ^ listOfRects reduce: [:a :b |
         self origin: (a origin min: b origin) corner: (a corner max: b
corner)]

If you care more about performance than idioms (not even sure if this is
legal):
merging4: listOfRects
    ^ listOfRects reduce: [:a :b |
         a setOrigin: (a origin min: b origin) corner: (a corner max: b
corner)]

And finally, the, in my opinion, most elegant version. Sadly, it's also the
slowest.
merging5: listOfRects
     ^ listOfRects reduce: [:a :b | a quickMerge: b]



Some unrepresentative benchmarks:

" Levente's version from above with temps "
[Rectangle merging2: {0 @ 0 extent: 100 @ 100. -20 @ -20 extent: 80 @ 80.
30 @ 30 extent: 100 @ 100}] bench '3,740,000 per second. 267 nanoseconds
per run. 37.46501 % GC time.'
" the 'clean' version "
[Rectangle merging3: {0 @ 0 extent: 100 @ 100. -20 @ -20 extent: 80 @ 80.
30 @ 30 extent: 100 @ 100}] bench '3,020,000 per second. 331 nanoseconds
per run. 40.93181 % GC time.'
" the version that mutates rectangles "
[Rectangle merging4: {0 @ 0 extent: 100 @ 100. -20 @ -20 extent: 80 @ 80.
30 @ 30 extent: 100 @ 100} asSet] bench '3,330,000 per second. 300
nanoseconds per run. 40.53189 % GC time.'
" using quickMerge "
[Rectangle merging5: {0 @ 0 extent: 100 @ 100. -20 @ -20 extent: 80 @ 80.
30 @ 30 extent: 100 @ 100}] bench '2,930,000 per second. 341 nanoseconds
per run. 42.32 % GC time.'

Best,
Tom

On Thu, Feb 18, 2021 at 11:17 PM Levente Uzonyi <leves at caesar.elte.hu>
wrote:

> Hi Chris,
>
> On Wed, 17 Feb 2021, Chris Muller wrote:
>
> > This is what I would do:
> >
> > merging: listOfRects
> >     "A number of callers of merge: should use this method."
> >     ^ listOfRects
> >         inject:
> >             (self
> >                 origin: Float infinity @ Float infinity
> >                 corner: Float infinity negated @ Float infinity negated)
> >         into: [ : rect : each | rect quickMerge: each ]
> >
> > With #quickMerge:, you're only creating a new Rectangle when it needed
> to grow to accomodate the current element, but many of the elements might
> fit completely, resulting in no additional instantiation.  Do an analysis
> of how
> > many temporary Point objects we create -- hint: it's a ton -- and my own
> attempts to optimize that in my Kml framework were not fruitful (e.g.,
> ~1%), with a trade-off of duplicating implementation across multiple
> methods and
> > making the system's code harder to read and understand and maintain.
>
> With my benchmark, your version is slower than the one from 2003,
> especially when the collection is small. And it doesn't handle the case of
> empty listOfRects the same way: it silently returns a rectangle instead of
> raising an error.
>
> Here's the version I came up with the other day:
>
>
> merging: listOfRects
>         "A number of callers of merge: should use this method."
>
>         | minTopLeftX minTopLeftY maxBottomRightX maxBottomRightY |
>         listOfRects do: [ :rectangle |
>                 | topLeft bottomRight |
>                 topLeft := rectangle topLeft.
>                 bottomRight := rectangle bottomRight.
>                 minTopLeftX
>                         ifNil: [
>                                 minTopLeftX := topLeft x.
>                                 minTopLeftY := topLeft y.
>                                 maxBottomRightX := bottomRight x.
>                                 maxBottomRightY := bottomRight y ]
>                         ifNotNil: [
>                                 topLeft x < minTopLeftX ifTrue: [
> minTopLeftX := topLeft x ].
>                                 topLeft y < minTopLeftY ifTrue: [
> minTopLeftY := topLeft y ].
>                                 bottomRight x > maxBottomRightX ifTrue: [
> maxBottomRightX := bottomRight x ].
>                                 bottomRight y > maxBottomRightY ifTrue: [
> maxBottomRightY := bottomRight y ] ] ].
>         ^self origin: minTopLeftX @ minTopLeftY corner: maxBottomRightX @
> maxBottomRightY
>
>
> Levente
>
> >
> >  - Chris
> >
> >
> > On Wed, Feb 17, 2021 at 11:27 AM Levente Uzonyi <leves at caesar.elte.hu>
> wrote:
> >       On Wed, 17 Feb 2021, Marcel Taeumel wrote:
> >
> >       > Hmm... looking at performance ... why not just add
> #asSequenceableCollection, which would only impact Set arguments?
> >
> >       I don't think we have such method. Adding one would raise the usual
> >       question: should it create a new collection or return self if self
> >       already to the requested collection kind?
> >       IIRC currently the only outlier is #asOrderedCollection which
> always
> >       creates a copy when the receiver is an OrderedCollection, and that
> >       property is being relied on, so it can't be changed...
> >
> >       > As a programmer, I do not want to choose between #merge: and
> #quickMerge:. Or similar. :-)
> >
> >       IMO, we simply need one quick solution. If you have a Set, you may
> need
> >       that help from the library even more.
> >       #quickMerge: is only good for merging two rectangles. It does not
> solve
> >       the GC issue #merge: has.
> >
> >
> >       Levente
> >
> >       >
> >       > Best,
> >       > Marcel
> >       >
> >       >       Am 13.02.2021 17:05:07 schrieb commits at source.squeak.org <
> commits at source.squeak.org>:
> >       >
> >       >       Nicolas Cellier uploaded a new version of Graphics to
> project The Inbox:
> >       >       http://source.squeak.org/inbox/Graphics-nice.446.mcz
> >       >
> >       >       ==================== Summary ====================
> >       >
> >       >       Name: Graphics-nice.446
> >       >       Author: nice
> >       >       Time: 13 February 2021, 5:04:52.453325 pm
> >       >       UUID: d13c1db2-370f-4fa6-b7ae-e6766bf0c8fb
> >       >       Ancestors: Graphics-dtl.445
> >       >
> >       >       Let Rectangle merging:/encompassing: an unordered
> collection.
> >       >
> >       >       =============== Diff against Graphics-dtl.445
> ===============
> >       >
> >       >       Item was changed:
> >       >       ----- Method: Rectangle class>>encompassing: (in category
> 'instance creation') -----
> >       >       encompassing: listOfPoints
> >       >       "A number of callers of encompass: should use this method."
> >       >       | topLeft bottomRight |
> >       >       + topLeft := bottomRight := listOfPoints anyOne.
> >       >       + listOfPoints do:
> >       >       - topLeft := bottomRight := listOfPoints first.
> >       >       - listOfPoints allButFirstDo:
> >       >       [:p |topLeft := topLeft min: p.
> >       >       + bottomRight := bottomRight max: p].
> >       >       - bottomRight := bottomRight max: p].
> >       >       ^self origin: topLeft corner: bottomRight
> >       >       !
> >       >
> >       >       Item was changed:
> >       >       ----- Method: Rectangle class>>merging: (in category
> 'instance creation') -----
> >       >       merging: listOfRects
> >       >       "A number of callers of merge: should use this method."
> >       >       + | aRectangle bottomRight topLeft |
> >       >       + aRectangle := listOfRects anyOne.
> >       >       + topLeft := aRectangle topLeft.
> >       >       + bottomRight := aRectangle bottomRight.
> >       >       - | bottomRight topLeft |
> >       >       - topLeft := listOfRects first topLeft.
> >       >       - bottomRight := listOfRects first bottomRight.
> >       >       listOfRects
> >       >       + do: [:r | topLeft := topLeft min: r topLeft.
> >       >       - allButFirstDo: [:r | topLeft := topLeft min: r topLeft.
> >       >       bottomRight := bottomRight max: r bottomRight].
> >       >       ^self origin: topLeft corner: bottomRight.
> >       >       !
> >       >
> >       >
> >       >
> >       >
> >
> >
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20210219/8c858661/attachment.html>