우리는이 과제의 본질이 실제로 매우 단순하다는 것을 잊지 말아야합니다. Haskell에 대한 튜토리얼에서 볼 수 있듯이 (이 작업을위한 솔루션의 작업을 중심으로 작성되었으며 점진적으로 개선되었습니다)

이제 프로그램이 어떻게 작동하고 의사 코드로 표현되는지에 대해 잠시 생각해 봅시다.

main = Read list of directories and their sizes.
       Decide how to fit them on CD-Rs.
       Print solution.

합리적으로 들리나요? 나는 그렇게 생각했다.

인생을 조금 단순화하고 지금은 프로그램 외부의 디렉토리 크기 (예 : ” du -sb *“)를 계산하고 stdin에서이 정보를 읽겠다고 가정 해 봅시다 .

( 히치하이커 안내서에서 Haskell까지, 1 장 )

또한 귀하의 질문에 따라 결과 디스크 레이아웃을 조정 (편집) 한 다음 도구를 사용하여 구울 수 있습니다.

파일 모음을 분할하기 위해 Haskell 튜토리얼에서 간단한 프로그램 변형을 재사용 (적응 및 재사용) 할 수 있습니다.

불행하게도,에 내가 다른 대답 여기에 언급했다고 도구 , 필수 분할 작업의 단순성이의 사용자 인터페이스의 복잡성과 bloatedness가 일치하지 않습니다 그것은 여러 가지 작업을 결합하기 위해 작성 되었기 때문에 (; 단계에서 수행하지만, 그러나 여전히 내가 생각할 수있는 가장 깨끗한 방식으로 결합되지 않았습니다).distributedistribute

코드를 사용하는 데 도움이되도록 다음은 파일 모음을 분할하는이 “필수”작업을 수행 하는 bash 코드 distribute( 380 행 ) 에서 발췌 한 내용입니다 .

# Splitting:

function splitMirrorDir() {
  if [[ ! -d "$THIS_BASES_DIR/$BASE/$type" ]]; then
    echo $"No base fixed for $type" >&2
    exit 1
  fi

  # Getting the list of all suitable files:
  local -a allFiles
  let 'no = 0' ||:
  allFiles=()
  # no points to the next free position in allFiles
  # allFiles contains the constructed list
  for p in "$THIS_BASES_DIR/$BASE/$type"/*.rpm; do
      if [[ ! -e "$p" ]]; then
      # fail on non-existent files
      echo $"Package file doesn't exist: " "$p" >&2
      return 1
      fi
      if [[ "$ONLY_REAL_FILES" == "yes" && ! -f "$p" ]]; then
      continue
      fi
      if [[ "$DIFF_TO_BASE" ]]; then
          older_copy="$DIFF_TO_BASE/$type/${p##*/}" # using shell param expansion instead of `basename' to speed up
          if [[ -h "$older_copy" || -a "$older_copy" ]]; then
          continue
      fi
      fi
      allFiles[$(( no++ ))]="$p"
  done
  readonly -a allFiles

  # Splitting the list of all files into future disks:
  #
  local -a filesToEat allSizes
  let 'no = 0' ||:
  filesToEat=()
  allSizes=($(getSize "${allFiles[@]}"))
  readonly -a allSizes
  # allSizes contains the sizes corrsponding to allFiles
  # filesToEat hold the constructed list of files to put on the current disk
  # no points to the next free position in filesToEat
  # totalSize should hold the sum of the sizes
  #  of the files already put into filesToEat;
  #  it is set and reset externally.
  for p in "${allFiles[@]}"; do
      if (( totalsize + ${allSizes[$(( no ))]} > CDVOLUME )); then
      eatFiles "${filesToEat[@]}"
          filesToEat=()
          finishCD
      startTypedCD
    fi
      let "totalsize += ${allSizes[$(( no ))]}" ||:
      filesToEat[$(( no++ ))]="$p"
  done
  eatFiles "${filesToEat[@]}"
}

function eatFiles() {
    #{ oldIFS="$IFS"; IFS=$'\n'; echo "$FUNCNAME: args: " "$*" | head >&2;  IFS="$oldIFS"; }
    zeroDelimited "$@" | xargs -0 --no-run-if-empty \
    cp -s \
    --target-dir="$THIS_LAYOUTS_DIR/cd$(( cdN ))/$PREFIX/$type$DOT_SUFFIX"/ \
    --
}

function startTypedCD() {
#  set -x
  mkdir -p "$THIS_LAYOUTS_DIR/cd$(( cdN ))/$PREFIX/$type$DOT_SUFFIX"
  start_action $" %s with %s" "$(( cdN ))" "$type"
#  set +x
}

function finishCD() {

( 454 행 이후에 더 읽으십시오 )

이 eatFiles함수는 미래 디스크의 레이아웃을 나뭇잎이 실제 파일에 대한 심볼릭 링크 인 트리로 준비합니다. 따라서 굽기 전에 레이아웃을 편집 할 수 있어야합니다. 이 mkisofs유틸리티에는 심볼릭 링크를 따르는 옵션이 있으며 실제로 내 mkiso기능 코드에 사용됩니다 .

제시된 스크립트 (물론 필요에 따라 다시 쓰고 쓸 수 있음)는 가장 간단한 아이디어를 따릅니다. 파일의 크기 (또는 더 정확하게는 패키지의 경우 distribute)를 나열된 순서대로 합산하는 것입니다. 재 배열하지 마십시오.

“하스켈에 대한 히치하이커 안내서”는 최적화 문제를보다 심각하게 고려하여 파일을 디스크에 더 잘 맞추기 위해 (그리고 더 적은 디스크를 필요로하기 위해) 파일을 스마트하게 재배치하려고 시도하는 프로그램 변형을 제안합니다.

충분한 예비가 이미 있습니다. CD를 싸서 갑시다.

당신이 이미 알고 있듯이, 우리의 문제는 고전적인 문제입니다. 그것은이라고합니다 “배낭 문제”
( 그것을 구글 은 그것이 이미 모르는 경우. 더 100,000 이상의 링크가 있습니다).

탐욕스러운 해결책부터 시작합시다 …

( 3 장 이상에서 더 읽으십시오 .)

다른 스마트 도구

데비안은 distributewrt 패키지 모음 보다 똑똑한 배포 CD를 만드는 도구를 사용한다고 들었 습니다. 결과는 패키지 간 종속성을 염려하고 패키지 모음을 만들려고 시도하기 때문에 더 좋습니다 . 첫 번째 디스크는 종속성으로 닫힙니다. 즉, 첫 번째 디스크의 패키지는 다른 디스크의 패키지를 필요로하지 않아야합니다 (또는 적어도 그러한 종속성의 수를 최소화해야합니다).

답변