Fleeting Thoughts (CS Edition)

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Fleeting Thoughts (CS Edition)

Postby Breakfast » Sat Feb 09, 2013 5:05 pm UTC

Maybe OOP concepts are so often implemented poorly because when we start to learn about programming we always begin with procedural techniques. If we began by teaching inheritance and polymorphism first would procedural logic and conditionals become the difficult concepts?

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Fleeting Thoughts (CS Edition)

Postby troyp » Tue Feb 12, 2013 3:29 pm UTC

It's hard to imagine stuff like jumps/loops and conditionals being difficult, they're too basic. You can't give someone instructions in RL without those concepts. You couldn't even think without some implicit understanding of them.

Plus, to do OO programming you'd still need procedural (or else functional) logic to build methods from. Any kind of turing complete computation will need something equivalent to loops and conditionals.

meta-FT: I approve of CS FT. We should have FT everywhere!

EvanED
Posts: 4327
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby EvanED » Tue Feb 12, 2013 4:41 pm UTC

I have a friend whose intro CS class was taught like that. If you wanted a conditional, you had to make two classes and use virtual dispatch. (I'm not quite sure how you bootstrapped the procedure.)

He says he pretty much hated it. (Though I wouldn't be surprised if he had programming experience before.)

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby ahammel » Tue Feb 12, 2013 5:12 pm UTC

My impression was that horrible OO code usually comes from using heavy OO concepts when they're not really needed (factories for simple objects, complicated multiple inheritance chains, that sort of thing). See this guy's opinion, for example.

I imagine starting out with OO and then moving to procedural would only exacerbate that problem.
He/Him/His/Alex
God damn these electric sex pants!

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Fleeting Thoughts (CS Edition)

Postby Breakfast » Tue Feb 12, 2013 6:08 pm UTC

EvanED wrote:I have a friend whose intro CS class was taught like that. If you wanted a conditional, you had to make two classes and use virtual dispatch. (I'm not quite sure how you bootstrapped the procedure.)

He says he pretty much hated it. (Though I wouldn't be surprised if he had programming experience before.)

I'd be interested to know why he hated it. It may be that the idea of starting with inheritance and polymorphism truly is a bad idea. Would you happen to know if the class was successful overall or if there is anymore information about classes structured similarly?
ahammel wrote:My impression was that horrible OO code usually comes from using heavy OO concepts when they're not really needed (factories for simple objects, complicated multiple inheritance chains, that sort of thing). See this guy's opinion, for example.

I imagine starting out with OO and then moving to procedural would only exacerbate that problem.

What I've taken from that article is that he's arguing that most people don't know how to properly use tools (concepts) in regards to OOP. But doesn't that really apply to any concept that gets used incorrectly or heavy-handedly? He seemed to be of the opinion that the principles, when used well, work well. I may have missed the point though so please correct me if I did.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1397
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Fleeting Thoughts (CS Edition)

Postby Xenomortis » Tue Feb 12, 2013 6:11 pm UTC

It seems a very backwards thing to do.
It's easier to explain (in very loose terms) what the computer does when writing procedurally; the layer of abstraction is much less than with full object orientation.
Image

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby ahammel » Tue Feb 12, 2013 6:55 pm UTC

Breakfast wrote:What I've taken from that article is that he's arguing that most people don't know how to properly use tools (concepts) in regards to OOP. But doesn't that really apply to any concept that gets used incorrectly or heavy-handedly? He seemed to be of the opinion that the principles, when used well, work well. I may have missed the point though so please correct me if I did.
Yeah, I agree. I'm not an OO hater, and I don't think Jeff is either. I just think you're solving the wrong problem by wanting to introduce OO earlier.

Beginners are obviously going to use the first tools they learn for just about any problem. I think it's better that they learn to use procedural and functional tools first, because those tools are more widely applicable than heavy OO concepts. It's better to take a coder who knows how to do good procedural and functional tasks and then teach her to abstract over that using OO for large, complicated projects than to take an Object-Happy coder and try to get him to scale back to simpler tools for simple jobs.

It's better to think "I have a complicated problem. Do I really need to use complicated design patterns for it?" than to think "I have a simple problem. Time for really complicated design patterns!".
He/Him/His/Alex
God damn these electric sex pants!

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Fleeting Thoughts (CS Edition)

Postby Breakfast » Thu Feb 14, 2013 6:03 pm UTC

ahammel wrote:Yeah, I agree. I'm not an OO hater, and I don't think Jeff is either. I just think you're solving the wrong problem by wanting to introduce OO earlier.

Beginners are obviously going to use the first tools they learn for just about any problem. I think it's better that they learn to use procedural and functional tools first, because those tools are more widely applicable than heavy OO concepts. It's better to take a coder who knows how to do good procedural and functional tasks and then teach her to abstract over that using OO for large, complicated projects than to take an Object-Happy coder and try to get him to scale back to simpler tools for simple jobs.

It's better to think "I have a complicated problem. Do I really need to use complicated design patterns for it?" than to think "I have a simple problem. Time for really complicated design patterns!".

I had realized that teaching beginners OOP concepts first would cause them to try and shoehorn problems into pre-fit design patterns and solutions; and I agree that it is harder to have someone scale down a design than provide a simple solution for a simple problem. I guess my hope was that I'd hear success stories were someone was taught like that. Ah well, that's why the idea was just a fleeting thought.

Everyone should feel free to share any thoughts they have on any CS topic!

Nem
Posts: 335
Joined: Fri Aug 14, 2009 12:19 pm UTC

Re: Fleeting Thoughts (CS Edition)

Postby Nem » Thu Feb 14, 2013 10:48 pm UTC

From the outside, i.e. not knowing OOP, given the responses here, I imagine either that OOP is being taught poorly - i.e. there's some simple analogy that would make it make sense that's not being used - or that it's being taught as a general solution to a set of problems, some of which it's ill suited to.

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Fleeting Thoughts (CS Edition)

Postby troyp » Fri Feb 15, 2013 3:53 am UTC

Nem wrote:From the outside, i.e. not knowing OOP, given the responses here, I imagine either that OOP is being taught poorly - i.e. there's some simple analogy that would make it make sense that's not being used - or that it's being taught as a general solution to a set of problems, some of which it's ill suited to.

I think at least the latter is true. Not so much about OOP in general, but inheritance. I think interface implementation inheritance is actually a somewhat specialized technique, and certainly not basic enough to be taught to beginners. Interface inheritance is much more generally important, but still something that should be taught a bit later on, I think. If nothing else, it would be good if students understood the problem abstract classes solve before coding them. They should be taught the importance of interfaces, then get some experience with abstract types just using duck typing (eg. writing tree processing functions that work on any class with a .subtrees() method), then learn whatever language constructs support them.

As far as analogies go, sometimes I wonder if there isn't more a problem with their presence than their absence. There's too much emphasis on objects as modelling real-world (often physical) stuff. There needs to be more on how classes and objects apply to programming. And they should be related to whatever the student has already encountered: closures, structs, whatever.

Perhaps even start off by converting some appropriate function to a class that stores the function arguments as attributes and then executes the function as a .run() method. That would be a simple illustration of combining data with related functions and of creating multiple instances of a class. Then you could do the same for other functions and explain how problem.run() looks up the run() method at runtime. And so forth.
(I'm just making this up on the spot, but the point is that OO stuff should follow logically from what students already know, rather than just all being dumped on them as this entire...fait accompli of programming constructs and rules and design principles that they're supposed to just accept as "the way to do things" without really knowing why.)

edit: s/interface/implemenation/
Last edited by troyp on Sat Feb 16, 2013 11:25 pm UTC, edited 1 time in total.

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Fleeting Thoughts (CS Edition)

Postby headprogrammingczar » Fri Feb 15, 2013 12:28 pm UTC

Fleeting thought: delimited continuations are a rather redundant thing to have in a pure language, when you can do something like this (Haskell):

Code: Select all

shift = Cont
reset = flip runCont id
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby ahammel » Sat Feb 16, 2013 7:29 pm UTC

Nem wrote:From the outside, i.e. not knowing OOP, given the responses here, I imagine either that OOP is being taught poorly - i.e. there's some simple analogy that would make it make sense that's not being used - or that it's being taught as a general solution to a set of problems, some of which it's ill suited to.
The other possibility is that OO is being taught just fine, and the complaints about it being misused are a bit over-hyped.

I have no idea if that's the case or not, but I suspect there's a tendency to remember only the very worst OO code one sees and report that to the internet.
He/Him/His/Alex
God damn these electric sex pants!

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby Xanthir » Mon Feb 18, 2013 6:27 am UTC

Based on my own personal experiences, I'm firmly of the opinion that inheritance of any kind is something to be used only in rare circumstances, and teaching it too early ruins people's conception of what OO is. It doesn't help that what most people actually mean by inheritance most of the time is captured best by mixins, which aren't implemented in most mainstream languages' syntaxes.

I got spoiled by the CLOS separation of OO concepts, and realized that most of the time, all I need is structs and some dispatch.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
3rdtry
Posts: 152
Joined: Sat Feb 16, 2013 1:46 pm UTC

Re: Fleeting Thoughts (CS Edition)

Postby 3rdtry » Mon Feb 18, 2013 7:17 pm UTC

I tend to obsess myself with things that seem too complex or arbitrary, trying to find "clean, nice" ways to organize things, even if there actually aren't.
For example, workspaces, windows and tabs are all basically three levels of the same thing. But two are handled by the OS and one by the application, and they are all different in some aspects. Trying to unify them would probably be counter productive. Same with hard disks, SSDs, RAM and processor cache.

(SSDs are also interesting in that they break the abstraction that memory is just "a long array of bytes". That's why we need TRIM, for example)

No, there's no point here, it's just a fleeting thought.

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby ahammel » Wed Feb 20, 2013 12:10 am UTC

Xanthir wrote:It doesn't help that what most people actually mean by inheritance most of the time is captured best by mixins, which aren't implemented in most mainstream languages' syntaxes.
Hooray for Ruby?

I've found doing OOP stuff much more fun in Ruby than Python, both because of mixins and for other reasons. But perhaps that's a coding fleeting thought.
He/Him/His/Alex
God damn these electric sex pants!

User avatar
Negrebskoh
Posts: 139
Joined: Fri Mar 01, 2013 11:49 pm UTC
Location: The Netherlands

Re: Fleeting Thoughts (CS Edition)

Postby Negrebskoh » Sat Mar 02, 2013 12:05 am UTC

troyp wrote:It's hard to imagine stuff like jumps/loops and conditionals being difficult, they're too basic.


And then you get program correctness and Hoare triples. Those are awesome, but... well, difficult.

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Fleeting Thoughts (CS Edition)

Postby troyp » Sat Mar 02, 2013 12:56 pm UTC

Well, I'd say the concept of a natural number is basic as well. I wouldn't mean to imply all of number theory is trivial...

User avatar
Negrebskoh
Posts: 139
Joined: Fri Mar 01, 2013 11:49 pm UTC
Location: The Netherlands

Re: Fleeting Thoughts (CS Edition)

Postby Negrebskoh » Sat Mar 02, 2013 4:04 pm UTC

troyp wrote:Well, I'd say the concept of a natural number is basic as well. I wouldn't mean to imply all of number theory is trivial...


Wasn't disagreeing or criticizing. :) But I'm taking a course in program correctness right now, so that was my fleeting CS thought, and it seemed to fit the quote.

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Fleeting Thoughts (CS Edition)

Postby troyp » Sun Mar 03, 2013 5:06 am UTC

Negrebskoh wrote:Wasn't disagreeing or criticizing. :) But I'm taking a course in program correctness right now, so that was my fleeting CS thought, and it seemed to fit the quote.

Oh, right...sorry. (I thought you were saying loops and conditionals weren't basic.)

FT:
Apparently delimited continuations can be used to implement dynamic scoping, which is...interesting. Now I'm wondering whether regular continuations can do the same. It doesn't seem possible to me that they could, but I don't have a deep understanding of (reified) continuations. I mainly just think of them as an awkward special form you have to stuff around with if you want exotic flow control in Scheme.

I know almost nothing about delimited continuations, unfortunately. I read a paper on them quite a while ago, but I've forgotten it. All I remember is they seemed nicer than undelimited continuations. And strictly more powerful - which I suspect is the key to how they can implement dynamic scoping.

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Fleeting Thoughts (CS Edition)

Postby headprogrammingczar » Sun Mar 03, 2013 1:09 pm UTC

Here's your almost-uselessly-quick introduction to delimited continuations, courtesy of #haskell:

Code: Select all

19:38 < dolio> I think one of the nicest forms of delimited continuations is reset = flip runCont id ; shift = Cont.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Fleeting Thoughts (CS Edition)

Postby Breakfast » Mon Apr 01, 2013 8:33 pm UTC

I'm not a functional programmer (ha...) so I'm trusting you guys to tell me if this is a typical solution in functional languages. The idea is to use currying, closures and continuation passing style (CPS) to build actions that could be combined to create and manage workflows.

Here's a small example in C#:

Code: Select all

using System;

namespace FunctionalExample
{
    class Program
    {
        static void Main(string[] args)
        {
            Action<string> _display = Curry(Display)(s => Console.WriteLine(s));

            _display("Hello World!");

            Console.ReadKey();
        }

        private static void Display(Action<string> a, string s)
        {
            a(s);
        }

        private static Func<Action<string>, Action<string>> Curry(Action<Action<string>, string> function)
        {
            return a => b => function(a, b);
        }
    }
}

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Fleeting Thoughts (CS Edition)

Postby troyp » Wed Oct 02, 2013 1:29 pm UTC

I've noticed my launcher program (Kupfer) gives some odd results. eg.

Code: Select all

e  -> emelFM2
em -> emacs

You'd expect that when the second letter agrees with both words, it would not change the original decision. That would be the case if you had a list of (perhaps frecency-ordered) apps and you progressively filtered it for instance.

The other oddity is simply the choices. I haven't used emelFM2 in forever, and I use emacs constantly. I usually have one emacs session going continuously, whereas I may open file managers a little more often, so I guess at one point I could have used emelFM2 more. But if anything, that suggests the algorithm is forever biased by its early observations.

I'm trying to remember the behaviour of other launchers I've used, but it's been a while and I never paid much attention. Does anyone know what kind of algorithm these launchers use? How well does your launcher predict your choices? I might look up the kupfer source later, but I'm curious about launchers in general, now. I'd just figured they use a simple frecency algorithm (or something approximating it if it's too much trouble to update the exact frecency), but maybe not.

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby ahammel » Wed Oct 02, 2013 2:24 pm UTC

troyp wrote:Does anyone know what kind of algorithm these launchers use? How well does your launcher predict your choices?
I'm 90% sure dmenu just uses alphabetical (perfect match) followed by alphabetical (fuzzy match):

Code: Select all

[null] -> [
v      -> v412-compliance
vi     -> vi
vit    -> dvitodvi
Works well enough for me.
He/Him/His/Alex
God damn these electric sex pants!

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Fleeting Thoughts (CS Edition)

Postby troyp » Wed Oct 02, 2013 5:01 pm UTC

ahammel wrote:I'm 90% sure dmenu just uses alphabetical (perfect match) followed by alphabetical (fuzzy match):

Code: Select all

[null] -> [
v      -> v412-compliance
vi     -> vi
vit    -> dvitodvi

Do you mean substring matching? Fuzzy matching would be more along the lines of:

Code: Select all

dvidvi  ->  dvitodvi
(I'm sure I've seen that with launchers, but I'm not sure which ones. Synapse and/or Do, maybe? I don't think dmenu does it, though.)

Actually substring matching could explain the emelFM2 result in that it matches "e" twice, whereas emacs only matches once. But that doesn't explain the other example I've noticed:

Code: Select all

ka  -> KAlarm
kal -> KAlgebra


Works well enough for me.

There is that. By far the main thing with a launcher is having it aware of all your programs (and whatever else you want to launch with it). The order of matches is secondary since it doesn't take long to type an unambiguous substring anyway.

Still, it would be nice if launchers were more adaptive. It would let them be used more as an alternative to keybindings (rather than just an alternative to menus or file managers). Your most common programs, or programs you've been using very recently, would be available in 3 keystrokes. And it would be more worthwhile to use for program switching.

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby Xanthir » Thu Oct 03, 2013 2:28 am UTC

The url input in browsers is an analog of a launcher, and it's adaptive in precisely the way you note. A ton of work goes into them. I'm only vaguely familiar with Chrome's, but it definitely involves historical usage data with a decay over time (visit something a lot, it'll come up for shorter substrings, but ignore it for long enough and it'll move down again), along with some heuristics built from real-world data about what kinds of urls people prefer to have returned. For example, I think it's much less likely to return a url where the match is in the query parameters than a url where the match is in the domain.

My personal website continually vacillates between my recipe app and my password generator, and will trigger different ones from different amounts of the url, as I type a random number of characters each time.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby ahammel » Thu Oct 03, 2013 2:47 am UTC

troyp wrote:Do you mean substring matching? Fuzzy matching would be more along the lines of:

Code: Select all

dvidvi  ->  dvitodvi
(I'm sure I've seen that with launchers, but I'm not sure which ones. Synapse and/or Do, maybe? I don't think dmenu does it, though.)
As it turns out, I mean substring matching. Also: I have a 'dvidvi' command.

dmenu isn't smart enough to use for switching, but I use a tiling window manager, so that's usually taken care of in two keystrokes. Sometimes three if I've got a lot of stuff open.
He/Him/His/Alex
God damn these electric sex pants!

speising
Posts: 2078
Joined: Mon Sep 03, 2012 4:54 pm UTC
Location: wien

Re: Fleeting Thoughts (CS Edition)

Postby speising » Thu Oct 03, 2013 3:45 pm UTC

the big problem i have with those heuristic matching algorithms is that i can never rely blindly on the behaviour. if i type "ab<enter>" today, i want it to start the same thing as it did yesterday, without having to look and check first.

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Fleeting Thoughts (CS Edition)

Postby troyp » Fri Oct 04, 2013 12:02 pm UTC

ahammel wrote:dmenu isn't smart enough to use for switching, but I use a tiling window manager, so that's usually taken care of in two keystrokes. Sometimes three if I've got a lot of stuff open.

I use a tiling manager too (although I use floating windows as much as tiling). But I often have a lot of programs running, on a bunch of different tags. Programs minimized, maximized, everywhere. For my main programs, it's usually just switching to a standard tag and then maybe switching focus, but for others it may take a moment to remember where it is, so a unified switching tool is attractive. Also, with a good launcher, you could afford to give it prime keybinding real estate. Maybe even take Ctrl-space off emacs. (Or Alt-space, which I don't use at the moment, since I have no window menu). That gives it an advantage over a direct keybinding which is probably more awkward (like a super key combination).

speising wrote:the big problem i have with those heuristic matching algorithms is that i can never rely blindly on the behaviour. if i type "ab<enter>" today, i want it to start the same thing as it did yesterday, without having to look and check first.

Yeah, that's an issue. A big graphical launcher with the app's icon helps, but you couldn't quite use it on autopilot like with a hotkey. You could have a way to "lock in" a string->app pairing, but that's detracting from the value of a frecency algorithm.

(If you don't want it adaptive at all, though, there's probably some launcher or launcher plugin that works that way. If not, you could whip up something using a list of apps from /usr/share/applications and dmenu or zenity.)

speising
Posts: 2078
Joined: Mon Sep 03, 2012 4:54 pm UTC
Location: wien

Re: Fleeting Thoughts (CS Edition)

Postby speising » Fri Oct 04, 2013 12:06 pm UTC

troyp wrote:(If you don't want it adaptive at all, though, there's probably some launcher or launcher plugin that works that way. If not, you could whip up something using a list of apps from /usr/share/applications and dmenu or zenity.)


ahem. that won't help me on win 7 i'm afraid.

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby ahammel » Fri Oct 04, 2013 1:36 pm UTC

speising wrote:ahem. that won't help me on win 7 i'm afraid.

Nothing will help you on Windows 7.
He/Him/His/Alex
God damn these electric sex pants!

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Fleeting Thoughts (CS Edition)

Postby Breakfast » Fri Oct 04, 2013 1:55 pm UTC

I'm working on a progress bar and want to get people's opinions on ways to "measure" progress.

    - Given a non-binary tree like data structure would it be good to measure progress with numberOfNodesCompleted / totalNumberOfNodes?
    - If nodes could be added during regular workflow would you rather the progress bar set itself back or not move?
    - If you could measure beforehand (given existing data) how many nodes are likely to be added, would you accept degrees of fuzziness in your progress bars?
    - Would this even be a good measure if nodes didn't conform to an average size? (for example, several large nodes that take significantly longer to complete but would still count the same as shorter nodes as far as "progress" is concerned)
    - If data was collected on the average times taken to fill out nodes would this provide a better measure of "progress?"

Those have just been my thoughts so far. If anyone has more or better ideas it would be greatly appreciated!

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Fleeting Thoughts (CS Edition)

Postby troyp » Fri Oct 04, 2013 3:32 pm UTC

Breakfast wrote:I'm working on a progress bar and want to get people's opinions on ways to "measure" progress.

I think for a lot of this, the answers depend on the exact application. What operation is being measured? What other information is being passed to the user? Is the progress bar attempting to impart real information or does it largely serve a psychological purpose? etc... But I'll try to answer as best I can in the abstract case.
  • Given a non-binary tree like data structure would it be good to measure progress with numberOfNodesCompleted / totalNumberOfNodes?
<snip>
  • Would this even be a good measure if nodes didn't conform to an average size? (for example, several large nodes that take significantly longer to complete but would still count the same as shorter nodes as far as "progress" is concerned)
  • If data was collected on the average times taken to fill out nodes would this provide a better measure of "progress?"

Ideally, the progress bar would measure fraction of total work completed (where work is proportional to time taken for a given level of resource usage). Of course, this may be expensive or impossible to measure in advance. Still, whatever measure is used (eg. fraction of nodes), it should at least roughly correlate with time taken.

Other factors to consider: does a node correspond to some unit of progress meaningful to the user? Does the program also display the current node being processed? If so, tying the progress bar to nodes may feel more consistent than using another measure (although you can always just tie progress bar update times to node completion and make the amount the bar grows vary according to node size).
If nodes could be added during regular workflow would you rather the progress bar set itself back or not move?

Actually, I'm a bit unsure of the scenario...
Are we performing some arbitrary operation (measured by the progress bar) on the "tree" (which may traverse or search the tree), but then inserting nodes in the middle of it?
Spoiler:
Yes, the bar should be set back. (Assuming the progress bar has a constant length - otherwise you could expand the "range" of the bar while leaving the "completed" bar the same)

Although the question brings up the issue of whether you should be able to add a node in the middle of the operation. If it's being inserted into an arbitrary position in a tree then it's a race as to whether it gets included in the operation.
Or: Is adding nodes to the tree the very operation we're measuring, and this question is about placing additional nodes in the queue to be inserted?
Spoiler:
In that case, the basic choices are:
(1) shrink the progress bar when nodes are added (or stretch the total bar if appropriate).
(2) complete the progress bar normally, then start another progress bar for the additional nodes added.
(2b) as (2), but bring up the second bar immediately

As a user, I think (1) offers a bit more peace of mind, since you can be confident the program is actually going to handle the operation (rather than having to wait and see if it does the right thing or drops the operations or screws things up somehow...) For the same reason, in the case of (2), I like (2b) where the program completes the added operations first, then closes the additional progress bar and continues with the original operation (obviously, this requires that order of operations is unimportant).

If you could measure beforehand (given existing data) how many nodes are likely to be added, would you accept degrees of fuzziness in your progress bars?

(I don't understand the question)

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Fleeting Thoughts (CS Edition)

Postby Breakfast » Fri Oct 04, 2013 6:38 pm UTC

So I can't give as much detail as I'd like because it's for work and all but the tree is basically analogous to an application process. Each node contains a specific set of data and all of the nodes together encapsulate the entire application.

Ideally, the progress bar would measure fraction of total work completed (where work is proportional to time taken for a given level of resource usage). Of course, this may be expensive or impossible to measure in advance. Still, whatever measure is used (eg. fraction of nodes), it should at least roughly correlate with time taken.

Other factors to consider: does a node correspond to some unit of progress meaningful to the user? Does the program also display the current node being processed? If so, tying the progress bar to nodes may feel more consistent than using another measure (although you can always just tie progress bar update times to node completion and make the amount the bar grows vary according to node size).


Each node has meaning to the user as do sets of nodes. This means we could measure progress as nodes vs. total nodes or data points vs total data points. Currently the thinking is to have a segmented progress bar where each segment refers to a predefined set of nodes. Each segment will be filled in based on an all-or-nothing approach to avoid the fact that nodes can be added or removed from the tree. We also have data about how long each of these segments should take to complete so the segments can be visually proportioned to suggest which might be longer / shorter.

If you could measure beforehand (given existing data) how many nodes are likely to be added, would you accept degrees of fuzziness in your progress bars?

(I don't understand the question)


I'm sorry I didn't phrase that question very well. Here's another attempt at it. Say a user must enter at least one node of data but may enter as many as they like. We do not know how many a particular user will enter. Given previous user information we see that the average user enters five nodes of data. Would it make sense to scale the progress bar off of this information? It would appear to users who enter less than five nodes that they are progressing more quickly while users that enter more than five willing think they are progressing slower than normal and may even see the progress bar move backwards.

Here's an interesting paper:
http://chrisharrison.net/projects/progressbars/ProgBarHarrison.pdf

EvanED
Posts: 4327
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby EvanED » Fri Oct 04, 2013 7:36 pm UTC

troyp wrote:
Breakfast wrote:I'm working on a progress bar and want to get people's opinions on ways to "measure" progress.

I think for a lot of this, the answers depend on the exact application. What operation is being measured? What other information is being passed to the user? Is the progress bar attempting to impart real information or does it largely serve a psychological purpose?
That's a good question. There are a few things that progress bars are useful for: "is my program actually still doing something" in which case the time remaining isn't so important and you could just do one of those continuously-scrolling bars, "is this going to take one minute and I should just wait for it, five minutes and I should go get a coffee, or thirty minutes and I should find something else productive to do in the interim?" (I would consider that second one a lot closer to "real information" than "psychological purpose", but it can still afford to be somewhat unreliable), etc.

Given a non-binary tree like data structure would it be good to measure progress with numberOfNodesCompleted / totalNumberOfNodes?

Would this even be a good measure if nodes didn't conform to an average size? (for example, several large nodes that take significantly longer to complete but would still count the same as shorter nodes as far as "progress" is concerned)

How big is the disparity, and what's the longest you'd expect to see a node take? For instance, I'd loooooove to have a progress indicator in SCons builds (I'd actually put a bit of money into sponsoring said feature), and the fact that CMake gives you one is something I see as a major advantage to that tool over SCons. That's true despite the facts that (1) some files can take far longer to compile than others (I have worked with a build where there's two orders of magnitude and minutes difference between File1 and File2) and (2) hypothetically nodes can be added throughout the build. And #of files yet to be built would be 90% of my ideal feature.

If data was collected on the average times taken to fill out nodes would this provide a better measure of "progress?"
Could be better. I'm not sure that this is possible in your scenario, but in the context of a build system what I think would be really awesome is if it stored the time it took to build a node from the previous run (and information about any new nodes that it spawned) and used that for the estimate. But I'm not sure that keeping around that state would be worth it. (Though it could theoretically lead to actually faster builds via smarter scheduling, so maybe it would be useful enough.)

If nodes could be added during regular workflow would you rather the progress bar set itself back or not move?
I would set it back.

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Fleeting Thoughts (CS Edition)

Postby troyp » Sat Oct 05, 2013 2:03 pm UTC

Breakfast wrote:So I can't give as much detail as I'd like because it's for work and all but the tree is basically analogous to an application process. Each node contains a specific set of data and all of the nodes together encapsulate the entire application.

Oh, I see. So then it wouldn't make sense to have a second progress bar pop up (either sequentially or concurrently), anyway? Then I'd definitely set back the progress bar if nodes are added.

Each node has meaning to the user as do sets of nodes. This means we could measure progress as nodes vs. total nodes or data points vs total data points. Currently the thinking is to have a segmented progress bar where each segment refers to a predefined set of nodes. Each segment will be filled in based on an all-or-nothing approach to avoid the fact that nodes can be added or removed from the tree. We also have data about how long each of these segments should take to complete so the segments can be visually proportioned to suggest which might be longer / shorter.

That sounds like a good idea. So the sequence of "sets of nodes" is fixed, but nodes may be added within a set, is that accurate? In that case, rather than setting back the bar, you could increase the length of the segment for the set that node was added to (although if you have the progress bar scaled to a constant final length, you'll end up shrinking the bar anyway).

I'm sorry I didn't phrase that question very well. Here's another attempt at it. Say a user must enter at least one node of data but may enter as many as they like. We do not know how many a particular user will enter. Given previous user information we see that the average user enters five nodes of data. Would it make sense to scale the progress bar off of this information? It would appear to users who enter less than five nodes that they are progressing more quickly while users that enter more than five willing think they are progressing slower than normal and may even see the progress bar move backwards.

(note: I'm not completely clear on the context here, and what the alternative would be)

If it's just a factor of 5 or so variation, I think the progress bar would still be useful. Of course, the more accurate the better.

Is the idea here that you would use this average data to size the segments that make up the empty bar? If so, that would make sense, although I'd rather have the size adjust once the data is entered.

If the application is going to progress through certain "phases" whose number and order but not length are known in advance, one option would be to have a "two-scale" progress bar. The overall bar would just have small equally-sized segments or "indicators" that light up as the phases complete*, but for the current phase you have a detailed "progress bar" based upon the amount of nodes/data points the user has added. It could be styled as (a) a "progress bar within a progress bar", where the global progress bar accordians out to show the local bar; or (b) two separate widgets, a set of progress indicators plus the bar for the current phase. (I'm not sure if that's applicable.)
* I guess if showing the expected relative lengths of the phases is important, you could have the global indicator be a proportioned bar. Eg. you could have a small progress bar above partitioned into phases (showing their average relative lengths), where the completed phases are green, the current phase yellow and the unstarted phases red. Then below, a larger, continuously growing progress bar (maybe yellow on black to match the current segment above) showing the progress of the current stage (according to the amount of nodes/data actually added).

User avatar
Copper Bezel
Posts: 2416
Joined: Wed Oct 12, 2011 6:35 am UTC
Location: Web exclusive!

Re: Fleeting Thoughts (CS Edition)

Postby Copper Bezel » Sat Oct 05, 2013 8:59 pm UTC

EvanED wrote:There are a few things that progress bars are useful for: "is my program actually still doing something" in which case the time remaining isn't so important and you could just do one of those continuously-scrolling bars, "is this going to take one minute and I should just wait for it, five minutes and I should go get a coffee, or thirty minutes and I should find something else productive to do in the interim?" (I would consider that second one a lot closer to "real information" than "psychological purpose", but it can still afford to be somewhat unreliable), etc.

In the general case, I find continuously scrolling progress bars to not be even psychologically sufficient, particularly if the task is complex. A continuously scrolling progress bar can hide the fact that the process is looping on some step where it's encountered an error, or that some step in the process is simply going to take an extraordinary amount of time for unusual reasons. I much prefer when there's some kind of brief console output available (so that if it's spending five minutes fetching tag information for songYouDidntEvenKnowYouHad.unsupportedFiletype, I know.)
So much depends upon a red wheel barrow (>= XXII) but it is not going to be installed.

she / her / her

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Fleeting Thoughts (CS Edition)

Postby troyp » Sun Oct 06, 2013 8:04 am UTC

Continuously scrolling as in "fills up, then empties and starts again"? Those bars are usually a console version of an hourglass or "whirligig" widget. I agree they don't give any psychological reassurance of progress. They're more to let you know the action has started (which is a useful function in itself).

I also find some kind of brief progress details (maybe in a drop-down section) really helpful.

EvanED
Posts: 4327
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby EvanED » Sun Oct 06, 2013 3:41 pm UTC

troyp wrote:Continuously scrolling as in "fills up, then empties and starts again"?
No, those are awful because they look like actual progress bars. I'm talking about something like what most versions of Windows show when booting, where there's a progress-bar looking thing but something just moves across it. (Windows 7, or maybe Vista, dropped that for another animation to show it's working.) I think on Apple I've seen a filled progress bar with moving stripes, as another example.

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Fleeting Thoughts (CS Edition)

Postby Breakfast » Mon Oct 07, 2013 12:08 pm UTC

troyp wrote:That sounds like a good idea. So the sequence of "sets of nodes" is fixed, but nodes may be added within a set, is that accurate? In that case, rather than setting back the bar, you could increase the length of the segment for the set that node was added to (although if you have the progress bar scaled to a constant final length, you'll end up shrinking the bar anyway).

That's right. Set's of nodes are fixed but nodes may be added to sets. So it might be beneficial to have each segment of the progress bar represent a set of nodes and potentially have more granular progress bars that represent the nodes in each set.

troyp wrote:(note: I'm not completely clear on the context here, and what the alternative would be)

If it's just a factor of 5 or so variation, I think the progress bar would still be useful. Of course, the more accurate the better.

Is the idea here that you would use this average data to size the segments that make up the empty bar? If so, that would make sense, although I'd rather have the size adjust once the data is entered.

Right again. We would be trying to size the segments in such a way that the user could estimate relatively how long a segment would take to fill out compared to the other segments. Sizing them based off of data was one idea and the other was sizing them based off of average times for filling out nodes / segments.

troyp wrote:If the application is going to progress through certain "phases" whose number and order but not length are known in advance, one option would be to have a "two-scale" progress bar. The overall bar would just have small equally-sized segments or "indicators" that light up as the phases complete*, but for the current phase you have a detailed "progress bar" based upon the amount of nodes/data points the user has added. It could be styled as (a) a "progress bar within a progress bar", where the global progress bar accordians out to show the local bar; or (b) two separate widgets, a set of progress indicators plus the bar for the current phase. (I'm not sure if that's applicable.)
* I guess if showing the expected relative lengths of the phases is important, you could have the global indicator be a proportioned bar. Eg. you could have a small progress bar above partitioned into phases (showing their average relative lengths), where the completed phases are green, the current phase yellow and the unstarted phases red. Then below, a larger, continuously growing progress bar (maybe yellow on black to match the current segment above) showing the progress of the current stage (according to the amount of nodes/data actually added).

And third time's a charm... Assuming I'm interpreting all of this correctly, it's almost exactly what we were planning before I posed my question here. Each segment of the progress bar would indicate no progress / segment started / segment complete. Segments that have significant numbers of nodes or that take a large amount of time would a smaller version of the large progress bar so that the user would still have a sense that they are making progress.

Copper Bezel wrote:
EvanED wrote:There are a few things that progress bars are useful for: "is my program actually still doing something" in which case the time remaining isn't so important and you could just do one of those continuously-scrolling bars, "is this going to take one minute and I should just wait for it, five minutes and I should go get a coffee, or thirty minutes and I should find something else productive to do in the interim?" (I would consider that second one a lot closer to "real information" than "psychological purpose", but it can still afford to be somewhat unreliable), etc.

In the general case, I find continuously scrolling progress bars to not be even psychologically sufficient, particularly if the task is complex. A continuously scrolling progress bar can hide the fact that the process is looping on some step where it's encountered an error, or that some step in the process is simply going to take an extraordinary amount of time for unusual reasons. I much prefer when there's some kind of brief console output available (so that if it's spending five minutes fetching tag information for songYouDidntEvenKnowYouHad.unsupportedFiletype, I know.)

I'm going to agree with Copper Bezel here if only with regards to the application I'm working on and the types of users we're expecting. A continuously scrolling progress bar could potentially be very discouraging and might deter many people from completing the process.

User avatar
PM 2Ring
Posts: 3620
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Fleeting Thoughts (CS Edition)

Postby PM 2Ring » Tue Oct 08, 2013 7:50 am UTC

Why not use a small image of the tree itself to indicate progress, using something like the Graphviz libraries? I guess it would be a bit of a CPU drain, but the "progress tree" doesn't need to have the full depth of the actual tree: details beyond a certain depth could be represented as a single node.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 3 guests