• Обертываем алгоритмы в итераторы
    +2
    А, ну-ка, проитерируйте по числам Фибоначчи назад больше, чем на два шага, значения которых сохранены в генераторе.
    Это несложно: Fn-2 = Fn - Fn-1
  • Российские школьники взяли три золота на Международной олимпиаде по информатике
    0
    Боюсь, список соответствия бюджетных вузов и поддерживающих компаний в РФ будет смешным (на уровне 1 семестр два часа в неделю) и слегка внутри-МКАДским.
    В моем городе нет ни одного филиала топовой ИТ-компании (Yandex, Google, Microsoft и т.п.), при этом местные компании стараются принимать участие в образовательном процессе: выступают спонсорами олимпиад, проводят различные бесплатные обучающие курсы, банальные стажировки для студентов, в конце концов. Уж про Яндексовский ШАДом и факультет в ВШЭ я молчу…
  • Российские школьники взяли три золота на Международной олимпиаде по информатике
    +6
    Вы не понимаете простой вещи: это не какая-то изолированная от остальной страны группа детей, это всего лишь верхушка большой системы. За спинами этих детей стоит множество других, которые тоже старались, занимались, но где-то не дотянули, проиграли этим. И даже если все дети с этой фотографии уедут за границу, большинство с нижнего уровня — останется. Кроме того многие из этих «суперзвёзд» уходят в науку или, по крайней мере, оставляют в ней какой-то след, и этим приносят пользу всему населению Земли, а не только одной конкретной стране.
  • Это маленькое чудо — алгоритм Кнута-Морриса-Пратта (КМП)
    +1
    Я вам что-то сначала поверил, а теперь осознал, что не понимаю, как он обобщается на случай множества шаблонов нефиксированной длины.
  • Это маленькое чудо — алгоритм Кнута-Морриса-Пратта (КМП)
    0
    Да, я именно про Рабина-Карпа и говорил (забыл, что у него есть устоявшееся название). А почему не самый простой то? По объему кода сопоставим с КМП, зато идея, лежащая в его основе, гораздо проще. И при этом довольный мощный: обобщается для двумерного случая (найти за O(n*m) все вхождения заданного шаблона прямоугольника в квадратной матрице n*m), для случая множества шаблонов.
  • Const и оптимизации в C
    0
    На мой взгляд, суть статьи в том, что компилятор не имеет права делать предположение (и соответственно, проводить исходя из этого какие-то оптимизации), что если нечто передается внутрь функции по указателю на константу (константной ссылке), то оно внутри этой функции по этому указателю не будет изменено (естественно, в том случае, когда реализацию функции он посмотреть не может). Это довольно контринтуитивно, хотя и логично, если вспомнить о наличии функционала аля const_cast, которым мы должны иметь возможность воспользоваться.
  • Это маленькое чудо — алгоритм Кнута-Морриса-Пратта (КМП)
    0
    В статье про это есть, правда без доказательств и оценки асимптотики. Если очень вкратце, то пусть l(S) — это префикс-функция строки S (для удобства восприятия будет считать значением функции саму строку, а не её длину, т.е. l(ababa)=aba). Тогда:

    1) Все (не только самый длинный) собственные префиксы, являющиеся также и суффиксами, строки S — это множество l(S), l(l(S)), l(l(l(S)))… (до тех пор, пока не получим пустую строку. Будем считать, что она также является подходящим префиксо-суффиксом).

    2) Рассмотрим строку Sc (дописали в конец строки символ c). Пусть l(Sc)=Ac (т.к. префикс-функция является суффиксом строки, то если только это не пустая строка, то она обязана заканчиваться на с. А может быть пустой строкой). Тогда нетрудно понять, что A является префиксо-суффиксом (каким-то, не факт, что самым длинным) строки S.

    3) Из этих двух соображений возникает алгоритм нахождения l(Sc). Будем последовательно перебирать все префиксо-суффиксы строки S, начиная с самого наибольшего (т.е. просто будем идти по ряду l(S), l(l(S)), l(l(l(S)))...) и проверять не будет ли это также префиксо-суффиксом для строки Sc (для этого необходимо и достаточно, чтобы символ, следующий за концом соответствующего префикса, был с).

    Примеры есть в статье, доказательство асимптотики в этом комментарии выше.
  • Это маленькое чудо — алгоритм Кнута-Морриса-Пратта (КМП)
    –1
    Для олимпиадных целей (цель — написать как можно проще, лишь бы попадало в требуемую асимптотику) самый простой алгоритм — это поиск с помощью хеш-функции. Особенно когда нам нужно найти только первое вхождение, тогда нам не обязательно верить, что если хеш-функции двух строк равны, то эти строки совпадают.
  • Const и оптимизации в C
    0
    «x» передается в foo одним из аргументов (через стек или регистр).
    В foo передается не x, а указатель на x.
    Поэтому, компилятор перестраховывается и делает повторную загрузку.
    Идея в том, что внутри bar x не меняется, а в foo передается через указатель на константу, поэтому «вроде как» внутри этой функции тоже не может менятся. Из этого компилятор должен бы сделать вывод, что x всегда 0 и нет никакого смысла прибавлять этот 0 к y.
  • Это маленькое чудо — алгоритм Кнута-Морриса-Пратта (КМП)
    +1
    Возвращайте вектор позиций вхождения или вы считаете, что функция поиска подстроки должна возвращать в качестве ответа массив вычисленных префикс-функций?
  • Это маленькое чудо — алгоритм Кнута-Морриса-Пратта (КМП)
    0
    Нет никакой разницы нужно ли найти первое вхождение или же все вхождения. Код, предложенный вам выше, ищет все вхождения (роль @ в нем играет '\0' на конце образца)
  • Последние новости о развитии C++
    +2
    Вторая строчка эквивалентна простому:
    {
      std::lock_guard<std::mutex> lock(m);
      // do something
    }
    

    Цель же введения этого нового способа записи в стандарт в банальной экономии строк кода.
  • Последние новости о развитии C++
    +2
    К слову, у вас есть идея как можно ввести эту фичу, не добавляя новых ключевых слов и при этом не сломав совместимость с подобным кодом:
    if (...)
      for (...)
        one_code_line_action;
    else
      ...
    
  • Последние новости о развитии C++
    0
    Можно завернуть код в «фиктивную» лямбду c мгновенным вызовом и выходить не break'ом, а return'ом:
    [&]{
      for (...) {
        ...
        if (...)
          return;
      }
      // Else part
      ...
    }();
    
  • Последние новости о развитии C++
    0
    С новым синтаксисом, насколько я понимаю, можно будет написать как-нибудь так:
    if (auto result_it = std::find(std::begin(container), std::end(container), a)
        ; result_it != std::end(container)) {
      do_something();
    } else {
      ...
    }
    
  • Собеседование на программиста в Amazon
    0
    Понятно. У меня в голове ваш вопрос трансформировался в «когда квадратичная сортировка будет наилучшим (самым быстрым) выбором». Потому что сортировка почти упорядоченных последовательностей и последовательностей, состоящих из длинных отсортированных кусков, — это «поле» Timsort.
  • Собеседование на программиста в Amazon
    0
    К слову, если заменить в вашей задаче два итератора на n итераторов, то задача становится гораздо более интересной, тут можно и доказать, что меньше чем за n + k log n (k — количество переходов к следующему элементу по итератору-ответу) её реализовать нелья, а в варианте с массивами поговорить о том, в какой последовательности их оптимальнее друг с другом сливать.
  • Собеседование на программиста в Amazon
    0
    Нет, это — не то. Автор комментария имел ввиду, скорей всего, тот факт, что квадратичные алгоритмы обгоняют быструю сортировку на коротких массивах. Но в реальности промышленные реализации quicksort'а учитывают данный факт и выполняют процедуру разбиения только для кусков длиннее некоторой заданной константы, а куски короче неё сортируют уже квадратичной сортировкой. Поэтому если квадратичный алгоритм при некоторой длине массива стабильно обгоняет такой вариант быстрой сортировки, то это просто означает, что мы взяли слишком маленькую константу.

    PS Пузырьковая сортировка — не лучший вариант квадратичной сортировки, она и не самая эффективная, и не самая интуитивно понятная, честно говоря, не знаю, почему она пользуется такой популярностью…
  • Собеседование на программиста в Amazon
    0
    Формально говоря, у вас написано не совсем то, что требовалось, и код работает за O(N^2). Хотя в правильный вариант, конечно, легко переделывается…
  • Собеседование на программиста в Amazon
    0
    Вопрос то простой, но вот описать ответ словами по телефону, не имея возможности ничего написать и показать собеседнику, может быть сложновато…

    К слову про «совсем не оптимально», если реализация встроенного алгоритма сортировки — это Timsort, то он посортирует такой массив за O(n).
  • Собеседование на программиста в Amazon
    +6
    Давайте и дальше тратить время на изучение сортировки массивов.
    Сортировка — один из первых вопросов, рассматривающихся в любом базовом курсе по алгоритмам. Во-первых, потому что она, как подзадача, входит во многие более сложные алгоритмы. Во-вторых, потому что это удобная для начала тема: постановка задачи близка каждому человеку, есть большое количество принципиально различных и при этом не слишком сложных и объемных для восприятия (но при этом эффективных) алгоритмов решения. В-третьих, в какой-то степени это, наверно, уже традиция.

    Поэтому, если на вопросах об алгоритмах сортировках человек «плавает», то можно уверенно сказать, что в данной области (алгоритмические знания) никаких обширных и систематизированных знаний у него нет. Конечно, есть множество вакансий для которых они и не нужны, но это уже другой вопрос…
  • Перевод С++ проекта на разработку с юнит-тестированием/TDD
    0
    Если интерфейсные классы не содержат данных
    Они содержат указатели на таблицу виртуальных функций, пусть эта деталь реализации от нас компилятором и скрывается
  • Relinx — ещё одна реализация .NET LINQ методов на C++, с поддержкой «ленивых вычислений»
    0
    Да, я бы на вашем месте хорошенько продумал и в явном виде прописал, кто чем владеет и как и кому это владение в процессе переходит. Мы же на языке без сборки мусора программируем, тут это важно. Ещё бы подумал над тем, что одни функции-члены класса у вас возвращают новый экземпляр relinx_object, а другие — меняют сам исходной объект (например, skip, мб какие-то ещё). Я понимаю, что в случае skip это вызвано идеей оптимизации, но выглядит такой интерфейс контринтуитивно.
  • Relinx — ещё одна реализация .NET LINQ методов на C++, с поддержкой «ленивых вычислений»
    +3
    В репозитории на github у вас по-прежнему:
    relinx_object(relinx_object &&) = default;
    

    Если вы, возможно, не поняли в чем её проблема, то попробую объяснить ещё раз: не для всех контейнеров move-конструктор реализован, как простой swap указателей на данные. Соответственно, итераторы (которые у вас просто копируются при таком задании конструктора), указывающие на данные старого контейнере, могут не быть корректными итераторами для перемещенного контейнера. Самый простой пример: массивы статической длины, если у вас Container будет типа std::array<int>, то перемещение этого массива — это просто побитовое копирование данных из старого объекта в новый, а, соответственно, _begin и _end нового объекта будут указывать внутрь старого массива. Если старый объект после этого уничтожается (например, он был временным объектом), то имеем use-after-free. Я бы накидал вам код для наглядности, но не смог быстро разобраться, что за новый параметр StoreType вы добавили в последней редакции, надеюсь и так понятно.

    Причем из-за выбранного вами дизайна, когда у вас один и тот же объект может быть как простой невладеющей парой итераторов, так и владеть собственным контейнером, кроме того для второго случая не всегда _begin указывает на начало владеемого контейнера (т.к. он может быть сдвинут с помощью skip, может и каких-то других функций), я не представляю как это можно легко исправить, не теряя при этом в эффективности (потому что понятно, что данные, лежащие по _begin и _end, всегда можно просто тупо скопировать).

    Что ещё бросилось в глаза при беглом изучении
    template<typename Container>
    auto from(Container &&c) -> decltype(auto)
    {
        return relinx_object<typename std::decay<decltype(std::begin(c))>::type>(
            std::begin(c), std::end(c));
    }
    

    Даже для prvalue аргумента (когда параметр выводится как rvalue ссылка Container&&) все равно используется невладеющий вип конструктора (по паре итераторов), соответственно, какой-нибудь такой код не сработает:
    vector<int> func();
    auto r = from(func());
    // ниже этой строчки r использовать нельзя,
    // т.к. вектор, который вернула func(), уже уничтожен
    

    Более того, версия from, принимающая std::initializer_list, благодаря какой-то неочевидной шаблонной магии, вызывает вышеупомянутую версию функции, поэтому даже такой код не будет работать:
    auto r = from({1, 2, 3});
    // дальше этой строчки r использовать нельзя
    


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

    Вторая проблема — у вас внутри объекта лежит огромная куча каких-то непонятных данных, объект, создаваемый из простой пары указателей (Iterator = T*), занимает в памяти вместо ожидаемых 16 байт аж целых 128. Не знаю как насчет остальных, но _indexer, _def_val_container и _default_value определенно лишние, они используются везде как типичные временные переменные:
    template<typename ForeachFunctor>
    auto for_each_i(ForeachFunctor &&foreachFunctor) const noexcept -> void
    {
        auto begin = _begin;
        auto end = _end;
    
        _indexer = 0;
    
        while (begin != end)
        {
            foreachFunctor(*begin, _indexer);
    
            ++_indexer;
            ++begin;
        }
    }
    

    В чем смысл помещения их внутрь объекта я не понимаю.

    Дальше:
    template<typename AvgFunctor>
    auto avarage(AvgFunctor &&avgFunctor) const noexcept -> decltype(auto)
    {
        return (sum(std::forward<AvgFunctor>(avgFunctor))
            / std::distance(_begin, _end));
    }
    

    Во-первых, конечно, average, во-вторых, в случае не RandomAccessIterator реализация неэффективна (два прохода вместо одного), а в случае InputIterator (по которым можно сделать только один проход, например, std::istream_iterator) вообще не сработает.

    Ну и по мелочи:
    using self_type = relinx_object<Iterator, ContainerType>;
    

    с последней редакцией указывает на неверный тип.

    relinx_object(ContainerType &&container) noexcept
        : _container(std::forward<ContainerType>(container))
        , _begin(std::begin(_container))
        , _end(std::end(_container)) {}
    

    Напишите по-русски _container(std::move(container)), у вас тут аргумент нешаблонный, никакой тип не выводится.
  • C++ без new и delete
    0
    Код, который был приведен выше — был абсолютно тривиальный и без включенной оптимизации
    О, а я был прав. В этом примере поди снова не включили?
  • C++ без new и delete
    0
    Да, так и будет, потому что проверка внутри delete не скрыта в недрах какой-нибудь вызываемой функции, а вставляется компилятором прямо по месту самого delete (что логично, т.к. иначе мы не смогли бы получать преимущества от знания, что в этой точке указатель всегда ненулевой). В комментарии ниже есть искусственный пример, показывающий, что в обоих случаях код будет идентичным.
  • C++ без new и delete
    +2
    Не знаю, кто как, но люди, которые моют руки перед едой, так код писать точно не будут. А напишут его, например, так:

    Только лучше так:
    foo(std::move(arg0), std::move(arg1));
    
    Экономим на лишнем инкременте/декременте счетчика и отвязываем время жизни объектов от времени жизни arg0 и arg1.
  • C++ без new и delete
    0
    // здесь выполняется проверка что в reset не передали тот же самый указатель
    Я не уверен, кстати, что подобная проверка (если я верно понял то, что в ситуации равенства обоих указателей при ней ничего не происходит) не нарушает стандарт. Стандарт (C++11 20.7.1.2.5p4) говорит нам о поведении reset() следующее:
    Effects: assigns p to the stored pointer, and then if the old value of the stored pointer, old_p, was not equal to nullptr, calls get_deleter()(old_p).
    Как видим, вышеупомянутой проверки стандарт не предусматривает, а значит в точке p.reset(x); должен быть вызван деструктор для x и освобождена память. Да, можно сказать, что дальше в момент вызова деструктора p у нас возникает UB из-за повторного удаления, и поэтому мы можем делать, что захотим. Ну а вдруг такого не будет (например, ниже мы вызовем release())?
  • C++ без new и delete
    +1
    Зачем оно там?
    В реальности, там в шаблоне конструкция вида:
    if (get() != nullptr)
      get_deleter()(get());
    
    для поддержки нестандартных deleter'ов (стандарт обязывает делать такую проверку и вызывать их только для ненулевых указателей). И да, в ситуациях, когда компилятор не может доказать (в примерах выше то у него всего на виду), что указатель ненулевой, проверка останется. Но и для простого delete компилятор прямо по месту такую проверку вставит, т.к., как вы верно указали, по стандарту delete от нулевого указателя абсолютно легален и должен просто не делать ничего, а вызывать, к примеру, какой-нибудь нетривиальный деструктор, передав ему нулевой указатель, не самая лучшая идея. Вот синтетический пример, в обоих случаях идет проверка.

    Вообще, по логике, если мы уверены, что в этой точке указатель не нулевой, то мы можем «подсказать» это компилятору, написав какое-нибудь не делающее ничего действие с использованием разыменования этого указателя (скажем, delete &*p;). Тогда компилятор имеет право считать, что указатель всегда ненулевой, т.к. иначе происходит UB. На практике, я чуток поигрался, и компиляторы (пока?) такие подсказки не воспринимают, нужно что-то очень явное с объектом сделать (например, вывести его на экран), чтоб такая оптимизация заработала. Возможно, у кого-нибудь получится найти рабочий способ?
  • C++ без new и delete
    0
    Вы, скорей всего, при компиляции оптимизацию не включили, вот у вас ничего и не заинлайнилось.
  • Разыменовывание нулевого указателя приводит к неопределённому поведению
    +1
    В плюсах есть такая интересная штука — указатель-на-член данных. По сути, это тот же offset от начала структуры, только типизированный. Но стандарт требует, чтобы этому указателю можно было присвоить нулевое значение (nullptr), которое значит, что он никуда не указывает. Как же быть, ведь смещение на 0 относительно начала структуры — это вполне легитимная вещь? Просто берут и хранят не само смещение, а смещение + 1 (то есть смещение в 0 становится единицей и т.д.), мне кажется, и в вашем случае подобным трюком можно воспользоваться.
  • Разыменовывание нулевого указателя приводит к неопределённому поведению
    0
    В ваших примерах, несмотря на то, что оператор разыменования в коде присутствует, фактического чтения данных по этому адресу не происходит, всё остается на уровне арифметики адресов. На уровне стандарта терминология, позволяющая разграничить эти два случая, тоже существует: оператор разыменования генерирует lvalue (адрес), а процесс чтения данных по адресу осуществляется с помощью lvalue-to-rvalue conversion. Но, видимо, авторы стандарта не захотели усложнять/поленились/не учли этого, в общем, по какой-то причине не разграничили эти случаи.
  • Нам запретят даже говорить о криптовалютах?
    –1
    Экономические теории скорее напоминают религию, чем науку.
    Насколько я смог понять, экономика — некий сплав из гуманитарной и точной дисциплины. Там есть очень большой слой, который строит различные математические модели, пытается их анализировать, искать наилучшую стратегию в рамках этой модели и так далее. И есть второй, условно гуманитарный слой, который занимается спорами о том, какие базовые принципы должны быть положены в основу этих моделей, чтобы они были похожи на то, что происходит в реальном мире, ну и пытается распространять полученные в рамках анализа моделей выводы на этот самый реальный мир и находить им подтверждения. Для этого слоя, как и, в принципе, для любой гуманитарной дисциплины характерно то, что вы описали: споры, различные течения и школы и все в этом духе.
  • Как мы объясняли детям, кто такой программист
    0
    Мне тоже кажется, что часть про то, как раньше было тяжело и вы не представляете как вам, дети, повезло, лишняя. И общий посыл доклада, что человек должен стремиться всё уметь и программирование ему в этом очень поможет, если я, конечно, верно его уловил, слишком философский для детей что ли.
  • Нам запретят даже говорить о криптовалютах?
    0
    Вывод активов это не преступление.
    Это когда они получены легальными методами.
  • Нам запретят даже говорить о криптовалютах?
    0
    Тогда каждый может проверить свой голос и спросить знакомого, действительно ли тот проголосовал так.
    Ради такой возможности не обязательно раскрывать анонимность. Система при голосовании, например, может просто выдавать вам какое-нибудь число, а потом публиковать отчет, где будет написано какое число за кого отдало голос. В принципе, даже электронная система для этого не обязательно, вы вполне могли бы писать в бюллетене при голосовании это число сами, а комиссия подсчета голосов формировать подобный отчет. Правда, от вбросов это всё не защищает, только от присваивания вашего голоса.
  • Нам запретят даже говорить о криптовалютах?
    +2
    Так же и с МММ: закона о пирамидах не было — вас ни кто не принуждал играть.
    Всё верно, но парень давал обещания, которые не сдержал. За это и был осужден, насколько я понимаю.
    А мне тут втирают как круто будет с биткоином.
    Конкретно в этой ветке вам «втирают» в чем разница между биткоином и МММ, смотрите свой же вопрос, с которого эта ветка началась.
    Вот ровно об этом государство и говорит :). Что это сурогат денег и все операции с ним — ваши личные проблемы.
    Нет, государство говорит: если ты, друг, будешь им пользоваться, мы тебя накажем, смотрите текст поста.
  • Нам запретят даже говорить о криптовалютах?
    +3
    Куда-то вас не туда понесло имхо, нету никаких гарантий ни для этой валюты, ни для одной из официальных валют, везде только ваши риски. Подскочил вот курс рубля к доллару в два раза недавно, и что случилось? Кто-то вам что-то возместил? «Привет Мавроди.»
  • Нам запретят даже говорить о криптовалютах?
    0
    Бумажки МММ позиционируются, как акции.

    Ближе уж к облигациям тогда.
  • Нам запретят даже говорить о криптовалютах?
    +1
    Ну так тут многие также рвутся на рынок, чтобы намайнить из воздуха денег.
    Это неважно, в истории человечества существовало множество видов денег, которые можно было «намайнить»: различные металлы (преимущественно драгоценные), скот, зерно, шкуры животных. Ещё раз повторюсь, основная разница в том, что в случае финансовых пирамид я (организатор пирамиды) вас обманываю, обещая некий доход, а в итоге своё обещание не выполняю, скрываясь в неизвестном направлении.