I just thought about it. If you really don’t care about position, why not keep it an array. You could treat it as a stack and just pop the last element each time (by keeping track of the last index and decrementing when you pop).
I don’t care about the position when i’m accessing an element, however, when i’m removing an element, the position matters. I still want to be able to remove elements at any order, but a stack will only let me remove items at the end.
The stack implementation still works in this case. Let’s say you have an element i you want to remove. Just swap i and top, then pop top element.
For a case where you want to remove elements in any order, and want to maintain O(1) time complexity, linked lists won’t help (unless they’re doubly linked, and sort of pseudo linked lists).
I’m not sure does the luau implementation allow you to swap elements, but in other languages moving a element from the middle of a stack to the top involves popping every element above that stack.
Think of a stack of plates.
You’re kinda right now that i’m thinking about it, the change from arrays to linked lists means that accessing is faster, but removing an arbitrary element in the list is slower. Not sure should i actually implement the linked list change now, because i remove elements from the list more often than i need to access them…
Using the array approach, Would this be O(1) complexity for accessing an element?
local itemId
for i, v in itemIds do
itemId = v
break
end
I don’t mean swap in a literal sense.
I mean
temp = stack[top]
stack[top] = stack[I]
stack[I] = temp
top-- (decrement top)
Yes, because in worst case it can only run once. Not sure how this would make this work though. This would have the same result as implementing a linked list.
I need to know the index position of the element i want to delete in that case, which i don’t since the itemIds are stored in an array-based stack.
This is getting confusing now, so lemme just restate the problem. I want to get a value of an arbitrary key in a list. I don’t know any keys, and i’d like to do this without iterating through every key.
Define arbitrary key (this is really the crux of the problem, and cause of confusion). The top of a stack or head of a linked list is by definition arbitrary. Or if you want it randomly, do the stack implementation I suggested, but randomly generate the index you want to swap.
By arbitrary keys i mean i have a table and i don’t know any of the keys:
local itemIds= {
[13284398] = "ItemId1",
[56765398] = "ItemId2",
[17684358]= "ItemId3"
}
I don’t know the keys 13284398, 56765398, and 17684358. But i’d like to get one of the values (“ItemId1”, “ItemId2”, or “ItemId3”) in the itemIds table.
Is there a way i can get any of the values efficiently (it can be random or not it, doesn’t matter)
If you don’t know the keys, then why do they have to be in that structure (why do the keys matter at all, other than as a way of referencing)? Why not implement a scenario where you know, at the very least, that they are sequential (like the stack method).
But given this scenario where you haven’t constructed it yourself, and therefore don’t know the keys (have been handed a random mapping), there is no way to fetch values in O(1) time.
Would this be an O(1) way to fetch a value. I think uses O(n) internally but not sure.
There is a crucial problem with this, and it’s that any other solution will be slower than a simple loop.
Performance is nice, but after all of this even the most “optimal” algorithm/data structure will be slower than a simple loop.
Lua is abstracted so farly, that any other solution will have to go through the C boundary many times.
You can even test this yourself. The time it takes to comb even 1,000,000 rows is only 0.005 seconds.
1 Like
Yes, as I say, this is O(1). This is also identical to doing a linked list or reversed stack implementation for what you’re trying to achieve.
That is O(n) since it combs through every object in the dictionary, but you can read my reply on why that’s fine.
Why is that the case? Wouldn’t it only iterate once, since he has a break in the body?
Or does Lua pre-emptively generate key/value pairs.
That still means it would have to comb through every key value pair until that point, therefore making it O(n).
Edit: I think I’m confused about the question. Are they asking how to get a random value from the dictionary? Or are they asking how to search the dictionary if it has a certain value?
But that point is the first iteration, for the worst case. So wouldn’t it be the same as itemId = itemIds[first_index]. Could be wrong, not particularly familiar with Lua internal workings,.
1 Like
Yeah I was assuming they wanted to search for if a dictionary had a certain value, not to search for a random value in the dictionary. Apologies if I misunderstood OP’s initial question.
If it is the second option, then yes that is O(1).