sistema_progs

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

201902-sort.sh (5208B)

      1 #!/usr/bin/env bash
      2 
      3 if [[ ! ${BLE_VERSION-} ]]; then
      4   source ../../src/benchmark.sh
      5 fi
      6 
      7 declare RANDSUP=32768
      8 
      9 function fill-rand {
     10   data=()
     11   local i n=${1:-10000}
     12   for ((i=0;i<n;i++)); do
     13     data[i]=$RANDOM
     14   done
     15 }
     16 
     17 function sort.command {
     18   data=($(printf '%s\n' "${data[@]}"|sort -n))
     19 }
     20 
     21 function sort.qsort1.1 {
     22   local L=$1 U=$2
     23   local p=${data[L+RANDOM*(U-L)/RANDSUP]}
     24 
     25   local i=$L j=$((U-1)) t
     26   while :; do
     27     while ((data[i]<p)); do ((i++)); done
     28     while ((i<j&&p<=data[j])); do ((j--)); done
     29 
     30     ((i<j)) || break
     31 
     32     ((t=data[i],data[i++]=data[j],data[j--]=t))
     33   done
     34   while ((data[j]==p)); do ((j++)); done
     35   #((j++))
     36   ((L+1<i)) && sort.qsort1.1 "$L" "$i"
     37   ((j+1<U)) && sort.qsort1.1 "$j" "$U"
     38 }
     39 function sort.qsort1 {
     40   local L=0 U=${#data[@]}
     41   ((L+1<U)) && sort.qsort1.1 "$L" "$U"
     42 }
     43 
     44 #------------------------------------------------------------------------------
     45 
     46 function sort.qsort3.1 {
     47   local L=$1 U=$2
     48 
     49   local length=$((U-L))
     50   if ((length<=1)); then
     51     return 0
     52 
     53   elif ((length==2)); then
     54     local a=${data[L]} b=${data[L+1]}
     55     if ((a>b)); then
     56       data[L]=$b
     57       data[L+1]=$a
     58     fi
     59     return 0
     60 
     61   elif ((length==3)); then
     62     local a=${data[L]} b=${data[L+1]} c=${data[L+2]}
     63     if ((b<a)); then
     64       if ((a<c)); then # bac
     65         data[L]=$b data[L+1]=$a
     66       elif ((b<c)); then # bca
     67         data[L]=$b data[L+1]=$c data[L+2]=$a
     68       else # cba
     69         data[L]=$c data[L+2]=$a
     70       fi
     71     else # ab
     72       if ((c<a)); then # cab
     73         data[L]=$c data[L+1]=$a data[L+2]=$b
     74       elif ((c<b)); then # acb
     75         data[L+1]=$c data[L+2]=$b
     76       fi
     77     fi
     78 
     79   elif ((length==4)); then
     80     local a=${data[L]} b=${data[L+1]} c=${data[L+2]} d=${data[L+3]}
     81     ((b<a)) && local a=$b b=$a
     82     ((d<c)) && local c=$d d=$c
     83 
     84     if ((a<c)); then
     85       #a|b,cd
     86       if ((b<c)); then # abcd
     87         data[L]=$a data[L+1]=$b data[L+2]=$c data[L+3]=$d
     88       elif ((b<d)); then # acbd
     89         data[L]=$a data[L+1]=$c data[L+2]=$b data[L+3]=$d
     90       else # acdb
     91         data[L]=$a data[L+1]=$c data[L+2]=$d data[L+3]=$b
     92       fi
     93     else
     94       #c|ab,d
     95       if ((d<a)); then # cdab
     96         data[L]=$c data[L+1]=$d data[L+2]=$a data[L+3]=$b
     97       elif ((d<b)); then # cadb
     98         data[L]=$c data[L+1]=$a data[L+2]=$d data[L+3]=$b
     99       else # cabd
    100         data[L]=$c data[L+1]=$a data[L+2]=$b data[L+3]=$d
    101       fi
    102     fi
    103 
    104   elif ((length<=64)); then
    105     local M=$((L+length/2))
    106     sort.qsort3.1 "$L" "$M"
    107     sort.qsort3.1 "$M" "$U"
    108 
    109     # merge
    110     local index=$L lhs rhs out=
    111     for rhs in "${data[@]:M:U-M}"; do
    112       while ((index<M&&(lhs=data[index])<rhs)); do
    113         out="$out $lhs"
    114         ((index++))
    115       done
    116       out="$out $rhs"
    117     done
    118     out="$out ${data[*]:index:M-index}"
    119 
    120     data=("${data[@]::L}" $out "${data[@]:U}")
    121 
    122   else #elif ((length<10)); then
    123     # quick sort
    124     local L=$1 U=$2
    125     local p=${data[L+RANDOM*(U-L)/RANDSUP]}
    126 
    127     local i=$L j=$((U-1)) t
    128     while :; do
    129       while ((data[i]<p)); do ((i++)); done
    130       while ((i<j&&p<=data[j])); do ((j--)); done
    131       ((i<j)) || break
    132       ((t=data[i],data[i++]=data[j],data[j--]=t))
    133     done
    134     while ((data[j]==p)); do ((j++)); done
    135     #((j++))
    136     ((L+1<i)) && sort.qsort3.1 "$L" "$i"
    137     ((j+1<U)) && sort.qsort3.1 "$j" "$U"
    138   fi
    139 }
    140 
    141 function sort.qsort3 {
    142   local L=0 U=${#data[@]}
    143   ((L+1<U)) && sort.qsort3.1 "$L" "$U"
    144 }
    145 
    146 #------------------------------------------------------------------------------
    147 
    148 function sort.array {
    149   local -a dict
    150   local a dup=0
    151   for a in "${data[@]}"; do ((dict[a]++&&dup++)); done
    152   if ((dup)); then
    153     # 重複があると駄目…
    154     data=()
    155     for a in "${!dict[@]}"; do
    156       for ((i=0;i<dict[a];i++)); do
    157         data+=("$a")
    158       done
    159     done
    160   else
    161     data=("${!dict[@]}")
    162   fi
    163 }
    164 
    165 #------------------------------------------------------------------------------
    166 
    167 function sort._insert {
    168   local L=${1:-0} U=${2:-${#data[@]}}
    169   for ((i=L+1;i<U;i++)); do
    170     for ((j=i;j>L;j--)); do
    171       ((data[j-1]<=data[j])) && break
    172       # ■
    173     done
    174   done
    175 }
    176 
    177 # fill-rand
    178 # declare -p data
    179 # sort.command
    180 # declare -p data
    181 
    182 ble-measure 'fill-rand'
    183 ble-measure 'fill-rand && sort.qsort1'
    184 ble-measure 'fill-rand && sort.qsort3'
    185 ble-measure 'fill-rand && sort.command'
    186 ble-measure 'fill-rand && sort.array'
    187 
    188 function check-sort-algorithm {
    189   local algorithm=$1
    190   local i
    191   for ((i=0;i<100;i++)); do
    192     fill-rand
    193     eval "$algorithm"
    194     prev=${data[0]}
    195     for v in "${data[@]}"; do
    196       ((prev<=v)) || return 1
    197       prev=$v
    198     done
    199   done
    200 }
    201 
    202 #check-sort-algorithm sort.qsort1 || echo failed
    203 #check-sort-algorithm sort.qsort3 || echo failed
    204 
    205 #------------------------------------------------------------------------------
    206 # swap の速度
    207 #
    208 #   長さ2の配列の swap は data=(...) の方が速い
    209 #   長さ2の配列の swap は t=${data[0]} data[0]=${data[1]} data[1]=$t の方が速い
    210 #
    211 
    212 # data=(4321 1324)
    213 # ble-measure 'local t=${data[0]}; data[0]=${data[1]}; data[1]=$t' # 5.88u(chat)
    214 # ble-measure 'data=("${data[1]}" "${data[0]}")' # 4.88u(chat)
    215 
    216 # data=(4321 123 1324)
    217 # ble-measure 'local t=${data[0]}; data[0]=${data[2]}; data[2]=$t' # 5.88u(chat)
    218 # ble-measure 'data=("${data[2]}" "${data[1]}" "${data[0]}")' # 4.88u(chat)