04.03.2009

Быстрый поиск в C# сложных объектов

Поиск по списку, каждый элемент которого сложный объект можно организовать следующим образом:


/// Управление буфером контейнеров пользователя
public class SmartBuffer
{
/// Буфер для хранения контейнеров для пользователя
private List _cargoList = new List();

/// Получить контейнер для записи
public Cargo GetWritebleBuffer()
{
Cargo cargo = new Cargo();
this._cargoList.Add(cargo);

return cargo;
}

/// Удалить контейнер
public void RemoveCargo(Cargo cargo)
{
if (this._cargoList.Contains(cargo))
this._cargoList.Remove(cargo);
}

/// Выбрать контейнеры, которые находятся в пределах окна
public List Select(Cargo myCargo, int xDelta, int yDelta)
{
// сортировать буфер
this.SortBuffer();

// выполнить поиск по заданному критерию
List cargos = this._cargoList.FindAll(
delegate(Cargo c)
{
if (c != null && c.ClientAsk != null &&
c.ClientAsk.X >= myCargo.ClientAsk.X - xDelta &&
c.ClientAsk.X <= myCargo.ClientAsk.X + xDelta &&
c.ClientAsk.Y >= myCargo.ClientAsk.Y - yDelta &&
c.ClientAsk.Y <= myCargo.ClientAsk.Y + yDelta &&
myCargo.ClientAsk.UserID != c.ClientAsk.UserID)
return true;

return false;
});

return cargos;
}

/// Сортировка буфера
public void SortBuffer()
{
this._cargoList.Sort(new SortCargoByXY());
}
}

/// Сортировщик для быстрой сортировки.
/// Построение двойного индекса сначало по X потом Y.
class SortCargoByXY : IComparer
{
public int Compare(Cargo x, Cargo y)
{
if (x == y) return 0;
if (x == null || x.ClientAsk == null ||
y == null || y.ClientAsk == null)
return -1;
else if (x.ClientAsk.X == y.ClientAsk.X)
{
if (x.ClientAsk.Y > y.ClientAsk.Y) return 1;
else return -1;
}
else if (x.ClientAsk.X > y.ClientAsk.X) return 1;
else return -1;
}
}



Результаты тестирования:
100 000 элементов списка
значения X и Y [0; 100 000]
Время сортировки 39мс
Время поиска 15мс
Машина Core 2 Duo E8200 2666HGz 4Гб ОЗУ

Комментариев нет: