Вычисление разницы элементов списка

Question

На вход подается список из кортежей. Каждый кортеж содержит по два числа(int). Нужно отсеять "похожие" вхождения.

Пример. На вход подается список вида :

d = [(55, 276), (55, 277), (104, 38), (104, 39), (104, 514), (104, 515), (105, 38), (105, 514), (210, 514), (210, 515)]

Нулевой и первый элемент почти идентичны, т.е. не выполнятся условие :

(abs(d[0][0] - d[1][0]) + abs(d[0][1] - d[1][1])) <= 10

, значит первый элемент можно удалить из списка. И дальше перебором ищем и удаляем похожие элементы. На выходе будет список: [(55, 277), (105, 514), (210, 515), (105, 38)]

Есть ли вариант ускорить выполнение программы и решить задачу без двух вложенных циклов ?

def remove_similar_coordinates(data: list) -> list:
    answer = []
    length_data = len(data)
    for x in range(length_data - 1):
        flag = True
        for y in range(x+1, length_data):
            if (abs(data[x][0] - data[y][0]) + abs(data[x][1] - data[y][1])) <= 10 :
                flag = False
                break
        if flag:
            answer.append(data[x])
    if length_data > 0:
        answer.append(data[-1])
    return answer

data = [(55, 276), (55, 277), (104, 38), (104, 39), (104, 514), (104, 515), (105, 38), (105, 514), (210, 514), (210, 515)]
remove_similar_coordinates(data)

Output: [(55, 277), (105, 38), (105, 514), (210, 515)]

Answer 1

С использованием set:

d = [(55, 276), (55, 277), (104, 38), (104, 39), (104, 514), (104, 515), (105, 38), (105, 514), (210, 514), (210, 515)]


class Wr:
    def __init__(self, v):
        self.v = v

    def __eq__(self, o):
        return abs(self.v[0] - o.v[0]) + abs(self.v[1] - o.v[1]) <= 10

    def __hash__(self):
        return True


print( list(i.v for i in set( Wr(v) for v in d )) )

Добавляем оверрайд оператора =, чтобы при добавлению в сэт значения сравнивались.

Answer 2

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

Решётка

На плоскости нарисуем решётку из квадратов размера d (расстояние на котором считаем точки близкими). Точки поместим в квадраты. Заметим что если две точки отстоят не далее чем на d, то они или в одном квадрате или в двух соседних через сторону или вершину.

Если хотим для точки q отыскать близкие, нам надо просмотреть только точки из девяти квадратов, остальные точки слишком далеки.

Код

Заведём словарь в котором ключём будут координаты квадрата, значением - множество точек в квадрате. Каждую новую точку будем сравнивать со всеми точками из девяти соседних квадратов. В любом случае, после сравнения, новая точка добавляется в "свой" квадрат.

В худшем случае точку придётся сравнить с 9 * d^2 другими точками. Для d = 10 это девятьсот точек. Много, но сложность линейная, это важнее.

Эта реализация из пары близких точек пропускает первую, удаляет вторую. В исходной постановке задачи наоборот. По этому в конце есть код, который подает точки на вход задом наперед и переворачивает ответ:

points = [(55, 276), (55, 277), (104, 38), (104, 39), (104, 514),
          (104, 515), (105, 38), (105, 514), (210, 514), (210, 515)]


def dist(p1, p2):
    x1, y1 = p1
    x2, y2 = p2
    return abs(x1 - x2) + abs(y1 - y2)


def key(p, d):
    x, y = p
    return x // d, y // d


def remove_near_items(points, d):
    dataset = {}

    def check_near_items(q):
        kx, ky = key(q, d)
        for x in range(kx - 1, kx + 2):
            for y in range(ky - 1, ky + 2):
                for p in dataset.get((x, y), frozenset()):
                    if dist(q, p) <= d:
                        return True
        return False

    for p in points:
        if not check_near_items(p):
            yield p
        dataset.setdefault(key(p, d), set()).add(p)


print(*reversed(tuple(remove_near_items(reversed(points), 10))))

$ python list_item_difference.py 
(55, 277) (105, 38) (105, 514) (210, 515)

БЛОГ НА HUSL

Вычисление разницы элементов списка

Ответы (2 шт):