I wrote a code to rotate a list a specific amount of places, the code I have below works but i would like to know if there is a more efficient way to do this.
public void Test8(List<int> items, int places)
{
int nums;
for (int i = 0; i < places; i++)
{
nums = items[items.Count() - 1];
items.RemoveAt(items.Count - 1);
items.Insert(0, nums);
}
}
This is a classic computer science problem. One technique that's slightly faster is to reverse the entire array, then reverse the two chunks of the array:
// If we want to shift two places, start with an array
[1, 2, 3, 4, 5, 6, 7, 8]
// Then reverse the entire array
[8, 7, 6, 5, 4, 3, 2, 1]
// Then reverse the first n elements, two in our case
[7, 8, 6, 5, 4, 3, 2, 1]
^^^^
// Then reverse the remaining items
[7, 8, 1, 2, 3, 4, 5, 6]
^^^^^^^^^^^^^^^^
Or, as code:
static void Reverse(List<int> items, int posFrom, int posTo)
{
// Helper to reverse a sub portion of an array in place
while (posFrom < posTo)
{
// Swap the first and last items
int temp = items[posFrom];
items[posFrom] = items[posTo];
items[posTo] = temp;
// Shrink down to the next pair of items
--posTo;
++posFrom;
}
}
static void Test8(List<int> items, int places)
{
// Sanity, if we try to rotate more than there are
// items in the array, it just loops around
places %= items.Count;
// Reverse the entire array
Reverse(items, 0, items.Count - 1);
// Reverse the first group of items
Reverse(items, 0, places - 1);
// Reverse the second group of items
Reverse(items, places, items.Count - 1);
}
This is O(n) time, irregardless of the shift size.
It can be faster if you implement it using Circular Array QUEUE (which theoritically have better memory management than the list). This does not need physically rotating the existing data, so it should be faster than your original code.
BTW, you can read other references in StackOverflow to enrich your knowledge, for ex:
You are inserting and removing list elements. There is some overhead associated with that. A list can be accessed by index. You can therefore loop through the list, moving elements to the position they should be in. You will need to use a temporary integer variable to avoid overwriting any list data.
Also good to check and make sure the rotation isn't nonsensical, i.e. rotating a list of length 3 right 5K by removing and adding items 5K times doesn't make sense, you can do that by doing something like places%=items.Count; before you start rotating.
Here is a similar question: C# Collection - Order by an element (Rotate)
Also, try this:
static void Main(string[] args)
{
var items = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
var rotatedItems = Rotate(items, 4);
// rotated is now {5, 6, 7, 8, 9, 1, 2, 3, 4}
Console.WriteLine(string.Join(", ", rotatedItems));
Console.Read();
}
public static IEnumerable<int> Rotate(IEnumerable<int> items, int places)
{
return items.Skip(places).Concat(items.Take(places));
}
You can write a user defined extension of List<int> that does the rotation by using List<T>.Reverse().
I took the basic idea from the C++ Standard Template Library which basically uses Reverse in three steps:
Reverse(first, mid)
Reverse(mid, last)
Reverse(first, last)
As far as I know, this is the most efficient and fastest way. I tested with 1 billion elements and the rotation Rotate(0, 50000, 800000) takes 0.00097 seconds.
(By the way: adding 1 billion ints to the List already takes 7.3 seconds)
Here's the extension you can use:
public static class Extensions
{
public static void Rotate(this List<int> me, int first, int mid, int last)
{
//indexes are zero based!
if (first >= mid || mid >= lastIndex)
return;
me.Reverse(first, mid - first + 1);
me.Reverse(mid + 1, last - mid);
me.Reverse(first, last - first + 1);
}
}
The usage is like:
static void Main(string[] args)
{
List<int> iList = new List<int>{0,1,2,3,4,5,6,7,8,9};
Console.WriteLine("Before rotate:");
foreach (var item in iList)
{
Console.Write(item + " ");
}
Console.WriteLine();
int firstIndex = 0, midIndex = 3, lastIndex = 5;
iList.Rotate(firstIndex, midIndex, lastIndex);
Console.WriteLine($"After rotate {firstIndex}, {midIndex}, {lastIndex}:");
foreach (var item in iList)
{
Console.Write(item + " ");
}
Console.ReadKey();
}
Circular Right-Shift Array with specified number of times in ArrayList. Specified Range of array elements and circular shift. become faster code as compare with array implementation
Code
using System;
using System.Collections;
public class Program
{
// Circular Array repeting logic in ArrayList
public static ArrayList CircularshiftArry(ArrayList a, int circularrep)
{
int I = 1;
while (I <= circularrep)
{
int n = a.Count;
a.Insert(0, a[n - I]);
I++;
}
return a;
}
public static void Main()
{
Console.WriteLine("ENTER HOW MANY CIRCULAR REPETATION YOU WANT");
int circularrep = int.Parse(Console.ReadLine());
ArrayList a = new ArrayList();
Console.WriteLine("HOW MANY ARRAY ELEMENTS YOU WANT TO ENTER");
int num = int.Parse(Console.ReadLine());
for (int i = 0; i < num; i++)
{
Console.WriteLine("ENTER ARRAY ELEMENTS:{0}", i);
int p = int.Parse(Console.ReadLine());
a.Add(p);
}
Console.WriteLine("\n");
Console.WriteLine("The enterd array is :");
for (int i = 0; i < num; i++)
{
Console.Write("{0}\t", a[i]);
}
ArrayList b = CircularshiftArry(a, circularrep);
Console.WriteLine("\n");
int N = b.Count;
Console.WriteLine("The {0}times circular shifted array is :", circularrep);
for (int i = 0; i < N - circularrep; i++)
{
Console.Write("{0}\t", b[i]);
}
Console.ReadLine();
}
}
