Это простая спецификация в каком порядке писать функцию: где расставлять её аргументы, где писать тело и как отличить вызов функции от её определения.
Мне кажется вы путаете лямбда-исчисление и лямбда-выражения. Последние вдохновлены первыми, но все-таки являются синтаксическим сахаром, а первое как раз про эквивалентное МТ функциональное представление алгоритмов.
Что вообще стоит считать алгоритмом? Сейчас в любом языке программирования присутствуют циклы и условные операторы, этого нам хватает для повседневности. Но вдруг мы могли бы добавить какую-нибудь хитрую операцию, которая позволила бы вычислять то, что без неё мы посчитать не сможем? Вот примерно таким же вопросом задавались математики 30-ых годов прошлого века, только вот у них на руках даже не было хоть какого-то единого понятия алгоритма, только какие-то отдельные применяемые в физике/математике методы. И вот тогда придумали
Лямбда-исчисление
Рекурсивные функции
Машину Тьюринга
Которые были +- эквивалентны и сводились к ключевому тезису "Все, что мы умеем вычислять может быть сведено к программе на машине Тьюринга". За почти 100 лет более полной модели вычислений так и не придумали, поэтому машина Тьюринга вошла в фундамент компьютерных наук. В современности она в большей степени является теоретическим инструментом -- например с её помощью формулируется проблема P и NP, на практике же мы все время пользуемся эквивалентами машины Тьюринга -- языками программирования (полные по Тьюрингу языки). Вот и суть как раз в том, что машина Тьюринга интересна с точки зрения теории и истории компьютерных наук, но на практике совершенно бесполезна, возможность решить какую-то осмысленную задачу небольшой машиной Тьюринга -- в этом есть определенная красота, но скорее всего никакой практической ценности.
Я этой темой не занимался, но работал со схожими и мне стало интересно. Почитал статью -- понял, что из неё мало что для себя вынесу. И нет, не потому статья плохая, а я всё знаю, а из-за отсутствия ссылок кроме ссылки сайта компании с трекером источника, зато вместо них есть вот это
Конкретные названия по понятным причинам мы называть не будем, ограничимся условными: клавиатуры M, G и Y.
Позволю себе оставить здесь цитату из одной популярной статьи на хабре
Тут что-то написано про leetcode, но я человек ответственный, поэтому к интервью не готовлюсь. Это кстати я не шуткую, реально: если вы ответственный человек, то вы, когда предстаёте перед компанией, отвечаете за то, что вы заявляете как ваши умения. Можно выучить типовые вопросы и даже казаться умнее и опытнее, чем есть, но по факту это переобучение на тестовых заданиях/вопросах. Ребята из ml поймут. Поэтому я гол как сокол и чист как стёклышко или что там ещё блин, если что-то знаю - скажу, что-то не знаю - скажу что не знаю. Таким образом работодатель знает, что он покупает и сколько ещё нужно вложить в меня средств на обучение. Все счастливы.
Вообще кажется, что по сути уникальными являются пункты 1 и 4 (из корректных), 2 -- это применение обычного Дейкстры на модифицированных весах с сохранением оптимальных путей, 3 сводится к обычному сетапу логарифмированием, а веса на вершинах можно перенести на рёбра небольшим преобразованием графа. К слову пункт 2 (из некорректных) вроде как решается Дейкстрой после разделения вершин. В любом случае хорошее обобщение.
У меня большое подозрение, что это все это очень похоже на кратчашие пути на полукольцах. Там есть например такая неочевидная функция: длина пути -- это конкатенация символов вдоль пути, а минимальная длина между s->t -- это longest common prefix всех s->t путей. Нахождение таких "кратчайших путей" например позволяет построить по конечному автомату эквивалентный ему, в котором символы появляются как можно раньше. Как сейчас не знаю, но раньше в распознавании речи это позволяло уменьшить задержку в онлайн сценарии.
Как же мастерски автор забайтил на закон Каннингема! Чтож, я повелся!
All software adds features until it is annoyingly complicated. It is then replaced by a "simpler" solution which adds features until it is exactly as complicated
Переводится как
Все программы обрастают новыми фичами пока не становятся раздражающе сложными. Затем они заменяются решениями проще, которые также обрастают новыми фичами, пока не станут настолько же сложными
Но самое смешное -- это то, что яицеголовому математику-нобелевскому лауреату Канторовичу вы дали по носу видимо совершенно не яицеголовым математиком-нобелевским лауреатом Леонтьевым. Если так было задумано, то браво! Если нет, то пойду грустить от того, что хабр уже не торт.
UPD. Уже было обсуждение про разворот битов, но думаю стоит добавить: clang 19.1.0 компилирует __builtin_bitreverse64 в .... инструкцию vgf2p8affineqb. Кто не в курсе -- это инструкция общего вида для преобразования байта путем умножения его на битовую матрицу 8х8 с арифметкой поля GF(2). Предназначалось это в большей степени для реализации GF(2^8), но нашло и такое интересное применение
Инлайн есть, но соврешенно не очевиден интуитивно. А еще я потратил 5 минут, чтобы набрать "тех" с телефона, с ноутбука не смльно лучше. Уверен Вы видели мою статью по кратчайшим путям -- вот там просто жесть была, глючило все, после каждой новой формулы мне приходилось проверять, не сломалась ли какая-нибудь из старых (а они ломались!), я думаю, что из-за этого статья писалась в 3 раза дольше. Больше я на это издевательство не готов. В общем не просто так я теперь в каждой статье предлагаю предлагаю хабру перейти на маркдаун вместо визивиг. Понятно что делать из хабра оверлиф -- это не вариант, но маркдаун -- это формат, принятый по всему миру и он простой. А еще там вполне человеческая поддержка латеха.
Я не разбираюсь во фронте, но уверен, что если дать клич по хабру, то найдутся умельцы, которые сервер с редактором маркдауна и загрузкой картинок поднимут за полдня.
По поводу вольности написания -- я категорически отказываюсь делать более формальные утверждения до тех пор пока на Хабре нет адекватной поддержки латеха (например markdown вместо wysiwyg). Если вы как-то на это повлияете, то я с удовольствием стану писать подробнее
def sort(self):
result = ListNode(None, None)
while self.next is not None:
self_next = self.next.next
self.next.next = result.next
result.next = self.next
self.next = self_next
result.push()
self.next = result.next
Ну, будет сравнений не количество инверсий, а n(n-1)/2 - количество инверсий. Никаких swap-ов тут все-равно нет, так что считать количества инверсий не обязательно вообще.
Так смысл анализа инверсий в "адаптивности", чтобы на "почти отсортированной последовательности" было "почти O(n)" и исходный посыл от @vadimr был о том, что пузырёк на адаптивный, но в отличие от вставок его проще применять к спискам
Вообще да, я немного поленился, по идее в реализацию пузырька надо добавить "если во внутреннем цикле ничего не произошло, то завершить процесс". Но вроде как и в этом случае нет ситуации, когда он сделает меньше сравнений, чем сортировка вставками, поэтому везде где можно применить пузырёк вставки сработают лучше
Вот про перетановки я как раз понимал и догадался до "сортируем ссылки хорошей сортировкой, свопаем оъекты по циклам" (и по хорошему на практике только так и надо делать), но то, что сортировка выбором делает вторую часть -- это я упустил. Но ничего, получил бурю эмоций и урок на всю жизнь.
Для меня до сих не очевидно как быть если есть повторяющиеся элементы.
Мне кажется вы путаете лямбда-исчисление и лямбда-выражения. Последние вдохновлены первыми, но все-таки являются синтаксическим сахаром, а первое как раз про эквивалентное МТ функциональное представление алгоритмов.
Что вообще стоит считать алгоритмом? Сейчас в любом языке программирования присутствуют циклы и условные операторы, этого нам хватает для повседневности. Но вдруг мы могли бы добавить какую-нибудь хитрую операцию, которая позволила бы вычислять то, что без неё мы посчитать не сможем? Вот примерно таким же вопросом задавались математики 30-ых годов прошлого века, только вот у них на руках даже не было хоть какого-то единого понятия алгоритма, только какие-то отдельные применяемые в физике/математике методы. И вот тогда придумали
Лямбда-исчисление
Рекурсивные функции
Машину Тьюринга
Которые были +- эквивалентны и сводились к ключевому тезису "Все, что мы умеем вычислять может быть сведено к программе на машине Тьюринга". За почти 100 лет более полной модели вычислений так и не придумали, поэтому машина Тьюринга вошла в фундамент компьютерных наук. В современности она в большей степени является теоретическим инструментом -- например с её помощью формулируется проблема P и NP, на практике же мы все время пользуемся эквивалентами машины Тьюринга -- языками программирования (полные по Тьюрингу языки). Вот и суть как раз в том, что машина Тьюринга интересна с точки зрения теории и истории компьютерных наук, но на практике совершенно бесполезна, возможность решить какую-то осмысленную задачу небольшой машиной Тьюринга -- в этом есть определенная красота, но скорее всего никакой практической ценности.
Я этой темой не занимался, но работал со схожими и мне стало интересно. Почитал статью -- понял, что из неё мало что для себя вынесу. И нет, не потому статья плохая, а я всё знаю, а из-за отсутствия ссылок кроме ссылки сайта компании с трекером источника, зато вместо них есть вот это
Блин, ребят, ну я не знаю
Позволю себе оставить здесь цитату из одной популярной статьи на хабре
Вообще кажется, что по сути уникальными являются пункты 1 и 4 (из корректных), 2 -- это применение обычного Дейкстры на модифицированных весах с сохранением оптимальных путей, 3 сводится к обычному сетапу логарифмированием, а веса на вершинах можно перенести на рёбра небольшим преобразованием графа. К слову пункт 2 (из некорректных) вроде как решается Дейкстрой после разделения вершин. В любом случае хорошее обобщение.
У меня большое подозрение, что это все это очень похоже на кратчашие пути на полукольцах. Там есть например такая неочевидная функция: длина пути -- это конкатенация символов вдоль пути, а минимальная длина между s->t -- это longest common prefix всех s->t путей. Нахождение таких "кратчайших путей" например позволяет построить по конечному автомату эквивалентный ему, в котором символы появляются как можно раньше. Как сейчас не знаю, но раньше в распознавании речи это позволяло уменьшить задержку в онлайн сценарии.
Девочка в красном пальто
Как же мастерски автор забайтил на закон Каннингема! Чтож, я повелся!
All software adds features until it is annoyingly complicated. It is then replaced by a "simpler" solution which adds features until it is exactly as complicated
Переводится как
Все программы обрастают новыми фичами пока не становятся раздражающе сложными. Затем они заменяются решениями проще, которые также обрастают новыми фичами, пока не станут настолько же сложными
Боже, что такое вы написали в последнем абзаце? Так вольно интерпретировать, еще и пропустить половину проблемы. Вот две ссылки, где все гораздо более прагматично и менее пафосно. Раздел 5.1.6 заметки Б.Т. Поляка и последнее интервью Канторовича.
Но самое смешное -- это то, что яицеголовому математику-нобелевскому лауреату Канторовичу вы дали по носу видимо совершенно не яицеголовым математиком-нобелевским лауреатом Леонтьевым. Если так было задумано, то браво! Если нет, то пойду грустить от того, что хабр уже не торт.
UPD. Уже было обсуждение про разворот битов, но думаю стоит добавить: clang 19.1.0 компилирует __builtin_bitreverse64 в .... инструкцию vgf2p8affineqb. Кто не в курсе -- это инструкция общего вида для преобразования байта путем умножения его на битовую матрицу 8х8 с арифметкой поля GF(2). Предназначалось это в большей степени для реализации GF(2^8), но нашло и такое интересное применение
взято из Алиса копается
Инлайн
есть, но соврешенно не очевиден интуитивно. А еще я потратил 5 минут, чтобы набрать "тех" с телефона, с ноутбука не смльно лучше. Уверен Вы видели мою статью по кратчайшим путям -- вот там просто жесть была, глючило все, после каждой новой формулы мне приходилось проверять, не сломалась ли какая-нибудь из старых (а они ломались!), я думаю, что из-за этого статья писалась в 3 раза дольше. Больше я на это издевательство не готов. В общем не просто так я теперь в каждой статье предлагаю предлагаю хабру перейти на маркдаун вместо визивиг. Понятно что делать из хабра оверлиф -- это не вариант, но маркдаун -- это формат, принятый по всему миру и он простой. А еще там вполне человеческая поддержка латеха.
Я не разбираюсь во фронте, но уверен, что если дать клич по хабру, то найдутся умельцы, которые сервер с редактором маркдауна и загрузкой картинок поднимут за полдня.
После некоторого обсуждения пришли вот к чему:
Задача нахождения минимального количества свопов в общем случае эквивалентна покрытию эйлерова графа максимальным количеством циклов.
Согласно статье Amir A. et al. On the cost of interchange rearrangement in strings она NP-трудна.
A few moments later ...
Ну кам он =)
Кормен и соавторы теорема 8.1
По поводу вольности написания -- я категорически отказываюсь делать более формальные утверждения до тех пор пока на Хабре нет адекватной поддержки латеха (например markdown вместо wysiwyg). Если вы как-то на это повлияете, то я с удовольствием стану писать подробнее
Видимо вот так
Так смысл анализа инверсий в "адаптивности", чтобы на "почти отсортированной последовательности" было "почти O(n)" и исходный посыл от @vadimr был о том, что пузырёк на адаптивный, но в отличие от вставок его проще применять к спискам
Ну да, такое себе, только с O(n) доп памятью
Скрытый текст
Вообще да, я немного поленился, по идее в реализацию пузырька надо добавить "если во внутреннем цикле ничего не произошло, то завершить процесс". Но вроде как и в этом случае нет ситуации, когда он сделает меньше сравнений, чем сортировка вставками, поэтому везде где можно применить пузырёк вставки сработают лучше
Интересный поворот событий. Если хотите, могу добавить к обсуждению в тг чате питерского CS клуба -- как будто мнения разошлись.
Вот про перетановки я как раз понимал и догадался до "сортируем ссылки хорошей сортировкой, свопаем оъекты по циклам" (и по хорошему на практике только так и надо делать), но то, что сортировка выбором делает вторую часть -- это я упустил. Но ничего, получил бурю эмоций и урок на всю жизнь.
Для меня до сих не очевидно как быть если есть повторяющиеся элементы.
А есть референс на т.3 вне taocp?
Вы лучше скажите, получилось ли у меня Вас удивить?)
Грубо, в этом не было нужды -- мне это было понятно и без Вашего комментария. В диалог я вступил осознанно.
Я сам бываю грубым, только в ответ на вопиющее неуважение, и даже в таком случае представляю претензии по существу и вступаю в диалог.