如何使用仅输出顺序的晦涩程序对大量文件进行排序

Question

我的一位同事想要运行一个 FORTRAN 程序，该程序接受文件参数并根据一些模糊的生物物理化学标准输出它们的顺序（最好是第一个）。他需要的是 10 个最好的结果。

虽然文件不大，但问题是他得到了一个

bash: /home/progs/bin/ardock: Argument list too long

，所以我创建了文件的6位字节长的符号链接，并将它们作为参数，这有效;-)

现在，如果文件数量确实太大，上述技巧无法发挥作用，那么您可以采取什么措施来从所有文件中获得最好的 10 个文件呢？您是否必须按块对文件进行排序并像这样将最好的与最好的进行比较？

#!/bin/bash

best10() { ardock "$@" | head -n 10; }
export -f best10

find . -name '*.dat' -exec bash -c 'best10 "$@"' _ {} + |
xargs bash -c 'best10 "$@"' _ |
xargs bash -c 'best10 "$@"' _ |
xargs bash -c ... | ... | ...

但是如何让它成为一个循环呢？

Answer 1

我建议通过迭代锦标赛来解决这个问题。

这个想法是，在第一轮中，你将所有输出任意分成 N 组。每组的前 10 名选手进入下一轮，你再次将它们分成 N 组。

假设 ardock 是确定性的，并且它提供了总顺序，那么这保证会给您提供前 10 名。

这是代码。我首先创建了 ardock 程序的测试版本。它根据哈希值对提供给它的参数进行排序，然后将它们打印出来。这只是为了让我有一些东西要测试。

import sys
import hashlib
def md5(s):
    m = hashlib.md5(s.encode('utf8'))
    return m.hexdigest()
args = sys.argv[1:]
args = sorted(args, key=md5)
print('\n'.join(args))

接下来，这是运行锦标赛的 Bash 脚本。

#!/bin/bash

export MAX_ARGS=20
export KEEP=10

ardock() {
    python3 test462_ardock_substitute.py "$@"
}
ardock_wrapper() {
    local file="$1"
    ardock $(< "$file") | head -n "$KEEP"
}
export -f ardock
export -f ardock_wrapper

# Create temp dir
dir="$(mktemp -d)"
echo "Created temp dir $dir"

level=0
# Make list of all candidates
seq 1 1000 > "$dir/$level.candidates"

while true; do
    # Split into files at most MAX_ARGS
    split -l "$MAX_ARGS" "$dir/$level.candidates" "$dir/$level.split."

    find "$dir" -name "$level"'.split.*' -print0 | \
        xargs -0 -n1 -I {} bash -c 'ardock_wrapper "$@"' _ {} > \
        "$dir/$((level + 1)).candidates"
    ((level+=1))
    linecount="$(wc -l < "$dir/$level.candidates")"
    echo "There are $linecount molecules remaining"
    if [[ "$linecount" -le "$KEEP" ]]; then
        break
    fi
done

echo "Final winners:"
cat "$dir/$level.candidates"

说明：

• 在每一轮中，都会创建一个文件

  0.candidates

  。这包含您想要测试的每个可能文件的文件名，以换行符分隔。就我而言，它只是前 1000 个整数。由于这是一个文件，因此它可以有你想要的大小。
• 此文件被分成更小的文件，每个文件有 $MAX_ARGS 行长。该值必须大于 KEEP 才能取得进展，但不需要大很多。如果它们是 20 和 10，那么每轮锦标赛，候选者的数量都会减少 2 倍。提高 $MAX_ARGS 会使算法更快。
• ardock 使用 xargs 和 ardock_wrapper 对每个文件运行一次。
• 输出被连接到另一个文件中，

  1.candidates

  。
• 重复。
• 如果剩下的线数小于或等于 $KEEP，则锦标赛结束。