Of all of them the work on the Array is the fastest. RoundRobinArrayList, using
the
RemoveAt(), Add() paradigm to do the shuffle is only slightly slower than the
Array
version. This is expected since internally the ArrayList is just doing the same
Copy
operation we performed. The array doesn't resize so intrinsically the same
speed is
achieved.
The for loop method is insanely slow at 4 seconds compared to only 2 tenths of a
second for the other two algorithms.
Creating the head/tail pointer version that has been suggested would by far be
the
fastest, however, it would require an entirely new collection be generated.
Depending
on how and when you do these shuffles there are some methods you could use that
would limit the number of copy operations if you do maintain the head/tail
yourself.
For instance, in an array of 50 elements with a backing store of 100 elements,
you could
shuffle the collection 50 times before you ran out of tail space to move the
first element
to. At this point you could have to copy the 50 element collection back to the
front of
your 100 element store. This isn't bad since it saves you 49 copy operations
you would
otherwise have had to incur.
using System;
using System.Collections;
public class RoundRobin {
private static void Main(string[] args) {
int iterations = 100000;
DateTime start, end;
start = DateTime.Now;
RoundRobinArray(iterations);
end = DateTime.Now;
Console.WriteLine("RoundRobinArray: {0}", end - start);
start = DateTime.Now;
RoundRobinArrayList(iterations);
end = DateTime.Now;
Console.WriteLine("RoundRobinArrayList: {0}", end - start);
start = DateTime.Now;
RoundRobinArrayList2(iterations);
end = DateTime.Now;
Console.WriteLine("RoundRobinArrayList2: {0}", end - start);
}
public static void RoundRobinArrayList2(int iterations) {
int capacity = 500;
ArrayList list = new ArrayList(capacity);
for(int i = 0; i < capacity; i++) {
list.Add(i);
}
for(int i = 0; i < iterations; i++) {
object first = list[0];
for(int j = 1; j < list.Count; j++) {
list[j - 1] = list[j];
}
list[list.Count - 1] = first;
}
}
public static void RoundRobinArrayList(int iterations) {
int capacity = 500;
ArrayList list = new ArrayList(capacity);
for(int i = 0; i < capacity; i++) {
list.Add(i);
}
for(int i = 0; i < iterations; i++) {
object tempElement = list[0];
list.RemoveAt(0);
list.Add(tempElement);
}
}
public static void RoundRobinArray(int iterations) {
int[] array = new int[500];
for(int i = 0; i < array.Length; i++) {
array[i] = i;
}
for(int i = 0; i < iterations; i++) {
int tempElement = array[0];
Array.Copy(array, 1, array, 0, array.Length - 1);
array[array.Length - 1] = tempElement;
}
}
}
--
Justin Rogers
DigiTec Web Consultants, LLC.
Blog:
http://weblogs.asp.net/justin_rogers
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:e7****************@TK2MSFTNGP09.phx.gbl...
That is interesting idea. I will need to think about it as would need to
change a bunch of stuff to integrate it. The manual method is pretty fast
and by my testing the for loop is faster then removing first element and
adding it back to the end (not by much however.) Thanks again for the
reply!
--
William Stacey, MVP
"Sherif ElMetainy" <el*************@wayout.net.NOSPAM> wrote in message
news:e3**************@TK2MSFTNGP12.phx.gbl... Hello
Would the following do the job? Basically this doesn't do any real
shifting of elements, you just move the index of the first element, so the rotate
operation should be very fast, while the access needs extra addition and
modulo operations. I demonstrated only Rotate and access, of course you
may need to modify Add, Insert, RemoveAt, IndexOf, etc according to this
change if you need to. I also didn't put error checking in the indexer. You
should check that index is less than Count and greater than zero.
public class RoundRobinArrayList : ArrayList {
private int startIndex = 0;
public RoundRobinArrayList() {
}
void Rotate() {
startIndex++;
}
public override object this[int index] {
get { return base[(index +startIndex) % base.Count]; }
set { base[(index +startIndex) % base.Count] = value;}
}
}
Best regards,
Sherif
"William Stacey [MVP]" <st***********@mvps.org> wrote in message
news:eN**************@TK2MSFTNGP09.phx.gbl... I can think of a couple ways to do this, but was wonder what the fastest
way you can think of.
Want to take any arraylist of > 1 element and make the first element the
last, and all the rest of the elements will move up one position. This
will be called a lot, so looking for speed. This just saving the index 0 as
tmp and then enum the list to move up the elements, then put the tmp object in last pos is the best way? Cheers
--
William Stacey, MVP