YetAnotherForum
Welcome Guest Search | Active Topics | Log In | Register

Why are tables stored out of order?
Kelvin
#1 Posted : Sunday, October 31, 2021 1:30:35 AM(UTC)
Rank: Advanced Member

Groups: Registered, Moderator
Joined: 3/26/2015(UTC)
Posts: 66
Man
Location: Georgia

Thanks: 3 times
Was thanked: 0 time(s) in 0 post(s)
So I noticed that when tables are defined, or when they have new elements inserted into them, that they don't store their elements in order. For instance, if I do this:

Code:

table <- {
a = 0
b = 1
c = 2
d = 3
}

foreach(key, i in table) {
print(key + " = " + i)
}


The result I get is this:

Code:

a = 0
c = 2
b = 1
d = 3


Similarly, if I insert something at runtime, it won't always be put at the end of the table. Why is this?
absence
#2 Posted : Thursday, November 11, 2021 10:55:56 AM(UTC)
Rank: Advanced Member

Groups: Registered
Joined: 8/23/2014(UTC)
Posts: 143
Man
Location: Northern Germany & Lincolnshire, U.K.

Thanks: 2 times
Was thanked: 10 time(s) in 10 post(s)
Tables store data using hashed keys (slots) for indexing, to speed up processing. Otherwise they'd exponentially slow down with size.
So the objects get stored under a key hash, not the key itself. When iterating, again for sake of processing speed, the hashtable will be iterated. So they ARE in a specific order, it just is not obviously related to something meaningful for human eyes.
(PS: As Hashtable size and hence organization is also dynamic, iteration order could even change when adding slots)
And BTW, that's the main reason why slots/keys can only be integer or string, because that's what Squirrels' internal (quite fast) hash algorithm is limited to

If you need to order output, iterate through it and store the keys to an array, sort the array as you like, then iterate that array to output table keys/data like this:
Code:

local sorted=[] ;
foreach (slot,object in mytable) { sorted.append(slot) } ;
sorted.sort(@(a,b) a<=>b) ; //comparison works on strings, too... guess why and how ;-)
foreach (slot in sorted) { print (slot+" = " + mytable[slot]+"\n") ; }
}
gcgcgc
#3 Posted : Tuesday, November 23, 2021 10:44:44 AM(UTC)
Rank: Member

Groups: Registered
Joined: 4/19/2011(UTC)
Posts: 11

Thanks: 1 times
Was thanked: 1 time(s) in 1 post(s)
Because Squirrel uses hash tables for its tables.
https://en.wikipedia.org/wiki/Hash_table
Each item is stored in a seemingly random position so that it hopefully goes into a different bucket, to speed up finding the item you want. It's not really random though, you need to be able to look for the same key in the same location later.
When looping through all the items in a table, Squirrel just goes through each bucket in turn because it's faster than building up a list and then sorting it.



Users browsing this topic
Guest
Forum Jump  
You cannot post new topics in this forum.
You cannot reply to topics in this forum.
You cannot delete your posts in this forum.
You cannot edit your posts in this forum.
You cannot create polls in this forum.
You cannot vote in polls in this forum.

Clean Slate theme by Jaben Cargman (Tiny Gecko)
Powered by YAF 1.9.4 | YAF © 2003-2010, Yet Another Forum.NET
This page was generated in 0.047 seconds.