Re: associated lists
Kat, I am not sure which version you were referring to, but if it's the last
'official' release in the archives, about two years old, it had not two, but
three versions, based on the same 'parallel' lists theme: standard, using find
for shorter lists (up to several hundred items), sorted, using binary search for
longer lists, and a hybrid with the cross-over point at 100 items.
I have not done any tests recently; at the time I tried 7 or 8 different schemes
(just from memory, some sort of comparison was included in the original
package), and the 'parallel lists' scheme was clearly superior. But, as you well
know, Euphoria is a bit of a moveable feast: Rob adds some new optimisations to
almost every version. Also processor characteristics change a lot over time, so
a bench mark that was quite reasonable yesterday possibly does not make much
sense today.
The trouble with the scheme you are suggesting is that you still have to 'unify'
the two halves under a common label. And as far as indexing, fetching, setting
and inserting operations are concerned, the corresponding functions (and they
have to be functions, because Rob would not give us parameter passing by
reference!:)), the two-level sequence does not seem to be much of a handicap.
Just as a curiosity, I am including a simplified version I am currently using.
You will notice, the nomenclature has changed a bit, but essentially it the same
beast as the one in the archives.
jiri
>Jiri, in your associated lists, both versions seem to be "parallel"
>lists of {{name},{value}}. Why not two separate lists of {name} and
>{value}? Wouldn't find()ing be faster with a split system, with it's
>inherently shorter sequences?
>Courious as a,
>Kat
-- tables.e : tables | dictionaries | associative lists
-- jiri babor
-- jbabor at paradise.net.nz
-- 2 August 2002
-- version 3.00
----------------------------------------------------------------
-- 'parallel sequence' scheme: {{key1, ..kN}, {val1, ..valN}}
----------------------------------------------------------------
-- without warning
-- without type_check
global constant EMPTY = {{},{}} -- empty table
global function index(sequence table, object key)
-- return *key* index, or zero if key not found
return find(key, table[1])
end function
global function fetch(sequence table, object key)
-- return table item with indicated key
return table[2][find(key, table[1])]
end function -- fetch
global function set(sequence table, object key, object new_value)
-- replace specified table item with a new value
-- return modified table
table[2][find(key, table[1])] = new_value
return table
end function -- set
global function insert(sequence table, object key, object val)
-- add new entry
table[1] = append(table[1], key)
table[2] = append(table[2], val)
return table
end function
global function store(sequence table, object key, object val)
-- store val in table under given key
-- if matching key is found, corresponding value is replaced
-- otherwise new key as well as value are appended
-- return modified table
integer i
i = find(key, table[1]) -- key index
if i then
table[2][i] = val
else
table[1] = append(table[1], key)
table[2] = append(table[2], val)
end if
return table
end function -- store
global function join(sequence table1, sequence table2)
-- concatenate table1 and table2
return {table1[1] & table2[1], table1[2] & table2[2]}
end function
global function delete(sequence s, object key)
-- delete entry with the specified key from the table s
sequence s1,s2
integer i,m
s1 = s[1]
s2 = s[2]
i = find(key, s1) -- index
m = length(s1)
return {s1[1..i-1]&s1[i+1..m], s2[1..i-1]&s2[i+1..m]}
end function -- delete
global function sort_table(sequence s)
-- shell sort table s by keys in ascending order
object t1i,t1j,t2i,t2j -- temporary objects
sequence s1,s2
integer gap, j, first, last
s1 = s[1]
s2 = s[2]
last = length(s1)
gap = floor(last / 3) + 1
while 1 do
first = gap + 1
for i = first to last do
t1i = s1[i]
t2i = s2[i]
j = i - gap
while 1 do
t1j = s1[j]
t2j = s2[j]
if compare(t1i, t1j) >= 0 then
j += gap
exit
end if
s1[j+gap] = t1j
s2[j+gap] = t2j
if j <= gap then
exit
end if
j -= gap
end while
s1[j] = t1i
s2[j] = t2i
end for
if gap = 1 then
return {s1,s2}
else
gap = floor(gap / 3) + 1
end if
end while
end function -- sort_table
global function Fetch(object table, sequence keys)
-- return item from *nested* table : 'deep' fetch
for i = 1 to length(keys) do
table = fetch(table, keys[i])
end for
return table
end function -- Fetch
global function Set(sequence table, sequence keys, object new_value)
-- 'deep', recursive set for *nested* tables
integer i,m
m = length(keys)
i = find(keys[1],table[1])
if m = 1 then
table[2][i] = new_value
else
table[2][i] = Set(table[2][i], keys[2..m], new_value)
end if
return table
end function -- Set
global function Insert(sequence table, sequence keys, object new_val)
-- 'deep', recursive insert for nested tables
-- store new_val in table under new (last) key in keys sequence
-- return modified table
integer i,n
n = length(keys)
if n = 1 then
table[1] = append(table[1], keys[1])
table[2] = append(table[2], new_val)
else
i = find(keys[1], table[1]) -- key index
table[2][i] = Insert(table[2][i], keys[2..n], new_val)
end if
return table
end function
global function Store(sequence table, sequence keys, object val)
-- 'deep', recursive store for *nested* tables
-- store val in table under last key in keys sequence
-- return modified table
integer i,n
i = find(keys[1], table[1]) -- key index
n = length(keys)
if n = 1 then
if i then
table[2][i] = val
else
table[1] = append(table[1], keys[1])
table[2] = append(table[2], val)
end if
else
table[2][i] = Store(table[2][i], keys[2..n], val)
end if
return table
end function -- Store
|
Not Categorized, Please Help
|
|
