> This one is better.
> BTW it's very interesting to check something :)
> Imagine we have image directory with ALL possible
> names from aaaa to zzzz. Which algorithm will work
> faster?
Well....
At my CPU/File I/O speeds, etc, the loop takes approx. six minutes to complete, slipping to almost seven minutes with 1000 files to process. The regex matching algorithm, however, takes roughly 0.00016 seconds per file with 100, which actually gets faster with more files, reaching .000046 seconds per file with 1000 files.
If all files were present from aaaa.jpg to zzzz.jpg, you would have 26^4, or 456,976 files. The brute force algorithm would still take at least 400 seconds, presumably, and the regex algorithm would presumably take less than 456,976*.000046, or 21.0 seconds. So, this regex algorithm apparently somehow edges it out either way.
Evidence and code follows:
Terminal output:
kev@mymachine ~/java$ rm -f image/*
kev@mymachine ~/java$ java AlgorithmTest 100
Making 100 files...
Starting brute force matching...
..........................Done.
Found 100 files in 368.11 seconds,
for an average of 3.6811000000000003 seconds/file.
Starting regex matching...
Found 100 files in 0.016 seconds,
for an average of 1.6E-4 seconds/file.
kev@mymachine ~/java$ rm -f image/*
kev@mymachine ~/java$ java AlgorithmTest 1000
Making 1000 files...
Starting brute force matching...
..........................Done.
Found 1000 files in 402.453 seconds,
for an average of 0.40245299999999995 seconds/file.
Starting regex matching...
Found 1000 files in 0.046 seconds,
for an average of 4.6E-5 seconds/file.
kev@mymachine ~/java$
import java.io.File;
import java.io.FilenameFilter;
import java.io.IOException;
import java.util.Random;
public class AlgorithmTest {
public static final String BASE = "image/";
public static final String EXT = ".jpg";
public static final String CHARS = "abcdefghijklmnopqrstuvwxyz";
public static Random random = new Random();
public static String getFileName() throws IOException {
String ret = BASE;
for (int i = 0; i < 4; i++) {
ret += CHARS.charAt( random.nextInt(26) );
}
ret += EXT;
return ret;
}
public static void makeACrapLoadOfFiles(int filesToCreate) throws IOException {
for (int i = 0; i < filesToCreate; i++) {
new File( getFileName() ).createNewFile();
}
}
public static int bruteForceFindFile() {
int found = 0;
for (char c1 = 'a'; c1 <= 'z'; c1++ ) {
System.out.print(".");
for (char c2 = 'a'; c2 <= 'z'; c2++ ) {
for (char c3 = 'a'; c3 <= 'z'; c3++ ) {
for (char c4 = 'a'; c4 <= 'z'; c4++ ) {
if ( new File(BASE +
String.valueOf(c1) +
String.valueOf(c2) +
String.valueOf(c3) +
String.valueOf(c4) +
EXT).exists() ) {
found++;
}
}
}
}
}
System.out.println("Done.\n");
return found;
}
public static int regexMatchingFindFile() {
int found = 0;
FilenameFilter fnf = new FilenameFilter() {
public boolean accept(File dir, String name) {
return (name.matches("^[a-z]{4}\\.jpg$"));
}
};
String[] files = null;
try {
File imageDir = new File("./image");
files = imageDir.list(fnf);
} catch (Exception e) {
e.printStackTrace();
}
for (int i = 0; i < files.length; i++) {
found++;
}
//// I could cheat and do a
// return files.length;
//// but it might violate the purpose of the exercise.
return found;
}
public static void main(String[] args) {
if (args.length < 1) {
System.out.println("Usage: pass in one integer argument saying " +
"how many files to test with.");
System.exit(-1);
}
int numFiles = Integer.parseInt(args[0]);
try {
System.out.println("\n\nMaking " + numFiles + " files...");
makeACrapLoadOfFiles(numFiles);
System.out.println("\n\nStarting brute force matching...");
long bfStart = System.currentTimeMillis();
int bfFound = bruteForceFindFile();
long bfEnd = System.currentTimeMillis();
double bfTime = ( (double)bfEnd - (double)bfStart ) / 1000.0;
double bfAverage = ( (double)bfTime/(double)bfFound );
System.out.println("Found " + bfFound + " files in " + bfTime + " seconds, ");
System.out.println(" for an average of " + bfAverage + " seconds/file." );
System.out.println("\n\nStarting regex matching...\n");
long maStart = System.currentTimeMillis();
int maFound = regexMatchingFindFile();
long maEnd = System.currentTimeMillis();
double maTime = ( (double)maEnd - (double)maStart ) / 1000.0;
double maAverage = (double)maTime/(double)maFound;
System.out.println("Found " + maFound + " files in " + maTime + " seconds, ");
System.out.println(" for an average of " + maAverage + " seconds/file.");
} catch (IOException ioe) {
ioe.printStackTrace();
}
}
}
