Кампания "за отмену Столлмана", начавшаяся с публикации в Medium предоставляет нам множество интересных данных. Так как подписание открытых писем за отмену и в поддержку Столлмана осуществляется на гитхабе, мы можем проанализировать некоторые характеристики обеих сторон, используя статистические данные, которые доступны через API.

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

Следующие предположения можно проверить ("X" может быть как предложением отменить Столлмана, так и выражением его поддержки):

• Противники X чаще ассоциированы с крупными компаниями чем сторонники

• Сторонники X чаще и больше коммитят код и этим более полезны сообществу СПО.

• Противники X значимо реже коммитят в репозитории со свободными лицензиями.

• Противники X предпочитают Rust (или JS), сторонники предпочитают C (или C++, Python)

• Противники X в большей степени социально активны, у них есть аккаунты в соц. сетях, твиттере, они часто пишут.

• Противники X не коммитят код по выходным (работают только в рабочее время, не энтузиасты)

• Большинство противников X зарегистрированы на гитхабе менее полугода назад

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

Мы создали репозиторий, в котором будет проходить работа. В нем же лежит эта статья, ее копия на Хабре будет актуализироваться по мере добавления пулл-реквестов. Присоединяйтесь к исследованию!

Далее будут детали.

Замечание о научной честности

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

Кампания за отмену Столлмана управляется из одного центра

Репозиторий противников Столлмана был создан 23 Mar 2021 10:42:36 AM PDT, сторонников - 23 Mar 2021 01:23:39 PM PDT. Видно, что репозиторий противников практически сразу начал активно набирать звезды. У репозитория сторонников был длительный период, когда звезды набирались медленно, но потом (видимо после публикации в соц сетях) процесс пошел много быстрее и количество звезд быстро обогнало противников.

$ cat get-stars.sh#!/bin/bashset -uepage=1owner_repo=$1while true; do    curl -s -H "Authorization: token $GITHUB_OAUTH_" \\        -H "Accept: application/vnd.github.v3.star+json" \\        "<https://api.github.com/repos/$owner_repo/stargazers?per_page=100&page=$page>"| \\        jq -r .[].starred_at_ | grep . || break    ((page++)) || truedone$ echo "epoch,con" >con.stars.csv$ ./get-stars.sh 'rms-open-letter/rms-open-letter.github.io'|while read a; do date -d $a +%s; done|sort -n|cat -n|awk '{print $2","$1}' >>con.stars.csv$ echo "epoch,pro" >pro.stars.csv$ ./get-stars.sh 'rms-support-letter/rms-support-letter.github.io'|while read a; do date -d $a +%s; done|sort -n|cat -n|awk '{print $2","$1}' >>pro.stars.csv$ join -t, -e '' -o auto -a1 -a2 con.stars.csv pro.stars.csv >joined.stars.csv

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

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

Активность в репозиториях сторонников и противников Столлмана

На момент написания этой статьи было 1345 комиттеров противников и 5000+ коммиттеров сторонников. Скачиваем историю коммитов:

$ cat get-commits.py#!/usr/bin/env pythonimport osimport requestsimport jsonimport sysrepo = sys.argv[1]headers = {'Authorization': 'token {}'.format(os.environ["GITHUB_OAUTH"])}commits = []page = 0while page < 300:    page += 1    data = requests.get('https://api.github.com/repos/{}/commits?per_page=100&page={}'.format(repo, page), headers=headers).json()    if len(data) == 0:        break    commits += dataprint(json.dumps(commits, indent=4))$ ./get-commits.py 'rms-open-letter/rms-open-letter.github.io' >con.commits.json$ ./get-commits.py 'rms-support-letter/rms-support-letter.github.io' >pro.commits.json

Посмотрим на изменение количества коммитов от времени с начала кампаний:

$ jq -r .[].commit.author.date pro.commits.json|sort -u|cat -n|awk '{print $2","$1}'|sed -e 's/T/ *' -e 's/Z/*' >pro.commits.csv$ jq -r .[].commit.author.date con.commits.json|sort -u|cat -n|awk '{print $2","$1}'|sed -e 's/T/ *' -e 's/Z/*' >con.commits.csv$ join -t, -e '' -o auto -a1 -a2 con.commits.csv pro.commits.csv >joined.commits.csv

Видно, что репозиторий сторонников гораздо активнее. Коммитов в репозиторий противников за последнее время практически не было. Репозиторий сторонников продолжает обновляться.

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

Посмотрим на распределение коммитов по дням недели.

$ jq -r .[].commit.author.date con.commits.json |./weekday-from-date.py >con.rms_commits.csv$ jq -r .[].commit.author.date pro.commits.json |./weekday-from-date.py >pro.rms_commits.csv$ join -t, con.rms_commits.csv pro.rms_commits.csv >joined.rms_commits.csv

Aктивность противников Столлмана сильно снижается на выходных, зато в среду мы видим пик. Это можно объяснить тем, что во многих компаниях среда это no meeting day.

Активность сторонников значительно менее вариативная. Коммиты совершаются во все дни недели

Противники Столлмана чаще имеют заполненные профили социальных сетей

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

$ jq -r .[].author.login con.commits.json|sort -u >con.logins$ jq -r .[].author.login pro.commits.json|sort -u >pro.logins$ cat get-user-events-data.sh#!/bin/bashset -uescript_dir=$(dirname $(realpath $0))get_data() {    local data_dir=$script_dir/$1 userdata events    for x in $(cat $1.logins); do        userdata=$data_dir/$x.userdata        [ -r $userdata ] && continue        curl -s -H "Authorization: token $GITHUB_OAUTH" "<https://api.github.com/users/$x>" >$userdata        sleep 1        events=$data_dir/$x.events        [ -r $events ] && continue        curl -s -H "Authorization: token $GITHUB_OAUTH" "<https://api.github.com/users/$x/events?per_page=100>" >$events        sleep 1    done}get_data $1$ ./get-user-events-data.sh con$ ./get-user-events-data.sh pro

Пример данных юзера, выгруженных из гитхаба:

{  "login": "zyxw59",  "id": 3157093,  "node_id": "MDQ6VXNlcjMxNTcwOTM=",  "avatar_url": "https://avatars.githubusercontent.com/u/3157093?v=4",  "gravatar_id": "",  "url": "https://api.github.com/users/zyxw59",  "html_url": "https://github.com/zyxw59",  "followers_url": "https://api.github.com/users/zyxw59/followers",  "following_url": "https://api.github.com/users/zyxw59/following{/other_user}",  "gists_url": "https://api.github.com/users/zyxw59/gists{/gist_id}",  "starred_url": "https://api.github.com/users/zyxw59/starred{/owner}{/repo}",  "subscriptions_url": "https://api.github.com/users/zyxw59/subscriptions",  "organizations_url": "https://api.github.com/users/zyxw59/orgs",  "repos_url": "https://api.github.com/users/zyxw59/repos",  "events_url": "https://api.github.com/users/zyxw59/events{/privacy}",  "received_events_url": "https://api.github.com/users/zyxw59/received_events",  "type": "User",  "site_admin": false,  "name": "Emily Crandall Fleischman",  "company": "Commure",  "blog": "",  "location": null,  "email": "emilycf@mit.edu",  "hireable": null,  "bio": null,  "twitter_username": null,  "public_repos": 24,  "public_gists": 0,  "followers": 2,  "following": 12,  "created_at": "2012-12-31T05:33:30Z",  "updated_at": "2021-03-14T01:53:51Z"}

В таблице ниже приводится процент пользователей, у которых заполнены поля twitter_username, company, bio и blog:

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

Противники Столлмана активнее на гитхабе

Посмотрим на поля public_repos, public_gists, followers и following:

Противники Столлмана активнее сторонников на гитхабе. У них в среднем больше followers, публичных репозиториев, они также чаще фолловят другие репозитории. Также у противников соотношение followers / following больше 3, в то время как у сторонников оно составляет 1.1.

Противники Столлмана не коммитят в гитхаб на выходных

Воспользуемся полем events_url, чтобы скачать историю действий юзеров.

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

cat weekday-from-date.py#!/usr/bin/env python                                                                                                                                                                                                                                                                                          import datetime                                                                                                                                         import sys                                                                                                                                                                                                                                                                                                      out = [0] \* 7                                                                                                                                          total = 0                                                                                                                                                                                                                                                                                                       for line in sys.stdin.readlines():                                                                                                                          weekday = datetime.datetime.strptime(line.strip(), '%Y-%m-%dT%H:%M:%SZ').weekday()                                                                      out[weekday] += 1                                                                                                                                       total += 1                                                                                                                                                                                                                                                                                                  for day, count in enumerate(out):                                                                                                                           print("{},{}".format(day, count / total))                                                                                                                                                                                                                                                                   $ jq -r .[].created<sub>at</sub> con/\*.events|./weekday-from-date.py >con.event<sub>day.normalized.csv</sub>                                             $ jq -r .[].created<sub>at</sub> pro/\*.events|./weekday-from-date.py >pro.event<sub>day.normalized.csv</sub>                                             $ join -t, con.event<sub>day.normalized.csv</sub> pro.event<sub>day.normalized.csv</sub> 

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

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

Итак, Снежинка хочет стать программистом. Теперь несколько деталей.

Кто Снежинка сейчас?

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

Код, обычно, ему дают написать несложный и не важный. Причина в особенностях Снежинки, которых две.

Ограничение гугл

Снежинка родился со смартфоном в руке. Не будем давать оценку этому факту, лишь беспристрастно опишем последствия.

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

Почти всё остальное Снежинка тоже может сделать, хоть и не знает, и не умеет. Потому что у Снежинки есть гугл его, снежинкин, персональный резервный мозг, который хранит в себе всё, что может пригодиться в жизни. Раз есть такой прекрасный резервный мозг, основной можно не нагружать. Чем Снежинка и пользуется.

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

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

Ограничение клип

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

В причинах ковыряться не будем, посмотрим на следствие: Снежинка не может сосредоточиться на одном вопросе дольше, чем на несколько минут (клип). Максимум 15, но в среднем 5-7.

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

И вот Снежинка решил подняться на уровень выше стать программистом. Или разработчиком не будем углубляться в терминологию. Более серьёзным чуваком, короче. Снежинка изъявил своё желание, и услышал требования к программисту.

Требования к программисту

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

После долгих споров, дискуссий и мозгового штурма Снежинке дали простую формулу 23 минуты. Кратко изложу суть.

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

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

Первое составные части объекта уже должны быть в голове. Не на бумаге, не в интернете, не у соседа, а в голове того, кто будет думать.

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

Теперь вы, наверное, уже понимаете, в чём загадка.

Загадка

Итак, подведём итоги и сформулируем загадку.

Программист должен уметь конструировать в голове сложные интеллектуальные объекты. Для этого нужно иметь в голове знания об объекте и уметь сконцентрироваться на 20 и более минут.

Снежинка хочет стать программистом. Но все знания Снежинки находятся не в его голове, а в гугле. Сконцентрироваться Снежинка способен на 5-7 минут, максимум на 15.

Как Снежинке стать программистом?

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

Но в современном мире иметь API недостаточно мало кто хочет формировать HTTP-запросы, передавать параметры, думать про правильную авторизацию. Поэтому мы предлагаем SDK для разных языков программирования: Python, PHP, C# и многих других. И кажется, что этого достаточно, чтобы сделать нашу платформу лёгкой в использовании для очень большой аудитории. Или всё-таки недостаточно?

Обратимся к статистике. По разным данным сейчас в мире насчитывается где-то 15-30 миллионов разработчиков цифра несомненно впечатляющая. Но, например, пользователей MS Excel в мире не менее 100 миллионов. Почему же они должны страдать? Ведь, будем честны, почти каждый из тех, кто хоть раз открывал Excel, явно ощущал недостаток возможностей по управлению коммуникационными платформами в этом без сомнения очень гибком программном продукте. Практически каждый день мы получаем на наш email сотни запросов, которые сводятся к очень простой просьбе: Я хочу звонить из Excel!. Однажды у окон нашего офиса даже выстроились люди с такими требованиями (видели фото выше?) Мы просто не могли оставаться в стороне.

Однако звонки это всё-таки слишком революционно, а главное, потребует установки дополнительных ActiveX-компонентов, что, безусловно, противоречит всем существующим и несуществующим политикам информационной безопасности, поэтому давайте начнём с более простой вещи SDK для работы с нашим API. Из средств разработки в Экселе доступен VBA, для него мы и создадим SDK.

Для того, чтобы выполнить API-запрос, необходимо:

1. Сформировать URL и тело POST-запроса.

2. Добавить аутентификационные параметры.

3. Непосредственно выполнить запрос.

4. Распарсить результат (в нашем случае это JSON).

Формируем URL и тело POST-запроса

Первая часть, казалось бы, самая простая: нужно просто закодировать параметры в URL-кодировку и склеить их. Но в стандартом VBA не предусмотрена URL-кодировка (позже мы поймём, почему). Ничего страшного, на просторах Интернета есть множество разных решений, выберем одно из них.

Public Function URL_Encode(ByRef txt As String) As String    Dim buffer As String, i As Long, c As Long, n As Long    buffer = String$(Len(txt) * 12, "%")     For i = 1 To Len(txt)        c = AscW(Mid$(txt, i, 1)) And 65535         Select Case c            Case 48 To 57, 65 To 90, 97 To 122, 45, 46, 95  ' Unescaped 0-9A-Za-z-._ '                n = n + 1                Mid$(buffer, n) = ChrW(c)            Case Is <= 127            ' Escaped UTF-8 1 bytes U+0000 to U+007F '                n = n + 3                Mid$(buffer, n - 1) = Right$(Hex$(256 + c), 2)            Case Is <= 2047           ' Escaped UTF-8 2 bytes U+0080 to U+07FF '                n = n + 6                Mid$(buffer, n - 4) = Hex$(192 + (c \ 64))                Mid$(buffer, n - 1) = Hex$(128 + (c Mod 64))            Case 55296 To 57343       ' Escaped UTF-8 4 bytes U+010000 to U+10FFFF '                i = i + 1                c = 65536 + (c Mod 1024) * 1024 + (AscW(Mid$(txt, i, 1)) And 1023)                n = n + 12                Mid$(buffer, n - 10) = Hex$(240 + (c \ 262144))                Mid$(buffer, n - 7) = Hex$(128 + ((c \ 4096) Mod 64))                Mid$(buffer, n - 4) = Hex$(128 + ((c \ 64) Mod 64))                Mid$(buffer, n - 1) = Hex$(128 + (c Mod 64))            Case Else                 ' Escaped UTF-8 3 bytes U+0800 to U+FFFF '                n = n + 9                Mid$(buffer, n - 7) = Hex$(224 + (c \ 4096))                Mid$(buffer, n - 4) = Hex$(128 + ((c \ 64) Mod 64))                Mid$(buffer, n - 1) = Hex$(128 + (c Mod 64))        End Select    Next    URL_Encode = Left$(buffer, n)End Function

Следующий нюанс передача даты и времени. В API Voximplant временные метки принимаются в UTC в формате YYYY-MM-DD hh:mm:ss. В Excel же дата и время хранятся без учёта часового пояса (на самом деле, в самой таблице они вообще хранятся как число с плавающей точкой). Поэтому нам придётся принимать дату/время из таблицы тоже UTC. Мы думаем, что все 100+ миллионов пользователей Excel знают, что такое UTC, и это не вызовет у них никаких вопросов.

Кстати, в VBA есть функция форматирования даты, и она даже работает, но весьма необычным образом. Интересующий нас формат даты описывается так: yyyy-mm-dd hh:mm:ss. То есть mm это либо месяц, либо минуты в зависимости от того, за чем оно следует: за hhили за yyyy (это не шутка, это даже в MSDN описано). В общем, если кто-то захочет вывести время без часов, придётся импровизировать.

Переходим к аутентификации

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

А что же VBA? К сожалению, разумно простого способа сформировать JWT-подпись просто не существует. Причина в том, что в VBA доступен фреймворк .NET версии 4.x, а функция RSA.ImportPkcs8PrivateKey, необходимая для загрузки приватного ключа из PKCS8, появилась только в .NET 5. Да и вообще, все .NET-разработчики используют для таких задач сторонние библиотеки.

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

Выполняем запрос

Переходим к третьей части к выполнению самого запроса. Встроенных средств работы с HTTP в VBA нет (теперь понятно, почему нет и функции URL-кодирования, а зачем?).

Но, тем не менее, это достаточно тривиальная манипуляция подключаем необходимый фреймворк MSXML 6.0 и Microsoft Scripting Runtime и выполняем запрос, подключая через COM сам MSXML. Просто!

Function makeRequest(name As String, params As Dictionary, accountId As Integer, apiKey As String) As Object    Dim objHTTP As New MSXML2.XMLHTTP60    Dim jsonData As String    Dim parsedJson As Object    Dim postString As String    postString = ""        Dim iterKey As Variant        For Each iterKey In params.Keys        postString = postString & "&" & iterKey & "=" & URL_Encode(params(iterKey))    Next    Url = "https://api.voximplant.com/platform_api/" + name    objHTTP.Open "POST", Url, False    objHTTP.send "account_id=" & accountId & "&api_key=" & apiKey & postString    jsonData = objHTTP.responseText    Set parsedJson = JsonConverter.ParseJson(jsonData)    Set makeRequest = parsedJsonEnd Function

Парсим JSON

Ну и, наконец, JSON. Как и всё остальное, парсер JSON надо искать где-то вовне экосистемы VBA. К счастью, на дворе 2021 год, есть GitHub, и кто-то уже озадачился созданием JSON-парсера для VBA. Мы взяли вот такой.

Он подключается как отдельный модуль и превращает JSON-строку в Dictionary. То, что нужно!

Дальше берём генератор одного из наших SDK (мы взяли питоновский), заменяем шаблоны и заставляем его генерировать код на VBA. В итоге получаем готовый SDK, который можно скачать на нашем GitHub.

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

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

Для этого пишем вот такую функцию:

Function getTotalCallCost(FromDate, ToDate, Username) As Double    Dim totalCost As Double    Dim lastCount As Integer    Dim offset As Integer    Dim res As Dictionary    Dim RecordsPerRequest As Integer    Dim api As New VoximplantAPI    totalCost = 0    lastCount = 1    offset = 0    RecordsPerRequest = 100        'Pass Voximplant account id and API key    api.SetCredentials 100, "aaaaaaaa-aaaa-aaaa-aaaa-aaaaaaaaaaaa"        Do While lastCount > 0        Set res = api.GetCallHistory(FromDate, ToDate, remote_number:=Username, with_calls:=True, with_records:=True, with_other_resources:=True, offset:=offset, count:=RecordsPerRequest)                Dim session As Variant        Dim item As Variant                For Each session In res("result")            For Each item In session("calls")                totalCost = totalCost + item("cost")            Next            For Each item In session("records")                totalCost = totalCost + item("cost")            Next            For Each item In session("other_resource_usage")                totalCost = totalCost + item("cost")            Next        Next                lastCount = res("count")        offset = offset + RecordsPerRequest    Loop        getTotalCallCost = totalCostEnd Function

И вызываем её следующим образом:

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

Резюме:

При желании можно и для VBA сделать какое-то подобие SDK. При его создании не пострадал ни один разработчик. Ах да, с 1 апреля! :D

Мы уже писали об удивительном свойстве числа e, которое может помочь, когда вслепую из конечного числа вариантов нужно выбрать единственный вариант. Сегодня давайте вспомним о тождестве Эйлера по праву самом красивом уравнении, важное место в котором занимает число e, но не только оно. Представьте на секунду, что вы почти ничего не знаете о математике, только начинаете открывать её бесконечную красоту и наслаждайтесь.

Все мы знаем о числе магическом отношении длины окружности к её диаметру. Число можно приближённо представить в виде дроби 22/7. Особенность числа состоит в том, что в его десятичной записи знаки после запятой никогда не заканчиваются. Его приближённое значение 3,141592653589793238 Вот почему называют иррациональным числом его нельзя записать в виде конечного числа цифр после запятой. А вот другое интересное иррациональное число e. Число e это "число Эйлера" (от Euler). Вот первые несколько цифр числа e: 2,7182818284590

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

Что означает эта запись? В натуральном логарифме f(x)=ln(x) это степень, в которую нужно возвести число e, чтобы получить x. Как же рассчитать значение e, спросите вы? Есть несколько способов.

Вот один из них: e это предел последовательности, общий член которой равняется (1+ 1/n). Вот ещё один: площадь области под графиком y=1/x от x=1 до x=e равняется одному единичному квадрату.

Ещё один способ определения e: посмотрите на ряд 1 + 1/1! + 1/2! + 1/3! + 1/4! +. Сумма этого ряда равняется e.

Чтобы вы почувствовали, насколько важным может быть число e, рассмотрим пример. Предположим, есть стеллаж с книгами, на каждой полке которого стоит только одна конкретная книга. Предположим также, что кто-то скинет на пол все книги и вы начнёте подбирать их с пола одну за одной и снова ставить на полки. Вероятность того, что каждая книга попадёт не на свою полку, составляет примерно 1/e. Чем больше книг, тем ближе такая вероятность будет к значению 1/e.

Поговорим теперь о другом интересном математическом объекте. Он называется просто: i. Разберёмся, что это такое.

Если умножить 2 на 2, получится 4. То есть 2 в квадрате равняется 4. Квадрат положительного числа это положительное число. Но, если возвести в квадрат 2, также получится 4, то есть положительное число. Другими словами, ни один квадрат действительного числа не может быть отрицательным числом. Вот тут-то и возникает понятие мнимого числа.

Число -1 записывается буквой i. i означает мнимую (imaginary) единицу. То есть запись -5 можно заменить записью 5 i. Отсюда следует, что i = -1. Число i формирует множество комплексных чисел, то есть комбинаций действительных и мнимых чисел. Например, запись 8 + i5 является комплексным числом. Для визуализации комплексных чисел используется плоскость мнимых чисел.

Изучать свойства комплексных чисел математики начали примерно с середины XVIII века. Однажды Эйлер развлекался с женой Тейлора... ох, простите... с рядом Тейлора. Ряд Тейлора:

Этому сумасброду просто стало интересно, как будет вести себя ряд Тейлора, если подставить в него число i (а что, вполне нормальная мысль для любого сумасброда).

И вот что у него начало получаться:

Но i = -1 (Ух! Меня уже начинает охватывать научный азарт!) Сгруппируем все члены ряда, содержащие i.

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

Мы получили знаменитую формулу Эйлера. Различные значения x и e^(ix) можно отразить на комплексной плоскости. Например,

Это комплексное число, которое может быть представлено на комплексной плоскости. Если продолжить наносить на график точки e^(ix) для разных значений x, получится окружность.

Если нужно узнать радиус r в любой точке (например, в точке 5 + 7i), рассчитывается значение x и берётся действительная часть re^(ix). Наконец, если в формулу Эйлера подставить значение x = , получаем:

(поскольку cos = 1 и sin = 0).

Объединив три самых необыкновенных математических символа, получаем магическое уравнение:

Вот оно перед вами по мнению математиков, самое красивое уравнение во всей математике. Оно называется Тождеством Эйлера.

Приходите на курс "математика для Data Science" и наши менторы покажут, как при помощи математики менять мир к лучшему. Но даже если менять мир в ваши планы пока не входит там можно будет подтянуть математическую базу. Будет сложно, но интересно.

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

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering

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

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

В самом простом варианте задачи голодное животное привязывается к боковой стенке длинного сарая верёвкой фиксированной длины.

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

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

Значит, площадь полукруга в два раза меньше:

При длине верёвки 4 коза выщипает площадь (в квадратных единицах), равную

Решение этой элементарной задачи не представляет особой сложности ни для математика, ни для козы, поэтому давайте сделаем её интереснее. Что, если коза будет привязана к боковой стенке сарая квадратной формы?

Предположим, что длина верёвки и длина стороны сарая равны 4 и что верёвка прикреплена к середине одной из сторон. На какой площади теперь может пастись коза? Коза по-прежнему может пастись в том же полукруге, что и в первой задаче.

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

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

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

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

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

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

Если длина верёвки больше 2 единиц, коза сможет обогнуть угол.

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

Нам необходимо найти длину верёвки, при которой общая площадь будет составлять 50 квадратных единиц. Математически это можно выполнить следующим образом: подставить в формулу площадь, равную 50, и решить это уравнение относительно r. Но для каждой области имеется своя формула расчёта площади. Какую же использовать?

Для того чтобы это выяснить, проведём небольшие вычисления. Если r 2, площадь области составит

Самая большая площадь будет при r = 2, то есть общая площадь составит

Это меньше 50, поэтому нам нужно более 2 единиц верёвки.

Если 2 < r 6, мы получаем полукруг плюс две четверти круга. Радиус полукруга равен r, а радиус четверти круга равен r 2, так как для того, чтобы добраться до угла, потребуется две единицы верёвки, а оставшаяся верёвка выступает в качестве радиуса четверти круга с центром в углу сарая.

Площадь этого полукруга равна

А площадь каждой четверти круга равна

Просуммировав выражения, получим общую площадь:

Наибольшую возможную площадь мы получим при r = 6, что даёт

квадратных единиц. Поскольку 50 < 26, это означает, что значение r, дающее 50 квадратных единиц площади, должно быть меньше 6.

Знание того, что значение r должно быть от 2 до 6 единиц, снимает вопрос о том, какую формулу для расчёта площади нужно использовать: если 2 < r 6, площадь

Чтобы найти точное значение r, которое даст 50 квадратных единиц площади, составим такое уравнение:

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

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

а затем воспользуемся формулой для решения квадратных уравнений. Немного алгебры и арифметики делают своё дело.

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

Поскольку мы смогли выделить r в уравнении, теперь мы точно знаем, какой длины должна быть верёвка, чтобы получить площадь в 50 квадратных единиц. (Обратите внимание, что найденное нами значение r, как и предполагалось, находится в пределах от 2 до 6.)

Думаете, это самая заковыристая задача с козой у сарая? Как бы не так! Математики обнаружили, что задача становится ещё более сложной, если поместить козу внутрь сарая.

Поместим козу внутрь квадратного сарая с длиной стороны 4 и прикрепим верёвку к середине стены. Какой длины должна быть верёвка, чтобы коза могла выщипать половину площади внутри сарая?

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

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

Начнём с треугольников. Согласно теореме Пифагора длины катетов в каждом правильном треугольнике равны

Таким образом, площадь одного из треугольников равна

Поэтому суммарная площадь обоих треугольников равняется

Перейдём к круговому сектору.

Площадь сектора равняется

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

Применяя теорему косинусов к равнобедренному треугольнику со сторонами r, r и 4, получаем:

и это уравнение можно решить для cos:

Чтобы выделить , нужно взять обратный косинус, или арккосинус, от обеих сторон уравнения. Это даёт:

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

Окончательная формула площади это сумма площади сектора и площадей двух треугольников, то есть:

Мы получили формулу для расчёта площади области, в которой может перемещаться коза внутри квадрата, полностью через r. Теперь нужно просто найти значение r, дающее козе доступ к половине площади. Площадь всего квадрата равна 16, поэтому нам остаётся только подставить в наше уравнение A = 8, решить его относительно r, и дело сделано.

Однако возникает одна небольшая проблема: это уравнение невозможно решить относительно r.

Вернее, это уравнение невозможно решить точно относительно r. Для приблизительного определения значения r можно использовать калькулятор (получится примерно 2,331), но выделить r в нашем уравнении нельзя. Сочетание в уравнении тригонометрических и полиномиальных функций создаёт непреодолимые препятствия для его точного разрешения относительно r.

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

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

Доступная для козы область имеет форму "линзы" два сложенных вместе круговых сегмента.

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

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

Упражнения

1. Если коза привязана к середине стороны квадратного сарая с длиной стороны 4 верёвкой длиной 8 единиц за пределами сарая, какова площадь области, которую может выщипать коза?

2. Если коза привязана к углу квадратного сарая с длиной стороны 4 верёвкой длиной 8 за пределами сарая, какова площадь области, которую может выщипать коза?

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

4. Если коза привязана к середине стороны квадратного сарая с длиной стороны 4 верёвкой длиной 10 за пределами сарая, какова площадь области, которую может выщипать коза?

Область состоит из полукруга радиуса 8, двух четвертей окружности радиуса 6 и двух четвертей окружности радиуса 2. Поскольку 8 равно половине периметра сарая, два полукруга за сараем пересекаются в середине.

Эта площадь состоит из трёх четвертей площади окружности радиуса 8 и двух четвертей площади окружности с радиусом 4.

И она равна

Эта область состоит из трёх четвертей окружности радиуса 8 и двух четвертей окружности радиуса 4.

И она равна

Подумайте, что произойдёт, если длина верёвки будет равна 10.

Поскольку углы равностороннего треугольника равны 60, доступная козе площадь составляет одну шестую часть круга радиуса r, площадь которой равна

Площадь равностороннего треугольника равна

Поэтому площадь треугольника с длиной стороны 4 равна

Положим обе площади равными

И с помощью этой формулы выразим r. Мы получим

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

Площадь, по-видимому, состоит из полукруга радиуса 10, двух четвертей окружности радиуса 8 и двух четвертей окружности радиуса 4. Эта площадь составляет

Но последние две четверти круга пересекаются за сараем.

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

Таким образом, общая площадь равна

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

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

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

• Профессия Data Analyst

• Курс по Data Engineering

Золото тамплиеров, пиратское хранилище, природная карстовая воронка или один гигантский обман? Проклятие острова Оук рассказывает нам, что семь человек должны умирать до того, как остров раскроет своё легендарное сокровище. Шесть человек погибли в поисках миллиардов в золоте, но опасность только подогревает исследования и спекуляции.

Разочаровывающий, увлекательный, манящий вы можете поставить любое прилагательное перед словами остров Оук, и будете правы, рассказывает Чарльз Баркхаус, историк шоу канала History Channel The Curse of Oak Island, в котором на протяжении восьми сезонов (с некоторыми результатами) рассказывается о продолжающихся поисках сокровищ.

Если вы не готовы к эмоциональной нагрузке, то можете собирать свои игрушки и уходить.

Охота за сокровищами денежной ямой острова Оук, то есть яма в 100 футов (около 30 с половиной метров) на острове в Новой Шотландии, где якобы хранится что угодно от пиратских сокровищ до Ковчега Завета, началась ещё в 1795 году. Хотя сокровища так и не были найдены, сопутствующие открытия очевидные подсказки, возможные ловушки и геологические диковинки заставляют искателей продолжать поиски, даже когда историки оспаривают более сенсационные заявления, связанные с кладом. Был ли остров Оук сокровищницей рыцарей-тамплиеров, секретным промышленным центром Британии или злополучной природной воронкой? Чтобы ответить на этот вопрос, конечно же, нужно копать.

Поиски начинаются

Остров Оук впервые привлёк к себе внимание вскоре после золотого века пиратства (примерно в 16501730 годах), когда Эдвард Лоу и Бартоло Мью Робертс патрулировали моря к северо-востоку от Америки. В 1795 году подросток из Новой Шотландии со своего дома на материке увидел парящие над островом странные огни.

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

Мальчики начали выкапывать то, что впоследствии стали называть денежной ямой. На глубине двух футов (60 сантиметров) они обнаружили круг из камней, окаймляющих окружность ямы, а на глубине 10 футов (3 метров) платформу из подогнанных в стенки ямы обрезков брёвен. Вторая платформа лежала на 20 футов (около 6 метров) ниже, но на этом рассказ о первом поиске заканчивается.

История возобновляется в начале 1800-х годов, когда компания Онслоу отправилась в первую официальную экспедицию для раскопок. Они продолжили раскопки с того места, где остановились в первый раз, обнаружив новые платформы через каждые 10 футов (около 3 метров) (приблизительно три метра), иногда со слоями замазки, древесного угля или кокосовых волокон. Кокосы не растут в радиусе 900 миль (приблизительно полтора километра) от Новой Шотландии, но в истории утверждается, что экипаж сделал ещё более грандиозное открытие на высоте 90 футов (более 27 метров): прямоугольный камень, исписанный странными знаками.

Исследователи и охотники за сокровищами сочли, что эти отметки были сделаны по ошибке инструментами экскаватора, но другие были уверены, что это секретный код, ведущий к зарытым сокровищам. В 1860-х годах профессор лингвистики из университета Далхаузи в Новой Шотландии изучил камень и определил, что код представляет собой подстановочный шифр: Сорок футов [кооло 12 метров] ниже погребены два миллиона фунтов. Но другая попытка перевода в 1970-х годах интерпретировала код как христианское предупреждение коптов не забывать о своём долге перед Господом.

Компания Онслоу продолжала копать, и на глубине 98 футов (кооло 30 метров) они обнаружили нечто, по звуку удара напоминавшее полый контейнер предположительно, хранилище сокровищ. Бригада прекратила работу на вечер, но когда они вернулись на следующее утро, то обнаружили, что котлован заполнен водой на 60 футов (около 18 метров). Предполагалось, что раскопки привели к срабатыванию мины-ловушки. И похоже, что наводнение, похоже, положило конец усилиям Онслоу; в 1805 году компания была распущена.

Удар проклятия

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

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

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

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

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

Не дали прорыва и современные технологии. Съёмочная группа 1971 года привезла камеры и монитор, чтобы исследовать примерно 235-футовую (чуть менее 72 метров) шахту (называемую скважиной 10X и находящуюся примерно в 180 футах (около 55 метров) от денежной ямы), и хотя они утверждали, что во время исследования на дне ямы был обнаружен деревянный сундук и отрубленная человеческая рука, этот инцидент так и не был зарегистрирован.

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

Несмотря на это, рассказывает Баркхаус, количество доказательств, которые мы находим [на острове Оук], заставляет вас поверить, что какая-то группа или какой-то человек сделали там нечто особенное.

Дыры в поиске

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

Есть другие пробелы: многие считают, что звенья золотой цепи от группы 1849 года были подброшены самой группой для поощрения будущих экспедиций, а камень с надписью, найденный в начале 1800-х годов, был зарегистрирован как найденный только в 1862 году. Этот камень вообще не упоминался в инвестиционном проспекте компании Oak Island Treasure Company за 1893 год: ни сам камень, ни его маркировка не были зарисованы или сфотографированы, а существующее сегодня изображение камня датируется 1949 годом. Именно с этого времени начинаются современные переводы.

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

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

Небылицы о денежной яме

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

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

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

Реальность такова, что они не всегда [достаточно знают об ордене]. Чтобы придать смысл миру, который нам трудно понять, мы часто придумываем повествования.

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

Тем не менее правда об острове Оук сохраняет элементы интриги. Исследование, проведённое историком Джой А. Стил и отставной морской геолог Гордон Фейдер доказывают, что на острове Оук располагался секретный британский промышленный центр.

Изучив деловую документацию и современную переписку, пара пришла к выводу, что в 1720 году корона совместно с британскими военными зафрахтовала частные компании, чтобы вести дела на острове Оук, включая производство сосновой смолы, изготовление латуни и волочение проволоки, чтобы помочь погасить задолженность. В то время это была крупнейшая промышленная разработка в Канаде, рассказывает Фейдер: Был миллион причин отправиться на остров Оук он ближе всего к пресной воде, ближе всего к берегу, безопасен; остров самый большой в заливе это хорошая стоянка.

Стил и Фейдер уверены, что Денежная яма была естественным геологическим объектом, который британцы использовали в качестве печи для обжига сосновой смолы для производства дёгтя, чтобы покрывать ими свои корабли. Раскопанные слои Денежной ямы дерево, уголь и шпаклёвка соответствуют тому, что можно было бы ожидать в старой смоляной печи, также рассказывает Фейдер. Он отмечает, что зарытое в бухте Смита, П-образное строение, скорее всего, было частью сарая для хранения сосновой смолы в бочках и на солнце.

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

Канцлер казначейства Англии (по сути, министр финансов) и другие высокопоставленные банковские чиновники того времени часто ссылались на Секрет в своей переписке, рассказывает Стил, который [несомненно] проект Оук-Айленд.

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

Контрсвидетельства природы

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

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

Можно наблюдать, как развивается воронка и как сосна в 60 футов (примерно 18 метров) падает [в неё] за две секунды, говорит он, иллюстрируя, как в яме могли разместиться предметы размером с мачты британских кораблей.

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

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

Эйткен пишет, что отложения над брекчией в Денежной яме утолщены до 37 футов (чуть более 11 метров), а это указывает на позднее заполнение впадины. По словам Эйткена, первоначальная впадина, обнаруженная в 1795 году, также соответствует типичному проявлению карстовой воронки на поверхности.

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

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

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

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

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

Притягательность настоящих сокровищ, будь то Святой Грааль, Ковчег Завета или огромный пиратский банк, затмевает собой все остальные находки на острове Оук. Охота может никогда не прекратиться. Навязчивая идея богатства, как указал один из зарегистрированных искателей сокровищ ещё в 1862 году, может стоить борьбы.

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

Как формируются карстовые воронки?

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

Если вам интересны не только исследования и поиски сокровищ и вы хотите исследовать данные и извлекать пользу из них, то вы можете присмотреться к нашему курсу Data Science, итог которого эквивалентен двум-трём годам активных самостоятельных поисков в науке о данных.

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

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering

Представьте, что у вас нет под рукой калькулятора (но есть циркуль и линейка или угольник) и вам нужно посчитать результат в виде отрезка. Задача решается за менее чем 5 простых шагов.

Базовая формула вычисления

Для начала докажем одну формулу, которая нам будет помогать с дальнейшим решением.

В прямоугольном треугольнике ABC проведем высоту h на сторону C. По теореме Пифагора выводим:

Подставляем всё в первую формулу:

И если раскрыть скобки:

После сокращения получаем:

Вот с помощью этой формулы и будем выводить наши решения.

Единичная мера длины

Так как мы вычисления проводим на плоскости с отрезками, нам необходимо определиться с мерой единичной длины равной 1. Если мы отложим отрезок 1 дециметр, то он так же будет равен 10 сантиметрам, 100 миллиметрам или 4 дюймам. Один отрезок и 4 разных чисел разной меры длины его определяют. Что бы выбрать одну систему счисления длин отрезков, примем за единицу длины какой-то отрезок. Какой - определим по ходу расчетов, и он зафиксирует нужную меру длины.

Циркуль как универсальный инструмент

Циркуль удобно использовать как средство:

• отмерить отрезок определенной длины, при этом знать величину этой длины совершенно нет надобности.

• прочертить дугу на одинаковом расстоянии от определённой точки.

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

Вычисление квадрата длины

Для вычисления квадрата величины X используем нашу формулу в виде:

Чертим прямую линию достаточной длины.

Откладываем на ней отрезок единичной длины.

От правого конца единичного отрезка 1 откладываем вверх перпендикуляр длиной X.

Проводим линию от левого конца единичного отрезка 1 до верхнего конца отрезка X.

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

Пример. У вас есть какой-то квадрат, со стороной X, начерченный на плоскости или на земле. Нужно узнать его площадь в попугаях. Одна сторона квадрата длиной X у нас уже есть. На соседней стороне откладываем длину одного попугая (там где 1 находится). Соединяем концы линией, откладываем перпендикуляр, продлеваем отрезок с попугаями до перпендикуляра и получаем решение в квадратных попугаях.

Вычисление квадратного корня длины

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

Чертим прямую линию достаточной длины.

Откладываем на ней единичный отрезок длины 1.

На продолжении единичного отрезка откладываем отрезок длины X.

Полученный отрезок 1+X делим пополам с помощью циркуля и получаем точку O. Как это сделать, приводить здесь не буду, это задачка из школьного курса. Обозначим длину найденной половины как R.

Вокруг центра O, циркулем нарисуем дугу радиусом R.

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

Вычисление обратной величины длины

Для вычисления обратной величины длины используем нашу формулу в виде:

Решение очень похоже на нахождение квадрата величины, только a и h меняются местами.

Чертим прямую линию достаточной длины.

Откладываем на ней отрезок длины X.

От правого края отрезка X откладываем вверх перпендикуляр единичной длины 1.

Соединяем концы отрезков линией.

От верхнего конца отрезка X откладываем перпендикуляр к линии продолжения отрезка 1. Полученный отрезок и есть решение.

Выводы

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

Если величина X сильно отличается от единичного отрезка 1, ошибка вычисления может быть значительной. Но если применить масштабирование, то ошибку можно значительно уменьшить. Например, при захождении корня длины 20, его можно поделить на 16 (4 раза поделить пополам), а потом ответ умножить на 4 (4 раза отложить полученный отрезок).

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

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

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

• просмотр(n) = попытка;

• смайл(s) = победа;

• смайлрейт(w, от worth) = количество смайлов/количество просмотров;

• контент = то, у чего есть эти самые просмотры и смайлы.

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

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

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

Мы экспериментировали с четырьмя алгоритмами:

• UCB1.

• eGreedy.

• Thompson Sampling.

• Wilson.

Первые три из них упоминаются довольно часто, а четвёртый, по неведомой мне причине, довольно сильно обделён вниманием.

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

1. 1000 единиц контента с предопределённым эталонным смайлрейтом, распределённым нормально от 0.0 до 0.006.

2. 10 тыс. пользователей. У каждого есть история просмотренного контента, и повторно он не показывается.

3. 10 итераций, где каждый пользователь по очереди запрашивает 10 единиц контента (суммарно 1 млн просмотров).

4. Вес контента рассчитывается честно. Используется не эталонный смайлрейт, а реальный, зависящий от количества просмотров и смайлов конкретной единицы контента.

5. Смайлы раздаются относительно честно. Когда реальный смайлрейт опускается ниже эталонного есть 10% вероятность, что очередной пользователь, увидевший этот контент, поставит смайл.

UCB1

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

Где:

• s смайлы;

• n просмотры;

• С коэффициент;

• N суммарное количество просмотров по всему контенту.

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

Результат:

Плюсы:

• Прост в реализации.

• Не требователен к вычислительным ресурсам.

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

Минусы:

• Самая тяжёлая (относительно) часть расчётов происходит в момент запроса на сортировку, так как завязана на суммарное количество просмотров по всему контенту и на лету пришлось бы пересчитывать вообще всё.

  Лайфхак: при достаточно большом суммарном объёме просмотров можно не заморачиваться вычислением sqrt(ln(N)) для каждой единицы контента. Отклонения если и будут, то настолько мизерными, что никакого реального ущерба точности не принесут. Также можно закешировать значения корней для всех n в разумных пределах. По памяти будет недорого, а скорости даст очень хорошо.

• У этого алгоритма очень сильно слагаемое, ответственное за эксплорацию. И, как видно на графике, он в целом тянет наверх весь контент, довольно плотной группой.

Таким образом, учитывая постоянную ротацию, старый качественный контент сильно проигрывает новому контенту с малым количеством показов. Примем N=10000, C=1 и посмотрим, как ведут себя два разных контента.

Контент 1:

• просмотры = 500;

• смайлы = 50;

• вес = 0.1 + 0.14 = 0.24.

Контент 2:

• просмотры = 1000;

• смайлы = 100;

• вес = 0.1 + 0.09 = 0.19.

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

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

смайлрейт + SQRT(ln(10000)/500) > 0.19
смайлрейт > 0.05

Необходимо иметь всего 25 смайлов на 500 просмотров. То есть объективно в два раза хуже, зато свежак.

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

eGreedy

Алгоритм, лично у меня вызывающий добрую улыбку. Суть проста до безобразия: есть некое пороговое значение (эпсилон), мы кидаем кубик и, если он больше этого значения, то отдаём самый топ, отсортированный по смайлрейту. Если меньше, то включаем эксплорацию отдаём случайный контент.

Результат:

Плюсы:

• Очень прост в реализации.

• Очень дёшев по вычислительным ресурсам.

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

• Довольно быстро находит самый ценный контент и запускает его в космос.

Минусы:

• Алгоритм максималист, идеальный горец остаться должен только один! Будь в тебе хотя бы минимальный изъян будешь отправлен к аутсайдерам.

• Нет механизмов отсечения однозначно плохого контента.

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

Так как вес контента считается крайне примитивно, он не пессимизирует контент с большим количеством просмотров и даёт равные шансы как для проверенного 100/1000, так и для выскочки 1/10. Получается ситуация обратная UCB1 в проигрыше всегда оказывается потенциально хороший контент с меньшим количеством просмотров.

Контент_1=100/1000=0.1
Контент_2=10/100=0.1

А теперь выдадим каждому по одному дополнительному просмотру. Вроде мелочь, но:

Контент_1=100/1001=0.0999
Контент_2=10/101=0.0990

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

Wilson

Как и UCB1, является детерминированным алгоритмом.

Где:

• w смайлрейт;

• n просмотр;

• z константа, определяющая величину доверительного интервала;

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

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

Результат:

Плюсы:

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

• Даёт хорошее распределение. Качественно пессимизирует гарантированно плохой контент.

Минусы:

• Страшная формула. Этот недостаток можно чуть сгладить, умножив верхнюю и нижнюю часть уравнения на n.

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

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

Thompson Sampling

Самый замороченный по математике алгоритм. Если совсем простыми словами, то для каждого контента мы строим бета-распределение и берём его значение в случайной точке.

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

Результат:

Плюсы:

• Даёт хорошее распределение. Качественно пессимизирует гарантированно плохой контент.

• Чертовски красив в графическом представлении.

Минусы:

• Очень тяжёлый по вычислительным ресурсам.

• Сложный в реализации. И нет нормальных библиотек под Java.

• Алгоритм отлит в бетоне и не предполагает из коробки каких-либо настроек, влияющих на эксплорацию.

• Из-за рандома вес необходимо считать в момент сортировки.

Лайфхак: частично сложность можно нивелировать, заранее рассчитав бета-распределения для всех разумных значений пар smile/view.

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

Итого выходит: 5000500100(сэмплов)4(байт во float) = ~1ГБ памяти.

В принципе, жить можно, но такое.

Вместо выводов

Их не будет. :) Выбор подходящего именно вам алгоритма долгая и кропотливая работа аналитиков, море гипотез, А/Б-тестов, графиков бизнес-метрик и поиск компромиссов. Задача же разработчика всё это реализовать так, чтобы оно работало качественно, быстро и, желательно, не требовало постройки нового ЦОД-а. Надеюсь, эта статья кому-нибудь поможет с последними двумя пунктами.

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

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

Группируем товары

Для примера будем использовать вот такой список:

Творог Тушенка Бананы Фундук Фарш Хлеб Яйца Пиво Хлопья Яблоки Перец Кетчуп Котлеты Лимонад Мороженное

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

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

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

Я пользовался русскоязычными эмбеддингами Navec. Он содержит 500 тысяч слов, и имеет библиотеку, которая предоставляет удобный интерфейс в виде питоновского словаря. Слово используется в качестве ключа, по которому возвращается вектор из 300 значений.

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

{'Выпечка': ['Хлеб'],
'Завтраки': ['Хлопья'],
'Консервы': ['Тушенка'],
'Молоко/Сыр/Яйца': ['Творог', 'Яйца'],
'Мясо': ['Фарш', 'Котлеты'],
'Напитки': ['Пиво', 'Лимонад'],
'Овощи/Фрукты': ['Бананы', 'Яблоки'],
'Орехи': ['Фундук'],
'Приправы': ['Перец', 'Кетчуп']}

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

Строим оптимальный маршрут

Координаты из 2 и 3 столбцов преобразуем в матрицу смежности M так, что элемент M(i,j) содержит расстояние от отдела i до отдела j. В моем случае визуализация матрицы смежности выглядит так:

Поскольку товары уже сопоставлены с отделами, в матрицу попадают только отделы, в которые я планирую заходить. В данном случае 11 отделов.

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

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

Поясню на примере. Предположим A(5,1105) = 10. 1105 в переводе в двоичную систему будет 10001010001, это значит что мы посетили отделы 1, 5, 7 и 11, которые соответствуют единицам. Номер строки 5 - говорит о том, что последней мы посетили точку 5. Соответственно, маршрут минимальной длинны через точки 1,5,7 и 11 с конечным пунктом в точке 5 имеет длину 10.

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

К примеру, столбцы, содержащие 1 и 2 единицы уже заполнены, и мы хотим вычислить значение первой строки 15 столбца. Переводим 15 в двоичную систему получаем 1101. Значит мы ищем длину минимального маршрута через точки 1,2 и 4, оканчивающийся в точке 1.

Он равен минимальному из 2 значений, M(1,2) + A(2, 5) и M(1,4) + A(4, 5). Тут мы смотрим на 5 столбец, так как в двоичном представлении он имеет вид 0101 то есть предыдущее состояние перед искомым. Так заполняем все клетки. Клетки, соответствующие невозможному состоянию, заполняем бесконечными значениями.

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

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

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

Пишем телеграм-бота

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

В качестве хостинга я выбрал google cloud platform, там я создал виртуальную машину на Debian, и установил на нее:
- python3 на нем написан весь код,
- git чтобы было удобно накатывать изменения,
- mySQL там будут храниться списки покупок,
- tmux чтобы бот не выключался при закрытии ssh-сессии.
Для взаимодействия с api телеграма используется библиотека aiogram.

Бот понимает всего 3 команды: /del# - удаляет позицию # из списка /clear - очистить список /sort - показать отсортированный список

Если бот получает сообщение без команды, оно воспринимается как позиция для занесения в список.

Когда к боту подключается новый пользователь в базе данных создается таблица user_xxxxxxxx, где xxxxxxxx - id пользователя в телеграме, далее весь список, будет храниться в этой таблице.

Вот такой результат, спасибо, что дочитали до конца, ссылка на проект на github https://github.com/Megachell/ListOptimizerBot

Пусть в аквариуме живут рыбки двух цветов.

Начнем с визуализации. Зададим число рыбок n=100 и договоримся что каждая из них имеет случайный цвет color 0 или 1, а также находится в случайной точке (x,y). Т.е. x, y, и color это три вектора длины n, а третью (z-) координату мы не рассматриваем.

%matplotlib inlineimport numpy as npimport matplotlib.pyplot as pltn = 100x, y = np.random.rand(n), np.random.rand(n)color = np.random.randint(0, 2, n)plt.scatter(x, y, c=color)

Те же три вектора в Mathcad Express можно сгенерировать так:

Для векторов x,y используем генератор случайных чисел с равномерным распределением на отрезке (0, 1), а для вектора color биномиального распределения, моделирующего, в том числе, однократное подбрасывание монеты. В данном конкретном розыгрыше в Mathcad получилось 47 рыбок 1 и 100-47=53 рыбок нулевого цвета.

Теперь перейдем к главному вопросу: почему разные рыбки обладают цветом номер 0 или 1?

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

Совокупность генов каждого живого существа, называемая генотипом, определяет его внешний вид. В частности, генотип каждой рыбки определяет ее цвет. В простейшем случае, модель которого мы и будем дальше программировать, цвет рыбки (0 или 1) определяет один конкретный ген ("ген цвета"). Аналогичная ситуация (один ген определяет цвет) имела место в классических опытах Грегора Менделя, основоположника современной генетики, с растениями гороха, а в других случаях (например, для окраса собак-такс) на цвет отдельной особи влияет сочетание нескольких генов.

Как именно гены кодируют цвет? Прежде всего, ген цвета рыбки может существовать в двух вариантах, которые называются аллелями (я буду избегать этого и некоторых других важных для биолога терминов, чтобы сосредоточиться на информатике). В генетике их принято обозначать прописной и строчной буквами (например, А и а). Я буду чаще пользоваться цифрой А=0, а=1.

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

• АА или 00

• Аа (то же самое, что аА) или 01

• аа или 11

Если рыбка несет ген цвета АА или Аа, то она серая, а если аа желтая. Т.е. тип гена А полностью блокирует тип а, поэтому вариант А (0) называют доминатным, а а (1) рецессивным.

Давайте реализуем расчет цвета рыбки по ее генетическому коду, который для i-й рыбки будем описывать вектором из двух компонентов, а генетический состав всей популяции соответственно, матрицей, которую назовем Аа. Пусть у нас есть три рыбки, каждая из которых с равной вероятностью несет генетический код 00, 10, 01 или 11. В первых трех случаях цвет рыбки будет серым, а в четвертом желтым.

n = 3Aa = np.zeros((n,2))color = np.zeros(n)for i in range(n):  Aa[i,0] = np.random.randint(0, 2, 1)  Aa[i,1] = np.random.randint(0, 2, 1)  color[i] = Aa[i,0] * Aa[i,1]print (Aa)print (color)

Результат работы программы вы видите на картинке:

Очевидно, при такой модели, если рыбок будет много, то цветных будет около 25%. Аналогичные вычисления в Mathcad для популяции из n=1000 рыбок приведены на следующем рисунке.

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

Все мы понимаем, что рекурсивное вычисление чисел Фибоначчи крайне неэффективно. Многим людям наверняка хотелось проверить, где пределы (не)эффективности, но не доходили руки, не хватало времени. Специально к старту нового потока курса 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-го члена последовательности Фибоначчи, а это именно то, что мы хотим сделать; эта формула названа в честь открывшего её французского математика Жака Филиппа Мари Бине. Вот она:

Вы можете заметить греческую букву 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 потребуется немногим более года. Но можно и быстрее на нашем курсе студенты не привязаны к программе и скорость их прогресса зависит от них самих.

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

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering

В эфире снова Радио SQL, здравствуйте, согалактчики!

Сегодня у нас обещанный разбор задачи на поиск последней цены. Прошёл как раз земляной месяц. У вас же 60 солов в месяце, да? Я немного путаюсь во всех этих ваших неметрических то 12-ти, то 60-тиричных системах времени. Впрочем, перейдём к делу.

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

with price(stock_id, prod_id, start_date, kind, price1, cost1, bonus1) as (values (1,1,to_date('2000-01-01','YYYY-MM-DD'),'R',100.0,32.12,6.49),       (1,1,'2000-01-02','P', 80.0, 0,   0),       (1,1,'2000-01-03','P', 70.0, 0,   0),       (1,1,'2000-01-04','R',110.0,33.48,6.19),       (1,1,'2000-01-05','P', 90.0, 0,   0),       (1,1,'2000-01-06','R',120.0,41.22,6.19),       (1,1,'2000-01-07','P', 80.0, 0,   0),       (1,1,'2000-01-08','P', 90.0, 0,   0),       (1,1,'2000-01-09','R', 93.0,36.87,6.49),       (1,1,'2000-01-10','R', 94.0,36.85,6.99),       (1,2,'2000-01-01','R',101.0,52.06,9.00),       (1,2,'2000-01-02','P', 81.0, 0,   0),       (1,2,'2000-01-03','P', 71.0, 0,   0),       (1,3,'2000-01-04','R',111.0,64.96,4.50),       (1,3,'2000-01-05','P', 92.0, 0,   0),       (1,3,'2000-01-06','R',122.0,66.83,4.60),       (1,3,'2000-01-07','P', 82.0, 0,   0),       (1,3,'2000-01-08','P', 92.0, 0,   0))select ...

 stock_id | prod_id | start_date | kind | price1 | cost1 | bonus1 | price1x ----------+---------+------------+------+--------+-------+--------+---------        1 |       1 | 2000-01-01 | R    |  100.0 | 32.12 |   6.49 |   100.0        1 |       1 | 2000-01-02 | P    |   80.0 |     0 |      0 |   100.0        1 |       1 | 2000-01-03 | P    |   70.0 |     0 |      0 |   100.0        1 |       1 | 2000-01-04 | R    |  110.0 | 33.48 |   6.19 |   110.0        1 |       1 | 2000-01-05 | P    |   90.0 |     0 |      0 |   110.0        1 |       1 | 2000-01-06 | R    |  120.0 | 41.22 |   6.19 |   120.0        1 |       1 | 2000-01-07 | P    |   80.0 |     0 |      0 |   120.0        1 |       1 | 2000-01-08 | P    |   90.0 |     0 |      0 |   120.0        ...

Задачу эту можно решать разными способами. Начнём с самого простого:

Первый подход

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

select * -- выбрать все поля из источника данных       -- а тут подзапрос, выбирающий нужную цену     , (select price1          from price sub         where sub.stock_id = p.stock_id -- те же склад           and sub.prod_id  = p.prod_id  -- и товар,           and sub.kind = 'R'            -- оставим только настоящие цены           and sub.start_date <= p.start_date  -- с датой более ранней или такой же,         order by start_date desc        -- отсортируем в порядке последние цены раньше         limit 1                         -- и возьмём только первую строку       ) as price1x  from price p;

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

Отлично, мы сделали это! Запускаем! Можно расслабиться, прыснуть себе чего-нибудь зободробительного в жвалы, сделать первый (и самый вкусный) гулп... И пока запрос работает, давайте немного отвлечёмся и поразмышляем об его эффективности.

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

А ну-ка запустим в соседнем окошке select count(*) from price и внимательно посмотрим как на количество записей, так и на время исполнения. Потому что именно эти два числа нужно будет умножить друг на друга, чтобы прикинуть общее время выполнения запроса. Наш запрос будет работать хоть сколько-нибудь обозримое время, только если количество записей не будет превышать десятков или сотен, ну максимум тысяч записей. Так что полюбовались на количество записей, и давай, тяни свои ложноножки (или ложноручки, что там у тебя) к консоли и прерывай запрос, пока не прилетели админы, чтобы убедительно объяснить на пальцах, что надо и что не надо делать на боевом сервере.

Подход второй

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

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

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

Так что оставим этот способ напоследок, а сперва попробуем способ получше, и это...

Подход третий

Что там у нас сделать-то надо было? Сгруппировать и для каждой группы выбрать значение?.. Ба, да сюда же прямо просятся аналитические функции! Они как раз предназначены для подобных задач, когда нужно что-то сгруппировать и выбрать для каждой группы. Если при этом нужно оставить только значения для каждой группы, то используются аналитические функции, а если нужно сохранить весь исходный набор данных то оконные.

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

select *     , agg_func(...) over (...) -- тут нужно будет определить окно и найти подходящую функцию  from price

Казалось бы всё просто. Функция будет из тех, которые возвращают одно из значений в группе, это first_value() или lag() или что-то подобное. А вот с определением окна нужно немного помудрить. Оконные функции позволяют определять окно, указав группировку и сортировку. Понятно, что в определении окна будет partition by stock_id, prod_id и что-то надо добавить, чтобы ближайшая предыдущая строчка с реальной ценой встала на фиксированное место в этой группе. Если это не получается сделать в лоб (как, например, если бы нам надо было выбрать просто самую первую или минимальную цену), то обычно помогает такой приём, когда определяют специальное вычислимое поле и по нему делают или группировку, или сортировку. Навскидку пишем case when kind='R' then, потому что от поля kind у нас точно есть зависимость, и задумываемся... Мнэ...

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

Решение постепенно нашлось, и вот какой приём при этом был применён. Получилась двухходовка. На первом этапе формируем специальное вычислимое поле, по которому на втором этапе уже выбираем нужные значения. Поле (назовём его уровнем цены) формируем так: суммируется нарастающим итогом для каждого склада и товара в порядке даты начала действия следующее: единица для строк с kind='R' и ноль для всего остального. Получается как раз, что уровень цены перещёлкивается на следующий, как только мы встречаем реальную цену:

select *     , sum(case when kind='R' then 1 else 0 end) -- сумма нарастающим итогом       over(partition by stock_id, prod_id       -- в разрезе складов и товаров            order by start_date                  -- порядок важен!            rows between unbounded preceding and current row) as lvl -- нам нужно именно до CURRENT ROW  from price

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

select *     , first_value(price1) over (partition by prod_id, stock_id, lvl                                     order by start_date) as price1x  from (select ...)

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

Итого, вот оно решение:

select p.*     , first_value(price1) over (partition by prod_id, stock_id, lvl                                     order by start_date) as price1x  from (select *             , sum(case when kind='R' then 1 else 0 end)               over(partition by stock_id, prod_id order by start_date                    rows between unbounded preceding and current row) as lvl  from price) p

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

select *     , first_value(price1) over w as price1x     , first_value(cost1)  over w as cost1x  from (select *             , sum(case when kind='R' then 1 else 0 end)               over(partition by stock_id, prod_id order by start_date                 rows between unbounded preceding and current row) as lvl          from price) pwindow w as (partition by prod_id, stock_id, lvl order by start_date)

Вот собственно и всё, на этом можно закончить, реализация второго подхода не понадобилась.

Выводы

1. Во время составления SQL-запроса имеет смысл думать про эффективность его работы.

2. Использовать оконные функции отличная идея.

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

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

Разбор решений, приведённых в комментариях

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

Так или иначе я насчитал 11 разных вариантов решения от 10 представителей. Вообще запросов было приведено больше, но часто следующий SQL-запрос в цепочке комментариев был развитием или исправлением предыдущего. Так что количество сильно зависит от того, как считать. Пройдёмся по хронологии.

Статья с условием задачи была опубликована 16 марта 2021 в 17:12. Первое решение от @nice17 16 марта 2021 в 17:34 было предложено уже через 22 минуты после публикации статьи (22 минуты, Карл! и ещё же надо было хоть по диагонали прочитать условие). Решение было неверным, но подход к решению явно был уже в нужном направлении. Чуть позже автор довёл его до правильного. А первое более-менее работающее решение (от @ZMB138 16 марта 2021 в 19:07) появилось меньше чем через два часа(!) после публикации, это была реализация подхода 2.

Первое решение в третьем подходе от @Kilor появилось ещё спустя полчаса 16 марта 2021 в 19:39. Автор применил хитрый ход, использовав функцию array_agg(), которая допускает использование FILTER в определении окна, что позволило отфильтровать только записи с реальными ценами и избежать рассмотренной мной двухходовости. Также продемонстрирован интересный ход, что вся найденная для сопоставления строка таблицы упаковывалась в JSON, из которого дальше выбиралось нужное поле. Или все нужные поля. Не очень универсально в плане разных диалектов SQL, но изящно. Последняя версия запроса от 17 марта 2021 в 10:18 уже без упаковки/распаковки в JSON получилась компактной и эффективной.

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

Аналогичный подход использовал @AngelloreA в запросе от 16 марта 2021 в 22:30. Сопоставляемая строка с реальными стоимостями упаковывалась правда не в JSON, а просто в текст, что потенциально чревато проблемами при распаковке (надо бы явно указать форматы), но это работает и тоже в один проход, то есть получилась реализация подхода 3.

@viras777 16 марта 2021 в 23:07 привёл необычное решение, где весьма остроумно для генерации уровней цены используется последовательность. В целом, как мне кажется, использовать последовательность для такого случая избыточно (да и Оккам не велел), плюс побочных эффектов в программировании обычно стараются избегать, но тем не менее оно работает.

@AlexKadetov уже 16 марта 2021 к 23:10 получил по сути такое же решение в подходе 3, к которому пришёл и я, пусть даже и с некоторыми огрехами в реализации. Вообще огрехи в реализации были много у кого, я старался не придираться, потому что в реальной жизни конечно всякий запрос ещё какое-то время доводится до кондиции, уточняется его работа и всё подобное вылавливается и исправляется.

Ночью @qvan 17 марта 2021 в 01:39 привёл несколько тяжеловесное, но рабочее решение в подходе 2. Утром @xxxcoltxxx 17 марта 2021 в 09:13 привёл более явное и ясное решение в реализации подхода 2. Чуть позже @jayrumi 17 марта 2021 в 13:11 тоже опубликовал своё пусть и несколько тяжеловесное, но работающее решение тоже в подходе 2.

Дальше опять вернулся @Kilor и 17 марта 2021 в 14:30 привёл пару красивых решений в подходе 2, продемонстрировав виртуозную технику JOIN-ов наборов данных. Ближе к вечеру @Miha_S7 17 марта 2021 в 18:19 привёл своё решение в подходе 3, повторяющее полученное мной в первой части статьи.

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

Итого, из интересного отмечу скорость, с которой тема была раскрыта со всех сторон, включая диалекты дружественных СУБД. Плюшкополучателем был избран @Kilor, как автор самого первого однопроходного решения (в подходе 3), а также за проявленную широту охвата техники владения SQL (использование оконных функций, JSON, FILTER, JOIN-ы) и ясную по форме реализацию с использованием всего перечисленного. С ним я уже связался. Специально отмечу самое первое работающее решение от @ZMB138, оригинальность и неожиданность использования последовательностей от @viras777, а также эталонное на мой взгляд решение от @AlexKadetov.

И отдельное большое спасибо всем, кто принял участие в обсуждении и поделился своими решениями.

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

Как входная последовательность попадает в модуль внимания

Модуль внимания присутствует в каждом энкодере внутри стека каждого энкодера, а также внутри стека каждого декодера. Сначала внимательно посмотрим на энкодер.

Для примера предположим, что мы работаем над задачей перевода с английского на испанский, где исходная последовательность слов The ball is blue, а целевая последовательность La bola es azul.

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

Внутри модуля внимания последовательность векторного представления проходит через три линейных слоя, создающих три отдельные матрицы запроса (Query), ключа (Key) и значения (Value). Именно эти три матрицы используются для вычисления оценки внимания [прим. перев. оценка определяет, сколько внимания нужно уделить другим частям входного предложения, когда мы кодируем слово в определённой позиции]. Важно помнить, что каждая "строка" этих матриц соответствует одному слову исходной последовательности.

Каждая входная строка это слово из последовательности

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

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

Каждое слово проходит серию обучаемых преобразований (трансформаций)

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

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

Оценка внимания это скалярное произведение матрицы ключа и матрицы запроса слов

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

Как видно из формулы, первый шаг в рамках модуля внимания умножение матрицы, то есть скалярное произведение между матрицей Query (Q) и транспонированием матрицы ключа Key (K). Посмотрите, что происходит с каждым словом. Итог промежуточная матрица (назовём её факторной матрицей [матрицей множителей]), где каждая ячейка это результат матричного умножения двух слов.

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

Оценка внимания скалярное произведение между запросом-ключом и значением слов

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

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

Какова роль слов запроса, ключа и значения?

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

Например, для предложения The ball is blue строка для слова blue будет содержать оценку внимания для слова blue с каждым вторым словом. Здесь blue это слово запроса, а другие слова ключ/значение. Выполняются и другие операции, такие как деление и softmax, но мы можем проигнорировать их в этой статье. Они просто изменяют числовые значения в матрицах, но не влияют на положение каждой строки слов в ней. Они также не предполагают никаких взаимодействий между словами.

Скалярное произведение сообщает нам о сходстве слов

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

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

Для получения скалярного произведения двух векторов мы умножаем пары чисел, а затем суммируем их.

• Если два парных числа (например, a и d выше) оба положительны или оба отрицательны, произведение положительно. Произведение увеличит итоговую сумму.

• Если одно число положительное, а другое отрицательное, произведение будет отрицательным. Произведение уменьшит итоговую сумму.

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

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

Как трансформер изучает релевантность между словами?

Скалярное произведение также применимо к оценке внимания. Если векторы для двух слов более выровнены, оценка внимания будет выше. Итак, какого поведения мы хотим от трансформера? Мы хотим, чтобы оценка внимания была высокой для двух релевантных друг другу слов в предложении. И мы хотим, чтобы оценка двух слов, не связанных друг с другом, была низкой.

Например, в предложении The black cat drank the milk слово milk очень релевантно к drank, возможно, немного менее релевантно для cat, и нерелевантно к black. Мы хотим, чтобы milk и drink давали высокую оценку внимания, чтобы milk и cat давали немного более низкую оценку, а для milk и black незначительную. Мы хотим, чтобы модель научилась воспроизводить этот результат. Чтобы достичь воспроизводимости, векторы слов milk и drank должны быть выровнены. Векторы milk и cat несколько разойдутся. А для milk и black они будут совершенно разными.

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

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

Следовательно, векторные представления слов milk и drank будут очень согласованными и обеспечат высокую оценку внимания. Они будут несколько отличаться для milk и cat, производить немного более низкую оценку и будут совершенно разными в случае milk и black: оценка внимания будет низкой вот лежащий в основе модуля внимания принцип.

Итак, как же работает трансформер?

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

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

Самовнимание энкодера в трансформере

Внимание используется в трансформере в трёх местах:

• Самовнимание в энкодере исходная последовательность обращает внимание на себя.

• Самовнимание в декодере целевая последовательность обращает внимание на себя.

• Энкодер-декодер-внимание в декодере целевая последовательность обращает внимание на исходную последовательность.

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

Декодер самовнимания в трансформере

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

В декодере самовнимания мы вычисляем релевантность каждого слова в целевом предложении каждому другому слову в целевом предложении.

Энкодер-декодер модуля внимания в трансформере

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

Заключение

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

Здесь мы видим, что за сложными идеями скрываются простые решения. Более того, есть ощутимая вероятность того, что вскоре понимание внутренних механизмов глубокого обучения станет второй грамотностью, как сегодня второй грамотностью стало знание ПК в целом и если вы хотите углубиться в область глубокого и машинного обучения, получить полное представление о современном ИИ, вы можете присмотреться к нашему курсу Machine Learning иDeep Learning, партнёром которого является компания NVIDIA.

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

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering