Re: round-robin an arraylist
From: Justin Rogers (Justin_at_games4dotnet.com)
Date: 05/14/04
- Next message: S Domadia: "problems with creategraphics and combo_click event."
- Previous message: Frans Bouma [C# MVP]: "Re: Losing pwd in transaction connectionstring"
- In reply to: William Stacey [MVP]: "Re: round-robin an arraylist"
- Next in thread: William Stacey [MVP]: "Re: round-robin an arraylist"
- Reply: William Stacey [MVP]: "Re: round-robin an arraylist"
- Messages sorted by: [ date ] [ thread ]
Date: Fri, 14 May 2004 01:34:19 -0700
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]" <staceywREMOVE@mvps.org> wrote in message news:e7v%23eIXOEHA.3476@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" <elmeteny.NOSPAM@wayout.net.NOSPAM> wrote in message > news:e34KmXUOEHA.2996@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]" <staceywREMOVE@mvps.org> wrote in message > > news:eNLGXbSOEHA.2336@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 > > > > > > > > > > >
- Next message: S Domadia: "problems with creategraphics and combo_click event."
- Previous message: Frans Bouma [C# MVP]: "Re: Losing pwd in transaction connectionstring"
- In reply to: William Stacey [MVP]: "Re: round-robin an arraylist"
- Next in thread: William Stacey [MVP]: "Re: round-robin an arraylist"
- Reply: William Stacey [MVP]: "Re: round-robin an arraylist"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
