Iterating thousands of times over large collections: advices

This is a pet project :)

I have hundreds of playlist files .m3u whose many entries have a wrong path. I'd like to fix them programmatically. Suppose one of my .m3U contains the following entry:

z:\wrong-folder\Michael Jackson - Thriller.mp3


The file is stored in:

G:\my-collection-of-mp3\any-folder\Michael Jackson - Thriller.mp3


The goal is to update the wrong path with the right one :)

I have to create a collection of all my mp3 (around 6000 files) and their path. As I said, I have hundreds of .mu3 ; each .m3u has 15-20 entries. I have to check each entry against my 6000-entries-collection until the name matches. Well it is a plethora of loops :)

To ease the process I would create an ordered dictionary of dictionary whose the key would be the first letter of the name i.e. "M" (for Michael Jackson - Thriller.mp3) and the sub dictionary would be:

- key: Michael Jackson - Thriller.mp3
- value: G:\my-collection-of-mp3\any-folder\Michael Jackson - Thriller.mp3


Doing so I would only to iterate over a subset of the collection (looking up for the first letter of the name) instead of iterating over the whole non ordered collection.

A / Albert Jones - Song 1.mp3 -> G:\my-collection-of-mp3\any-folder\Albert Jones - Song 1.mp3

M / Michael Jackson - Thriller -> G:\my-collection-of-mp3\any-folder\Michael Jackson - Thriller.mp3


Do you think it is ok? What else would you recommend?

• Why do you think you need to break up a dictionary of just 6000 files? What makes you think you can repeat a key (e.g. M) in a dictionary? What have you tried? SO is for specific programming questions. – Blam Aug 22 '12 at 16:27
• It is a dictionary of dictionary – roland Aug 22 '12 at 16:28
• Still why do you think you need to break up 6000? Hash is Int32. Did you try a straight single dictionary? – Blam Aug 22 '12 at 16:31

If you are particularly interested in doing substring look-ups, you could look into the Trie data structure. You will be stuck writing your own, however, as there is no implementation I know of in the BCL.

Alternatively, if you just want to put something together quick, you could just use a normal, single-level-deep dictionary keyed by file name. If you build your dictionary for existing MP3s first using an actual System.Collections.Hashtable or (preferably) System.Collections.Generic.Dictionary<TKey,TValue>, the key lookups will be constant-time.

The only loops you will need are the initial loop to build the correct file path dictionary, then the loops over .m3u files with sub-loops over their referenced files. Retrieving the correct mp3 reference for each file in a m3u is just value = dictionary [key] or dictionary.TryGetValue (key, out value). The lookups themselves are not loops - rather, they generate hash codes for the keys which ultimately translate to array indexes in the underlying data structure.

• By the way, List<T> has a BinarySearch() ; do you think it is worth taking a look at it based on my situation? – roland Aug 22 '12 at 18:30
• The BinarySearch function would work as well if you make sure the list is kept sorted. Assuming the function to retrieve your list of correct file paths is already sorted, it is possible that this ends up performing better. I couldn't tell you for sure if the overhead of hash generation would out-weigh the logarithmic-time binary search for 6000 elements, though. Since this is a personal project, it may be interesting to do it both ways and compare, since neither should take all that much time to implement. – Dan Lyons Aug 23 '12 at 17:54

If I were you I'd do two passes (error checking, case-invariance and recursion omitted for clarity).

Pass1:

  Dictionary<string, string> paths = new Dictionary...
foreach(var filepath in files(recursively))


Pass2:

  foreach(string path in m3ulist)
if(!System.IO.File.Exists(path))
{
string key = new System.IO.FileInfo(path);
if(paths.ContainsKey(key))
MessageBox.Show(string.Format("replacing path {0} with {1}", key, paths[key]));
else
MessageBox.Show(string.Format("could not find mp3 path", key));
}

• I guess the line in the second pass should be string key = new System.IO.FileInfo(path).FileName;. – Daniel Hilgarth Aug 22 '12 at 16:22
• The potential problem here is duplicate FileName. But still +1 – Blam Aug 22 '12 at 16:33
• This is what I first came up with. Isn't it possible to improve performance? – roland Aug 22 '12 at 16:51
• @roland So you had the same code and came to the conclusion paths.ContainsKey(key) was the bottle neck? How did you determine that? – Blam Aug 22 '12 at 17:31
• No particular assumption. Only thought that other solutions would have brought other benefits – roland Aug 22 '12 at 18:19