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

Ситуация такова:

  • Есть 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 разных координат).

    Пусть 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. В среднем случае вы, вероятно, сделаете гораздо лучше, чем это.

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

     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 триллиона. знак равно


    незначительный побочный эффект:

    Вы можете уменьшить как базовую, так и экспонентов в своих вычислениях, сделав несколько проходов «обрезки». например

     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)) по количеству точек. Вы можете сделать это одновременно с хэшированием. Если плохой парень организует ваш ввод, он может сделать эту оптимизацию неработоспособной вообще. Но в зависимости от вашего распределения вы можете увидеть значительное ускорение.