ArrayList optimization

Question

i am currently working on this for personal gratification and would like some advice on how i can make this code faster :

I have one ArrayList composed of an object note, which have coordinates and color value stored in it.

Each "note" is created in real time during the rendering call.

I have made this function :

void keyPressed() {  
    if (key == 's' || key == 'S') {
        PImage img = createImage(posX, specSize, RGB);
        for(int x = 0; x < posX; x++){
            for(int y = 0; y < specSize; y++){
                for(int i = 0; i < notes.size(); i++){
                    if( (notes.get(i).getX() == x) 
                         && (notes.get(i).getY() == y) ){

                        int loc = x + y*posX;
                        img.pixels[loc] = color(notes.get(i).getR(),
                                    notes.get(i).getG(), notes.get(i).getB());
                    }
                }
            }
        }
    img.updatePixels();
    img.save("outputImage.png");
    }
}

So when i press the "S" key, i run a loop on the width and height because they can be different in each run, and then on my arrayList and get the corresponding "note" with it's x and y position. then i write my picture file. As you can imagine, this is really, really, slow...

Around 5 to 6 minutes for a 1976x256px file. For me it's okay but it would be great to shorten this a little.

Is there a way to optimize this three loops? If you need more code, please let me know it's a small code and i don't mind.

Dawood ibn Kareem · Accepted Answer · 2014-01-05 07:43:14Z

1

How about this?

void keyPressed() {  
    if (key == 's' || key == 'S') {
        PImage img = createImage(posX, specSize, RGB);
        for(int i = 0; i < notes.size(); i++){
            int x = notes.get(i).getX();
            int y = notes.get(i).getY();
            int loc = x + y*posX;
            img.pixels[loc] = color(notes.get(i).getR(),
                           notes.get(i).getG(), notes.get(i).getB());
        }
        img.updatePixels();
        img.save("outputImage.png");
    }
}

Update:

Not sure what the type of notes is, but something like this might work too. Insert the correct type for one element of Notes into the for loop where I wrote ???.

void keyPressed() {  
    if (key == 's' || key == 'S') {
        PImage img = createImage(posX, specSize, RGB);
        for(??? note : notes ){
            int x = note.getX();
            int y = note.getY();
            int loc = x + y * posX;
            img.pixels[loc] = color(note.getR(), note.getG(), note.getB());
        }
        img.updatePixels();
        img.save("outputImage.png");
    }
}

edited Jan 5, 2014 at 7:43

answered Jan 5, 2014 at 7:36

Dawood ibn Kareem

80.2k15 gold badges102 silver badges112 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

GaelDev Over a year ago

Well, after coffe-break, this is what i've figured too :), exept your for syntaxes is better. But on another topic, my rendering is very slow, it's in opengl 2.0, but each note render a line, and this however i can't achieve to make faster. (i'm still new to stack and i don't know if i must edit the first post with your answer and if i can ask the new question in here or on a new subject if you can help whith that too :))

Dawood ibn Kareem Over a year ago

I think you should ask it as a new question entirely, but maybe include a link to this question in it.

tgkprog · Accepted Answer · 2014-01-05 07:44:02Z

1

Can clone notes (and any other object that is used to save) and do this in a different thread so its async to UI. the code will take same or more time but the user can use the rest of the app. Clone is neccesary as you want a snap shot of state when save was clicked.

Dont make a thread put use a ThreadPoolExecutor with one thread max. In the run method could apply what David suggested - one loop instead of two.

answered Jan 5, 2014 at 7:44

tgkprog

4,7434 gold badges47 silver badges76 bronze badges

Comments

Community · Accepted Answer · 2020-06-20 09:12:55Z

0

Convert your list of notes into a structure mapped like

Map<Integer, Map<Integer, Note> noteMap

Then replace your inner-most loop with a single call like

yNoteMap = note.get(x);

if (yNoteMap != null) {

note = yNoteMap.get(y);

if (note != null) {

// do stuff with note

}

}

Your computational complexity will go from about O(n^3) to O(n^2).

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Jan 5, 2014 at 7:53

einnocent

4,0594 gold badges37 silver badges44 bronze badges

Comments

Amir Pashazadeh · Accepted Answer · 2014-01-05 07:59:15Z

Create a class such as Point with two properties of x and y and implement proper equals and hashcode methods as:

public class Point {
    private final int x;
    private final int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }

        if (o == null || getClass() != o.getClass()) {
            return false;
        }

        Point point = (Point) o;

        if (x != point.x)
            return false;
        if (y != point.y)
            return false;

        return true;
    }

    @Override
    public int hashCode() {
        int result = x;
        result = 31 * result + y;
        return result;
    }
}

now put the Point as key of a map, and find your points using this, so you don't have to iterate over the whole lists.

Collectives™ on Stack Overflow

ArrayList optimization

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related