3

Let's say I have an algorithm whose running time is exponential in the worst case, but I'm using a very efficient heuristic for it that in practice seems to make it work in linear time.

Basically, the algorithm has a queue, and it keeps pushing/popping items until it's empty.
For the sake of illustration, pretend the algorithm is A*, with the exception that when we reach a node twice, we don't discard the longer path -- we investigate that one as well. So, potentially, we have an exponential number of paths to investigate, but because of the heuristic, it can be linear in practice.

Clearly, the point of the question is that I can never be sure how close I am to the answer.
The only statistics I can compute efficiently for progress purposes are lower bounds on the remaining work, not upper bounds.

What is a good way to display a progress bar for such an algorithm?

Improve this question
6
  • You'd have to look at other unknowns. The big one that comes to mind is life - where we measure progress in milestones and stages but one can never say how far through they are. Is there some way to break up your process the same way? Does it have infancy, childhood, adolescence, young adulthood, prime earning years, maturity, retirement, and old age? Or something analogous?
    – Imperative
    Jun 19, 2014 at 0:07
  • @Imperative: There are no milestones, and I believe it's an NP-hard problem that I'm dealing with, so I don't expect there to be any that I've missed. Again, think of the A* example I gave: it's just a huge loop that keeps pushing/popping off the queue until it pops a path whose terminus is the destination. There are no milestones there, because I have no idea what the intermediate nodes may be.
    – user541686
    Jun 19, 2014 at 0:09
  • 1
    Well in terms of the programming/logic aspect, there are better exchanges in the network. I'm thinking of this as a display problem so it's much simpler. A progress bar, by definition, requires a benchmark. Whether you're bench marking against past data, mean data across clients, or an actual end point it sort of requires a point of reference to orient on. Otherwise you end up with the classic problem Windows has with progress bars when installing software where they become meaningless.
    – Imperative
    Jun 19, 2014 at 0:22
  • With that said, most progress bars in that case are just a moving line to indicate "data is being processed, this process has not hung"
    – Imperative
    Jun 19, 2014 at 0:22
  • @Imperative: How would benchmark data change anything? It's still possible for the time to go over those of the previous benchmarks...
    – user541686
    Jun 19, 2014 at 0:26

3 Answers 3

Reset to default
12

My recommendations are mostly based on the book Designing and Engineering Time by S.Seow:

  • Use non-temporal units for progress indicator, e.g. number of paths, etc. At least, it adds meaningful indicator and shows responsiveness of the long process.
  • Inform user on lower time bound, e.g. "This takes at least 20 min". This allow user to decide if the process affordable for him right now and plan his activity.
  • Use Time Anchor Matrix to express the time. This is the set of numbers, people gravitate to in time expression: 1, 2, 3, 5, 10, 15, 20, and 30.
  • Use background execution and notification. Allow users to do other work while process execution and notify them on process completion.
  • Allow user to cancel the long task and use mid-term results if possible. For example, some users could be happy with non-optimal, but quite fast results. This is just trade-off.
  • Use appropriate progress bar, see the pictures:

.

enter image description here

.

enter image description here

Improve this answer
2
  • +1 this is a fantastic answer, way better than anything I expected. Thank you!
    – user541686
    Jun 19, 2014 at 10:16
  • @Mehrdad, this is indeed a fantastic answer. As a side note, one could see how a very detailed and technically elaborated question such as yours can be answered using the long-standing principles coming from an user-oriented perspective ;) Thanks again, Alexey for the recap from the book.
    – Son Do Lenh
    Jun 19, 2014 at 21:48
1

This scenario just doesn't fit with a progress bar type feedback. You never know how close you are to the end, so you can't show progress as a percentage of a fixed length bar.

What about using a pulsing / rotating animation to indicate that the algorithm is still running? You can accompany this with some stats on how many nodes are processed (or whatever else might be useful to the user to indicate progress). You don't know when it will finish, but you can say how much it has done so far.

Improve this answer
1
  • I dislike "doing something" animations that give no indication of progress. If a program will frequently operate on similar batches of things, it may have no way of recognizing that a given job is similar to a previous one, but the user might know. If the program displays "Processed 19,293 items" and a user knows from experience that it would take about five more minutes once it reached that point, a user who saw that message again would know that there were about five minutes left. If the program simply showed an animation, the user would know nothing.
    – supercat
    Jul 25, 2014 at 22:37
0

What about showing a linear progress but once you'll see it's deviating from the linear progress too much, displaying sth like "wow, decent problem to chew, gimme some time". And depending on how much you want to invest into this, you can set more break points - if it reaches let's say 1.5^2 of expected time you can display "this one's tough, go and grab a coffee in the meantime"

Kinda a variation of the infancy, childhood, adolescence, but these stages would not be strictly set to let's say 0-6 years etc. but would be defined according expected and real time.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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