Ytdyklly

I have 6 files and would like to group them by 2 or 3 according to the average size.

file1.log 50G

file2.log 40G

file3.log 20G

file4.log 10G

file5.log 30G

file6.log 70G

File6 is 70G is the biggest file and I would like to group the rest of the files according to the biggest.

The output should look like this:

1. Group by 1 should contain all the files - Parallel 1


2. Group by 2 - Parallel 2

Output 1

file4.log 10G

file5.log 30G

file6.log 70G

Output 2

file1.log 50G

file2.log 40G

file3.log 20G

Notice average is both files are equals.

The third group parallel 3 should look like this:

output 1

file6.log 70G

output2

file1.log 50G

file3.log 20G

output3

file2.log 40G

file4.log 10G

file5.log 30G

It does not have to be the exact average, just divide the file the closest average possible.

Thanks!!

#!/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 = %dn' "$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

The above zsh shell script does binning of all the files in the current directory with a maximum bin size based strictly on the size of the largest file. It implements a first-fit algorithm with the files ordered by decreasing size. This is what's called the "FFD" algorithm in the "Bin packing problem" Wikipedia article. The "MFFD" algorithm is non-trivial to implement in zsh in less than 200 or so lines of code, so I won't post it here.

Testing:

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

The number at the start of each line above corresponds to the bin number assigned to the file.

This seems to be pretty much equivalent to the Bin Packing problem.

The Bin Packing problem is NP-hard, so there is no known shortcut to doing it, brute force (trying all the options in some sensible order that excludes silly attempts, like adding more files to an already oversized group) is the way to go.

For six files, the brute force approach should be simple enough to do by hand; just list all the possible groupings, count how they split the file usage, and choose the one that gives you the smallest maximum group size.