Русский
Русский
English
Авторизация
Ip-адрес
Восстановление пароля
Регистрация
Статистика
Реклама

Рекурсия

Перевод Как учить рекурсию разработчикам программного обеспечения

10.02.2021 14:12:50 | Автор: admin

Пришло время переосмыслить обучение рекурсии с помощью реальных кейсов вместо элегантных математических уравнений




Для программистов, особенно программистов-самоучек, первое знакомство с миром рекурсии в основном связано с математикой. При упоминании рекурсии программисты сразу вспоминают некоторые из наших любимых слов на F нет, не те самые слова на F, а:

Фибоначчи

function fibonacci(position) {if (position < 3) return 1;return fibonacci(position - 1) + fibonacci(position - 2);}

Факториал

function factorial(num) {if (num === 1) return num;return num * factorial(num - 1);}


Рекурсивные версии функций Фибоначчи и факториала одни из самых красивых фрагментов кода, которые можно увидеть. Эти краткие фрагменты при выполнении работы полагаются лишь на самих себя. Они воплощают в себе определение рекурсии функции, которая вызывает себя (вызов самой себя это рекурсия). Меня совсем не удивляет тот факт, что функции Фибоначчи и факториалы инкапсулируют тему рекурсии наподобие разнообразных руководств, которые показывает пример работы кода на основе счётчиков или TODO-листов. Фибоначчи и факториалы настолько же тривиальны, как счётчики или TODO-листы.

Возможно, вы слышали выражение, что все итерационные алгоритмы можно выразить рекурсивно. Другими словами, функция, использующая цикл, может быть переписана для использования самой себя. Теперь, если любой итерационный алгоритм может быть написан рекурсивно, то же самое должно быть верно и для обратного.

Примечание: итерационный алгоритм или функция это алгоритм, который использует цикл для выполнения работы.

Давайте вернёмся к рекурсивной функции Фибоначчи и вместо этого запишем её как итеративную функцию Фибоначчи:

function fibonacci(index = 1) {let sequence = [0, 1, 1];if (index < 3) return 1;for (let i = 2; i < index; i++) {sequence.push(sequence[sequence.length - 1] + sequence[sequence.length - 2]);}return sequence[index];}

Давайте возьмём рекурсивную функцию факториала и напишем её как итеративную функцию:

function factorial(num) {if (num === 1) return 1;for (let i = num  1; i >= 1; i--) {num = num * i;}return num;}

Оба подхода приводят к одному и тому же выводу. Если вы возьмёте одинаковые входные данные, то функции дадут один и тот же результат. Даже путь, по которому они прошли, возможно, один и тот же. Единственное различие заключается в метафорическом способе транспортировки, используемом на пути к получению результата.

Итак, если мы можем писать рекурсивные функции итеративно, зачем нам вообще нужно беспокоиться о рекурсии и какая от этого польза в программировании?

Основная причина, по которой мы используем рекурсию, упрощение алгоритма до терминов, легко понятных большинству людей. Здесь важно отметить, что цель рекурсии (или, скорее, преимущество от рекурсии) состоит в том, чтобы сделать наш код более понятным. Однако важно знать, что рекурсия не является механизмом, который используется для оптимизации кода скорее всего, это может иметь неблагоприятное влияние на производительность по сравнению с эквивалентной функцией, написанной итеративно.

Краткий вывод из этого: рекурсивные функции повышают читаемость кода для разработчиков, а итерационные функции оптимизируют производительность кода.

Во многих статьях и руководствах по рекурсии, которые я читал раньше, разочаровывает то, что они склоняются к осторожности и зацикливаются только на разговоре о таких функциях, как рекурсивные Фибоначчи или факториалы. Их рекурсивное написание не даёт разработчикам никаких реальных преимуществ. Это всё равно, что рассказать шутку без каких-либо предпосылок к ней.

Если преобразовать рекурсивные функции в итерационные, мы также получаем довольно неплохой код. Пожалуй, он так же легко читаем, как и его рекурсивные эквиваленты. Конечно, он может не иметь такого же уровня элегантности, но если он всё ещё читаем, я собираюсь пойти дальше и отдать предпочтение оптимизации кода, чем наоборот.

Поэтому кажется правдоподобным, что многие люди, впервые изучающие рекурсию, с трудом могут увидеть реальную пользу от её использования. Может быть, они просто видят в этом некую чрезмерную абстракцию. Так чем же полезна рекурсия? Или, ещё лучше, как мы можем сделать изучение рекурсии полезным?

Полезную рекурсию можно найти, когда мы на самом деле пытаемся написать код, напоминающий сценарий из реальной жизни.

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

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

Итак, теперь, когда мы подошли к этой теме, давайте представим следующий кейс: ваш босс прислал вам структуру данных, состоящую из разных отделов, каждый из которых содержит E-mail всех, кто работает в этом отделе. Однако отдел может состоять из подразделений: объектов и массивов разного уровня. Ваш босс хочет, чтобы вы написали функцию, которая сможет отправлять электронное письмо на каждый из этих адресов электронной почты.

Вот структура данных:

const companyEmailAddresses = {finance: ["jill@companyx.com", "frank@companyx.com"],engineering: {qa: ["ahmed@companyx.com", "taylor@companyx.com"],development: ["cletus@companyx.com", "bojangles@companyx.com", "bibi@companyx.com"],},management: {directors: ["tanya@companyx.com", "odell@companyx.com", "amin@companyx.com"],projectLeaders: ["bobby@companyx.com","jack@companyx.com","harry@companyx.com","oscar@companyx.com",],hr: ["mo@companyx.com", "jag@companyx.com", "ilaria@companyx.com"],},sales: {business: {senior: ["larry@companyx.com", "sally@companyx.com"],},client: {senior: ["jola@companyx.com", "amit@companyx.com"],exec: ["asha@companyx.com", "megan@companyx.com"],},},};

И как же с этим справиться?

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

Наш окончательный код может выглядеть примерно так:

function sendEmail(emailAddress) {console.log(`sending email to ${emailAddress}`);}function gatherEmailAddresses(departments) {let departmentKeys = Object.keys(departments);for (let i = 0; i < departmentKeys.length; i++) {if (Array.isArray(departments[departmentKeys[i]])) {departments[departmentKeys[i]].forEach((email) => sendEmail(email));} else {for (let dept in departments[departmentKeys[i]]) {if (Array.isArray(departments[departmentKeys[i]][dept])) {departments[departmentKeys[i]][dept].forEach((email) => sendEmail(email));} else {for (let subDept in departments[departmentKeys[i]][dept])if (Array.isArray(departments[departmentKeys[i]][dept][subDept])) {departments[departmentKeys[i]][dept][subDept].forEach((email) => sendEmail(email));}}}}}}

Я проверил вывод этого кода, может быть, я даже написал для него небольшой модульный тест. Этот код неразборчивый, но он работает. Учитывая количество вложенных циклов, можно утверждать, что он крайне неэффективен. А кто-то на заднем плане может кричать: Big O? Больше похоже на Big OMG, верно?

Конечно, есть и другие способы решения этой задачи, но то, что у нас есть на данный момент, работает. В любом случае, это всего лишь небольшая функция, и там не так много адресов электронной почты, и, вероятно, она не будет использоваться часто, так что это не имеет значения. Давайте вернёмся к работе над более важными проектами, прежде чем босс найдёт для меня еще одну побочную задачу!

Через пять минут ваш босс возвращается и говорит, что он также хочет, чтобы функция работала, даже если новые отделы, подразделения и адреса электронной почты будут добавлены в эту структуру данных. Это меняет ситуацию, потому что теперь мне нужно учитывать возможность наличия подподподразделений, подподподподразделений и так далее.

Внезапно итерационная функция больше не удовлетворяет критериям.

Но, о чудо, мы можем использовать рекурсию!

function sendEmail(emailAddress) {console.log(`sending email to ${emailAddress}`);}function gatherEmailAddresses(departments) {let departmentKeys = Object.keys(departments);departmentKeys.forEach((dept) => {if (Array.isArray(departments[dept])) {return departments[dept].forEach((email) => sendEmail(email));}return gatherEmailAddresses(departments[dept]);});}

Итак, наконец-то у нас есть функция, которая использует рекурсию в более-менее реальном кейсе. Давайте разберёмся, как это всё работает.

Наша функция перебирает ключи из companyEmailAddresses, проверяет, является ли значение этого ключа массивом, и если да, то отправляет электронное письмо каждому значению в этом массиве. Однако, если значение вышеупомянутого ключа не является массивом, она снова вызовет себя gatherEmailAddresses (функция рекурсивно выполняется). Однако вместо того чтобы передавать весь объект companyEmailAddresses, как это было в первый раз, функция просто передаст узел объекта для подкаталога, через который он изначально проходил в цикле.

Эта функция имеет два преимущества по сравнению с нашим предыдущим итеративным аналогом:

Она соответствует дополнительным критериям, установленным нашим начальником. Пока функция продолжает следовать тому же шаблону, она может обрабатывать любые новые объекты или массивы, добавленные к ней, без необходимости изменять ни одной строчки кода;

Код легко читаем. У нас нет набора вложенных циклов, которые наш мозг должен попытаться отслеживать.

Также можно заметить, что наша функция на самом деле содержит итеративные и рекурсивные элементы. Нет причин, по которым алгоритм должен быть исключительно тем или иным. Совершенно нормально иметь что-то итеративное, например функцию forEach, содержащую рекурсивные вызовы самой себя.

Давайте на мгновение вернёмся ко второму пункту. Функцию будет легче читать, только если вы поймёте, как работает рекурсия вне рамок Фибоначчи, факториала и любых других подобных функций, которые можно найти в книге/курсе To Crack The Coding Interview. Итак, давайте немного углубимся в то, что именно происходит внутри нашей рекурсивной функции.

Наша функция принимает в качестве единственного параметра одно значение объект. Передаваемый объект это переменная companyEmailAddresses, представляющая собой гротескного монстра:

const companyEmailAddresses = {finance: ["jill@companyx.com", "frank@companyx.com"],engineering: {qa: ["ahmed@companyx.com", "taylor@companyx.com"],development: ["cletus@companyx.com", "bojangles@companyx.com", "bibi@companyx.com"],},management: {directors: ["tanya@companyx.com", "odell@companyx.com", "amin@companyx.com"],projectLeaders: ["bobby@companyx.com","jack@companyx.com","harry@companyx.com","oscar@companyx.com",],hr: ["mo@companyx.com", "jag@companyx.com", "ilaria@companyx.com"],},sales: {business: {senior: ["larry@companyx.com", "sally@companyx.com"],},client: {senior: ["jola@companyx.com", "amit@companyx.com"],exec: ["asha@companyx.com", "megan@companyx.com"],},},};

Первое, что мы делаем с ним, это выполняем метод Object.keys(), который возвращает массив с каждым отделом. Примерно так: ["finance", "engineering","management", "sales"]. Затем мы проходим по companyEmailAddresses с помощью forEach, используя массив отделов как способ проверить каждый отдел на предмет определённых вещей. В нашем случае мы используем его, чтобы проверить, является ли структура каждого узла массивом или нет, что мы делаем с помощью метода Array.isArray(departments[dept]). Если он возвращает true, мы просто переходим к перебору этого массива, вызывая функцию sendEmail() для каждого значения. Достаточно простая реализация, а до сих пор мы не использовали рекурсию. Возможно, вам даже не нужно было читать этот абзац, но по крайней мере это объяснение здесь есть, если оно вам действительно нужно. В любом случае давайте перейдем к интересному рекурсии.

Если наш метод Array.isArray(departments[dept]) возвращает false, это означает, что мы получили объект, следовательно, он является подразделением. В нашей итеративной функции мы просто повторяли процесс, т. е. выполнили еще один цикл, но сделали это для подразделения. Но вместо этого в рекурсивной функции мы снова вызываем функцию gatherEmailAddresses(), передавая тот же объект companyEmailAddresses, что и раньше. Ключевое отличие здесь в том, что вместо передачи объекта из его корня (весь объект), мы передаём его с позиции подкаталога, где подкаталог становится новым корнем. Мы знаем, что наш объект companyEmailAddresses просто состоит из множества объектов, которые содержат либо объект, либо массив. Поэтому наша функция была написана таким образом, что если она получит массив, она знает, что это конец узла, поэтому она будет пытаться отправить электронные письма. Но если она попадает в объект, ей нужно продолжать работу.

Имеет смысл?

Вот несколько структур, которые я написал, чтобы попытаться пояснить их в дальнейшем.

Весь наш объект состоит из четырёх отделов. Первый отдел это массив. Дополнительного обхода не требуется, поскольку мы сразу попали в листовой узел. Этот отдел вернёт true в Array.isArray().

finance: ["jill@companyx.com","frank@companyx.com"],

Второй отдел это объект. Этот отдел вернёт false в Array.isArray(). Это требует дополнительного обхода, поэтому мы вызываем функцию gatherEmailAddresses(), передавая department[dept], что эквивалентно companyEmailAddresses["engineering"] или коду, который вы видите ниже.

engineering: {qa: ["ahmed@companyx.com","taylor@companyx.com"],development: ["cletus@companyx.com","bojangles@companyx.com","bibi@companyx.com"],},

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

Как вы помните, первое, что делает наша функция, это вызывает Object.keys() для переданного объекта. Это выдаст нам ["qa", "development"]. Затем мы перебираем каждый отдел (или, в данном случае, подразделение). Мы проверяем, является ли отдел/подразделение qa массивом с помощью Array.isArray(). Да, является, поэтому мы вернем true, следовательно мы можем использовать функцию sendEmail(). То же самое может произойти и с "development", поскольку это тоже массив.

engineering: {qa: ["ahmed@companyx.com","taylor@companyx.com"],development: ["cletus@companyx.com","bojangles@companyx.com","bibi@companyx.com"],},

Третий отдел (третье подразделение) имеет аналогичную структуру со вторым отделом (второе подразделение), в то время как четвёртый отдел имеет еще два отдела, а эти два отдела также содержат очередные два отдела а наша рекурсивная функция проходит по каждому из них. Я не приложил фрагмент кода для этого случая, поскольку считаю, что вы уже поняли, как работает рекурсия.

Заключение


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

Однако я хотел бы еще раз подчеркнуть: если вы используете рекурсию, производительность кода может снизиться, хотя этого не должно быть. Рекурсия не должна внезапно стать вашим привычным инструментом вместо итерации. Выгода, которую вы добились в читаемости кода, может быть потеряна в его производительности. В конечном счёте это зависит от представленной вам задачи. Вы столкнётесь с некоторыми задачами в программировании, которые могут хорошо подойти для рекурсии, в то время как другие задачи могут лучше подойти для итераций. В некоторых случаях, например в задаче, с которой мы столкнулись ранее, лучше всего использовать оба подхода. А если вы уже давно выучили рекурсию и хотите новых знаний, например в области data science или machine learning используйте промокод HABR, который дает +10% к скидке на обучение, указанной ниже на баннере.


image


Другие профессии и курсы
ПРОФЕССИИ



КУРС


Подробнее..
Категории: Javascript , Программирование , Блог компании skillfactory , Учебный процесс в it , Учебный процесс , Рекурсия , Skillfactory

Рекурсия сознания ловушка мышления и барьер прогрессу. Исторический очерк

23.06.2020 02:20:15 | Автор: admin
С момента появления языка как второй сигнальной системы инструмента для мышления и общения, человечество получило критическое преимущество перед всеми другими живыми существами, поведение которых управляется системами первого уровня и поэтому принципиально ограничено в уровнях абстрагирования.
Но, давая человеку инструмент огромной силы, язык и абстрактное мышления в то же время создают ограничения и ловушки, ведущие к проблемам, конфликтам и деструктивному поведению. Чем человечество последние 5000 лет в основном и занимается. (Может и 500 000, но нет письменных свидетельств).
90-99% всех войн, конфликтов, ссор и убийств происходят по идейным, идеологическим, религиозным, политическим и другим абстрактным причинам, лежащим в сфере идей и информации, а не материального мира. И прежде чем война, конфликт, ссора приводит к реальным действиям, ей всегда предшествует этап намерения, замысла, подготовки, планирования, нагнетания, организации, проходящий на уровне слов и информации.
Источник и инструмент всех войн, убийств, дискриминации, инквизиции, угнетения язык.
Но он же инструмент науки, культуры, прогресса, развития, цивилизации.
И виноват в проблемах не инструмент, а незрелое мышление, сознание и культура тех, кто его использует.
Еще с античных времен лучшие умы это понимали и пытались исправить.
Aristotle Altemps Inv8575
Наибольший вклад в развитие цивилизации внес, конечно, Аристотель. Разработка формальной логики дала хоть и простой, но все-же общепризнанный и легко применимый инструмент разрешения споров и поиска истины. По сути, это создало основу, фундамент всей Западной цивилизации.
Хотя до сих пор формальную логику понимает и умеет пользоваться, по разным оценкам, не более 1-10% населения планеты.
И уже в те времена философы и мыслители, используя этот инструмент, натолкнулись на ловушку рекурсии, лежащую в основе значительной части парадоксов, апорий и логических противоречий.
Парадокс лжеца, апории Зенона, множество других парадоксов в основе всех одна и та же мыслительная ошибка. Считать, что высказывание, направленное само на себя, ничем не отличается от высказываний, имеющих другое основание.
Это высказывание написано на русском языке, Это высказывание истинное рекурсивные высказывания без парадокса.
Это высказывание ложное пример парадоксальной рекурсии.
Некоторые античные мыслители даже сошли с ума или покончили жизнь самоубийством, пытаясь разрешить такие загадки.
Но выхода так и не нашли.
Философы средневековья и Возрождения потратили тысячи часов на решения подобных и еще более схоластических вопросов, но единственным продуктом были все более и более абстрактные теории, в которых авторы избретали новые названия для старых категорий и все больше в них запутывались.
Как ехидно заметил Пуанкаре,
"все, что ученый на самом деле создает это язык, которым он это возвещает."

Выходы из логического тупика начали находить только по мере развития естественных и точных наук где-то к началу XX века. Нашлись они, как и можно было ожидать, представителями самой формальной и точной науки математики.
Bertrand Russell transparent bg
Б. Рассел в своих Основаниях математики (1903) показал, что класс не может включать сам себя в виде элемента класса, а тип не может быть сам себе подтипом. Аналогично множество, включающее само себя в качестве подмножества, обладает особыми свойствами и не может рассматриваться в ряду обычных множеств, не приводя к логическим ошибкам указанного типа.
1925 kurt gdel
Наиболее полно и красиво разобрался с этой проблемой Курт Гёдель, опубликовавший в 1931 году свои знаменитые теоремы о неполноте:
Любая формальная система аксиом содержит неразрешенные предположения

Логическая полнота (или неполнота) любой системы аксиом не может быть доказана врамках этой системы. Для ее доказательства или опровержения требуются дополнительные аксиомы (усиление системы).

Доказательство этой вроде бы простой истины, с которой философы не могли справиться тысячелетиями, не прошло даром для ученого в этой борьбе он подорвал свой разум, поймал серьезную паранойю и умер от голода и истощения, всеми забытый и оставленный.
Так что будьте осторожны с рекурсией, это отражение отражений, из которого можно и не вернуться!

Работы Гёделя оказали серьезное влияние на все точные науки, не только математику.
Einstein 1921 by F Schmutzer - restoration
Его идеи продолжил в физике Альберт Эйнштейн, утверждавший, что
"невозможно решить проблему на том же уровне, на котором она возникла. Нужно стать выше этой проблемы, поднявшись на следующий уровень".
По сути, это та же теорема о неполноте, выраженная в более абстрактной форме.
Не обошли вниманием эту тему и отечественные исследователи.
Ivan Pavlov 1934
Великий ученый и мыслитель Иван Петрович Павлов еще в далеком 1918 году предвосхитил на много лет Структурный Дифференциал А. Коржибского, исследователя уровней абстрагирования, в своих лекциях Об уме вообще, о русском уме в частности:
"действительность, понять которую ставит своей задачей ум, эта действительность является в значительной степени скрытой от него. Она, как говорится, спрятана за семью замками. Между действительностью и умом стоит и должен стоять целый ряд сигналов, которые совершенно
заслоняют эту действительность."

"Что такое наши слова, которыми мы описываем факты, как не новые сигналы, которые могут, в свою очередь, затемнить, исказить истину."

"словесная передача этим другим обстановки всего его дела не соответствует, не воспроизводит точно и полно действительности."

"когда вы начнете оперировать с теми словесными сигналами этикетками, которые вы поставили на место фактов, то здесь фальсификация действительности может достигать огромнейших размеров."


Alfred Korzybski
Это описание тех же уровней абстрагирования, и принципов отношения реальности, языка и сознания, что показаны А. Коржибским на его Структурном Дифференциале в книге Science and Sanity в 1933 году, и даже почти теми же самыми словами.
Но, благодаря картинкам и материальной модели, идеи Коржибского все-таки поняли в тот момент несколько человек, (как, впрочем, и Эйнштейна сразу после публикации Теории Относительности) и в результате этого появились и НЛП, и Дианетика с Сайентологией, и некоторые направления позитивной психологии, маркетинга, рекламы, политтехнологий, пропаганды и других инструментов работы с сознанием. К сожалению, на первоисточник авторы этих разработок предпочитают не ссылаться, чтобы не палить тему.
Но, по крайней мере, идея Карта не территория вышла за рамки научных статей и стала достоянием широкого круга людей и достаточно общепринятым фактом.
А И. Павлов опередил эпоху, и в то непростое время, его глубоко не понял, наверное, вообще никто.
И даже сейчас, через почти 100 лет после этих исследований, публикаций и выступлений, контролировать свое абстрагирование, отслеживать уровни, избегать рекурсии и не попадать в уровневые ловушки умеет не так много людей, на порядки меньше, чем владеют формальной логикой.
Хорошо, что на этом ресурсе собираются люди, близкие к ИТ и программированию, которых с первых шагов в профессии обучают логике, структуре и строгости мышления и которые знают, что программа не должна вызывать сама себя в качестве подпрограммы, массив не может включать сам себя в качестве элемента массива, а переменная не может принимать в качестве значения сама себя.
Но то, что для программистов самоочевидно, совсем не так в других областях науки и деятельности.
Миллионы людей продолжают пытаться выучить язык с помощью языкового описания языка (грамматики), не замечая, что они попадают в логическую ловушку рекурсии без шанса выбраться оттуда.
Когда вы не знаете, как построить предложение на другом языке, чтобы выразить нужную вам мысль, вы сказать этого не можете.
Но когда вы выучили правило и знаете, как построить это предложение, вы все равно сказать это не сможете.
Потому что та зона мозга, которая должна управлять этим действием, занята мыслями о том, как это сделать (правилами).
Это подобно попытке укусить себя за зубы или перерезать нож ножом. Причем этим самым ножом.
Рекурсия в чистом виде.
Но этого почти никто не замечает, кроме психологов-физиологов, которые давно используют такой механизм блокировки речи для исследований языка и мышления.
Психолингвист и методист Стивен Крашен сформулировал эту идею в виде Гипотезы грамматического монитора. Он утверждает, что грамматика не может служить инструментом для порождения устной речи, а только как монитор для последующего контроля и коррекции. Но, исходя из фактов, полученных другими науками, это никакая не гипотеза, а аксиома, следующая из законов логики, математики, психологии, физиологии. И только фрагментация и сегментация наук и все более узкая специализация ученых не позволяет это заметить.
Аналогичные проблемы с бесконтрольным абстрагированием и злоупотреблением рекурсией можно найти в сфере психологии, когда начинают исследовать мышление с помощью мышления, в методологии, когда пытаются управлять управлением с помощью управления, в философии, которая множит абстрактные сущности без всякого страха перед Оккамом, и во многих других сферах человеческой деятельности.
И задача технарей, айтишников, представителей точных наук помочь выбраться из рекурсивной ловушки, дать инструменты структурирования мышления, научить избегать рекурсии и совместно с гуманитариями разработать новые продукты и инструменты, решающие насущные задачи и лишенные рекурсивных замыканий.
Одним из таких инструментов может быть Структурно-Визуальный метод, разработанный автором этой статьи. Он предлагает для структурирования знаний в некоторой предметной области использовать визуальное представление структуры с использованием цвета для кодирования ограниченного количества смыслов самого верхнего уровня абстракции.
С помощью этого метода были получены некоторые интересные схемы и модели для разных предметных областей ИТ, управления, психологии, лингвистики, педагогики, изучения иностранных языков, а их практическое применение оказалось довольно результативным и перспективным.
Но об этом в следующих статьях, если это будет интересно читателям Хабра.

Успехов вам в любой деятельности и осознанного абстрагирования!
Подробнее..
Категории: Мозг , Визуализация данных , Научно-популярное , Мышление , Математика , Психология , Рекурсия , Изучение языков , Язык , Логика , Абстрагирование , Философия , Лингвистика

SQL HowTo 1000 и один способ агрегации

19.06.2020 12:20:11 | Автор: admin
Наш СБИС, как и другие системы управления бизнесом, не обходится без формирования отчетов каждый руководитель любит сводные цифры, особенно всякие суммы по разделам и красивые "Итого".

А чтобы эти итоги собрать, необходимо по исходным данным вычислить значение некоторой агрегатной функции: количество, сумма, среднее, минимум, максимум, и, как правило, не одной.


Сегодня мы рассмотрим некоторые способы, с помощью которых можно вычислить агрегаты в PostgreSQL или ускорить выполнение SQL-запроса.

Совместные агрегаты


Давайте сразу возьмем задачу чуть посложнее, чем тривиальное вычисление единственного агрегата. Попробуем вычислить по одной и той же выборке несколько агрегатов одновременно, и пусть это будут количество и сумма элементов в некотором входном наборе:

->  $1 = '{2,3,5,7,11,13,17,19}'<-  count | sum      8 |  77

Это самый-самый простой случай просто сразу одновременно в запросе пишем count и sum:

SELECT  count(*), sum(prime)FROM  unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime;

И хоть агрегатных функций мы использовали две, в плане у нас все хорошо узел Aggregate выполнялся всего лишь один раз:


Несовместимые агрегаты


Проблемы начинаются, если мы хотим вычислить сразу несколько агрегатов, но вот у каждого из них разные условия [не]включения одной и той же записи исходного набора. Например, попробуем вычислить для нашего набора количество чисел больше и меньше 10 отдельными полями:

->  $1 = '{2,3,5,7,11,13,17,19}'<-  countlt | countgt        4 |       4

Вложенные запросы


Понятно, что это можно сделать самым примитивным способом вложенными запросами к CTE, каждый из которых сначала выфильтровывает себе из общей выборки подходящий под условия кусочек, а потом считает на нем отдельный агрегат:

WITH src AS (  SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime) SELECT  (SELECT count(*) FROM src WHERE prime < 10) countlt, (SELECT count(*) FROM src WHERE prime > 10) countgt;



Какие из этого плана можно сделать выводы? Много бегаем и много фильтруем дважды [CTE Scan + Rows Removed by Filter: 4].

А если выборка будет из 10K записей, а агрегатов захочется 3-4-5?.. Совсем нехорошо.

FILTER-агрегаты


Этот вариант, наверное, самый простой и понятный:

SELECT  count(*) FILTER(WHERE prime < 10) countlt, count(*) FILTER(WHERE prime > 10) countgtFROM  unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime;



Он идеален во всех отношениях, быстро и эффективно решает все наши задачи, но имеет и ложку дегтя доступен только с версии 9.4 (мало ли у кого что на бою стоит).

Агрегаты от условия


Допустим, 9.4 еще не подвезли, а запрос все-таки хочется написать в один проход. В этом случае можно воспользоваться знанием, что count(*) FILTER(WHERE cond) эквивалентно sum(CASE cond):

SELECT  sum(CASE WHEN prime < 10 THEN 1 ELSE 0 END) countlt, sum(CASE WHEN prime > 10 THEN 1 ELSE 0 END) countgtFROM  unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime;

Или можно чуть короче, если вспомнить о возможности скастовать boolean в integer вместо CASE с результатами 1/0:

SELECT  sum((prime < 10)::integer) countlt, sum((prime > 10)::integer) countgtFROM  unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime;

Вообще, подход вычисления агрегата от некоторого условия достаточно универсален, но имеет и свои подводные камни.

Агрегация в массив


Допустим, мы хотим теперь получить не просто количество чисел, подходящих под то или иное условие, но массивы из них состоящие:

->  $1 = '{2,3,5,7,11,13,17,19}'<-   primeslt |   primesgt  {2,3,5,7} | {11,13,17,19}

И тут нам тоже поможет агрегат ведь он возвращает одно значение, но тип его может быть не обязательно скаляром, но записью таблицы или даже массивом с помощью array_agg.

Вариант с использованием FILTER очевиден:

WITH src AS (  SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime)SELECT  array_agg(prime) FILTER(WHERE prime < 10) primeslt, array_agg(prime) FILTER(WHERE prime > 10) primesgtFROM  src;



А вот если попытаться превратить его в агрегат от условия придется разбираться с попаданием в набор NULL'ов, что уже совсем невесело:

WITH src AS (  SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime) , tmp AS (  SELECT    array_agg(CASE WHEN prime < 10 THEN prime END) primeslt -- {2,3,5,7,NULL,NULL,NULL,NULL}  , array_agg(CASE WHEN prime > 10 THEN prime END) primesgt -- {NULL,NULL,NULL,NULL,11,13,17,19}  FROM    src)SELECT  ARRAY(SELECT * FROM unnest(primeslt) prime WHERE prime IS NOT NULL) primeslt, ARRAY(SELECT * FROM unnest(primesgt) prime WHERE prime IS NOT NULL) primesgtFROM  tmp;

Но если вам хоть немного повезло, и стоит хотя бы версия 9.3, то можно воспользоваться функцией array_remove для достижения того же эффекта:

WITH src AS (  SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime) SELECT  array_remove(array_agg(CASE WHEN prime < 10 THEN prime END), NULL) primeslt, array_remove(array_agg(CASE WHEN prime > 10 THEN prime END), NULL) primesgtFROM  src;

Несколько агрегатов: Function Scan vs CTE


Мы тут внезапно вынесли наш исходный набор в CTE а почему? Потому что так банально быстрее. Давайте проверим на простом примере:

SELECT  array_agg(i) FILTER(WHERE i % 2 = 0) even, array_agg(i) FILTER(WHERE i % 2 = 1) oddFROM  generate_series(1, 1000000) i;




WITH src AS (  SELECT generate_series(1, 1000000) i)SELECT  array_agg(i) FILTER(WHERE i % 2 = 0) even, array_agg(i) FILTER(WHERE i % 2 = 1) oddFROM  src;



Почти на 40% быстрее! Пример, конечно, вырожденный, но эффект имеет место быть.

DISTINCT + OVER


Еще один способ агрегации за единственный проход заключается в использовании уникализации выборки с помощью DISTINCT и применения окна к агрегатной функции:

WITH src AS (  SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime)SELECT DISTINCT  array_agg(prime) FILTER(WHERE prime < 10) OVER() primeslt, array_agg(prime) FILTER(WHERE prime > 10) OVER() primesgtFROM  src;

Единственная проблема такая группировка небесплатна:



Сложный агрегат


Но предположим, что мы хотим что-то этакое сложное, для чего нет подходящего агрегата:

->  $1 = '{2,3,5,7,11,13,17,19}'<-                 exp                  |   val  2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 = | 9699690

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

Соберем запрос, который решит нашу задачу:

WITH RECURSIVE src AS (  SELECT    *  FROM    unnest('{2,3,5,7,11,13,17,19}'::integer[])      WITH ORDINALITY T(prime, rn)), T(rn, exp, val) AS (  SELECT    0::bigint    -- база агрегации  , '{}'::integer[]  , 1UNION ALL  SELECT    src.rn    -- итеративное вычисление сразу всех агрегатов  , exp || src.prime  , val * src.prime   FROM    T  JOIN    src      ON src.rn = T.rn + 1 -- переход к следующей записи)SELECT  array_to_string(exp, ' * ') || ' = ' exp, valFROM  TORDER BY -- отбор финального результата  rn DESCLIMIT 1;



Кучеряво! Попробуем упростить и ускорить, опираясь на тот факт, что входной аргумент заведомо является массивом то есть может быть перебран поэлементно:

WITH RECURSIVE src AS (  SELECT '{2,3,5,7,11,13,17,19}'::integer[] arr), T(i, exp, val) AS (  SELECT    1::bigint    -- база агрегации  , '{}'::integer[]  , 1UNION ALL  SELECT    i + 1    -- итеративное вычисление сразу всех агрегатов  , exp || arr[i]  , val * arr[i]  FROM    T  , src  WHERE    i <= array_length(arr, 1))SELECT  array_to_string(exp, ' * ') || ' = ' exp, valFROM  TORDER BY -- отбор финального результата  i DESCLIMIT 1;



Намного лучше!

Math.bonus


Применим string_agg и немного математической магии:


WITH src AS (  SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime)SELECT  string_agg(prime::text, ' * ') || ' = ' exp, exp(sum(ln(prime)))::integer val -- для любителей математикиFROM  src;

Подробнее..
Категории: Программирование , Ненормальное программирование , Postgresql , Sql , Высокая производительность , Блог компании тензор , Sql tips and tricks , Базы данных , Explain , Explain.tensor.ru , Array , Unnest , Рекурсия , Агрегаты

У меня зазвонил телефон. Кто говорит?.. Поможет слон

17.08.2020 16:16:01 | Автор: admin
Автоматическое определение клиента и его региона по входящему телефонному звонку стало неотъемлемой частью любой развитой HelpDesk или CRM-системы. Только надо уметь делать это быстро тогда появляется масса возможностей.

Например, можно менеджеру сразу показать из какого города идет звонок, подтянуть актуальный прайс и условия доставки, вывести карточку звонящего клиента, последние сделки с ним, конкретное контактное лицо, да много чего полезного, как это умеет наш СБИС CRM!


А как этот функционал реализовать самостоятельно? Оказывается, не так уж сложно. Собрать и опробовать работающую модель можно, буквально, на коленке нужна только связка из Node.js и PostgreSQL.

Определяем регион по номеру


Давайте предположим, что АТС присылает нам уже нормализованный и отформатированный до 10 цифр (будем рассматривать только звонки внутри России) входящий телефонный номер. Как наиболее эффективно понять, откуда пришел звонок?

Собираем телефонные коды


Сначала нам понадобится база телефонных кодов России в привязке к регионам. Для этого можно воспользоваться официальным источником актуальной выпиской из плана нумерации на сайте Федерального агентства связи.

Но найти мало, надо эти данные скачать и извлечь. В этом нам поможет небольшой скрипт для Node.js, использующий библиотеку request:

const async = require('async')  , request = require('request');const fs = require('fs');let queue = [  'ABC-3xx', 'ABC-4xx', 'ABC-8xx', 'DEF-9xx']  .map(key => (    {      base : 'https://rossvyaz.gov.ru'    , path : `/data/${key}.csv`    }  ));let ranges = [];async.doWhilst(  cb => {    // берем из очереди и загружаем очередную страницу    let task = queue.shift();    request(      {        url  : task.base + task.path      , pool : false      }    , (err, res, body) => {        // примитивный разбор CSV        body.split('\n').forEach(line => {          let tds = line.split(';');          let place = tds[5].split('|');          ranges.push([            tds[0]          , tds[1]          , tds[2]          , tds[4]          , place[place.length - 1]          , place[place.length - 2] && place[place.length - 2].startsWith('р-н') ? place[place.length - 2] : ''          , place.length > 1            ? place[0].startsWith('р-н')              ? ''              : place[0]            : ''          ]);        });        return cb(err);      }    );  }  // итерируем, пока очередь заданий непуста, cb => {    return cb(null, queue.length);  }  // когда все распарсили - подчищаем данные и формируем файл для загрузки в БД, err => {    // чистим коды и диапазоны    ranges.forEach(row => {      // убираем пересечение цифр кода и диапазона      let ln = row[0].length + row[1].length - 10;      if (ln > 0) {        let sfx = row[0].slice(-ln);        if (row[1].startsWith(sfx) && row[2].startsWith(sfx)) {          row[1] = row[1].slice(ln);          row[2] = row[2].slice(ln);        }      }      // пересобираем общий префикс      let pfx;      for (let i = 1; i < row[1].length; i++) {        if (row[2].startsWith(row[1].slice(0, i))) {          pfx = row[1].slice(0, i);        }        else {          break;        }      }      if (pfx) {        row[0] = row[0] + pfx;        row[1] = row[1].slice(pfx.length);        row[2] = row[2].slice(pfx.length);      }    });    let sql = `SET client_encoding = 'UTF-8';CREATE TABLE phonecodes(  code    varchar, numb    varchar, nume    varchar, oper    varchar, region    varchar, district    varchar, city    varchar);COPY phonecodes FROM STDIN;`;    // собираем COPY-формат    let copy = ranges.map(row => row.join('\t')).join('\n') + '\n\\.\n';    fs.writeFileSync('phonecodes.sql', sql + copy);  });

Теперь загрузим его в нашу тестовую базу, и можно работать:

psql -f phonecodes.sql -U postgres tst

Если все сработало как надо, в нашу таблицу будет загружено почти 378 тысяч диапазонов:

SETCREATE TABLECOPY 377937

Замечу, что в нашем примере и код, и граничные номера диапазона представлены строками. Да, их можно превратить в integer/bigint, но мы пока не будем этим заниматься. Тем более, что входящий номер телефона не всегда состоит только из цифр например, некоторые таксофоны могут сообщать свой номер с цифрой A.

Ищут пожарные, ищет милиция...


Сначала попробуем наивный запрос:

WITH src AS (  SELECT '4852262000' num -- входящий номер)SELECT  *FROM  src, phonecodesWHERE  num LIKE (code || '%') AND -- проверяем совпадение кода  num BETWEEN (code || numb) AND (code || nume) -- проверяем вхождение в диапазонLIMIT 1;


[посмотреть на explain.tensor.ru]

Вычитали почти 70 тысяч строк (и это еще повезло, что не все 380!), почти 10MB данных перелопатили не слишком эффективно, но результат достигнут:

num        | code   | numb | nume | oper | region           | district | city-----------------------------------------------------------------------------------4852262000 | 485226 | 0000 | 9999 | МТС  | Ярославская обл. |          | Ярославль

Но давайте как-то избавимся от Seq Scan! Для этого нам всего-то нужен индекс, который поможет искать по LIKE, так ведь?..

Увы, нет. Если нам надо искать column LIKE (val || '%'), то нам помогут префиксные индексы с varchar_pattern_ops, но у нас-то все наоборот val LIKE (column || '%'). И мы получаем ситуацию близкую к той, что я описывал в статье Классифицируем ошибки из PostgreSQL-логов.

Используем знания о прикладной области


Близкую, но, к счастью, все-таки существенно проще данные у нас фиксированы и их относительно немного. Причем по кодам записи распределены достаточно разреженно:

SELECT -- сколько кодов с таким кол-вом диапазонов  ranges, count(*)FROM  (    SELECT -- сколько диапазонов по каждому коду      code    , count(*) ranges    FROM      phonecodes    GROUP BY      1  ) TGROUP BY  1ORDER BY  1 DESC;

Только лишь около сотни кодов имеют по 10 диапазонов, а почти четверть вообще ровно один:

ranges | count--------------    10 |   121     9 |   577     8 |  1705     7 |  3556     6 |  6667     5 | 10496     4 | 12491     3 | 20283     2 | 22627     1 | 84453

Поэтому давайте проиндексируем пока только код. А раз все диапазоны одного кода нам понадобятся все вместе упорядочим нашу таблицу с помощью CLUSTER, чтобы записи лежали физически рядом:

CREATE INDEX ON phonecodes(code);CLUSTER phonecodes USING phonecodes_code_idx;

А теперь вспомним, что телефонный номер у нас состоит ровно (всего!) из 10 цифр, среди которых нам надо вычленить префиксный код. То есть наша задача спокойно решается простым перебором не более чем 10 вариантов:

WITH RECURSIVE src AS (  SELECT '4852262000' num), T AS (  SELECT    num pfx -- в качестве исходного "префикса" задаем весь номер  , NULL::phonecodes pc  FROM    srcUNION ALL  SELECT    substr(pfx, 1, length(pfx) - 1) -- "отщипываем" последнюю цифру  , (      SELECT        X      FROM        phonecodes X      WHERE        code = T.pfx AND -- проверяем полное совпадение префикса        (TABLE src) BETWEEN (code || numb) AND (code || nume) -- проверяем вхождение в диапазон      LIMIT 1    ) pc  FROM    T  WHERE    pc IS NOT DISTINCT FROM NULL AND -- ищем, пока ничего не нашли    length(pfx) > 2 -- ... и префикс еще может оказаться кодом)SELECT  (pc).* -- "разворачиваем" найденную запись диапазона в поляFROM  TWHERE  pc IS DISTINCT FROM NULL;


[посмотреть на explain.tensor.ru]

Нам потребовалось всего 5 обращений к индексу, чтобы найти искомый код. Выигрыш кажется микроскопическим в абсолютных цифрах, но мы получили снижение нагрузки в 150 раз относительно наивного варианта! Если вашей системе приходится обрабатывать десятки и сотни тысяч таких запросов в час экономия становится весьма солидной!
А можно делать еще меньше итераций по индексу если все коды заранее привести к классическому виду от 3 до 5 цифр. Правда, тогда возрастет количество диапазонов в каждом коде, и их фильтрация может добавить проблем.

Определяем клиента по номеру


Теперь давайте представим, что у нас уже есть таблица с клиентами, где записан подчищенный номер телефона убраны все скобки, дефисы, и т.п.

Но вот неприятность, далеко не все и них имеют код города то ли менеджеры ленятся забивать, то ли АТС так настроена, что присылает не полные, а внутригородские номера Как тогда найти клиента ведь поиск по полному соответствию уже не сработает?

АТС дает полный номер


В этом случае воспользуемся тем же переборным алгоритмом. Только отщипывать цифры будем не с конца номера, а с начала.

Если номер в карточке клиента был указан полностью, мы на первой же итерации на него наткнемся. Если не полностью когда отрежем какой-то из подходящих кодов.

Безусловно, нам потребуется какая-то перекрестная проверка по другим реквизитам (адрес, ИНН, ...), чтобы не получилось ситуации, что из входящего номера мы отрезали код Москвы, а по оставшемуся 7-значному номеру нашли клиента из Санкт-Петербурга.

АТС дает городской номер


пришло от АТС      :     262000указано в карточке : 4852262000

Тут ситуация интереснее. Приращивать каждый возможный код к короткому номеру и пробовать искать мы не можем их слишком много. Взглянем на ситуацию с другой стороны буквально:

    reverse(262000) -> 000262reverse(4852262000) -> 0002622584

Оказывается, если развернуть строки с номерами, то задача превращается в обычный префиксный поиск, который легко решается с помощью индекса с varchar_pattern_ops и LIKE!

CREATE INDEX ON client(reverse(phone) varchar_pattern_ops);


SELECT  *FROM  clientWHERE  reverse(phone) LIKE (reverse($1) || '%');

А дальше, опять-таки перепроверяем дополнительную информацию из какого региона АТС нам прислала номер, к какому региону относится клиент.
Подробнее..
Категории: Программирование , Node.js , Postgresql , Sql , Блог компании тензор , Sql tips and tricks , Crm , Рекурсия , Телефония , Определение местоположения

PostgreSQL Antipatterns Бесконечность не предел!, или Немного о рекурсии

01.10.2020 22:19:19 | Автор: admin
Рекурсия очень мощный и удобный механизм, если над связанными данными делаются одни и те же действия вглубь. Но неконтролируемая рекурсия зло, которое может приводить или к бесконечному выполнению процесса, или (что случается чаще) к выжиранию всей доступной памяти.


СУБД в этом отношении работают по тем же принципам "сказали копать, я и копаю". Ваш запрос может не только затормозить соседние процессы, постоянно занимая ресурсы процессора, но и уронить всю базу целиком, съев всю доступную память. Поэтому защита от бесконечной рекурсии обязанность самого разработчика.

В PostgreSQL возможность использовать рекурсивные запросы через WITH RECURSIVE появилась еще в незапамятные времена версии 8.4, но до сих пор можно регулярно встретить потенциально-уязвимые беззащитные запросы. Как избавить себя от проблем подобного рода?

Не писать рекурсивные запросы

А писать нерекурсивные. С уважением, Ваш К.О.

На самом деле, PostgreSQL предоставляет достаточно большое количество функционала, которым можно воспользоваться, чтобы не применять рекурсию.

Использовать принципиально другой подход к задаче


Иногда можно просто взглянуть на задачу с другой стороны. Пример такой ситуации я приводил в статье SQL HowTo: 1000 и один способ агрегации перемножение набора чисел без применения пользовательских агрегатных функций:

WITH RECURSIVE src AS (  SELECT '{2,3,5,7,11,13,17,19}'::integer[] arr), T(i, val) AS (  SELECT    1::bigint  , 1UNION ALL  SELECT    i + 1  , val * arr[i]  FROM    T  , src  WHERE    i <= array_length(arr, 1))SELECT  valFROM  TORDER BY -- отбор финального результата  i DESCLIMIT 1;

Такой запрос можно заменить на вариант от знатоков математики:

WITH src AS (  SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime)SELECT  exp(sum(ln(prime)))::integer valFROM  src;

Использовать generate_series вместо циклов


Допустим, перед нами стоит задача сгенерировать все возможные префиксы для строки 'abcdefgh':

WITH RECURSIVE T AS (  SELECT 'abcdefgh' strUNION ALL  SELECT    substr(str, 1, length(str) - 1)  FROM    T  WHERE    length(str) > 1)TABLE T;

Точно-точно тут нужна рекурсия?.. Если воспользоваться LATERAL и generate_series, то даже CTE не понадобятся:

SELECT  substr(str, 1, ln) strFROM  (VALUES('abcdefgh')) T(str), LATERAL(    SELECT generate_series(length(str), 1, -1) ln  ) X;

Изменить структуру БД


Например, у вас есть таблица сообщений форума со связями кто-кому ответил или тред в социальной сети:

CREATE TABLE message(  message_id    uuid      PRIMARY KEY, reply_to    uuid      REFERENCES message, body    text);CREATE INDEX ON message(reply_to);


Ну и типовой запрос загрузки всех сообщений по одной теме выглядит примерно так:

WITH RECURSIVE T AS (  SELECT    *  FROM    message  WHERE    message_id = $1UNION ALL  SELECT    m.*  FROM    T  JOIN    message m      ON m.reply_to = T.message_id)TABLE T;

Но раз у нас всегда нужна вся тема от корневого сообщения, то почему бы нам не добавлять его идентификатор в каждую запись автоматом?

-- добавим поле с общим идентификатором темы и индекс на негоALTER TABLE message  ADD COLUMN theme_id uuid;CREATE INDEX ON message(theme_id);-- инициализируем идентификатор темы в триггере при вставкеCREATE OR REPLACE FUNCTION ins() RETURNS TRIGGER AS $$BEGIN  NEW.theme_id = CASE    WHEN NEW.reply_to IS NULL THEN NEW.message_id -- берем из стартового события    ELSE ( -- или из сообщения, на которое отвечаем      SELECT        theme_id      FROM        message      WHERE        message_id = NEW.reply_to    )  END;  RETURN NEW;END;$$ LANGUAGE plpgsql;CREATE TRIGGER ins BEFORE INSERT  ON message    FOR EACH ROW      EXECUTE PROCEDURE ins();


Теперь весь наш рекурсивный запрос может быть сведен всего лишь к вот такому:

SELECT  *FROM  messageWHERE  theme_id = $1;

Использовать прикладные ограничители


Если поменять структуру базы мы не в силах по каким-то причинам, давайте посмотрим, на что можно опереться, чтобы даже наличие ошибки в данных не приводило к бесконечному выполнению рекурсии.

Счетчик глубины рекурсии


Просто увеличиваем счетчик на единицу на каждом шаге рекурсии вплоть до момента достижения предела, который мы считаем заведомо неадекватным:

WITH RECURSIVE T AS (  SELECT    0 i  ...UNION ALL  SELECT    i + 1  ...  WHERE    T.i < 64 -- предел)

Pro: При попытке зацикливания мы все равно сделаем не более указанного лимита итераций вглубь.
Contra: Нет гарантии, что мы не обработаем повторно одну и ту же запись например, на глубине 15 и 25, ну и дальше будет каждые +10. Да и про вширь никто ничего не обещал.

Формально, такая рекурсия не будет бесконечной, но если на каждом шаге количество записей увеличивается по экспоненте, мы все хорошо знаем, чем это кончается

см. Задача о зёрнах на шахматной доске

Хранитель пути


Поочередно дописываем все встретившиеся нам по пути рекурсии идентификаторы объектов в массив, который является уникальным путем до него:

WITH RECURSIVE T AS (  SELECT    ARRAY[id] path  ...UNION ALL  SELECT    path || id  ...  WHERE    id <> ALL(T.path) -- не совпадает ни с одним из)

Pro: При наличии цикла в данных мы абсолютно точно не станем обрабатывать повторно одну и ту же запись в рамках одного пути.
Contra: Но при этом мы можем обойти, буквально, все записи, так и не повторившись.

см. Задача о ходе коня

Ограничение длины пути


Чтобы избежать ситуации блуждания рекурсии на непонятной глубине, мы можем скомбинировать два предыдущих метода. Или, если не хотим поддерживать лишних полей, дополнить условие продолжения рекурсии оценкой длины пути:

WITH RECURSIVE T AS (  SELECT    ARRAY[id] path  ...UNION ALL  SELECT    path || id  ...  WHERE    id <> ALL(T.path) AND    array_length(T.path, 1) < 10)

Выбирайте способ на свой вкус!
Подробнее..
Категории: Программирование , Postgresql , Sql , Администрирование баз данных , Блог компании тензор , Sql tips and tricks , Рекурсия , Триггер , Иерархия

Перевод Избегайте рекурсии в Python вспомните о замыкании

25.02.2021 16:13:17 | Автор: admin


Вот что получается, когда кандидат наук заморачивается рекурсией

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

Одно из гораздо лучших решений по возможности задействовать динамическое планирование: вероятно, оно лучший способ решать задачи, которые можно разделить на подзадачи. Одна из моих предыдущих статей демонстрирует мощь динамического планирования.


Здесь я представлю ещё одну технику Python, которую можно использовать как альтернативу рекурсивной функции. Эта техника не превосходит динамическое планирование, но она гораздо проще, с точки зрения мышления. Другими словами, иногда сложно заставить динамическое планирование работать из-за абстракции идей, тогда как проще воспользоваться замыканием.

Что такое замыкание в Python?


Прежде всего позвольте мне на простом примере продемонстрировать, что такое замыкание в Python. Посмотрите на функцию ниже:

def outer():x = 1def inner():print(f'x in outer function: {x}')return inner

Функция outer определяется с функцией inner внутри, а функция outer возвращает функцию inner; именно она возвращаемое значение outer.

Здесь вложенная функция это и есть замыкание. Если проверить возвращаемое значение внешней функции, окажется, что оно является функцией.


Что делает замыкание? Поскольку оно вернуло функцию, мы, конечно, можем запустить её.


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


Следовательно, мы также можем сказать, что в замыкании Python мы определили функцию, которая определяет функции.

Доступ к внешним переменным из внутренней функции


Как тогда мы можем использовать замыкание, чтобы заменить им рекурсию? Не торопитесь. Давайте посмотрим на другую проблему, связанную с доступом к внешним переменным из внутренней функции.

def outer():x = 1def inner():print(f'x in outer function (before modifying): {x}')x += 1print(f'x in outer function (after modifying): {x}')return inner

В замыкании выше мы хотим добавить 1 к внешней переменной x во внутренней функции. Это работает неочевидным образом.


По умолчанию вы не сможете получить доступ к внешней переменной из внутренней функции. Однако так же, как мы определяем глобальную переменную в Python, мы можем сообщить внутренней функции замыкания, что переменная не должна рассматриваться как локальная, это делается с помощью ключевого слова nonlocal.

def outer():x = 1def inner():nonlocal xprint(f'x in outer function (before modifying): {x}')x += 1print(f'x in outer function (after modifying): {x}')return inner

Теперь предположим, что мы хотим пять раз добавить единицу к переменной x. Можно просто написать цикл for.

f = outer()for i in range(5):print(f'Run {i+1}')f()print('\n')


Фибоначчи с помощью замыкания


Фибоначчи обычно используется как пример рекурсивных функций, как рекурсивный Hello, World!. Напомню, о чём речь. Последовательность Фибоначчи это ряд чисел, каждое следующее число это сумма двух чисел перед ним. Первые два числа, X и X, особенные. Это 0 и 1. Значит, X, как упоминалось выше, это сумма X и X. И так далее [сократил].

Рекурсивная функция требует, чтобы мы мыслили в обратном порядке, от текущей ситуации к предыдущей ситуации и, в конечном счёте, об условии завершения рекурсии. При помощи замыкания можно думать о проблеме более естественным образом. В коде ниже показана реализация Фибоначчи через замыкание:

def fib():x1 = 0x2 = 1def get_next_number():nonlocal x1, x2x3 = x1 + x2x1, x2 = x2, x3return x3return get_next_number

Мы знаем, что Фибоначчи начинается с двух специальных чисел X = 0 и X = 1, поэтому просто определяем их во внешней функции. Затем внутренняя функция get_next_number просто возвращает сумму двух чисел, полученных от внешней функции. Кроме того, не забудьте обновить X и X с помощью X и X. Код можно упростить:

...x3 = x1 + x2x1, x2 = x2, x3return x3

Вот так:

x0, x1 = x1, x0 + x1return x1

Этот код сначала обновляет две переменные, а затем возвращает вторую, что эквивалентно коду выше. Затем мы можем использовать это замыкание, чтобы вычислить числа Фибоначчи. Например, вот последовательность Фибоначчи до двадцатого.

fibonacci = fib()for i in range(2, 21):num = fibonacci()print(f'The {i}th Fibonacci number is {num}')




Сравниваем производительность


А как насчёт производительности? Давайте сравним! Сначала реализуем функцию Фибоначчи рекурсивно:

def fib_recursion(n):if n == 0:return 0elif n == 1:return 1else:return fib_recursion(n-1) + fib_recursion(n-2)

Функцию можно проверить: вывести 20-е число последовательности Фибоначчи.


Теперь напишем то же самое с замыканием.

def fib_closure(n):f = fib()for i in range(2, n+1):num = f()return num



Сравниваем скорость.


2,79 мс против 2,75 мкс. Замыкание в 1000 раз быстрее рекурсии! Интуитивно понятно: причина в том, что все временные значения для каждого уровня рекурсии хранятся в памяти отдельно, тогда как замыкание каждый раз обновляет одни и те же переменные. Кроме того, существует ограничение глубины рекурсии. В случае замыкания, поскольку это в основном цикл for, никаких ограничений нет. Вот пример получения 1000-го числа Фибоначчи.


Это действительно огромное число, но метод замыкания может завершить вычисление примерно за 100 мкс, тогда как рекурсия сталкивается со своими ограничениями.

Как ещё применять замыкание?


Замыкания Python очень полезны не только как замена рекурсивных функций. В некоторых случаях оно также может заменить классы Python на решение изящнее, особенно когда в классе не слишком много атрибутов и методов. Предположим, у нас есть словарь студентов с их экзаменационными отметками.

students = {'Alice': 98,'Bob': 67,'Chris': 85,'David': 75,'Ella': 54,'Fiona': 35,'Grace': 69}

Хочется иметь несколько функций, которые помогут нам фильтровать студентов по оценкам, помещать их в разные классы. Однако со временем критерии могут измениться. В этом случае можно определить замыкание Python, вот так:

def make_student_classifier(lower_bound, upper_bound):def classify_student(exam_dict):return {k:v for (k,v) in exam_dict.items() if lower_bound <= v < upper_bound}return classify_student

Замыкание определяет функцию, которая, в свою очередь, определяет другие функции на основе динамически передаваемых параметров. Мы передадим нижнюю и верхнюю границы класса оценки, и замыкание вернёт нам функцию, которая отфильтрует студентов.

grade_A = make_student_classifier(80, 100)grade_B = make_student_classifier(70, 80)grade_C = make_student_classifier(50, 70)grade_D = make_student_classifier(0, 50)

Код выше даёт нам 4 функции, которые классифицируют учащегося по соответствующим классам на основе указанных нами границ. Обратите внимание, что мы можем изменить границу в любой момент, чтобы выполнить другую функцию или переопределить текущие функции оценки. Давайте теперь проверим функции.


Выглядит очень аккуратно! Но имейте в виду, что в более сложных случаях всё равно нужно определять классы.

Что в итоге?


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

В самом деле, замыкание может оказаться не лучшим решением некоторых проблем, с точки зрения производительности, особенно когда применимо динамическое планирование. Однако намного проще работать с ним в плане мышления. Иногда динамическое планирование излишне: например, когда не так уж важна производительность, может быть достаточно замыкания.

Замыкание также может использоваться, чтобы заменить некоторые юзкейсы, для удовлетворения которым мы можем захотеть реализовать класс. В таких случаях замыкание выглядит аккуратнее и элегантнее.

image
Узнайте подробности, как получить Level Up по навыкам и зарплате или востребованную профессию с нуля, пройдя онлайн-курсы SkillFactory со скидкой 40% и промокодом HABR, который даст еще +10% скидки на обучение:

Подробнее..
Категории: Программирование , Python , Совершенный код , Блог компании skillfactory , Рекурсия , Skillfactory , Замыкания

Перевод Парсим протобаф на скорости больше 2 Гбс. как я научился любить хвостовую рекурсию в C

12.05.2021 18:04:50 | Автор: admin


Отличную функцию недавно добавили в основную ветку компилятора Clang. С помощью атрибутов [[clang::musttail]] или __attribute__((musttail)) теперь можно получить гарантированные хвостовые (tail) вызовы в C, C++ и Objective-C.

int g(int);int f(int x) {    __attribute__((musttail)) return g(x);}

(Онлайн-компилятор)

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

Применение этого подхода в парсинге протокола сериализации дало поразительные результаты: мы смогли парсить на скорости свыше 2 Гб/с., более чем вдвое быстрее лучшего предыдущего решения. Это ускорение будет полезно во многих ситуациях, так что неверно будет ограничиваться одним лишь утверждением хвостовые вызовы == двукратное ускорение. Однако эти вызовы ключевой элемент, благодаря которому стал возможен такой прирост скорости.

Я расскажу, в чём достоинства хвостовых вызовов, как мы с их помощью парсим протокол и как можно распространить эту методику на интерпретаторы. Думаю, что благодаря ей интерпретаторы всех основных языков, написанных на С (Python, Ruby, PHP, Lua и т.д.), могут получить значительный прирост производительности. Главный недостаток связан с портируемостью: сегодня musttail является нестандартным расширением компилятора. И хотя я надеюсь, что оно приживется, однако пройдет некоторое время, прежде чем расширение распространится достаточно широко, чтобы C-компилятор вашей системы мог его поддерживать. При сборке вы можете пожертвовать эффективностью в обмен на портируемость, есть окажется, что musttail недоступно.

Основы хвостовых вызовов


Хвостовой вызов это вызов любой функции, находящейся в хвостовом положении, последнее действие перед тем, как функция вернёт результат. При оптимизации хвостовых вызовов компилятор компилирует для хвостового вызова инструкцию jmp, а не call. Тогда не выполняются служебные действия, которые в обычной ситуации позволяют вызываемой g() возвращать вызывающей f(), например, создание нового фрейма стека или передача адреса возврата. Вместо этого f() напрямую обращается к g(), как если бы та была частью неё самой, а g() возвращает результат напрямую тому, кто вызвал f(). Эта оптимизация безопасна, потому что фрейм стека f() больше не нужен после начала хвостового вызова, ведь стало невозможно обратиться к какой-либо локальной переменной f().

Пусть это и выглядит банально, но у такой оптимизации есть две важные особенности, открывающие новые возможности по написанию алгоритмов. Во-первых, при выполнении n последовательных хвостовых вызов стек памяти уменьшается с O(n) до O(1). Это важно потому, что что стек ограничен и переполнение может обрушить программу. Так что без этой оптимизации некоторые алгоритмы являются опасными. Во-вторых, jmp избавляет от избыточной производительности call, и в результате вызов функции становится таким же эффективным, как и любая другая ветка. Обе эти особенности позволяют использовать хвостовые вызовы в качестве эффективной альтернативы обычным итеративным структурам управления вроде for и while.

Эта идея вовсе не нова и восходит к 1977 году, когда Гай Стил (Guy Steele) написал целую работу, в которой утверждал, что вызовы процедур повышают чистоту архитектур по сравнению с GOTO, и что при этом оптимизация хвостовых вызовов позволяет не терять в скорости. Это была одна из Лямбда-работ, написанных в период с 1975 по 1980, в которых был сформулировано много идей, лёгших в основу Lisp и Scheme.

Оптимизация хвостовых вызовов даже для Clang не в новинку. Он и до этого мог оптимизировать их, как GCC и многие другие компиляторы. На самом деле атрибут musttail в этом примере совсем не меняет результат работы компилятора: Clang уже оптимизировал хвостовые вызовы под -O2.

Новое здесь это гарантия. Хотя компиляторы зачастую успешно оптимизируют хвостовые вызовы, однако это лучшее из возможного, и вы не можете на это полагаться. В частности, оптимизация наверняка не сработает в неоптимизированных сборках: онлайн-компилятор. В этом примере хвостовой вызов скомпилирован в call, так что мы вернулись к стеку размером O(n). Вот почему нам нужен musttail: пока у нас нет гарантии от компилятора, что наши хвостовые вызовы будут всегда оптимизированы во всех режимах сборки, писать алгоритмы с такими вызовами для итерации будет небезопасно. А придерживаться кода, который работает только при включённых оптимизациях, будет довольно жёстким ограничением.

Проблема с циклами интерпретатора


Компиляторы это невероятная технология, но они не совершенны. Майк Пол (Mike Pall), автор LuaJIT, решил написать интерпретатор LuaJIT 2.x на ассемблере, а не C, и он назвал это главным фактором, благодаря которому интерпретатор получился таким быстрым. Позднее Пол подробнее объяснил, почему С-компиляторам трудно даются главные циклы интерпретатора. Два главных тезиса:

  • Чем больше функция и чем сложнее и обширнее набор соединений её потока управления, тем сложнее распределителю регистров в компиляторе поддерживать в регистрах самые важные данные.
  • Когда в одной функции смешаны быстрые и медленные пути, наличие медленных путей снижает качество кода быстрых путей.

Эти наблюдения хорошо отражают наш опыт оптимизации парсинга протокола сериализации. И решить обе проблемы помогут нам хвостовые вызовы.

Вам может показаться странным сравнивать циклы интерпретатора с парсерами протокола сериализации. Однако их неожиданное для вас сходство определяется природой wire-формата протокола: это набор пар ключ-значение, в которых ключ содержит номер поля и его тип. Ключ работает как код операции в интерпретаторе: он говорит нам, какую операцию нужно выполнить для парсинга этого поля. Номера полей в протоколе могут идти в любом порядке, так что нужно быть готовым в любой момент перейти к любой части кода.

Логично будет писать такой парсер с помощью цикла while с вложенным выражением switch. Это был лучший подход для парсинга протокола сериализации в течение всего времени существования протокола. Вот, например, код парсинга из текущей С++-версии. Если представить поток управления графически, то получим такую схему:


Но схема не полная, потому что почти на каждом этапе могут возникнуть проблемы. Тип поля может оказаться неправильным, или данные окажутся повреждены, или мы можем просто перейти в конец текущего буфера. Полная схема выглядит так:


Нам нужно как можно дольше оставаться на быстрых путях (голубого цвета), но столкнувшись с трудной ситуацией придётся обрабатывать её с помощью fallback-кода. Такие пути обычно длиннее и сложнее быстрых, они затрагивают больше данных и зачастую используют неудобные вызовы других функций для обработки ещё более сложных случаев.

В теории, если объединить эту схему с профилем, то компилятор получит всю необходимую информацию для генерирования наиболее оптимального кода. Но на практике при таком размере функции и количестве связей нам часто приходится бороться с компилятором. Он выкидывает важную переменную, которую мы хотим сохранить в регистре. Он применяет манипуляции с фреймом стека, которые мы хотим обернуть вокруг вызова fallback-функции. Он объединяет идентичные пути кода, которые мы хотим оставить разделёнными для прогнозирования ветвления. Всё это выглядит на попытку играть на пианино в варежках.

Улучшаем циклы интерпретатора с помощью хвостовых вызовов


Описанные выше рассуждения это по большей части перефразированные наблюдения Пола об основных циклах интерпретатора. Но вместо того, чтобы кидаться в ассемблер, мы обнаружили, что адаптированная под хвостовые вызовы архитектура может дать нам необходимое управление для получения из С почти оптимального кода. Я работал над этим со своим коллегой Гербеном Ставенгой (Gerben Stavenga), который придумал большую часть архитектуры. Наш подход аналогичен архитектуре WebAssembly-интерпретатора wasm3, в котором этот паттерн назван метамашиной.

Мы поместили код нашего двухгигабитного парсера в upb, маленькую protobuf-библиотеку на C. Он полностью рабочий и проходит все тесты соответствия протоколу сериализации, но пока нигде не развёрнут, а архитектура не реализована в С++-версии протокола. Но когда в Clang появилось расширение musttail (и upb обновили для его использования), упал один из главных барьеров на пути к полному внедрению нашего быстрого парсера.

Мы отошли от одной большой парсинговой функции и применяем для каждой операции свою собственную маленькую функцию. Каждая хвостовая функция вызывает следующую операцию в последовательности. Например, вот функция для парсинга одиночного поля фиксированного размера (код упрощён по сравнению с upb, многие мелкие подробности архитектуры я убрал).

Код 
#include <stdint.h>#include <stddef.h>#include <string.h>typedef void *upb_msg;struct upb_decstate;typedef struct upb_decstate upb_decstate;// The standard set of arguments passed to each parsing function.// Thanks to x86-64 calling conventions, these will be passed in registers.#define UPB_PARSE_PARAMS                                          \  upb_decstate *d, const char *ptr, upb_msg *msg, intptr_t table, \      uint64_t hasbits, uint64_t data#define UPB_PARSE_ARGS d, ptr, msg, table, hasbits, data#define UNLIKELY(x) __builtin_expect(x, 0)#define MUSTTAIL __attribute__((musttail))const char *fallback(UPB_PARSE_PARAMS);const char *dispatch(UPB_PARSE_PARAMS);// Code to parse a 4-byte fixed field that uses a 1-byte tag (field 1-15).const char *upb_pf32_1bt(UPB_PARSE_PARAMS) {  // Decode "data", which contains information about this field.  uint8_t hasbit_index = data >> 24;  size_t ofs = data >> 48;  if (UNLIKELY(data & 0xff)) {    // Wire type mismatch (the dispatch function xor's the expected wire type    // with the actual wire type, so data & 0xff == 0 indicates a match).    MUSTTAIL return fallback(UPB_PARSE_ARGS);  }  ptr += 1;  // Advance past tag.  // Store data to message.  hasbits |= 1ull << hasbit_index;  memcpy((char*)msg + ofs, ptr, 4);  ptr += 4;  // Advance past data.  // Call dispatch function, which will read the next tag and branch to the  // correct field parser function.  MUSTTAIL return dispatch(UPB_PARSE_ARGS);}


Для такой маленькой и простой функции Clang генерирует код, который практически невозможно превзойти:

upb_pf32_1bt:                           # @upb_pf32_1bt        mov     rax, r9        shr     rax, 24        bts     r8, rax        test    r9b, r9b        jne     .LBB0_1        mov     r10, r9        shr     r10, 48        mov     eax, dword ptr [rsi + 1]        mov     dword ptr [rdx + r10], eax        add     rsi, 5        jmp     dispatch                        # TAILCALL.LBB0_1:        jmp     fallback                        # TAILCALL

Обратите внимание, что здесь нет пролога и эпилога, нет вытеснения регистров, вообще не используется стек. Единственные выходы jmp из двух хвостовых вызовов, но для передачи параметров код не нужен, потому что аргументы уже лежат в правильных регистрах. Пожалуй, единственное возможное улучшение, которое мы здесь видим, заключается в условном переходе для хвостового вызова jne fallback вместо jne с последующим jmp.

Если бы вы увидели дизассемблирование этого кода без символьной информации, то не поняли бы, что это была вся функция. Это в равной степени мог быть быть базовый блок более крупной функции. И именно это мы делаем: берём цикл интерпретатора, который представляет собой большую и сложную функцию, и программируем его блок за блоком, передавая между ними поток управления через хвостовые вызовы. Мы полностью контролируем распределение регистров на границе каждого блока (как минимум шести регистров), и поскольку функция достаточно простая и не вытесняет регистры, мы достигли своей цели хранения самого важного состояния на протяжении всех быстрых путей.

Мы можем независимо оптимизировать каждую последовательность инструкций. И компилятор будет обрабатывать все последовательности тоже независимо, потому что они расположены в отдельных функциях (при необходимости можно предотвращать инлайнинг с помощью noinline). Так мы решаем описанную выше проблему, при которой код из fallback-путей ухудшает качество кода быстрых путей. Если поместить медленные пути в полностью отдельные функции, то можно гарантировать стабильность скорости быстрых путей. Красивый ассемблер остаётся неизменным, на него не влияют никакие изменения в других частях парсера.

Если применить этот паттерн к примеру Пола из LuaJIT, то можно примерно сопоставить его написанный вручную ассемблер с небольшими ухудшениями качества кода:

#define PARAMS unsigned RA, void *table, unsigned inst, \               int *op_p, double *consts, double *regs#define ARGS RA, table, inst, op_p, consts, regstypedef void (*op_func)(PARAMS);void fallback(PARAMS);#define UNLIKELY(x) __builtin_expect(x, 0)#define MUSTTAIL __attribute__((musttail))void ADDVN(PARAMS) {    op_func *op_table = table;    unsigned RC = inst & 0xff;    unsigned RB = (inst >> 8) & 0xff;    unsigned type;    memcpy(&type, (char*)&regs[RB] + 4, 4);    if (UNLIKELY(type > -13)) {        return fallback(ARGS);    }    regs[RA] += consts[RC];    inst = *op_p++;    unsigned op = inst & 0xff;    RA = (inst >> 8) & 0xff;    inst >>= 16;    MUSTTAIL return op_table[op](ARGS);}

Получившийся ассемблер:

ADDVN:                                  # @ADDVN        movzx   eax, dh        cmp     dword ptr [r9 + 8*rax + 4], -12        jae     .LBB0_1        movzx   eax, dl        movsd   xmm0, qword ptr [r8 + 8*rax]    # xmm0 = mem[0],zero        mov     eax, edi        addsd   xmm0, qword ptr [r9 + 8*rax]        movsd   qword ptr [r9 + 8*rax], xmm0        mov     edx, dword ptr [rcx]        add     rcx, 4        movzx   eax, dl        movzx   edi, dh        shr     edx, 16        mov     rax, qword ptr [rsi + 8*rax]        jmp     rax                             # TAILCALL.LBB0_1:        jmp     fallback

Я вижу здесь лишь одну возможность улучшения не считая вышеупомянутой jne fallback: по какой-то причине компилятор не хочет генерировать jmp qword ptr [rsi + 8*rax], вместо этого он загружает в rax и затем выполняет jmp rax. Это небольшие проблемы генерирования кода, которые, надеюсь, в Clang скоро исправят без излишних затруднений.

Ограничения


Один из главных недостатков этого подхода заключается в том, что все эти прекрасные последовательности на ассемблере катастрофически пессимизируются при отсутствии хвостовых вызовов. Любой нехвостовой вызов приводит к созданию фрейма стека и вытеснению в стек многих данных.

#define PARAMS unsigned RA, void *table, unsigned inst, \               int *op_p, double *consts, double *regs#define ARGS RA, table, inst, op_p, consts, regstypedef void (*op_func)(PARAMS);void fallback(PARAMS);#define UNLIKELY(x) __builtin_expect(x, 0)#define MUSTTAIL __attribute__((musttail))void ADDVN(PARAMS) {    op_func *op_table = table;    unsigned RC = inst & 0xff;    unsigned RB = (inst >> 8) & 0xff;    unsigned type;    memcpy(&type, (char*)&regs[RB] + 4, 4);    if (UNLIKELY(type > -13)) {        // When we leave off "return", things get real bad.        fallback(ARGS);    }    regs[RA] += consts[RC];    inst = *op_p++;    unsigned op = inst & 0xff;    RA = (inst >> 8) & 0xff;    inst >>= 16;    MUSTTAIL return op_table[op](ARGS);}

Неожиданно получаем вот это 
ADDVN:                                  # @ADDVN        push    rbp        push    r15        push    r14        push    r13        push    r12        push    rbx        push    rax        mov     r15, r9        mov     r14, r8        mov     rbx, rcx        mov     r12, rsi        mov     ebp, edi        movzx   eax, dh        cmp     dword ptr [r9 + 8*rax + 4], -12        jae     .LBB0_1.LBB0_2:        movzx   eax, dl        movsd   xmm0, qword ptr [r14 + 8*rax]   # xmm0 = mem[0],zero        mov     eax, ebp        addsd   xmm0, qword ptr [r15 + 8*rax]        movsd   qword ptr [r15 + 8*rax], xmm0        mov     edx, dword ptr [rbx]        add     rbx, 4        movzx   eax, dl        movzx   edi, dh        shr     edx, 16        mov     rax, qword ptr [r12 + 8*rax]        mov     rsi, r12        mov     rcx, rbx        mov     r8, r14        mov     r9, r15        add     rsp, 8        pop     rbx        pop     r12        pop     r13        pop     r14        pop     r15        pop     rbp        jmp     rax                             # TAILCALL.LBB0_1:        mov     edi, ebp        mov     rsi, r12        mov     r13d, edx        mov     rcx, rbx        mov     r8, r14        mov     r9, r15        call    fallback        mov     edx, r13d        jmp     .LBB0_2


Чтобы избежать подобного, мы пытались вызывать другие функции только через инлайнинг или хвостовые вызовы. Это может утомлять, если у операции много мест, в которых может возникнуть необычная ситуация, не являющаяся ошибкой. Например, когда мы парсим протокол сериализации целочисленные переменные часто бывают длиной один байт, но более длинные не являются ошибкой. Инлайнинг обработки таких ситуаций может ухудшить качество быстрого пути, если fallback-код окажется слишком сложным. Но хвостовой вызов fallback-функции не позволяет легко вернуться к операции при обработке нестандартной ситуации, так что fallback-функция должна уметь завершать операцию. Это приводит к дублированию и усложнению кода.

В идеале это проблему можно решить с помощью добавления __attribute__((preserve_most)) в fallback-функции с последующим нормальным вызовом, а не хвостовым. Атрибут preserve_most возлагает на вызываемого ответственность за сохранение почти всех регистров. Это позволяет перекладывать задачу вытеснения регистров на fallback-функции, если такое понадобится. Мы экспериментировали с этим атрибутом, но столкнулись с таинственными проблемами, решить которые не смогли. Возможно, мы где-то допустили ошибку, вернёмся к этому в будущем.

Главное ограничение заключается в том, что musttail не является портируемым. Очень надеюсь, что атрибут приживётся, его внедрят в GCC, Visual C++ и других компиляторах, а однажды даже стандартизируют. Но это случится не скоро, а что нам делать сейчас?

Когда расширение musttail недоступно, нужно для каждой теоретической итерации цикла выполнить хотя бы один верный return без хвостового вызова. Мы ещё не реализовали такой fallback в библиотеке upb, но думаю, что она превратится в макрос, который в зависимости от доступности musttail будет либо делать хвостовые вызовы, либо просто возвращать.
Подробнее..
Категории: Программирование , C , Высокая производительность , Блог компании mail.ru group , Никто не читает теги , Рекурсия , Хвостовая рекурсия

SQL HowTo обрабатываем дерево упорядочиваем иерархию с рекурсией и без

19.10.2020 20:09:27 | Автор: admin
Видимо, это осень так влияет, что за последний месяц на PostgreSQL уже и в Морской бой играли, и Жизнь Конвея эмулировали Что уж оставаться в стороне! Давайте и мы потренируем мозг в реализации нетривиальных алгоритмов на SQL.

Тем более, сегодняшняя тема родилась из обсуждения моей же статьи PostgreSQL Antipatterns: Бесконечность не предел!, или Немного о рекурсии, где я показал, как можно заменить рекурсивное чтение иерархичных данных из таблицы на линейное.

Прочитать-то мы прочитали, но ведь чтобы для вывода упорядочить элементы дерева в соответствии с иерархией, уж точно придется воспользоваться рекурсией! Или нет? Давайте разберемся, а заодно решим на SQL пару комбинаторных задач.


Давайте возьмем в качестве примера прочитанный из базы набор записей чего-то вроде справочника сотрудников. Они образуют ориентированное дерево из отделов и работающих в них сотрудников, которое выглядит примерно вот так:



Точнее, это нам хочется, чтобы оно выглядело именно так дочерний узел под родительским, правильная сортировка детей внутри одного предка, красивые отступы Но база-то нам отдаст записи отсортированными в том порядке, который удобнее ей скорее всего, по первичному ключу id:


Давайте все-таки сначала формально определим те правила, которым должен отвечать искомый порядок записей:

  • элемент-предок стоит раньше любого из элементов его поддерева
  • дочерние элементы внутри одного родительского упорядочиваются по дополнительному прикладному ключу

Второе требование отражает привычные для пользователя паттерны, когда папки внутри одного каталога отображаются отсортированными по названию, а ответы на сообщение в ветке форума по времени.

Мы, для простоты, возьмем в нашем примере в качестве такого ключа data.

Таков путь!


Собственно, а что мы такое можем сконструировать, чтобы сортировка этого чего-то давала нам желаемый результат?

Давайте для каждого элемента дерева вычислим путь цепочку из прикладных ключей всех элементов, которые надо пройти от корня, чтобы его достигнуть:



Но если на каждом шаге такого пути мы сортируем элементы согласно прикладному ключу, то и массивы, составленные из этих ключей, будучи отсортированными, дадут нам искомый порядок записей!

Рекурсивная сортировка


Сначала воспользуемся наиболее традиционным и очевидным способом получения нужного нам результата рекурсивным запросом:

WITH RECURSIVE src(id, pid, data) AS (  VALUES    (1, NULL, 'A')  , (2, 1, 'AA')  , (3, 2, 'AAA')  , (4, 1, 'AB')  , (5, 2, 'AAB')  , (6, 3, 'AAAA')  , (7, 5, 'AABA')  , (8, 4, 'ABA')  , (9, 7, 'AABAA')  , (10, 2, 'AAC')), T AS (  SELECT    id  , ARRAY[data] path -- инициализируем массив пути корневым элементом  FROM    src  WHERE    pid IS NULLUNION ALL  SELECT    s.id  , T.path || s.data -- наращиваем путь  FROM    T  JOIN    src s      ON s.pid = T.id)SELECT  *FROM  srcNATURAL JOIN  TORDER BY  path; -- сортируем согласно пути


 id | pid | data  |         path----+-----+-------+-----------------------  1 |     | A     | {A}  2 |   1 | AA    | {A,AA}  3 |   2 | AAA   | {A,AA,AAA}  6 |   3 | AAAA  | {A,AA,AAA,AAAA}  5 |   2 | AAB   | {A,AA,AAB}  7 |   5 | AABA  | {A,AA,AAB,AABA}  9 |   7 | AABAA | {A,AA,AAB,AABA,AABAA} 10 |   2 | AAC   | {A,AA,AAC}  4 |   1 | AB    | {A,AB}  8 |   4 | ABA   | {A,AB,ABA}

Подключаем комбинаторику


А теперь вернемся к началу статьи и подумаем, как же все-таки для той же самой задачи мы можем создать нерекурсивное решение. В этом нам поможет
Комбинаторика (комбинаторный анализ) раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка).
Сначала решим несколько небольших типовых задач из этой области.

Комбинации


Пусть у нас есть исходный массив {A,B,C}, все элементы которого уникальны. Получим все комбинации массивов той же длины, состоящие из его элементов:

{A,A,A}{A,A,B}{A,A,C}{A,B,A}{A,B,B}...{C,C,B}{C,C,C}

Достаточно очевидно, что при длине массива N таких вариантов будет ровно N^N, но как получить их на SQL?

Обратим внимание, что каждой комбинации элементов соответствует комбинация позиций этих элементов в исходном массиве, если пронумеровать их с нуля. А каждой такой комбинации число в N-ричной системе счисления:

3^2 |  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  1  2  2  2  2  2  2  2  2  23^1 |  0  0  0  1  1  1  2  2  2  0  0  0  1  1  1  2  2  2  0  0  0  1  1  1  2  2  23^0 |  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2=== |  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Решение становится достаточно очевидным:

  • генерируем каждое число в диапазоне 0 .. N^N - 1
  • раскладываем в N-ричную систему счисления
  • берем элемент на соответствующей позиции разложения

SELECT  dstFROM  -- исходный набор элементов  (VALUES('{A,B,C}'::varchar[])) data(src)  -- кэшируем размер набора, LATERAL array_length(src, 1) n  -- кэшируем границу интервала, LATERAL (SELECT (n ^ n)::bigint l) X  -- генерируем все числа на интервале, LATERAL generate_series(0, l - 1) num  -- формируем разложение числа в N-ричной системе, LATERAL (    SELECT      array_agg((num % (n ^ (pos + 1))::bigint) / (n ^ pos)::bigint ORDER BY pos DESC) num_n    FROM      generate_series(0, n - 1) pos  ) Y  -- собираем элементы согласно "цифрам", LATERAL (    SELECT      array_agg(src[num_n[pos] + 1]) dst    FROM      generate_subscripts(num_n, 1) pos  ) Z;

Перестановки


Но в оригинальном наборе у нас каждый элемент был уникален, а в полученных нами комбинациях это правило не соблюдается. Исправим, получив все возможные перестановки. Для этого отфильтруем из num_n только те, где встречаются все цифры:

JOIN LATERAL(  SELECT    count(DISTINCT unnest) = n cond  FROM    unnest(num_n)) flt  ON cond

Полный вариант запроса 
SELECT  dstFROM  -- исходный набор элементов  (VALUES('{A,B,C}'::varchar[])) data(src)  -- кэшируем размер набора, LATERAL array_length(src, 1) n  -- кэшируем границу интервала, LATERAL (SELECT (n ^ n)::bigint l) X  -- генерируем все числа на интервале, LATERAL generate_series(0, l - 1) num  -- формируем разложение числа в N-ричной системе, LATERAL (    SELECT      array_agg((num % (n ^ (pos + 1))::bigint) / (n ^ pos)::bigint ORDER BY pos DESC) num_n    FROM      generate_series(0, n - 1) pos  ) Y  -- фильтруем комбинации с неполным набором "цифр"JOIN LATERAL(    SELECT      count(DISTINCT unnest) = n cond    FROM      unnest(num_n)  ) flt    ON cond  -- собираем элементы согласно "цифрам", LATERAL (    SELECT      array_agg(src[num_n[pos] + 1]) dst    FROM      generate_subscripts(num_n, 1) pos  ) Z;

Это дает нам все возможные перестановки исходного набора:

{A,B,C}{A,C,B}{B,A,C}{B,C,A}{C,A,B}{C,B,A}

Можно использовать и неэкспоненциальный алгоритм на основе тасований, работающий за O(N*N!), но его реализация явно выходит за рамки данной статьи.

Подмножества


Сделаем шаг чуть в сторону и научимся генерировать все подмножества исходного набора с сохранением порядка. То есть для нашего набора {A,B,C} должно получиться вот это:

{}{A}{B}{A,B}{C}{A,C}{B,C}{A,B,C}

В принципе, задача очень близка к первой решенной нами. Только вместо позиции двоичная цифра означает отсутствие или наличие соответствующего элемента в результирующем наборе:

2^2 |  0  0  0  0  1  1  1  12^1 |  0  0  1  1  0  0  1  12^0 |  0  1  0  1  0  1  0  1=== |  0  1  2  3  4  5  6  7

Поскольку двоичная арифметика представлена в компьютерах гораздо эффективнее, мы можем воспользоваться функциями работы с битовыми строками:

  -- кэшируем разложение числа в двоичной системе, LATERAL (SELECT num::bit(64) num_n) Y  -- собираем элементы согласно "цифрам", LATERAL (    SELECT      coalesce(array_agg(src[i]) FILTER(WHERE get_bit(num_n, 64 - i) = 1), '{}') dst    FROM      generate_series(1, n) i  ) Z

Полный вариант запроса 
SELECT  dstFROM  -- исходный набор элементов  (VALUES('{A,B,C}'::varchar[])) data(src)  -- кэшируем размер набора, LATERAL array_length(src, 1) n  -- кэшируем границу интервала, LATERAL (SELECT (2 ^ n)::bigint l) X  -- генерируем все числа на интервале, LATERAL generate_series(0, l - 1) num  -- кэшируем разложение числа в двоичной системе, LATERAL (SELECT num::bit(64) num_n) Y  -- собираем элементы согласно "цифрам", LATERAL (    SELECT      coalesce(array_agg(src[i]) FILTER(WHERE get_bit(num_n, 64 - i) = 1), '{}') dst    FROM      generate_series(1, n) i  ) Z;

Иерархия без рекурсии!


Теперь, вооруженные всеми приведенными выше алгоритмами, попробуем найти решение нашей задачи сначала в общем виде, а затем разберем один из типичных частных случаев.

Пути-дороги


Для начала воспользуемся тем фактом, что в качестве элементов пути, который идентифицирует конкретную запись, можно использовать уникальные ключи промежуточных записей в нашем случае это id.

Но сортировать по такому пути, конечно, будет некорректно поэтому для дальнейшей сортировки превратим id записей в соответствующее значение data, которое использовали в первом варианте.
Дано: газовая плита, чайник. Задача: вскипятить воду.
Физик: Зажечь плиту, наполнить чайник водой и поставить на плиту, ждать.
Математик: Аналогично.

Дано: зажженная газовая плита, наполненный водой чайник. Задача: вскипятить воду.
Физик: Поставить чайник на плиту, ждать.
Математик: Выливаем воду из чайника на плиту. Огонь погас, чайник пуст, задача сведена к предыдущей.
Народный анекдот
Но как найти путь до каждого из элементов без рекурсии? Вот здесь нам и пригодятся алгоритмы выше.

Корректный путь от корня до конкретного элемента обладает следующими свойствами:

  • Правило #1: начинается и заканчивается нужными нам элементами
    path[1] = root AND path[array_length(path, 1)] = id
  • Правило #2: предок каждого элемента, кроме корневого, так же присутствует в наборе
    pid = ANY(path) OR pid = root
  • Правило #3: из всех таких наборов искомый самой маленькой длины
    Иначе для id=3 наборы {1,2,3} и {1,2,3,4} окажутся равноподходящими, поскольку предок id=4 (pid=1) тоже присутствует.
  • Правило #4: предок каждого элемента стоит ровно в предыдущей позиции
    pid = path[pos - 1]

Итак, намечаем план действий:

  • генерируем все подмножества элементов, исключая root и id, формируя тело пути по правилу #1
  • проверяем выполнение правила #2
  • выбираем, согласно правилу #3, самый короткий набор
  • генерируем все перестановки его элементов
  • проверяем выполнение правила #4
  • что осталось искомый путь

Полный вариант запроса, смотреть с осторожностью
Я вас предупредил [источник картинки]

WITH src(id, pid, data) AS (  VALUES    (1, NULL, 'A')  , (2, 1, 'AA')  , (3, 2, 'AAA')  , (4, 1, 'AB')  , (5, 2, 'AAB')  , (6, 3, 'AAAA')  , (7, 5, 'AABA')  , (8, 4, 'ABA')  , (9, 7, 'AABAA')  , (10, 2, 'AAC'))-- кэшируем ID корневого элемента, root AS (  SELECT    id  FROM    src  WHERE    pid IS NULL  LIMIT 1)-- формируем уже известные пути и предварительные наборы, preset AS (  SELECT    *  , CASE      -- для корневого элемента путь состоит только из него самого      WHEN pid IS NULL THEN ARRAY[id]      -- для ссылающегося на корневой - из пары      WHEN pid = (TABLE root) THEN ARRAY[pid, id]    END prepath  , CASE      WHEN pid IS NULL THEN NULL      WHEN pid = (TABLE root) THEN NULL      -- все ID, кроме корневого и собственного - EXCLUDE CURRENT ROW      ELSE array_agg(id) FILTER(WHERE pid IS NOT NULL) OVER(ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING EXCLUDE CURRENT ROW)    END preset  FROM    src)-- формируем "переборные" пути, prepath AS (  SELECT    id  , prepath  FROM    -- отбираем только элементы, чей путь еще не определили    (      SELECT        id      , pid      , preset src -- комбинируемый набор      FROM        preset      WHERE        prepath IS NULL    ) data    -- подмножества  , LATERAL (      SELECT        dst pathset      FROM        -- кэшируем размер набора        LATERAL array_length(src, 1) n        -- кэшируем границу интервала      , LATERAL (SELECT (2 ^ n)::bigint l) X        -- генерируем все числа на интервале      , LATERAL generate_series(1, l - 1) num -- тут можно с 1, поскольку пустой набор нас заведомо не интересует        -- кэшируем разложение числа в двоичной системе      , LATERAL (SELECT num::bit(64) num_n) Y        -- собираем элементы согласно "цифрам"      , LATERAL (          SELECT            coalesce(array_agg(src[i]) FILTER(WHERE get_bit(num_n, 64 - i) = 1), '{}') || data.id dst          FROM            generate_series(1, n) i        ) Z        -- проверяем наличие предка в наборе      , LATERAL (          SELECT            NULL          FROM            (              SELECT                (SELECT pid FROM src WHERE id = dst[i] LIMIT 1) _pid              FROM                generate_subscripts(dst, 1) i            ) T          HAVING            bool_and(_pid = (TABLE root) OR _pid = ANY(dst))        ) rule2      -- отбираем первый подходящий минимальной длины      ORDER BY        array_length(dst, 1) -- rule3      LIMIT 1    ) X    -- перестановки  , LATERAL (      SELECT        dst prepath      FROM        -- исходный набор элементов        (SELECT pathset) data(src)        -- кэшируем размер набора      , LATERAL array_length(src, 1) n        -- кэшируем границу интервала      , LATERAL (SELECT (n ^ n)::bigint l) X        -- генерируем все числа на интервале      , LATERAL generate_series(0, l - 1) num        -- формируем разложение числа в N-ричной системе      , LATERAL (          SELECT            array_agg((num % (n ^ (pos + 1))::bigint) / (n ^ pos)::bigint ORDER BY pos DESC) num_n          FROM            generate_series(0, n - 1) pos        ) Y        -- фильтруем комбинации с неполным набором "цифр"      JOIN LATERAL(          SELECT            count(DISTINCT unnest) = n cond          FROM            unnest(num_n)        ) flt          ON cond        -- собираем элементы согласно "цифрам"      , LATERAL (          SELECT            array_agg(src[num_n[pos] + 1]) dst          FROM            generate_subscripts(num_n, 1) pos        ) Z        -- проверяем наличие предка в предыдущей позиции      , LATERAL (          SELECT            NULL          FROM            (              SELECT                (SELECT pid FROM src WHERE id = dst[i] LIMIT 1) _pid              , i              FROM                generate_subscripts(dst, 1) i            ) T          HAVING            bool_and((i = 1 AND _pid = (TABLE root)) OR _pid = dst[i - 1])        ) rule4    ) Y)SELECT  src.*  -- восстанавливаем "путь" из прикладных ключей, (    SELECT      array_agg(data ORDER BY i)    FROM      coalesce(X.prepath, ARRAY[(TABLE root)] || Y.prepath) p -- помним о необходимости добавить "корень"    , LATERAL generate_subscripts(p, 1) i    , LATERAL (        SELECT          data        FROM          src        WHERE          id = p[i]        LIMIT 1      ) T  ) pathFROM  srcLEFT JOIN  preset X    USING(id)LEFT JOIN  prepath Y    USING(id)ORDER BY  path;

А попроще можно?..


Можно и попроще, если заранее известно, что порядок детей внутри одного родителя определяется некоторым сквозным ключом. Например, это может быть некоторый монотонно возрастающий timestamp сообщений в ветке форума или, как в нашем случае, первичный ключ типа serial (id).

В таком случае, мы уже точно знаем порядок следования идентификаторов записей в нужном нам пути он совпадает с общей сортировкой по этому ключу. И нам надо только выкинуть лишние id из списка всех предстоящих:

WITH src(id, pid, data) AS (  VALUES    (1, NULL, 'A')  , (2, 1, 'AA')  , (3, 2, 'AAA')  , (4, 1, 'AB')  , (5, 2, 'AAB')  , (6, 3, 'AAAA')  , (7, 5, 'AABA')  , (8, 4, 'ABA')  , (9, 7, 'AABAA')  , (10, 2, 'AAC'))-- кэшируем ID корневого элемента, root AS (  SELECT    id  FROM    src  WHERE    pid IS NULL  LIMIT 1)-- собираем все предстоящие id в массив для текущего, prepath AS (  SELECT    id  , pid  , array_agg(id) OVER(ORDER BY id /*!!! сортировка по тому самому ключу*/ ROWS UNBOUNDED PRECEDING EXCLUDE CURRENT ROW) src  FROM    src  WHERE    pid IS NOT NULL)-- находим пути, pre AS (  SELECT    id  , path  FROM    prepath    -- подмножества  , LATERAL (      SELECT        dst path      FROM        -- кэшируем размер набора        LATERAL array_length(src, 1) n        -- кэшируем границу интервала      , LATERAL (SELECT (2 ^ n)::bigint l) X        -- генерируем все числа на интервале      , LATERAL generate_series(0, l - 1) num        -- кэшируем разложение числа в двоичной системе      , LATERAL (SELECT num::bit(64) num_n) Y        -- собираем элементы согласно "цифрам"      , LATERAL (          SELECT            coalesce(array_agg(src[i]) FILTER(WHERE get_bit(num_n, 64 - i) = 1), '{}') || id dst          FROM            generate_series(1, n) i        ) Z        -- проверяем наличие предка в предыдущей позиции      , LATERAL (          SELECT            NULL          FROM            (              SELECT                (SELECT pid FROM src WHERE id = dst[i] LIMIT 1) _pid              , i              FROM                generate_subscripts(dst, 1) i            ) T          HAVING            bool_and((i = 1 AND _pid = (TABLE root)) OR (i > 1 AND _pid = dst[i - 1]))        ) rule4    ) X)SELECT  src.*  -- восстанавливаем "путь" из прикладных ключей, (    SELECT      array_agg(data ORDER BY i)    FROM      (        SELECT          CASE            -- для корневого элемента путь состоит только из него самого            WHEN pid IS NULL THEN ARRAY[id]            -- для ссылающегося на корневой - из пары            WHEN pid = (TABLE root) THEN ARRAY[pid, id]            ELSE ARRAY[(TABLE root)] || pre.path          END p -- помним о необходимости добавить "корень"      ) p    , LATERAL generate_subscripts(p, 1) i    , LATERAL (        SELECT          data        FROM          src        WHERE          id = p[i]        LIMIT 1      ) T  ) pathFROM  srcLEFT JOIN  pre    USING(id)ORDER BY  path;

Понятно, что производительность таких экспоненциальных решений не особо велика и применять в бою надо с большой осторожностью, но как гимнастика для ума вполне.
Подробнее..
Категории: Ненормальное программирование , Алгоритмы , Postgresql , Sql , Блог компании тензор , Sql tips and tricks , Рекурсия , Lateral , Комбинаторика , Перестановки , Подмножества , Битовые строки

Все есть бит

04.09.2020 20:08:16 | Автор: admin
Бог это вечная и бесконечная истина, не имеющая ценности и смысла.
Барух Бенедикт Спиноза

Сегодня я хочу рассказать вам о самой смелой и красивой гипотезе в современной теоретической физике. Многие ученые относятся к ней крайне скептически, некоторые называют ее откровенно шизофреническим бредом, а другие находят крайне интересной. Давайте же пустимся в путешествие, которое может навсегда изменить ваше представление о Вселенной.



В поисках теории всего


Начиная с середины 20-ого века самой сложной и перспективной задачей теоретической физики является поиск так называемой теории всего, которая объединит в себе общую теорию относительности и квантовую механику, тем самым дав точное объяснение всем наблюдаемым физическим явлениям. На роль такой теории претендуют многочисленные теории струн, теория квантовой петлевой гравитации и многие другие. Но мы будем говорить не о них. Мы сделаем шаг еще дальше.

Профессор MIT Макс Тегмарк в своей книге Наша математическая Вселенная призывает нас задуматься о самом удивительном свойстве всех существующих физических теорий, которое обычно люди считают само собой разумеющимся все наши физические теории описываются математикой.

С точки зрения эмпиризма (философия первичности материи по отношению к идее) в этом нет ничего удивительного, человек изобретал язык математики, наблюдая за реальным миром.Мы изобрели цифры и счет, чтобы считать предметы, мы изобрели геометрию, чтобы строить прочные здания. Со временем наши математические инструменты становились все более сложными и отдаленными от повседневных нужд мы изобретали дифференциалы, интегралы, математический анализ, теорию групп, топологию. Но в конце концов мы всегда находили физические явления, которые поразительно хорошо описывались с помощью этих самых инструментов.

Но давайте взглянем на математичность физических законов с точки зрения идеализма (философия первичности идеи по отношению к материи). Все математические законы живут в пространстве идей и не зависят даже от существования нашей Вселенной. Если даже ничего не существовало бы, дважды два все также равнялось бы четырем. Рождение галактик и звезд, движение планет, химические реакции и генетические мутации строго следовали математическим формулам задолго до появления людей. Мы лишь открыли эти законы, но не изобрели их.

Так что же будет с теорией относительности, квантовой механикой или пресловутой теорией всего, если мы выкинем из них всю словесную шелуху, вроде слов квант, пространство, свет. Там останутся только формулы, и ничего больше. И в этом месте рассуждений Макс Тегмарк задает интереснейший вопрос: что может полностью описываться чистой математикой? И он дает на него единственно разумный ответ. Чистой математикой может быть описана лишь сама чистая математика. Таким образом Тегмарк приходит к самой поразительной из возможных гипотез: вся наша Вселенная это математическая структура.

Все из бита


Макс Тегмарк не был первым, кто пришел к такой идее. Задолго до него эту идею выдвигал знаменитый американский физик, научный руководитель Ричарда Фейнмана, Хью Эверетта и Кипа Торна, а также автор терминов черная дыра и кротовая нора Джон Уилер.

В своей статье it from bit Джон Уилер задумывался над тем фактом, что все свойства элементарных частиц вроде массы, заряда, спина, цвета, странности и красоты не имеют никакого собственного смысла, а лишь проявляются при взаимодействиях с другими частицами. Таким образом, все эти свойства являются по сути битом информации в некоторой математической структуре. Уилер писал:
Все сущее каждая частица, каждое силовое поле, даже сам пространственно-временной континуум получают свою функцию, свой смысл и, в конечном счёте, самое своё существование даже если в каких-то ситуациях не напрямую из ответов, извлекаемых нами с помощью физических приборов, на вопросы, предполагающие ответ да или нет, из бинарных альтернатив, из битов. Всё из бита символизирует идею, что всякий предмет и событие физического мира имеет в своей основе в большинстве случаев в весьма глубокой основе нематериальный источник и объяснение; то, что мы называем реальностью, вырастает в конечном счёте из постановки да-нет-вопросов и регистрации ответов на них при помощи аппаратуры

Чтобы вы лучше поняли, что имел в виду Джон Уилер, я приведу вам в пример картинку из книги Макса Тегмарка о том, как отношения между точками пространства (ребра куба) можно представить в виде матрицы битов:



Сами вершины этого куба, обозначенные индексом от 1 до 8, не несут никакого смысла, а вот матрица отношений между ними (ребер куба) уже обладает некоторыми уникальными свойствами: например, вращательной симметрией. Наша Вселенная, конечно же, устроена на порядки сложнее куба, но в ее основе лежат те же самые принципы. Поняв это, мы можем двигаться дальше.

Инфляционная модель Вселенной и фракталы


Если мы все-таки живем в математической модели, то в какой?

Давайте посмотрим на нашу Вселенную: она состоит из множества скоплений миллиардов галактик, галактики состоят из миллиардов звезд, у многих звезд есть несколько планет, а у многих планет есть некоторое количество спутников. Более того, согласно гипотезе вечной инфляции, являющейся объяснением и расширением инфляционной модели развития вселенной, в отдаленном от нас пространстве ежесекундно происходят миллионы больших взрывов, порождающих свои пузыри Вселенных.

Но вернемся к нашему миру: все скопления, галактики, звезды и планеты, в какой бы части Вселенной они не находились, очень похожи между собой, но все же уникальны. Какая математическая структура обладает такими свойствами? Это фрактал.



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

Асимметрия времени и вычисление рекурсивной функции


И как раз фрактальная структура нашей Вселенной открывает нам глаза на самую главную загадку современной физики время. Идет ли время только вперед? Линейно ли оно?

Современная физика говорит о существовании так называемой асимметрий времени или стрел времени. Первая стрела времени психологическая: мы помним прошлое, но не будущее. Эта ассиметрия является частным случаем более общей второй стрелы времени причинно-следственной. Причины порождают следствия, но не наоборот. С другой стороны это может быть лишь частью нашего восприятия и при обратном ходе времени мы бы приняли причины за следствия, а следствия за причины. Но существуют третья абсолютно объективная асимметрия времени, также называемая вторым законом термодинамики энтропия в замкнутой системе со временем всегда растет. То есть, при обратном ходе времени она бы падала.

Как это можно объяснить? Одним из первых объяснение, согласующееся с гипотезой математической Вселенной, дал немецкий пионер компьютеростроения и автор первого языка программирования высокого уровня Конрад Цузе. Он предположил, что наша Вселенная является не статичной математической моделью, а постоянно вычисляющийся чистой рекурсивной функцией. На вход такой функции поступает результат вычисления предыдущей итерации. Каждый тик такой функции является планковским временем, а проще говоря мгновением. Такая гипотеза очень хорошо объясняет все стрелы времени. Результат вычисления такой функции зависит от ее входа будущее зависит от прошлого, но не наоборот. Со временем количество информации в такой системе будет расти, а значит будет расти и энтропия. И главное, эта гипотеза очень хорошо согласуется с фрактальностью нашей Вселенной, ведь фрактал результат вычисления рекуррентной функции.

Таким образом, мы можем дать определение времени таким образом: время это процесс вычисления чистой рекурсивной функции расчета развития нашей Вселенной.

Вы можете возразить, что наша Вселенная недетерминирована и при коллапсе волновой функции Шредингера результат выхода кванта из суперпозиции непредсказуем. Но согласно многомировой интерпретации квантовой механики Эверетта в момент коллапса волновой функции наша Вселенная просто разделяется на две параллельных реальности, в одной из которых суперпозиция переходит в одно состояние, а в другой в противоположное.

Также стоит учесть, что это время не то же самое, что описывается в общей теории относительности Эйнштейна. Это абсолютное время тики процессора вычисляющего нашу Вселенную.

Матрица и антропный принцип


Но если вся наша Вселенная это вычислительная машина, то как определить, что мы живем не в Матрице? С одной стороны это недоказуемо и неопровергаемо. С другой стороны, если мы живем в Матрице и крутимся на компе у какого-то программиста из реальной вселенной, то его вселенная тоже будет подчинятся законам математики и тоже может оказаться Матрицей второго уровня, которая существует в реальном мире. Этот ряд можно продолжать до бесконечности и ни в одном уровне Матрицы не будет возможности доказать, существует или нет реальный мир более высокого уровня.

В любом случае, у Макса Тегмарка есть более красивое объяснение математичности нашей Вселенной. Для начала зададимся вопросом: почему мы живем именно в такой математической структуре, а не в какой-то другой? Тегмарк находит ответ на этот вопрос в антропном принципе: все непротиворечивые математические структуры существуют, но лишь в немногих из них может зародится такая тонко настроенная Вселенная, которая позволяет существовать нейронным сетям, способным осознать причинно-следственные связи.

Заключение



У гипотезы математической вычислимой Вселенной существуют интересные последствия: герои книг, фильмов, историй и даже ваш выдуманный друг столь же реальны, как и вы сами, так как точно так же являются математическими структурами, придуманными другой математической структурой внутри громадной математической структуры. Это заставляет задуматься над самим значением слова реальность.

Для более глубокого ознакомления с данной темой я рекомендую книгу Макса Тегмарка "Наша математическая Вселенная" и статью в википедии про цифровую физику.
Подробнее..
Категории: Научно-популярное , Физика , Математика , Рекурсия , Вселенная , Квантовая физика , Время , Панкомпьютенционализм , Цифровая физика

Как Пифагор, Платон и Будда предвосхитили самую смелую гипотезу современной науки

21.05.2021 02:08:49 | Автор: admin
Рафаэль Санти - фреска "Афинская школа"Рафаэль Санти - фреска "Афинская школа"

Меня всегда поражало, что основы всей нашей цивилизации были заложены людьми, жившими две с половиной тысячи лет назад и не имевшими почти никаких способов получения знаний о мире кроме собственного разума - только лишь с помощью него одного они по капле воды смогли догадаться о существовании океана.

В этом посте я хочу рассказать про трех великих философов античности, чьи идеи о природе сущего находят подтверждение в теориях квантовой механики и самых смелых гипотезах современной теоретической физики.

Как появился Пегас?

Величайшим из древнегреческих философов по праву считается ученик Сократа афинянин Платон. Именно благодаря его "Диалогам" до нас дошла большая часть сведений о греческой философской мысли.

Несмотря на то, что Платон изучал и даже преподавал математику, никаких особенных математических достижений он после себя не оставил. Но все же девизом основанной им Академии он избрал фразу "Не геометр да не войдет", тем самым подчеркнув важность математики для познания мира и формирования ума.

Основной идеей философии Платона была, извините за каламбур, сама "идея". Именно он ввел в оборот это слово, которое на древнегреческом звучало как "эйдос". Для объяснения своей теории Платон обычно использовал аллегорию, позже ставшую известной как миф о пещере. Я вкратце приведу здесь только самую ее суть.

Представьте себе абсолютно пустую белую комнату. В этой комнате нет дверей, на одной из стен почти под потолком располагается единственное окно. Под этим окном стоит кресло, к которому железными цепями крепко-накрепко привязан человек. Его голова и тело зафиксированы таким образом, что единственное, что он видит - противоположную от окна стену. Этот человек в раннем детстве был похищен учеными, подключен к системам жизнеобеспечения и привязан цепями к своему креслу, он вырос в этой комнате и никогда не видел мира за ее пределами. Время от времени ученые проносят за окном какие-то предметы: статуи, животных, растений, зданий. Узник не видит самих предметов, а видит лишь только тени, отбрасываемые ими на противоположную от окна стену комнаты. Он различает в этих тенях схожие паттерны и дает им названия. Узник искренне считает, что те тени на стене, что он видит и которым дает имена - реальны.

По мнению Платона, люди, подобно гипотетическому узнику, заблуждаются, будто с помощью зрения, слуха, обоняния, осязания и вкуса познают реальность. Он утверждает, что, на самом деле, все, что мы получаем от органов чувств - это всего-лишь навсего блеклые тени единственно реальных вещей - "идей". Это утверждение стало краеугольным камнем всей философии идеализма.

Под "идеей" Платон понимал некий прообраз, слепком с которого является материальная вещь, идеалом, которого она никогда не сможет достигнуть. Возьмем, к примеру, сделанный из дерева круглый стол. Его форма будет очень близка к кругу, но каким бы искусным не был плотник, как бы он не старался, стол никогда не будет совершенно круглым. Его площадь будет очень близка к \pi r^2 , но никогда точно этой формуле соответствовать не будет. Таким образом, круглая форма этого стола является лишь слепком с некоего идеального круга. Как и сам стол, и все другие столы на свете несмотря на разницу форм и материалов являются лишь слепками с идеи стола.

Платон заметил, что математика полностью существует в мире идей. Представьте себе стол, на котором лежат три яблока. Так вот, само количество яблок "три" - это всего-лишь иллюзия, это идея в нашей голове. В материальном мире никакого количества нет - есть просто яблоки. Их количество существует лишь в нашем уме, а сами числа, которыми выражается количество, и все операции над ними существуют в мире идей. Подумайте над таким вопросом, было ли два плюс два было равно четырем до Большого Взрыва?

Платон верил, что как глаза нам даны чтобы видеть, а уши чтобы слышать, так и разум нам дан, чтобы воспринимать идеи. Ходит байка, что однажды за ужином в разговоре с Платоном известный циник Диоген воскликнул: "Стол и чашу вижу, а стольности и чашности не вижу", на что Платон резко парировал: "Чтобы видеть стол и чашу, нужны глаза, которые у тебя есть, а чтобы видеть стольность и чашность, нужен разум, которого у тебя нет. Да и вообще о чем можно спорить с человеком, живущим в бочке". Кстати, слово "циник" в предыдущем предложении относится не к моральной характеристике Диогена, а к тому, что он являлся ярким представителем философской школы циников, или в правильном произношении киников, что переводится с древнегреческого как "собаки". Вы можете знать содержащее этот же корень слово "кинолог", то есть "изучающий собак".

Киники были не единственными, кто придерживался противоположной платоновскому идеализму теории - материализму. Эта теория утверждает, что идеи нереальны и не существуют сами по себе - мы получаем их из анализа окружающего нас материального мира. Таким образом идея стола формируется у нас лишь потому, что мы видели в своей жизни десятки столов. Известный шотландский философ Дэвид Юм демонстрировал это на примере того, что простые идеи у человека появляются лишь из органов чувств, а сложные складываются из простых. Так идея летающего коня Пегаса - это сумма двух простых идей "лошади" и "крыльев", полученных нами из нашего непосредственного опыта наблюдения материального мира.

По иронии судьбы, одним из основоположников материализма стал платоновский ученик Аристотель, всегда обожавший поспорить со своим учителем. Не менее иронично, что самого Аристотеля судьба наградила столь же непослушным учеником, который предпочел завоевание мира нудным урокам по философии.

Музыка вселенной и сакральная геометрия

Другой знаменитый древнегреческий мыслитель Пифагор, живший за несколько веков до Платона, вошел в историю как великолепный математик и философ, настолько великий, что именно он ввел в обиход сами слова "философ" и "математик". В молодости Пифагор много путешествовал и провел долгие годы в Египте, где обучался различным наукам. После он ненадолго вернулся в родной город Самос, откуда тем не менее по политическим причинам был вынужден вскоре сбежать, и окончательно осел на юге Италии, где создал свою знаменитую пифагорейскую школу и где встретил свою трагическую смерть.

Пифагорейская школа была не только математически-философским кружком, но и религиозной сектой со странными правилами вроде "запрещается есть бобы", а также тайным обществом с запретом на распространение знаний. Доподлинно неизвестно, что именно из математических открытий и философских концепций было создано самим Пифагором, а что было приписано ему его последователями, так как запись учения была запрещена, и оно передавалось лишь устным путем, а до нас оно дошло лишь в пересказе других античных философов. По свидетельствам Аристотеля, именно учение пифагорейцев заложило основу взглядов Платона.

Основой метафизики Пифагора служило утверждение о том, что в основе всего лежит число. Он пришел к такому заключению, изучая музыку. Пифагор заметил, что интервал между высотами двух звуков зависит от соотношения длин струн, издающих их. Очевидно, что Пифагор не был первым, кто догадался об этом, но он был первым, кто провел глубокие исследования этой закономерности и свел музыку к строгой формальной математической системе. Именно Пифагор создал музыкальный строй и теорию о музыкальной гармонии, ставшей основой всей античной и современной музыки.

Поняв, что в основе музыки лежат строгие математические законы, и заметив множество подобных закономерностей в других областях, Пифагор задался вопросом, возможно ли такое, что звуковая гармония является лишь выражением всеобщей гармонии Вселенной, которая точно так же, как и музыка, описывается математикой. Подтверждения этой идеи Пифагор и его последователи нашли в астрономии. Они заметили, что все небесные тела движутся согласно строгим математическим законам. На базе этих наблюдений пифагорейцы создали учение о гармонии сфер, или как еще ее называли "мировой музыке" - музыкально-математическом устройстве космоса.

Учение пифагорейцев о гармонии сфер и создание пифагорейцем Филолаем задатков теории о гелиоцентрическом строении мира повлияло на множество известных астрономов последующих веков. Николай Коперник посвятил пифагорейцам свою книгу "О вращении небесных тел", Иоганн Кеплер озаглавил главный труд своей жизни "Гармония мира", закончив его описанием того, как "cогретый тёплым напитком из кубка Пифагора" засыпает под звуки небесной музыки. Исаак Ньютон писал, что видел в пифагорейском учении намеки на открытые им законы тяготения. Альберт Эйнштейн в одном из интервью сказал, что является "платонистом или пифагорейцем, так как считает логическую простоту незаменимым и эффективным инструментом своего исследования".

Мысль, что в основе всего лежит число, послужила основанием всей философии пифагорейцев. Пифагор и его последователи поклонялись числам. Число "один", по-другому называемое монадой, они считали божественным. Число "два" - причиной раздвоения. Каждое число они рассматривали геометрически, веря, что геометрическое изображение числа несет некий сакральный смысл. Их вера в сакральную геометрию породила целую науку о фигурных числах, одно из которых, тетраксис, они считали особенно священным.

Тетраксис - священный символ пифагорейцевТетраксис - священный символ пифагорейцев

Основу метафизических воззрений пифагорейской школы составило учение о двух противоположностях - пределе и беспредельном. Под пределом понимались числа, а под беспредельным - абстрактные математические понятия бесконечности. Филолай утверждал, что "природа, сущая в космосе, гармонически слажена из беспредельных и определяющих; так устроен и весь космос, и все, что в нём".

Но давайте пока что остановимся, и отложим устройство космоса на потом, а пока посмотрим в противоположную сторону - внутрь самого себя.

Пустота и мгновенность бытия

В "Критике чистого разума" известный немецкий философ Иммануил Кант пытался найти, но так и нашел Ding an sich, "вещь в себе" или менее буквально "вещь саму по себе", то есть предмет, свойства которого не зависят от нашего восприятия.

За две тысячи лет до Канта над похожим вопросом размышлял выдающийся индийский философ Сиддхартха Гаутама Шакьямуни, более известный нам под именем Будда. Само слово "Будда" образовано от индоевропейского корня "буд" и дословно переводится на русский как "пробудившийся".

Прежде чем углубляться в детали метафизики Гаутамы, давайте сыграем с вами в небольшую игру и из двух предложенных предложений выберем наиболее осмысленное:

  • Глокая куздра штеко будланула бокра и курдячит бокрёнка

  • Сангху Будда учил о шуньяте, пратитье-самутпаде, анитье, кшаникаваде и анатмане.

Кажется, что единственными осмысленными словами тут являются "Будда учил", но это не так. Второе предложение мы можем перевести на литературный русский примерно так: своей монашеской общине Будда преподавал учение о пустоте, взаимозависимом возникновении, непостоянстве составных вещей, мгновенности бытия и отсутствии собственного Я у вещей. Давайте поподробнее разберем каждое из понятий.

Шуньята - пустота. Будда учил, что все вещи и явления существуют только лишь в нашем сознании. Возьмем к примеру, человека. Человек воспринимается нами как нечто одушевленное, но по-сути человек это всего-лишь иллюзия, созданная набором взаимодействующих органов. Каждый из органов в свою очередь являются иллюзией, созданной набором взаимодействующих клеток. Каждая из клеток является иллюзией, созданной набором взаимодействующих молекул. Каждая из молекул является иллюзией, созданной набором взаимодействующих атомов. А каждый атом является иллюзией, созданной набором взаимодействующих протонов, нейтронов и электронов. Получается, что человек это всего-лишь облако как-то взаимодействующих друг с другом элементарных частиц. И только наше сознание придает этому облаку и каждому слою его абстракции какой-то смысл, именно наше сознание видит в целом нечто большее, чем сумму его частей, именно оно создает из пустоты бесконечно сложные объекты - живых существ, страны, галактики, математику, веб-сайты, произведения искусства.

Но если вы попробуете ответить на вопрос где именно находится само ваше сознание, вы придете к парадоксальному выводу. Сознание находится в вашем мозгу, ваш мозг в вашем теле, ваше тело на планете Земля, Земля в Солнечной системе, Солнце в Млечном Пути, Млечный Путь во Вселенной. Но где находится сама Вселенная? Только в вашем сознании.

Пратитья-самутпада - взаимозависимое возникновение. Будда учил, что ничто не может появиться из пустоты само по себе. Для появления любой новой вещи или явления необходимо взаимодействие двух или более частей. Чай появляется из взаимодействия горячей воды и листьев, а атом водорода из взаимодействия протона и электрона. А раз для появления любой вещи необходимо как минимум две части, то это значит, что все вещи являются составными.

Анитья - непостоянство составных вещей. Будда учил, что все составные вещи недолговечны и подвержены исчезновению. Все рождается и все умирает - растения, животные, люди, страны, религии, планеты, галактики и даже сама Вселенная проходят через этот цикл появления и исчезновения. И не существует ничего, что может обойти этот закон и существовать вечно.

Кшаникавада - мгновенность времени. Будда учил, что вне нашего сознания не существует ни прошлого, ни будущего. Прошлое - это лишь наши воспоминания, а будущее - это лишь расчет возможных вариантов развития событий. Единственное, что реально - это краткий миг между прошлым и будущем, исчезающе малое мгновение настоящего. Даже само течение времени является нашей иллюзией. Как смена 24 кадров в секунду на экране создает фильм, так и очень быстрая смена мгновений создает для наблюдателя всеобъемлющую иллюзию устойчивой и постоянной реальности.

Анатман - отсутствие собственного Я у вещей. Будда учил, что ни одна вещь не является неизменной и не имеет "души" или "самости" - чего-то, что остается у вещи с течением времени и определяет ее. Чтобы лучше понять это утверждение, давайте рассмотрим его на примере корабля Тесея. Корабль плавал по морям долгие годы, что-то в нем ломалось, гнило, и поэтому корабль часто чинили. При починке в нём постепенно заменяли доски, и так продолжалось до тех пор, пока в нем не осталось ни одной старой доски. Возникает вопрос: если все доски в корабле заменили, то является ли он тем же самым кораблем, которым был когда-то? Будда отвечает на этот вопрос отрицательно и утверждает, что ни корабль, ни какая-либо другая вещь или явление не обладает собственной ''душой", своим собственным Я. Но при этом Будда не отрицает целостности самого потока состояний, вызванного действием закона причин и следствий, и утверждает, что именно целостность этого потока и создает у нас иллюзию существования "сущности" вещей.

Доктрина анатмана может быть применена не только к другим вещам, но и к нам самим. Являюсь ли я тем самым человеком, которым я был в возрасте пяти лет? Мое тело сильно изменилось, все его клетки много раз обновились, мой ум изменился, мои знания увеличились во много раз. Единственное, что осталось во мне от меня пятилетнего - это смутные обрывки нескольких воспоминаний. Поэтому можно смело утверждать, что несмотря на целостность потока причин и следствий, сделавшего из меня пятилетнего меня сегодняшнего - это все-таки совершенно разные люди. Но если я сейчас не имею ничего общего со мной пятилетним, то то же самое можно сказать и об отсутствии единства между мной сейчас и мной секунду назад. Таким образом, целостность нашего собственного сознания, нашего "Я", является иллюзией, образованной быстрой сменой различных состояний.

Может показаться, что Будда - нигилист и отрицает реальность чего бы то ни было, ведь все вещи и явления иллюзорны, но это не совсем так. Лучше всего позицию Будды и его последователей описал известный буддийский мыслитель Нагарджуна. Он утверждает, что знание об истинном устройстве Вселенной трансцендентно, оно приходит только после Просветления, которое заключается в понимании того, что реальность не описуема, а описываемое - не реальность. Нагарджуна видит единственный способ приблизиться к точному описанию устройства мира в определении его через отрицание того, чем он не является. Таким образом Нагарджуна приходит к выводу, что наш физический мир не реален, но и не нереален.

Для лучшего осознания этой истины буддисты советуют практиковать медитацию. А для того, чтобы помочь себе очистить свое сознание от посторонних мыслей при медитации, рекомендуют использовать мантру "Ом мани падмэ хум", произнесение которой занимает ровно один выдох воздуха из легких, помогает настроить ритм дыхания и забивает голову, не позволяя возникать лишним мыслям. Если вы начнете медитировать прямо сейчас, то вы наверняка заметите, как в вашей голове короткой электрической искрой промелькнет мысль: "Так, что это я вообще сейчас читаю? Какие нафиг еще медитации, мантры, пегасы и сакральная геометрия? Какого черта этот пост вообще делает в хабе математики и физики, и на Хабре вообще? Когда уже автор начнет втирать про рептилоидов?". Так что давайте пока что вернемся обратно в русло нашей статьи и поговорим о гипотезах современной теоретической физики.

Философия и физика

Все известные нам теории физики обладают одним настолько очевидным свойством, что иногда бывает даже трудно заметить его существование. Формулировка этого свойства может показаться вам трюизмом, но, если вдуматься, она им отнюдь не является. Это свойство состоит в том, что если очистить любую теорию физики от словесного описания, то все что останется - это набор аксиом о неких абстрактных объектах и набор формул, по которым эти абстрактные объекты взаимодействуют. Это свойство полностью подтверждает правоту Пифагора, считавшего, что Вселенная основана на математике.

Более того, если мы опустимся глубоко вниз на уровень элементарных частиц, мы увидим, что вся наша материя не является чем-то твердым и незыблемым, а является чистой математикой, существующей в мире идей Платона. Электроны и фотоны проявляют свойства не только частиц, но и волн, то есть по сути математических функций - это явление называется корпускулярно-волновым дуализмом. Также наблюдается другое интересное явление - принцип неопределенности Гейзенберга, при котором увеличение точности измерения одной характеристики частицы уменьшает точность измерения другой - этот принцип порождается исключительно математическими ограничениями и служит отличным подтверждением того, что на квантовом уровне наш мир является скорее "идеальным", чем "материальным". Именно "идеальность" нашего мира делает возможным нарушение принципа локальности - в мире математики нет времени и вычисление значений характеристик частицы происходит мгновенно вне зависимости от разделяющего эти частицы расстояния.

Далее, если мы поднимемся высоко на верх на уровень галактик и околосветовых скоростей, мы увидим, что и там наша реальность становится все менее "материальной" и все более странной. Мы увидим, что при приближении к скорости света время для нас относительно времени для неподвижного наблюдателя замедляется. Мы обнаружим в пространстве-времени точки, названные черными дырами, которые засасывают все окружающее их вещество и даже свет, которые, тем не менее, с их собственной точки зрения падает в эту дыру бесконечно долго. Мы убедимся в том, что наш мир скорее является некой математической идеей нежели чем-то материальным.

Если же мы захотим найти в этом безумном мире что-то стабильное и определенное, на что можно опереться, то нас постигнет неудача. Любые понятия или объекты физики не несут никакого собственного смысла. Возьмем, к примеру, электрический заряд. Наличие электрического заряда никак не может быть определено у одной единственной частицы - для того, чтобы подтвердить его существование нужно как минимум две частицы, а чтобы определить, что заряд - величина количественная нужно как минимум три частицы. То есть можно сказать, что заряд даже не существует без взаимодействия частиц. Это наблюдение подтверждает тезис Будды о взаимозависимом возникновении всех вещей и явлений.

Все вышеприведенные доводы показывают нам, как хорошо учения античных философов согласуются с самыми передовыми открытиями физики 20 века. Но что нам может предложить современная физическая и философская мысль?

Теория всего

Рассуждения знаменитого британского физика Стивена Хокинга дают нам интересную пищу для размышлений. Хокинг писал о том, что если даже мы завершим работу над "теорией всего" и найдем все уравнения и константы, согласно которым работает наша Вселенная, то перед нами мгновенно встанет следующий вопрос: почему именно эти уравнения? Что вдыхает в них огонь?

Самым очевидным и простым ответом на этот вопрос является, конечно, существование Бога-Творца и его промысла. Но есть и другой ответ, его дает американский физик Макс Тегмарк, профессор MIT и автор книги "Наша математическая вселенная". Тегмарк утверждает, что самый разумный ответ на данный вопрос такой: все непротиворечивые математические структуры реально существуют, и мы живем в одной из них. Эта гипотеза хороша тем, что она не плодит никаких лишних сущностей. Используя антропный принцип, мы можем допустить, что в некоторых очень сложных математических структурах возможно появление подструктур, обладающих самосознанием и способных исследовать саму эту структуру. Такими подструктурами являемся мы - Homo Sapiens.

Логическим развитием гипотезы математической вселенной Тегмарка служит гипотеза рекурсивно-вычисляемой вселенной Стивена Вольфрама. Ее главная идея состоит в том, что математическая структура, в которой мы живем, не финитна, а постоянно и рекурсивно самовычисляема. То есть, что настоящее - краткий миг между прошлым и будущем - это конкретное состояние нашей структуры, а физические законы Вселенной - это некая функция, и следующее состояние структуры является результатом применения функции к ее предыдущему состоянию.

Аргументы в пользу гипотезы рекурсивной Вселенной

В пользу гипотезы рекурсивно-вычисляемой математической Вселенной говорят некоторые факты.

Первым аргументом является существование нескольких осей времени, то есть таких явлений, в которых состояние системы в прошлом и будущем не симметрично относительно настоящего:

  • Причинно-следственная ось: причины порождают следствия, а не наоборот.

  • Психологическая ось: мы помним прошлое, но не знаем ничего о будущем.

  • Термодинамическая ось: энтропия в замкнутой системе только растет.

И если с первыми двумя утверждениями еще можно поспорить и заявить, что причинно-следственная связь - это лишь иллюзия, порожденная нашим умом, то поспорить со вторым законом термодинамики так просто не получится.

Эти и другие оси времени очень хорошо объясняются рекурсивным вычислением Вселенной. Текущее состояние - это входные данные функции, а следующее состояние - это выходные данные функции. Выходные данные зависят от входных, следующее состояние памяти зависит от текущего, а сложность и разнообразие получаемых состояний со временем может только расти.

Вторым аргументом в пользу гипотезы может послужить сильное сходство строения нашей Вселенной и многих объектов, существующих в ней, со строением фракталов, порождаемых рекурсивными функциями. Фрактал - это множество, обладающее самоподобием - объект, в точности или приближённо совпадающий с частью самого себя. Именно так устроена наша Вселенная. Планетарные системы похожи на атомы, звездные системы похожи на планетарные, а устройство галактик похоже на устройство звездных систем. Но при том, каждый из уровней имеет свою собственную неповторимую структуру. Посмотрите, насколько изображение множества Мандельброта, порождаемое простейшей рекурсивной функцией z(n+1) = z(n)^2 + c, напоминает фотографии далеких галактик.

Множество МандельбротаМножество Мандельброта

Вселенная - матрица или Матрица?

Гипотеза о рекурсивно-вычисляемой Вселенной неизбежно наводит на мысли о том, что весь наш мир может быть лишь симуляцией, работающей на каком-то мощном компьютере во внешней "настоящей" реальности, а все мы - лишь персонажами игры Sims. Такую возможность нельзя отрицать, но она никак не противоречит нашей гипотезе. Если мы действительно живем в симуляции, то компьютер, на котором вычисляется наша Вселенная точно также должен быть устроен на принципах математики, ведь математика живет в мире платоновских идей и не является частью нашей реальности. Чтобы создание такого компьютера было возможно, внешняя "настоящая" Вселенная тоже должна быть основана на строгих математических законах. А следовательно к ней точно также может быть применена гипотеза симуляции, и существа, живущие во внешней Вселенной, не могут точно быть уверены в том, что их мир не является симуляцией. Но как бы далеко в бесконечность не уходила вложенность симуляций друг в друга, в конце концов на самом верху должна будет существовать "самая настоящая" Вселенная, и она тоже должна быть основана на законах математики.

В поисках Бога

Как это ни странно, но именно основание нашего мира на математике оставляет в нем место для Бога. Чтобы понять, как это возможно, стоит мысленно отправиться в начало 20 века. В те времена среди математиков и философов была очень популярна идея о том, что вся математика может быть сведена к некоему компактному ядру, состоящему из аксиом и методов доказательства теорем. Знаменитый британский философ и математик Бертран Рассел, более всего известный по названному в его честь летающему в космосе чайнику, считал, что это ядро будет основано на логике - это направление поиска оснований математики называлось логицизмом. Великий немецкий математик Давид Гильберт, который кроме своих блестящих успехов в математике также внес значительный вклад в физику, оказав Альберту Эйнштейну помощь в создании уравнений гравитационного поля для общей теории относительности и заложив основы математического аппарата квантовой механики, считал, что это ядро будет основано на формальных системах - это направление называлось формализмом.

Все мечты Рассела и Гильберта были разрушены 7 сентября 1930 года в Кёнинсберге (нынешнем российском Калининграде). В этот день молодой австрийский математик Курт Гёдель представил доказательство того, что в любой непротиворечивой формальной арифметике существует недоказуемая и неопровержимая формула. Это значит, что даже если наша Вселенная основана на законах математики, сводимых к некоторым базовым аксиомам, то существуют утверждения, которые даже теоретически невозможно будет ни доказать, ни опровергнуть. В математике такие недоказуемые и неопровержимые в рамках некоторой аксиоматики утверждения обычно называют абсурдными. Одним из таких абсурдных утверждений является гипотеза о существовании Бога-Творца. Поэтому для верующих в его существование людей всегда останется лазейка даже в математической Вселенной - верую, ибо абсурдно.

Заключение

Надеюсь, что вам понравился пост, и вы сможете извлечь из него что-нибудь полезное для себя. Напоследок мне хочется посоветовать вам книги, под впечатлением от которых написан этот пост:

  • "Мир Софии" - автор Юстейн Гордер - детская, но все же очень интересная и познавательная даже для взрослых книга про 14-летнюю девочку Софию, изучающую философию на собственной шкуре

  • "История западной философии" - автор Бертран Рассел - книга известного британского философа, в которой подробно и детально рассматривается вся западная философия: древнегреческая, еврейская, христианская, немецкая и английская

  • "Чапаев и пустота" - автор Виктор Пелевин - книга дает наиболее красочное и захватывающее описание буддийской философии

  • "Дзен и искусство ухода за мотоциклом" - автор Роберт Пирсиг - книга, пытающаяся найти ответ на вопрос "Что такое качество?" и полезная для любого программиста

  • "Наша математическая Вселенная" - автор Макс Тегмарк - книга физика-теоретика об устройстве нашей Вселенной

Спасибо за внимание!

Подробнее..
Категории: Научно-популярное , Физика , Математика , Читальный зал , Рекурсия , Вселенная , Фрактал , Будда , Пифагор , Принцип неопределённости , Тегмарк , Шуньята , Платон , Рекурсия!

Перевод Как я посчитал миллионное число Фибоначчи

05.05.2021 20:22:59 | Автор: admin

Все мы понимаем, что рекурсивное вычисление чисел Фибоначчи крайне неэффективно. Многим людям наверняка хотелось проверить, где пределы (не)эффективности, но не доходили руки, не хватало времени. Специально к старту нового потока курса Fullstack-разработчик на Python мы решили поделиться переводом статьи, автор которой шаг за шагом показывает возможности современного Python на примере разных подходов к вычислению чисел Фибоначчи. В статье вы найдёте проблемные значения n и сравнение производительности оптимального и неоптимального решений на графике.

Нет, заголовок вообще не кликбейтный. Несколько дней назад я действительно хотел найти оптимальное решение для расчёта чисел Фибоначчи, хотелось попробовать вычислить стотысячное число последовательности, но я задумался; если я могу вычислить стотысячное число, то что остановит меня в поисках миллионного числа Фибоначчи? Сегодня я покажу, как шёл к вычислению и с какими проблемами столкнулся.

Последовательность Фибоначчи одна из наиболее известных математических последовательностей и самый простой пример рекуррентных отношений. Каждое число последовательности это сумма двух предыдущих чисел, начиная с 0 и 1. Получается такая последовательность:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 и так далее...

В следующие несколько минут я исследую несколько разных подходов, а затем покажу оптимальное решение:

  1. Простая рекурсия.

  2. Кеш с рекурсией.

  3. Итеративный метод.

  4. Формула Бине.

  5. Расчёт 1000000-го числа Фибоначчи.

Но, прежде чем мы начнём, я должен сказать, что все упомянутые тайминги касаются оборудования, на котором я работаю сейчас, а версия Python 3.9.1.

Простая рекурсия

Это очень простой способ получить N-ное число Фибоначчи на Python:

def recursiveFib(n):    if n == 1 or n == 2:        return 1    return recursiveFib(n - 1) + recursiveFib(n - 2)

В коде используется рекурсия, он вызывает сам себя несколько раз, вычисляя предыдущее число и используя это число для вычисления следующего. Но это также недостаток, поскольку функция чрезвычайно неэффективна и ресурсоёмка: на каждом этапе она вычисляет предыдущие 2 числа, а также предыдущие 2 числа этих чисел и т. д.

Вскоре вы достигаете точки, когда вычисление следующего числа занимает слишком много времени, например, на моём компьютере мне потребовалось 1,43 секунды, чтобы вычислить 35-е число. Очевидно, что вычисление более высоких значений будет чрезвычайно медленным и практически невозможным.

Кеш с рекурсией

Поскольку мы постоянно вычисляем предыдущие 2 числа, для хранения числа можно воспользоваться возможностями кеширования, не нужно будет вычислять числа несколько раз. Встроенный модуль functools позволяет нам работать с LRU кешем; этот тип кеша организует элементы в порядке их использования. Такой подход может значительно ускорить процесс.

from functools import lru_cache@lru_cache()def recursiveFibCached(n):    if n == 1 or n == 2:        return 1    return recursiveFibCached(n - 1) + recursiveFibCached (n - 2)

Во-первых, нам нужно импортировать декоратор lru_cache из модуля functools и поместить его перед нашей функцией. Мы можем указать значение maxsize, чтобы сообщить кешу, сколько элементов нужно хранить, но по умолчанию оно равно 128, это значение прекрасно работает. Используя кеш, мы можем вычислить 200-е число Фибоначчи всего за 0,0002252 секунды!

Одна проблема с использованием рекурсии заключается в том, что если вы попытаетесь вычислить 501-е число, то получите ошибку RecursionError: maximum recursion depth exceeded in comparison. Но, к счастью, проблему можно решить, установив большее значение глубины рекурсии:

import syssys.setrecursionlimit(5000)

Теперь мы можем вычислить 1000-е число Фибоначчи, на вычисление которого мне потребовалось всего 0,001198 секунды. Однако это создало для меня ещё одну проблему: по какой-то странной причине я не мог вычислить 1553-е число в последовательности, и даже после увеличения предела рекурсии ничего не произойдёт, ничего не будет распечатано на терминале, и программа просто закончит выполнение. Очевидно, что это проблема и недостаток на моём пути к вычислению миллионного числа Фибоначчи.

Итеративный метод

Вы можете увидеть, что применение рекурсивного решения проблемы в компьютерной науке часто рассматривается как халатность, а итеративные методы считаются намного лучше. Для генерации чисел Фибоначчи мы можем создать итеративное решение:

def iterativeFib(n):    a, b = 0, 1    for i in range(n):        a, b = b, a + b    return a

Мы можем воспользоваться им, чтобы вычислить любое число Фибоначчи (я не тестировал подход с особенно большими числами), и часто этот подход работает также очень быстро, 1000-е число вычислилось всего за 0,0028195 секунды.

Вы можете задаться вопросом, почему нельзя воспользоваться этим подходом для вычисления 1000000-го числа, и да, это возможно, но займёт немного времени. Продолжайте читать, и я расскажу, почему.

Формула Бине

Формула Бине это формула, которая может использоваться для вычисления n-го члена последовательности Фибоначчи, а это именно то, что мы хотим сделать; эта формула названа в честь открывшего её французского математика Жака Филиппа Мари Бине. Вот она:

Формула Бине для вычисления n-ного числа FibonacciФормула Бине для вычисления n-ного числа Fibonacci

Вы можете заметить греческую букву PHI (), она означает золотое сечение:

Уравнение золотого сечения, phiУравнение золотого сечения, phi

Можно написать формулу на Python и сразу же начать работать с ней:

def formulaFib(n):    root_5 = 5 ** 0.5    phi = ((1 + root_5) / 2)    a = ((phi ** n) - ((-phi) ** -n)) / root_5    return round(a)

Примечание: для реализации на Python нам нужно вернуть округление вычисляемого числа, потому что при вычислении большого числа Python вернёт результат, в котором может быть более двадцати девяток после запятой.

Всё это хорошо, так как теперь у нас нет никаких циклов и мы можем мгновенно вычислить ответ, верно? Что ж, в этом методе есть небольшая загвоздка. Если мы попытаемся вычислить что-либо выше 1475-го числа, то столкнёмся с ошибкой: OverflowError: (34, result too large). Это связано с тем, как в python реализованы числа с плавающей точкой, они могут иметь конкретное максимальное значение, которое мы превышаем, когда используем этот метод.

Однако исправить ситуацию очень легко. Мы можем использовать встроенный модуль под названием decimal, чтобы создать десятичный объект с гораздо более высокой точностью и подходящим для работы с уравнением размером:

import decimaldef formulaFibWithDecimal(n):    decimal.getcontext().prec = 10000    root_5 = decimal.Decimal(5).sqrt()    phi = ((1 + root_5) / 2)    a = ((phi ** n) - ((-phi) ** -n)) / root_5    return round(a)

В этой новой функции мы устанавливаем значение точности длиной 10000 цифр, преобразуем наше значение квадратного корня из 5 в десятичное значение объекта и используем его в нашем уравнении. Это позволяет нам легко вычислить 10000-е число в последовательности за поразительные 0,0692986 секунды, а это по сравнению со всеми нашими предыдущими методами огромное улучшение.

Расчёт 1000000-го числа Фибоначчи

Теперь вы, возможно, заметили, что формула работает медленнее итерационного решения, когда n=10000. Это связано с тем, что в формуле нам нужно создать десятичный объект и использовать его в уравнении, этот процесс занимает больше времени, чем повторение одной простой инструкции 10000 раз. Но история ещё не окончена.

Увеличение количества циклов может радикально увеличить длительность всего процесса. В какой-то момент, когда n составляет приблизительно 89200, время, необходимое итеративному решению для вычисления ответа, равно времени, которое необходимо при вычислении по формуле; когда же n увеличивается, время выполнения итеративного алгоритма возрастает с большей скоростью, чем время на решение по формуле.

График, показывающий время работы формулы Бине и итерационного решенияГрафик, показывающий время работы формулы Бине и итерационного решения

На графике видно точку пересечения времени выполнения формулы и итерационных графиков. Исходя из этого мы можем сказать, что с увеличением n время вычисления числа Фибоначчи по формуле возрастает линейно. Но при итеративном решении время увеличивается с увеличением n. Это даёт нам понять, что для вычисления миллионного числа Фибоначчи нам нужно использовать формулу. Дополнительное изменение, которое я должен был сделать, чтобы правильно вычислить число, увеличить точность моего десятичного объекта строкой кода decimal.getcontext().prec = 300000.

Ваше время выполнения алгоритма может отличаться. На моём компьютере, чтобы вычислить 1000000-е число Фибоначчи, потребовалось:

  • 8,832661 секунды при решении с итерацией;

  • 1,151380 секунды с формулой Бине, это в 7,7 раза быстрее!

Если вам хочется узнать число, оно состоит из 208988 цифр и в текстовом файле занимает 209 КБ:

Заключение

Вот так я вычислил миллионное число Фибоначчи, конечно, я мог бы вычислить число больше, но на самом деле для этого нет никакой реальной причины, и это заняло бы много времени, даже с использованием формулы Бине. Из приведённого выше графика я могу оценить затраты времени: чтобы вычислить миллиардное число Фибоначчи, мне потребуется примерно 310,8467 секунды, я оставлю это читателям. А чтобы получить специальность Fullstack-разработчик на Python потребуется немногим более года. Но можно и быстрее на нашем курсе студенты не привязаны к программе и скорость их прогресса зависит от них самих.

Узнайте, как прокачаться и в других специальностях или освоить их с нуля:

Другие профессии и курсы

ПРОФЕССИИ

КУРС

Подробнее..
Категории: Python , Математика , Блог компании skillfactory , Рекурсия , Занимательные задачки , Числа , Задачки , Skillfactory , Фибоначчи , Заметки о производительности , Последовательности

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru