分级文件转换成大致相等大小的目录

鉴于形式的文件名的排序列表分级文件转换成大致相等大小的目录

{artist}-{title}.mp3

我希望将这些文件分发到255个箱（子目录），这样每个箱中包含的文件数目大致相同的，与艺术家是“原子”的限制，即没有艺术家应该有分布在多个目录上的曲目。结果应保持排序（即忽略分箱，我们仍然有相同的列表排序）。

我已经尝试过：

def partition(lst, n): 
    q, r = divmod(len(lst), n) 
    indices = [q * i + min(i, r) for i in range(n + 1)] 
    result = [lst[indices[i]:indices[i + 1]] for i in range(n)] 
    assert sum(len(x) for x in result) == len(lst) 
    assert len(set(len(x) for x in result)) <= 2 
    return result

然后我经历以及他们移动到前面的箱强制的限制，艺术家是原子的：我用这种方法划分成列表正好255份如果他们已经有另一条轨道。这种方法是次优的和破碎的，因为我留下了大量的空箱（由于有，在某些情况下，同一艺术家的许多曲目）

来源

2013-04-15 wim

我没有时间来实现这个所以这里是一些伪代码：从列表中获取一个艺术家名字，将属于该艺术家的所有文件移动到一个单独的列表中（称为'a'）并将它们从最初列表中移除。得到文件中文件最少的目录（为此写入一个函数），将列表“a”中的文件添加到之前获得的目录中。重复此操作，直到您的初始列表中没有更多文件。 –

对不起，我忘记指定应该保留排序，这意味着您的建议不起作用。我将它编辑成问题... – wim

在黑客一小时后，这是一个小时我想出了更好的解决方案。它通过创建一个艺术家的dict进行跟踪，然后通过贪婪地配对相邻的条目来减少到255个按键。

我敢肯定，它仍然不是最佳的，但它是可行的，我会在这里重现它在任何情况下，有一个类似的问题要解决：

d = collections.OrderedDict() 
# build an OrderedDict of artist to track(s) 
for fn in files: 
    artist, title = fn.split('-') 
    if (artist,) not in d: 
    d[artist,] = [] 
    d[artist,].append(fn) 

def window(seq, n=2): 
    it = iter(seq) 
    result = tuple(itertools.islice(it, n)) 
    if len(result) == n: 
    yield result  
    for elem in it: 
    result = result[1:] + (elem,) 
    yield result 

while len(d) > 255: 
    # find the pair of adjacent keys with minimal number of files contained 
    k1, k2 = min(window(d), key=lambda x: len(d[x[0]] + d[x[1]])) 
    # join them into the first key and nuke the latter 
    d[k1] += d[k2] 
    del d[k2]

来源

2013-04-15 15:27:20 wim

这大致是我在想什么。如果没有预先知道样本的字母分布，我认为这是一个胜利者。当然，根据样本大小，数据传递2可能会产生更好的结果。 –

分级文件转换成大致相等大小的目录

回答

相关问题