Little problem(s) July 2022

[DavidM]

(07-07-2022 10:51 AM)pier4r Wrote:  (I hope GET is O(1) with lists in userRPL, now I start to have doubts).

It isn't with lists, but it is with type 3 or 4 arrays.

Remember that lists can contain many different types of objects as elements (even other lists), so the size of each element may vary and cannot be assumed in advance. Lists have no associated metadata (pointers, tables, etc.) that would assist in locating specific elements. The only way to locate element n is to sequentially step through elements 1..(n-1) first.

Conversely, type 3 (real) or 4 (complex) arrays use the same-sized data for each element, so the offset of a specific element is easily computed from its indices.

The varying size of the data elements in a type 29 (symbolic/exact) array give it a data structure very similar to a list, so GET is similarly constrained with those.