I’d like to get any element in the dictionary without a key, O(1) time complexity.
Example dictionary
local dictionary = {
Key1 = "Stop",
Key2 = "Woke",
Key3 = "Developers"
}
Is there a way to get any value, whether it’s “Stop”, “Woke” or “Developers” without being given a key.
I searched the table library but there’s no functions there to help me. I know other programming languages have methods for this.
Is there a way to do this in roblox lua.
You can make an inversed dictionary:
local dict = {
Key1 = "Foo",
Key2 = "Bar",
Key3 = "Baz",
}
local dictInverse = {
Foo = "Key1",
Bar = "Key2",
Baz = "Key3",
}
print(dictInverse.Foo) --> O(1) time
Just a side note: please keep political statements out when not necessary!
I don’t know the exact contents of dictionary beforehand. How would i go about it?
And also, i don’t know any keys, i just have arbitrary dictionary, and i want to get a value out of it.
I believe that other languages with this kind of behavior built-in would keep a copy of the original dictionary but inversed. You can do that like so:
local dict = {
Key1 = "Foo",
Key2 = "Bar",
Key3 = "Baz",
}
local dictInverse = {}
for key, value in dict do
dictInverse[value] = key
end
print(dictInverse.Foo) --> O(1) time
Is there a reason you only want to get the key in a dictionary? There could be alternative solutions that do not require creating new dictionaries.
I’m not sure whether the solution you provided will work in my case, because i’d have to create the dictInverse before getting the key ( O(n) time complexity )
Lemme explain my problem more specifically:
I have a list called itemIds. Each time an item is created, it adds the itemId to the end of the list. Each time an item is destroyed, it gets removed from the list.
Because of this behavior of adding and removing itemIds regardless of their order in the list, the list is not sequential, and therefore is technically a dictionary.
So at runtime i may have a itemIds dictionary like the following:
-- Each letter would be an itemId
itemIds = {
[26] = "a",
[34] = "b",
[39] = "c",
[40] = "d",
[41] = "e",
[45] = "f",
[46] = "g",
[47] = "h"
}
As you can see, the indexes are integers, but they aren’t sequential, as a result:
#itemIds == 0 -- true
I’d like to be able to destroy a any (as in it doesn’t have to be random) item, based on it’s itemId stored in the dictionary.
So i need to be able to get the itemId, in order to destroy the item.
If you’re worried about O(n) time complexity, how are you creating the original dictionary in the first place. An O(n) algorithm off the back of another O(n) algorithm has no impact on overall time complexity.
How/in what scenario are you fetching itemIds currently?
Table.remove will remove the item and shift all the items after it down so the list remains sequential. Why use a dictionary?
You are correct that two O(n) algorithms would generally be no difference to a single O(n) algorithm.
However my case is quite different because:
Items are generated every time period, it’s efficient (O(1)) to create a single item.
But an item is destroyed every time period too. The specific item that’s destroyed doesn’t matter, but just one item is destroyed. I’m trying to figure out a O(1) time complexity way of doing this.
Might as well make linked lists then
You’re right, this is a possibility, but that means that removing items would be a O(n) time complexity, whereas currently it is O(1).
Could you explain this a little more. I’ve heard of the linked list data structure, but i haven’t seen any practical use case of this (until now).
Linked lists are efficient if you often insert and delete items since the order doesn’t matter.
Inserting and removing items won’t require rearrangement of the entire structure
Multiple ways to implement linked lists in lua. This is the best:
https://www.lua.org/pil/11.3.html
Linked lists work by having a link between elements. You have a head and tail in a lot of common implementations but this isn’t necessary for your requirements (doubly linked lists with a prev element also exist).
In terms of practical usage, they’re instrumental in things exactly like the problem you’re facing. E.g. The heap is a dynamic memory structure, which is used for dynamic memory allocation. When you assign a variable in C using malloc, or using the new keyword in many other languages you use dynamic memory allocation. The dynamic memory is allocated on the heap which keeps track of currently in use variables by creating links between them. When a variable is no longer in use, it’s removed from the linked list and cleared during garbage collection.
Guess I’m confused as to what the problem is exactly. You want to be able to remove element [40] = ‘d’ using the 40 or the ‘d’?
He wants to remove random items from a list and access items without knowing their index/key since the removal of items leaves gaps
So to get a element with O(1) time complexity, would that just be the first element in the linked list
But make sure you rereference your head as head.next before you delete the current head. If that makes sense.
Thank you, i’ll switch my implementation of itemIds to use linked lists instead of arrays.
ah. I see. linked list is O(n) though.
yep but it suits his purpose
He was only concerned with efficiency so used time complexity as an indicator
