Sliding an array in java - algorithm based

I'm writing a program in java where I need to slide the elements of the array and it should be performing as less as possible number of operations as it's inside a double loop and I'm working with length of array ranging from upto 10^8.

Example : A = {1,2,3,4,5,6} Result : A = {2,3,4,5,6,1} for 1st time A = {3,4,5,6,1,2} for 2nd time and so on..

Please feel free to sugge开发者_如何学运维st any other data structure or any modifications to the array!! Thank you guys!! :D

The simplest way to achieve that effect, is to do a "circular array"; that is, instead of moving the contents of the array, you can simply store the index that marks the beginning of the array.

To get the item at index i, you then do:

Type item = arr[(offset + i) % arr.length];

This way, you get the same properties as you have in an array, and you can perform any rotation in O(1).

In order to make this less of a hassle to use, you could make a simple wrapper class, that simply wraps an array, allowing easy rotation through this method. That way, the code could look clean, while you get efficient rotation.

In order to achieve an O(1) complexity, you could...

1. use a linked list
2. wrap your array with a class that stores the start position and let you access the array through "virtual" indexes (wrapped.acces(i) => array[(start + i) % array.length]
3. "double" your array and slice it in an appropriate way (so you don't have to change the surrounding code)

Otherwise, if you want to stick with your data structure, you need to pay O(n), no matter what.

I'd go with (2), because it is faster to both random access and linear access patterns (arrays have better data locality + O(1) random access complexity wrt O(n) of linked lists).

Use Collections.rotate(Arrays.asList(myArray), myDistance).

If you're not married to the idea of using arrays, then you could make use of the Collections.rotate() method.

List<Integer> list = new ArrayList<Integer>();

for (int i = 1; i <= 6; i++) {
    list.add(i-1, new Integer(i));
}

int j = 0;
while (j < 100) {
    Collections.rotate(list, -1);
    System.out.print("{");
    for (Integer integer : list) {
        System.out.print(integer + ", ");
    }
    System.out.println("}");
}

Why do You have to rotate the table ?

Imagin that table is a circle and after that you can walk like this:

Object object = array[(offset + i) % array.length];

This give you O(1) on any access or rotation step;

You can use a simple List for that. If you do this sliding often, a queue would be the best choice. The thing is, the array doesn't really change, you just start to read at position x and then continue to read at the start of the array length(array)-x elements. This is the fastest Variant.