TCL的阵列是在什么样的数据结构中实现的？

Question

在TCL中处理非常大的日期时，我想知道在数组中搜索的速度有多快。不幸的是，数组中的填充过程不如其他著名的脚本语言中执行得好。

Answer 1

Tcl称为"数组"的数据结构是从字符串值到变量的关联映射（它被认为是类似变量的，因为它有一个名称，您可以执行高级操作，如将trace附加到它）。从本质上讲，它是一个哈希表（事实上，它是所有哈希表实现中速度最快的一个），因此随着元素数量的增加，它的扩展性非常好。

但它与C、Java、C#、Python等语言中的数组不同…Tcl中与这些数组最匹配的是列表，它是一个值（即无名称、可自动序列化），包含从"小"整数（即索引）到值的紧凑映射。它的重量比Tcl数组轻得多（实际上，它是使用C数组实现的）。

它们不支持同一组操作。事实上，Tcl中还有第三个数据结构需要注意：字典。这是一个从字符串到值的关联映射值。它还使用哈希表（使用与Tcl用于数组的超快算法相同的算法）来实现，尽管有一些自定义，因此有一个固定的迭代顺序（插入顺序，因为当你往返序列化时，它有很好的属性）。

你可以把列表放在字典里，也可以把字典放在列表里。您可以将任意一个放置在数组元素中。但是您不能将数组（或数组的元素）放入列表或字典中；你能做的最好的事情就是把数组的名称放进去（因为这只是一个普通的旧字符串）。

---

性能比较

列表是创建速度最快的（尤其是使用lrepeat），并且具有快速更新和快速查找操作。假设你是按索引工作的。搜索内容需要线性扫描。

数组和字典的创建速度较慢——最慢的创建速度取决于的具体操作——但它们都支持超快速查找和按键更新。（测试密钥的存在也会进行查找；它在算法上几乎与读取相同。）搜索特定有效载荷的存在仍然很慢；它仍然需要线性扫描。

请注意，在Tcl:中计时时，总是计时对过程的调用，因为过程比免费代码得到了更多的优化。

proc doStuffList {size value1 value2} {
    for {set i 0} {$i < $size} {incr i} {
        lappend theList $i
    }
    return [list [lindex $theList $value1] [lindex $theList $value2]]
}
proc doStuffDict {size value1 value2} {
    for {set i 0} {$i < $size} {incr i} {
        dict set theDict $i $i
    }
    return [list [dict get $theDict $value1] [dict get $theDict $value2]]
}
proc doStuffArray {size value1 value2} {
    for {set i 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]"

在这台笔记本电脑上，我得到了这样的输出：

列表：每次迭代58.565204微秒dicts:114.074002微秒/次迭代数组：每次迭代118.863908微秒

但要注意，哪一个是最好的选择完全取决于你正在做的事情的细节使用最适合您算法的数据结构；合身会确保它对你有很好的效果。

Answer 2

这里有一个简单的测试，显示数组和列表的性能。我的初始测试显示，列表的填充速度比数组快。Array在搜索时间上加快了一些速度。

array.tcl

#!/usr/bin/tclsh
set array_time [time {
        array unset my_array
        for {set i 0} {$i < 365} {incr i} {
                set "my_array($i)" $i
        }
        set a [info exists my_array(180)]
        set b [info exists my_array(366)]
} 100]
set list_time [time {
        set my_list [list]
        for {set i 0} { $i < 365} {incr i} {
                lappend my_list $i
        }
        set x [lsearch $my_list 180]
        set y [lsearch $my_list 366]
} 100]
puts "$a, $b"
puts "$x, $y"
puts "array: $array_time

输出：

% ./array.tcl
1, 0
180, -1
array: 360.54830999999996 microseconds per iteration
list: 362.89529000000005 microseconds per iteration