Wittiest
|
  |
| Joined: 02 Mar 2009 |
| Total Posts: 9665 |
|
|
| 28 Jul 2017 09:07 PM |
| If so, why did you choose this over an array? |
|
|
| Report Abuse |
|
|
Haggie125
|
  |
| Joined: 02 Apr 2008 |
| Total Posts: 761 |
|
|
| 28 Jul 2017 10:17 PM |
| Everything in Lua is a table and that is how it shall remain because tables are awesome \o/ |
|
|
| Report Abuse |
|
|
Wittiest
|
  |
| Joined: 02 Mar 2009 |
| Total Posts: 9665 |
|
|
| 28 Jul 2017 11:34 PM |
| That's my inclination as well. In C, the use is obvious due to memory allocation. But in lua, might as well go for it with never using LLs |
|
|
| Report Abuse |
|
|
|
| 29 Jul 2017 12:30 AM |
Considered: yes Used: no
Unfortunately (yes, UNfortunately) concerns of memory and pointers aren't even topics in lua (or minimally so if they are).
To implement linked lists or many other kinds of data structures, you would likely need a node class from which to create your node objects and, well..
..lua and OOP mix like oil and water. |
|
|
| Report Abuse |
|
|
Wittiest
|
  |
| Joined: 02 Mar 2009 |
| Total Posts: 9665 |
|
|
| 29 Jul 2017 12:35 AM |
Well, you could implement it this way. http://wiki.roblox.com/index.php?title=Linked_list
Same with trees. I just don't see a point in Lua. Maybe in very special circumstances, creating a tree could be useful. |
|
|
| Report Abuse |
|
|
Briicks
|
  |
| Joined: 03 Apr 2015 |
| Total Posts: 1796 |
|
|
| 29 Jul 2017 12:37 AM |
what exactly do you want to do? get a table from in game and be able to change it and show it in game without having to shutdown?
|
|
|
| Report Abuse |
|
|
|
| 29 Jul 2017 12:54 AM |
@Wit
Interesting. I figured there should probably be a way to make rudimentary structures with tables. However, I wonder if certain graphs are complex enough to rule out that method. |
|
|
| Report Abuse |
|
|
Wittiest
|
  |
| Joined: 02 Mar 2009 |
| Total Posts: 9665 |
|
|
| 29 Jul 2017 12:55 AM |
@Briicks,
No. I was just asking a vague question. There are data structures that I've been exposed to in learning C that I don't think have any application in Lua, but I wanted to see if I was wrong about that. It turns out that tables are the way to go in Lua, so my assumption was correct. |
|
|
| Report Abuse |
|
|
|
| 29 Jul 2017 01:18 AM |
| I mean, I guess it COULD be useful? I want to say it probably has better memory and insertion time, if that's what you're looking for. Because I believe that tables will double their size whenever they get filled up, but with a linked list, it doesn't have to do that (duh), and it's probably a little bit better in memory usage, since you end up not needing to allocate the space for a table, just the members of your object. However, I could be totally wrong, because I'm not too sure how Lua works under the hood. |
|
|
| Report Abuse |
|
|
|
| 29 Jul 2017 05:53 PM |
| @Abstract likely true, but it looks like the wiki example uses tables anyway. |
|
|
| Report Abuse |
|
|
|
| 29 Jul 2017 06:04 PM |
Singly linked lists are possible in Lua, I like to use them sometimes to diverse my code.
local function Clone1DTable(tbl) local rt = {}; for i,v in pairs(tbl) do rt[i] = v; end return rt; end
local function CreateList(...) local arg = {...}; local node = {value = 0; next = nil}; function node:push(new_n) new_n.next = self; return new_n; end function node:pop() local new_n = self.next; self.next = nil; return new_n; end local node_storage = {}; for i = 1, #arg do node_storage[#node_storage + 1] = Clone1DTable(node); node_storage[#node_storage].value = arg[i]; node_storage[#node_storage].next = node_storage[#node_storage - 1]; end return node_storage[#node_storage]; --return the top of the list. end
local my_linked_list = CreateList(1, 2, 3, 4, 5); local cptr = my_linked_list; while (cptr ~= nil) do print(cptr.value, cptr.next); cptr = cptr.next; wait(); end
:) |
|
|
| Report Abuse |
|
|
PuddyTats
|
  |
| Joined: 03 Apr 2008 |
| Total Posts: 79351 |
|
|
| 29 Jul 2017 06:15 PM |
Hey, hey, hey! This is me!
So, a bit of stuff: I'm currently working with my professor on implementing exercises to represent different data structures, and as such, I have A LOT of experience with what's good and what's bad about each of them.
Ok, so why you'd use a LinkedList:
By default, tables are either arrays or maps. These are each good for different things and Linked Lists are also good for different things.
Arrays are good for two things: Getting/Setting any index is constant (i.e. this doesn't take any time at all) and adding to the back of the array is constant.
Maps are good for locating, adding, and removing anything in constant time - but it does this without any concept of order.
Linked Lists can add elements to the front and back of the list (and you could give it a pointer to the middle, making it good for adding to the middle ; or you can manipulate it for different cases). The main thing here, though, is adding to the front. If you have to add/remove at the front for something, linked lists are ideal. It's a constant time operation, meaning you won't slow down your game. Whereas using an array, it's O(n) because everything gets pushed back one spot. As a result, if you're doing a lot of it, this causes A LOT of lag. You don't want that.
Then there's sooo many other structures (binary trees, skiplists, etc) that are also good for their own purposes - it really depends on a case-by-case basis of what you need. That doesn't change by the language you're using because it all boils down to the same things and there's no perfect structure.
SO TL;DR VERSION: LinkedLists: Adding, removing from the front Arrays: Adding, removing from the back; setting, getting any index Maps: Adding, removing, setting, getting with no concept of order OTHER DATA STRUCTURES: Other things.
- |
|
|
| Report Abuse |
|
|
PuddyTats
|
  |
| Joined: 03 Apr 2008 |
| Total Posts: 79351 |
|
|
| 29 Jul 2017 06:19 PM |
ALSO BECAUSE THAT WASN'T LONG ENOUGH
Most people in Roblox just stick to tables because they're not sure how to implement their own data structures. It's a lot simpler, but it's also why so many games have massive lag.
Just try this in studio: local arr = { };
local tm = tick (); for i = 1, 1000000 do table.insert (arr, 1, i); end
print ("done insertions"); print ("that took ", tick () - tm, " ms");
Be warned tho! It'll take quite some time before that ends.
- |
|
|
| Report Abuse |
|
|
|
| 29 Jul 2017 06:22 PM |
@puddy but you *can* create your own sense of order with maps/dictionaries alphabetically. You can get the ascii int equivalent of the current char in a string index, and add it up with the rest, then determine which index is greater than or less than the others. |
|
|
| Report Abuse |
|
|
PuddyTats
|
  |
| Joined: 03 Apr 2008 |
| Total Posts: 79351 |
|
|
| 29 Jul 2017 06:23 PM |
Like a sort afterwards? It's possible but then you lose the entire purpose behind it. It won't be constant time operations at that point.
- |
|
|
| Report Abuse |
|
|
|
| 29 Jul 2017 06:41 PM |
@Puddy *sort* of. What I am talking about is something more like:
local my_dictionary = {abc = 123; def = 321};
local function ConvertStringToInt(str_ind) local rt_int = 0; for i = 1,## #t#######o rt_ind = rt_ind + (str_ind):byte(); end return rt_int; end
local function CreateOrderedArrayFromDictionary(list) local new_table = {}; local index_data = {}; local ordered_array = {}; for i,v in pairs(list) do local new_int = ConvertStringToInt(i); new_table[new_int] = v; --probably not the best thing to do performance-wise, but it works index_data[#index_data + 1] = new_int; end local min_index = math.min(unpack(index_data)); --kind of funny that unpack was deprecated sometime after Lua 5.1 local max_index = math.max(unpack(index_data)); for i = min_index, max_index do --also probably not very effecient performance-wise but it gets the point across. if new_table[i] ~= nil then --since i simply added up all of the characters in each string index to get an int, there is bound to be plenty of nil values in the table. ordered_array[#ordered_array + 1] = new_table[i]; end end return ordered_array; end
local ordered_array = CreateOrderedArrayFromDictionary(my_dictionary);
that simply allows you to order the elements in your dictionary what ever way you are trying to.
(you could also store each index as a value in a separate array that keeps track of the numerical order in which each string index was created) i.e.
local index_memory = {}; local my_dictionary = {};
local function Add_Value(key, value) index_memory[#index_memory + 1]###e#### my_dictionary[key] = value; end
for i = 1, 5 do Add_Value("index:"..i, i); end
Something more interesting about Lua tables is that index types are not only limited to int and string! You can have boolean, function, and table index types!
local my_crazy_table = { [{a = 123}] = 123; [true] = 321; [function() print"hi"; end] = 789; }; |
|
|
| Report Abuse |
|
|
PuddyTats
|
  |
| Joined: 03 Apr 2008 |
| Total Posts: 79351 |
|
|
| 29 Jul 2017 06:59 PM |
Thing about that is every time you call to create your ordered array, that's going to be a lot of steps - At least n steps to go through every element of the list; At least n steps between min_index and max_index, and could be quite a bit more;
Then you could also be using up a lot of memory to run that function (creating the new table, index data, and ordered array).
Without really going over it, I'd assume it'd fall into the same issues you'd get with using a regular array - when you get into really big data, it probably won't be very fast.
It'd probably have certain cases where it'd be great, like if you add stuff, get the ordered array, then never add or remove anything afterwards - but you'd still have benefits from using different kinds of data structures. Linked Lists would still be better if you're adding and getting from the front in a random order, for example.
- |
|
|
| Report Abuse |
|
|
|
| 29 Jul 2017 07:04 PM |
| @puddy, yeah i never said it would be efficient, i even left comments regarding efficiency. I sometimes like to use singly linked lists since they mimic behavior of the stack. :) |
|
|
| Report Abuse |
|
|
PuddyTats
|
  |
| Joined: 03 Apr 2008 |
| Total Posts: 79351 |
|
|
| 29 Jul 2017 07:10 PM |
Oh, yeah. You can usually do most of anything using any structure you want. The thing with them is they're really designed for one very specific use case, and if you use it for anything outside of that you're going to be slow.
And people won't stand for slow. If you write the perfect app that does everything you want it to and it takes a second too long, people won't use it. That's the reality of this stuff.
And that's why data structures exist! c: I luv dems.
- |
|
|
| Report Abuse |
|
|