Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

Control Flow

2 (2.2%)

Arrays, Strings, Pointers, and References

8 (9%)

Functions

4 (4.5%)

Basic object-oriented programming

30 (33.7%)

A bit more advanced OOP (Composition, Operator overloading, Inheritance, Virtual Functions)

18 (20.2%)

Templates

8 (9%)

Other (Explain)

4 (4.5%)

Working with files?  (Streams)

15 (16.9%)

Total Members Voted: 89

[Siquo]

Your fill is going to check every pixel 4 times. Once it works, you might want to look at that. Or not, if it's already fast enough to your tastes

[ILikePie]

The fill works, and I don't really care how fast it does at the moment. If its starts getting really slow with bigger images I might have it work like this, but it looks to complex to implement, at least for a lazy guy like me.

[Supermikhail]

Oh, recursive functions are very useful, not using them is missing out on a lot. Is some cases you can do the same with a loop, but for things like that flood fill, a loop can't do much.

Yeah, after looking at that Wikipedia article I can see how it works. But I wouldn't be able to make up something like that myself. That's some high level thinking I must say.

About optimization, which would run faster, this:

Code: [Select]

int i = 0;
for ( ; i < 10; i++) {
blah
}
or this:

Code: [Select]

int i = 0;
while (i++ < 10) {
blah
}
A quick google  search yielded no results, is that because they work the same speed wise?

I thought that they are considered synonyms, except that look at ex.3 here. Although somebody correct me. Also, what are the priorities between the "++" and the "<" operators? Does it work as intended in the while loop? My asking this is a hint that it would be clearer to go with a for loop.

[Siquo]

Generally ++i is faster than i++, since i++ needs to create a copy to return. But only by such a small margin that it's usually not worth the bother, and especially not for built-in types such as int. Otherwise they look much the same.

Except... i++ is processed after <, I think, so

Code: [Select]

int i = 0;
while (i++ < 10) {
blah
}might run 11 times instead of ten. But it's monday morning and too early for me to tell, and I can't try it out at the moment.

Correction fake edit: No, it will run 10 times, but from 1-10 and not 0-9, as i is upped before the loop, as while is evaluated before the loop. Solution is to ++i inside the loop and not in the while.
The excercise no 3b from supermikhael fails, but for a different reason.

[ILikePie]

I thought that they are considered synonyms, except that look at ex.3 here. Although somebody correct me. Also, what are the priorities between the "++" and the "<" operators? Does it work as intended in the while loop? My asking this is a hint that it would be clearer to go with a for loop.

It does, x++ < y checks if x is smaller than y and then increments x, ++x < y is the exact opposite, incrementing x and then comparing the two. I guess for the sake of clarity I could with a for loop, unless whiles are magically faster.

Fake edit: beaten by siquo, I'm still pretty sure i++ checks first, increments later though.

[Siquo]

It does increment after the check, but before the statements in the loop. If you use i in the loop, it'll show counting from 1-10.

I think

[Supermikhail]

That's also why I thought it counter-intuitive but didn't write it. It would seem that the reason for initializing i before a for loop would be for it to tell the user how many times it's looped (assuming there is a "break;" somewhere inside), but then in the while loop it does this stuff. And I thought wouldn't it be easier to initialize it to 1 in the first place?

[ILikePie]

you could have int i = -1; while(loop) {}, but it looks ugly, and no one likes ugly.

I get a floating point exception, SIGFPE or whatever you call it. I fire up gdb to see what it means, it tells me it a SIGFPE error, and gives me this: 0x08048b97. I'm guessing it refers to a line, is there anyway to make that string human readable?

[Siquo]

SIGFPE could be a number of things, including (and it usually is) division by zero.

[qwertyuiopas]

Oh, recursive functions are very useful, not using them is missing out on a lot. Is some cases you can do the same with a loop, but for things like that flood fill, a loop can't do much.


About optimization, which would run faster, this:

Code: [Select]

int i = 0;
for ( ; i < 10; i++) {
blah
}
or this:

Code: [Select]

int i = 0;
while (i++ < 10) {
blah
}
A quick google  search yielded no results, is that because they work the same speed wise?

Both of those should be practically identical. Also, in either case, if optimization is enabled, the compiler will find a way to make it better.

When it comes to optimization, eliminating a realloc or a sprintf will be far more important than a minimal change to a loop that could easily be optimized by the compiler with no loss of readability.

Remember, -O3 is the best optimization, unless the algorithm itself is slow. (-O3 is gcc's "maximum optimization" parameter. Most IDEs and other compilers will have a setting with equivalent effect, but it probably will not be "-O3". Find the one for your compiler/IDE and use it if you need speed rather than obfuscate your loops to gain a 1% increase.)

[Blacken]

Oh, recursive functions are very useful, not using them is missing out on a lot. Is some cases you can do the same with a loop, but for things like that flood fill, a loop can't do much.

What? There is precisely nothing that can be done recursively that cannot be done in an iterative manner. Generally speaking, in languages that don't implement tail recursion or do so poorly (Java and .NET don't do so by default), a recursive solution is going to be slower by as much as an order of magnitude and a recursive solution will require O(n) memory, where n is the number of stack frames used. Scheme and other languages that effectively implement tail recursion will not have the same problem, but then you have to actually be writing your code in those languages.

Recursion is a conceit for the programmer and truly useful in only a relatively small subset of tasks. Programmers who think they understand recursion tend to overuse it, in large part because they do not actually understand it.

The fill works, and I don't really care how fast it does at the moment. If its starts getting really slow with bigger images I might have it work like this, but it looks to complex to implement, at least for a lazy guy like me.

You certainly should care, because it's wrong and a concern for both security and stability. What happens when you attempt to recursively flood-fill a massive image space? Your program is going to smash the stack.

Generally ++i is faster than i++, since i++ needs to create a copy to return. But only by such a small margin that it's usually not worth the bother, and especially not for built-in types such as int. Otherwise they look much the same.

This is not really correct--it's implementation-specific exactly what sort of performance result this will engender. Any modern compiler --either Intel, Microsoft, or GCC--should optimize it such that the increment instruction is performed after the evaluation of the expression. If there is no expression, then there will only be an increment operation.

Where it does matter is in evaluative expressions (especially those that involve functions)--and should probably be avoided in such statements anyway due to problems with legibility and determinism (especially re: multithreaded applications).

[ILikePie]

Why do I get the feeling most of you think I'm a moron?

You certainly should care, because it's wrong and a concern for both security and stability. What happens when you attempt to recursively flood-fill a massive image space? Your program is going to smash the stack.

How would you write a function that fills in any space at any size, without using recursion? Just a loop wouldn't do, because it won't fill the whole space. Yes, there are definitely better ways of doing what I tried to do, but you will always end up using recursion somewhere.

[Siquo]

[trolling removed]

My solution (semipseudocode):

Code: [Select]

bool changed = true
x = startingpointx, y = startingpointy
minx = newminx = x-1, maxx = newmaxx = x+1, miny = newminy = y-1, maxy = newmaxy = y+1
While(changed){
  changed=false
// loop over the area neighbours
  for(i=minx;i<maxx;i++){
    for(j=miny;i<maxy;y++{
      if(isValidPixelLocation(i,j)){
        if(shouldFill(i,j)){
         doFill(i,j);
         changed=true
         if(i==maxx){newmaxx=maxx+1}
         if(i==minx){newminx=minx-1}
         if(j==maxy){newmaxy=maxy+1}
         if(j==miny){newminy=miny-1}
      }
    }
  }
// Enlarge search-area
  maxx = newmaxx
  maxy = newmaxy
  minx = newminy
  miny = newminy
}
Explanation: from the starting pixel, make a square that surrounds it and check it's pixels (you start with a 3x3 square).
If any of em changed, enlarge the area to include that one.
Then repeat with that larger area.

I just realised this doesn't work, unless you make in the shouldFill(x,y) function a check that checks if one of it's neighbours was recently filled, and check that you don't "refill" an already filled pixel, but I spent so much time typing it I won't remove it, and I'll leave that as an exercise

Another (even better) way would be to keep a list of recently changed pixels (starting with your startingpixel), loop over that list, "Fill" those pixels, and making a new list with all neighbours of all those pixels that should be changed. Repeat for the new list. Why is it more efficient than recursion? Because every single recursion is kept in memory, and now you discard your old list with every loop.

Yes I'm making this up as I go along

[ILikePie]

Hmm, that sounds interesting, you could search for some pixels around the origin fill them in, and enlarge the search area until you reach a border. But then there's the part where the search area goes beyond the border...


The scanline fill still looks superior to me though.

[Siquo]

Hmm, that sounds interesting, you could search for some pixels around the origin fill them in, and enlarge the search area until you reach a border. But then there's the part where the search area goes beyond the border...

Exactly, that's why you still need a list for "recently changed pixels", in which case the second solution, working just with lists, is better.
Something like

Code: [Select]

std::list<std::pair<int,int> >* list= 0    // list to loop. Some people prefer null, as 0 is C and not C++ or something, it's not discussion-worthy
std::list<std::pair<int,int> >* newList = new std::list<std::pair<int,int> >;   // list containing the "new" pixels
newList->push_back(std::pair<int,int> (x,y)); // fill the new list with the first pixel

while(newList && newList->size() > 0){  // loop as long as we have pixels in our new list
  // delete the old list
  delete list;
  list = newList
  //make new list
  newList = new std::list<std::pair<int,int> >;
  //loop list
  for(std::list<std::pair<int,int> >::iterator i = list->begin(); i < list->end(); i++){
    for (x loop over neighbourpixels, 4 times or eight times, depending on whehter you want to fill diagonally){
     for (y){
      if(validPixel(x,y)){  // check if we're still in bounds of the image
       if(shouldFill(x,y)) { // checks if the existing color is the "fill" color
         Fill(x,y)  // Fill the pixel
         newList->push_back(std::pair<int,int> (x, y));  // and put it in our list for the next iteration
       }
     }
   }
  }
}
delete list;
delete newList;
Here I use the std::pair<int,int>  for pixel location, but you can use any class containing an x and y, of course. Using pointers means the list doesn't have to be copied every time, but you need to take care to either delete all superfluous lists, or maybe clear them and reuse them. Pair members are accessed by pair.first and pair.second. Be careful with nested templateclasses: a space is necessary between all > >, or it will see it as operator >>. The iterator i in the loop is a pointer to the pair, so you'd get i->first and i->second for your x and y.

validPixel(), Fill(), and shouldFill() should need to have the image object passed to them as well, it should not be "global".

Or something like that

[trolling removed]