Wataru

Если реализовывать самостоятельно, то самый эффективный вариант - использовать структуру бор. Правда, тут надо чтобы все файлы влезли в память.

Десятки гигабайт - это не тот объем где стоит использовать распределенную ферму. Вы копируя файлы туда-сюда больше времени потратите, чем на обработку на одной машине.

Если памяти на компьютере не 64-128гб, и писать что-то не хочется, то можно файл отсортировать и потом подсчитать там повторения за один проход. Это будет чуть медленнее теоретически оптимального решения. rPman уже привел линуксовую команду, которая это делает. Только разбивать на части просто так нельзя, надо чтобы одинаковые строки остались вместе, иначе собирать ответ с нескольких кусков надо будет хитро. Но это и не надо в вашей задаче.

Если же вы что-то распределенное все-таки хотите использовать, то ваша задача - это фактически обучающий пример для всяких map-reduce фреймворков типа hadoop. Но там придется повозиться с установкой и настройкой этого добра и код с примера скопировать.

Без теории тут никак.
Тут 2 варианта: или стройте конечный недетерменированный автомат (с эпсилон переходами), который соответствует этому регулярному выражению и дальше применяйте стандартный алгоритм проверки. что автомат принимает заданную строку. Или второй вариант: пишите динамическое программирование "соответствует ли вот этот префикс заданной строки вот этому префиксу регулярного выражения".

Конечный автомат будет и побыстрее работать и памяти меньше требовать.

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

Эта задача решается алгоритмом "сканирующая прямая".

Представьте что у есть вертикальная линия, которая двигатеся слева-направо непрерывно. В каждый момент времени на прямой могут появиться какие-то прямоугольники, могут закончиться какие-то прямоугольники или ничего не поменяется - в этот момент прямая какие-то прямоугольники пересекает.

Надо взять какую-то хитрую структуру данных, чтобы хранить все открытые (в данном случае - последние закрытые) прямоугольники на прямой. В моменты открытия/закрытия прямоугольников надо структуру данных обновлять или опрашивать.

Тут подойдет что-нибудь вроде std::set в C++ - структура хранящая упорядоченное множество объектов, с доступом и изменением за логарифм, умеющая искать ближайший к заданному значению слева и справа (lower_bound, upper_bound). Хранить в ней мы будем вертикальные отрезки, помеченные номерами их прямоугольникв. Не знаю ее аналоги в других языках - нужно что-то реализованное или на binary search tree, или на skip list.

Когда прямоугольник открывается надо посмотреть, с какими отрезками в set данный отрезок пересекается. Все эти отрезки надо добавить в ответ, удалить полностью покрываемые новым отрезком, а торчащие из него укоротить. Таким образом мы будем поддерживать множество "видимых" отрезков с прямой - ближайших к ней слева.

В этой задаче можно забить на правые границы прямоугольников и на их ширину (раз нет пересечений). Соседями каждого отрезка - левого края будут ближайшие к нему левые края каких-то прямоугольников.
Поэтому вам надо получить все отрезки заданные в виде {x, y1, y2, id} и отсортировать их (сначала по x, потом по y). Потом в этом порядке их обходите и применяйте новый отрезок к структуре данных. Все удаляемые отрезки + 2 пересекающихся сверху и снизу пойдут в список соседних для нового отрезка.

Этот алгоритм за O(n log n) получит всех соседей для всех прямоугольников.
Это что-то похожее вот на эту задачку с leetcode

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

Можно через vector::reserve задать ему необходимый объем. Тогда он сразу же выделит все память и, если вы не будете в него класть больше этого размера элементы, он не будет перевыделять память вообще.

Еще можно изменить ваш дизайн. Например, вместо vector использовать list, итераторы в котором не портятся от добавления. Или хранить вместо итераторов/указателей на элементы в векторе индексы.

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

Разбейте задачу на подзадачи:

1) Проверить, что данный элемент надо удалить
1.1) Проверить, что элемент не уникальный
1.2) Проверить, что элемент - не первый среди одинаковых (один-то его надо оставить)
2) Удалить элемент из массива дописав 0 в конце.

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

Матрицы используются для записи преобразований. Надо домножать на них вектор из координат точки - получится новый вектор, который и будет результатом преобразования. Любое линейное преобразование можно записать в виде матрицы.

Четвертая координата позволяет записывать одной матрицей повороты/растяжения и сдвиги. Если у вас матрица 3x3 (не "трехмерная" - у нее все так же есть только ширина и высота), то точка (0, 0, 0) всегда останется (0, 0, 0). Ведь на что 0 не домножай - останется 0. Поэтому матрицами 3x3 можно записать только повороты и сжатия, но не сдвиги.

Поэтому вводят фиктивное четвертое измерение w. При этом удобно считать, что координаты точки (x, y, z, w) - Это (x/w, y/w, z/w). Это еще иногда называют однородными координатами. Еще один плюс этого объекта в том, что им можно описать точки на бесконечности (когда w = 0).

Вот тут уже можно составить линейное преобразование (т.е. взять матрицу), которое оставляет w нетронутым, но использует его для сдвига:

x' = a11*x + a12*y + a13*z + a14*w
...
w' = w

Вот в a14 - как раз и находится сдвиг по оси X.

Надо смотреть, что там компилятор нагенерировал.

Создайте 2 функции, которые отличаются только вот в этих вот местах.
Вставьте код в https://godbolt.org/

Смотрите ассемблерный код для двух функций.

Может, срабатывает strict aliasing. Видя тип T сомпилятор понимает, что эта переменная не может быть изменена какими-то другими std::byte в соседнем коде и может, например, пропустить загрузку-выгрузку данных в регистр из памяти.

Может вообще что-то другое.

Единственный вариант разобраться - это смотреть на ассемблерный код функций, которые вы и сравниваете. Не каких-то кусков, оттуда надерганных, а функций целиком.

Проблема вот тут:

parent.resize(++n);
glub.resize(n);
for (int i = 1; i <= n; i++) {

Выход за границу массива. Неопределенное поведение.
Вы выделяете массивы длины n (увеличенного на 1) и потом проходитесь от 1 до n (увеличенного на 1). Но ведь индексы в массиве только до n-1.

Правильно так:

parent.resize(n+1);
glub.resize(n+1);
for (int i = 1; i <= n; i++) {

unordered_map<ID, Material>

Решение попроще, за квадрат:
Пропустили ведущие и trailing пробелы, проверили, что строка начианется с "min" (иначе ничего делать не надо, возвращаем все).
Потом заведите счетчик открытых скобок, пройдитесь до первой запятой внутри одной пары скобок. Рекурсивно преобразуйте левую часть, добавьте к этому min и результат рекурсивного преобразования правой части (от зяпятой до закрывающей скобки в конце).

Решение поумнее, за линию:

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

Итак, функция, опять же, проверяет, что есть min. Если нет - возвращает всю строку до первой "," или непарной ")" - нужен счетчик открытых скобок.
В противном случае, пропускает "min", "(". Рекурсивно преобразовывает от этой позиции. Потом смотрит, что после позиции, которую вернула рекурсивная функция, лежит ",". Иначе - ошибка. Добавляет min к ответу, Рекурсивно преобразовывает оставшееся и добавляет к ответу. Проверяет, что дальше после позиции где закончила обработку рекурсивная функция лежит ")". Возвращает следующую за этим позицию.

Можно не возвращать преобразованную строку, а сразу все функции могут просто дописывать свой ответ в какое-то одно место. А возвращать int - индекс конца. Ну, или длину обработанной части строки - так даже понятнее.