Using sortedcontainers module (sortedlist) for intra_blob etc.

[Twenkid]

I suggest using sorted lists (kept sorted automatically) regarding intra_blob and other use-cases where the list is modified and has to be in sorted order all the time:

  eval_fork_ += [   # sort per append?
                        (G, 1, 0),    # rng = input rng, fia=0;  est. match of input gradient at rng+1
                        (G- ave_blob, 1, 1),  # -root_blob_cost; est. match of input angle at rng+1
                        (Gg, rng, 0), # rng = kernel rng, fia=0; est. match of gg at rng*2
                        (Ga, rng, 0)  # rng = kernel rng, fia=0; est. match of ga at rng*2
                    ]
                    new_eval_fork_ = []  # forks recycled for next intra_blob
                    for val, irng, fia in sorted(eval_fork_, key=lambda val: val[0], reverse=True):

For short lists and sorting once the simple calls to "sorted"/sort may be similar in performance.

https://pythonawesome.com/fast-and-pure-python-implementation-of-sortedlist/ http://www.grantjenks.com/docs/sortedcontainers/ https://stackoverflow.com/questions/1109804/does-python-have-a-sorted-list

Performance: http://www.grantjenks.com/docs/sortedcontainers/performance.html

I tried sortedconainters and it automatically sorted by the first element of a tuple, so it's seamless. It sorts in ascending order, reverse order is done by an iterator:

 __reversed__()[source]
Return a reverse iterator over the sorted list.
sl.__reversed__() <==> reversed(sl)

The test:

Python 3.6.4 (default, Jan  5 2018, 02:35:40) 
[GCC 7.2.1 20171224] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import sortedcontainers
>>> s = sortedcontainers.SortedList()
>>> s.update([9,2,6,4,1])
>>> s
SortedList([1, 2, 4, 6, 9])
>>> s+=[44,11,34,67]
>>> s
SortedList([1, 2, 4, 6, 9, 11, 34, 44, 67])
>>> t = sortedcontainers.SortedList()
>>> t+=[(5,2,6,7), (1,5,7,8), (9,3,3,3)]
>>> t
SortedList([(1, 5, 7, 8), (5, 2, 6, 7), (9, 3, 3, 3)])

for i in reversed(t): print(i)
... 
(9, 3, 3, 3)
(5, 2, 6, 7)
(1, 5, 7, 8)

for i in t: print(i)
... 
(1, 5, 7, 8)
(5, 2, 6, 7)
(9, 3, 3, 3)

Documentation:

http://www.grantjenks.com/docs/sortedcontainers/introduction.html#sorted-list

[boris-kz]

Thanks Todor!

On Sun, Jun 30, 2019 at 9:41 AM Todor Arnaudov notifications@github.com wrote:

Reg.:

evalfork += [ # sort per append? (G, 1, 0), # rng = input rng, fia=0; est. match of input gradient at rng+1 (G- ave_blob, 1, 1), # -root_blob_cost; est. match of input angle at rng+1 (Gg, rng, 0), # rng = kernel rng, fia=0; est. match of gg at rng2 (Ga, rng, 0) # rng = kernel rng, fia=0; est. match of ga at rng2 ] new_evalfork = [] # forks recycled for next intra_blob for val, irng, fia in sorted(evalfork, key=lambda val: val[0], reverse=True):

and other needs for sorted collections, for short lists the simple calls to "sorted"/sort may be similar in performance, but for many appends while keeping the sorted order, the difference will grow.

https://pythonawesome.com/fast-and-pure-python-implementation-of-sortedlist/ http://www.grantjenks.com/docs/sortedcontainers/ https://stackoverflow.com/questions/1109804/does-python-have-a-sorted-list

Performance: http://www.grantjenks.com/docs/sortedcontainers/performance.html

I thought there might be caveats with defining the key for sorting since tuples are used, however I tried sortedconainters and it automatically sorted by the first element of a tuple, so it's seamless. It sorts in ascending order,I didn't find mentioning a flag for reversing, it is done by getting an iterator from the structure:

reversed()[source] Return a reverse iterator over the sorted list.

sl.reversed() <==> reversed(sl)

The test:

Python 3.6.4 (default, Jan 5 2018, 02:35:40) [GCC 7.2.1 20171224] on linux Type "help", "copyright", "credits" or "license" for more information.

import sortedcontainers s = sortedcontainers.SortedList() s.update([9,2,6,4,1]) s SortedList([1, 2, 4, 6, 9]) s+=[44,11,34,67] s SortedList([1, 2, 4, 6, 9, 11, 34, 44, 67]) t = sortedcontainers.SortedList() t+=[(5,2,6,7), (1,5,7,8), (9,3,3,3)] t SortedList([(1, 5, 7, 8), (5, 2, 6, 7), (9, 3, 3, 3)])

for i in reversed(t): print(i) ... (9, 3, 3, 3) (5, 2, 6, 7) (1, 5, 7, 8)

for i in t: print(i) ... (1, 5, 7, 8) (5, 2, 6, 7) (9, 3, 3, 3)

Documentation:

http://www.grantjenks.com/docs/sortedcontainers/introduction.html#sorted-list

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/boris-kz/CogAlg/issues/33?email_source=notifications&email_token=AFABOGOAQASM2KSPRLVOCLDP5CZXLA5CNFSM4H4MSZL2YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4G4PYMCA, or mute the thread https://github.com/notifications/unsubscribe-auth/AFABOGJK4UNAVID5PP2OMQDP5CZXLANCNFSM4H4MSZLQ .

[boris-kz]

That's good to know, but I expect fork_ to be very short or empty in most cases. So it's probably not worth extra complexity.

On Sun, Jun 30, 2019 at 10:34 AM Boris Kazachenko boris.kz@gmail.com wrote:

Thanks Todor!

On Sun, Jun 30, 2019 at 9:41 AM Todor Arnaudov notifications@github.com wrote:

Reg.:

evalfork += [ # sort per append? (G, 1, 0), # rng = input rng, fia=0; est. match of input gradient at rng+1 (G- ave_blob, 1, 1), # -root_blob_cost; est. match of input angle at rng+1 (Gg, rng, 0), # rng = kernel rng, fia=0; est. match of gg at rng2 (Ga, rng, 0) # rng = kernel rng, fia=0; est. match of ga at rng2 ] new_evalfork = [] # forks recycled for next intra_blob for val, irng, fia in sorted(evalfork, key=lambda val: val[0], reverse=True):

and other needs for sorted collections, for short lists the simple calls to "sorted"/sort may be similar in performance, but for many appends while keeping the sorted order, the difference will grow.

https://pythonawesome.com/fast-and-pure-python-implementation-of-sortedlist/ http://www.grantjenks.com/docs/sortedcontainers/ https://stackoverflow.com/questions/1109804/does-python-have-a-sorted-list

Performance: http://www.grantjenks.com/docs/sortedcontainers/performance.html

I thought there might be caveats with defining the key for sorting since tuples are used, however I tried sortedconainters and it automatically sorted by the first element of a tuple, so it's seamless. It sorts in ascending order,I didn't find mentioning a flag for reversing, it is done by getting an iterator from the structure:

reversed()[source] Return a reverse iterator over the sorted list.

sl.reversed() <==> reversed(sl)

The test:

Python 3.6.4 (default, Jan 5 2018, 02:35:40) [GCC 7.2.1 20171224] on linux Type "help", "copyright", "credits" or "license" for more information.

import sortedcontainers s = sortedcontainers.SortedList() s.update([9,2,6,4,1]) s SortedList([1, 2, 4, 6, 9]) s+=[44,11,34,67] s SortedList([1, 2, 4, 6, 9, 11, 34, 44, 67]) t = sortedcontainers.SortedList() t+=[(5,2,6,7), (1,5,7,8), (9,3,3,3)] t SortedList([(1, 5, 7, 8), (5, 2, 6, 7), (9, 3, 3, 3)])

for i in reversed(t): print(i) ... (9, 3, 3, 3) (5, 2, 6, 7) (1, 5, 7, 8)

for i in t: print(i) ... (1, 5, 7, 8) (5, 2, 6, 7) (9, 3, 3, 3)

Documentation:

http://www.grantjenks.com/docs/sortedcontainers/introduction.html#sorted-list

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/boris-kz/CogAlg/issues/33?email_source=notifications&email_token=AFABOGOAQASM2KSPRLVOCLDP5CZXLA5CNFSM4H4MSZL2YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4G4PYMCA, or mute the thread https://github.com/notifications/unsubscribe-auth/AFABOGJK4UNAVID5PP2OMQDP5CZXLANCNFSM4H4MSZLQ .