Alan McGovern writes: > I was just browsing through the List<T> implementation and made a few speed > optimisations. I'm not sure if changing from foreach(blah) to for(int i=0; i< > blah, i++) is ok or not, but it does offer a large speed increase. So let me > know if that's ok or not. > > Optimised Methods: > RemoveAll - from 0x up to 50x faster > > (The reason for the huge speed increase is that if you have a list<int> > containing entirely the number 5, removing from the end will be much more > efficient than removing from the start as you won't have to shift the entire > array over and over. Removing from the end will *always* be faster than > removing from the start, but the exact speed increase is highly dependant on > the number of matches).
You can avoid any duplicate shifting by keeping one additional variable. I have not looked at the rest of the class, so this may not be quite right, but should capture the rough idea of always-linear behavior: int ii, jj; // Scan past the non-matching prefix of the list. for (ii = 0; ii < _size; ++ii) { if (match(_items[ii])) break; } // Could optimize away the repeated call to match(_items[ii]) here. // The speedup of doing so is questionable. // Do in-place removal for the remaining items. for (jj = ii; ii < _size; ++ii) { if (!match(_items[ii])) _items[jj++] = _items[ii]; } // dispose of _items[jj] through _items[_size] here _size = jj; Michael Poole _______________________________________________ Mono-devel-list mailing list Mono-devel-list@lists.ximian.com http://lists.ximian.com/mailman/listinfo/mono-devel-list