0

これがここでよく聞かれる質問なのか、それともこれに対する回答が得られるのかはわかりませんが、画像を含むフォルダー構造から DB リンクレコードを生成する疑似コードアプローチを探していますファイル。

次のような構造のフォルダーのセットがあります。

+-make_1/
  | +--model_1/
  |    +-default_version/
  |    |   +--1999
  |    |   +--2000
  |    |   |   +--image_01.jpg
  |    |   |   +--image_02.jpg
  |    |   |   +--image_03.jpg
  |    |   |   ...
  |    |   +--2001
  |    |   +--2002
  |    |   +--2003
  |    |   ...
  |    |   +--2009
  |    +--version_1/
  |    |   +--1999
  |    |   ...
  |    |   +--2009
  |    +--version_2/
  |    |   +--1999
  |    |   +--2000
  |    |   +--2001
  |    |   |   +--image_04.jpg
  |    |   |   +--image_05.jpg
  |    |   |   +--image_06.jpg
  |    |   |   ...
  |    |   +--2002
  |    |   +--2003
  |    |   |   +--image_07.jpg
  |    |   |   +--image_08.jpg
  |    |   |   +--image_09.jpg
  |    |   ...
  |    |   +--2009
  ...  ... ...

本質的には、1999 年から始まる年ごとの車両の可能な画像を表します。

メーカーとモデル (例: メーカー: アルファ ロメオ、モデル: 145) には、さまざまなトリムやバージョンがあります。各トリムまたはバージョンは、同じように見えるが、燃料の種類またはエンジン容量に違いがある多くの車両に見られる場合があります。

重複を保存するために、上記のフォルダー構造はデフォルトのフォルダーを使用します...そして、2000年以降のデフォルトバージョンの画像が表示されます。各バージョンのリンク テーブルを作成する必要があります - 独自のオーバーライド イメージがあるかどうか、またはデフォルト バージョンを使用するかどうかに基づいて...

たとえば、version_1 にはイメージ ファイルがないため、2000 年から 2009 年までのデフォルト イメージへのリンクを作成する必要があります。

一方、バージョン 2 は 2000 年にデフォルトのイメージを使用して開始しますが、最初は 2001 ～ 2002 年、次に 2003 ～ 2009 年の 2 つの新しいセットを使用します。したがって、必要なリンクのリストは...

version    start     end   file_name
=======    =====   =====   =========
version_1   2000    2009   image_01.jpg
version_1   2000    2009   image_02.jpg
version_1   2000    2009   image_03.jpg
...
version_2   2000    2001   image_01.jpg
version_2   2000    2001   image_02.jpg
version_2   2000    2001   image_03.jpg
version_2   2001    2003   image_04.jpg
version_2   2001    2003   image_05.jpg
version_2   2001    2003   image_06.jpg
version_2   2003    2009   image_07.jpg
version_2   2003    2009   image_08.jpg
version_2   2003    2009   image_09.jpg
...

(デフォルトは単なるプレースホルダーであり、リンクは必要ありません。)

現時点では、フォルダーを調べてアレイを構築し、最後に脂肪をトリミングしています。ある種のテキスト処理アプローチを使用して、ショートカットがあるかどうか疑問に思っていましたか? 約 45,000 のフォルダーがあり、そのほとんどは空です :-)

4

1 に答える 1

1

実行可能ファイルにかなり近い Python 疑似コードを次に示します (適切なインポートと、実際の書き込みを行う writerow 関数の定義が必要です -- 中間ファイル、DB、CSV などに):

# first, collect all the data in a dict of dicts of lists
# first key is version, second key is year (only for non-empty years)

tree = dict()
for root, dirs, files in os.walk('make_1/model_1'):
    head, tail = os.path.split(root)
    if dirs:
       # here, tail is a version
       tree[tail] = dict
    elif files:
       # here, tail is a year
       tree[os.path.basename(head)][tail] = files

# now specialcase default_version
default_version = tree.pop('default_version')
# determine range of years; rule is quite asymmetrical:
#   for min, only years with files in them count
min_year = min(d for d in default_version if default_version[d])
#   for max, all years count, even if empty
max_year = max(default_version)

for version, years in tree.iteritems():
    current_files = default_version[min_year]
    years.append(max_year + 1)
    y = min_year
    while years:
        next_change = min(years)
        if y < next_change:
            for f in current_files:
                writerow(version, y, next_change-1, f)
        y = next_change
        current_files = years.pop(y)

仕様と例のあいまいさの 1 つは、default_version が数年後にファイルのセットを変更できるかどうかです。ここでは、それが起こらないと想定しています (特定のバージョンのみがそのように変更され、デフォルト バージョンは常に 1 つのセットを保持します)。のファイル)。

そうでない場合、デフォルト バージョンが (たとえば) 1999 年と 2003 年に変更され、version1 が 2001 年と 2005 年に変更された場合はどうなるでしょうか。 、または01で指定したもの？

仕様の最も複雑なバージョン (default_version と特定のバージョンの両方が変更可能で、最新の変更が優先され、特定とデフォルトの両方が同じ年に変更された場合は特定が優先される) では、すべてのここで行うように (特定のバージョンの一連の変更)を使用する代わりに、デフォルト バージョンと特定のバージョンの一連の変更年を慎重に「優先的にマージ」することにより、特定のバージョンごとに「次の変更年」のシーケンスを作成yearsする --もちろん、シーケンスに配置された各変更年は、適切なファイルのセットに関連付ける必要があります。

したがって、正確な仕様を表現できる場合は、コーナー ケースに至るまで、この疑似コードを変更して必要なマージを行う方法を示すことができます。正確な仕様が明確になるまで作業を行いたくありません。仕様は確かに簡単です。作業は不要です!-)

編集：新しいコメントが明確になったように、正確な仕様は確かに最も複雑なものであるため、適切にマージを行いました. したがって、上記の単純な回答の最後のループは次のように変更されます。

for version, years_dict in tree.iteritems():
    # have years_dict override default_version when coincident
    merged = dict(default_version, **years_dict)
    current_files = merged.pop(min_year)
    merged[max_year + 1] = None
    y = min_year
    while merged:
        next_change = min(merged)
        for f in current_files:
            writerow(version, y, next_change-1, f)
        y = next_change
        current_files = merged.pop(y)

重要な変更点は次のmerged = dict(...行です: Python では、これはマージされた新しい dict を作成することを意味します (dict は一般的なマッピングであり、通常、他の言語ではハッシュマップと呼ばれます)。これは、 と の合計またはマージですdefault_versionがyears_dict、キーが両方に存在する場合、値 fromyears_dictが優先されます。これは、両方に存在する年 (つまり、ファイルに変更がある年) のキー条件を満たします。

その後は順風満帆です: anydict.pop(somekey) はキーに対応する値を返します (また、それを anydict から削除します); min(anydict) は、辞書内の最小キーを返します。の「センチネル」イディオムに注意してくださいmerged[max_year + 1] = None。これは、「最大の 1 年後」の年は常に変更年 (ダミーのプレースホルダー値は None) と見なされるため、最後の行セットが常に適切に書き込まれることを示しています。 (最大年は ですmax_year + 1 - 1。つまり、max_year希望どおり正確に です)。

このアルゴリズムは、最大限に効率的ではなく、最も単純です! 私たちは何度も何度もやっていmin(merged)て、それを O(N 二乗) にしています。それぞれの変更年数はせいぜい数十年であるはずなので、余裕があると思いますmergedが、純粋主義者はひるむでしょう。もちろん、O(N logN) のソリューションを提示することもできます。年を一度だけソートし、そのシーケンスをたどって の連続する値を取得するだけですnext_change。完全を期すために...：

default_version[max_year + 1] = None

for version, years_dict in tree.iteritems():
    merged = dict(default_version, **years_dict)
    for next_change in sorted(merged):
        if next_change > min_year:
            for f in merged[y]:
                writerow(version, y, next_change-1, f)
        y = next_change

ここでsortedは、 のキーをmerged並べ替えたリストを示します。forそのリストを最初から最後までたどるステートメント (および最初は何も出力しない if ステートメント) に切り替えました。センチネルは default_version に置かれるようになりました (別のわずかな最適化のために、ループの外にあります)。この最適化されたバージョン (本質的には、わずかに高い抽象化レベルで動作するため) が以前のものよりも小さく、単純であることが判明したのは面白いことです;-)。

于 2009-07-05T21:57:05.133 に答える