Fast algorithm for clustering groups of elements given their size/time
Finally I could devise a better algorithm by turning the problem upside down (ie, using bottom up construction instead of top-down).

In my OP algo, I first create a cluster and its groups, and then I walk through the whole files list until I could either fill completely the groups sizes, or there's no file in the files list small enough to fit.

Here it's the other way around: I walk through the files list, and for each file I either assign it to a group if it fits, or if it's too big I create a cluster and init it with this file. To do that, I continually maintain a list of groups sizes to fill, using insertion sort so that when I pick a file to organize, I just need to check its size against the first item of the "to-fill" list.

Here's the algorithm, running in O(n log(g)) (thank's to insertion sort or binary search trees):

For each file:
    - If to-fill list is empty or file.size &gt; first-key(to-fill):
      * Create cluster c with file in first group g1
      * Add to-fill[file.size].append([c, g2], [c, g3], ..., [c, gn])
    - Else:
      * ksize = first-key(to-fill)
      * c, g = to-fill[ksize].popitem(0)
      * Add file to cluster c in group g
      * nsize = ksize - file.size
      * if nsize &gt; 0:
        . to-fill[nsize].append([c, g])
        . sort to-fill if not an automatic ordering structure


Since it's running in O(n log(g)), the number of groups has little impact on the running time, contrary to the algo in the OP. Maybe it's possible to do better, but for now it is fast enough for me, since it can reasonably work on lists of 10M files under 20 seconds.

For those interested, here's a working implementation in Python (I used the sortedcontainers module for the sorted list, which runs in O(log(g)) instead of O(g) for insertion sort):



from collections import OrderedDict
from random import randint
from lib.sortedcontainers import SortedList

def gen_rand_fileslist(nbfiles=100, maxvalue=100):
    fileslist = {}
    for i in xrange(nbfiles):
        fileslist["file_%i" % i] = randint(1, maxvalue)
    return fileslist

def group_files_by_size_fast(fileslist, nbgroups, mode=1):
    '''Given a files list with sizes, output a list where the files are grouped in nbgroups per cluster.'''
    For each file:
        - If to-fill list is empty or file.size &gt; first-key(to-fill):
          * Create cluster c with file in first group g1
          * Add to-fill[file.size].append([c, g2], [c, g3], ..., [c, gn])
        - Else:
          * ksize = first-key(to-fill)
          * c, g = to-fill[ksize].popitem(0)
          * Add file to cluster c in group g
          * nsize = ksize - file.size
          * if nsize &gt; 0:
            . to-fill[nsize].append([c, g])
            . sort to-fill if not an automatic ordering structure
        '''
    ftofill = SortedList()
    ftofill_pointer = {}
    fgrouped = [] # [] or {}
    ford = sorted(fileslist.iteritems(), key=lambda x: x[1])
    last_cid = -1
    while ford:
        fname, fsize = ford.pop()
        #print "----\n"+fname, fsize
        #if ftofill: print "beforebranch", fsize, ftofill[-1]
        #print ftofill
        if not ftofill or fsize &gt; ftofill[-1]:
            last_cid += 1
            #print "Branch A: create cluster %i" % last_cid
            fgrouped.append([])
            #fgrouped[last_cid] = []
            fgrouped[last_cid].append([fname])
            if mode==0:
                for g in xrange(nbgroups-1, 0, -1):
                    fgrouped[last_cid].append([])
                    if not fsize in ftofill_pointer:
                        ftofill_pointer[fsize] = []
                    ftofill_pointer[fsize].append((last_cid, g))
                    ftofill.add(fsize)
            else:
                for g in xrange(1, nbgroups):
                    try:
                        fgname, fgsize = ford.pop()
                        #print "Added to group %i: %s %i" % (g, fgname, fgsize)
                    except IndexError:
                        break
                    fgrouped[last_cid].append([fgname])
                    diff_size = fsize - fgsize
                    if diff_size &gt; 0:
                        if not diff_size in ftofill_pointer:
                            ftofill_pointer[diff_size] = []
                        ftofill_pointer[diff_size].append((last_cid, g))
                        ftofill.add(diff_size)
        else:
            #print "Branch B"
            ksize = ftofill.pop()
            c, g = ftofill_pointer[ksize].pop()
            #print "Assign to cluster %i group %i" % (c, g)
            fgrouped[c][g].append(fname)
            nsize = ksize - fsize
            if nsize &gt; 0:
                if not nsize in ftofill_pointer:
                    ftofill_pointer[nsize] = []
                ftofill_pointer[nsize].append((c, g))
                ftofill.add(nsize)
    return fgrouped
fgrouped2 = group_files_by_size_fast(fileslist, nbgroups)

def grouped_count_sizes(fileslist, fgrouped):
    '''Compute the total size per group and total number of files. Useful to check that everything is OK.'''
    fsizes = {}
    total_files = 0
    allitems = None

    for fkey, cluster in enumerate(fgrouped):
        fsizes[fkey] = []
        for subcluster in cluster:
            tot = 0
            for fname in subcluster:
                tot += fileslist[fname]
                total_files += 1
            fsizes[fkey].append(tot)
    return fsizes, total_files

if __name__ == '__main__':
    nbfiles = 10000000
    nbgroups = 10
    fileslist = gen_rand_fileslist(nbfiles)
    fgrouped = group_files_by_size(fileslist, nbgroups)
    fsizes, total_files = grouped_count_sizes(fileslist, fgrouped)
    print total_files
    print fsizes