☰

ファイルを最大ファイルの平均サイズにグループ化

tag-icon • tag-icon shell-script awk sed
ファイルを最大ファイルの平均サイズにグループ化

6つのファイルがあり、平均サイズに応じて2〜3つにグループ化したいと思います。

file1.log 50G
file2.log 40G
file3.log 20G
file4.log 10G
file5.log 30G
file6.log 70G

File6これは70G最大のファイルであり、最大のファイルに基づいて残りのファイルをグループ化したいと思います。

出力は次のようになります。

  1. 1にグループ化すると、すべてのファイルを含める必要があります。 - パラレル1
  2. 2にグループ化 - パラレル2

出力1

file4.log 10G
file5.log 30G
file6.log 70G

出力2

file1.log 50G
file2.log 40G
file3.log 20G

両方のファイルの平均は同じです。

3番目の並列3セットは次のとおりです。

出力1

file6.log 70G

出力2

file1.log 50G
file3.log 20G

出力3

file2.log 40G
file4.log 10G
file5.log 30G

正確な平均である必要はなく、できるだけ近い平均にファイルを分割するだけです。

ありがとうございます！ ！

答え1

#!/usr/bin/env zsh

# To care about hidden filenames:
#setopt GLOB_DOTS

# Load the zstat builtin
zmodload -F zsh/stat b:zstat

# Get the regular files in the current directory,
# ordered by size (largest first)
files=( ./*(.OL) )

# Precalculate the filesizes
typeset -A filesizes
for file in "${files[@]}"; do
    filesizes[$file]=$( zstat +size "$file" )
done

# The maximum size of a bin is the size of the largest file
maxsize=${filesizes[${files[1]}]}

binsizes=()
typeset -A filebins
for file in "${files[@]}"; do
    filesize=${filesizes[$file]}
    bin=1   # try fitting into first bin first
    ok=0    # haven't yet found a bin for this file
    for binsize in "${binsizes[@]}"; do
        if (( filesize + binsize <= maxsize )); then
            # File fits in this bin,
            # update bin size and place file in bin
            binsizes[$bin]=$(( filesize + binsize ))
            filebins[$file]=$bin
            ok=1    # now we're good
            break
        fi
        # Try next bin
        bin=$(( bin + 1 ))
    done

    if [ "$ok" -eq 0 ]; then
        # Wasn't able to fit file in existing bin,
        # create new bin
        binsizes+=( "$filesize" )
        filebins[$file]=${#binsizes[@]}
    fi
done

# Do final output
printf 'Bin max size = %d\n' "$maxsize"
for file in "${files[@]}"; do
    printf '%d: %s (file size=%d / bin size=%d)\n' "${filebins[$file]}" "$file" \
        "${filesizes[$file]}" "${binsizes[$filebins[$file]]}"
done | sort -n

上記のzshシェルスクリプトは現在のディレクトリ内のすべてのファイルをビニングし、最大ビニングサイズは次のものに基づいています。厳しく最大ファイルサイズ。ファイルが小さい順にソートされる優先順位適応アルゴリズムを実装します。これがいわゆる「FFD」アルゴリズムですウィキペディア記事「ボクシングの問題」。 「MFFD」アルゴリズムの実装は単純ではなく、zsh200行未満のコードが必要なので、ここに公開しません。

テスト：

$ ls -l
total 450816
-rw-r--r--  1 kk  wheel  10485760 Jan 19 23:53 file-10.log
-rw-r--r--  1 kk  wheel  20971520 Jan 19 23:53 file-20.log
-rw-r--r--  1 kk  wheel  31457280 Jan 19 23:53 file-30.log
-rw-r--r--  1 kk  wheel  41943040 Jan 19 23:53 file-40.log
-rw-r--r--  1 kk  wheel  52428800 Jan 19 23:53 file-50.log
-rw-r--r--  1 kk  wheel  73400320 Jan 19 23:53 file-70.log

$ zsh ../script.sh
Bin max size = 73400320
1: ./file-70.log (file size=73400320 / bin size=73400320)
2: ./file-20.log (file size=20971520 / bin size=73400320)
2: ./file-50.log (file size=52428800 / bin size=73400320)
3: ./file-30.log (file size=31457280 / bin size=73400320)
3: ./file-40.log (file size=41943040 / bin size=73400320)
4: ./file-10.log (file size=10485760 / bin size=10485760)

上記の各行の先頭にある数字は、ファイルに割り当てられたビン番号に対応します。

答え2

これはほぼ同等のようです。ボックス包装質問。

Bin Packingの問題はNPハードなので、これを行うための既知のショートカットはありません。無差別の代入（すでに大きすぎるグループに多くのファイルを追加するなどの愚かな試みを除いて、合理的な順序ですべてのオプションを試してください）が実行可能な方法です。

6つのファイルを使用する場合、無差別代入アプローチは、可能なすべてのグループを手動で一覧表示し、ファイル使用量を分割する方法を計算し、最小最大グループサイズを提供するグループを選択するのに十分簡単です。

関連情報