Max evaluation formula

Hi,

I have to find max (and min) values of an OderedCollection. I have seen
many times the following formula to find maximum values:

maxTestTable := OrderedCollection new.
valueMax := maxTestTable inject: 1 into: [:answer :each | answer max:
each ].

Now: it works when the 1 is smaller than the maximum value in the
collection, otherwise it gives back 1, which is not good in the
following case (in the range of -5 to -2.5):

        ( 5 to: 10 ) do: [ :x | maxTestTable add:  0 - (x * 0.5)].

if you execute the valueMax now and inspect it, you will see it is 1
(instead of -2.5).

(By the way the same (i.e the opposite) is true for min).

Well, an obvious circumvention would be to inject the first value:

     valueMax := maxTestTable inject: (maxTestTable at:1) into:
[:answer :each | answer max: each ].

but then you check the first value 2 times, which is not a big deal,
only I have a bad feeling coming from the old fashioned programmer
tradition: why should I check it twice?

Is there a better way to find the max (min) values?

Thanks,
Janos

Janos,

> Is there a better way to find the max (min) values?

I think I might be missing something here, but why not just use

maxTestTable inject: -100000 into: [:answer :each |
        answer max: each ].

BTW.  For non time critical situations, and smallish collections,  I
usually use

aCollection asSortedCollection last

--
Ian

Use the Reply-To address to contact me (limited validity).
Mail sent to the From address is ignored.

Ian,

I am staying in battle (well in joy) of my function plotting MVP
triads, where I have chosen one way to create the values table first..
Your BuildView tutorial is an excellent starting point...

In the general case where you look for max and min, you cannot have a
presupposition of -100000. What if the function range is -150000
-120000?

The asSortedCollection is much more esthetical (even if it sorts, but
you are right, if it is not time critical).

Many thanks,
Janos

Janos wrote:

> Is there a better way to find the max (min) values?

I don't think there is an elegant solution.  However you express it, you'll
always have the problem of what to do if the collection is empty -- which makes
it difficult to find a sensible general solution that one could add to
Collection.

I don't know of any way of doing a #max which isn't strange or clunky, unless
you can make use of knowledge that only the caller would have (the range of
possible values and whether the collection can be empty).

FWIW, I have a "strange" solution which I use occasionally.  A custom object
which responds to #max: by answering the parameter.  The class is called
Identity[*], and so a max implementation could read:

    aCollection
        inject: Identity new
        into: [:max :each | max max: each].

but you still have the problem of empty collections.

    -- chris

[*] So named because it acts as a mathematical (left-)identity value for a
number of binary operations, +, -, *, #max:, etc, so you can use it to
distribute any of those operations across any non-empty collection.  Eg.
    aCollection
        inject: Identity new
        into: [:sum :each | sum + each].

Janos,

> In the general case where you look for max and min, you cannot have a
> presupposition of -100000. What if the function range is -150000
> -120000?

OK, fair comment (although I would have thought that you could come up
with _some_ value that would suit most occasions).

How about ...

maxTestTable inject: nil into: [:answer :each |
        answer ifNil: [each] ifNotNil: [answer max: each ]].

You could use the same technique when looking for a min value.  It will
answer nil if the collection is empty so you might want to also add a
test for that - although your original code would have a similar problem.

--
Ian

Use the Reply-To address to contact me (limited validity).
Mail sent to the From address is ignored.

Ian,


I did not know you could have inject: nil, until now I have learned:
nil could be dangerous.

But yes! This is it!

Now the esthetical beauty of Smalltalk (and the order of the world) has
been restored, and I have even 2 different solutions. Great!

Thanks again,
Janos

Janos wrote:

> Is there a better way to find the max (min) values?

Another way -- which I had completely forgotten about -- is to add #injectInto:
to Collection

==========================
injectInto: a2Block
 "same as #inject:into: except that it starts with the first element (in #do:
  order) of the collection, or throws an error if there are no elements"

#CUadded.

 ^ self
        injectInto: a2Block
        ifEmpty: [self error: 'Collection is empty'].
==========================
injectInto: a2Block ifEmpty: a1Block
 "same as #inject:into: except that it starts with the first element (in #do:
  order) of the collection, and answers the value of a1Block if there are no
  elements"

 | acc block1 block2 block |
#CUadded.

 block := block1 := [:first | acc := first. block := block2].
 block2 := [:each | acc := a2Block value: acc value: each].

 self do: [:each | block value: each].

 ^ block == block2
      ifTrue: [acc]
      ifFalse: [a1Block value].
==========================

With those defined you can compute the max with just

    aCollection injectInto: [:acc :each | acc max: each].

This implementation of #injectInto:ifEmpty: is perhaps a little precious ;-)

    -- chris

Chris,

wow!

This belongs for me to the graduate degree of Smalltalk University.

Very nice and elegant solution.

Thank you,
Janos

"Chris Uppal" <[hidden email]> wrote in message
news:43ef3f48$0$1167$[hidden email]...
> Janos wrote:
>
>> Is there a better way to find the max (min) values?
>
> Another way -- which I had completely forgotten about -- is to add
> #injectInto:
> to Collection
> ...

Why not just?

    aCollection inject: aCollection anyOne into: [:max :each | max max:
each].

(much as I like the use of blocks in your implementation :-)).

Regards

Blair

Blair,

> Why not just?
>
>     aCollection inject: aCollection anyOne into: [:max :each | max max:
> each].

Three reasons:

1)  Janos's question was about how to find the maxima it without considering
the same element twice in the #inject:into:.  Apparently he finds the idea
distasteful.  And I have complete sympathy -- not so much because it's
inefficient, but it's /unclean/.  (Moderately obfuscated too -- you have to
stop and think to see that it works.)

2) It doesn't generalise to other pairwise operations, such as finding the
product of a collection.

3) I hadn't noticed that you had added #anyOne to D6...

BTW, I think there should be a #removeAnyOne operation too.  Ideally it should
remove, and answer, the same object as would be answered by #anyOne, but at
minimum part of its contract should be that:

    [aCollection isEmpty] whileFalse:
        [self doSomethingWith: aCollection removeAnyOne]

does not introduce any needless inefficiency.  I know that you don't favour
(further) broadening the Collections protocol, but I find such loops rather
useful; for instance as a natural way to maintain a "work queue" during any
operation that both generates and dispatches work items.  And implementing it
to satisfy the above conditions requires breaking encapsulation.

> (much as I like the use of blocks in your implementation :-)).

Imitation is the sincerest form of flattery...

(And, indeed, the only form for which I have any talent at all ;-)

    -- chris

Blair McGlashan wrote:
injectInto: a2Block ifEmpty: a1Block
  "same as #inject:into: but start with first element (in #do: order)
   of the collection.  Answer value of a1Block iff collection isEmpty.
  "

        | block result |
        self detect: [:any| true] ifNone: [^a1Block value].
        block := [:r :f| block := r. f].
        result := [:r :n| result := a2block value: r value: n].
        self do: [:each | result := block value: result value: each].
        block := nil.
        ^result


-cstb

cstb wrote:

       result := [:r :n| a2block value: r value: n].

>     self do: [:each | result := block value: result value: each].
>     block := nil.
>     ^result


-cstb

cstb wrote:

> self detect: [:any| true] ifNone: [^a1Block value].

Why not just:

    self isEmpty ifTrue: ...

much clearer, and presumably at least as quick ?

> block := [:r :f| block := r. f].
> result := [:r :n| result := a2block value: r value: n].
> self do: [:each | result := block value: result value: each].
> block := nil.

Why set 'block' to nil ?

> ^result

    -- chris

Chris Uppal escribió:
> cstb wrote:
>>self detect: [:any| true] ifNone: [^a1Block value].
> Why not just:
>     self isEmpty ifTrue: ...
> much clearer, and presumably at least as quick ?

Here at work we're always tempted to implement #ifEmpty:
#ifNotEmpty: in collection, ala #ifNil: #ifNotNil.

We are too conservative and didn't implemented them yet. :-D

Regards,

--
Esteban.

Esteban A. Maringolo wrote:

> Here at work we're always tempted to implement #ifEmpty:
> #ifNotEmpty: in collection, ala #ifNil: #ifNotNil.
>
> We are too conservative and didn't implemented them yet. :-D

<symathetic grin/>

The one I keep missing, but have never dared add is Boolean>>andNot:

    -- chris

Chris,

        neat implementation!  Its 8.5% faster than ours in Collection.  BTW, we
call it fold: after lisp & fp usage:

fold: binaryBlock
     "Evaluate the block with two elements of the receiver,
      then with the result of the first evaluation and another element,
      then with the result of the second evaluation and another
      element...
      For unordered collections, elements are picked in some unspecified
      order, for ordered collections, they are picked in the order they
      are stored in the collection.  Answer the result of the final
      evaluation. If the receiver is empty, fail. If the receiver
      contains a single element, answer the element."
     "#('to' 'be' 'or' 'not' 'to' 'be') asSet fold: [:a :b | a, ' ', b]"

     | firstValue nextValue |
     firstValue := nextValue := Object new. "a convenient object not in
the receiver"
     self do:
         [:each |
          firstValue == nextValue
             ifTrue: [nextValue := each]
             ifFalse: [nextValue := binaryBlock value: nextValue value:
each]].
     ^nextValue == firstValue
         ifTrue: [self emptyCollectionError]
         ifFalse: [nextValue]

But you're cheating yourself if you don't add an overriding
implementation in SequenceableCollection:

fold: binaryBlock
     | size nextValue |
     (size := self size) = 0 ifTrue: [^self emptyCollectionError].
     nextValue := self at: 1.
     2 to: size do:
         [:i |
          nextValue := binaryBlock value: nextValue value: (self at: i)].
     ^nextValue

Chris Uppal wrote:
--
_______________,,,^..^,,,____________________________
Eliot Miranda              Smalltalk - Scene not herd

Eliot,

> neat implementation!  Its 8.5% faster than ours in Collection.

Thanks, but the idea was all Blair's.  (I think the block-based
#do:separatedBy: implementation was his, anyway).


> But you're cheating yourself if you don't add an overriding
> implementation in SequenceableCollection:

I should have thought of that myself.  Surprisingly, having tested it, it turns
out that the "sane" implementation is actually very marginally slower on
Dolphin !  (I think because it cannot take the optimised path of #do: but
incurs the cost of range-checking in #from:to:keysAndValuesDo:)

I have to admit that a plain-Jane implementation using #do: and a Boolean flag
is significantly faster still, but that's boring...  But now I've measured it,
I shall have to decide which version to live with -- grace vs. speed :-(

    -- chris

======= plain Jane version =========
injectInto: a2Block ifEmpty: a1Block
 "same as #inject:into: except that it starts with the first element (in #do:
order)
 of the collection, and answers the value of a1Block if there are no elements"

 | isFirst acc |
#CUadded.

 isFirst := true.
 self do: [:each | isFirst
    ifTrue: [acc := each. isFirst := false]
    ifFalse: [acc := a2Block value: acc value: each]].

 ^ isFirst
  ifTrue: [a1Block value]
  ifFalse: [acc].

==============================