Какой самый быстрый способ вернуть координаты x, y, которые присутствуют как в списке A, так и в списке B?

Question

У меня есть два списка (список A и список B) координат x, y, где 0

Я думал о том, чтобы представить списки в виде двух битов и делать их поразрядно и, возможно,?

Список А содержит около 1000 записей и изменений.возможно один раз каждые 10 000 запросов.Список B будет сильно отличаться по длине и будет отличаться при каждом проходе.

РЕДАКТИРОВАТЬ: я должен отметить, что ни одна координата не будет в списках дважды;Например, 1,1 не может быть в списке A более одного раза.

Answer 1

Представляет (x, y) как одно 24-битное число, как описано в комментариях.

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

Для каждого B выполните бинарный поиск в списке. Поскольку размер A составляет около 1000 элементов, для проверки членства вам потребуется не более 10 целочисленных сравнений (в худшем случае).

Если у вас есть немного больше памяти (около 2 МБ) для игры, вы можете создать битовый вектор для поддержки всех возможных 24-битных чисел, а затем выполнить однобитовую операцию для каждого элемента, чтобы проверить на членство. Таким образом, A будет представлен одним 2 ^ 24-битным числом с набором битов, если значение есть (иначе 0). Чтобы проверить членство, вы просто должны использовать соответствующий бит и операцию.

Answer 2

Это легко, если вы реализуете предикат STL, который упорядочивает две пары (т.е. return (R.x < L.x || (R.x==L.x && R.y < L.y). Затем вы можете вызвать std::list::sort, чтобы упорядочить их, и std::set_intersection, чтобы найти общие элементы. Не нужно писать алгоритмы

Answer 3

Поскольку A довольно статичен, вы можете рассмотреть вопрос о построении структуры запроса и проверке всех элементов в B на предмет их наличия в A. Одним из примеров будет std :: set> A, и вы можете запросить как A.find (element_from_b)! = A.end () ...

Таким образом, общее время выполнения - наихудший случай O (b log a) (где b - количество элементов в B и a соответственно).Также обратите внимание, что, поскольку a всегда около 10000, log a в основном является константой.

Answer 4

Определение порядка на основе их лексикографического порядка (сортировка сначала по x, затем по y). Сортируйте оба списка по порядку за O (n log n), где n - это большее количество элементов в каждом списке. Установите указатель на первый элемент каждого списка и продвиньте указатель на меньший элемент; когда указатели ссылаются на элементы с одинаковым значением, поместите их в набор (чтобы избежать множественности в каждом списке). Эта последняя часть может быть выполнена за время O (n) (или O (m log m), где m - количество элементов, общих для обоих списков).

Обновление (на основе комментариев ниже и редактирования выше): поскольку ни одна точка не появляется более одного раза в каждом списке, вы можете использовать список или вектор или деку, чтобы удерживать точки, общие для обеих или некоторых другие (амортизированные) вставки с постоянным временем, реализующие временные характеристики O (n) независимо от количества общих элементов.

Answer 5

Поместите координаты списка A в некоторый набор (вероятно, хэш, bst или кучу), и вы сможете быстро увидеть, присутствует ли координата из списка B.

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

Хэши хорошо сообщают вам, если в них что-то есть, хотя, в зависимости от того, как это реализовано, могут плохо работать при попытке найти то, чего в нем нет.

bst и heaps одинаково хороши для того, чтобы сообщать вам, есть ли в них что-то или нет, но не работают теоретически так же хорошо, как хэши, когда в них что-то есть.

Answer 6

Я думаю, что хэширование - ваш лучший выбор.

// Psuedocode:

1. INPUT: два списка, каждый с координатами (x, y)
2. найди список, который длиннее, назови его A
3. хеширует каждый элемент в A
4. перейти в другой список, назовите его B
5. хешируйте каждый элемент в B и найдите его в таблице.
6. если есть совпадение, вернуть / сохранить (x, y) где-нибудь
7. повторить # 4 до конца

Предполагая, что длина A равна m, а длина B равна n, время выполнения O (m + n) -> O (n)

Answer 7

Если я правильно понимаю, вы хотите общие координаты в X и Y - пересечение (наборы) Листинга A и B?Если вы используете STL:

#include <vector>
#include <std>
using namespace std;
// ...
set<int> a; // x coord (assumed populated elsewhere)
set<int> b; // y coord (assumed populated elsewhere)
set<int> in; // intersection
// ...
set_intersection(a.begin(), a.end(), b.begin(), b.end(), insert_iterator<set<int> >(in,in.begin()));

Answer 8

Это проблема, которая просто кричит мне: " Bloom Filter ".