Most efficient way to create an array of counting numbers

Question

What's the most efficient way to make an array of a given length, with each element containing its subscript?

Possible description with my dummy-level code:

/**
 * The IndGen function returns an integer array with the specified dimensions.
 *  
 *  Each element of the returned integer array is set to the value of its 
 *  one-dimensional subscript.
 *  
 *  @see Modeled on IDL's INDGEN function: 
 *      http://idlastro.gsfc.nasa.gov/idl_html_help/INDGEN.html 
 *  
 *  @params size
 *  @return int[size], each element set to value of its subscript
 *  @author you
 *  
 *  */

public int[] IndGen(int size) {
    int[] result = new int[size];
    for (int i = 0; i < size; i++) result[i] = i;
    return result;
}

Other tips, such as doc style, welcome.

Edit

I've read elsewhere how inefficient a for loop is compared to other methods, as for example in Copying an Array:

Using clone: 93 ms

Using System.arraycopy: 110 ms

Using Arrays.copyOf: 187 ms

Using for loop: 422 ms

I've been impressed by the imaginative responses to some questions on this site, e.g., Display numbers from 1 to 100 without loops or conditions. Here's an answer that might suggest some methods:

public class To100 {
public static void main(String[] args) {
        String set = new java.util.BitSet() {{ set(1, 100+1); }}.toString();
        System.out.append(set, 1, set.length()-1);
    }
}

If you're not up to tackling this challenging problem, no need to vent: just move on to the next unanswered question, one you can handle.

Answer 1

Since it's infeasible to use terabytes of memory at once, and especially to do any calculation with them simultaneously, you might considering using a generator. (You were probably planning to loop over the array, right?) With a generator, you don't need to initialize an array (so you can start using it immediately) and almost no memory is used (O(1)).

I've included an example implementation below. It is bounded by the limitations of the long primitive.

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Counter implements Iterator<Long> {
    private long count;
    private final long max;

    public Counter(long start, long endInclusive) {
        this.count = start;
        this.max = endInclusive;
    }

    @Override
    public boolean hasNext() {
        return count <= max;
    }

    @Override
    public Long next() {
        if (this.hasNext())
            return count++;
        else
            throw new NoSuchElementException();

    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

Find a usage demonstration below.

Iterator<Long> i = new Counter(0, 50);
while (i.hasNext()) {
    System.out.println(i.next());  // Prints 0 to 50
}

Answer 2

only thing i ca think of is using "++i" instead of "i++" , but i think the java compiler already has this optimization .

other than that, this is pretty much the best algorithm there is.

you could make a class that acts as if it has an array yet it doesn't , and that it will simply return the same number that it gets (aka the identity function) , but that's not what you've asked for.

Answer 3

As other have said in their answers, your code is already close to the most efficient that I can think of, at least for small sized arrays. If you need to create those arrays a lot of times and they are very big, instead of continuously iterating in a for loop you could create all the arrays once, and then copy them. The copy operation will be faster than iterating over the array if the array is very big. It would be something like this (in this example for a maximum of 1000 elements):

public static int[][] cache = {{0},{0,1},{0,1,2},{0,1,2,3},{0,1,2,3,4}, ..., {0,1,2,...,998,999}};

Then, from the code where you need to create those arrays a lot of times, you would use something like this:

int[] arrayOf50Elements = Arrays.copyOf(cache[49], 50);

Note that this way you are using a lot of memory to improve the speed. I want to emphasize that this will only be worth the complication when you need to create those arrays a lot of times, the arrays are very big, and maximum speed is one of your requirements. In most of the situations I can think of, the solution you proposed will be the best one.

Edit: I've just seen the huge amount of data and memory you need. The approach I propose would require memory of the order of n^2, where n is the maximum integer you expect to have. In this case that's impractical, due to the monstrous amount of memory you would need. Forget about this. I leave the post because maybe it is useful for others.