Python：同じベース名の異なるディレクトリにあるファイルをグループ化します

Question

私は特にイライラしています。

私は、1つのディレクトリに何千ものファイルセット、たとえば/path/to/file#####.txtを持っています。他のディレクトリには、同じベース名を使用していますが、接尾辞が異なる（おそらく同じ数の）ファイルがあります。 /diff/path/to/file#####.txt.foo。

私は

[['/path/to/file#####.txt', '/diff/path/to/file#####.txt.foo', 
    '/another/path/to/file#####.txt.bar'], ...] 

としてリストのリストを持っているように、それはそうですが、そこに各subforlderで対応するファイルがあるが、それが保証されないということは保証しませ一緒にグループにこれらのファイルをしようとしています。つまり、'/path/to/file#####.txt'が存在する可能性がありますが、'/diff/path/to/file#####.txt.foo'が存在しない可能性があります。この場合、そのベース名をスキップする必要があります。

ここでの目的は、同期データの読み込み用のファイルリストを作成することです。

これを効率的に行うにはどうすればよいですか？

Answer 1

私はかなり効率的ですが、最もエレガントではない解決策を思いつきました。

基本的には、まずすべてのファイルのベース名を見つけて、すべての可能なセットのリストを作成します。

groups = [['/path/to/file00000.txt', '/diff/path/to/file00000.txt.foo', 
    '/another/path/to/file00000.txt.bar'], 
    ['/path/to/file00001.txt', '/diff/path/to/file00001.txt.foo', 
    '/another/path/to/file00001.txt.bar'], ...] 

その後、私は、私はちょうど、今、私は「悪い」ですインデックスのリストを持っていることを

del_idx = [] 
for i in xrange(len(groups)): 
    for j in len(groups[i]): 
     if not os.path.exists(groups[i][j]): 
      del_idx.append(i) 
      continue # Because if one doesn't exist, no need to check others 

のように、os.path.exists()を使用して、各ディレクトリ内の指定されたベース名を持つファイルの存在を確認それらを削除するには、逆にループスルーします。

for i in xrange(len(del_idx)-1,-1,-1): 
    groups.pop(del_idx[i]) 

これは私が唯一の3タプルを持っていますが、パスのかなりの数がタプルであるならば、これはおそらく壊すでしょう私の場合、正常に動作します。

〜260kファイルの場合、グループ全体の構築には12秒かかっていました。存在チェックには35秒かかり、削除には12秒かかりました。これはかなり合理的ですが、このアルゴリズムはm個のファイルとサイズnのグループではO（m * n）なので、グループサイズが大きくなると理想的ではありません。

Answer 2

私の提案された解決策：

import glob 
import os.path as op 
from collections import defaultdict 
def variable_part(file, base, ext): 
    return file[len(base):-len(ext)-1] 
def func(dirs): 
    base = 'file' 
    files = defaultdict(list) 
    dirext = [] 
    for d in dirs: 
     local_files = glob.glob(op.join(d, '*')) 
     local_ext = '.'.join(local_files[0].split('.')[1:]) 
     for f in local_files: 
      files[variable_part(op.basename(f), base, local_ext)].append(f) 
    return list(files.values()) 

がそれをプロファイリングしていないが、それは近いに最適だということです私の気持ちは、しかし、それぞれのファイル名が一度に処理され、そして最初のディレクトリの後filesへのアクセスを持っている必要がありますすでに償却されている。間違いなく、特に文字列を扱う際の最適化が可能です。

可変部分が0からM-1までの整数である場合、N個のディレクトリがある場合は、長さNの一連のMリストX_kを持つことが最適です。各X_k [i]はi番ディレクトリのファイルファイル .xxxの有無に応じて1または0に設定される。それでは、最終的なファイル名リストを作成し、削除の必要性を排除します（これは気付いたことがありますが、リストに対しては高価な操作です）。

いずれの場合でも、このアルゴリズムの最小複雑度はN * Mであるため、各ディレクトリに移動してすべてのファイルをチェックすることはできません。 35秒は、すべてのディレクトリを取得してメモリ内で作業する単一のシステムコールで最適化することはできますが、全体的な複雑さ、つまりアルゴリズムのスケーラビリティは変わりません。

私はちょっとこれに興味があり、テストをしました。確かに、globで検索されたファイル名の作業は、各ファイルの存在を確認するよりも速くなります（少なくとも、私のmac HFS +ファイルシステム、ssdでは）。

In [0]: def x(): 
    ...:  return [os.path.exists('test1/file%06d.txt.gz' % i) for i in range(10000)] 
    ...: 

In [1]: def y(): 
    ...:  ff = glob.glob('test1/*') 
    ...:  res = [False]*10000 
    ...:  for s in ff: 
    ...:   res[int(s[10:16])] = True 
    ...:  return res 
    ...: 

In [2]: %timeit x() 
10 loops, best of 3: 71.2 ms per loop 

In [3]: %timeit y() 
10 loops, best of 3: 32.6 ms per loop