비닝 (binning) 파일

Question

양식의 파일 이름의 정렬 된 목록을 감안할 때

{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 부분으로 목록을 분할 : 이미 해봤 무엇

그들이 이미 다른 트랙을 가지고 있다면. 이 방법은 비효율적이며 깨진 것입니다. 빈 빈이 많이 남기 때문에 (같은 아티스트가 여러 트랙을 가지고있는 경우가 있기 때문에)

Answer 1

한 시간 동안 해킹 한 후 여기에 더 나은 해결책은 내가 생각해 냈습니다. 트랙에 아티스트의 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]