![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
petropavelПо ссылке из ЖЖ наткнулся на задачку, одну из каверзных задачек, что дают на собеседовании в гугле
( http://f010n3-m.ath.cx/?p=310 вот тут вот, из чьего жж я туда попал - не помню ).
Формулировка задачи: 15. How many piano tuners are there in the entire world?
(Сколько настройщиков пианино живёт во всём мире?)
Я вспомнил, что видел где-то обсуждение подобной задачи, только там спрашивалось, кажется, сколько бензоколонок есть в Лос-Анджелесе.
Я накропал товарищу в блог своё видение этой задачи, и благополучно забыл адрес блога.
С утра сегодня решил поискать, что же мне написали, погуглил, и наткнулся прямо на дословную формулировку этой самой задачи в Википедии. Оказывается, это задача Ферми, и этот класс задач призван выявить у человека способность делать обоснованные количественные оценки вещей, которые невозможно точно подсчитать или вывести из начальных условий.
Вот статья в википедии:
http://en.wikipedia.org/wiki/Fermi_problem
Я сказал, что, возможно, даже смогупритянуть за уши предположить, нафига нам всё это в зоопарке какое отношение подобный тип задач имеет к работе в Гугле,
Начнём потихоньку.
Предположим, что у нас есть программа, которая записывает обращения клиентов в нашу организацию, в примерно такую таблицу:
У нас есть индексы по колонкам "дата обращения" и "Пол".
Задача: отобрать информацию по всем женщинам, обратившимся к нам в прошлом месяце.
Всю работу с таблицей делает какой-то гипотетический движок, наподобие сервера SQL.
Движок у нас тупой, но исполнительный. У него есть 2 варианта действий:
1) отобрать из таблицы всех женщин (использовав индекс по Gender, из полученной выборки отобрать тех, кто пришёл в прошлом месяце (индекс по date_o)
2) отобрать из таблицы всех, кто пришёл в прошлом месяце (индекс по date_o), из них отобрать всех женщин (индекс по Gender.
Математически способы 1) и 2) эквивалентны, оба дадут правильный результат.
Разница между ними будет только в объёме проделанной работы.
Понятно, что в типичном случае выборка всех женщин (gender) даст нам в результате примерно половину строк из таблицы.
Если организация работает, скажем, 1 год, то выборка всех клиентов за 1 месяц даст нам 1/12 часть строк из таблицы; если больше года - соответственно ещё меньшую часть.
Понятно, что для минимизации тупого перебора нужно на первом шаге отсеять максимальное количество ненужной информации.
Чтобы движок мог делать сколь-нибудь обоснованный выбор между 1) и 2), нам нужно снабдить его некоторой дополнительной информацией, как то:
- количеством строк в таблице
- количеством различающихся значений в колонке (или ключей в индексе) - это называется термином "кардинальность" (cardinality). Для поля gender кардинальность будет равна 2, для поля "дата" - будет примерно равна количеству дней, прожитых системой.
- возможно, ещё какие-то параметры статистического толка.
Тогда можно будет усложнить наш движок, с тем, чтобы он анализировал трудоёмкость выполнения того или иного плана, и выбирал наиболее "дешевый" из возможных.
В реальных СУБД нечто подобное действительно проделывается, подсчёт таких параметров называется "сбор статистики", и обычно выполняется каким-нибудь автоматизированным скриптом раз в неделю, в ночь на воскресенье, ну или как-то так.
Важный момент - для того, чтобы это работало, статистика не обязана быть абсолютно точной. Неважно, что среди клиентов было 51.3% мужчин и 48.7% женщин, или в первую половину января не пришло ни одного клиента, потому что офис тупо не работал. Более того, собрать достоверную статистику по типичного размера базе бывает очень долго, и используется режим Estimate statistics, когда движок анализирует 10% от таблицы или индекса. и экстраполирует статистику на всю таблицу.
Так вот, "сколько настройщиков пианино в мире" - этот вопрос будет иметь смысл, если мы зададимся целью найти, например, настройщика-китайца, живущего в Москве. Что мы должны будем просмотреть в первую очередь - список настройщиков в мире, или список китайцев в Москве? Если оба списка у нас есть, и правильный результат мы получим в обоих случаях :)
( http://f010n3-m.ath.cx/?p=310 вот тут вот, из чьего жж я туда попал - не помню ).
Формулировка задачи: 15. How many piano tuners are there in the entire world?
(Сколько настройщиков пианино живёт во всём мире?)
Я вспомнил, что видел где-то обсуждение подобной задачи, только там спрашивалось, кажется, сколько бензоколонок есть в Лос-Анджелесе.
Я накропал товарищу в блог своё видение этой задачи, и благополучно забыл адрес блога.
С утра сегодня решил поискать, что же мне написали, погуглил, и наткнулся прямо на дословную формулировку этой самой задачи в Википедии. Оказывается, это задача Ферми, и этот класс задач призван выявить у человека способность делать обоснованные количественные оценки вещей, которые невозможно точно подсчитать или вывести из начальных условий.
Вот статья в википедии:
http://en.wikipedia.org/wiki/Fermi_problem
Я сказал, что, возможно, даже смогу
Начнём потихоньку.
Предположим, что у нас есть программа, которая записывает обращения клиентов в нашу организацию, в примерно такую таблицу:
+----------------+-----+-----------+-------------------------+ | дата обращения | Имя | Пол (м/ж) | какая-то доп.информация | +----------------+-----+-----------+-------------------------+ | date_o |Name | Gender | other_info | +----------------+-----+-----------+-------------------------+
У нас есть индексы по колонкам "дата обращения" и "Пол".
Задача: отобрать информацию по всем женщинам, обратившимся к нам в прошлом месяце.
Всю работу с таблицей делает какой-то гипотетический движок, наподобие сервера SQL.
Движок у нас тупой, но исполнительный. У него есть 2 варианта действий:
1) отобрать из таблицы всех женщин (использовав индекс по Gender, из полученной выборки отобрать тех, кто пришёл в прошлом месяце (индекс по date_o)
2) отобрать из таблицы всех, кто пришёл в прошлом месяце (индекс по date_o), из них отобрать всех женщин (индекс по Gender.
Математически способы 1) и 2) эквивалентны, оба дадут правильный результат.
Разница между ними будет только в объёме проделанной работы.
Понятно, что в типичном случае выборка всех женщин (gender) даст нам в результате примерно половину строк из таблицы.
Если организация работает, скажем, 1 год, то выборка всех клиентов за 1 месяц даст нам 1/12 часть строк из таблицы; если больше года - соответственно ещё меньшую часть.
Понятно, что для минимизации тупого перебора нужно на первом шаге отсеять максимальное количество ненужной информации.
Чтобы движок мог делать сколь-нибудь обоснованный выбор между 1) и 2), нам нужно снабдить его некоторой дополнительной информацией, как то:
- количеством строк в таблице
- количеством различающихся значений в колонке (или ключей в индексе) - это называется термином "кардинальность" (cardinality). Для поля gender кардинальность будет равна 2, для поля "дата" - будет примерно равна количеству дней, прожитых системой.
- возможно, ещё какие-то параметры статистического толка.
Тогда можно будет усложнить наш движок, с тем, чтобы он анализировал трудоёмкость выполнения того или иного плана, и выбирал наиболее "дешевый" из возможных.
В реальных СУБД нечто подобное действительно проделывается, подсчёт таких параметров называется "сбор статистики", и обычно выполняется каким-нибудь автоматизированным скриптом раз в неделю, в ночь на воскресенье, ну или как-то так.
Важный момент - для того, чтобы это работало, статистика не обязана быть абсолютно точной. Неважно, что среди клиентов было 51.3% мужчин и 48.7% женщин, или в первую половину января не пришло ни одного клиента, потому что офис тупо не работал. Более того, собрать достоверную статистику по типичного размера базе бывает очень долго, и используется режим Estimate statistics, когда движок анализирует 10% от таблицы или индекса. и экстраполирует статистику на всю таблицу.
Так вот, "сколько настройщиков пианино в мире" - этот вопрос будет иметь смысл, если мы зададимся целью найти, например, настройщика-китайца, живущего в Москве. Что мы должны будем просмотреть в первую очередь - список настройщиков в мире, или список китайцев в Москве? Если оба списка у нас есть, и правильный результат мы получим в обоих случаях :)
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2009-09-10 06:38 am (UTC)То есть - ты получил формулу, прежде чем скакать от радости, ты прикинь, какая получилась размерность. Если надо было найти массу, должны получиться килограммы (граммы, фунты, пуды), но никак не секунды, и не кубические литры на одного квадратного человека.
Сошлась размерность - посчитай быстренько порядок величины, все эти "десять в N-й степени", это быстро. Если получилось что-то неправдоподобное, проверь, какую-нибудь гравитационную постоянную, или число Авогадро, или ещё что-то такое, возможно, забыл.
То есть, навык-то в любом случае полезный :-)
no subject
Date: 2009-09-10 07:00 am (UTC)Дело в том, что в твоих прикидках есть, имхо, два существенных упущения. Ты учел только домашние пианино. А эти звери еще (и как правило!) живут в детсадах, школах, вузах, клубах, домах и дворцах культуры, театрах; в большом количестве - в музыкальных школах, музучилищах и консерваториях.
Далее: необходимость настройки раз в два года - это если пианино стоит и никто его не двигает. А если переезд - надо настраивать, даже если предыдущая настройка производилась месяца два назад. Ну и периодичность настройки, так сказать, общественных пианинов существенно выше, чем у домашних. До такой степени, что в училищах и консерваториях есть, кажется, даже отдельные ставки настройщиков. А домашние инструменты для них - так, подработка.
Ну и, наконец, еще важный фактор. Мой приятель подрабатывает настройщиком, но вообще-то он музыкант, это его основная работа. Я не знаю, какое количество пианино он настраивает в месяц. Может, и одно или два. При этом все равно он настройщик.
no subject
Date: 2009-09-10 07:17 am (UTC)С другой стороны, никто же не сможет это посчитать точно, тем более, с учётом того, что есть пианисты-настройщики по совместительству, итд.
Вон в Википедии написано, что сам Ферми оценил мощность атомной бомбы, по расстоянию, на которое улетел лист бумаги. Он сказал - 10 килотонн, после всех измерений и расчётов учёные сошлись на 20 килотоннах.
no subject
Date: 2009-09-10 07:40 am (UTC)он говорил, что это всего лишь показывает умение человека рассуждать.
если его такой вопрос ставит в тупик, это плохо.
no subject
Date: 2009-09-10 07:48 am (UTC)поумничатьпорассуждать :-)no subject
Date: 2009-09-10 07:58 am (UTC)Просто я некоторое время работаю как раз с оракловыми запросами, и мне показалось забавным притянуть за уши этих настройщиков именно к оракловому Cost-Based Optimizer :-) Чем, собственно, и поделился.
no subject
Date: 2009-12-13 01:22 pm (UTC)Что касается Ферми, кстати, на меня сильное впечатление произвел такой факт его биографии: когда ему было 13 то ли 14 он спросил у какого-то инженера, не помню имени, какой-то, кажется, друг семьи, правда ли что есть раздел геометрии где изучаются свойства фигур без применения понятия меры (то есть длины). Тот ответил что да, имея в виду проективную геометрию. В ответ Ферми немедленно спросил как в таком случае возможно практическое инженерное применение этих свойств.
Это характерно для всего стиля его дальнейшей работы. Он был, видимо, последним физиком такого калибра, который равно владел и теорией и экспериментом и четко видел между ними связь. Это не так просто, как может показаться со стороны - увидеть в реальном эксперименте где сработала реальная физика. Для этого и нужно умение делать оценки на пальцах и сразу отбрасывать весь "шум".
no subject
Date: 2009-12-13 03:05 pm (UTC)no subject
Date: 2009-12-13 09:31 pm (UTC)