Лучше ли уменьшить сложность пространства или сложность времени для данной программы?

Question

Сетка подсветки: с учетом сетки NxN с набором координат лампы. Каждая лампа обеспечивает освещение каждого квадрата по оси x, каждый квадрат на их оси y и каждый квадрат, который лежит по диагонали (подумайте о королеве в шахматах). Учитывая массив координат запроса, определите, подсвечена ли эта точка или нет. Уловка при проверке запроса на все лампы, примыкающие к или к, этот запрос отключается. Диапазоны для переменных/массивов было около: 10^3 < г N < 10^9, 10^3 < лампы < 10^9, 10^3 < запросов < 10^9

Похоже, я могу получить один, но не оба. Я попытался довести это до логарифмического времени, но я не могу найти решение. Я могу уменьшить сложность пространства, но это не так быстро, экспоненциально. Где я должен сосредоточиться, скорость или пространство? Кроме того, если у вас есть какие-либо данные о том, как вы решите эту проблему, прокомментируйте.

Answer 1

Лучше ли автомобиль ехать быстро или пройти долгий путь на небольшом топливе? Это зависит от обстоятельств.

Предложение.

Во-первых, обратите внимание, что вы можете пронумеровать все диагонали, чтобы входы, например, включались, используя первую точку в качестве «источника» для nw-se и ne-sw. Диагонали по этой точке нумеруются нулями. Диагонали nw-se увеличиваются на пиксель, например, в северо-восточном направлении, и уменьшаются (отрицательные) на юго-запад. Аналогично, ne-sw пронумерованы, увеличиваясь в, например, северо-западное направление и снижение (отрицательное) на юго-восток.

С учетом источника, легко записать постоянные функции времени, которые идут от (x, y) координат до соответствующих диагональных чисел.

Теперь каждый комплект координат лампы, естественно, связан с 4 номерами: (x, y, nw-se diag #, sw-ne dag #). Вам не нужно их явно хранить. Скорее вы хотите 4 карты xMap, yMap, nwSeMap и swNeMap такие, что, например, xMap [x] создает список всех координат лампы с координатой x x, nwSeMap [nwSeDiagonalNumber (x, y)] создает список всех лампы на этой диагонали и аналогично для других карт.

Учитывая запрос, найдите соответствующие 4 списка. Из них легко справиться с соседними квадратами. Если какой-либо список длиннее 3, удаление смежных квадратов не может сделать его пустым, поэтому точка запроса подсвечивается. Если это всего лишь 3 или меньше, это постоянная операция времени, чтобы увидеть, смещены ли они.

Это решение требует, чтобы входные точки были представлены в 4 списках. Поскольку они должны быть представлены в одном списке, вы можете утверждать, что для этого алгоритма требуется только постоянный коэффициент пространства по отношению к входу. (Например, такая же стоимость, как mergesort.)

Время выполнения ожидается постоянным на точку запроса для поиска 4 хэш-таблиц.

Без особых проблем этот алгоритм можно разделить, чтобы он мог быть уменьшен с карты, если количество фонарных колодок велико.

Но может быть достаточно и проще всего запустить его на одной большой машине. С миллиардом ламповых ламп и тщательным выбором структуры данных было бы непросто реализовать с 24 байтами на лампочку на языке незапакованных структур, таких как C. Таким образом, операционная система размером 32 ГБ должна работать нормально. Для построения карт с несколькими потоками требуется некоторая синхронизация, но это делается только один раз.Запросы могут быть доступны только для чтения: синхронизация не требуется. Хорошая 10-ядерная машина должна делать миллиардные запросы менее чем за минуту.