Algorithm optimization for a map of strings

[baudolino]

I have a map<string, time_t>; string represents a filesystem path, time_t is a timestamp associated with that path. My problem is to find the best version of a directory and its subdirectories, regarding its timestamp.

For example, if I have:
/home, 1000
/home/user1, 2000
the best version is (/home, 1000) AND (/home/user1, 2000) ( because /home includes /home/user1 and /home/user1 has a timestamp bigger than its parent directory).

If I have:
/home, 2000
/home/user1, 1000
the best version is (/home, 2000) ( because /home includes /home/user1 and /home/user1 has a timestamp smaller than its parent directory).


A larger example:
/home/ ---> 1000
/home/user1 ---> 2000
/home/user1/aaa --> 500
/home/user2 ---> 3000
/mnt --> 1000
/mnt/cdrom -->2000
/usr/ --->3000
/usr/bin -->2000

I have to find the best versions of every directory (that means the most recent time for a directory); in my example, this should be:

/home, 1000
/home/user1, 2000
/home/user2, 3000
(/home/user1/aaa has a timestamp of 500, less than /home/user1 timestamp, so it's no good)

/mnt, 1000
/mnt/cdrom, 2000

/usr, 3000
(usr/bin has a timestamp of 2000, less than /usr timestamp, so it;s no good).

I'm using an algorithm to do my job, but I'm not satisfied with it. Basically, I iterate through map: for every item, find if the next items are included in it and verify their timestamps, keep a stack of parents etc etc etc.

I know that exist a better solution, but I cannot find it :(. Maybe someone could help me, I'm not asking that one writes the code for me, but merely indicates me the algorithm I should use, or how this problem could be decomposed (something like this: "hey, stupid, just use Divide and conquer"; or "you moron, this is a classic example of XXX algorithm").
Thanks.

[weaknessforcats]

Have you considered a multimap<string, string> where the key is the parent folder and the value is the full path to the folder?

That way you could use the equal_range algorithm passing iterators for the begin and end of the multimap. You will get back a pair of iterators that bracket all occurrences of the key. If I understand correctly you can iterate this range and keep the highest time stamp.

[baudolino]

Thank you, I've used a multimap and backtracking, now the code looks easier to understand.

This is the initial map (keys)

/mnt/download/Backup/data/Test/faild/root/0/4
/mnt/download/Backup/data/Test/faild/root/0/4/h
/mnt/download/Backup/data/Test/faild/root/1
/mnt/download/Backup/data/Test/faild/root/1/6
/mnt/download/Backup/data/Test/faild/root/1/6/j
/mnt/download/Backup/data/Test/faild/root/1/6/l
/mnt/download/Backup/data/Test/faild/root/1/8
/mnt/download/Backup/data/Test/faild/root/1/9
/mnt/download/Backup/data/Test/faild/root/1/9/m
/mnt/download/Backup/data/Test/faild/root/2/a
/mnt/download/Backup/data/Test/faild/root/2/a/n
/mnt/download/Backup/data/Test/faild/root/2/c
/mnt/download/Backup/data/Test/faild/root/2/c/p
/mnt/download/Backup/data/Test/faild/root/3/f
/mnt/download/Backup/data/Test/faild/root/3/f/q
/mnt/download/Backup/data/Test/faild/root/3/f/v


This is the multimap (keys and values):

/mnt/download/Backup/data/Test/faild/root---->1
/mnt/download/Backup/data/Test/faild/root/0---->4
/mnt/download/Backup/data/Test/faild/root/0/4---->h
/mnt/download/Backup/data/Test/faild/root/1---->8
/mnt/download/Backup/data/Test/faild/root/1---->6
/mnt/download/Backup/data/Test/faild/root/1---->9
/mnt/download/Backup/data/Test/faild/root/1/6---->l
/mnt/download/Backup/data/Test/faild/root/1/6---->j
/mnt/download/Backup/data/Test/faild/root/1/9---->m
mnt/download/Backup/data/Test/faild/root/2---->c
/mnt/download/Backup/data/Test/faild/root/2---->a
/mnt/download/Backup/data/Test/faild/root/2/a---->n
/mnt/download/Backup/data/Test/faild/root/2/c---->p
/mnt/download/Backup/data/Test/faild/root/3---->f
/mnt/download/Backup/data/Test/faild/root/3/f---->q
/mnt/download/Backup/data/Test/faild/root/3/f---->v

My algorithm follows:

for every p in multimap
if p already visited
continue
endif

mark p as visited
equal_range(p);
//backtracking algorithm: for every item in range, make an equal_range(key + value) etc etc
endfor

I have a problem, though: this loop iterates through all multimap's elements, even through the ones that have been processed (hence the test "if p was already visited"). To get rid of this loop, I need to find out the unique keys of multimap (and apply equal_range only for them). How can I do this, let alone the possibility that I could remember those unique keys when multimap is created?

Thank you.

[JosAH]

If you consider that file system a tree, is it true that you want to find the paths
from the root to a node down the tree as long as the child 'value' is larger than
the parent's value?

kind regards,

Jos

[baudolino]

you want to find the paths from the root to a node down the tree as long as the child 'value' is larger than
the parent's value

Not exactly. Even if child's value is smaller than root's value, maybe child's child value is larger than root's.

/home 100
/home/user 50
/home/user/file 200

In this case, solution is: (/home,100) and (/home/user/file,200).
/home/user is useless because has a smaller timestamp than its parent.

[JosAH]

Not exactly. Even if child's value is smaller than root's value, maybe child's child value is larger than root's.

/home 100
/home/user 50
/home/user/file 200

In this case, solution is: (/home,100) and (/home/user/file,200).
/home/user is useless because has a smaller timestamp than its parent.

So if a child has a larger value than its parent it's going to be part of that 'best' list?
If so, a simple depth first recursive traversal can do the job.

kind regards,

Jos

[baudolino]

If so, a simple depth first recursive traversal can do the job.

Basically, that is what I've done, after using a multimap (only that are several trees, each one corresponding to a unique key): start at every root (every unique key) and explore as far as possible before backtracking.

But I didn't know how to do it when using my initial map. Thanks, weaknessforcats, for the multimap idea.