ПрограммированиеФорумОбщее

Вертикальная ось симметрии

Страницы: 1 2 Следующая »
#0
0:38, 25 апр 2019

Попалась такая задачка на одном тесте, проверить существует ли вертикальная ось симметрии у множества точек на плоскости. Я ее решил сортировкой по X и проверкой среднего у минимума и максимум (соответственно конец и начало массива) на равенство оси симметрии. На вскидку получается сложность как O(N/2+log(N)*N)

Мне сказали что можно быстрее если использовать hash_map, но до меня совершенно не дошло куда его вставлять в данной задаче. Есть у кого идеи? Или меня динамили?

Предположим, решение: найти первые минимум и максимум это O(N), а затем через их среднее автоматически считать для больших X зеркальную точку и заполнять hash_map, таким образом складывать пары и отбрасывать точки на оси симметрии, тоже O(N). Итого О(N+N). Но насколько это по факту производительности быстрее если hash_map заполняется двумя значениями на ключ, только при существовании оси симметрии?

#1
13:25, 25 апр 2019

ищешь минимум и максимум, отсюда получаешь центр симметрии. далее заталкиваешь в хешмеп все точки, лежащие по одну сторону от плоскости симметрии. далее пробегаешься по точкам по вторую сторону плоскости и проверяешь, что их зеркальное отображение есть в хешмепе. линейная сложность average case.

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

#2
14:21, 25 апр 2019

Suslik
Да я как раз привел пример с одной хешмапой в нуль посте, но мне не кажется это по производительности выигрышным, насколько я знаю тут в основном на заполнение хешмапы все время уйдет. А с сортировкой даже память выделять не понадобиться.

В целом задача даже не на знание хешмапы, больше смахивает на тест сообразительности.

#3
18:07, 25 апр 2019

https://rextester.com/ZTUZP79750
Как можно заметить, время в расчёте на 1 элемент в версии с hash_map тоже увеличивается.

#4
18:10, 25 апр 2019

Да, у меня одномерный пример, но вроде суть общая.
Т. е. какбы линейный алгоритм по идее с какого-то момента быстрее n*log(n)-ного, но на практичных размерах вектор заруливает.

#5
18:28, 25 апр 2019

FordPerfect
> Да, у меня одномерный пример, но вроде суть общая.
Да не суть, чуть условие сортировки (можно даже пузырьковую на один проход по Y сделать) и ключ подправить - будет двухмерный.

Я так понял это на удаленной машине запускается, потому что по всем тестам выигрывает vector кроме 2 элементов (все время одинаково). Тестирующий утверждал что hash_map должен как раз таки на больших массивах рулит, тут видим все наоборот.

#6
20:58, 25 апр 2019

foxes
> Тестирующий утверждал что hash_map должен как раз таки на больших массивах
> рулит, тут видим все наоборот
В том примере, который предоставил FordPerfect под капотом у unorederd_map всё та же логарифмическая сложность (из-за переаллокаций хешмапы и рехеша). Поэтому в том примере unorederd_map никогда не обгонит вектор. Чтобы избавится от логарифма - нужно делать reserve().

Но самый фокус в том, что тут впринципе ни хешмапа ни сортировка не нужна. Узнать есть ось симметрии или нет можно просто в 2 прохода по исходному вектору.

Вот "прокачанный" результат:
https://rextester.com/CWNGU40325
Здесь уже видно, что с увеличением количества данных разрыв между сортировкой на векторе и unordered_map сокращается. Вот только ограничения rextester не дают увидеть момент, когда unoredered_map побеждает.
Ну и добавил solve3 который всех доминирует.

upd. Хотя не, не видно что unordered_map даже с reserve обгоняет вектор, но в целом reserve ускорил работу хешмапы раза в 2. Возможно потому, что unordered_map использует closed addressing на линкед листах, и логарифм возникает на менеджере памяти. Поидее хешмапа с open_addressing и с reserve должна все же обогнать вектор в песпективе.

#7
21:48, 25 апр 2019

MrShoor
> под капотом у unorederd_map всё та же логарифмическая сложность (из-за переаллокаций хешмапы и рехеша)
Это ещё почему?
> Search, insertion, and removal of elements have average constant-time complexity.
https://en.cppreference.com/w/cpp/container/unordered_map/insert

> Но самый фокус в том, что тут впринципе ни хешмапа ни сортировка не нужна. Узнать есть ось симметрии или нет можно просто в 2 прохода по исходному вектору.
> Ну и добавил solve3 который всех доминирует.
Контрпример: [-10,-5,-10,-5,+3,+6,+12,+9].

#8
21:55, 25 апр 2019

FordPerfect
> Это ещё почему?
http://www.cplusplus.com/reference/unordered_map/unordered_map/max_load_factor/

The container uses the value of max_load_factor as the threshold that forces an increase in the number of buckets (and thus causing a rehash).

> Контрпример: [-10,-5,-10,-5,+3,+6,+12,+9].
Хм... действительно, перепутал необходимое и достаточное условие. Бинарным сложением делать нельзя. :)

#9
22:11, 25 апр 2019

MrShoor
> The container uses the value of max_load_factor as the threshold that forces an increase in the number of buckets (and thus causing a rehash).
И? С чего бы это давало логарифмическую сложность?

https://en.cppreference.com/w/cpp/container/unordered_map/insert

5-6) Average case: O(N), where N is the number of elements to insert. Worst case: O(N*size()+N)

#10
0:20, 26 апр 2019

FordPerfect
> И? С чего бы это давало логарифмическую сложность?
Когда происходит рехеш - все элементы копируются. Рехеш происходит когда мы переваливаем max_load_factor. И тут все зависит от стратегии роста размера хешмапы. Если они выделяют в 2 раза больше бакетов, то рехеши будут при 2, при 4, при 8 и т.д. бакетов. Что и есть тот самый логарифм.

> 5-6) Average case: O(N), where N is the number of elements to insert. Worst case: O(N*size()+N)
Это с учетом того, что рехеш не произойдет.

#11
1:23, 26 апр 2019

MrShoor
> Что и есть тот самый логарифм.
Нет, это O(N). Полное количество копируемых данных примерно равно удвоенному конечному размеру.
Количество рехешей, действительно log2(N), но этот логарифм входит слагаемым, а не множителем.

#12
1:23, 26 апр 2019

MrShoor
> Если они выделяют в 2 раза больше бакетов, то рехеши будут при 2, при 4, при 8 и т.д. бакетов. Что и есть тот самый логарифм.
Нет же. При этой стратегии средняя сложность линейна от количества вставок, так же, как и у vector.push_back().

> Это с учетом того, что рехеш не произойдет.
Вот серьёзно - с чего ты это взял?

#13
2:32, 26 апр 2019

}:+()___ [Smile]
FordPerfect
Да, понял. Спасибо за объяснение, действительно логарифм там не множитель, а слагаемое.
Тогда какие у вас идеи, почему у хешмапы сложность не линейная?
Вот третьим столбцом вывел время на обработку одного элемента:
https://rextester.com/ZYFS28352
На 1024 элемента ушло 57.617 наносекунд на элемент
А при 1048576 элементов на каждый элемент ушло уже по 203.274 наносекунды.

#14
3:02, 26 апр 2019

MrShoor
> Тогда какие у вас идеи, почему у хешмапы сложность не линейная?
Я изначально предполагал что скачки по памяти против линейного перебора не дадут выиграть хешу. Если посмотреть на оба варианта то после 16384 практически одинаково подскакивают больше чем в два раза.

Страницы: 1 2 Следующая »
ПрограммированиеФорумОбщее

Тема в архиве.