Для начала стоит сказать, что "переаллоцирование слайса" не происходит. Слайс - это просто структура, которая под собой содержит len, capacity, и указатель на массив, который содержит элементы слайса. Если и происходит переаллокация, то именно массива, а не слайса.
В функции modifyByAppend на самом деле ничего не переаллоцируется, а пишется значение просто в следующий байт и меняется len на 2, но т.к. значение длины пишется не в тот же самый слайс, по выходу из функции len остается 1. Дальше думаю происходит магия println, который просто не выводит элементы с индексом больше чем len.
Проверить, что значение в modifyByAppend остается в памяти можно через пакет unsafe.
Я присоединюсь к коментатору выше, код не смотрел, но докерфайл с php, docker-compose и установка compose через docker run php bash несколько удручает.
Один вопрос - зачем хранить все сообщение в БД если фактически нам надо хранить id записей которые мы уже репостнули?
Во-первых, в ней ни слова о том, что в некоторых случаях (1,26%, если я верно посчитал) мы можем получить одинаковые задания, следующие друг за другом, а еще в части случае мы просто поменяем множители местами. Это редкие случаи, но на мой взгляд важные. Во-вторых, мой комментарий лишь показывает возможный путь размышления над задачей и что при решении "в лоб" есть некоторые дополнительные расходы и любому разработчику стоит задуматься о поиске более простого пути.
С генерацией случайного числа и потом поиска его множителей есть проблема, которая состоит в том, что для начала было бы неплохо понять, а не простое ли это число. Конечно от 1 до 100 их не так много и можно захардкодить их и пытаться перегенирировать, но уже на этом этапе понятно, что генерация сразу произведения сопряжена с некоторыми сложностями и стоит поискать путь попроще
Я бы не назвал это "лишними операциями". Задача стоит в поиске такой ноды, в которой черепаха равноудалена от начала, а кролик равноудален от черепахи. После ее нахождения мы точно:
можем сказать, что в списке есть цикл
найти начало цикла
вычислить его длину
При этом гарантируется, что при наличии цикла такая нода встретится при первом проходе черепахи по нему. На мой взгляд это крайне изящный алгоритм)
Дело - не в четности как таковой. Тот факт что X(n) = X(2n) дает гарантию, что после того как мы скинем один из указателей на начало списка встреча произойдет в начале цикла. Есть ли такая гарантия после оптимизации?
Я хочу сказать именно то что и написал - гарантируется что за первый проход черепахи по циклу кролик ее встретит. Доказательство - по ссылке. Третий пример вырожденный, потому что там "хвост" = 0, очевидно что он ее перескочит, т.к. мы уже находимся в цикле.
Вы все верно ухватили, у Кнута именно это и было написано, дальше я лишь доказал тот факт, что если мы ищем ближайшее к 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 - натуральное число
Fun fact - из последних собеседований на 250к, которые я проходил, про ООП спрашивали меня ровно один раз
И конечно нет никаких примеров когда их оценка была максимально далека от реальности? Мне в голову приходит как минимум 2.
Не у всех цель оффер в FAANG
Так это буквально и есть обучение - вы решали рутинные задачи и спустя какое-то время начали их выполнять быстрее.
Defined behavior - это поведение которое не определено в спецификации. Интересные курсы
Категорически не согласен.
Для начала стоит сказать, что "переаллоцирование слайса" не происходит. Слайс - это просто структура, которая под собой содержит len, capacity, и указатель на массив, который содержит элементы слайса. Если и происходит переаллокация, то именно массива, а не слайса.
В функции modifyByAppend на самом деле ничего не переаллоцируется, а пишется значение просто в следующий байт и меняется len на 2, но т.к. значение длины пишется не в тот же самый слайс, по выходу из функции len остается 1. Дальше думаю происходит магия println, который просто не выводит элементы с индексом больше чем len.
Проверить, что значение в modifyByAppend остается в памяти можно через пакет unsafe.
https://go.dev/play/p/D9D7vUPNkEK
Разве это основная мотивация?
Это не нюанс интерфейсов, а различие между *Bar и Bar. Bar не включает в себя методы *Bar, а вот обратный вариант уже включает.
Я присоединюсь к коментатору выше, код не смотрел, но докерфайл с php, docker-compose и установка compose через docker run php bash несколько удручает.
Один вопрос - зачем хранить все сообщение в БД если фактически нам надо хранить id записей которые мы уже репостнули?
Я ее прочел. Она мне не нравится.
Во-первых, в ней ни слова о том, что в некоторых случаях (1,26%, если я верно посчитал) мы можем получить одинаковые задания, следующие друг за другом, а еще в части случае мы просто поменяем множители местами. Это редкие случаи, но на мой взгляд важные.
Во-вторых, мой комментарий лишь показывает возможный путь размышления над задачей и что при решении "в лоб" есть некоторые дополнительные расходы и любому разработчику стоит задуматься о поиске более простого пути.
Ничего проще нет чем что, позвольте уточнить
С генерацией случайного числа и потом поиска его множителей есть проблема, которая состоит в том, что для начала было бы неплохо понять, а не простое ли это число. Конечно от 1 до 100 их не так много и можно захардкодить их и пытаться перегенирировать, но уже на этом этапе понятно, что генерация сразу произведения сопряжена с некоторыми сложностями и стоит поискать путь попроще
Крайне холиварная формулировка.
https://github.com/golang-standards/project-layout/issues/117
Не совсем ясно что конкретно имеется в виду, хотя на мой взгляд в БД именно хранение и доступ к данным - самая интересная часть.
Я бы не назвал это "лишними операциями". Задача стоит в поиске такой ноды, в которой черепаха равноудалена от начала, а кролик равноудален от черепахи. После ее нахождения мы точно:
можем сказать, что в списке есть цикл
найти начало цикла
вычислить его длину
При этом гарантируется, что при наличии цикла такая нода встретится при первом проходе черепахи по нему. На мой взгляд это крайне изящный алгоритм)
Дело - не в четности как таковой. Тот факт что X(n) = X(2n) дает гарантию, что после того как мы скинем один из указателей на начало списка встреча произойдет в начале цикла. Есть ли такая гарантия после оптимизации?
Тогда у меня вопрос - как найти начало цикла в вашей оптимизированной версии?
Я хочу сказать именно то что и написал - гарантируется что за первый проход черепахи по циклу кролик ее встретит. Доказательство - по ссылке. Третий пример вырожденный, потому что там "хвост" = 0, очевидно что он ее перескочит, т.к. мы уже находимся в цикле.
https://habr.com/ru/articles/743514/comments/#comment_25685034
На самом деле алгоритм как раз гарантирует встречу на первом проходе черепахи, оптимизация не нужна
Вы все верно ухватили, у Кнута именно это и было написано, дальше я лишь доказал тот факт, что если мы ищем ближайшее к 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