• Почему вызов метода класса гораздо медленее вызова обычной функции и как это исправить?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Подозреваю, что дело в оптимизаторе. В первом примере компилятор понимает, что цикл ничего не делает и вырезает его весь нафиг. Во втором же случае, разделение на файлы не позволило оптимизатору убрать цикл. Можно покрутить опциями оптимизатора, что бы была кросс-модульная оптимизация (не помню правильное название), но в итоге вы будете сравнивать пустоту с пустотой.

    Правильнее добавить в тестируемую функцию какую-то работу. Тогда вы будуте действительно сравнивать вызов функции и метода. Или отключить всю оптимизацию.
    Ответ написан
    2 комментария
  • Как описать алгоритм для работы с очередями?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Если вам надо минимизировать общее время обработки всех клиентов (максимальное время работы какой-то из касс), то это NP-полная задача. Даже упращенная версия лишь с двумя кассами, если числа в задаче могут быть очень большими - не решается без полного перебора или каких-то вырвиглазных мозгодробительных методов оптимизации типа метода отжига.

    Если же числа небольшие, то для двух касс еще есть решение через динамическое программирование, но его сложно обобщить на большее количество касc.
    Ответ написан
    Комментировать
  • Почему leetcode не принимает правильно решенные задачи на python?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если одна и та же программа работает у вас локально, но падает с ошибкой интерпетации на сервере, то, скорее всего, дело в версии питона. Python 2 и python 3 довольно сильно отличаются. Сравните версии.
    Ответ написан
    1 комментарий
  • Зачем нужен амперсанд перед именем функции/метода?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    На самом деле понятнее писать вот так:
    int& Foo();

    Функция возвращает ссылку на int. Ссылка - это как указатель, только она не может указывать вникуда. Соответственно, вы не можете завести переменную ссылку сразу не инициализировав ее - а на что она будет указывать. И также ссылки, в отличии от указателей, не надо ее разыменовывать.

    Использовать можно, например, вот так:
    int& ref = Foo();
    std::cout << ref+10;


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

    Так же можно через эту возвращенную ссылку изменять основной объект:
    int x;
    int& Foo() {
        return x;
    }
    ...
    
    x = 0;
    int& ref = Foo();
    ref = 10;
    std::cout << x:

    Этот код выведет 10.

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

    Ну и еще, можно с этой возвращенной ссылкой работать и как с обычным int:
    int x = 2 + Foo();
    Но если вы не собираетесь менять значение внутри или не пытаетесь сэкономить на копировании объекта, то вам нет смысла вообще ссылки использовать.

    Ну и, конечно, аккуратно со ссылками надо быть. Вполне можно извернуться и получить ссылку указывающую на удаленную память. Напрямую ссылки на локальные переменные компилятор возвращать не дает, но если сначала взять адрес в указатель, а потом его разименовать и вернуть как ссылку, то вы получите undefined behavior.
    Ответ написан
    1 комментарий
  • В чем отличия между кодами?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    assign делает совсем не то, что вы думаете. Оно заменяет строку s на подстроку.

    Вам надо использовать s.substr.
    Ответ написан
    Комментировать
  • Как оформить список C++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Используйте snprintf. Так можно с тем же форматом вывести все данные не в консоль, а в строку.
    Ответ написан
  • Зачем Zobrist хешированию случайные числа?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Наверное, можно и константами ограничиться. Вот только выписывать 768 констант никому не охота. Что-то простое брать, вроде подряд идущих чисел - плохой хеш будет. Надо реально 700 разных псевдослучайных чисел.
    Ответ написан
    Комментировать
  • Что означает -'0' на C?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Это вычитание значения '0' из значения str[j]. И то и другое - символы, они же char. В языке Cи, это целочисленный тип. Просто каждому символу дается его ascii код.

    Тут это используется для получения численнного значения цифры из ее символьного значения, ведь символы '0'-'9' в ascii идут подряд в натуральном порядке.
    Ответ написан
    Комментировать
  • Доказательство простого факта. Математический анализ, равномерная непрерывность. Как?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Я так понял в условии на самом деле говрится, что для любого достаточно маленького z (0 < z < Z0) функциональный ряд равномерно сходится на (a+z, b-z)

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

    Пусть есть a<x0<b. Возьмем z = min(Z0, (x0-a)/2, (b-x0)/2). Используем данное, что ряд равномерно сходится на отрезке (a+z,b-z), а значит F на этом отрезке непрерывна. Значит F непрерывна в точке x0 (ведь мы так z подобрали, чтобы x0 в этом интервале лежала). Мы взяли любую точку x0 из (a,b), а значит F непрерывна на всем интервале.

    Edit: Если же в условии тупо дана равномерная сохдимость на каком-то интервале (c,d) (a < c < d < b), а не для сколь угодно близкого к (a,b) вложенного интервала, то, очевидно, что непрерывности там никакой и нет.
    Ответ написан
    Комментировать
  • Как правильно пропарсить лабиринт в граф?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Самое простое - это сделать вершиной каждую клетку и гнать в этом графе поиск в ширину. Можно даже не строить граф явно - а просто при обходе смотреть на четырех соседей и проверять, а не стена ли там, а были ли мы в клетке (x+dx[k], y+dy[k]), и класть координаты в очередь, если надо.

    Вы же хотите считать только перекрестки и повороты врешинами. В худшем случае, если поворотов в лабиринте много - это будет даже медленнее обхода в ширину. Потому что он работает за линию, а дейкстра - за O(n log n) в лучшем случае. Плюс там константа больше у этого n log n. Правда, это можно решить если вместо дейкстры использовать обобщенный 0-1-BFS (BFS с ограниченными ребрами - там где много очередей используется). Но реализация будет сильно посложнее простого BFS.

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

    Что-то типа такого:
    int last_node = 0;
    for (i = x_start, j = y_start; i <n && j < m; i+= dx, j+=dy) {
       if (is_wall[i][j]) {
        last_node = -1;
      }  
      if (node_number[i][j] <- 0) continue;
      if (last_node > 0) {
        // добавить ребро между вершинами.
        AddEdge(last_node, node_number[i][j]);
      }
      last_node = node_number[i][j];
    }


    Тут я просто добавляю ребра в строке или столбце между двумя соседними вершинами.
    Ответ написан
    Комментировать
  • Как определить тип функции для шаблона?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Можно использовать typedef int value_type; в классе с Setter/Getter.

    Тогда в вашем шаблоне вы можете использовать C::value_type. Так в STL, например, сделано.

    Плюсы: не надо обязательно заводить n. Можно обзывать его как удобнее или оно может вообще иметь другой тип, если свойство хранится неявно.

    Минусы: Надо обязательно заводить этот самый value_type и обновлять его вместе с методами Getter/Setter.
    Ответ написан
  • Сдвиг двумерного массива, появление ошибки Stack around the variable 'arr' was corrupted. Как исправить без переписывания кода?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Код исправляется элементарно. Надо внутренний цикл по j гнать не до 0, а до 1. Что бы не вылезать за границу массива, вы же там к j-1 -ому элементу обращаетесь. А поскольку вы делаете swap, то вы меняете элементы массива с памятью перед ним. Массив - локальная переменая, а значит он лежит на стеке и вот это вот затирание памяти рядом с массивом и есть это самое "Stack around the variable 'arr' was corrupted".

    Ну и по стилю - вместо i > -1 обычно пишут i >= 0.
    Ответ написан
    Комментировать
  • Как решить задачу с символами? Почему не работает одна функция?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вам надо не делать break. А сохранить куда-то текущее значения счетчика kol и также установить флаг, что вы встретили u. После цикла, который заканчивается чтением точки, надо, если флаг u был не встречен, вернуть значение счетчика kol. Иначе - сохраненное значение.

    Ваш первый вариант работал бы сразу, если бы вы сначала читали всю строчку в память и циклом по ней проходились. Но, поскольку надо всю строку всегда прочитать, то break ломает работу функции.
    Ответ написан
    3 комментария
  • Как дописывать число в файл со сложением через base64?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Вместо числа пишите в файл строку. Строку получайте прогоняя число через какую-то библиотеку с base64 функцией.
    Ответ написан
    Комментировать
  • Как записать значение в файл и зашифровать его на языке C?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Открывайте файл в бинарном режиме "wb" и пишите туда через fwrite (лучше побайтово, чтобы не мучиться с переносимостью из-за порядком байтов в int).

    Читайте, соответственно, через fread.

    Для шифрования лучше всего, во-первых, байты в разном порядке писать, (не 0,1,2,3, а, скажем, 2,0,3,1) и, во-вторых, xor-ить их с какими-то константами. А еще лучше не с константами, а со случайными данными, которые тоже записываются в файл рядом. Или не рядом, так будет закономерность меньше видна.

    Но все это может спасти только от людей незнакомых с reverse engineering'ом и отладкой. Более менее осведомленный ползователь посмотрит в ассемблерный код и поймет, что и как там читается и где и что надо поменять. Но да, это посложнее просто редактирования txt файла.

    Ну и, artmoney с cheat engine никто не отменял.
    Ответ написан
    Комментировать
  • Алгоритм максимально равномерного распределения предметов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    std::vector<int> DistributeExtraObjectsFairly(std::vector<int> objects, int extra_objects) {
        std::vector<int> permutation;
        permutation.reserve(objects.size()+1);
        permutation.resize(objects.size());
        std::iota(permutation.begin(), permutation.end(), 0);
        std::sort(permutation.begin(), permutation.end(),
            [&objects](const int &a, const int &b) {return objects[a] < objects[b];});
        int num_increased = 1;
        permutation.push_back(0);
        int step = (objects[permutation[num_increased]] - objects[permutation[num_increased-1]]) * num_increased;
        while (extra_objects >= step && num_increased < objects.size()) {
            extra_objects -= step;
            ++num_increased;
            step = (objects[permutation[num_increased]] - objects[permutation[num_increased-1]]) * num_increased; 
        }
        int final_value = objects[permutation[num_increased-1]] + extra_objects / num_increased;
        int num_bigger_values = extra_objects % num_increased;
        for (int i = 0; i < num_bigger_values; ++i) {
            objects[permutation[i]] = final_value + 1;
        }
        for (int i = num_bigger_values; i < num_increased; ++i) {
            objects[permutation[i]] = final_value;
        }
        return objects;
    }


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

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

    Edit: работает за O(n log n), где n - количество элементов в списке. Быстрее, я подозреваю, никак. Есть еще решение за O(n log M) - где М - максимально возможное число во входных данных. Это через бинпоиск по минимальному числу в конце.
    Ответ написан
    Комментировать
  • Почему при вызове деструктора не меняется переменная?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Я так понимаю, у вас проблема со строчкой
    aobj1[0] = a(2);

    Тут вызывается конструктор для временного значения a. Потом оператор копирования из временной переменной в *aobj. Потом вызывается деструктор временного значения.

    А потом где-то в конце произойдет и деструктор aobj.

    У aobj delete_counter после этой строчки равен 1 (ведь он скопирован у временного значения, которое сделало delete_counter единицей в констукторе). В конце при вызове деструктора aobj там delete_counter будет 1 в начале.

    Вы смотрите на адрес this в дебагере в деструкторе. Два вызваных деструктора будут для двух разных объектов (для временного значения и для aobj).

    Если вы хотите какой-то счетчик ссылок делать, то вам надо переопределять операторы копирования и перемещения (а так же все возможные конструкторы). И там аккуратно изменять счетчик ссылок. И счетчик ссылок должен быть частью общего объекта - частью класса b, а не класса a.
    Ответ написан
    4 комментария
  • Почему простой цикл на c++ выполняется медленнее, чем на golang?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вы сами в комментариях привели дизассемблированный код. Go по какой-то причине оптимизирует код лучше - тупо выкидывает весь ваш цикл.

    Чтобы этого не было, можно ксорить не с константой, а с индексом i, например.
    Ответ написан
    Комментировать
  • Как объявить функцию в другой функции?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Надо использовать forward declaration.

    Перед F напишите
    int G(int n);

    Это скажет компилятору, что есть вот такая функция. Ее определение же остается также дальше по тексту после F.
    Ответ написан
    Комментировать
  • Как избежать дублирования последней строки из файла?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Вам надо проверять, что вернет fscanf. Если оно у вас вернет что-то меньшее 2, то значит оно не смогло прочитать обе строки. В этом случае надо выходить из цикла и не класть новую запись в таблицу
    Ответ написан
    Комментировать