❔ How do I search through a list for the first missing value in a range of numbers?
For instance; a list of
0, 1, 2, 4, 5, 6, 7, 9 would return 3 if you're looking for the first "missing" value.
Likewise, a list of 1, 2, 4, 5, 6, 7, 9 would return 0.12 Replies
Create a list that contains the full sequence, then iterate over those two lists at once
Check if the items match, and return the first one that's not matching
Yeah, but I would need it to use 3 separate ranges of numbers, and I'm trying to keep it as skinny as possible, if at all possible.
Why 3?
Two
The list you're checking, and the list you're checking against
Alternatively, you can of course check if
n+1 - 1 == 1I'm basically making a new ID, and I want it to take the first value that's free so I can use that, rather than just adding 1 to the end of the list(which will be what happens if I don't find anything). I have 3 separate ranges of numbers that would need to be checked, depending on a value that's passed in. Does that make more sense? I know I'm not explaining the best.
Also these lists are around 100 million long, so making that separate full list would be pretty impractical. 😅
I wouldn't worry about taking up every possible ID, then, to be honest
No database engine does
They just keep track of the last ID and insert the next item at that plus one
Yeah, that's fair. I was just trying to save as much space as possible, I guess. Though, I doubt anyone will hit 100 million items in one database.
Thanks for the help!
check out free lists some time
Do you have a link?
Free list
A free list (or freelist) is a data structure used in a scheme for dynamic memory allocation. It operates by connecting unallocated regions of memory together in a linked list, using the first word of each unallocated region as a pointer to the next. It is most suitable for allocating from a memory pool, where all objects have the same size.
Fre...
the id stuff is captured in this blog https://skypjack.github.io/2019-02-14-ecs-baf-part-1/
ECS back and forth
Part 1 - Introduction
Ok, I'll take a look in a little bit. Thanks!
Was this issue resolved? If so, run
/close - otherwise I will mark this as stale and this post will be archived until there is new activity.