bash脚本:如何有效地在字符串末尾附加字符(O(1))

Question

简单的问题:我有一个n个条目的数组A,每个条目包含一个字符.我想以有效的方式从这个数组创建相应的字符串S,即在O(n)时间内,不使用外部命令,只需bash代码和bash内置.

这种明显的方式......

func_slow ()
{ 
 local numel=${#A[*]}
 for ((i=0; i < numel ; i++))
 do
    S=${S}${A[$i]}   
 done
}

使用bash效率不高.它是O(n ^ 2)时间,因为"追加"操作S = $ {S} $ {A [$ i]}不会花费O(1)时间最坏情况(甚至O(1)时间摊销,这将是足以保证整个O(n)时间.它每次都需要O(#S)(显然它通过复制$ {S}和$ {A [$ i]}来生成新的字符串S.).我能在O(n)时间内找到解决这个问题的唯一方法(没有外部命令)就是定义这个函数

func_fast ()
{
 local numel=${#A[*]}
 for ((i=0; i < numel ; i++))
 do
    echo -n "${A[$i]}"
 done
}

然后像这样使用它

S=`func_fast`

这需要O(n)时间,它只使用bash代码和bash内置.使用有效的追加运算符(允许func_slow在O(n)时间运行的运算符)实现(在语言的解释器中)字符串,同时仍保留O(1)时间直接访问字符串的每个位置非常简单.从算法的角度来看,我想知道我是否缺少一些特殊的高效bash字符串运算符.

Answer 1

使用与IFS的数组合并:

IFS= eval 'S="${A[*]}"'

此外,如果您要将字符串附加到变量,只需使用此表单:

S+="another"

另一种快速方法是使用printf:

printf -v S '%s' "${A[@]}"

添加一些基准.使用具有100000个整数元素的数组:

time printf -v X '%s' "${A[@]}"

real    0m0.481s
user    0m0.474s
sys     0m0.004s

time IFS= eval 'X="${A[*]}"'

real    0m0.107s
user    0m0.106s
sys     0m0.000s

X=''; L=${#A[@]}; time for (( I = 0; I < L; ++I )); do X+=${A[I]}; done

real    0m24.469s
user    0m24.351s
sys     0m0.074s