Как стать автором
Поиск
Написать публикацию
Обновить

Комментарии 73

Спасибо за перевод!
Эта статья подводит нас к очень интересной проблеме: американцы привыкли работать с несистемными размерами, поэтому для них естественно использовать цепочку преобразований для перевода попугаев в футы. Первое же, что приходит в голову человеку, знакомому с СИ — перевести все единицы в СИ и назад. Никакого графа, поиска в глубину и т.д. — все «общеизвестные преобразования» должны быть заранее вбиты в таблицу с коэффициентами вроде «1 фут = 0.3048 метра» и все вычисления должны происходить через метры. Если у нас нет таблицы таких «общеизвестные преобразований» в метры и программа стартует с пустой таблицей, то первым делом ее надо «обучить», наполнив эту таблицу. Если данные для обучения выданы в произвольном порядке, то их надо отсортировать так, чтобы они всегда опирались на уже существующие преобразования.
В любом случае, финальное вычисление после этого будет делаться в два умножения. Я просто не могу себе представить как у автора получился «интуитивный подход», это для нас совершенно неестественно.
Всего голосов 45: ↑44 и ↓1+43

Таблица преобразований — это один из входных параметров задачи и она фиксирована. То есть оперировать можно только с этими коэффициентами и там далеко не для всех пар величин есть коэффициент.


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

Всего голосов 2: ↑1 и ↓10
Но задача отлично решается при наличии полной таблицы преобразований в метры. Значит перед работой надо неполную таблицу сделать полной, это подготовительная операция. А само преобразование уже потом делается в два умножения. Конечно, мы можем где-то потерять точность из-за количества операций с плавающей запятой, но это тоже решаемо, н-р, рациональными дробями.
Всего голосов 16: ↑16 и ↓0+16
Хотел бы я посмотреть, как ваша реализация рациональных дробей будет работать со значениями навроде 1.0737e−17
Комментарий пока не оценивали0

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

Всего голосов 8: ↑7 и ↓1+6
При чём тут double? Nomad1 предложил вместо плавающей запятой использовать рациональные дроби.

Пример потери точности при умножении double есть прямо в тексте статьи.
Комментарий пока не оценивали0
Во-первых, кустарной реализации на собеседовании (да и в коммерческой разработке) быть не должно, потому что рациональные дроби не делал только ленивый. Если говорить о .Net, то разумно использовать, н-р, Rationals.Net, где числитель и знаменатель задаются BigInteger — оберткой вокруг массива чисел, без ограничений по размеру и порядку. Для C++ берем cpp_rational с такими же свойствами.
Во-вторых, дробь с e-17 это совсем не много, задается 64-битными числами, пусть и близко к пределу.
В-третьих, при некотором желании (и желании сделать пару велосипедов) можно использовать представление с мантиссой и экспонентой (даже тот же double) и в рациональных дробях. Ошибка будет накапливаться только при очень большой разнице между исходной и результирующей величиной (ангстремы в парсеки).
Всего голосов 2: ↑2 и ↓0+2
Вот как раз на собеседовании в гугл от вас ожидают реализовать то, что в коммерческой разработке принято брать готовым, не разбираясь, что внутри.

А то я тоже у них на какой-то вопрос по поводу потери точности ляпнул «тогда возьмём длинную арифметику», после чего до конца часа писал на доске реализацию умножения десятичных дробей произвольной длины, да так и потонул в обработке разных граничных случаев.
Комментарий пока не оценивали0
Ну тут я вам не отвечу, я у гугла не был на собеседовании :)
Здравый смысл говорит о том, что рациональные числа в boost появились в 1999году. Через 20 лет реализовывать их заново это, кхм, странно. Ну может только чтобы впечатлить собеседника.
Всего голосов 1: ↑1 и ↓0+1

Откуда берётся эта потеря точности? double это пара (m, e) = m*2**e, где m — 10 бит мантиссы, и e — 52 бита экспоненты. У мантиссы есть погрешность d(m) >= 2**-52. У экспоненты погрешности нет, за исключением случая когда 10 бит не хватает (но это бы означало, что мы оперируем с числами порядка 2**1024). Когда мы умножаем два числа, то получаем m1*m2*2*(e1+e2). Погрешность произведения здесь d(m1)+d(m2). Тоже самое при делении. Короче говоря, каждое умножение снижает точность на один бит, а всего битов 52. Допустим нам нужно 6 десятичных знаков точности как в этом примере. Это 20 бит. Значит мы можем спокойно потерять 32 бита точности. Чтобы потреять 32 бита точности нам нужен граф в котором кратчайшее расстояние между двумя вершинами равно 32. Нехилый такой граф. При желании конечно можно выдумать нереальный пример вроде "первести валюту WLP в индекс RKP" и единственная цепочка преобразований идёт через мутные офшорные акции коих 35.

Всего голосов 2: ↑2 и ↓0+2
Вы заметили, как Google показывает коэффициент конверсии 1.0739e-17, но мой расчёт вручную даёт 1.0737e-17?
Комментарий пока не оценивали0

Ну и какой вывод? Считая вручную мы обычно не записываем на бумгае 15 знаков после запятой, а лишь 5-6 как в примере. 4 преобразвания с такой потерей точности и вот у нас ошибка в 5 знаке.

Всего голосов 5: ↑5 и ↓0+5
Я просто не могу себе представить как у автора получился «интуитивный подход», это для нас совершенно неестественно.

У континентальной Европы, Англии/США и Японии разные инженерные школы.

Вопрос культурных различий в этом контексте ничуть не хуже, чем умение применять алгоритмы на графах. Люди просто думают одни и те же мысли совершенно по-разному.
Всего голосов 1: ↑1 и ↓0+1

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

Комментарий пока не оценивали0
Алгоритм все так же применяется, просто на другой стадии — на подготовке данных. Т.е. наша инженерная школа подразумевает очень простое и точное решение этой задачи — «видишь не-СИ значение, приведи его к СИ». В данной формулировке задача решается в два умножения. То, чего хочет автор — решение с помощью графа — нам кажется нелогичным, но при этом нормально такой подход использовать для разворчивания намайненных данных в таблицу, т.е. на подготовительном этапе. Тут уже можно проявить фантазию в поиске наименьшего количества конверсий, проставлении коэффициентов достоверности и т.д. Но конкретно представители нашей школы на этом собеседовании будут ошеломлены и обескуражены, ведь это уровень средней школы.
Всего голосов 2: ↑2 и ↓0+2

Это и есть финальный ответ, на 5+ (в части 4). Обходим граф один раз, строим таблицу с эталонной величиной и потом переводим туда-обратно все что надо.


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


Это решение, да, очевиднее тем, кто работает с единицами си. Но тем, кто футы в мили переводит, гораздо инуитивнее делать переводы в несколько этапов, потому что 1231760 запомнить проще, чем 12, 36, 63360 и другие кривые числа. Именно поэтому входные данные такие.

Всего голосов 2: ↑2 и ↓0+2
Отсюда вытекает свойство «кратчайший путь / наименьшее число умножений»

BFS это метод перебора узлов графа, как и DFS у него нет свойства находить кратчайший путь.

Всего голосов 6: ↑1 и ↓5-4

Оказывается у BFS есть такое свойство.

Всего голосов 4: ↑4 и ↓0+4

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

Комментарий пока не оценивали0

Отчасти, вы правы. Но только если рассматривать значение узла как путь. Автор имел ввиду минимальное количество узлов = умножений. То-есть в данной задаче длина всех узлов равна.

Комментарий пока не оценивали0

В невзвешенном графе (веса всех рёбер равны единица), BFS — это алгоритм поиска кратчайшего пути.

Комментарий пока не оценивали0
НЛО прилетело и опубликовало эту надпись здесь
Кажется это решается с помошью dimensional table. Надо только граф ориентировать в таблицу с расстояниями.
Комментарий пока не оценивали0
Я подозреваю, что на собеседовании валились люди, получившие образование в метрической системе. У них когнитивный диссонанс от неоптимального решения. А товарищ явно пушил в сторону деревьев.
Всего голосов 7: ↑6 и ↓1+5
Имхо на собеседовании валились люди с инженерным подходом к решению задачи. Irl обычно не создаётся конвертор всего во все. Первый вопрос, который должен задать грамотный специалист — вопрос о применимости данной системы. То что приведено в качестве примера — неприменимо от слова совсем именно по причине быстрой деградации точности. Второй вопрос: оптимальный путь для каждого значения нужно найти только один раз, причем это путь не до искомой системы измерения, а до промежуточной общей (например СИ или любой другой). Полученное значение зафиксировать в таблице и поставить отметку о необходимости повышения точности. При таком подходе время первичного поиска пути конвертации и как следствие оптимальность алгоритма не будет иметь решающего значения, т.к. все остальные конвертации по данному направлению будут иметь фиксированное время (согласен с Nomad1).
Всего голосов 5: ↑4 и ↓1+3
Я про то, что товарищ, ИМХО демонстрировал то на что его натаскали в американском ВУЗе — питон + деревья. При этом он демонстрировал знания без понимания. Это заученный материал, не переваренный. При этом он ожидал именно этого и от собеседуемых.
Я думаю отвалились на его собеседованиях слабые и сильные программисты, а средние прошли.
Всего голосов 5: ↑5 и ↓0+5
НЛО прилетело и опубликовало эту надпись здесь
И наверное, я бы эту задачу начал с построения множества возможных элементов преобразования для каждого элемента конвертации. Тогда задача решается просто: берём множества возможных преобразований запрошенных элементов конвертации и находим их пересечение (поиск промежуточного общего). Если не пересекаются — не судьба. Если пересекаются — сразу имеем кратчайший путь конвертации. Добавление нового элемента конвертации сводится к формированию его собственного множества с элементами конвертации, в которые он умеет конвертировать, и к добавлению этого элемента конвертации в те множества элементов конвертации, которые входят в сформированное собственное множество данного элемента.
Комментарий пока не оценивали0
А насколько рационально тратить ресурсы при поиске ответа на каждый запрос в поисковике? Не будет ли проще принять одну из единиц как «стандартную» (например, тот же метр из СИ), и просто при добавлении в базу любой новой единицы пересчитывать ее в метры, и хранить в БД один коэффициент? Тогда задача из топика сведется к двум банальным арифметическим действиям для любой из пар единиц измерения. Да и проверка возможности/невозможности решения сведется к запросу «для обеих ли заданных единиц измерения существуют записи в БД».
Всего голосов 2: ↑2 и ↓0+2
Проще, но проблема в том, что отношения к «стандартной» единице в общем случае для конвертируемых единиц в анализируемом наборе данных может не существовать. Короче, и вы тоже мыслите как инженер и собеседование не прошли :)
Всего голосов 2: ↑2 и ↓0+2
В моем мире инженер — это похвала. :)

Кстати, многих запутал перевод.
Given a list of conversion rates (formatted in the language of your choice) as a collection of origin unit, destination unit, and multiplier, for example:

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


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

Всего голосов 2: ↑2 и ↓0+2
НЛО прилетело и опубликовало эту надпись здесь
На самом деле мой косяк тут тоже есть — должен был перед началом реализации уточнить «а не будет ли возможным в условии задачи двух разных систем измерения длины, не имеющих способа пересчета из одной в другую». За то, что не подумал об этом меня и назвали инженером. )))
Всего голосов 1: ↑1 и ↓0+1
Назвали не за то, что не подумали, а за подход к решению. Автор пляшет от общего, сферического, и как следствие, неоптимального решения. Причем задачу решает в лоб. «Инженерный» подход (в моем понимании :) ) предполагает использование частного решения, с учётом известных проектировщику ограничений. Это ограничивает область применимости, но повышает эффективность. Т.е. для забивания гвоздя используется не синхрофазатрон, а другой, более удобный для этого инструмент.
То, что делает автор, допустимо и даже приветствуется в исследовательской работе, но недопустимо для решения, которое реализуется в железе.
Нижe предлагают для решения задачи использовать непересекающиеся множества (DSU). Судя по описанию, это то, к чему я пришел после непродолжительного анализа возможных путей решения задачи ( знал, что велосипед изобретаю :)). Исходя из этого могу предположить, что этап аналитической работы по изучению существующих алгоритмов и решений был пропущен в пользу инструмента, для которого уже есть наработки, что не есть хорошо при проектировании систем.
Печаль заключается в том, что автор, участвуя в подборе специалистов, во-первых, определяет технические подходы компании к решению задач; во-вторых, влияет на развитие тех специалистов, которыми руководит.
Всего голосов 2: ↑2 и ↓0+2
НЛО прилетело и опубликовало эту надпись здесь
Хорошая статья. Но отмечу, что не все единицы измерения конвертируются через умножение/деление на число, порой преобразования бывают посложнее, например логарифмическое или полиномиальное. Хотя решение не сильно поменяется, просто ребрам будут приписываться не числа, а функции. А путь тогда будет, по сути, соответствовать композиции функций.
Всего голосов 2: ↑2 и ↓0+2
Не знаю ни одного логарифмического преобразования, а из полиномиальных — только линейные с константой (между температурными шкалами).

Я бы отметил другое — что есть «сложные единицы», чей набор практически не ограничен. Например, редко используемые единицы плотности «хандредвейт на акр» (сwt/ac) и «хандредвейт на тысячу квадратных футов» (cwt/MSF) гугловскому калькулятору неизвестны — хотя по отдельности он понимает и хандредвейты, и акры, и футы. А ведь сложные единицы могут быть и ещё экзотичнее, вроде «пудов на квадратный аршин».
Комментарий пока не оценивали0
Там со звуком вроде логарифмы: децибелл это логарифм чего то.
Всего голосов 1: ↑1 и ↓0+1
Таки да, но ни в какую другую единицу децибел не переводится.
Комментарий пока не оценивали0

Тем не менее это прецедент и серьёзный. Раньше у нас были пары преобразований типа "1 метр = 3 фута" и неявное допущение, что вот это "=" означает умножение. Теперь же мы добавляем пару "1 децибел = 10 аудиоджоулей", но "=" здесь означает логарифм. И вся эта хитрая конструкция с графом рушится: как бы будем сранивать какое преобразование короче если слева и справа трехэтажная формула с логарифмами?

Всего голосов 2: ↑1 и ↓10
Как я описывал, ребрам приписываем не числа, а функции. А путь тогда будет, по сути, соответствовать композиции функций.
Всего голосов 1: ↑1 и ↓0+1

Цель поиска — найти кратчайший путь. Как мы будем сравнивать эти композиции функций?

Всего голосов 2: ↑2 и ↓0+2
Кратчайший путь это, очевидно, тот, в котором меньше ребер. И тогда в композиции будет меньше функций.
Комментарий пока не оценивали0
В контексте данной статьи, кратчайший путь — это тот, который вносит наименьшую погрешность при вычислениях.
Комментарий пока не оценивали0

Нет, это именно количество преобразований, если в контексте статьи. BFS ничего про погрешность не знает.

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

А если учитывать, что точность сильнее теряется подальше от 1, то становится ещё интереснее. Что лучше, умножить 2 числа 10 порядков или 10 раз но 2 но 0.5 (пример грубый).

Всего голосов 1: ↑0 и ↓1-1
Не знаю, что такое «аудиоджоуль». И гугл тоже не знает.
Если это единица энергии, то децибел в неё не переводится.
Комментарий пока не оценивали0
она переводится в безразмерные «разы» — т.е. усиление интенсивности звука в 10 раз — 10 децибел, в 100 раз — 20 децибел, а в 10000 раз — 40 децибел.
Посмотрите еще в сторону площадей и объемов — там квадратные и кубические см к км нелинейные.
Комментарий пока не оценивали0
Что не так с площадями и объёмами?
1 км3 = 1015 см3, соотношение вполне линейное.
Комментарий пока не оценивали0

Скажем перевести 1 акр в метры.

Комментарий пока не оценивали0
С тем же успехом можно вольты переводить в килограммы.
Всего голосов 1: ↑1 и ↓0+1
Физики любят измерять массу частиц в электронвольтах )). В СГС, кажется
Всего голосов 2: ↑2 и ↓0+2
Абсолютная шкала тоже существует, за ноль децибел принимается порог слышимости.
Комментарий пока не оценивали0
НЛО прилетело и опубликовало эту надпись здесь

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

Всего голосов 9: ↑9 и ↓0+9
Во-первых, работа в Reddit была потрясающей.

Почему была?
Комментарий пока не оценивали0

Можно ещё быстрее за O(log n) с помощью Heavy-Light Decomposition.
Представим всё в виде дерева (леса). По факту между каждой парой вершин есть два ориентированных ребра. В одну сторону мы делим, а в другую сторону умножаем на одну и ту же величину. Поэтому можно мысленно представить неориентированный граф и найти в нём любое остовное дерево. Выберем в качестве корня центроид для лучшей константы. И снова мысленно направим рёбра в сторону от корня к листам. Назначим, каждому ребру коэффициент так, чтобы в сторону от корня к листу умножать, а в обратную делить. Теперь можно сделать HLD — разбить дерево на log путей. Затем на каждом пути сделать структуру, позволяющую быстро считать произведение. Мы можно использовать ту же идею, что и в частичных суммах: посчитаем произведения на префиксах. Ответ: pref[r] / pref[l — 1]. Всё построение выполняется за O(V + E), т. к. используются только обходы в глубину.
Теперь как искать ответ. Коэффициент между двумя единицами измерения — произведение/отношение коэффициентов на пути. Простой путь в дереве между любой парой вершин единственнен; — это путь a -> lca(a, b) -> b. Ответ: f(lca(a, b) -> b) / f(a -> lca(a, b)). Он ищется за O(log n) — не более log путей на запрос, в каждом из которых операция за O(1)

Всего голосов 1: ↑1 и ↓0+1

Можно. А чем это будет лучше сразу системы непересекающихся множеств, которая за 2 умножения/деления всегда даёт ответ? Добавление в систему в среднем O(1). Построение всей системы строго O(N) (1 BFS или подобное из корневой).


А вообще задача мне показалась как-то ну очень простой. Граф пришёл в голову сразу, отсчёт от центра тоже.

Комментарий пока не оценивали0
А вообще задача мне показалась как-то ну очень простой.

Всё верно.
Принцип собеседования в гугле — начать с очень простой задачи, и на протяжении часа добавлять усложнения.
Комментарий пока не оценивали0

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

Всего голосов 1: ↑1 и ↓0+1

Хмм, действительно отличное решение. И ошибка будет меньше. Как-то я просто при виде задачи сразу подумал над быстрым поиском пути в дереве, а до DSU не догадался.

Комментарий пока не оценивали0
Спасибо! Пришел практически к этому путем размышлений. Теперь буду знать как это называется — DSU!!! :)
Комментарий пока не оценивали0
Любой американец, который путешествовал за пределами США, знает, что большая часть мира для измерения расстояний использует таинственную единицу «километр»

Вспомнилось: "There is a world outside US, yes!"

Что касается перевода единиц, то, интуитивно (но с условием, что единицы одного типа: скажем, длину в длину переводим, а не площадь в объем) же, кажется, что достаточно выделить одну единицу как основную, эталонную, от которой остальные зависят, так сразу получаем возможность выразить преобразуемое число в тих эталонных единицах, а потом число эталонных единиц в целевых единицах. Да, есть вопрос точности, но граф как таковой оценку точности преобразования также дает опосредованную, а точность, по сути, будет зависеть от округления каждой операции. Но это, кажется, слишком простое объяснение для собеседования девелопера — тут даже код красиво не напишешь на доске.
Всего голосов 1: ↑1 и ↓0+1
НЛО прилетело и опубликовало эту надпись здесь

К своему стыду (после прочтения комментариев) первой мыслью таки было "кратчайший путь на графе". Второй мыслю было "привести к СИ".

Всего голосов 1: ↑1 и ↓0+1
Да, статья познавательная. Но какое это имеет отношение к реальному программированию?
Если кто-то скажет, что имеет — он бы не прошел у меня собеседование.
Всего голосов 1: ↑0 и ↓1-1
Когда-то мой знакомый ПМ в шутку сформулировал термин превентивное планирование — обработка и переформулирование задачи таким образом, чтобы ее можно было решить без написания программы :)
Всего голосов 1: ↑1 и ↓0+1
Не поверите, прямо сейчас решаю точно эту задачу. Имея набор пар валют нужно рассчитать средний курс одной валюты в другой, желательно быстро, желательно не потратив на это кучу памяти. На работу к вам не пойду, у вас похоже задачи тухлые очень, вида «вставить данные из формочки в БД».
Всего голосов 1: ↑1 и ↓0+1
Как посредственный программист я бы решил этот вопрос без графов.
Выделил бы базовые типы величин (размер, вес, температура, площадь).
Каждый тип дополнил бы некоей «идеальной величиной», в которую удобно конвертировать остальные.
В итоге любое преобразование занимает ровно 2 операции (из одной в абсолютную, из абсолютной в нужную).
Проблему невозможных преобразований (из литра в метры) решал бы за меня полиморфизм — если единицы от разных абстрактных классов, то они одна из них просто не залезет в метод конвентера.
Комментарий пока не оценивали0

У вас нет классов, методов и прочего. Есть, условно говоря, текстовый файлик на вход. И там может быть


увррик деннон 3.124
деннок зазак 484.005
...

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

Всего голосов 1: ↑1 и ↓0+1

— Алекс, это ведь будет LPG-граф. Так давайте и будем хранить его в графовой СУБД, а коэффициенты преобразований вычислять запросами. Что у вас там есть развернутого? Neo4, говорите… Ну тогда так:


MATCH (foot:Unit {name:'foot'}), (meter:Unit {name:'meter'})
WITH shortestPath ((foot)-[:RATIO*]-(meter)) AS p
WITH nodes(p) AS ns, relationships(p) AS rs
WITH [i IN range(0, length(rs)-1) |
      CASE
      WHEN ns[i] = startNode(rs[i])
           THEN rs[i].ratio
           ELSE 1/rs[i].ratio
      END
     ] AS ratios
RETURN reduce (acc = 1, r IN ratios | acc * r)

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


— Добро пожаловать в Google Knowledge Graph, сынок.

Комментарий пока не оценивали0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Показать лучшие за всё время

Истории

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr