Flood fill algorithm without recursion?

[RandomLetters]

Why not specify the type using List<Integer> ?

[Tony]

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).

[DemonWasp]

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.

[Tony]

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.

[tyuo9980]

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.

[DemonWasp]

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.

[mirhagk]

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?

[DemonWasp]

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

[Tony]

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.