Multi-dimensional or Associative lists?

ID:151989
 
Jun 27 2008, 8:15 pm
I've been wondering, if it's better to store data as a multi-dimensional list, or as a list with several list associations. (With the same content.)
Basically, considering everything taken into account, (data stored during compile-time, data stored during runtime, data stored in savefiles, CPU used, etc.), which is better in a given situation.
Of course, there are some situations when one is always better than the other, let's try and forget (however impossible that may be) about those situations, and contradict ourselves with this question.
Let's use this example that comes to mind:
//Storing every single turf in the world:
var/turfs[world.maxx][world.maxy][world.maxz]
for(var/turf/T in world)
    turfs[T.x][T.y][T.z]=T
//OR
var/list/turfs=list()
for(var/turf/T in world)
    turfs["[T.x],[T.y],[T.z]"]=T
//Of course, with both conditions starting with a savefile being created,
//and ending with this:
F["turfs"]<<turfs
Which usage is better in such a situation? The 3-dimensional list, or the associative one?
Jun 27 2008, 9:53 pm (Edited on Jun 29 2008, 2:52 pm)
The former threatens the list limit (65,535 unique lists), while the latter threatens the string limit (65,535 unique strings). In practice the former is slightly less intensive, with only 1+x+x*y lists, with x*y lists containing z elements each. The latter would require x*y*z strings. However, if you are using lists frequently and strings infrequently it is possible that the latter might have more room before you threaten the limit.

If you are doing this for saving purposes, directly dumping every turf in the world is a very inefficient means of saving. I would suggest using DMP/DMM saving (for considerable hard drive space savings at the cost of efficiency) or writing each map file as a custom symbol table -- instead of writing each turf, write each Z-level data as a carriage-return delimited sequence of characters into a savefile, with directories handled by :

"1"={"
.......#####....
.......#...#....
.....**+...#.T..
..T..*.#...#....
.....*.######...
.T...*...+..#...
.....*...#..#...
...T.*...####...
.....*.T........
..T.**...T......
....*T..........
...T*.....T.....
....*...........
....*..T........
...T*...........
....*..........."}


...et cetera.


If you are not doing this for saving purposes, why do you need to store a list of the turfs at all when you can simply get any turf any time you like with the locate(x,y,z) proc?
Jun 27 2008, 10:25 pm
In response to Jtgibson
It was just an example, and I got some good info from you on this. I have not yet made my own map saving code.
Thanks.
Jun 27 2008, 10:27 pm
In response to Jtgibson
Saving hard-drive space? Essentially, the DMM format is a bitmap format, meaning it's very bulky.
Jun 27 2008, 11:11 pm
In response to Popisfizzy
Why not try creating a compression code then, for example, instead of #####, you could simply put #5 to say that there's 5 #'s in a row. And, you can even get further in depth, by figuring out what characters are in common through out and referencing them in a list so, like %=##$ and *=&^& so ##$&^&#;#$##$&^& becomes %*%%*. Compression isn't that hard of a concept. You could even get down even to the bits of the data for compression. (I'm pretty sure most compression formats are compressed in some way like that.)
Jun 27 2008, 11:23 pm
In response to Popisfizzy
Jun 27 2008, 11:40 pm
In response to Naokohiro
It's because compression is damned hard to do in DM.
Jun 28 2008, 12:29 am
You could also use a single list. It takes a bit more processing, but one list can store many times the object limit. Just use tokens to separate items that would normally be separate lists. You could also use the order of items in the list to determine associations. (I do that in my BigBump library.)
Jun 28 2008, 7:24 am
Naokohiro wrote:
I've been wondering, if it's better to store data as a multi-dimensional list, or as a list with several list associations. (With the same content.)

Neither. Both of them will use up lists toward's BYOND's internal limit, but the latter will also use up strings. A single list is your best bet.

BYOND doesn't really handle multi-dimensional lists very well, but anyway I've always found them more of a hindrance than a help ever since I escaped BASIC.

Lummox JR
Jun 28 2008, 9:48 am
In response to Lummox JR
Okay, say I'm using a multidimensional list to store 144 objs which are added to the player's screen? (Stored only once, of course.) They are in a 12x12 grid, so it's L[12][12]. The objects are altered dynamically so their icons are changed and the player can see it. So, I'm using those numbers as coordinates to easily get the right object. Should I not do it that way? If it was a single list, I'd have to loop through the objects and get the right one based on its screen_loc var, which is worse I would think than simply doing L[x][y].
(Anyone can answer.)
Jun 28 2008, 10:54 am
In response to Naokohiro
Use a single list where order matters. No looping is required. For instance, if items are listed by column then use L[12*(X-1)+Y].
Jun 28 2008, 11:46 am
In response to ACWraith
Thanks. That will work good.
So, the consensus is that using just a list is better than an associative or a multi-dimensional, then?
Jun 28 2008, 6:41 pm
In response to Naokohiro
Of course it is; but there's nothing inherently bad in using associative lists. A simple associative list counts the same for the list limit as a regular list. Learn To Love Associative Lists. =D
Jun 28 2008, 10:22 pm
In response to Kaioken
Aye, but as was pointed out, associative lists count towards the text limit as well as the list limit.
Jun 28 2008, 10:27 pm
In response to Naokohiro
That's an incorrect conclusion. Obviously enough, associative lists count only for the list limit. Text strings count for the text string limit. They're not connected at all.

Yes, it is perfectly possible and not uncommon for an associative list not to use text strings. The only limitation is that numbers cannot be used as a key in an associative list.
Jun 28 2008, 10:31 pm
In response to Kaioken
Lummox JR wrote:
Naokohiro wrote:
I've been wondering, if it's better to store data as a multi-dimensional list, or as a list with several list associations. (With the same content.)

Neither. Both of them will use up lists toward's BYOND's internal limit, but the latter will also use up strings. A single list is your best bet.


Lummox JR

He didn't say anything about the text limit, though, my bad. (I assumed he meant it would use up strings that count towards the string limit, he could have simply meant it uses more memory.)
Ask him about it, he obviously knows more than me.
Jun 28 2008, 10:43 pm
In response to Naokohiro
Naokohiro wrote:
He didn't say anything about the text limit, though, my bad. (I assumed he meant it would use up strings that count towards the string limit, he could have simply meant it uses more memory.)

You're misunderstanding what I said, in reply to you saying:

as was pointed out, associative lists count towards the text limit as well as the list limit.

What I said is, using a [associative or not] list counts towards the list limit. Using a text string counts toward the strings limit. But, using associative lists doesn't count toward the string limit. Obviously enough, if a list (any list) has a string in it, it counts toward the string limit, but its the string <t>itself, it doesn't have anything to do with the list itself, other than it possibly keeps it in existence due to referencing it (DM's strings are cached, which also means you can reuse the same strings how many times you want with no disadvantage). But obviously, if there's an obj in a list, then it counts for the /obj limit, if there's a string it counts for the string limit...

If you're going to stick strictly to the first post's example, you could redesign it not to use strings should the need arise, of course.

Ask him about it, he obviously knows more than me.

I've no need to ask about it, though.