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® 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
