Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Generic Gap Buffer

, 25 Oct 2007
A list-style collection for fast insert and remove operations.
gapbuffer.zip
GapBuffer
GapBuffer.suo
GapBuffer
bin
Release
GapBuffer.dll
GapBuffer.pdb
Properties
PerformanceTest
bin
Release
GapBuffer.dll
GapBuffer.pdb
PerformanceTest.exe
PerformanceTest.pdb
PerformanceTest.vshost.exe
Properties
#region Using Directives

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

using Slusser.Collections.Generic;

#endregion Using Directives


namespace PerformanceTest
{
	class Program
	{
		#region Fields

		private static Stopwatch stopwatch;

		#endregion Fields


		#region Main

		static void Main(string[] args)
		{
			stopwatch = new Stopwatch();

			// Test random insert performance
			Console.WriteLine();
			TestRandomInsert();

			// Test insert performance
			Console.WriteLine();
			TestInsert();

			// Test random remove performance
			Console.WriteLine();
			TestRandomRemoveAt();

			// Test remove performance
			Console.WriteLine();
			TestRemoveAt();
		}

		#endregion Main


		#region Tests

		private static void TestRandomRemoveAt()
		{
			const int iterations = 200000;
			Random r = new Random();
			Console.WriteLine("Removing {0:0,0} items randomly from each collection: ", iterations);

			int[] items = new int[iterations];
			for (int i = 0; i < items.Length; i++)
				items[i] = i;

			List<int> list = new List<int>(items);
			list.Capacity = items.Length;
			stopwatch.Reset();
			stopwatch.Start();
			for (int i = items.Length - 1; i >= 0; i--)
				list.RemoveAt(r.Next(i));
			stopwatch.Stop();
			Trace.Assert(list.Count == 0);
			Console.WriteLine("List<int> time: {0:0,0}ms", stopwatch.ElapsedMilliseconds);

			GapBuffer<int> buffer = new GapBuffer<int>();
			buffer.AddRange(items);
			buffer.Capacity = items.Length;
			stopwatch.Reset();
			stopwatch.Start();
			for (int i = items.Length - 1; i >= 0; i--)
				buffer.RemoveAt(r.Next(i));
			stopwatch.Stop();
			Trace.Assert(buffer.Count == 0);
			Console.WriteLine("GapBuffer<int> time: {0:0,0}ms", stopwatch.ElapsedMilliseconds);
		}

		private static void TestRandomInsert()
		{
			const int iterations = 200000;
			Random r = new Random();
			Console.WriteLine("Inserting {0:0,0} items randomly into each collection: ", iterations);

			List<int> list = new List<int>();
			list.Capacity = iterations;
			list.Add(0);
			stopwatch.Reset();
			stopwatch.Start();
			for (int i = 1; i < iterations; i++)
			{
				list.Insert(r.Next(i), i);
			}
			stopwatch.Stop();
			Trace.Assert(list.Count == iterations);
			Trace.Assert(list.Capacity == iterations);
			Console.WriteLine("List<int> time: {0:0,0}ms", stopwatch.ElapsedMilliseconds);


			GapBuffer<int> buffer = new GapBuffer<int>();
			buffer.Capacity = iterations;
			buffer.Add(0);
			stopwatch.Reset();
			stopwatch.Start();
			for (int i = 1; i < iterations; i++)
			{
				buffer.Insert(r.Next(i), i);
			}
			stopwatch.Stop();
			Trace.Assert(buffer.Count == iterations);
			Trace.Assert(buffer.Capacity == iterations);
			Console.WriteLine("GapBuffer<int> time: {0:0,0}ms", stopwatch.ElapsedMilliseconds);
		}

		private static void TestRemoveAt()
		{
			const int iterations = 200000;
			Console.WriteLine("Removing {0:0,0} items from the beginning of each collection: ", iterations);

			int[] items = new int[iterations];
			for (int i = 0; i < items.Length; i++)
				items[i] = i;

			List<int> list = new List<int>(items);
			list.Capacity = items.Length;
			stopwatch.Reset();
			stopwatch.Start();
			for (int i = 0; i < items.Length; i++)
				list.RemoveAt(0);
			stopwatch.Stop();
			Console.WriteLine("List<int> time: {0:0,0}ms", stopwatch.ElapsedMilliseconds);

			GapBuffer<int> buffer = new GapBuffer<int>();
			buffer.AddRange(items);
			buffer.Capacity = items.Length;
			stopwatch.Reset();
			stopwatch.Start();
			for (int i = 0; i < items.Length; i++)
				buffer.RemoveAt(0);
			stopwatch.Stop();
			Console.WriteLine("GapBuffer<int> time: {0:0,0}ms", stopwatch.ElapsedMilliseconds);
		}

		private static void TestInsert()
		{
			const int iterations = 200000;
			Console.WriteLine("Inserting {0:0,0} items into the beginning of each collection: ", iterations);

			List<int> list = new List<int>();
			list.Capacity = iterations;
			stopwatch.Reset();
			stopwatch.Start();
			for (int i = 0; i < iterations; i++)
			{
				list.Insert(0, i);
			}
			stopwatch.Stop();
			Trace.Assert(list.Count == iterations);
			Trace.Assert(list.Capacity == iterations);
			Console.WriteLine("List<int> time: {0:0,0}ms", stopwatch.ElapsedMilliseconds);

			GapBuffer<int> buffer = new GapBuffer<int>();
			buffer.Capacity = iterations;
			stopwatch.Reset();
			stopwatch.Start();
			for (int i = 0; i < iterations; i++)
			{
				buffer.Insert(0, i);
			}
			stopwatch.Stop();
			Trace.Assert(buffer.Count == iterations);
			Trace.Assert(buffer.Capacity == iterations);
			Console.WriteLine("GapBuffer<int> time: {0:0,0}ms", stopwatch.ElapsedMilliseconds);
		}

		#endregion Tests
	}
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Jacob Slusser
Web Developer
United States United States
Rather than attempt to keep up my biography, I will refer you to my website:
 
www.codetruffles.com

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.141223.1 | Last Updated 25 Oct 2007
Article Copyright 2007 by Jacob Slusser
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid