1
$\begingroup$

In our organization we have various business units that organize their data in different ways. The folder structure can vary, but they abide by business unit practices when making backups etc.

I am to make a scraper that locates backups and copies them. I have found a general way to describe the business unit specific way of making backups. I do not wish to search the whole directory structure because it may be massive.

/X
  A
   a
  B
   a
  C
   a

Here for instance, in order to locate all the lower case "a", I can say that the criteria is a list of strings

"*","*","a"

The X will satisfy the first asterisk. The A/B/C subfolders will satisfy the second asterisk and the lower case a's will satisfy the lower case a criteria. Already, we see a potential for the two "" to be represented as "" and a multiplier modifier.

All well and good. In C#, this is easy. The DirectoryInfo class has the GetDirectories method which performs a scan with a searchpattern.

However, what if the structure is staggered? What if I would like to list the criteria as follows?

Pattern="*" MaxRepetitions=3 MinRepetitions=1
Pattern="a" MaxRepetitions=1 MinRepetitions=1

The code becomes messy quick. For instance "a" will also be satisfied by "*" criteria, so the engine may not be "sure" which criteria is being exhausted and therefore must test multiple criteria on next pass. I assume regex has solved this problem because it runs so fast on large strings and still manages to return without duplicates.

Are there any pointers? Is there any theory behind how to preserve a context (visitor state), assuming this is the visitor pattern.

$\endgroup$
0
$\begingroup$

These things are generally done through backtracking. Which in your case would look somewhat like this:

  1. Go down 3 levels and look for 'a'
  2. If you find some -> perform your magic
  3. If you find none (or if you do, depending on the implementation) -> go up 1 level repeat steps 1-3

Really this is no better than simply searching all directories in the worst case, but there is no way you can guarantee having found all a's without searching every directory anyway (assuming no prior knowledge). However this solution will have a much better average case performance if the a's are always at the maximum level than simply starting to search at level 1, then level 2 etc.

edit: also, regexes are fast because the average CPU performs billions of operations per second. If you're copying files then the copying will be the part slowing it own drastically anyway so you probably should not be too concerned with the performance of your searching algorithm

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.