Okay... I definately see what you mean...just for the sake of the archives,
here is my new class with some performance numbers. I've added the test
method down at the bottom for reference.
new method (in milliseconds)
0 10,000 calls to List.Insert()
0 15,000 calls to List.Insert()
0 20,000 calls to List.Insert()
15.625 50,000 calls to List.Insert()
15.625 75,000 calls to List.Insert()
15.625 100,000 calls to List.Insert()
old method (in milliseconds)
203.125 10,000 calls to List.Insert()
265.625 15,000 calls to List.Insert()
1062.5 25,000 calls to List.Insert()
6687.5 50,000 calls to List.Insert()
18296.875 75,000 calls to List.Insert()
35468.75 100,000 calls to List.Insert()
class List
{
private const int INITIAL_BUFFER_SIZE = 10;
private int[] _list;
private int _length = 0;
public List()
{
this._list = new int[INITIAL_BUFFER_SIZE];
}
public void Insert(int value)
{
this.Insert(value, BinarySearch(value));
if ( this._length == this._list.Length )
this.IncrementArraySize();
}
private void Insert(int value, int index)
{
for(int i = this._length; i > index; --i)
this._list[i] = this._list[i-1];
this._list[index] = value;
this._length++;
}
private int BinarySearch(int value)
{
int left = 0;
int right = this._length -1;
int middle = 0;
while (left <= right)
{
middle = (left + right) / 2;
if (value < this._list[middle])
{ right = middle -1; }
else if (value > this._list[middle])
{ left = middle +1; }
else if (value == this._list[middle])
{ break; }
}
return left;
}
private void IncrementArraySize()
{
int[] tempArray = new int[this._list.Length *2];
Array.Copy(this._list, tempArray, this._list.Length);
this._list = tempArray;
}
}
// Test Method
static void Main(string[] args)
{
List list = new List();
DateTime startTime = DateTime.Now;
for (int i=0; i<100000; i++)
list.Insert(i);
DateTime endTime = DateTime.Now;
TimeSpan timeSpan = endTime - startTime;
Debug.WriteLine(timeSpan.TotalMilliseconds);
}
----- Original Message -----
From: "Doug Tarr" <[EMAIL PROTECTED]>
To: <[email protected]>
Sent: Friday, October 07, 2005 10:19 PM
Subject: Re: [ADVANCED-DOTNET] Inserting Items into sorted list
Ryan,
I take it back slightly. Array.Copy is not the problem here, it's the
new Array(). Array.Copy is more or less equivalent regardless of
where you allocate since you have to move all the elements after the
inserted one no matter how you do it.
The problem is that you are doing this N times:
tempArray = new int[this._list.Length+1];
whereas if you were to double the length of the array when it hit the
limit, you would allocating an array O(log N) times.
- Doug
On 10/7/05, Ryan Graham <[EMAIL PROTECTED]> wrote:
I did struggle with the Array.Copy portion of the method. I didn't like it
as I was writting it. Are you suggesting that I have some padding at the
end
of my array? So perhaps, for every 5 inserts (or whatever seems to be most
optimal) I add another 5 empty spaces? Or did I miss your point entirely?
----- Original Message -----
From: "Doug Tarr" <[EMAIL PROTECTED]>
To: <[email protected]>
Sent: Friday, October 07, 2005 4:33 PM
Subject: Re: [ADVANCED-DOTNET] Inserting Items into sorted list
Ryan,
I wouldn't say you bombed it. Maybe a B-/C+. :)
Array.Copy is expensive on every insert. You can avoid that by
growing your array by a specified amount each time instead of +1 on
each insert. Hence the performance penalities you pay in .NET for a
poorly initialized collection.
The boundary checks for less than first or greater than last are
unnecessary and they don't help performance.
FWIW, look at a reference implementation. Take a look at how
SortedList etc is implemented in the CLR using Reflector.
The rest is form - binary search should be a separate function.
HTH
-Doug
On 10/7/05, Ryan Graham <[EMAIL PROTECTED]> wrote:
> I totally bombed this question in an interview so I'm posting my answer
> here
> for comments and suggestions... perhaps (god help me) I'm just not that
> bright, but this works and seems to be fairly efficent. The idea was
> simple,
> insert an integer into a list that has already been sorted.
>
> private int[] _list;
> ...
> public void Insert(int value)
> {
> int[] tempArray;
>
> // check for special cases
> if (this._list == null)
> { // first item added create new array
>
> this._list = new int[1];
> this._list[0] = value;
> return;
> }
> else if (this._list[this._list.Length-1] <= value)
> { // item to be added is greater than the last
> // item in the array, append item to end
>
> tempArray = new int[this._list.Length+1];
> Array.Copy(this._list, tempArray, this._list.Length);
> this._list = tempArray;
> this._list[this._list.Length-1] = value;
>
> return;
> }
> else if (this._list[0] >= value)
> { // item to be added is less than the first
> // item in the array, insert item to the beginning
>
> tempArray = new int[this._list.Length+1];
> Array.Copy(this._list, 0, tempArray, 1, this._list.Length);
> this._list = tempArray;
> this._list[0] = value;
>
> return;
> }
>
> int left = 0;
> int right = this._list.Length;
> int middle = 0;
> int mod = 0;
>
> // binary search loop
> while (left <= right)
> {
> // modify the pivot point
> middle = (left + right) / 2;
>
> if (value > this._list[middle])
> { // item is greater than the pivot point
>
> //Debug.WriteLine(value + " > " + this._list[middle]);
> mod = 1;
> left = middle + 1;
> }
> else if (value < this._list[middle])
> { // item is less than the pivot point
>
> //Debug.WriteLine(value + " < " + this._list[middle]);
>
> mod = 0;
> right = middle - 1;
> }
> else
> { // item is equal to the pivot point
>
> //Debug.WriteLine(value + " = " + this._list[middle]);
> break;
> }
> }
>
> // modify the pivot point again
> middle += mod;
>
> // rebuild array to allow space for new item
> tempArray = new int[this._list.Length+1];
> Array.Copy(this._list, 0, tempArray, 0, middle);
> Array.Copy(this._list, middle, tempArray, middle+1,
> tempArray.Length -
> (middle +1));
>
> // insert new item
> this._list = tempArray;
> this._list[middle] = value;
> }
>
> ===================================
> This list is hosted by DevelopMentor(r) http://www.develop.com
>
> View archives and manage your subscription(s) at
> http://discuss.develop.com
>
===================================
This list is hosted by DevelopMentor(r) http://www.develop.com
View archives and manage your subscription(s) at
http://discuss.develop.com
===================================
This list is hosted by DevelopMentor(r) http://www.develop.com
View archives and manage your subscription(s) at
http://discuss.develop.com
===================================
This list is hosted by DevelopMentor® http://www.develop.com
View archives and manage your subscription(s) at http://discuss.develop.com
===================================
This list is hosted by DevelopMentor® http://www.develop.com
View archives and manage your subscription(s) at http://discuss.develop.com
