Maybe using 'append' for arrays is the problem?  Would ArrayList be more efficient?

Without reading your code:

I didn't look at your code either, but it should not be that slow ( edit: by that I mean your goal program should not require slowness). I would use an integer ArrayList to keep track of the "parent" pixels. The loop would be something like this:

I suspect that the solution is to use a collection that only accepts unique values. You have already mentioned a couple the Set and HashMap but I should point out that the Set is an interface so you would need a concrete class such as HashSet or TreeSet.

When using an ArrayList or LinkedList searching the list is sequential, in other words the time taken to traverse the list is proportional to the number of elements in the list. So if the list size doubles then the time taken to traverse it (such as using contains) doubles and in this case the problem is searching for duplicates so they can be avoided.

Both the Set and Map type collections are very fast at storing and finding elements inside them, and are faster than the ArrayList and LinkedList when the data set becomes large. They also have the advantage of only storing unique values.

The speed is based on how the data is stored inside the collection, and here you should be aware that Tree and Hash collections are very different internally. The TreeMap and HashMap collections need to specify a key which uniquely identifies a value.

For instance a passport number (key) uniquely identifies a person (value). In this program the key will be an xy coordinate. To use a HashMap or TreeMap then we need a class to represent the key and another class to represent the value.

The PixelPos class below has been designed to work as a key for either the TreeMap or HashMap collection you would need to design a class to represent the value (information about the pixel).

It maybe the actual value class is virtually none existant, for instance you may only want to store the pixel color which is an int. In this case rather than create a seperate class add this to the key class and dispense with the value class. Effectively the key is also the value and if you do this then use the TreeSet or HashSet alternatives.

There are a number of advantages over using these collections in that all the elements have unique keys. If you attempt to store an element with the same key (i.e. same hash-code or comparesTo returns zero) then it simply replaces the previous entry which is probably acceptable behaviour in your program. If not then simple use the contains method before inserting the data.

HTH

1. // Must implement Comparable interface for
2. //tree collection
3. public class PixelPos implements Comparable {
4.     public int x;
5.     public int y;
6. 
   
7.     // Required for hash collections
8.     public int hashCode(){
9.         return (x + "," + y).hashCode();   
10.     }
11. 
    
12.     // Required for tree collections
13.     public boolean equals(Object o){
14.         PixelPos p = (PixelPos) o;
15.         return (x == p.x && y == p.y);
16.     }
17. 
    
18.     // Required for tree collections
19.     public int compareTo(Object o) {
20.         PixelPos p = (PixelPos) o;
21.         if(x == p.x && y == p.y)
22.             return 0;
23.         // If different on y then order by y
24.         if(y != p.y)
25.             return (y < p.y) ? -1 :1;
26.         else // Same y then the x must differ
27.             return (y < p.y) ? -1 :1;
28.     }
29. 
    
30. }

Wow, everyone - thanks for the great suggestions!

@quarks, thanks especially for the detailed reply on Sets, etc.  These struck me as likely a good call, but scared me a bit!  Probably a good reason to learn about them... :)

I'll have to chew on everyone's suggestions and see what happens.  Will report back (probably with further questions)!

Great suggestions all. 

@quarks, I'm definitely going to have to spend more time looking into your suggestions.  Time to learn some more powerful formats for bigger data!

However, @asimes' solution worked out of the box and was a real performance improvement - thanks!

Some creepy early results can be seen here:
http://www.jeffreythompson.org/blog/2013/01/11/seed-sorting