sistema_progs

Programas para customizar o meu entorno de traballo nos meus equipos persoais
Log | Files | Refs

array.sh (2863B)

      1 #!/usr/bin/env bash
      2 
      3 if [[ ! ${BLE_VERSION-} ]]; then
      4   source ../../src/benchmark.sh
      5 fi
      6 
      7 S=({1..10000})
      8 
      9 # 2016-07-07
     10 # ここでは巨大配列に対して効率的に処理を実行する方法について考える。
     11 
     12 #------------------------------------------------------------------------------
     13 # array#filter
     14 
     15 function truncateD.1 {
     16   local -a A=()
     17   A=("${S[@]}")
     18 
     19   local N=${#S[@]}
     20   local i=$((N/4*3))
     21   A=("${S[@]::i}")
     22 }
     23 function truncateD.unset1 {
     24   local -a A=()
     25   A=("${S[@]}")
     26 
     27   local N=${#S[@]}
     28   local i=$((N/4*3))
     29   for ((j=i;j<N;j++)); do
     30     unset 'A[i]'
     31   done
     32 }
     33 function truncateD.unset2 {
     34   local -a A=()
     35   A=("${S[@]}")
     36 
     37   local N=${#S[@]}
     38   local i=$((N/4*3))
     39   for ((j=N;--j>=i;)); do
     40     unset 'A[j]'
     41   done
     42 }
     43 
     44 # ble-measure truncateD.1 # 101972us for 10k
     45 # ble-measure truncateD.unset1 # 347972us for 10k
     46 # ble-measure truncateD.unset2 # 203972us for 10k
     47 # # 元の配列の長さと削除する長さに依存する。
     48 
     49 function filterD.1 {
     50   local -a A=()
     51   A=("${S[@]}")
     52 
     53   local i j=-1 N=${#S[@]}
     54   for ((i=0;i<N;i++)); do
     55     if ((A[i]%243!=2)); then
     56       ((++j!=i)) && A[j]="${A[i]}"
     57     fi
     58   done
     59 
     60   local k
     61   for ((k=N;--k>j;)); do
     62     unset 'A[k]'
     63   done
     64 }
     65 
     66 function filterD.2 {
     67   local -a A=()
     68   A=("${S[@]}")
     69 
     70   local field i=0 j=-1 N=${#S[@]}
     71   for field in "${A[@]}"; do
     72     if ((field%243!=2)); then
     73       ((++j!=i)) && A[j]="$field"
     74     fi
     75     ((i++))
     76   done
     77 
     78   local k
     79   for ((k=N;--k>j;)); do
     80     unset 'A[k]'
     81   done
     82 }
     83 
     84 ble-measure filterD.1 # 855972us for 10k
     85 ble-measure filterD.2 # 551972us for 10k
     86 
     87 
     88 #------------------------------------------------------------------------------
     89 
     90 function seq_read.1 {
     91   local s=0 N=${#S[@]}
     92   for ((i=0;i<N;i++)); do
     93     ((s+=S[i]))
     94   done
     95 }
     96 
     97 function reverse_read.1 {
     98   local s=0 N=${#S[@]}
     99   for ((i=N-1;i>=0;i--)); do
    100     ((s+=S[i]))
    101   done
    102 }
    103 
    104 # ble-measure seq_read.1
    105 # ble-measure reverse_read.1
    106 
    107 #------------------------------------------------------------------------------
    108 # sparse_array_read
    109 #
    110 #   bash では疎な配列を作成することができる。
    111 #   疎な配列に対して連続的に添字を動かしてアクセスする場合の速度はどうか。
    112 #   疎な配列の場合には連続的に添字を動かすと殆どの場合で hit しない。
    113 #   この様な場合にアクセスは遅くならないだろうかというのが気になる。
    114 #
    115 
    116 S1=()
    117 S1[1]=1
    118 S1[10]=1
    119 S1[100]=1
    120 S1[1000]=1
    121 S1[10000]=1
    122 S1[100000]=1
    123 
    124 function sparse_array_read.dense {
    125   local s=0
    126   for ((i=0;i<10000;i++)); do
    127     ((s+=S[i]*i))
    128   done
    129 }
    130 
    131 function sparse_array_read.1 {
    132   local s=0
    133   for ((i=0;i<10000;i++)); do
    134     ((s+=S1[i]*i))
    135   done
    136 }
    137 
    138 function sparse_array_read.1r {
    139   local s=0
    140   for ((i=0;i<10000;i++)); do
    141     ((s+=S1[9999-i]*i))
    142   done
    143 }
    144 
    145 # ble-measure sparse_array_read.dense
    146 # ble-measure sparse_array_read.1
    147 # ble-measure sparse_array_read.1r