HackerRank账单拆分(Bill Division)问题Bash解法超时求优化

我在HackerRank平台上尝试用BASH解决Bill Division（账单拆分）问题，该问题逻辑简单，我已用多种语言完成实现，但Bash版本遇到了超时问题。

初始解决方案及问题 #

我的初始Bash代码如下：

#!/bin/bash

billDivision() {
    local n="${1}"
    local k="${2}"
    local b_charged="${3}"
    shift 3
    local bills=( "${@}" )
    
    (( b_actual = -bills[ k ] ))
    for bill in "${bills[@]}"; do
        (( b_actual += bill ))
    done
    (( b_actual /= 2 ))
    (( b_overcharge = b_charged - b_actual ))
    if(( b_overcharge <= 0 )); then
        echo "Bon Appetit"
    else
        echo "${b_overcharge}"
    fi
}

read nk
n="$( echo "${nk}" | cut -d " " -f 1 )"
k="$( echo "${nk}" | cut -d " " -f 2 )"
read ar
IFS=" "; read -ra arr <<< "${ar}"
read b
result="$( billDivision "${n}" "${k}" "${b}" "${arr[@]}" )"
echo "${result}"

该方案在除测试用例4和5外的所有用例中均可正常运行，但这两个用例会出现*Time limit exceeded（超时）*问题。

我了解Bash采用类似链表结构的稀疏数组，访问性能并非最优，推测超时原因是这些测试用例中的数组过长，验证后该假设成立。因此我尝试去掉数组，改为遍历空格分隔的字符串，甚至将函数内联：

#!/bin/bash

read nk
n="$( echo "${nk}" | cut -d " " -f 1 )"
k="$( echo "${nk}" | cut -d " " -f 2 )"
read bills
read b_charged

(( counter = 0 ))
for bill in ${bills}; do
    if(( counter++ != k )); then
        (( b_actual += bill ))
    fi
done
(( b_actual /= 2 ))
(( b_overcharge = b_charged - b_actual ))
if(( b_overcharge <= 0 )); then
    echo "Bon Appetit"
else
    echo "${b_overcharge}"
fi

但结果仍为测试用例4和5超时。

优化思路与解决方案 #

Bash原生循环在处理超大量元素时，字符串展开和迭代的开销极大，这是超时的核心原因。以下两种方案可以解决问题：

方案1：纯Bash优化（避免字符串展开） #

通过tr将空格分隔的账单转为每行一个元素，再用while read逐个读取，避免一次性展开超长字符串的开销：

#!/bin/bash

read -r nk
n=$(cut -d' ' -f1 <<< "$nk")
k=$(cut -d' ' -f2 <<< "$nk")

b_actual=0
counter=0
# 将空格分隔的账单转为换行分隔，逐行读取
while read -r bill; do
    if (( counter != k )); then
        (( b_actual += bill ))
    fi
    (( counter++ ))
done < <(tr ' ' '\n' <<< "$(read -r bills; echo "$bills")")

read -r b_charged

(( b_actual /= 2 ))
(( b_overcharge = b_charged - b_actual ))

if (( b_overcharge <= 0 )); then
    echo "Bon Appetit"
else
    echo "$b_overcharge"
fi

方案2：用awk处理（性能最优） #

awk是专门的文本处理工具，循环性能远优于Bash原生循环，直接用awk完成所有计算可以大幅提升速度：

#!/bin/bash

read -r nk
read -r bills
read -r b_charged

# 用awk计算并输出结果
awk -v k=$(cut -d' ' -f2 <<< "$nk") -v b="$b_charged" '
{
    total = 0
    for (i=1; i<=NF; i++) total += $i
    actual = (total - $(k+1)) / 2  # awk索引从1开始，需将k加1
    if (b - actual <= 0)
        print "Bon Appetit"
    else
        print b - actual
}' <<< "$bills"

超时原因分析 #

• 初始方案中，传递超长数组给函数以及遍历数组的开销极大，Bash稀疏数组的访问效率低下
• 第二个方案中，for bill in ${bills}会将整个超长字符串展开为所有元素，这个过程需要大量内存和时间，当元素数量极大时，性能会急剧下降

内容的提问来源于stack exchange，提问作者z32a7ul