Исправление slovazap, (текущая версия) :
Если ты точно уверен что у тебя именно здесь узкое место, и это не голос внушённой преподавателями догмы «n² - плохо», то выбирай:
Итерируемся по одному списку, при этом поддерживаем итератор по второму списку на начало диапазона key - delta. Для каждого элемента из первого списка проходимся по второму от этого итератора до key + delta. O(n) если ключи хорошо разбросаны, O(n²) в худшем случае. Если у координат разные распределения, может быть быстрее пересортировать но хорошей координате чем получить квадрат на плохой.
Строим для одного из списков структуру данных с быстрым лукапом - бинарное дерево по ключу, либо пространственная структура данных учитывающая все кординаты (32-дерево, хотя для него измерений уже многовато, rtree и другие про разбиение пространства). Проходимся, соответственно, по одному списку, лукапим быстрее чем за линию в полученной структуре. O(nlogn), причём если использовать пространственные структуры данных это будет и в худшем случае.
Примерно то же, но используем хэшмапу с расширением запроса или ответа. Берёшь в своём пятимерном пространстве дискретную сетку с ребром ячейки 2*delta. Каждый вектор попадает в одну ячейку-кубик этой сетки. delta-окрестность вектора пересекается с 32 ячейками сетки. Соответственно, можно взять хэшмапу с ключами от координат кубика, и либо записать в неё каждый вектор 32 раза, либо делать к ней 32 запроса, таким образом получая вектора в delta-окрестности заданной точки за константу. Может иметь смысл взять сетку крупнее. Это O(n) если вектора хорошо разбросаны, и O(n²) в вырожденном случае.
Видно что эффективность решений сильно зависит от распределения векторов. Если они любят кучковаться на расстояниях меньше погрешности, чтобы не получить квадрат лучше брать 2 вариант, или делать предобработку (прореживание или кластеризация, это можно за O(n) сделать, хотя это и даст неточное решение). Алсо имеет значение по какому списку итерироваться, а по какому строить структуру для лукапа, особенно если в них значительно различается распределение или размер. Алсо решения можно комбинировать, разделяя обособленные вектора и кучки.
Исправление slovazap, :
Если ты точно уверен что у тебя именно здесь узкое место, и это не голос внушённого в институте догматического «n² - плохо», то выбирай:
Итерируемся по одному списку, при этом поддерживаем итератор по второму списку на начало диапазона key - delta. Для каждого элемента из первого списка проходимся по второму от этого итератора до key + delta. O(n) если ключи хорошо разбросаны, O(n²) в худшем случае. Если у координат разные распределения, может быть быстрее пересортировать но хорошей координате чем получить квадрат на плохой.
Строим для одного из списков структуру данных с быстрым лукапом - бинарное дерево по ключу, либо пространственная структура данных учитывающая все кординаты (32-дерево, хотя для него измерений уже многовато, rtree и другие про разбиение пространства). Проходимся, соответственно, по одному списку, лукапим быстрее чем за линию в полученной структуре. O(nlogn), причём если использовать пространственные структуры данных это будет и в худшем случае.
Примерно то же, но используем хэшмапу с расширением запроса или ответа. Берёшь в своём пятимерном пространстве дискретную сетку с ребром ячейки 2*delta. Каждый вектор попадает в одну ячейку-кубик этой сетки. delta-окрестность вектора пересекается с 32 ячейками сетки. Соответственно, можно взять хэшмапу с ключами от координат кубика, и либо записать в неё каждый вектор 32 раза, либо делать к ней 32 запроса, таким образом получая вектора в delta-окрестности заданной точки за константу. Может иметь смысл взять сетку крупнее. Это O(n) если вектора хорошо разбросаны, и O(n²) в вырожденном случае.
Видно что эффективность решений сильно зависит от распределения векторов. Если они любят кучковаться на расстояниях меньше погрешности, чтобы не получить квадрат лучше брать 2 вариант, или делать предобработку (прореживание или кластеризация, это можно за O(n) сделать, хотя это и даст неточное решение). Алсо имеет значение по какому списку итерироваться, а по какому строить структуру для лукапа, особенно если в них значительно различается распределение или размер. Алсо решения можно комбинировать, разделяя обособленные вектора и кучки.
Исправление slovazap, :
Если ты точно уверен что у тебя именно здесь узкое место, и это не голос внушённого в институте догматического «n² - плохо», то выбирай:
Итерируемся по одному списку, при этом поддерживаем итератор по второму списку на начало диапазона key - delta. Для каждого элемента из первого списка проходимся по второму от этого итератора до key + delta. O(n) если ключи хорошо разбросаны, O(n²) в худшем случае.
Строим для одного из списков структуру данных с быстрым лукапом - бинарное дерево по ключу, либо пространственная структура данных учитывающая все кординаты (32-дерево, хотя для него измерений уже многовато, rtree и другие про разбиение пространства). Проходимся, соответственно, по одному списку, лукапим быстрее чем за линию в полученной структуре. O(nlogn), причём если использовать пространственные структуры данных это будет и в худшем случае.
Примерно то же, но используем хэшмапу с расширением запроса или ответа. Берёшь в своём пятимерном пространстве дискретную сетку с ребром ячейки 2*delta. Каждый вектор попадает в одну ячейку-кубик этой сетки. delta-окрестность вектора пересекается с 32 ячейками сетки. Соответственно, можно взять хэшмапу с ключами от координат кубика, и либо записать в неё каждый вектор 32 раза, либо делать к ней 32 запроса, таким образом получая вектора в delta-окрестности заданной точки за константу. Может иметь смысл взять сетку крупнее. Это O(n) если вектора хорошо разбросаны, и O(n²) в вырожденном случае.
Видно что эффективность решений сильно зависит от распределения векторов. Если они любят кучковаться на расстояниях меньше погрешности, чтобы не получить квадрат лучше брать 2 вариант, или делать предобработку (прореживание или кластеризация, это можно за O(n) сделать, хотя это и даст неточное решение). Алсо имеет значение по какому списку итерироваться, а по какому строить структуру для лукапа, особенно если в них значительно различается распределение или размер. Алсо решения можно комбинировать, разделяя обособленные вектора и кучки.
Исправление slovazap, :
Выбирай:
Итерируемся по одному списку, при этом поддерживаем итератор по второму списку на начало диапазона key - delta. Для каждого элемента из первого списка проходимся по второму от этого итератора до key + delta. O(n) если ключи хорошо разбросаны, O(n²) в худшем случае.
Строим для одного из списков структуру данных с быстрым лукапом - бинарное дерево по ключу, либо пространственная структура данных учитывающая все кординаты (32-дерево, хотя для него измерений уже многовато, rtree и другие про разбиение пространства). Проходимся, соответственно, по одному списку, лукапим быстрее чем за линию в полученной структуре. O(nlogn), причём если использовать пространственные структуры данных это будет и в худшем случае.
Примерно то же, но используем хэшмапу с расширением запроса или ответа. Берёшь в своём пятимерном пространстве дискретную сетку с ребром ячейки 2*delta. Каждый вектор попадает в одну ячейку-кубик этой сетки. delta-окрестность вектора пересекается с 32 ячейками сетки. Соответственно, можно взять хэшмапу с ключами от координат кубика, и либо записать в неё каждый вектор 32 раза, либо делать к ней 32 запроса, таким образом получая вектора в delta-окрестности заданной точки за константу. Может иметь смысл взять сетку крупнее. Это O(n) если вектора хорошо разбросаны, и O(n²) в вырожденном случае.
Видно что эффективность решений сильно зависит от распределения векторов. Если они любят кучковаться на расстояниях меньше погрешности, чтобы не получить квадрат лучше брать 2 вариант, или делать предобработку (прореживание или кластеризация, это можно за O(n) сделать, хотя это и даст неточное решение). Алсо имеет значение по какому списку итерироваться, а по какому строить структуру для лукапа, особенно если в них значительно различается распределение или размер. Алсо решения можно комбинировать, разделяя обособленные вектора и кучки.
Исправление slovazap, :
Выбирай:
Итерируемся по одному списку, при этом поддерживаем итератор по второму списку на начало диапазона key - delta. Для каждого элемента из первого списка проходимся по второму от этого итератора до key + delta. O(n) если ключи хорошо разбросаны, O(n²) в худшем случае.
Строим для одного из списков структуру данных с быстрым лукапом - бинарное дерево по ключу, либо пространственная структура данных учитывающая все кординаты (32-дерево, хотя для него измерений уже многовато, rtree и другие про разбиение пространства). Проходимся, соответственно, по одному списку, лукапим быстрее чем за линию в полученной структуре. O(nlogn), причём если использовать пространственные структуры данных это будет и в худшем случае.
Примерно то же, но используем хэшмапу с расширением запроса или ответа. Берёшь в своём пятимерном пространстве дискретную сетку с ребром ячейки 2*delta. Каждый вектор попадает в одну ячейку-кубик этой сетки. delta-окрестность вектора пересекается с 32 ячейками сетки. Соответственно, можно взять хэшмапу с ключами от координат кубика, и либо записать в неё каждый вектор 32 раза, либо делать к ней 32 запроса, таким образом получая вектора в delta-окрестности заданной точки за константу. Может иметь смысл взять сетку крупнее. Это O(n) если вектора хорошо разбросаны, и O(n²) в вырожденном случае.
Видно что эффективность решений сильно зависит от распределения векторов. Если они любят кучковаться на расстояниях меньше погрешности, чтобы не получить квадрат лучше брать 2 вариант, или делать предобработку (прореживание или кластеризация, это можно за O(n) сделать). Алсо имеет значение по какому списку итерироваться, а по какому строить структуру для лукапа, особенно если в них значительно различается распределение или размер.
Исправление slovazap, :
Выбирай:
Итерируемся по одному списку, при этом поддерживаем итератор по второму списку на начало диапазона key - delta. Для каждого элемента из первого списка проходимся по второму от этого итератора до key + delta. O(n) если ключи хорошо разбросаны, O(n²) в худшем случае.
Строим для одного из списков структуру данных с быстрым лукапом - бинарное дерево по ключу, либо пространственная структура данных учитывающая все кординаты (32-дерево, хотя для него измерений уже многовато, rtree и другие про разбиение пространства). Проходимся, соответственно, по одному списку, лукапим быстрее чем за линию в полученной структуре. O(nlogn), причём если использовать пространственные структуры данных это будет и худшем случае.
Примерно то же, но используем хэшмапу с расширением запроса или ответа. Берёшь в своём пятимерном пространстве дискретную сетку с ребром ячейки 2*delta. Каждый вектор попадает в одну ячейку-кубик этой сетки. delta-окрестность вектора пересекается с 32 ячейками сетки. Соответственно, можно взять хэшмапу с ключами от координат кубика, и либо записать в неё каждый вектор 32 раза, либо делать к ней 32 запроса, таким образом получая вектора в delta-окрестности заданной точки за константу. Может иметь смысл взять сетку крупнее. Это O(n) если вектора хорошо разбросаны, и O(n²) в вырожденном случае.
Видно что эффективность решений сильно зависит от распределения векторов. Если они любят кучковаться на расстояниях меньше погрешности, чтобы не получить квадрат лучше брать 2 вариант, или делать предобработку (прореживание или кластеризация, это можно за O(n) сделать). Алсо имеет значение по какому списку итерироваться, а по какому строить структуру для лукапа, особенно если в них значительно различается распределение или размер.
Исправление slovazap, :
Выбирай:
Итерируемся по одному списку, при этом поддерживаем итератор по второму списку на начало диапазона key - delta. Для каждого элемента из первого списка проходимся по второму от этого итератора до key + delta. O(n) если ключи хорошо разбросаны, O(n²) в худшем случае.
Строим для одного из списков структуру данных с быстрым лукапом - бинарное дерево по ключу, либо пространственная структура данных учитывающая все кординаты (32-дерево, хотя для него измерений уже многовато, rtree и другие про разбиение пространства). Проходимся, соответственно, по одному списку, лукапим быстрее чем за линию в полученной структуре. O(nlogn), причём если использовать пространственные структуры данных это будет и худшем случае.
Примерно то же, но используем хэшмапу с расширением запроса или ответа. Берёшь в своём пятимерном пространстве дискретную сетку с ребром ячейки 2*delta. Каждый вектор попадает в одну ячейку-кубик этой сетки. Если дискретные координаты кубика взять в качестве ключа хэшмапы, можно получить вектора в известном кубике за константу. Для заданного вЕктора векторА в его delta-окрестности лежат либо в его же, либо в соседних кубиках (всего 32 кубика). Соответственно, нужно либо положить целевые векторы в хэшмапу 32 раза, либо сделать в неё 32 запроса. На асимптотическую сложность это не влияет, хотя вычислительно тяжело, но всегда можно взять сетку покрупнее. Это O(n) если вектора хорошо разбросаны, и O(n²) в вырожденном случае.
Видно что эффективность решений сильно зависит от распределения векторов. Если они любят кучковаться на расстояниях меньше погрешности, чтобы не получить квадрат лучше брать 2 вариант, или делать предобработку (прореживание или кластеризация, это можно за n сделать). Алсо имеет значение какой список брать основным, а в какой лукапить, если в них значительно различается распределение или размер.
Исправление slovazap, :
Выбирай:
Итерируемся по одному списку, при этом поддерживаем итератор по второму списку на начало диапазона key - delta. Для каждого элемента из первого списка проходимся по второму от этого итератора до key + delta. O(n) если ключи хорошо разбросаны, O(n²) в худшем случае.
Строим для одного из списков структуру данных с быстрым лукапом - бинарное дерево по ключу, либо пространственная структура данных учитывающая все кординаты (32-дерево, хотя для него измерений уже многовато, rtree и другие про разбиение пространства). Проходимся, соответственно, по одному списку, лукапим быстрее чем за линию в полученной структуре. O(nlogn), причём если использовать пространственные структуры данных это будет и худшем случае.
Примерно то же, но используем хэшмапу с расширением запроса или ответа. Берёшь в своём пятимерном пространстве дискретную сетку с ребром ячейки 2*delta. Каждый вектор попадает в одку ячейку-кубик этой сетки. Если дискретные координаты кубика взять в качестве ключа хэшмапы, можно получить вектора в известном кубике за константу. Для заданного вЕктора векторА в его delta-окрестности лежат либо в его же, либо в соседних кубиках (всего 32 кубика). Соответственно, нужно либо положить целевые векторы в хэшмапу 32 раза, либо сделать в неё 32 запроса. На асимптотическую сложность это не влияет, хотя вычислительно тяжело, но всегда можно взять сетку покрупнее. Это O(n) если вектора хорошо разбросаны, и O(n²) в вырожденном случае.
Видно что эффективность решений сильно зависит от распределения векторов. Если они любят кучковаться на расстояниях меньше погрешности, чтобы не получить квадрат лучше брать 2 вариант, или делать предобработку (прореживание или кластеризация, это можно за n сделать). Алсо имеет значение какой список брать основным, а в какой лукапить, если в них значительно различается распределение или размер.
Исходная версия slovazap, :
Выбирай:
Итерируемся по одному списку, при этом поддерживаем итератор по второму списку на начало диапазона key - delta. Для каждого элемента из первого списка проходимся по второму от этого итератора до key + delta. O(n) если ключи хорошо разбросаны, O(n²) в худшем случае.
Строим для одного из списков структуру данных с быстрым лукапом - бинарное дерево по ключу, либо пространственная структура данных учитывающая все кординаты (octree, хотя для него измерений уже многовато, rtree и другие). Проходимся, соответственно, по одному списку, лукапим быстрее чем за линию в полученной структуре. O(nlogn), причём если использовать пространственные структуры данных это будет и худшем случае.
Примерно то же, но используем хэшмапу с расширением запроса или ответа. Берёшь в своём пятимерном пространстве дискретную сетку с ребром ячейки 2*delta. Каждый вектор попадает в одку ячейку-кубик этой сетки. Если дискретные координаты кубика взять в качестве ключа хэшмапы, можно получить вектора в известном кубике за константу. Для заданного вЕктора векторА в его delta-окрестности лежат либо в его же, либо в соседних кубиках (всего 32 кубика). Соответственно, нужно либо положить целевые векторы в хэшмапу 32 раза, либо сделать в неё 32 запроса. На асимптотическую сложность это не влияет, хотя вычислительно тяжело, но всегда можно взять сетку покрупнее. Это O(n) если вектора хорошо разбросаны, и O(n²) в вырожденном случае.
Видно что эффективность решений сильно зависит от распределения векторов. Если они любят кучковаться на расстояниях меньше погрешности, чтобы не получить квадрат лучше брать 2 вариант, или делать предобработку (прореживание или кластеризация, это можно за n сделать). Алсо имеет значение какой список брать основным, а в какой лукапить, если в них значительно различается распределение или размер.