What is the time complexity of reading a list element by index? If it's O(n) instead of O(1), does the "for each item in list" block at least read the list elements in O(1) time?
I haven't seen official statements on any optimizations added to the AI2 lists data type, which can be experimentally verified to be linked lists.
Linked lists add in-memory pointers to their list item values, pointing to the next item. (I can't tell if they also have previous pointers.)
You can verify this by searching this board for my Ouroborous sample.
So for timing purposes, I would expect selecting item 1,000,000 of an AI2 list to take 1,000,000 times as long as selecting item 1 from that list, traversing 1,000,000 links.
That sounds reasonable. I haven't verified it experimentally.
It would be quite dumb of that block to not keep its place between loop cycles.
I can imagine doing some mischief to the list links between cycles, for interesting results.
An sqlite database will be quicker than an AI2 list for "big data"
If I replace a list with a dictionary where the keys are indices 1, 2, 3..., will I get a “list” with O(1) element access time?
I started an experiment for this, and got an unexpected result in the Blocks Editor, without even connecting to the Companion yet:
I may have to interpose a global variable for the dictionary access.
dictionary_complexity.aia (2.2 KB)
PS ... It was my Brave browser on my new PC, blocking some of the Blockly code.
The problem cleared up when I turned off Brave script monitors for this site.
Never mind.
I set up a test framework you can play with, for timing tests.
It took seven milliseconds to build up a dictionary of 1,000,000 entries, and less than a millisecond to access the last item.
My list test was still running across a bio break, so I have no results for you but a negative one. I suspect the Add Item To List block is not finding any pointer to the last item of the list, and has to wlk the whole list every time it wants to add an item to the list. Using the Insert Item at Slot 1 block might be faster. I leave that to you to try.
dictionary_complexity (1).aia (3.8 KB)
I went to clean up my testing session, and found this result:
The list experiment took 25 minutes to add 1,000,000 items to a list, in a compiled app.
I suspect it is going the long way around for every Add Item to List operation.
Switching to an Insert List Item block did not speed up the updates.
dictionary_complexity (2).aia (4.4 KB)
Thank you, ABG.
For what it is worth, using sqlite:
To create 1 million records took 0.47 secs
To read back all 1 million records (id and value) took 1.5secs
To query and return the 1 millonth record took 0.000096 of a second
Even with just a single value for each record the db was 58mb !
1 Like
Oh wow, this is actually very fast. Thank you.