In what kind of data structure implemented TCL's array? -

working on manipulation of big dates in tcl wondering how fast searching in arrays. unfortunately fill process in arrays not performs in other famous scripting languages.

the data structure tcl calls “array” associative map string values variables (and it's considered variable-like, in has name , can advanced things attaching trace it). under hood, it's hash table (and in fact it's 1 of fastest hash table implementations of all) scales pretty number of elements increases.

but it's not same arrays you'd find in language c, java, c#, python, … thing in tcl closely matches list, value (i.e., nameless, automatically serializable) holds compact map “small” integers (i.e., indices) values. it's lighter weight tcl array (indeed, it's implemented using c array).

they don't support same set of operations. indeed, there's third data structure in tcl aware of: dictionary. that's value associative map strings values. it's implemented using hash table (using same super-fast algorithm tcl uses arrays) though customization there's fixed order of iteration (the insertion order, because that's got properties when round-trip serialization).

you can put lists in dictionaries , dictionaries in lists. can put either in array element. can't put array (or element of array) in either list or dictionary; best can put name of array in (as that's plain old string).

---

performance comparison

lists fastest create (especially lrepeat) , have both fast update , fast lookup operations. provided you're working index. searching contents requires linear scan.

arrays , dictionaries slower create — slowest depends on exactly you're doing — both support super-fast lookup , update key. (testing presence of key lookup; it's algorithmically identical read.) searching presence of particular payload still slow; still requires linear scan.

note when timing things in tcl: always time call procedure, procedures more heavily optimised free code.

proc dostufflist {size value1 value2} {     {set 0} {$i < $size} {incr i} {         lappend thelist $i     }     return [list [lindex $thelist $value1] [lindex $thelist $value2]] } proc dostuffdict {size value1 value2} {     {set 0} {$i < $size} {incr i} {         dict set thedict $i $i     }     return [list [dict $thedict $value1] [dict $thedict $value2]] } proc dostuffarray {size value1 value2} {     {set 0} {$i < $size} {incr i} {         set thearray($i) $i     }     return [list $thearray($value1) $thearray($value2)] }  puts "lists: [time {dostufflist 500 150 450} 1000]" puts "dicts: [time {dostuffdict 500 150 450} 1000]" puts "arrays: [time {dostuffarray 500 150 450} 1000]" 

on laptop, output:

 lists: 58.565204 microseconds per iteration dicts: 114.074002 microseconds per iteration arrays: 118.863908 microseconds per iteration 

but aware best option depends totally on details of you're doing. use data structure fits algorithm best; fitting ensure performs you.