5 ms·
Make it an explicit part of the data model.
by mvc 8y ago
Make it an explicit part of the data model.
- ridiculous_fish 8y agoA quicksort that supported progress reporting and cancellation might have a function parameter that it calls periodically to report progress, with the function returning a bool indicating cancellation. But this is using code, not data. How might this be implemented within the data model?
- yen223 8y agoHow do you measure progress in a quicksort?
- ridiculous_fish 8y agoGlad you asked. The progress should be a bound on the worst case time. If you have N elements, then the initial worst case time is N^2. Say after the first partition, you are left with pieces N/3 and 2N/3; the worst case time is now (N/3)^2 + (2N/3)^2. Your progress after the first partition is the difference between the original worst case and the new worst case. This can make for uneven progress advancement but it’s monotonic: the progress bar will never go backwards.
- jhomedall 8y agoYou would implement the sort so that it either: 1: Returns the sorted list (once finished) 2: Returns an intermediate state containing the progress of the sort in addition to the current state of the sort. You would repeatedly pass the intermediate state to the sorting function until finished. You can use the progress component of the intermediate state to track progress. Something like the following (I don't actually write Haskell, so this could probably be represented better): data SomeIntermediateState = ... data Progress = Double data SortState a = Complete [a] | InProgress (SomeIntermediateState, Progress) sortInit :: [a] -> SortState sort :: SortState -> SortState