BashでProject Euler(7) 配列

Bashに配列はあります。ただ、とても遅いです。
white spaceで区切って()で括ると配列になります。

#!/bin/bash

a=(1 2)
a+=(3)
echo ${a[@]}    # 1 2 3

a+=(3)は、見た通り要素を追加しています。
これは本当に追加なのでしょうか。多くの要素を追加して、経過時間を調べればだいたいわかります。

#!/bin/bash

N=$1
a=()
for n in `seq 1 $N`; do
    a+=($n)
done

これを、引数を変えてtimeで時間計測すると

arg    100000  1000000 10000000
real 0m0.656s 0m6.357s 1m4.420s

線形のようですね。
ちなみに、構築だけならこのほうが速いです。

#!/bin/bash

N=$1
a=(`seq 1 $N`)

3倍くらい速かったです。
参照は、次のようにします。

a=(1 2 3 4 5)
echo ${a[0]}    # 1

他の参照方法は、

echo ${a[@]}        # 1 2 3 4 5
echo ${a[@]:1:3}    # 2 3 4

2つ目は、0-baseの開始位置と長さを指定しています。

値の代入は、

a[1]=3

これで、Problem 7が解けます。エラトステネスの篩のややこしいバージョンになっていますが。

#!/bin/bash

make_prime_table() {
    N=$1
    a=()
    for n in `seq 1 $N`; do
        a+=(1)
    done
    
    for((p=2; p*p<=N; ++p)); do
        for n in `seq $((p*p)) $p $N`; do
            a[$n]=0
        done
    done
    
    for n in `seq 2 $N`; do
        if [ ${a[n]} -eq 1 ]; then
            echo $n
        fi
    done
}

primes() {
    N=10000
    ps=(`make_prime_table $N`)
    for p in ${ps[@]}; do
        echo $p
    done
    
    k=1
    while :; do
        a=()
        for n in `seq 1 $N`; do
            a+=(1)
        done
        offs=$((k*N))
        for p in ${ps[@]}; do
            if [ $((p*p)) -ge $((offs+N)) ]; then
                break
            fi
            for n in `seq $(((offs+p-1)/p*p)) $p $((offs+N-1))`; do
                a[$((n-offs))]=0
            done
        done
        for n in `seq 0 $((N-1))`; do
            if [ ${a[n]} -eq 1 ]; then
                p=$((n+offs))
                echo $p
                ps+=($p)
            fi
        done
        k=$((k+1))
    done
}

nth() {
    n=$1
    while read x
    do
        n=$((n-1))
        if [ $n -eq 0 ]; then
            echo $x
            break
        fi
    done
}

N=$1
primes | nth $N