array-reverse.sh (15167B)
1 #!/usr/bin/env bash 2 3 if [[ ! ${BLE_VERSION-} ]]; then 4 printf '%s\r' 'loading ble.sh...' 5 source ../../out/ble.sh --lib 6 printf '%s\n' 'loading ble.sh... done' 7 fi 8 9 S=({1..10000}) 10 11 S1=({1..10}) 12 S2=({1..100}) 13 S3=({1..1000}) 14 S4=({1..10000}) 15 S5=({1..100000}) 16 17 # 総評: 18 # 19 # 他の行列にコピーする場合には reverse3 が最速である。 20 # in-place の時は reverse5.1 が最速である。 21 # 22 # インターフェイスを少し変えると reverse7.2b が最速である。 23 # 24 # 改行が含まれている要素がないと保証できる場合は 25 # ある程度以上の要素数の時に外部コマンドを呼び出した方が速くなる。 26 # 27 28 ## @var measure_reverse_flags 29 ## 30 ## measure_reverse_flags に含まれる文字に該当する 31 ## reverse について計測を行います。 32 ## 33 measure_reverse_flags=01234567C 34 35 _ble_measure_count=1 36 37 #------------------------------------------------------------------------------ 38 # reverse 39 # 40 # bash では同時に二つ以上の配列に触ると遅くなる。 41 # 更に逆順にループを回した場合も遅くなる。 42 # この様な場合にどう reverse を実装するのがよいか。 43 # 44 45 function copy.0 { 46 local -a A=() 47 A=("${S[@]}") 48 } 49 ble-measure copy.0 # 55072us for 10k (何と reverse.2 よりも遅い... [@] は [*] より遅い様だ) 50 51 #------------------------------------------------------------------------------ 52 # 2016-07-07 愚直な実装 O(N^2) 53 # 54 # function reverse.0 { 55 # local -a A=() 56 # local e N=${#S[@]} 57 # for ((i=0;i<N;i++)); do 58 # A[i]="${S[N-1-i]}" 59 # done 60 # } 61 62 function ble/array#reverse0 { 63 local __ble_dst=$1 __ble_src=${2:-$1} 64 if [[ $__ble_dst != $__ble_src ]]; then 65 builtin eval " 66 local __ble_i __ble_len=\${#$__ble_src[@]} 67 $__ble_dst=() 68 for ((__ble_i=0;__ble_i<__ble_len;__ble_i++)); do 69 $__ble_dst[__ble_i]=\${$__ble_src[__ble_len-1-__ble_i]} 70 done" 71 else 72 builtin eval " 73 local __ble_i=0 __ble_j=\$((\${#$__ble_src[@]}-1)) __ble_tmp 74 while ((__ble_i<__ble_j)); do 75 __ble_tmp=\${$__ble_src[__ble_i]} 76 $__ble_src[__ble_i]=\${$__ble_src[__ble_j]} 77 $__ble_src[__ble_j]=\$__ble_tmp 78 ((__ble_i++,__ble_j--)) 79 done" 80 fi 81 } 82 83 if [[ $measure_reverse_flags == *0* ]]; then 84 # (a) $__ble_dst=() なし 85 # (b) $__ble_dst=() あり ... N が大きい時に速くなるので採用 86 # (c) $__ble_dst+=() で追記 ... 却って遅いので却下 87 88 # ----------------------------------- # (a) (b) (c) 89 ble-measure 'ble/array#reverse0 A S' # 1101969.90 us 671970.00 us 787970.10 us 90 ble-measure 'ble/array#reverse0 A S1' # 533.60 us 543.00 us 657.10 us 91 ble-measure 'ble/array#reverse0 A S2' # 3509.60 us 3490.00 us 4620.10 us 92 ble-measure 'ble/array#reverse0 A S3' # 40569.60 us 35770.00 us 47570.10 us 93 ble-measure 'ble/array#reverse0 A S4' # 1031969.60 us 618970.00 us 738970.10 us 94 fi 95 96 #------------------------------------------------------------------------------ 97 # 2016-07-07 external commands (改行が含まれていると駄目) 98 # 99 # # ～ O(N) 100 # # 外部コマンド呼び出し 101 # # 改行が含まれていると駄目 102 # function reverse.1 { 103 # local -a A=() 104 # A=($(printf '%s\n' "${S[@]}" | tac)) 105 # } 106 # # ～ O(N) 107 # # 外部コマンド呼び出し 108 # # 改行が含まれていると駄目 109 # function reverse.2 { 110 # local -a A=() 111 # IFS=$'\n' eval 'A=($(echo "${S[*]}" | tac))' 112 # } 113 # ble-measure reverse.1 # 99972us for 10k 114 # ble-measure reverse.2 # 44372us for 10k *** 115 116 function ble/array#reverse1 { 117 local __ble_dst=$1 __ble_src=${2:-$1} 118 ble/util/assign-array "$__ble_dst" "printf '%s\n' \"\${$__ble_src[@]}\" | tac" 119 } 120 function ble/array#reverse2 { 121 local __ble_dst=$1 __ble_src=${2:-$1} 122 IFS=$'\n' ble/util/assign-array "$__ble_dst" "tac <<< \"\${$__ble_src[*]}\"" 123 } 124 125 if [[ $measure_reverse_flags == *1* ]]; then 126 ble-measure 'ble/array#reverse1 A S1' # 13970.00 us 127 ble-measure 'ble/array#reverse1 A S2' # 13470.00 us 128 ble-measure 'ble/array#reverse1 A S3' # 18370.00 us 129 ble-measure 'ble/array#reverse1 A S4' # 86950.00 us 130 ble-measure 'ble/array#reverse1 A S5' # 824000.00 us 131 fi 132 133 if [[ $measure_reverse_flags == *2* ]]; then 134 ble-measure 'ble/array#reverse2 A S1' # 9120.00 us 135 ble-measure 'ble/array#reverse2 A S2' # 10570.00 us 136 ble-measure 'ble/array#reverse2 A S3' # 13370.00 us 137 ble-measure 'ble/array#reverse2 A S4' # 35160.00 us 138 ble-measure 'ble/array#reverse2 A S5' # 286000.00 us 139 fi 140 141 #------------------------------------------------------------------------------ 142 # 2016-07-07 for ～ O(N) 143 # 144 # function reverse.3 { 145 # local -a A=() 146 # local e i=${#S[@]} 147 # for e in "${S[@]}"; do 148 # A[--i]="$e" 149 # done 150 # } 151 # ble-measure reverse.3 # 204972us for 10k *** 152 # 153 # Note: 154 # 155 # * dst[--i] する前に dst をクリアした方が速い。 156 # クリアしないと O(N ln N) の様な感じの応答である。 157 # 158 159 function ble/array#reverse3 { 160 local __ble_dst=$1 __ble_src=${2:-$1} 161 eval " 162 [[ \$__ble_dst != \$__ble_src ]] && $__ble_dst=() 163 local __ble_elem __ble_ind=\${#$__ble_src[@]} 164 for __ble_elem in \"\${$__ble_src[@]}\"; do 165 $__ble_dst[--__ble_ind]=\$__ble_elem 166 done" 167 } 168 169 if [[ $measure_reverse_flags == *3* ]]; then 170 ble-measure 'ble/array#reverse3 A S' # 183970.00 us 171 ble-measure 'ble/array#reverse3 A S1' # 378.00 us 172 ble-measure 'ble/array#reverse3 A S2' # 1920.00 us 173 ble-measure 'ble/array#reverse3 A S3' # 17970.00 us 174 ble-measure 'ble/array#reverse3 A S4' # 181970.00 us 175 ble-measure 'ble/array#reverse3 A S5' # 1879970.00 us 176 fi 177 178 #------------------------------------------------------------------------------ 179 # 2016-07-07 brace-expansion O(N) 180 # 181 # ブレース展開を用いて A=([0]=${S[9]} ... [9]=${S[0]}) などの文字列を生成し、 182 # それを eval するという方法。 183 # 184 # # O(N) 185 # function reverse.4.1 { 186 # local -a A=() 187 # local m="$((${#S[@]}-1))" 188 # eval "A=($(eval "printf '[$m-%d]=\"\${S[%d]}\" ' {0..$m}{,}"))" 189 # } 190 # # O(N^2) 191 # function reverse.4.2 { 192 # local -a A=() 193 # local m="$((${#S[@]}-1))" 194 # eval "A=($(eval "printf '[%d]=\"\${S[$m-%d]}\" ' {0..$m}{,}"))" 195 # } 196 # ble-measure reverse.4.1 # 369972us for 10k 197 # ble-measure reverse.4.2 # 632972us for 10k 198 199 function ble/array#reverse4.1 { 200 local __ble_dst=$1 __ble_src=${2:-$1} 201 eval "local __ble_max=\$((\${#$__ble_src[@]}-1))" 202 eval "$__ble_dst=($(eval "printf '[$__ble_max-%d]=\${$__ble_src[%d]} ' {0..$__ble_max}{,}"))" 203 } 204 function ble/array#reverse4.1a { 205 local __ble_dst=$1 __ble_src=${2:-$1} 206 eval "local __ble_max=\$((\${#$__ble_src[@]}-1)) __ble_init" 207 ble/util/assign __ble_init "printf '[$__ble_max-%d]=\${$__ble_src[%d]} ' {0..$__ble_max}{,}" 208 eval "$__ble_dst=($__ble_init)" 209 } 210 function ble/array#reverse4.2 { 211 local __ble_dst=$1 __ble_src=${2:-$1} 212 eval "local __ble_max=\$((\${#$__ble_src[@]}-1))" 213 eval "$__ble_dst=($(eval "printf '[%d]=\${$__ble_src[$__ble_max-%d]} ' {0..$__ble_max}{,}"))" 214 } 215 216 if [[ $measure_reverse_flags == *4* ]]; then 217 # 計測コマンド # reverse4.1 reverse4.1a reverse4.2 218 #--------------------------------------- # ------------- ------------- -------------- 219 ble-measure 'ble/array#reverse4.1a A S' # 346970.00 us 371969.90 us 686970.00 us 220 ble-measure 'ble/array#reverse4.1a A S1' # 7320.00 us 728.90 us 7350.00 us 221 ble-measure 'ble/array#reverse4.1a A S2' # 12270.00 us 3469.90 us 12270.00 us 222 ble-measure 'ble/array#reverse4.1a A S3' # 39670.00 us 33569.90 us 42270.00 us 223 ble-measure 'ble/array#reverse4.1a A S4' # 355970.00 us 371969.90 us 640970.00 us 224 ble-measure 'ble/array#reverse4.1a A S5' # 3810970.00 us 4104969.90 us 76781970.00 us 225 fi 226 227 #------------------------------------------------------------------------------ 228 # 2016-07-07 improvements for in-place reverse 229 # 230 # 予め $__ble_dst=() として置かないと $__ble_dst[--__ble_i] が遅くなる。 231 # in-place の時は $__ble_dst=() としておく事ができないので遅い。 232 # 233 # A=("${S[@]}") 234 # function reverseD.swap { # ble/array#reverse0 A A 235 # local i j t 236 # for ((i=0,j=${#A[@]}-1;i<j;i++,j--)); do 237 # t="${A[i]}" 238 # A[i]="${A[j]}" 239 # A[j]="$t" 240 # done 241 # } 242 # function reverseD.for-in { # ble/array#reverse3 A A 243 # local e i="${#A[@]}" 244 # for e in "${A[@]}"; do 245 # A[--i]="$e" 246 # done 247 # } 248 # function reverseD.set-for { # ble/array#reverse5.1 A A 249 # set -- "${A[@]}" 250 # local e i="$#" 251 # A=() 252 # for e; do A[--i]="$e"; done 253 # } 254 # function reverseD.for-copy { # ble/array#reverse5.2 A A 255 # local -a B=() 256 # local e i="${#A[@]}" 257 # for e in "${A[@]}"; do B[--i]="$e"; done 258 # A=("${B[@]}") 259 # } 260 # ble-measure reverseD.swap # 693972us for 10k 261 # ble-measure reverseD.for-in # 495972us for 10k 262 # ble-measure reverseD.set-for # 258971us for 10k 263 # ble-measure reverseD.for-copy # 256972us for 10k 264 265 # set で __ble_src の内容を待避する方法 266 function ble/array#reverse5.1 { 267 local __ble_dst=$1 __ble_src=${2:-$1} 268 eval "set -- \"\${$__ble_src[@]}\" 269 local __ble_i=\$# 270 $__ble_dst=() 271 for __ble_tmp; do $__ble_dst[--__ble_i]=\$__ble_tmp; done" 272 } 273 274 # 別の配列に reverse してから __ble_dst にコピーする方法 275 function ble/array#reverse5.2 { 276 local __ble_dst=$1 __ble_src=${2:-$1} 277 eval " 278 local __ble_i=\${#$__ble_src[@]} 279 local -a __ble_arr=() 280 for __ble_tmp in \"\${$__ble_src[@]}\"; do 281 __ble_arr[--__ble_i]=\$__ble_tmp 282 done 283 $__ble_dst=(\"\${__ble_arr[@]}\")" 284 } 285 286 # 初回ループで $__ble_dst=() を実行する方法 (A) 287 function ble/array#reverse5.3 { 288 local __ble_dst=$1 __ble_src=${2:-$1} 289 eval " 290 local __ble_elem __ble_ind=\${#$__ble_src[@]} __ble_flag=0 291 for __ble_elem in \"\${$__ble_src[@]}\"; do 292 ((__ble_flag)) || __ble_flag=1 $__ble_dst=() 293 $__ble_dst[--__ble_ind]=\$__ble_elem 294 done" 295 } 296 297 # 初回ループで $__ble_dst=() を実行する方法 (B) eval による方法 298 # 遅くなった。cf ble-measure "eval ''" → 10.50 us/eval で増分が説明できる。 299 function ble/array#reverse5.4 { 300 local __ble_dst=$1 __ble_src=${2:-$1} 301 eval " 302 local __ble_elem __ble_ind=\${#$__ble_src[@]} __ble_init='$__ble_dst=() __ble_init=' 303 for __ble_elem in \"\${$__ble_src[@]}\"; do 304 eval \"\$__ble_init\" 305 $__ble_dst[--__ble_ind]=\$__ble_elem 306 done" 307 } 308 309 if [[ $measure_reverse_flags == *5* ]]; then 310 # 計測方法 # reverse5.1 reverse5.2 reverse5.3 reverse5.4 311 # ------------------------------------- # ------------- ------------- ------------- ------------- 312 ble-measure 'ble/array#reverse5.1 A S' # 238970.00 us 241970.10 us 252970.00 us 348970.10 us 313 ble-measure 'ble/array#reverse5.1 A S1' # 370.00 us 442.10 us 453.00 us 562.10 us 314 ble-measure 'ble/array#reverse5.1 A S2' # 2350.00 us 2440.10 us 2660.00 us 3640.10 us 315 ble-measure 'ble/array#reverse5.1 A S3' # 23370.00 us 23770.10 us 25570.00 us 34970.10 us 316 ble-measure 'ble/array#reverse5.1 A S4' # 239970.00 us 243970.10 us 251970.00 us 348970.10 us 317 ble-measure 'ble/array#reverse5.1 A S5' # 2518970.00 us 2561970.10 us 2723970.00 us 3506970.10 us 318 fi 319 320 #------------------------------------------------------------------------------ 321 # 2018-07-15 BASH_ARGV を用いた実装。 322 # 323 # * 元々のコードは https://github.com/dylanaraps/pure-bash-bible#reverse-an-array より。 324 # しかし、其処に載っているコードは壊れている。 325 # 326 # reverse_array() { 327 # shopt -s extdebug 328 # f()(printf '%s\n' "${BASH_ARGV[@]}"); f "$@" 329 # shopt -u extdebug 330 # } 331 # 332 # $ reverse_array A B C 333 # C 334 # B 335 # A 336 # array-reverse.sh <-- Broken 337 # 338 # BASH_ARGV には呼び出し元で設定されていた引数が末尾に続くようである。 339 # 340 # * BASH_ARGV の性質について。 341 # 試してみた所 shift や set -- をしても BASH_ARGV は更新されない様である。 342 # 従って、関数呼び出しは何れにしても必要である。 343 # 344 # * 元のコードを修正して実装する。 345 # 実際に計測してみると O(N^2) である。 346 347 function ble/array#reverse6/.helper { 348 eval "$__ble_dst=(\"\${BASH_ARGV[@]::$__ble_len}\")" 349 } 350 function ble/array#reverse6 { 351 local __ble_dst=$1 __ble_src=${2:-$1} 352 [[ ! -o extdebug ]]; local __ble_extdebug=$? 353 ((__ble_extdebug)) || shopt -s extdebug 354 eval "local __ble_len=\${#$__ble_src[@]}" 355 eval "ble/array#reverse6/.helper \"\${$__ble_src[@]}\"" 356 ((__ble_extdebug)) || shopt -u extdebug 357 return 0 358 } 359 360 if [[ $measure_reverse_flags == *6* ]]; then 361 ble-measure 'ble/array#reverse6 A S' # 1026969.70 usec/eval (copy0 = 55369.70us) 362 ble-measure 'ble/array#reverse6 A S1' # 416.60 usec/eval 363 ble-measure 'ble/array#reverse6 A S2' # 1450.60 usec/eval 364 ble-measure 'ble/array#reverse6 A S3' # 23070.60 usec/eval 365 ble-measure 'ble/array#reverse6 A S4' # 1015970.60 usec/eval 366 # ble-measure 'ble/array#reverse6 A S5' # 208812970.60 usec/eval 367 fi 368 369 #------------------------------------------------------------------------------ 370 # 2018-07-15 別の方針: 初めから引数に指定してもらう方法 371 372 function ble/array#reverse7.1 { 373 local __ble_dst=$1; shift 374 eval "$__ble_dst=(); while ((\$#)); do $__ble_dst[\$#-1]=\$1; shift; done" 375 } 376 377 function ble/array#reverse7.2 { 378 local __ble_dst=$1; shift 379 eval "local __ble_i=\$# __ble_e; $__ble_dst=(); for __ble_e; do $__ble_dst[--__ble_i]=\$__ble_e; done" 380 } 381 382 function ble/array#reverse7.2b { 383 eval "shift; local i$1=\$# e$1; $1=(); for e$1; do $1[--i$1]=\$e$1; done" 384 } 385 386 387 if [[ $measure_reverse_flags == *7* ]]; then 388 # 計測方法 # reverse7.1 reverse7.2 reverse7.2b 389 # --------------------------------------------- # ------------- ------------- ------------- 390 ble-measure 'ble/array#reverse7.2 A "${S[@]}"' # 1511970.00 us 229969.50 us 221969.50 us 391 ble-measure 'ble/array#reverse7.2 A "${S1[@]}"' # 396.00 us 331.50 us 296.50 us 392 ble-measure 'ble/array#reverse7.2 A "${S2[@]}"' # 3170.00 us 2279.50 us 2169.50 us 393 ble-measure 'ble/array#reverse7.2 A "${S3[@]}"' # 45170.00 us 22369.50 us 21569.50 us 394 ble-measure 'ble/array#reverse7.2 A "${S4[@]}"' # 1512970.00 us 231969.50 us 224969.50 us 395 ble-measure 'ble/array#reverse7.2 A "${S5[@]}"' # -------.-- us 2467969.50 us 2377969.50 us 396 fi 397 398 if [[ $measure_reverse_flags == *C* ]]; then 399 echo -n 'reverse0 : '; A=(); ble/array#reverse0 A S1; declare -p A 400 echo -n 'reverse1 : '; A=(); ble/array#reverse1 A S1; declare -p A 401 echo -n 'reverse2 : '; A=(); ble/array#reverse2 A S1; declare -p A 402 echo -n 'reverse3 : '; A=(); ble/array#reverse3 A S1; declare -p A 403 echo -n 'reverse4.1a: '; A=(); ble/array#reverse4.1a A S1; declare -p A 404 echo -n 'reverse5.1 : '; A=(); ble/array#reverse5.1 A S1; declare -p A 405 echo -n 'reverse6 : '; A=(); ble/array#reverse6 A S1; declare -p A 406 echo -n 'reverse7.2b: '; A=(); ble/array#reverse7.2b A "${S1[@]}"; declare -p A 407 fi