Wataru

Как компилируете-то? Пока похоже, что вы пытаетесь собрать исполнительный файл прямо из main.cpp, где через include обхявлен класс, но определение все лежит в другом модуле трансляции, который вообще в команде не учавствует.

Или пользуйтесь системой сборки (cmake, visual studio, ninja, и т.д...) или вручную запускайте 3 команды: сделать объектник из main.cpp, сдлеать объектник из EcsSystems.cpp, собрать из объектников исполняемый файл.

Просто при обходе - нет ничего не даст.

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

Судя по комментариям, вам надо найти полное совподение поддерева: Так что поддерево вершины имеет ровно столько же точно также расставленных вершин, как и второе дерево.

Умное и быстрое решение, к сожалению, будет сложно написать без std::unordered_map. Такое решение будет работать за O(n). Самостоятельно хеш таблицу писать будет сложно. Но если без хеш таблицы, то решение будет работать также медленно, как и тупое рекурсивное прикладывание, поэтому приведу тут все решение.

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

Для нумерации форм надо рекурсивно получить номера для двух детей и потом проверить, а встречали ли вы раньше вершину с двумя такими детьми. Если да - то вы знаете ее номер. Если нет - то назначьте новый номер. Вот тут и нужена хеш таблица, она же unordered_map.

Пустые вершины всегда имеют какой-то номер, допустим, 0.

Это решение, кстати, легко адаптируется на изоморфизм - если вам можно менять местами детей. Тогда пары надо отсортировать перед проверкой. Также оно адаптируется на небинарные деревья. Тут у вас будут не пары чисел, а набор чисел.

void Match(Tree *stack, Tree *needle) {
  std::unordered_map<std::pair<int, int>, int> shapes;
  int needle_shape = ClassifyShape(needle, shapes, -1);
  ClassifyShape(stack, shapes, needle_shape);
}

int ClassifyShape(Tree *tree, std::unordered_map<std::pair<int, int>, int> &shape, int find_shape) {
  if(!tree) return 0;
  int l = ClassifyShape(tree->left);
  int r = ClassifyShape(tree->right);
  auto pat = make_pair(l, r);
  auto it =  shapes.find(pat);
  int this_shape = -1;
  if (it == shapes.end()) {
    this_shape = shapes.size();
    shapes[pat] = this_shape;
  } else {
    this_shape =  it->second;
  }
  if (this_shape == find_shape) {
    std::cout << "Found match at node " << tree->value << std::endl;
  }
  return this_shape;
}

В нивном решении надо заменить unordered_map shapes на массив пар чисел (или массив структур или два массива чисел). Циклом в нем проищите текущую пару l, r, если не нашли, то допишите в конец.

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

Но, возможно вашему преподу такое будет слишком заумно. Тогда вам нужна аккуратная рекурсивная функция сравнения:

bool Compare(Tree* a, Tree *b) {
  if (a->left && !b->left) return false;
  if (a->right && !b->right) return false;
  return (!a->left || Compare(a->left, b->left)) && (!a->right || Compare(a->right, b->right));
}

Тут все просто. Если у корней разная конфигурация детей, то деревья точно не совпали. А дальше надо чтобы рекурсивно совпали поддеревья в левых и правых детях.

А дальше вам надо рекурсивно пройтись по первому дереву и вызвать вот эту Compare для текущей вершины и корня второго дерева. Если совпало - то выводите текущую вершину.

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

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

Вот построили вы деревья для всех строк, дальше надо их попарно сравнить простым рекурсивным обходом. Если оба дерева содержат переход по какому-то символу, рукурсивно идите по нему. Если дошли до глубины N - вы нашли совпадение. Можно вообще идти пока не обломитесь и взять максимальную глубину. Такой обход обойдет дерево один раз для каждой пары строк. Да, еще надо будет хорошенько потрахаться с хранением дерева на диске и подгрузкой его кусками, ибо в оперативку оно все не поместится никак.

Второй вариант, возможно более подходящий для таких объемов данных - это полиномиальные хеши. Можно для каждой строки вычислить L-N+1 хешей для всех подстрок длины N. Первый хеш считается тупо по формуле, а дальше дописывание одного символа справа и удаление одного символа слева можно за 2 операции пересчитать. Вот так вы быстро, за линейное время, можете построить все хеши для одной строки. Запишите их в файл, отсортируйте его (гуглите - известная задача сортировки очень большого файла). А потом операцией слияния можно найти повторяющиеся числа во всех файлах.

Более того, можно не сравнивать каждый файл с каждым, а выполнять слияние сразу на всех файлах. Для этого надо завести приоритетную очередь, она же куча, она же heap, в которую складывать текущие числа из всех файлов (по одному из файла) вместе с указателем на сам файл. Вам надо из этой очереди вынуть минимальное число, и потом вынимать дальше, пока минимум в очереди не изменился. Т.е. вынуть все одинаковые минимальные числа. Файлы, на которые они указывают - это строки с совпадениями. Пометьте это где-то, и для каждого файла прочитайте следующее число и положите его в очередь.

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

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

Если все-таки надо искать совпадения по всем строкам глобально, то придется помучиться. Разбейте ваши данные на K частей примерно одинакового размера так, что каждый компьютер может обработать по 2 части, а хранить хотя бы по 3 части.

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

Надо будет провести K-1 раундов. На первом раунде части 1 и 2 лежат на компьютере 1, части 3 и 4 на втором, и т.д. На втором раунде вы храните части 2 и 3 на компе 1, 4 и 5 на компе 2 ... K и 1 на последнем. При переходе между раундами каждый комп отдает одну часть куда-то, и одну откуда-то получает. На третьем и четвертом раунде вы обрабатываете все пары, в которых вторая часть имеет номер на 2 больше первой части (если брать по модулю K). И так далее. На последнем раунде будут обрабатываться пары, где одно число больше другого на (K-1)/2.

Например, для K=4 вы получаете такие пары на компах:

1. (1,2) (3,4)
2. (2,3) (4,1)
3. (1 3) (2 4)

Тут надо порисовать и составить схему так, чтобы поменьше данных перекладывалось. Для некоторых K так красиво не получится, и какие-то компы будут простаивать на каких-то раундах.

По поводу оптимизаций - узкое место будет загрузка данных с диска и передача их по сети. Ассемблером баловаться тут смысла нет особо. Запускайте кучу потоков, чтобы диск не простаивал. Еще репликацию данных можно запускать параллельно с обработкой предыдущего куска, если места хватает.

Нет. Компилятору же надо знать, что там за деструктор вызывать. Что вы в void* на самом деле положили - он знать не может. Более того, там не только деструкторы, там и delete у указателей вызван не будет. Руками придется сначала привести к правильному типу и потом отчистить память (что вызовет деструктор).

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

Это известная, очень сложная (NP-сложная) задача об упаковке.

Для сотен тысяч входных списков вы оптимальное по количеству кусков в ответе решение не найдете за все время до тепловой смерти вселенной. Всякие аппроксимации, вроде вашего жадного алгоритма, могут найти лишь какое-то хорошее, но не лучшее разбиение. В частности, у вас используется Next-Fit аппроксимация - вы в итоге можете выдать в 2 раза больше кусков в ответе, чем можно было бы. Есть более сложные алгоритмы, которые, например, гарантируют ухудшение максимум в 1.7 раза.

Соглашусь с Dr. Bacon, через yield код вашего решения может быть чуть красивее, но я не совсем понимаю, что в вашей реализации вам так "не красиво". Хотя я не питонист.

Далее, вы упоминули, что ключи во входных данных - это номера домов, а числа в списках - номера квартир. Вы как-то объединяете дома с ограничением на количество квартир. Не знаю, что у вас за задача на самом деле, но мне кажется логичным, что вам надо бы объединять дома только рядом. С одной улицы, или вообще идущие подряд. Ведь если в одной группе идут квартиры из домов в разных концах города, то какая вообще разница, что квартиры из одного дома могут быть в разных группах? Если такое ограничение ввести, то задача упрощается и ваше решение будет оптимальным.

Будет. Бинарному поиску главное, чтобы числа в массиве не убывали. Даже если там числа больше предыдущего не только на 1.

Размер результирующего массива тоже arrSize. Не надо его делить на 3.
Еще инициализация массива у вас не "значение элемента массива равно его порядковому номеру". Вы там тупо единицами все инициализируете.

Ну и вывод в цикле будет весьма спамный.

Ускорение: a=v/t
Расстояние: s=at^2/2

t= 11 сек
v= 100 км/ч = 27.777(7) м/с

Подставьте сами