sorting - （快速）在 POSIX sh 中对文件列表进行排序

据我所知，此代码完全符合 POSIX。唯一不兼容 POSIX 的部分是pwgen用于测试数据生成。我不想在那一块上过分，因为我不认为它是实际代码的一部分——它只是为了方便……测试它。

好的部分：

它正在使用数组！（实际上，它确实以兼容的方式模拟了数组。）
具有随机枢轴选择的迭代、几乎就地快速排序算法。这确实是灰胡子答案的改编版本。“几乎”部分来自使用堆栈仿真来跟踪间隔，O(log(n))如果我没记错的话，它平均使用大约额外的空间。
文件名可以包含任何字符（但是NUL，这是 POSIX shell 中的一个常见问题，并且文件系统通常不允许这样做）。
比较功能comp_lex_rev可以很容易地换成不同的/修改为其他行为，例如，如果您需要按顺序进行数字排序 - 即，它是模块化的。

丑陋的部分：

rand()- 基于随机数生成，但其他任何事情都很难便携。我的初始代码用于读取/dev/urandom和解析该数据，但当然，这不是 POSIX 的一部分。
奇怪的，以函数为前缀的变量名。这是 POSIX sh 不支持局部变量的直接后果。可以通过保存旧值、使用您认为合适的变量并最终恢复原始值来模拟它们（在某种程度上），但这确实使代码更加不可读（并且容易出错，因为您要么需要有一个修复函数中的退出点或在每个可能的退出点复制恢复功能）。使用唯一 (ahem) 字符串为变量添加前缀可以解决此问题，用可读性换取范围。
需要直接访问全局输入伪数组。在子shell中调用函数而不处理结果只会浪费CPU时间，因为父进程中的原始数据不会改变。这是 shell 脚本中的一个普遍问题，但可能值得一提。
整数很棘手。最初，我将随机数获取部分明确限制为2^16 - 1，因为这是保证的最小整数大小 - 这可能意味着 shell 也必须至少支持它。但是，在那里执行限制是没有意义的。相反，我在生成输入数组时选择了某种溢出检测。请记住，shell 中可用的最大整数大小是特定于实现的，具有硬下限。
由于是基于 shell 的，与直接二进制实现相比，它非常慢，例如，C.expr因速度慢而臭名昭著，并且分叉给其他程序会使 shell 脚本更慢。作为轶事，我能够通过使用 zsh 内部正则表达式处理替换grep和调用来大大减少 zsh 脚本中的处理时间。sed同样，这一点是 shell 脚本的一个普遍问题，与我的代码无关，但记住这一点也很好。

#!/bin/sh

#set -x

comp_lex_rev () {
  comp_lex_rev_a="${1:?'No lhs passed to comp_lex_rev(), this is invalid.'}"
  comp_lex_rev_b="${2:?'No rhs passed to comp_lex_rev(), this is invalid.'}"

  comp_lex_rev_expr_out="$('expr' "x${comp_lex_rev_a}" '>' "x${comp_lex_rev_b}")"
  if [ '1' -eq "${comp_lex_rev_expr_out}" ]; then
    return '0'
  else
    return '1'
  fi
}

get_rand () {
  get_rand_min="${1:?'No minimum value passed to get_rand(), this is invalid.'}"
  get_rand_max="${2:?'No maximum value passed to get_rand(), this is invalid.'}"

  # Minimum value must be positive.
  if [ '0' -gt "${get_rand_min}" ]; then
    return '1'
  fi

  # Max > min doesn't make sense... (we could just swap them here, but meh.)
  if [ "${get_rand_min}" -gt "${get_rand_max}" ]; then
    return '1'
  fi

  # Not much to do if both are the same value.
  if [ "${get_rand_min}" -eq "${get_rand_max}" ]; then
    'printf' '%s\n' "${get_rand_min}"
    return '0'
  fi

  # Just be extra careful.
  get_rand_out=''
  while [ -z "${get_rand_out}" ] || [ "${get_rand_min}" -gt "${get_rand_out}" ] || [ "${get_rand_max}" -lt "${get_rand_out}" ]; do
    get_rand_out="$('awk' '
      BEGIN {
        srand ();
        printf ("%u", (rand () * (('"${get_rand_max}"' - '"${get_rand_min}"') + 1)) + '"${get_rand_min}"');
      }')"
  done

  'printf' '%s\n' "${get_rand_out}"
}

qsort () {
  qsort_arr="${1:?'No array base passed to qsort(), this is invalid.'}"
  qsort_n="${2:?'No array length passed to qsort(), this is invalid.'}"

  if [ '2' -gt "${qsort_n}" ]; then
    # One or zero elements are always sorted.
    return '0'
  fi

  qsort_range_0='0'
  qsort_range_1="$((${qsort_n} - 1))"
  qsort_range_n='2'
  # Must have at least one pair entry in the range "stack".
  while [ '1' -lt "${qsort_range_n}" ]; do
    qsort_range_n="$((${qsort_range_n} - 1))"
    eval 'qsort_high="${qsort_range_'"${qsort_range_n}"'}"'
    qsort_range_n="$((${qsort_range_n} - 1))"
    eval 'qsort_low="${qsort_range_'"${qsort_range_n}"'}"'

    qsort_cur_i="${qsort_low}"
    qsort_pivot_i="$('get_rand' "${qsort_low}" "${qsort_high}")"
    if [ '0' -ne "${?}" ]; then
      # Fetching random value failed, fall back to rightmost element.
      qsort_pivot_i="${qsort_high}"
    fi

    eval 'qsort_pivot="${'"${qsort_arr}"'_'"${qsort_pivot_i}"'}"'

    # Move pivot up if it isn't already.
    if [ "${qsort_high}" != "${qsort_pivot_i}" ]; then
      eval "${qsort_arr}"'_'"${qsort_pivot_i}"'="${'"${qsort_arr}"'_'"${qsort_high}"'}"'
      eval "${qsort_arr}"'_'"${qsort_high}"'="${qsort_pivot}"'
      qsort_pivot_i="${qsort_high}"
    fi

    eval 'qsort_cur="${'"${qsort_arr}"'_'"${qsort_cur_i}"'}"'
    while [ "${qsort_pivot_i}" -gt "${qsort_cur_i}" ]; do
      if 'comp_lex_rev' "${qsort_cur}" "${qsort_pivot}"; then
        qsort_cur_i="$((${qsort_cur_i} + 1))"
        eval 'qsort_cur="${'"${qsort_arr}"'_'"${qsort_cur_i}"'}"'
      else
        eval "${qsort_arr}"'_'"${qsort_pivot_i}"'="${qsort_cur}"'
        qsort_pivot_i="$((${qsort_pivot_i} - 1))"
        eval "${qsort_arr}"'_'"${qsort_cur_i}"'="${'"${qsort_arr}"'_'"${qsort_pivot_i}"'}"'
        eval 'qsort_cur="${'"${qsort_arr}"'_'"${qsort_pivot_i}"'}"'
      fi
    done
    eval "${qsort_arr}"'_'"${qsort_pivot_i}"'="${qsort_pivot}"'

    qsort_lhs_size="$((${qsort_pivot_i} - ${qsort_low}))"
    qsort_rhs_size="$((${qsort_high} - ${qsort_pivot_i}))"
    if [ "${qsort_lhs_size}" -le "${qsort_rhs_size}" ]; then
      if [ '1' -lt "${qsort_lhs_size}" ]; then
        eval 'qsort_range_'"${qsort_range_n}"'="$((${qsort_pivot_i} + 1))"'
        qsort_range_n="$((${qsort_range_n} + 1))"
        eval 'qsort_range_'"${qsort_range_n}"'="${qsort_high}"'
        qsort_range_n="$((${qsort_range_n} + 1))"

        eval 'qsort_range_'"${qsort_range_n}"'="${qsort_low}"'
        qsort_range_n="$((${qsort_range_n} + 1))"
        eval 'qsort_range_'"${qsort_range_n}"'="$((${qsort_pivot_i} - 1))"'
        qsort_range_n="$((${qsort_range_n} + 1))"
      fi
    else
      eval 'qsort_range_'"${qsort_range_n}"'="${qsort_low}"'
      qsort_range_n="$((${qsort_range_n} + 1))"
      eval 'qsort_range_'"${qsort_range_n}"'="$((${qsort_pivot_i} - 1))"'
      qsort_range_n="$((${qsort_range_n} + 1))"
    fi

    if [ '1' -lt "${qsort_rhs_size}" ]; then
      eval 'qsort_range_'"${qsort_range_n}"'="$((${qsort_pivot_i} + 1))"'
      qsort_range_n="$((${qsort_range_n} + 1))"
      eval 'qsort_range_'"${qsort_range_n}"'="${qsort_high}"'
      qsort_range_n="$((${qsort_range_n} + 1))"
    fi
  done
}

print_arr () {
  print_arr_arr="${1:?'No array base passed to print_arr(), this is invalid.'}"
  print_arr_n="${2:?'No array length passed to print_arr(), this is invalid.'}"

  print_arr_i='0'
  while [ "${print_arr_n}" -gt "${print_arr_i}" ]; do
    if [ '0' -ne "${print_arr_i}" ]; then
      'printf' '===\n'
    fi
    eval "'"'printf'"'"' '"'"'%s\n'"'"' "${'"${print_arr_arr}"'_'"${print_arr_i}"'}"'
    print_arr_i="$((${print_arr_i} + 1))"
  done
}

generate_testdata () {
  generate_testdata_dir="${1:?'No testdata directory passed to generate_testdata(), this is invalid.'}"

  generate_testdata_i='0'
  generate_testdata_n='100'
  (
    'mkdir' "${generate_testdata_dir}"
    'cd' "${generate_testdata_dir}"
    while [ "${generate_testdata_n}" -gt "${generate_testdata_i}" ]; do
      # We'll map the first underscore character to a space character and
      # ditto for right curly bracket vs. newline since pwgen generates no
      # such characters by default.
      ':' > "$('pwgen' '-s' '-y' '-c' '-n' '-r' '/' '100' '1' | 'sed' '-e' 's#_# #' '-e' 's#}#\
#')"
      generate_testdata_i="$((${generate_testdata_i} + 1))"
    done
  )
}

main () {
  main_testdir='testdata'
  if [ ! -d "${main_testdir}" ]; then
    'generate_testdata' "${main_testdir}"
  fi

  main_cur_file=''
  main_flist_n='0'
  main_flist_old_n="${main_flist_n}"
  for main_cur_file in "${main_testdir}"/*; do
    if [ -f "${main_cur_file}" ]; then
      eval 'main_flist_'"${main_flist_n}"'="${main_cur_file}"'
      main_flist_n="$((${main_flist_n} + 1))"

      if [ "${main_flist_old_n}" -ge "${main_flist_n}" ]; then
        # Overflow (or... none-flow?), stop working.
        'printf' 'Too many files to handle, aborting.\n' >&'2'
        return '1'
      else
        main_flist_old_n="${main_flist_n}"
      fi
    fi
  done

  # Sort, in reverse order.
  'qsort' 'main_flist' "${main_flist_n}"

  # And finally print out.
  'print_arr' 'main_flist' "${main_flist_n}"

  # In GNU terms,
  # 'find' "${main_testdir}" '-type' 'f' '-print0' | 'sort' '-rz' | 'sed' '-e' 's#\x0#\n===\n#g'
  # should return about the same data, only with an additional separator at the end.
}

# Actual main code.
'main'

sorting - （快速）在 POSIX sh 中对文件列表进行排序

问题描述

解决方案

推荐阅读