C # Lambda Expression Speed

Question

Раньше я не использовал много лямбда-выражений, и я столкнулся со случаем, когда подумал, что могу использовать одно из них. У меня есть пользовательский список из ~ 19 000 записей, и мне нужно выяснить, существует ли запись в списке или нет, поэтому вместо того, чтобы писать несколько циклов или использовать linq для просмотра списка, я решил попробовать это:

for (int i = MinX; i <= MaxX; ++i)
{
    tempY = MinY;

    while (tempY <= MaxY)
    {
        bool exists = myList.Exists(item => item.XCoord == i && item.YCoord == tempY);

        ++tempY;
    }
}

Единственная проблема в том, что выполнение занимает ~ 9 - 11 секунд. Я делаю что-то не так, это просто случай, когда мне не следует использовать такое выражение?

Спасибо.

РЕДАКТИРОВАТЬ: Извините. Я должен уточнить. Я создаю список записей с циклом for и while и проверяю, существует ли эта запись в myList. Это единственный способ думать об этом. Я пересмотрю это и посмотрю, что я получу.

Answer 1

Этот код не имеет смысла для меня, поэтому очень трудно сказать, правильно вы это делаете или нет. Хорошие шансы, что да, вы делаете это неправильно.

Вместо того, чтобы показывать код, попробуйте это. Предположим, у вас есть метод, который сделал точно , что вы хотите. Какой будет подпись этого метода? Не тело, просто подпись.

Предположим, например, что вы хотите задать вопрос "содержит ли этот список точек конкретную точку?" Тогда подпись будет

bool Contains(List<Point> list, Point p)

Предположим, вы хотите задать вопрос "содержит ли этот список точек какую-либо точку внутри этого прямоугольника?" Тогда подпись будет

bool ContainsAny(List<Point> list, Rectangle r)

Предположим, вы хотите задать вопрос: «Что общего у этих двух списков?» тогда подпись будет

List<Point> Intersection(List<Point> l1, List<Point> l2)

и так далее. Укажите, что вы пытаетесь сделать более четко, и мы поможем вам оптимизировать эту операцию. Начните с подписи.

Answer 2

Это не проблема с лямбда, это проблема с вашим алгоритмом. Вы переходите от MinX к MaxX, сколько? затем вы перебираете то же самое от MinY до MaxY, затем вы перебираете ~ 19 000 записей. таким образом, если цикл X равен 10, а цикл y равен 10, то вы делаете 19 000 * 10 * 10 вызовов. Это может быть намного хуже.

Answer 3

Ваш алгоритм неэффективен. Если вы выполняете несколько поисков в одном и том же списке, вам необходимо:

1. Сортировка списка соответствующим образом (по клавише поиска).
2. Используйте двоичный поиск , чтобы найти нужную запись.

Другой вариант, если память не проблема, и вы хотите, чтобы она работала очень быстро, - это поместить записи в Dictionary<Your_Key,Record>. Это даст вам самый быстрый доступ после его настройки.

Answer 4

Разве это не то, что вы хотите?

myList.Where(
    item=>item.XCoord>=MinX
        &&item.XCoord<=MaxX
        &&item.YCoord>=MinY
        &&item.YCoord<=MaxY
)

Все полученные элементы будут удовлетворять критерию exists.

... или я не так понял?

Answer 5

Я собираюсь продолжить ответ Кевина с хорошим решением на основе linq.

Исходный код эффективно рассчитал двумерный логический массив, указывающий, существовала ли координата в myList в x и y координатах для каждого элемента массива.

Тест, используемый для каждого x & y, можно выразить в виде лямбда-функции следующим образом:

Func<int, int, bool> original =
    (x, y) =>
        myList.Exists(item => item.XCoord == x && item.YCoord == y);

Это неэффективно, так как вызывается метод Exists, и, следовательно, список повторяется для каждой проверенной координаты x & y. Будет ли повторяться весь список или нет, зависит от того, найдено или нет совпадение. Во многих случаях совпадений не будет, поэтому весь список посещают несколько раз.

Поэтому лучше предварительно вычислить словарь словарей, чтобы определить, существует ли координата в myList для любой x & y координаты.

var xyLookup =
    (from item in myList
     group item by item.XCoord into XCoords
     select new
     {
         X = XCoords.Key,
         YLookup = (from x in XCoords
                    group x by x.YCoord into YCoords
                    select new
                    {
                        Y = YCoords.Key,
                        Coords = YCoords
                    }).ToDictionary(a => a.Y, a => a.Coords)
     }).ToDictionary(b => b.X, b => b.YLookup);

xyLookup теперь позволяет следующей лямбда-функции заменить оригинальную версию.

Func<int, int, bool> refactored =
    (x, y) =>
        xyLookup.ContainsKey(x) && xyLookup[x].ContainsKey(y);

Предварительное вычисление xyLookup занимает некоторое время, поэтому, согласно моим тестам, если у меня массив 3х3, а myList содержит 3 координаты, то оба метода примерно одинаковы. Я ожидаю, однако, что фактический размер массива и количество элементов в myList будет намного больше на практике.

Если у меня есть массив 100x100 с 10000 координат в myList, тогда xyLookup примерно в 91 раз быстрее, чем оригинальный метод.

Я люблю linq ...: -)