Вы все верно ухватили, у Кнута именно это и было написано, дальше я лишь доказал тот факт, что если мы ищем ближайшее к r число которое делится на L без остатка, то оно будет лежать в промежутке от r до r + L
Строго говоря, надо доказывать, что позиция когда-нибудь совпадёт. Это так, потому что скорости, 1 и 2, взаимно простые.
Свойство цикла: X(n) = X (n + k * L), где k - натуральное число, а L - длина цикла. Словами: если мы из любой ноды пройдем количество шагов кратное циклу мы окажемся в ней же.
В случае если X(n) = X(2n), то n (mod L) = 0 из свойства выше, т.е. n = k * L.
Теперь можно показать, если n - первое такое число (их больше чем одно), то r < n < r + L n > r - т.к. такое X(n) = X(2n) справедливо только для нод внутри цикла.
Теперь покажем что r + L > n
r = z * L + y, где y = r (mod L) и принадлежит натуральным числам.
Пусть первым n, которое больше r и делится без остатка на L будет r + t, или
z * L + y + t
Т.к. n (mod L) = 0, то y + t = L, или t = L - y
Получается что: r + L > r + L - y
Неравенство выполняется, потому что y - натуральное число
То есть, от той позиции t (mod L), где сейчас стоит черепаха, до стартовой позиции цикла 0, нужно сделать r шагов.
Я бы только уточнил, что до позиции цикла 0 будет L - t шагов, но при этом есть гарантия, что если мы стоя на позиции t пройдем r шагов - мы попадем в начало цикла.
У самого цикла есть характеристика - его длина. И есть свойство - если мы выберем любую ноду внутри цикла и пройдем число шагов кратное его длине мы окажемся в том же месте. Т.к. расстояние между черепахой и кроликом как раз такое число, то если мы начнем бежать черепахой сначала списка, то начало цикла как раз и есть первая нода, в которой они встретятся.
Я ни про какие оптимизации не говорил, я про классический вариант алгоритма. Расстояние до начала цикла особо не имеет значения, оно влияет только на количество шагов до встречи черепахи и кролика в первый раз, свойства алгоритма от этого не меняются
Это абсолютно точно верно. Вообще об этой задаче проще становится думать (по крайней мере лично мне) когда ты цикл представляешь в виде бесконечной числовой последовательности, часть которой постоянно повторяется. Место их встречи - это некое количество шагов, которое прошла черепаха и по свойствам цикла это количество делится нацело на длину цикла. Если вернуть черепаху в начало то разница в расстояниях между ними - это удвоенное расстояние которое прошла черепаха, но которое все еще делится нацело на длину цикла. А значит, что как только черепаха, двигаясь от начала, попадет на начало цикла кролик будет там же.
Нет, не означает, потому что по дефолту команда docker-compose up создает отдельную сеть при запуске. Вообще кейсы когда надо указать сеть достаточно редкие, я с таким встречался только один раз, когда надо было чтобы тулза в одном контейнере могла достучаться до minikube.
Еще не ясно зачем пробрасывать 9000 порт у php, вряд ли мы захотим с хоста к нему присоединиться, а порт это действие занимает.
А вообще, раз уж мы говорим о докере, то локальная разработка только часть проблемы, ведь дальше мы захотим все это как-то деплоить, и делать это желательно не руками, а значит нам надо:
Настроить в ci/cd билд контейнеров
Настроить деплой этих контейнеров в какое-то окружение
И вот под эти цели все что описано выше слабо подходит.
Запускать нужные тулзы внутри контейнера, и маунтить хостовую систему внутрь него. Например, чтобы выполнить composer update достаточно просто запустить контейнер композера с флагом --rm и смаунтить внутрь него хостовую fs. Можно подрубить Makefile, тогда становится жить чуть проще.
Не могу сказать что там супер сложного в multistage, который могут освоить не только лишь все, но опишу свой опыт работы с докером, который побуждает к поиску альтернатив для билда образов:
Имеем Laravel приложение, которое живёт в 3х образах, которые билдятся из одного репозитория. Для билда используем buildkit, т.к. можно для каждого dockerfile задать соответствующий dockerignore и кеш выгружать вместе с образом.
Проблема следующая: для работы php используется расширение, которое билдятся в районе 15 минут локально и ещё дольше в контексте CI/CD, для билда которого ещё надо поставить зависимости через apt-get.
Что ж, идём на сайт докера, и выясняем, что для RUN'ов кеш считается не по файлам, которые содержит слой, а по самой инструкции. А значит если dockerfile не меняли в бранче то --cache-from master должен всегда кешировать первые слои, в которых содержатся инструкции вида RUN apt-get update && apt-get install... На практике, --cache-from работает 50/50. Когда работает, а когда нет, что может критично сказаться на времени пайплайна. Почему и по какой причине так происходит я устал разбираться. Если и есть способ решения этой проблемы силами Docker + buildkit, то я его не нашел и если есть инструмент, который избавит меня от таких вот загадок, на которые ответ кроется глубоко в недрах source кода, то лучше его использовать.
Контекст сборки и dockerignore
Гораздо удобней для этих целей не создавать определенную структуру проекта, а использовать buildkit, который позволяет для каждого dockerfile положить рядом соответствующий dockerignore, а dockerignore описать как whitelist. Это позволяет контролировать что попадает в контекст при билде, отчасти упрощает написание самих dockerfile и сильно упрощает жизнь если надо сбилдить два разных образа из одного репозитория (nginx + php, например)
Победит Х т.к. его ход сейчас.
Прошлый ход — ход 0, который очевидно не 7, т.к. иначе он мог просто выиграть, заняв центр, а значит остаются ходы 2 и 8, оба из которых бездарные, т.к. подарили кресту выигрыш.
Вы все верно ухватили, у Кнута именно это и было написано, дальше я лишь доказал тот факт, что если мы ищем ближайшее к r число которое делится на L без остатка, то оно будет лежать в промежутке от r до r + L
Свойство цикла: X(n) = X (n + k * L), где k - натуральное число, а L - длина цикла. Словами: если мы из любой ноды пройдем количество шагов кратное циклу мы окажемся в ней же.
В случае если X(n) = X(2n), то n (mod L) = 0 из свойства выше, т.е. n = k * L.
Теперь можно показать, если n - первое такое число (их больше чем одно), то r < n < r + L
n > r - т.к. такое X(n) = X(2n) справедливо только для нод внутри цикла.
Теперь покажем что r + L > n
r = z * L + y, где y = r (mod L) и принадлежит натуральным числам.
Пусть первым n, которое больше r и делится без остатка на L будет r + t, или
z * L + y + t
Т.к. n (mod L) = 0, то y + t = L, или t = L - y
Получается что:
r + L > r + L - y
Неравенство выполняется, потому что y - натуральное число
Выходит что r < n < r + L
На сколько я помню, до гарантируется, что первое r + t:
r < r + t < r + L
0 < t < L
Т.е. остаток от деления здесь тоже лишний
Я бы только уточнил, что до позиции цикла 0 будет
L - t шагов, но при этом есть гарантия, что если мы стоя на позиции t пройдем r шагов - мы попадем в начало цикла.
У самого цикла есть характеристика - его длина. И есть свойство - если мы выберем любую ноду внутри цикла и пройдем число шагов кратное его длине мы окажемся в том же месте. Т.к. расстояние между черепахой и кроликом как раз такое число, то если мы начнем бежать черепахой сначала списка, то начало цикла как раз и есть первая нода, в которой они встретятся.
Я ни про какие оптимизации не говорил, я про классический вариант алгоритма. Расстояние до начала цикла особо не имеет значения, оно влияет только на количество шагов до встречи черепахи и кролика в первый раз, свойства алгоритма от этого не меняются
Это абсолютно точно верно. Вообще об этой задаче проще становится думать (по крайней мере лично мне) когда ты цикл представляешь в виде бесконечной числовой последовательности, часть которой постоянно повторяется. Место их встречи - это некое количество шагов, которое прошла черепаха и по свойствам цикла это количество делится нацело на длину цикла. Если вернуть черепаху в начало то разница в расстояниях между ними - это удвоенное расстояние которое прошла черепаха, но которое все еще делится нацело на длину цикла. А значит, что как только черепаха, двигаясь от начала, попадет на начало цикла кролик будет там же.
Если мне не изменяет память, то позицию черепахи надо бы сбросить на начало списка, тогда их встреча будет в начале
Схвачу еще минусов, но все-таки задам этот вопрос: а что вы такого хотите найти в кластере, что поможет вам дебажить?
Если не секрет - а научила она вас чтобы что?
Тут вы конечно лукавите, в геймдеве гит точно не промышленный стандарт
Вообще статья достаточно слабая.
Нет, не означает, потому что по дефолту команда docker-compose up создает отдельную сеть при запуске. Вообще кейсы когда надо указать сеть достаточно редкие, я с таким встречался только один раз, когда надо было чтобы тулза в одном контейнере могла достучаться до minikube.
Еще не ясно зачем пробрасывать 9000 порт у php, вряд ли мы захотим с хоста к нему присоединиться, а порт это действие занимает.
А вообще, раз уж мы говорим о докере, то локальная разработка только часть проблемы, ведь дальше мы захотим все это как-то деплоить, и делать это желательно не руками, а значит нам надо:
Настроить в ci/cd билд контейнеров
Настроить деплой этих контейнеров в какое-то окружение
И вот под эти цели все что описано выше слабо подходит.
Запускать нужные тулзы внутри контейнера, и маунтить хостовую систему внутрь него.
Например, чтобы выполнить composer update достаточно просто запустить контейнер композера с флагом --rm и смаунтить внутрь него хостовую fs.
Можно подрубить Makefile, тогда становится жить чуть проще.
Даже если сейчас нет закона, который мы не можем смоделировать, это не означает что его не имеется в принципе, вполне возможно мы такой закон не знаем
Никак не запрещает. Так же никто не запрещает в танке поставить автомат с кока-колой, но какой в этом смысл?
Не могу сказать что там супер сложного в multistage, который могут освоить не только лишь все, но опишу свой опыт работы с докером, который побуждает к поиску альтернатив для билда образов:
Имеем Laravel приложение, которое живёт в 3х образах, которые билдятся из одного репозитория. Для билда используем buildkit, т.к. можно для каждого dockerfile задать соответствующий dockerignore и кеш выгружать вместе с образом.
Проблема следующая: для работы php используется расширение, которое билдятся в районе 15 минут локально и ещё дольше в контексте CI/CD, для билда которого ещё надо поставить зависимости через apt-get.
Что ж, идём на сайт докера, и выясняем, что для RUN'ов кеш считается не по файлам, которые содержит слой, а по самой инструкции. А значит если dockerfile не меняли в бранче то --cache-from master должен всегда кешировать первые слои, в которых содержатся инструкции вида RUN apt-get update && apt-get install... На практике, --cache-from работает 50/50. Когда работает, а когда нет, что может критично сказаться на времени пайплайна. Почему и по какой причине так происходит я устал разбираться. Если и есть способ решения этой проблемы силами Docker + buildkit, то я его не нашел и если есть инструмент, который избавит меня от таких вот загадок, на которые ответ кроется глубоко в недрах source кода, то лучше его использовать.
Гораздо удобней для этих целей не создавать определенную структуру проекта, а использовать buildkit, который позволяет для каждого dockerfile положить рядом соответствующий dockerignore, а dockerignore описать как whitelist. Это позволяет контролировать что попадает в контекст при билде, отчасти упрощает написание самих dockerfile и сильно упрощает жизнь если надо сбилдить два разных образа из одного репозитория (nginx + php, например)
buildkit уже включен в последние версии docker, включается просто переменной окружения.
https://docs.docker.com/develop/develop-images/build_enhancements/
Если говорить строго, то смерть это естественное (по всем законам природы) продолжение жизни и возникло оно не "для жизни", а "вследствие жизни".
И сама постановка вопроса — "смерть как проблема жизни" выглядит достаточно странно.
Единственная ошибка в условии — это предположение, что оба игрока достаточно умны.
Победит Х т.к. его ход сейчас.
Прошлый ход — ход 0, который очевидно не 7, т.к. иначе он мог просто выиграть, заняв центр, а значит остаются ходы 2 и 8, оба из которых бездарные, т.к. подарили кресту выигрыш.