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
