Computer Science Canada :: View topic - Flood fill algorithm without recursion?

Computer Science Canada

Flood fill algorithm without recursion?

Author:

tyuo9980 [ Fri Dec 30, 2011 3:10 pm ]

Post subject:

Flood fill algorithm without recursion?

I need to use a flood fill for my program but java limits my stack calls.

How would I be able to implement a floodfill without using recursion or queues?

The reason why i cant use queues is that im using ready to program ide and it only has up to java v1.4 libraries.

code:

public static void calcArea (int x, int y)
{
boolean boundary = false;

for (int i = 1 ; i <= walls ; i++)
{
if (x == wallx1 [i] && x == wallx2 [i] && y > wally1[i] && y < wally2[i]) //vertical
   {
boundary = true;
   }
   else if (y == wally1 [i] && y == wally2 [i] && x > wallx1[i] && x < wallx2[i]) //horizontal
   {
boundary = true;
   }
}

if (!CArea [x] [y] && !boundary)
{
if (x > 9 && x < 431 && y > 79 && y < 551)
{
CArea [x] [y] = true;
calcArea (x + 1, y);
calcArea (x - 1, y);
calcArea (x, y + 1);
calcArea (x, y - 1);
}
}

return;
}

Author:	Tony [ Fri Dec 30, 2011 3:30 pm ]
Post subject:	Re: Flood fill algorithm without recursion?
tyuo9980 @ Fri Dec 30, 2011 3:10 pm wrote: I need to use a flood fill for my program but java limits my stack calls. More likely you're limited by the memory available to the OS than the language of choice. In specific, you likely just have an infinite loop somewhere.

Author:	tyuo9980 [ Fri Dec 30, 2011 3:36 pm ]
Post subject:	Re: Flood fill algorithm without recursion?
im 100% sure its java. i increase the stack available in eclipse and it works.

Author:	Tony [ Fri Dec 30, 2011 4:02 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
There's BFS, but that uses a queue -- what's the problem with those?

Author:	tyuo9980 [ Fri Dec 30, 2011 4:10 pm ]
Post subject:	Re: Flood fill algorithm without recursion?
queues came in java 1.5 i think. ready to program uses 1.4.2 so no go

Author:	Tony [ Fri Dec 30, 2011 4:13 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
You can implement a queue with an array. Java 4 has arrays, doesn't it?

Author:	tyuo9980 [ Fri Dec 30, 2011 4:22 pm ]
Post subject:	Re: Flood fill algorithm without recursion?
how would i use an array to queue?

Author:	Tony [ Fri Dec 30, 2011 10:37 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
array is just a datastore. You can also keep data in a linked list, file on disk, or somewhere in the cloud. It doesn't really matter, as you're supposed to put in an API layer in between. That is, implement the interface of Queue<E>. With arrays -- item goes into the queue == item gets added to the end of the array. Item leaves the queue == item gets removed from the front of the array.

Author:	mirhagk [ Sat Dec 31, 2011 12:10 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
The recursive algorithm seems like it will call itself infinite times. For instance the first call with then call one with the node to the left, which will then call it with the node to the right (ie the starting node) and it will go back and forth forever. You need some way of figuring out if you've calculated that square before.

Author:	Tony [ Sat Dec 31, 2011 2:29 pm ]
Post subject:	Re: Flood fill algorithm without recursion?
Tony @ Fri Dec 30, 2011 3:30 pm wrote: In specific, you likely just have an infinite loop somewhere.

Author:	mirhagk [ Sat Dec 31, 2011 7:15 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
Yeah I know that you mentioned it tony, but it was obvious that he didn't see it, and he'd be going about implementing some queueing algorithms only to end up with the same problem.

Author:	tyuo9980 [ Sat Dec 31, 2011 10:03 pm ]
Post subject:	Re: Flood fill algorithm without recursion?
there is no infinite loop. the function works very well. if (!CArea [x] [y] && !boundary) { CArea [x] [y] = true; .... this is where i see if the square has been checked already. if an area is checked it will be set to true. this is a video of my function: http://www.youtube.com/watch?v=mQPbzsALF0M

Author:	mirhagk [ Sun Jan 01, 2012 12:04 am ]
Post subject:	RE:Flood fill algorithm without recursion?
Okay, well then there is no reason why it wouldn't work, as the call stack for java is larger then how large your thing.

Author:	tyuo9980 [ Sun Jan 01, 2012 12:08 am ]
Post subject:	Re: Flood fill algorithm without recursion?
how large exactly is java's stack size? Because this flood fill will reach a maximum of 197400 stacks which is ~5.3mb of space. How would I be able to reduce the usage?

Author:	Tony [ Sun Jan 01, 2012 12:08 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
looking into this further, Java does limit the stack size, as it assumes that multiple threads (each with its own stack) will be running. StackOverflow vs. OutOfMemory... Since you have just a single thread, it could safely crank that limit up to be over 9000, but presumably "Ready To Program" is not cool with JVM flags. You can reduce the stack usage by making less non-terminating method calls. e.g., filling open areas in larger blocks. If you know you've got a chunk of 10x10 available to you, you can fill the inner 9x9 block and terminate, leaving just the outer perimeter to contribute to the stack-size growth. This would grow the stack at 19% of the previous levels (though, of course, require more computation to figure out if such "optimization" moves are even available). Alternatively you could just throw the points onto the heap, and not make recursive calls. Which is basically the Queue approach (just, using any other datastore that's available).

Author:

tyuo9980 [ Mon Jan 02, 2012 7:15 pm ]

Post subject:

Re: Flood fill algorithm without recursion?

i implemented a queue and it eliminated the overflow error, but its SUPER DUPER WHOPPERINGLY slow.

code:

public static void calcArea (int xx, int yy)
{
LinkedList listx = new LinkedList ();
LinkedList listy = new LinkedList ();
int listLength = 1;
int x, y;

listx.add (new Integer (xx));
listy.add (new Integer (yy));

for (int l = 0 ; l < listLength ; l++)
{
x = Integer.parseInt (listx.get (l).toString ());
y = Integer.parseInt (listy.get (l).toString ());

if (!CArea [x] [y])
{
boundary = false;

for (int i = 1 ; i <= walls ; i++)
{
if (x == wallx1 [i] && x == wallx2 [i] && y >= wally1 [i] && y <= wally2 [i]) //vertical
{
boundary = true;
Boundary [x] [y] = true;
}
else if (y == wally1 [i] && y == wally2 [i] && x >= wallx1 [i] && x <= wallx2 [i]) //horizontal
{
boundary = true;
Boundary [x] [y] = true;
}
}

if (!boundary)
{
CArea [x] [y] = true;
area++;

if (!CArea [x + 1] [y])
{
listx.add (new Integer (x + 1));
listy.add (new Integer (y));
listLength++;
}

if (!CArea [x - 1] [y])
{
listx.add (new Integer (x - 1));
listy.add (new Integer (y));
listLength++;
}

if (!CArea [x] [y + 1])
{
listx.add (new Integer (x));
listy.add (new Integer (y + 1));
listLength++;
}

if (!CArea [x] [y - 1])
{
listx.add (new Integer (x));
listy.add (new Integer (y - 1));
listLength++;
}
}
}
}
}

Author:	mirhagk [ Mon Jan 02, 2012 7:32 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
Why do you need to parse the integers?

Author:	Tony [ Mon Jan 02, 2012 8:02 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
I would guess that parsing is a workaround for the list being of a generic "Object" type, but that's not really the problem in comparison to: get(int index) is an O(n) operation which is bad bad news, considering that nothing is ever removed from the queue.

Author:	tyuo9980 [ Mon Jan 02, 2012 8:10 pm ]
Post subject:	Re: Flood fill algorithm without recursion?
On opertation? I dont quite get you there. How would removing items from the queue be beneficial? i dont think that i need to remove anything from the queue since it just goes through the list until it ends.

Author:	mirhagk [ Mon Jan 02, 2012 8:15 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
Well tony, recurisively is potentially O(n) as well, basically what it means is that the time and memory grows linearly with the number of pixels inside the area.

Author:	tyuo9980 [ Mon Jan 02, 2012 8:20 pm ]
Post subject:	Re: Flood fill algorithm without recursion?
ahh i see. so if i remove items from the queue it would take less time to grab the values.

Author:	mirhagk [ Mon Jan 02, 2012 8:22 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
No it won't take less time, just less memory

Author:	tyuo9980 [ Mon Jan 02, 2012 8:26 pm ]
Post subject:	Re: Flood fill algorithm without recursion?
memory isnt an issue. how would i make it faster?

Author:	Tony [ Mon Jan 02, 2012 9:16 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
The way a linked list works is that to get 3rd element, you start at element 1 to find out where element 2 is, then follow that to 3rd. This continues linearly, so to get(n) you need to perform ~n operations -- thus it's of the order O(n) -- http://en.wikipedia.org/wiki/Big_O_notation It's a good idea to remove elements, so that you only ever grab stuff from the front, as get(1) is about 1000 times faster than get(1000)

Author:	tyuo9980 [ Mon Jan 02, 2012 9:22 pm ]
Post subject:	Re: Flood fill algorithm without recursion?
thanks. this helps out a lot. i'll get that done in a few minutes and see how it results.

Author:

tyuo9980 [ Mon Jan 02, 2012 9:48 pm ]

Post subject:

Re: Flood fill algorithm without recursion?

its MUCH MUCH faster now. however its still not fast enough. i need something that's almost instant on my computer as the ones at school are pretty slow.

The whole area takes around 285ms to calculate. Are there any other improvements that I can make?

code:

public static void calcArea (int xx, int yy)
{
LinkedList listx = new LinkedList ();
LinkedList listy = new LinkedList ();
int x, y;

listx.add (new Integer (xx));
listy.add (new Integer (yy));

do
{
x = Integer.parseInt (listx.get (0).toString ());
y = Integer.parseInt (listy.get (0).toString ());
listx.remove (0);
listy.remove (0);

if (!CArea [x] [y])
{
boundary = false;

for (int i = 1 ; i <= walls ; i++)
{
if (x == wallx1 [i] && x == wallx2 [i] && y >= wally1 [i] && y <= wally2 [i]) //vertical
{
boundary = true;
Boundary [x] [y] = true;
}
else if (y == wally1 [i] && y == wally2 [i] && x >= wallx1 [i] && x <= wallx2 [i]) //horizontal
{
boundary = true;
Boundary [x] [y] = true;
}
}

if (!boundary)
{
CArea [x] [y] = true;
area++;

if (!CArea [x + 1] [y])
{
listx.add (new Integer (x + 1));
listy.add (new Integer (y));
}

if (!CArea [x - 1] [y])
{
listx.add (new Integer (x - 1));
listy.add (new Integer (y));
}

if (!CArea [x] [y + 1])
{
listx.add (new Integer (x));
listy.add (new Integer (y + 1));
}

if (!CArea [x] [y - 1])
{
listx.add (new Integer (x));
listy.add (new Integer (y - 1));
}
}
}
}
while (listx.size() != 0);
}

Author:

Tony [ Mon Jan 02, 2012 10:15 pm ]

Post subject:

RE:Flood fill algorithm without recursion?

You probably dont need that boundary-finding loop to be inside the main loop. Just calculate all the boundary points once, instead of checking again and again for every point.

If you mark boundary points as CArea, then you wouldn't even need a separate boundary check.

Also, you might want to use addFirst instead of add, to stick stuff into the front. This makes your LinkedList behave as a Stack instead of a Queue, but should be faster for the same reasons as described before (it's slow to get to the end... unless the internal implementation keeps a tail pointer; I don't know if that is the case or not).

Some other points:
- remove(index) also returns the element at that index, so you can do

code:

x = Integer.parseInt (listx.remove (0).toString ());

- would casting be faster than parsing?

code:

x = (Integer)listx.remove(0);

- since x is already an Integer, we could just do

code:

listx.add (x);

which skips half of Integer constructor calls

Author:

tyuo9980 [ Mon Jan 02, 2012 10:30 pm ]

Post subject:

Re: RE:Flood fill algorithm without recursion?

Tony @ Mon Jan 02, 2012 10:15 pm wrote:

You probably dont need that boundary-finding loop to be inside the main loop. Just calculate all the boundary points once, instead of checking again and again for every point.

If you mark boundary points as CArea, then you wouldn't even need a separate boundary check.

Also, you might want to use addFirst instead of add, to stick stuff into the front. This makes your LinkedList behave as a Stack instead of a Queue, but should be faster for the same reasons as described before (it's slow to get to the end... unless the internal implementation keeps a tail pointer; I don't know if that is the case or not).

^^I'll be looking into that later. thanks

thanks for that. shaved off 10ms.

- remove(index) also returns the element at that index, so you can do

code:

x = Integer.parseInt (listx.remove (0).toString ());

I'm unable to cast in ready to program IDE. it works in eclipse but it wont be an option at school.

- would casting be faster than parsing?

code:

x = (Integer)listx.remove(0);

I get the no overload for the method was found in LinkedList error.

- since x is already an Integer, we could just do

code:

listx.add (x);

which skips half of Integer constructor calls

Author:	tyuo9980 [ Mon Jan 02, 2012 10:57 pm ]
Post subject:	Re: Flood fill algorithm without recursion?
CArea is the checkedArea. if it has been checked, then it becomes true. Boundary is the check to see which parts of the field is the border (the outline of the filled polygon) and I use that for boundary collision. If I had another way to check where the border is, it would massively speed up the flood fill. Eclipse is also 4 times faster than Ready and there would still be a huge delay even if java didnt have a stack limit. Comparing queuing and recursion on eclipse, it seems that queuing is 2 times slower.

Author:	Tony [ Mon Jan 02, 2012 11:16 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
right, but since you don't revisit checked areas, CArea could also effectively act as a border, as those points will not be crossed.

Author:	tyuo9980 [ Mon Jan 02, 2012 11:23 pm ]
Post subject:	Re: RE:Flood fill algorithm without recursion?
Tony @ Mon Jan 02, 2012 11:16 pm wrote: right, but since you don't revisit checked areas, CArea could also effectively act as a border, as those points will not be crossed. Well you still have to check if CArea is on the border or not. I might as well have another variable in place.

Author:

Tony [ Mon Jan 02, 2012 11:28 pm ]

Post subject:

RE:Flood fill algorithm without recursion?

but your code is structured as

code:

if (!CArea [x] [y])
{
...
if (!boundary) ...

that's an extra if-statement for every single point filled.

Author:	tyuo9980 [ Tue Jan 03, 2012 12:42 am ]
Post subject:	Re: Flood fill algorithm without recursion?
i saw that early on as well, but for some reason it runs much faster with that there, even though its checking that point twice.

Author:	Tony [ Tue Jan 03, 2012 12:55 am ]
Post subject:	RE:Flood fill algorithm without recursion?
well that doesn't sound like a reasonable claim, so I wouldn't really trust such an assertion without seeing the testing code.

Author:

tyuo9980 [ Tue Jan 03, 2012 1:37 am ]

Post subject:

Re: Flood fill algorithm without recursion?

here it is:

code:

public static void calcArea (int xx, int yy)
{
LinkedList listx = new LinkedList ();
LinkedList listy = new LinkedList ();
int x, y;

listx.addFirst (new Integer (xx));
listy.addFirst (new Integer (yy));

do
{
x = Integer.parseInt (listx.remove (0).toString ());
y = Integer.parseInt (listy.remove (0).toString ());

if (!CArea [x] [y])
{
boundary = false;

//if point is on wall
for (int i = 1 ; i <= walls ; i++)
{
if (wallDir [i] == vertical)
{
if (x == wallx1 [i] && y >= wally1 [i] && y <= wally2 [i])
{
boundary = true;
Boundary [x] [y] = true;
break;
}
}
else
{
if (y == wally1 [i] && x >= wallx1 [i] && x <= wallx2 [i])
{
boundary = true;
Boundary [x] [y] = true;
break;
}
}
}

if (!boundary) //if not at border
{
CArea [x] [y] = true;
area++;

g.drawRect (x,y,0,0);
c.ViewUpdate();

if (!CArea [x + 1] [y]) //checks right side
{
listx.addFirst (new Integer (x + 1));
listy.addFirst (new Integer (y));
}

if (!CArea [x - 1] [y]) //left side
{
listx.addFirst (new Integer (x - 1));
listy.addFirst (new Integer (y));
}

if (!CArea [x] [y + 1]) //below
{
listx.addFirst (new Integer (x));
listy.addFirst (new Integer (y + 1));
}

if (!CArea [x] [y - 1]) //above
{
listx.addFirst (new Integer (x));
listy.addFirst (new Integer (y - 1));
}
}
}
}
while (listx.size () != 0);
}

Author:	Tony [ Tue Jan 03, 2012 1:54 am ]
Post subject:	RE:Flood fill algorithm without recursion?
not sure what this is supposed to be, as it still uses boundary variable, still recalculates it inside the loop, and now also spends a bunch of time drawing things.

Author:	tyuo9980 [ Tue Jan 03, 2012 2:05 am ]
Post subject:	Re: Flood fill algorithm without recursion?
o sry. i just wanted to see how it was filling it is double checking but it is faster. around 10ms actually.

Author:	tyuo9980 [ Tue Jan 03, 2012 2:08 am ]
Post subject:	Re: Flood fill algorithm without recursion?
http://www.mediafire.com/?ba2itzfrk54f0xx if you want to take a look at the whole thing

Author:	tyuo9980 [ Tue Jan 03, 2012 2:14 am ]
Post subject:	Re: Flood fill algorithm without recursion?
Heres the check for how long it takes to fill. add this before the do while loop in the calcArea method: long dly = System.currentTimeMillis (); and this after the loop: System.out.println (System.currentTimeMillis () - dly);

Author:	Tony [ Tue Jan 03, 2012 2:14 am ]
Post subject:	RE:Flood fill algorithm without recursion?
can you post the slower non-boundary code that this is benchmarked against?

Author:

tyuo9980 [ Tue Jan 03, 2012 2:22 am ]

Post subject:

Re: Flood fill algorithm without recursion?

code:

public static void calcArea (int xx, int yy)
{
LinkedList listx = new LinkedList ();
LinkedList listy = new LinkedList ();
int x, y;

listx.addFirst (new Integer (xx));
listy.addFirst (new Integer (yy));

long awef = System.currentTimeMillis ();

do
{
x = Integer.parseInt (listx.remove (0).toString ());
y = Integer.parseInt (listy.remove (0).toString ());

boundary = false;

//if point is on wall
for (int i = 1 ; i <= walls ; i++)
{
if (wallDir [i] == vertical)
{
if (x == wallx1 [i] && y >= wally1 [i] && y <= wally2 [i])
{
boundary = true;
Boundary [x] [y] = true;
break;
}
}
else
{
if (y == wally1 [i] && x >= wallx1 [i] && x <= wallx2 [i])
{
boundary = true;
Boundary [x] [y] = true;
break;
}
}
}

if (!boundary) //if not at border
{
CArea [x] [y] = true;
area++;

if (!CArea [x + 1] [y]) //checks right side
{
listx.addFirst (new Integer (x + 1));
listy.addFirst (new Integer (y));
}

if (!CArea [x - 1] [y]) //left side
{
listx.addFirst (new Integer (x - 1));
listy.addFirst (new Integer (y));
}

if (!CArea [x] [y + 1]) //below
{
listx.addFirst (new Integer (x));
listy.addFirst (new Integer (y + 1));
}

if (!CArea [x] [y - 1]) //above
{
listx.addFirst (new Integer (x));
listy.addFirst (new Integer (y - 1));
}
}
}

while (listx.size () != 0);

System.out.println (System.currentTimeMillis () - awef);
}

update:
this helps a bit too. eliminated an if statement.

code:

for (int i = 1 ; i <= walls ; i++)
{
if (x == wallx1 [i] && y >= wally1 [i] && y <= wally2 [i]) //vertical
{
boundary = true;
Boundary [x] [y] = true;
break;
}
else if (y == wally1 [i] && x >= wallx1 [i] && x <= wallx2 [i]) //horizontal
{
boundary = true;
Boundary [x] [y] = true;
break;
}
}

Author:	tyuo9980 [ Tue Jan 03, 2012 3:09 pm ]
Post subject:	Re: Flood fill algorithm without recursion?
x = listx.remove (0).hashCode (); y = listy.remove (0).hashCode (); returns an int value and i dont have to convert to int from string! this cuts the calculation time in half!

Author:	Tony [ Tue Jan 03, 2012 4:01 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
well that's... a hack. Nice.

Author:	mirhagk [ Tue Jan 03, 2012 9:12 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
I don't get why you need that at all to be honest.

Author:	Zren [ Wed Jan 04, 2012 12:13 am ]
Post subject:	Re: Flood fill algorithm without recursion?
Suggestion: Queue queue = new LinkedList(); We can define the variable as a Queue, which would force us to just use Queue-related functions. Now Queue is an interface, so we can't create an instance of it, so we have to create an instance of a class that implements it. In this case, a LinkedList. The advantages of this? It will force yourself to only use the methods required for the Queue interface, thus your forced to learn how that data structure works instead of relying on methods from the List interface. @Tony: Edit the next part if you feel like continuing to chuck hints at the man. The properties of a List A List can hold anything. You can store numbers (Integer, Double, Float, etc), Strings, and pretty much anything that inherits the class Object. Any time you insert a number, it's actually an instance of Integer (or Double depending on the case), not the primitive type (int, double, ...). So it's safe to say that List is a collection of Objects and it's children classes. So whenever we use list.get(id) or queue.poll(), we're actually returning an Object. Read up about Generics: http://docs.oracle.com/javase/tutorial/extra/generics/intro.html

Author:	RandomLetters [ Wed Jan 04, 2012 12:20 am ]
Post subject:	RE:Flood fill algorithm without recursion?
Why not specify the type using List<Integer> ?

Author:	Tony [ Wed Jan 04, 2012 12:30 am ]
Post subject:	Re: RE:Flood fill algorithm without recursion?
Zren @ Wed Jan 04, 2012 12:13 am wrote: @Tony: Edit the next part if you feel like continuing to chuck hints at the man. Hah, nice. Though I think I'll leave that part up. RandomLetters @ Wed Jan 04, 2012 12:20 am wrote: Why not specify the type using List<Integer> ? Zren already mentioned Generics. While that would make for better code, Generics were introduced in Java 5, which would simply not work with OP's "Ready to Program" (Java 4).

Author:

DemonWasp [ Wed Jan 04, 2012 12:35 am ]

Post subject:

RE:Flood fill algorithm without recursion?

Suggestions:

1. Use Integer.valueOf(String) instead of new Integer(String). This will avoid creating new instances of Integer when an object already exists, which I suspect it will frequently in your case (how many times does the value 4 show up as a coordinate? Well, once for every row and once for every column, past a 4x4 area...)

2. Specify the base you want to use when parsing integers with parseInt or valueOf as the second argument: Integer.valueOf("123", 10). Code style, mostly.

3. Normally, I would insist that you use .intValue(), but as it turns out, .hashCode() is documented to return the value of the encapsulated integer. You might want to put a comment on that, so you remember what you were doing when you look at this later.

4. ArrayList is much faster than LinkedList. You should generally not .remove(0) from an ArrayList, but even if you do it's still faster. You could probably get a speed boost just by changing:
From:

Java:

LinkedList listx = new LinkedList ();

To:

Java:

List listx = new ArrayList();

5. Possible logic bug: Your for-loop over the walls[] array starts at 1, not 0. Was that intentional?

6. If you still have a performance issue, implement a CircularIntegerQueue of your own and use that instead of ArrayList. This will eliminate the need to wrap primitive ints in reference-type Integer objects, and will eliminate the list-remove costs entirely. Alternatively, find an open-source software project that offers something like that and use that instead.

7. Use Java 6 or Java 7. This alone will eliminate huge amounts of performance trouble, as the JVM got an awful lot faster since 1.4.2 (which was considered "past end of life" over 4 years ago). Unfortunately, cannot be done without moving away from ReadyToProgram.

Author:

Tony [ Wed Jan 04, 2012 1:25 am ]

Post subject:

Re: RE:Flood fill algorithm without recursion?

Hey guys, lets go on a tangental ride into the wonders of Java!

DemonWasp @ Wed Jan 04, 2012 12:35 am wrote:

1. Use Integer.valueOf(String) instead of new Integer(String). This will avoid creating new instances of Integer when an object already exists, which I suspect it will frequently in your case (how many times does the value 4 show up as a coordinate? Well, once for every row and once for every column, past a 4x4 area...)

Here's a puzzle:

code:

class Foo {
public static void main(String[] args) {
Integer i1 = 127;
Integer i2 = 127;
Integer i3 = 128;
Integer i4 = 128;
System.out.println(i1 == i2);
System.out.println(i3 == i4);
}
}

What does the output print? (Java 5+)

~~~~~
Though the point stands -- constructors are expensive function calls. If you are working with a lot of data, avoiding creation of objects could be a performance boost. Reminds me of Hadoop's org.apache.hadoop.io.Text extends BinaryComparable http://hadoop.apache.org/common/docs/r0.20.1/api/org/apache/hadoop/io/Text.html

Quote:

- provides methods to serialize, deserialize, and compare texts at byte level
- provides methods for string traversal without converting the byte array to a string

Sorting millions of strings at the byte level is crazy fast.

Author:	tyuo9980 [ Wed Jan 04, 2012 4:17 am ]
Post subject:	Re: Flood fill algorithm without recursion?
I tested some of the ideas out in eclipse and surprisingly i couldnt find any performance difference when i implemented generics. Changing to arraylists however made the program much more slower.

Author:

DemonWasp [ Wed Jan 04, 2012 10:55 am ]

Post subject:

Re: RE:Flood fill algorithm without recursion?

Tony @ Wed Jan 04, 2012 1:25 am wrote:

What does the output print? (Java 5+)

For those wondering, it outputs:

code:

true
false

Reason being that Tony's code implicitly uses Integer.valueOf(int). In the documentation for that, they say " If a new Integer instance is not required, this method should generally be used in preference to the constructor Integer(int), as this method is likely to yield significantly better space and time performance by caching frequently requested values."

By "caching frequently requested values", they meant they were doing the static optimization of caching the values 0-127, instead of what you actually frequently requested. While it seems silly, it actually works out alright for many cases, including this one. The worst case is that it just calls the constructor anyway, so very little harm done. You can see the source they used here: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/lang/Integer.java

@tyuo: Hmm; ArrayLists are usually just plain faster than LinkedLists, though I suppose your current program is doing a lot of remove-first operations (which for LinkedLists is relatively quick, but for ArrayLists involves an array-copy operation, which is expensive). The whole operation can be much faster than either if you build yourself a circular array-based queue (specifically for ints, since that's what you want).

Generics don't improve performance. They let you write safer code by automatically adding type checking at compile time. In short, their best use is to avoid writing casts all the time.

Author:	mirhagk [ Wed Jan 04, 2012 12:22 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
Generics don't improve performance? I though they would at least remove all run-time castings, which would actually do a lot. Do they not do that?

Author:	DemonWasp [ Wed Jan 04, 2012 12:54 pm ]
Post subject:	Re: RE:Flood fill algorithm without recursion?
mirhagk @ Wed Jan 04, 2012 12:22 pm wrote: Generics don't improve performance? I though they would at least remove all run-time castings, which would actually do a lot. Do they not do that? Casts actually don't seem to hurt performance very much; there is a JVM instruction (checkcast) that is used to supply the ClassCastException when you make an invalid cast, and it should execute fairly quickly. Primitive casts use particular JVM instructions to perform the cast, such as l2i for long-2-int, and are even faster. Notably, Java's generics don't actually remove the need to cast (checkcast instruction), they just make it implicit rather than explicit. Because Java's generics are erased rather than reified, the type information inside the angle brackets disappears in the compilation process and the checkcasts are added to code that refers to that particular variable. That is, the compiler adds the casts for you. There was a long debate about whether it was preferable to have erased generics or reified generics, and there are a lot of valid reasons for both. While erased generics were definitely the right choice for getting people to port their software to newer versions of Java (necessary at the time), reified generics are a better idea in general, and there has been a recent push to switch in Java 8 (originally Java 7, but pushed back because of the SUN/Oracle debacle). See also: http://gafter.blogspot.com/2004/09/puzzling-through-erasure-answer.html and http://gafter.blogspot.com/2006/11/reified-generics-for-java.html

Author:	Tony [ Wed Jan 04, 2012 1:07 pm ]
Post subject:	RE:Flood fill algorithm without recursion?
Cached Integers are actually in the -128 to 127 range. The idea can be extended to a larger range (see source code DemonWasp linked to), to avoid any new construction within the loop. Building up this cache list outside the function will make sense, as I think this function is called multiple times during app's lifetime. I second the idea that circular array (native arrays!) queues will be much much faster (no constructors, no linking/unlinking elements into a list). But it's more implementation work, and you need to know the max queue size ahead of time.

You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy