CODEWITHSUNDEEP
javaarraysarraylist
user717572
user717572

Reputation: 3652

Store value at unspecified index in an Array. What's faster?

Say I want to add a value to an array, but it doesn't matter where, as long as the current item at that index is null. This null could be anywhere in the array, at random locations. I just want to have my value somewhere in my array. Should I iterate over it like this: 

    for (int i = 0; i < 64; i++) {
        if (items[i] == null) {
            items[i] = obj;
            return;
        }

This way it may have to iterate over a lot of elements before it finds a null spot. Would it be faster to use another type, i.e. ArrayList ?

This is for a game, so performance is very crusial, and this is done maybe 300 times per second (also accessing, and deleting items). So for a game, what should I use best to store items, to iterate over ?

Upvotes: 1

Views: 384

Answers (2)

Jerome
Jerome

Reputation: 4582

You can refactor that piece of work in many different ways using the numerous Collection implementations but do you need it ? Is that necessary ? Will that improve your performances ? Do you have realtime constraint (meet deadline) ? Are these few lines of code your bottleneck ? Your array has 64 boxes, can it be resized ? Are the items mostly null at the end of the array of at the beginning ? Do you need to be Thread-safe ? Did you run a stress / load test and measure how much time you spend in these lines (average, lowest and highest) ?

There are many optimizations you can do but they will depend on the behavior of your application.

Maybe you can rethink slightly your program to improve performances. IMO it usually is the most efficient. Did you think of replacing your array by something else ? You can do your own implementation (a lightweight one) of the Queue interface to manage the relevant (non-null) items. If you were relying on the position in the array, then you can add that information in the items (I suppose these are Objects).

Upvotes: 0

gSamp
gSamp

Reputation: 93

One way I have used in the past is to use an array and a Queue. Any time you add a object to the array you first check your queue to see if you have any empty slots. Anytime you destroy a object you set the array slot to null and add the index to the queue so you can quickly pull it out later. During my tests this was faster than a List because you only resize the array if you make it bigger.

code wise

Queue<int> emptySlots;
Object[] arrayOfStuff;

public void AddStuff(object stuffToAdd)
{
    if (this.emptySlots.Count > 0)
    {
        int index = this.emptySlots.Dequeue();
        //make sure your objects know their position in the array
        stuffToAdd.ID = index;
        this.arrayOfStuff[index] = stuffToAdd;            
    }
    else
    {
        //resize array and add new object to end rememebering to fetch its id
    }
}

public void RemoveStuff(object stuffToRemove)
{
    this.emptySlots.Enqueue(stuffToRemove.ID);
    this.arrayOfStuff[stuffToRemove.ID] = null;
}

Upvotes: 1

Related Questions