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

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 ... | ... | ...

这里的问题是，需要的数量xargs是事先不知道的，那么如何使其成为一个循环呢？

注意：由于程序正在输出以换行符分隔的文件路径流，我知道这xargs可能会中断。这里不用担心，您可以将文件名视为字母数字。

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

# Maximum number of arguments ardock can accept at once
export MAX_ARGS=20
# How many of the top candidates should be kept?
export KEEP=10
# How many parallel copies of ardock to run.
# Use 0 to run one for every core you have.
CORES=1

ardock() {
    python3 test462_ardock_substitute.py "$@"
}
ardock_wrapper() {
    # Run ardock, outputting best $KEEP lines
    ardock "$@" | 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
    # 1) Read in $level candidates
    # 2) Split into groups of $MAX_ARGS and run ardock
    # 3) Output to $level + 1 candidates file
    < "$dir/$level.candidates" \
        xargs -P "$CORES" -n "$MAX_ARGS" bash -c 'ardock_wrapper "$@"' _ > \
        "$dir/$((level + 1)).candidates"
    ((level+=1))
    # Count lines in output
    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 个整数。由于这是一个文件，因此它可以任意大。
• 该文件使用 xargs 进行分割，最多$MAX_ARGS为每次调用 ardock 提供一个文件。
• （注意$MAX_ARGS：这必须大于$KEEP才能取得进步，但不需要太大。例如，如果它们是 20 和 10，那么每一轮比赛，候选者的数量都会减少一个系数2. 提高$MAX_ARGS使算法更快。）
• ardock_wrapper负责$KEEP从 ardock 获取每个输出的顶行。
• 输出被连接到另一个文件1.candidates.
• 重复。
• 如果剩下的线数小于或等于 $KEEP 线，则锦标赛结束。

此代码在 Linux 上使用 Bash 5.0.17 进行了测试。