Как проверить, эффективно ли прямоугольные образуют декартовы координаты? - PullRequest
Новая
       8

Как проверить, эффективно ли прямоугольные образуют декартовы координаты?

6 голосов
/ 18 мая 2011

Ситуация выглядит следующим образом:

  • Имеется N массивов.
  • В каждом массиве (0..N-1) есть (x, y) кортежей (декартовых)координаты) сохранено
  • Длина каждого массива может быть разной

Я хочу извлечь подмножество комбинаций координат, которые составляют полный треугольник размера N. Другими словами;все декартовы координаты смежны друг с другом.

Пример: 

findRectangles({
    {*(1,1), (3,5), (6,9)}, 
    {(9,4), *(2,2), (5,5)}, 
    {(5,1)},
    {*(1,2), (3,6)}, 
    {*(2,1), (3,3)}
})

дает следующее: 

[(1,1),(1,2),(2,1),(2,2)],
..., 
...(other solutions)...

Никакие две точки не могут быть получены из одного набора.

Сначала я только вычислил декартово произведение, но это быстро становится невозможным (на данный момент у меня есть 18 массивов точек, каждый из которых приблизительно содержит 10 различных координат).

Ответы [ 2 ]

5 голосов
/ 18 мая 2011

Вы можете использовать хеширование с большим эффектом: 

hash each point (keeping track of which list it is in)
for each pair of points (a,b) and (c,d):
    if (a,d) exists in another list, and (c,b) exists in yet another list:
        yield rectangle(...)

Когда я говорю exists, я имею в виду сделать что-то вроде: 

hashesToPoints = {}
for p in points:
    hashesToPoints.setdefault(hash(p),set()).add(p)
for p1 in points:
    for p2 in points:
        p3,p4 = mixCoordinates(p1,p2)
        if p3 in hashesToPoints[hash(p3)] and {{p3 doesn't share a bin with p1,p2}}:
            if p4 in hashesToPoints[hash(p4)] and {{p4 doesn't share a bin with p1,p2,p3}}:
                yield Rectangle(p1,p2)

ЭтоO(#bins^2 * items_per_bin^2) ~ 30000, что очень быстро в вашем случае с 18 массивами и 10 items_per_bin - намного лучше, чем внешний подход к продукту, который ... намного хуже с O(items_per_bin^#bins) ~ 3 трлн.=)

младший sidenote:

Вы можете уменьшить как основание, так и показатель степени в своих вычислениях, сделав несколько проходов "сокращения".например, 

remove each point that is not corectilinear with another point in the X or Y direction
then maybe remove each point that is not corectilinear with 2 other points, in both X and Y direction

Вы можете сделать это, отсортировав по X-координате, повторите для Y-координаты, по O(P log(P)) времени по количеству точек.Вы можете сделать это одновременно с хешированием.Если плохой парень организует ваш вклад, он может заставить эту оптимизацию вообще не работать.Но в зависимости от вашего дистрибутива вы можете увидеть значительное ускорение.

0 голосов
/ 19 мая 2011

Пусть XY будет вашим набором массивов. Создайте два новых набора X и Y, где X равен XY со всеми массивами, отсортированными по координате x, а Y равен XY со всеми массивами, отсортированными по координате y.

  • Для каждой точки (x0, y0) в любом из массивов в X: найдите каждую точку (x0, y1) с той же координатой x и другой координатой y в остальных массивах из X
  • Для каждой такой пары точек (если она существует): найдите Y для точек (x1, y0) и (x1, y1)

Пусть C будет размером самого большого массива. Тогда сортировка всех наборов занимает время O (N * C * log (C)). На шаге 1 для поиска единственной точки совпадения требуется время O (N * log (C)), поскольку все массивы в X отсортированы. Поиск всех таких точек находится в O (C * N), так как в целом существует не более C * N баллов. Шаг 2 занимает время O (N * log (C)), так как Y отсортирован.

Следовательно, общее асимптотическое время выполнения находится в O (C * N ^ 2 * log (C) ^ 2).

Для C == 10 и N == 18 вы получите примерно 10.000 операций. Умножьте это на 2, так как я снизил этот коэффициент из-за обозначения Big-O.

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

Также обратите внимание, что это время выполнения в худшем случае, когда все прямоугольники начинаются с одной и той же x-координаты. В среднем случае вы, вероятно, будете делать это намного лучше.

...