分級文件轉換成大致相等大小的目錄

鑑於形式的文件名的排序列表分級文件轉換成大致相等大小的目錄

{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可能會產生更好的結果。 –

分級文件轉換成大致相等大小的目錄

回答

相關問題