Wataru

Проблема с win api: https://learn.microsoft.com/en-us/windows/win32/in...

Оно ожидает вот такие коды. И, если для заглавных английских букв оно еще совпадает с кодами ascii, то для строчных букв - нет.

Как компилируете-то? Пока похоже, что вы пытаетесь собрать исполнительный файл прямо из 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 у указателей вызван не будет. Руками придется сначала привести к правильному типу и потом отчистить память (что вызовет деструктор).

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

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

Есть. Называется int. Вам надо хранить количество десятитысячных в числе. Иными словами, вы вместо x храните в int x*10000. При выводе делите на 10000 (и установите выводить 4 знака).

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

Upd: И вообще, раз уж разговор о C++, то можно реализовать свой класс. Там можно даже отдельно хранить целую часть и 4 знака после запятой. Если вам встроенной точности int/int64_t не хватает. Все математические операции можно переопределить и работать, как со встроенным типом. Вообще, по-умному, это называется fixed point numbers.

Есть несоклько системных АПИ.

Например, DirectShow или MediaFoundation.

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

Если вы не планируете открывать камеру, а вам надо только информацию о ней собрать, или вы работаете с определенным устройством, то MediaFoundation вам подойдет лучше.

Иначе смотрите DirectShow.

Можно найти много примеров кода в интернете.

Это копирование массива. На C++, если используете vector, то можно присвоение использовать. Там произойдет копия.

Тут фактически 2 задачи:
1) Разбить строку на слова. Тут вам поможет string::substr
2) Проверить, что сторка s2 встречается в тексте. Вы уже умеете пользоваться string::find.

Где он там, как функция-то?

vector<int> cps = {};
Заводит вектор cps, инициализирует его пустым. Можно = {} и не писать, вектор итак будет по умолчанию инициализировн пустым.

cps.push_back(i);
Вызывает метод push_back у cps.
Этот метод добавляет в конец вектора переданное значение.

Тут вам надо знать, что такое классы и их методы в C++.

Много ошибок:
1) number[i - 3] == 8; number[i - 2] == 8;, вопреки вашим ожиданиям, не присвоит значения в массиве значению 8. Тут выполняются 2 сравнения с 8, результат которых игнорируется.

2) Неинициализированные переменные. В частности, k, из-за чего происходит выход за границы массива.
Плюс, если x изначально окажется 3 (а она тоже не инициализирована), то после первой же 8 вы как бы найдете вхождение и тоже будете выходить за границы массива.