Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Allow accessing column entry by position #65

Open
webmaster128 opened this issue Sep 18, 2024 · 1 comment
Open

Allow accessing column entry by position #65

webmaster128 opened this issue Sep 18, 2024 · 1 comment

Comments

@webmaster128
Copy link
Member

Right now, column entries can only efficiently be accessed by the auto-incrementing ID (called "key" and "ix" in code). This is nice as it allows creating append focussed maps much easier to use than today.

However, this does not allow for selecting a random element. If you know len(), and you want to get an item between 0 and len()-1, you don't know which ID to look for. In order to serve a large number of use cases from the NFT space, we should add both efficient access by ID as well as efficient access by position. This then makes the following operations fast:

  • get first element
  • get last element
  • get nth element

In order to allow implementing that, we need some sort of secondary index.

I'm not quite sure how to effiently implement that. The challenge is somewhat similar to implementing LinkedList::get in Java. This guy recommends "some sort of tree". The best model I found so far to make that happen is a Skip List, especially "Indexable skiplist".

@uint
Copy link
Collaborator

uint commented Sep 20, 2024

That's all good.

I'm wondering if it would make sense to step back, write down a list of use cases, look at it, and then figure out if we want one or more separate abstractions for them.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants