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 |
In reply to this post by Janos Kazsoki
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]. |
In reply to this post by Janos Kazsoki
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 |
In reply to this post by Janos Kazsoki
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 |
In reply to this post by Chris Uppal-3
"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 |
In reply to this post by Blair McGlashan-3
Blair McGlashan wrote:
> "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 > 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:
> Blair McGlashan wrote: > >> "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 > > > 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| a2block value: r value: n]. > self do: [:each | result := block value: result value: each]. > block := nil. > ^result -cstb |
In reply to this post by jas
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 |
In reply to this post by Chris Uppal-3
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: > 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 > > -- _______________,,,^..^,,,____________________________ 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]. ============================== |
Free forum by Nabble | Edit this page |