خوارزمية البحث في المجلد

Question

لست متأكدا مما إذا كان هذا هو النوع المعتاد من السؤال الذي طرحته هنا، أو إذا سأحصل على أي إجابات على هذا واحد، لكنني أبحث عن نهج رمز زائدي لإنشاء سجلات ربط DB من بنية مجلد تحتوي على صورة الملفات.

لدي مجموعة من المجلدات، وهي منظمة كما folllows:

+-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 فصاعدا. أحتاج إلى إنتاج جدول الروابط لكل إصدار - استنادا إلى ما إذا كان لديك صور خاصة بهم، أو ما إذا كان الاستفادة من الإصدار الافتراضي ...

لذلك على سبيل المثال، لا يحتوي الإصدار_1 على ملفات صور، لذلك أحتاج إلى تحقيق روابط للصور الافتراضية، بدءا من عام 2000 واستمرت حتى عام 2009.

يبدأ الإصدار 2 من ناحية أخرى باستخدام الصور الافتراضية في عام 2000، ولكن ثم يستخدم مجموعتين جديدين أولا 2001-2002، ثم 2003-2009. قائمة الروابط المطلوبة وبالتالي ...

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
...

(الافتراضي هو مجرد ذلك - حامل مكان، ولا توجد روابط مطلوبة لها.)

في الوقت الحالي، أعاني من خلال المجلدات، ومصفوفات البناء، ثم تقليم الدهون في النهاية. كنت أتساءل فقط عما إذا كان هناك قطع قصيرة، باستخدام نوع من نهج معالجة النصوص؟ هناك حوالي 45000 مجلدات، معظمها فارغة :-)

Answer 1

إليك بعض Python Pseudoodocode، بالقرب من القابل للتنفيذ (يحتاج إلى واردات مناسبة و DEF لوظيفة 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)

غموض واحد في المواصفات والمثال هو ما إذا كان من الممكن أن يقوم Default_Version بتغيير مجموعة الملفات في بضع سنوات - هنا، أفترض أنه لا يحدث (إصدارات محددة فقط تغيير بهذه الطريقة، الإصدار الافتراضي يحمل دائما مجموعة واحدة من الملفات).

إذا لم يكن هذا هو الحال، فما يحدث ما إذا كان الإصدار الافتراضي يتغير في سنوات (Say) 1999 و 2003، وإصدار الإصدار 1 في عامي 2001 و 2005 - ما هي الملفات التي يجب أن تستخدم الإصدار 1 ل 03 و 04، الجديد في الإصدار الافتراضي ، أو تلك المحددة في 01؟

في الإصدار الأكثر تعقيدا من المواصفات (حيث يمكن أن يتغير كل من Default_version و One المحددة، مع التغيير الأحدث لأعلى الأسبقية، وإذا كان كل من التغيير المحدد والإفتراضي في نفس العام، فإن الأسبقية المحددة التي يحتاجها المرء للحصول على كل تسلسل "Next Change Year" التسلسل، لكل إصدار محدد، عن طريق "دمج الأولوية" الدقيق تسلسل سنوات التغيير للحصول على إصدار افتراضي ومحدد، بدلا من استخدام years (يجب أن يرتبط تسلسل التغييرات في الإصدار المحدد) كما أفعل هنا - وكل عملية تغيير في التسلسل مرتبطا بمجموعة الملفات المناسبة بالطبع.

لذلك إذا كان من الممكن التعبير عن المواصفات الدقيقة، في حالات الزاوية، يمكنني إظهار كيفية القيام بالاندمج المطلوب عن طريق تعديل هذا pseudoodocode - أفضل عدم القيام بالعمل حتى يتم توضيح المواصفات الدقيقة، لأنه إذا كان المواصفات هي بالفعل أبسط، والعمل لن يكون غير عملي! -)

يحرر: كما أوضح تعليق جديد، فإن المواصفات الدقيقة هي في الواقع الأكثر تعقيدا، لذلك نحن نقوم بالاندماج بشكل مناسب. لذلك الحلقة في نهاية الإجابة المبسطة أعلاه التغييرات على:

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(... خط: في بيثون، فإن هذا يعني جعل دمج DICT الجديد (DICT هو رسم خرائط عام، وسيتم تسمية عادة HASHMAP بلغات أخرى) وهو المبلغ، أو الاندماج، من default_version و years_dict, ، ولكن عندما يكون مفتاح موجود في كل من هؤلاء، فإن القيمة من years_dict الأسبقية - مما يلبي الشرط الرئيسي لمدة عام موجود (أي هو سنة مع تغيير في الملفات) في كليهما.

بعد ذلك إبحار سهل: anydict.pop (قنصر) إرجاع القيمة المقابلة للمفتاح (وأيضا يزيلها من أي قاعدة)؛ يعيد MIN (Anycedict) الحد الأدنى للمفتاح في القاموس. لاحظ "الحارس" المصطلح في merged[max_year + 1] = None: . max_year + 1 - 1, وهذا هو بالضبط max_year, ، حسب الرغبة).

هذه الخوارزمية ليست فعالة بشكل فعال، أبسط فقط! كانوا يفعلون min(merged) مرارا وتكرارا، مما يجعلها O (N Squared) - أعتقد أننا نستطيع تحمل ذلك لأن كل منها 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 بيان للمشي في تلك القائمة من البداية إلى النهاية (وإذا كانت البياناتية لإنتاج أي شيء في المرحلة الأولى). يتم الآن وضع Sentinel الآن في Default_Version (لذلك إنه خارج الحلقة، لتحسين طفيف آخر). من المضحك أن نرى أن هذه النسخة الأمثل (بشكل أساسي لأنها تعمل بمستوى أعلى قليلا من التجريد) تبين أن تكون أصغر وأبسط من تلك السابقة ؛-).