将文件分组为最大文件的平均大小

将文件分组为最大文件的平均大小

我有 6 个文件,想根据平均大小将它们按 2 或 3 进行分组。

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

File670G是最大的文件,我想根据最大的文件对其余文件进行分组。

输出应如下所示:

  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 应该是这样的:

输出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

上面的zshshell 脚本对当前目录中的所有文件进行分箱,最大分箱大小基于严格地最大文件的大小。它实现了一个优先适应算法,文件按大小递减顺序排列。这就是所谓的“FFD”算法维基百科文章“装箱问题”。 “MFFD”算法的实现并不简单,zsh只需不到 200 行左右的代码,因此我不会将其发布在这里。

测试:

$ 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)

上面每行开头的数字对应于分配给文件的 bin 编号。

答案2

这似乎几乎相当于箱式包装问题。

Bin Packing 问题是 NP 困难的,因此没有已知的捷径可以做到这一点,暴力(以某种合理的顺序尝试所有选项,排除愚蠢的尝试,例如向已经过大的组添加更多文件)是可行的方法。

对于六个文件,暴力方法应该足够简单,可以手动完成;只需列出所有可能的分组,计算它们如何分割文件使用情况,然后选择为您提供最小最大组大小的分组即可。

相关内容