Как стать автором
Обновить
23
0

Пользователь

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

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

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

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

К слову про «совсем не оптимально», если реализация встроенного алгоритма сортировки — это Timsort, то он посортирует такой массив за O(n).

Информация

В рейтинге
Не участвует
Откуда
Ижевск, Удмуртия, Россия
Зарегистрирован
Активность