Оптимизация выбора квадранта

Question

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

private int Quadrant(Point p)
{
    if (p.X >= Center.X)
        return p.Y >= Center.Y ? 0 : 3;
    return p.Y >= Center.Y ? 1 : 2;
}

Center имеет тип Point, координаты ints. Да, я запустил профиль кода, и нет, это не преждевременная оптимизация.

---

Поскольку это используется только для внутреннего использования, я полагаю, что мои квадранты не имеют в декартовом порядке , если они находятся в диапазоне 0-3.

Answer 1

Самый быстрый способ в C / C ++:

(((unsigned int)x >> 30) & 2) | ((unsigned int)y >> 31)

(30/31 или 62/63, в зависимости от размера int)Это даст квадранты в порядке 0, 2, 3, 1.

Правка для Л.Бушкина:

(((unsigned int)(x - center.x) >> 30) & 2) | ((unsigned int)(y-center.y) >> 31)

Answer 2

Мне только что сообщили о решении, которое дает 0,1,2,3 результатов квадранта, упорядоченных правильно:

#define LONG_LONG_SIGN (sizeof(long long) * 8 - 1)

double dx = point.x - center.x;
double dy = point.y - center.y;

long long *pdx = (void *)&dx;
long long *pdy = (void *)&dy;

int quadrant = ((*pdy >> LONG_LONG_SIGN) & 3) ^ ((*pdx >> LONG_LONG_SIGN) & 1);

Это решение для координат x, y двойного типа.

Я провел некоторое тестирование производительности этого метода и метода с ветвлением, как в первоначальном вопросе: мои результаты таковы: метод ветвления всегда немного быстрее (в настоящее время у меня стабильное отношение 160/180) , поэтому я предпочитаю метод ветвления, а не метод с побитовыми операциями.

---

UPDATE

Если кому-то интересно, все три алгоритма были объединены в EKA-алгоритмы C / Objective-C-репозиторий как алгоритмы "декартовой выборки квадрантов":

1. Оригинальный алгоритм ветвления
2. Битовый алгоритм @ruslik из принятого ответа.
3. Альтернатива побитовая, предложенная одним из моих коллег, которая немного медленнее второго алгоритма, но возвращает квадранты в правильном порядке.

Все алгоритмы оптимизированы для работы с точками двойного типа.

Тестирование производительности показало, что в целом первый алгоритм ветвления является победителем в Mac OS X, хотя на машине с Linux мы видели, что второй алгоритм работает немного быстрее, чем алгоритм ветвления.

Итак, общий вывод - придерживаться алгоритма ветвления, потому что побитовые версии не дают никакого увеличения производительности.

Answer 3

Я не знаю, что вы можете сделать этот код значительно быстрее в C #.Однако то, что вы можете сделать, это посмотреть, как вы обрабатываете точки, и посмотреть, сможете ли вы избежать ненужных вызовов этого метода.Возможно, вы могли бы создать структуру QuadPoint, в которой хранится квадрант, в котором находится точка (после того, как вы ее вычислили один раз), чтобы вам не пришлось делать это снова.что делает ваш алгоритм, и возможно ли сохранить / запомнить информацию о квадранте.Если каждая точка абсолютно уникальна, это, очевидно, не поможет.

Answer 4

Моей первой попыткой было бы избавиться от вложенного условного выражения.

int xi = p.X >= Center.X ? 1 : 0;
int yi = p.Y >= Center.Y ? 2 : 0;
int quadrants[4] = { ... };
return quadrants[xi+yi];

Поиск в массиве в квадрантах является необязательным, если разрешено перенумеровывать квадранты. Мой код все еще нуждается в двух сравнениях, но они могут выполняться параллельно.

Заранее прошу прощения за любые ошибки в C #, так как обычно кодирую C ++.

---

Возможно, что-то более эффективное возможно, когда две беззнаковые 31-битные координаты хранятся в 64-битной переменной без знака.

// The following two lines are unnecessary
// if you store your coordinated in unsigned longs right away
unsigned long Pxy = (((unsigned long)P.x) << 32) + P.y;
unsigned long Centerxy = (((unsigned long)Center.x) << 32) + Center.y;

// This is the actual calculation, only 1 subtraction is needed.
// The or-ing with ones hast only to be done once for a repeated use of Centerxy.
unsigned long diff = (Centerxy|(1<<63)|(1<<31))-Pxy;
int quadrant = ((diff >> 62)&2) | ((diff >> 31)&1);

---

Сделав шаг назад, возможно другое решение. Не разбивайте структуру данных сразу на сектора, а попеременно в обоих направлениях. Это также делается в соответствующем Kd-дереве