2

简单的问题：我有一个包含 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 字符串运算符。

4

3 回答 3

5

使用 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
于 2013-09-26T23:12:58.407 回答
1

如果要进行就地编辑，将文本添加到末尾，可以执行以下操作：

sed -ie 's/$/WHATEVER/g' FILENAME

或者，将文本添加到开头：

sed -ie 's/^/WHATEVER/g' FILENAME

特殊字符必须通过\. 正则表达式备忘单是您最好的朋友。

于 2015-02-14T16:32:22.150 回答
-1

不确定计算复杂性，但这有效：

t=${A[@]}
S=${t// /}
于 2013-09-26T23:17:07.203 回答