☰

二分查找失败的行

tag-icon • tag-icon shell-script text-processing search split
二分查找失败的行

git必须bisect run找出哪个版本引入了错误。

我有一个大文件（100GB），并且至少有一行是坏的，但是我必须检查它的程序不会告诉我哪一行。

这些行是记录，因此我可以使用headand tailand编写二分搜索/2（将前半部分传递给程序，如果没有错误，则将后半部分传递给程序），并基于此再次拆分后半部分。

但是是否已经存在无需我干预即可完成此操作的自动化工具（类似于git bisect run）？

答案1

您可以使用split将文件拆分为多个部分，并且它有一个选项仅按行拆分：

$ ls
bigfile
$ split -n l/2 bigfile
$ ls
bigfile xaa xab

这真的只有在文件才有意义能被分割并按行组织，这仅适用于文本文件。

有了这个，您可以轻松构建自己的二等分工具，例如如下所示：

#!/bin/sh

TESTPROG=$1
DATA=$2

usage() {
    echo "usage: $0 <testprog> <datafile>"
    echo "     will bisect <datafile> to the single line where <testprog> exits with '0'"
    exit 1
}

if [ ! -x "${TESTPROG}" ]; then  usage; fi
if [ ! -e "${DATA}" ]    ; then  usage; fi

BISECTDIR=$(mktemp -d)

splitfiles() {
    split -e -n l/2 $1 ${BISECTDIR}/$2bisect_
    echo ${BISECTDIR}/$2bisect_*
}
cleanup() {
    rm -rf "${BISECTDIR}"
    exit 0
}

i=1
while [ $(head -2 "${DATA}" | wc -l) -gt 1 ]; do
  echo "testing: ${DATA} $(head -2 "${DATA}" | wc -l)" 1>&2
  files=$(splitfiles ${DATA} ${i})
  count=$(echo $files | awk '{print NF}')
  if [  ${count} -lt 2 ]; then
      cat $files
      cleanup
  fi
  DATA=""
  for f in $files; do
          if ${TESTPROG} "${f}" 1>/dev/null 2>/dev/null; then
          DATA="${f}"
          break
      fi
  done
  i=$(( i+1 ))
done

cleanup

警告：这会将所有平分数据放入/tmp（如果您不喜欢这样，请更改 BISECTDIR 的定义）；另外，这只会在最后清理平分的数据文件。所以你可能需要足够的空间......

答案2

https://gitlab.com/ole.tange/tangetools/-/tree/master/find-first-fail

find-first-fail -f 100g.file -v myprogram

它将识别myprogram失败的 X..Y 行。它通过两次二分搜索来实现这一点：首先，它保持 X=1 并搜索 Y，因此它找到最小的 Y，其中myprogram1..Y 失败。然后它保留 Y 并搜索 X，从而找到myprogram失败的 X..Y。

如果有多个部分myprogram失败，则只会识别其中之一。

答案3

刚刚完成一个通用二等分工具，用 Bash 编写并经过彻底测试。现在的代码：

#!/usr/bin/env bash

set -o errexit -o noclobber -o nounset -o pipefail
shopt -s failglob inherit_errexit

next_file="$2"
entries_checked=0

cleanup() {
    if (("${DEBUG-0}" > 0)); then
        printf 'Number of entries checked: %d.\n' "$entries_checked" >&2
    fi
    rm --force --recursive "$work_dir"
}
work_dir="$(mktemp --directory)"
trap cleanup EXIT

while true; do
    ((++entries_checked))
    if (("${DEBUG-0}" > 0)); then
        printf 'Remaining entry count: %d.\n' "$(wc --lines < "$next_file")" >&2
    fi
    split_prefix="${work_dir}/${entries_checked}-"
    split --elide-empty-files --number=l/2 "$next_file" "$split_prefix"
    split_files=("$split_prefix"*)
    if (("${DEBUG-0}" > 1)); then
        printf 'First split file entry count: %d.\n' "$(wc --lines < "${split_files[0]}")" >&2
    fi
    if [[ -v split_files[1] ]]; then
        if (("${DEBUG-0}" > 1)); then
            printf 'Second split file entry count: %d.\n' "$(wc --lines < "${split_files[1]}")" >&2
        fi
    fi

    entry="$(tail --lines=1 "${split_files[0]}")"
    if (("${DEBUG-0}" > 1)); then
        printf 'Checking entry: “%s”.\n' "$entry" >&2
    fi

    if ENTRY="$entry" "$SHELL" <<< "$1"; then
        if (("${DEBUG-0}" > 1)); then
            printf 'Command successful.\n' >&2
        fi

        rm "${split_files[0]}"

        if ! [[ -v split_files[1] ]]; then
            echo 'No insertion point found.' >&2
            exit 3
        fi
        next_file="${split_files[1]}"
    else
        if (("${DEBUG-0}" > 1)); then
            printf 'Command failed.\n' >&2
        fi

        first_bad_entry="$entry"

        if [[ -v split_files[1] ]]; then
            rm "${split_files[1]}"
        fi
        next_file="${split_files[0]}"
        if (("$(head --lines=2 "$next_file" | wc --lines)" == 1)); then
            printf '%s\n' "$first_bad_entry"
            exit
        fi
    fi
done

相关内容