bash 脚本：如何有效地在字符串末尾附加字符（O（1））
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19040151/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
bash script: How to append characters at the end of a string efficiently (O(1))
提问by terr
Simple problem: I have an array A of n entries each one containing one character. I want to create the corresponding string S from this array in an efficient way, i.e. in O(n) time, without using external commands, just bash code and bash builtins.
简单的问题：我有一个包含 n 个条目的数组 A，每个条目包含一个字符。我想以一种有效的方式从这个数组中创建相应的字符串 S，即在 O(n) 时间内，不使用外部命令，只使用 bash 代码和 bash 内置函数。
This obvious way...
这种明显的方式...
func_slow ()
{
local numel=${#A[*]}
for ((i=0; i < numel ; i++))
do
S=${S}${A[$i]}
done
}
is not efficient with bash. It's O(n^2) time because the "append" operation S=${S}${A[$i]} doesn't take O(1) time worst case (or even O(1) time amortized which would be enough to guarantee an overall O(n) time). It takes O(#S) each time (clearly it generates the new string S by copying both ${S} and ${A[$i]}). The only way I can find to solve this in O(n) time (without external commands) is by defining this function
使用 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
}
and then using it like this
然后像这样使用它
S=`func_fast`
This takes O(n) time and it just uses bash code and bash builtins. Implementing (within an interpreter of a language) strings with an efficient append operator (one that would allow func_slow to run in O(n) time) while still retaining O(1) time direct access of each position of a string is pretty simple from an algorithmic point of view, I was wondering if I'm missing some special efficient bash string operator.
这需要 O(n) 时间，它只使用 bash 代码和 bash 内置函数。使用高效的附加运算符（允许 func_slow 在 O(n) 时间内运行）实现（在语言的解释器中）字符串，同时仍然保留对字符串每个位置的 O(1) 时间直接访问非常简单从算法的角度来看，我想知道我是否缺少一些特殊的高效 bash 字符串运算符。
回答by konsolebox
Use array merging with IFS:
使用 IFS 合并数组：
IFS= eval 'S="${A[*]}"'
Also if you're going to append a string to a variable, just use this form:
此外，如果您要将字符串附加到变量，只需使用以下形式：
S+="another"
Another fast way is to use printf:
另一种快速的方法是使用 printf：
printf -v S '%s' "${A[@]}"
Adding some benchmarks. With an array having 100000 integral elements:
添加一些基准。对于具有 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
回答by Oliver Niesen
If you want to do an in-place edit, adding text to the end, you can do this:
如果要进行就地编辑，在末尾添加文本，可以执行以下操作：
sed -ie 's/$/WHATEVER/g' FILENAME
Or, to add text to the beginning:
或者，在开头添加文本：
sed -ie 's/^/WHATEVER/g' FILENAME
Special characters will have to be escaped via \. A regex cheat sheet is your best friend.
特殊字符必须通过\. 正则表达式备忘单是您最好的朋友。
回答by William Pursell
Not sure about the computational complexity, but this works:
不确定计算复杂度，但这有效：
t=${A[@]}
S=${t// /}
