[Glass] There is really no way to have an ordered/sorted collection together with indexes?

[Mariano Martinez Peck via Glass]

On Mon, Aug 7, 2017 at 4:27 PM, Norm Green via Glass <
glass at lists.gemtalksystems.com> wrote:

> Since you are keeping the prices sorted, you can lookup a price in the
> sorted list using a binary search.  This gives you a worst-case search of
> log2(n) +1, which should be pretty fast as long as the price comparison
> methods are fast.  You should be able to create a subclass of
> SortedCollection to do this.
>
>

Hi Norm,

Thanks for the idea. I was using binary search already in other places, so
yeah, I can also do that here. However, I never found out a GemStone method
for this and instead I ported the implementation from Pharo:

SequenceableCollection >> findBinaryIndex: aBlock do: actionBlock ifNone:
exceptionBlock
  "Search for an element in the receiver using binary search.
The argument aBlock is a one-element block returning
0 - if the element is the one searched for
<0 - if the search should continue in the first half
>0 - if the search should continue in the second half
If found, evaluate actionBlock with the index as argument
If no matching element is found, evaluate exceptionBlock,
with the indexes of the 'bounding' elements as arguments.
Warning: Might give invalid indexes, see examples below
Examples:
#(1 3 5 7 11 15 23)
findBinaryIndex: [ :arg | 11 - arg ]
do: [ :found | found ]
ifNone: [ :a :b | 'between: ', {a. b} printString ]
#(1 3 5 7 11 15 23)
findBinaryIndex: [ :arg | 12 - arg ]
do: [ :found | found ]
ifNone: [ :a :b | 'between: ', {a. b} printString ]
#(1 3 5 7 11 15 23)
findBinaryIndex: [ :arg | 0.5 - arg ]
do: [ :found | found ]
ifNone: [ :a :b | 'between: ', {a. b} printString ]
#(1 3 5 7 11 15 23)
findBinaryIndex: [ :arg | 25 - arg ]
do: [ :found | found ]
ifNone: [ :a :b | 'between: ',{a. b} printString ] "

  | index low high test |
  low := 1.
  high := self size.
  [
  index := (high + low) // 2.
  low > high ]
    whileFalse: [
      test := aBlock value: (self at: index).
      test = 0
        ifTrue: [ ^ actionBlock value: index ]
        ifFalse: [
          test > 0
            ifTrue: [ low := index + 1 ]
            ifFalse: [ high := index - 1 ] ] ].
  ^ exceptionBlock cull: high cull: low



Do you think that's safe enough or I am missing a GemStone implementation?
The only thing I found in GemStone is:

SequenceableCollection >> binarySearchIncludes: anObject
  "Returns true if the argument anObject is equal to an element of the
receiver.
 Returns false otherwise.

 Note that this search is optimized based on the assumption that the sort
criteria
 is consistent with the equality comparison. That is, if (x <= y) & (y <=
x) then (x = y).
 This assumption will not hold if sorting is done on one instance variable
and
 equality comparison is done on another instance variable (for example).
 SortedCollection>>#'includes:' is no longer implemented and the linear
search
 is inherited from Collection.  See bug 40575."

  ^ (self indexOf: anObject) ~~ 0



Also keeping 2 collections that each reference the same large set of
> objects should not be that expensive in terms of repository size.
>

Well.. yes.. but these can have 365 days * 20 years * 30k companies. And
this is only daily prices..not even considering minute/hourly/etc.  So I am
not sure.



> That said, I agree that keeping the prices in 1 collection is a cleaner
> design.
>
>
Yes...it complicates logic a lot having 2...

Cheers,


> Norm
>
>
>
> On 8/7/17 11:23, Mariano Martinez Peck via Glass wrote:
>
> Hi guys,
>
> I am storing huge lists of "prices". For this, it really helps me to store
> things ordered (by date)...either in an SequenceableCollection or a
> SortedCollection. On the other hand, I do want to use indexes to speedup my
> query to find price for a given date (equality index).
>
> But I have found no way to have them both. The only workaround I found is
> to keep 2 collections for each of these collections, one sorted/ordered,
> and the other one an unordered one for querying via index. But this is a
> pain from "developing" point of view, as well as for unnecessary repository
> growth.
>
> Am I missing something?
>
> Thanks in advance,
>
> --
> Mariano
> http://marianopeck.wordpress.com
>
>
> _______________________________________________
> Glass mailing listGlass at lists.gemtalksystems.comhttp://lists.gemtalksystems.com/mailman/listinfo/glass
>
>
>
> _______________________________________________
> Glass mailing list
> Glass at lists.gemtalksystems.com
> http://lists.gemtalksystems.com/mailman/listinfo/glass
>
>


-- 
Mariano
http://marianopeck.wordpress.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.gemtalksystems.com/mailman/private/glass/attachments/20170807/8633e843/attachment.html>