在什么样的数据结构中实现了TCL的数组？

Question

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

Answer 1

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

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

Answer 2

Tcl 称为“数组”的数据结构是从字符串值到变量的关联映射（它被认为是类变量，因为它有一个名称你可以做一些高级的事情，比如附加一个 trace 到它）。在引擎盖下，它是一个散列 table（事实上它是所有实现中最快的散列 table 之一）所以它随着元素数量的增加而扩展得很好。

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

它们不支持同一组操作。实际上，Tcl 中还有第三种数据结构需要注意：字典。这是一个值，它是从字符串到值的关联映射。它还使用散列 table 实现（使用 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]"

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

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

但请注意，最佳选择完全取决于您正在做的事情的细节。使用数据结构最适合你的算法；合身将确保它为您提供良好的性能。

在什么样的数据结构中实现了TCL的数组？

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

arrays

tcl

性能比较