☰

算法列表

tag-icon • tag-icon bash shell zsh ksh
算法列表

两个列表相减的快速方法是什么1。这些列表可能很小，也许是 shell 工作中的直接方式。或者列表可能很长，也许外部工具是更快的方法。

假设您有两个列表：

list1=( 1 2 3 4 5 6 7 8 9 10 11 12 )
list2=( 1 2 3   5   7 8 9    11 12 )

如何从 list1 中删除 list2 的所有元素以获得结果列表 ( listr) 等价于：

listr=( 4 6 10 )

列表也可以位于文件内部，如果列表很大（它可能使用太多内存），则应该如此。

为了简单起见，我将所有算法放在社区答案中。

请阅读其中进行的多项测试。

多组

最初的问题是要在 list2 中找到完整列表（list1）中缺失的元素，且不重复。

但是，如果列表是：

list1=( a a b b b c     d d   )
list2=(     b b   c c c d d e )

和定义多集减法如下在此页面中，预期结果为：

listr= ( a a b )

只有算法 1 和 3 可以正常工作。
算法 2 和 4 都无法做到这一点。
算法 5 (comm) 可以通过执行 来匹配此定义comm -23。
算法 6 (zsh) 失败。我不知道如何让它发挥作用。
算法 7（通讯）。如上所述，使用-23作品。

我还没有分析所有的算法设置对称差定义应该产生：

listr=( a a b c c e )

但comm -3 list1.txt list2.txt | tr -d ' \t'有效。

1是的，我知道在 shell 中处理文本文件（行列表）是一个坏主意，它的设计速度很慢。
但是这里有似乎无法避免的情况。
我（我们）愿意接受建议。

答案1

您可以使用comm删除两个列表共有的任何内容：

listr=($(comm -3 <(printf "%s\n" "${list1[@]}" | sort) <(printf "%s\n" "${list2[@]}" | sort) | sort -n))

这会按照预期的顺序对两个列表进行排序comm，比较它们，仅输出两个列表中唯一的项目，然后按数字顺序再次对它们进行排序。

如果两个列表均按字典顺序排序（按照LC_COLLATE），可以避免再次排序：

listr=($(comm --nocheck-order -3 <(printf "%s\n" "${list1[@]}") <(printf "%s\n" "${list2[@]}")))

如果您需要比较的值存储在文件中，这也很有效。

答案2

#!/bin/zsh
list1=( 1 2 3 4 5 6 7 8 9 10 11 12 )
list2=( 1 2 3   5   7 8 9    11 12 )
listr=("${(@)list1:|list2}")
typeset -p listr

答案3

抽象的：

  • 对于长列表，如果列表已经排序，则 comm (alg7) 是最快的。

  • zsh 解决方案是（迄今为止）最快的如果没有读取文件，也就是说，列表是“在内存中”给出的。但是，这与必须从文件中读取值的所有其他解决方案进行比较并不公平。我将原始代码（避免了测试中读取文件的时间）更改为还包括读取文件时间的代码。

这是社区答案，仅报告每个答案的时间。

请做编辑并添加您的解决方案/选项以比较所有内容。

算法列表

  • alg1：朴素的循环解决方案。
  • alg2：使用外部sort和uniq -u
  • alg3：在 bash 中处理字符串。
  • alg4：在排序列表上加入 -v （谢谢@Kusalananda）
  • alg5：通讯（谢谢@斯蒂芬·基特）
  • alg6：zsh（谢谢@Llua）
  • alg7：comm 但在已经排序的文件上（谢谢@斯蒂芬·基特）

zsh 手册中的注释：

${name:|arrayname}
如果 arrayname 是数组变量的名称（注意，不是内容），则 arrayname 中包含的任何元素都将从名称替换中删除。

测试

由于有多种方法可以解决这个问题，因此我们需要一个通用框架来测试（公平地）答案。

一些准则（如果您发现不公平，请更改它们）：

  • 测量足够的重复次数以获得合理的精度。
  • 在所使用的外壳内部进行测量（避免装载/卸载外壳）。
  • 通过不打印或重定向到 /dev/null 来避免输出开销。

测试代码：

#!/bin/bash
alg1(){
         arr=( "${list1[@]}" )
         for i in "${list2[@]}"; do
             for j in "${!arr[@]}"; do
         if [[ "$i" == "${arr[j]}" ]]; then
             unset arr["$j"]
             break
         fi
             done
     done
     printf '%s ' "${arr[@]}"; echo
}

alg2(){
         arr=($({ printf '%s\n' "${list1[@]}" "${list2[@]}"; } | sort | uniq -u))
         printf '%s ' "${arr[@]}"; echo
}

alg3(){
         a=" $(printf '%s ' ${list1[@]})" # Watch the space at the start!!.
         for i in "${list2[@]}"; do
         a=${a/ "$i" / };
     done
     printf '%s\n' "$a"
}

alg4(){  join -v 1 list1.txt list2.txt ; }

alg5(){  #listr=$(
                    comm -3 <(printf "%s\n" "${list1[@]}" | sort) \
                            <(printf "%s\n" "${list2[@]}" | sort) |
                sort -n
     #)
      }

alg6(){ zsh -c '  alg6(){
                           list1=( $(cat list1.txt) )
                           list2=( $(cat list2.txt) )
                           listr=("${(@)list1:|list2}")
                           typeset -p listr
                        }
                  TIMEFMT="%E %U %S"
                  time ( for ((k=0;k<'"$1"';k++)); do alg6; done; )
                '
      }
#: <<-\_comment_
alg7(){ comm -23 list1.txt list2.txt; }

try(){ for ((k=0;k<$1;k++)); do "$2"; done; }

#list1=( 1 2 3 4 5 6 7 8 9 10 11 12 )
#list2=( 1 2 3   5   7 8 9    11 12 )

#list1=( a a b b b c     d d   )
#list2=(     b b   c c c d d e )

size=1000000
list1=( "0" $(seq 1 "$size") )
list2=( "${list1[@]}" ); unset "list2[123]" "list2[234]" "list2[345]"

printf '%s\n' "${list1[@]}" | sort >list1.txt
printf '%s\n' "${list2[@]}" | sort >list2.txt

repeats=${1:-10}; shift
out=${1:-no}    ; shift
(($#==0)) && set -- alg{1..7}

TIMEFORMAT='%R %U %S'
for   i
do    printf '%s ' "$i"
      if [[ $out == no ]]; then
      [[ $i != alg6 ]] &&
          time try "$repeats" "$i" >/dev/null ||
          time alg6 "$repeats" >/dev/null
      else
      [[ $i != alg6 ]] &&
          time try "$repeats" "$i"            ||
          time alg6 "$repeats"
      fi
done

结果：

简短列表（如代码中所示）：

$ ./script
alg1 2.056 0.806 1.237
alg2 3.478 3.126 1.756
alg3 0.999 0.728 0.304
alg4 1.186 0.780 0.434
alg5 5.234 1.926 1.722
alg6 2.71s 1.64s 1.26s
     2.758 1.637 1.265
alg7 1.156 0.799 0.422

alg6 的时间由 zsh 报告，之后由 bash 报告。
另外，如果将文件读取从函数中移到外部，zsh 的执行时间确实会更小（0.050）。

更长的清单

测试仅包含 500 个值（10 次重复）的列表表明 alg1 效率非常低。将其从进一步测试中删除：

alg1 4.149 3.471 0.657
alg2 0.145 0.055 0.063
alg3 0.219 0.180 0.009
alg4 0.039 0.015 0.003
alg5 0.149 0.018 0.027
alg6 0.06s 0.02s 0.02s
     0.087 0.030 0.018
alg7 0.033 0.008 0.008

测试 5k 值（10 次重复）表明 alg3 的效率也很低：

alg2 0.590 0.526 0.187
alg3 12.957 12.888 0.044
alg4 0.098 0.047 0.008
alg5 0.654 0.028 0.036
alg6 0.16s 0.12s 0.04s
     0.211 0.118 0.044
alg7 0.038 0.022 0.014

测试 50k 值（10 次重复）：

alg2 6.487 5.838 1.611
alg4 0.488 0.469 0.019
alg5 5.073 0.250 0.056
alg6 1.42s 1.20s 0.21s
     1.467 1.206 0.216
alg7 0.271 0.247 0.014

500k（10 次重复）

alg4 5.471 5.269 0.156
alg6 15.14s 13.33s 1.91s
     15.215 13.335 1.926
alg7 2.833 2.655 0.138

对于 1M（10 次重复）

alg4 11.127 10.804 0.251
alg7 5.772 5.525 0.230

相关内容