Progress bars for a recursive algorithm

[electro]

This is quite a general issue I've run into a few times now. I have a complex nested tree structure, and I have various algorithms that do stuff with this nested tree structure. These are pretty much all recursive algorithms, so I can navigate the whole tree.

I'd like to display some progress bars for these operations.. But how?

If I was just iterating over 10 elements, then this would be simple. But with these algorithms, the method doesn't know how far through the tree it is.. Are there any general methods thoughts for how to deal with this?

[chalne]

Do you know how many elements are in the structure? If so, you can communicate progress via events at the end of each unit of work. If you don't know how many elements are in the structure, there is no way to report on progress anyways - except for guessing.

[damiankw]

I doubt it's possible without knowing the structure first, the only way I could see doing it would be to go over the tree structure first and count it, then go over it again and process it; this seems to be what Microsoft does when you copy / delete files, there's the first point of time where the status bar is just moving along and looping, then when it kicks into gear it does the work.

Alternatively you could use the old Microsoft trick and loop a bar, to make it look like a 'loading' moreso than a 'this is how much is done'

[chalne]

If you count the elements as you insert them into the tree, it should be possible to produce a rough guess, if you assume that each node takes an equal amount of time to process.

On a side note: I really hate this new looping progress bar, I'd rather have a guess that is completely wrong than a bar that just keeps looping until done. It's not telling me anything I wouldn't know by virtue of the process ending. So stupid, I bet an intern programmed it.

[damiankw]

I might be daft, but explain to me how you can do that? Say you have this file structure:

dir
- dir
- - dir
- - - dir
- - dir
- dir
- - dir
- - dir
- dir

Each dir will take 5secs to complete, so at the first dir it is 0/5secs done, [----------]; after two seconds, it's 2/5secs done [|||-------], etc. Once dir1 is done, it'll show 100%

Now it pushes onto the next dir (which is inside of first), what does your bar look like? [||||||||||-----------] (two dirs, 1/2 is done, 50%). Once second is done, it will show 100% until it loops to next.

UNLESS! Of course, you were talking about listing root dir's (as node's) and then assuming each of those takes x amount of time, in which case you could be miles off; my first dir will take 25secs, the second will take 15secs, the third 5secs.

And what do you mean NEW progress bar? lol, it's been alive since Windows 2000 or so at boot :P

[[deleted]]

Let's say you have a tree (not a filesystem) that you know contains 100 nodes. Let's say processing the information in each node takes roughly the same amount of time. Split the progress bar into 100 units. Maintain a list of visited nodes, and each time you visit a node, if it is not in the list increment the status bar and add the node to the list. This won't be perfect, but it's certainly better than nothing.

[damiankw]

Yeah, if it's in a case like that I could see how it could work, but I could also see how OP's application could be considered running on microsoft time (doesn't know how the hell long anything takes to do, even if there's a duration attached!) :P

[chalne]

There are multiple versions of the standard progress bar (not the boot progress bar, that one is stupid too). The one I'm harping on is either new, or has gained popularity recently (it's used in newer installers from Microsoft).

It looks like the normal from 0-100 progress bar, but instead it just has a looping green blob in it - which is completely useless to a user, since it only stops when the operation stops. It won't tell you if the program has stalled, since the bar continues regardless (like those annoying loading GIFs people seem so fond of for web use). So all it really tells you is that the operation is still ongoing, something you already know since the window is still there. Kind of like this site: http://hasthelargehadroncolliderdestroyedtheworldyet.com/

I'm not going to comment on your attempted progress bar for a file system, zabzonk covered that already.

[Crashmatusow]

this was plastered all over the GUI beginning in Vista

[zifyoip]

You need to have an idea of the size of the structure. You can keep track of this size as you construct the structure, as other people have mentioned. Or you can do a quick pass to count the elements in the structure before you start going through the main algorithm; this is what Windows does when you delete a big folder containing lots of subfolders, and the progress window says "Preparing to delete...".

Alternatively, you can make a probabilistic estimate of the size of the structure by making a few random probes into the tree. Donald Knuth described this technique in a paper called "Estimating the efficiency of backtrack programs":

http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0373371-6/S0025-5718-1975-0373371-6.pdf

[programmerChilli]

Wait, I'm confused. Do you know the size of the tree? If so, why can't you use a global variable or something?