associated list processing speeds

ID:151820
 
Jan 28 2009, 12:40 pm
just curious if anyone knows...

Consider an associated list with 10,000 separate index/value associations:

var/L[] = list("object 1"=blah,"obj 2"=myah,....)

And let's say you wanted the value for L["some index"]

Would it be faster to determine the value in the case where:

var/L[10000] (same as above)

or

var/L[10][1000] (where the list has been split into 10 categories, each with 1000 index elements)
the second case would be accessed via L["index 1"]["index 2"]

Is either one significantly faster than the other?
What about for larger/smaller sample sizes?
Jan 28 2009, 1:06 pm
Using multidimensional lists is pretty much always going to take longer than using a single list, I would think. The lookup on an associative list is pretty fast because BYOND uses a binary tree to handle the lookup. You'd probably incur more overhead on the interpreter handling the double index than you would on the lookup itself.

I haven't run actual numbers on this though, so I suppose it's possible profiling could show you something different.

Lummox JR
Jan 28 2009, 4:14 pm
In response to Lummox JR
I have a very similar question, just with another option...
Which would be fastest here for which situation?
Generation (startup), access time, writing new information, reorganizing list contents (reading and writing).
If just one is the faster in every circumstance then no need to clarify, I just figured I'd ask specifically because the different scenarios are the reason why I want to know.

Associated list
 
var/list/L=list("A"=1,"B"=2,"C"=3)

Two separate lists
var/list/L=list("A","B","C")
var/list/LData=list(1,2,3)

One multidimensional list:
var/list/L=list(list("A","B","C"),list(1,2,3))


Jan 28 2009, 4:58 pm
In response to Lummox JR
The lookup on an associative list is pretty fast because BYOND uses a binary tree to handle the lookup.

Haha just had a pretty big d'oh moment. I did my RefSortedList for fast containment tests when the built in associative lists are hard coded and already provide that functionality. Switched to using them for my Region library and got a massive speed increase.
Jan 28 2009, 5:12 pm
In response to AJX
... given what he's just said, it would almost certainly be fastest to have an associative list.
Jan 28 2009, 5:39 pm
In response to Popisfizzy
Faster than a multi dimensional list, sure, but what about two separate lists being accessed only by a single index? Hence the question. I only threw in multi-dimensional lists as an option for completeness. :P
Jan 28 2009, 6:16 pm
In response to AJX
... you can't access to lists by a single index, as two lists would be stored at different indexes.
Jan 28 2009, 7:57 pm (Edited on Jan 29 2009, 1:56 am)
In response to Popisfizzy
What are you talking about? Maybe I don't understand what you're saying, or maybe you don't understand what I'm saying.

This is what I'm saying:
Option A: Associative List
var/list/L=list("A"=1,"B"=2,"C"=3)
var/A
for(var/i=1,i<=L.len,i++)
   A=L[i]
   world<<"[i]: [L[i]]: [L[A]]"

Option B: Two Lists Same Index
var/list/L=list("A","B","C")
var/list/LData=list(1,2,3)
for(var/i=1,i<=L.len,i++)
   world<<"[i]: [L[i]]: [LData[i]]"

As I said, both with give identical output, it is just being handled differently. An index is something used to access a specific point in a list. If you have two lists that are correlated like I describe, then you would use 1 index to access the name of the entry, then the data associated with it. Meaning you are accessing the two lists with one index.
Jan 29 2009, 7:02 am
In response to AJX
AJX wrote:
Faster than a multi dimensional list, sure, but what about two separate lists being accessed only by a single index?

Lookup by a numeric index is always going to be faster than using associations, because there's no need to traverse the binary tree. If you have an index handy, then looking up the same index in two different lists should be faster than looking up an item in one list, then looking up its associated value.

Lummox JR
Jan 29 2009, 7:40 am
In response to AJX
You can just do this instead.

var/list/L = list("A","B","C")

world << "[L[1]] = 1" // etc


If that was just an example, then forget what I said.
Jan 30 2009, 8:30 am
In response to Andre-g1
That WAS just an example. lol. Ty though.