Вы описали "что" делается в статье. Но сама статья о том "как" это делается.
Как не написать "простыню" из if'ов при реализации сравнения.
Как сделать так, чтобы сравнение работало на всех возможных парах в рамках выбранной разрядной сетки. С доказательной базой.
Как сделать так, чтобы при сравнении не использовать разрядную сетку в 4 раза больше.
Как от решений неравенств и уравнений перейти сразу к компараторам. Эта часть может быть использована везде, где написание компаратора сводится к решению уравнений/неравенств.
Анализ максимумов (размер лабиринта) и (неявная) демонстрация простоты ее обоснования (по сравнению с float/double).
Смотрите, в Вашем примере не учтена накопительная ошибка вычисления, которая безусловно будет при сложении. Вот тут даже описано насколько может быть все плохо. Мои оценки выше по максимальной размерности лабиринта получены следующим образом.
Для float/double длины мантисс соответственно 23 и 53 бита.
Найдем значение когда при сложении дробная часть будет полностью отсутствовать в числе и игнорироваться при сложении. Это значения и соответственно. Далее распишу только для float.
Полученное число есть верхняя граница длины пути в лабиринте. А как мы уже знаем кратчайший путь точно не больше количества всех клеток в лабиринте. Поэтому 8388608 - это площадь лабиринта. В случае квадратного лабиринта размеры будут ~2897x2897.
При полученных размерах лабиринта теоретически может возникнуть ситуация когда мы прибавляем корень из двух, а по факту прибавляется просто 1.
Насколько вычислительные ошибки влияют в первом и последующих двоичных знаках после запятой тоже можно выяснить, но тогда оценка будет еще меньше.
Можно конечно попытаться обосновать, что кратчайший путь в пустом лабиринте - это точно не проход по всем клеткам лабиринта. Но тогда надо как-то пытаться уточнять верхнюю границу и доказывать это.
Что мне нравится в способе с целыми числами: простая доказательная база, которая еще и легко масштабируется. А мне нравится когда что-то доказано, нежели получено экспериментами с написанием кода.
Дополнительным плюсом является сравнение на равенство при извлечении из очереди с приоритетом. В случае с double/float придется либо вводить точность сравнения, либо слепо обрабатывать такие вершины. В случае с составными числами - это просто операция ==.
Так или иначе, наличие нашей с Вами дискуссии свидетельствует о более сложной природе float и double по сравнению с целыми числами.
Отличие от рассмотрения большего количества соседей ведет к появлению "скачков". Даже если мы включим ходы конем, то это уже будет неэлементарное перемещение, так как при ходе конем есть промежуточные клетки, которые нужно пройти. При рассмотрении только 8 соседей никаких промежуточных клеток между ними не возникает.
По поводу окрестности, где ходы по всем 8 направлениям стоят одинаково. Разумеется такая "классическая" постановка тоже имеет место быть. Давайте рассмотрим, почему и диагональные ходы равные корню из двух тоже имеют место быть. Для начала придумаем легенду к этой задаче. Пусть по лабиринту ездит робот. Он не поворачивается, у него есть лишь механизм переключения колес по 4 направлениям. В каждом направлении есть прямая и обратная передача. Затраты энергии на переключение колес пренебрежительно малы. Затраты энергии на передвижение пропорциональны пройденному расстоянию.
А теперь рассмотрим следующий кусочек лабиринта (# - стена, . - пустота, p и q - опорные точки, там тоже пустота).
Вниз, 4 раз вниз-вправо (диагональ), вправо, вверх-вправо, 2 раза вверх.
Если по всем 8 направлениям стоимость пути одинаковая, то стоимость первого пути равна 10, а стоимость второго - равна 9. Второй путь короче первого. Если же по диагоналям стоимость пути равна корню квадратному из двух, то длина первого пути равна 10, а длина второго - равна . Первый путь короче второго.
Очевидно, что для задачи с роботом подходит именно второй подход.
По поводу того насколько быстро работают числа. В постановке задачи ничего не сказано про то, что это должно работать быстрее, чем float или double. Тем не менее? некоторые попытки сделать оптимизации присутствуют. В исходном коде есть похожий тест, можно из него сделать benchmark. Я, честно сказать, не пробовал.
По поводу точности: проблемы (кстати как раз вышеописаная) начнется всего скорее тогда, когда при сложении дробная часть начнет полностью отбрасываться. Для float это уже может случаться при размерах лабиринта 2897x2897. Для double 94906265x94906265. Я, честно сказать, досконально сейчас не проверял, может быть еще что-то упустил. Замечу, что понять максимумы с составными числами гораздо проще.
Почему Фибоначчи с замыканиями код производительный, а рекурсивный вычисляет n-2 число по сути два раза? Без мемоизации там же в дичайшее дерево разворачивается все с плачевной производительностью… И тут не проблема рекурсивных вызовов, а проблема их использования именно в таком исполнении.
Тогда автор статьи что-то совсем упоролся. Эта задача еще проще, IMHO :-)
В оригинальном комментарии это было просто «к слову». Как демонстрация задачи из множества «решение опирается на другой алгоритм» остается K-максимум в массиве.
Проходил интервью в марте 2019 в Google и Microsoft. Яндекс, Microsoft: начало 2017 года. yadi.sk/i/Qni2rzVc7BG1sA — то, что я знаю для прохождения алгоритмических секций (возможно даже список еще не совсем полный).
Аналогично, сначала сделал через кучу, а на доп. вопрос уже сказал, что можно и через quick select (кстати, не знал, что оно имеет еще и название). Он, кстати, эффективнее кучи, так как там линейная сложность по времени.
Немного покритикую статью.
1) Сейчас на алгоритмических интервью в основном все-таки спрашивают задачи где надо придумать алгоритм (при этом можно не особо знать хоть какие-то алгоритмы вообще), либо «составить» эффективный алгоритм, благодаря знанию «алгоритма». Примерами здесь могут быть как раз та самая задача, упомянутая в статье про K-тый максимум (эта задача уже баян баянистый), который по сути опирается на знание работы быстрой сортировки. Либо, задачки на промоделировать что-то в лоб (только обойтись наименьшим количеством кода). Видел только один раз когда спрашивали написать почти напрямую алгоритм Дейкстры.
По поводу того, что задачу необязательно дорешивать: частично правда. Но нужно хотя бы словами успеть рассказать эффективный алгоритм.
2) Можно конечно бесконечно ныть, что алгоритмы не нужны. Можно попробовать их все-таки освоить (готовясь к интервью) и оглянуться на свой код, который когда-либо был реализован. Возможно, станет сюрпризом, что что-то можно было сделать проще, эффективнее, быстрее.
3) По поводу soft skills и behavior questions. В настоящее время рекрутеры снабжают информацией о базовых принципах компании. На каждый из этих принципов нужно подобрать (придумать в крайнем случае) историю. Встречный вопрос интервьюверу тут неуместен, так как он(а) не придумывал(а) историю, идя интервьювировать. В целом это несложное интервью, если готовы истории заранее. Главное распознать про какой принцип хотят поговорить интервьверы. Очень круто, если истории универсальные.
Мой опыт: 1 успешное собеседование в Яндекс, 2 успешных собеседования в Microsoft (Прага, Редмонд), 1 успешное собеседование в Google (Мюнхен).
Чтобы как-то вот так: Пользователь в Интернете -> [Сервер, на котором настроен прокси и cjdns в Hyperboria] -> [Телеграм нода в Hyperboria]. Извне (интернет) доступен только прокси, который умеет посылать на единственный адрес. Живых нод, кстати, по данным fc00.org колеблется от ~540 до ~570. Причем есть какие-то изолированые ноду. Соглашусь, что если есть возможность держаться подальше от самой ноды, при этом имея к ней стабильный коннект — то лучше так и сделать. В любом случае, всё это пока бесполезно, пока телеграмм ноды еще нет в Hyperboria. Хороший вариант, если люди будут поднимать такие ноды для себя и друзей, т.е. прокси будет запаролирован. Найти и заблокировать такое будет уже сложнее, особенно если каждый из таких проксей не будет обслужить клиентов слишком массово. Хотя может это и уже слишком утопично.
Можно попробовать на ноде, смотрящей в Hyperboria поставить проксю, которая настроена на то, чтобы проксировать трафик в Hyperboria (можно вообще ограничить прокси, чтобы ходил на одну единственную ноду). А сам прокси пускай смотрит в интернет (т.е. как и все остальные прокси, которые сделаны для людей). Чем больше таких волонтеров будет — тем проще противостоять блокировке. Соглашусь с тем, что вероятнее всего нужно хорошо попиарить cjdns/Hyperboria, но почему бы и нет?
Почитал мат. часть. Да, похоже что нужно ввести метод, который проверяет поддерживается ли определенный тип обёрткой или нет. Спасибо за замечание, учту!
Я использовал Expressions по следующим причинам:
1) компилируется минимум и функции просты до безобразия. Все, что можно не компилировать — не компилируется. Кроме того, кроме компиляцию создаются ещё некоторые вспомогательные структуры для конструирования как встроенных во фрейморк, так и кастомных запросов. Сгенерированные функции проверять каждый раз решарпером — думаю это лишнее, остальной код проверить конечно же можно.
2) их всего три и вряд ли предвидится больше.
3) не хочется никаких лишних действий кроме как использовать репозиторий и передать ему модель (в том числе унаследовать и добавить функции).
4) в силу природы отложенной инциализации репозиториев разогрев будет сущим пустяком по времени (я не думаю, что за один запрос будет использовано более 10 репозиториев).
Спасибо! Посмотрел пока мельком — то чего не хватало когда писал (превращение в SQL подобное с Select/Where писал сам и в данный момент в этой части кода пока не очень все нравится. Посмотрю подробнее.
Не совсем. Все-таки в интерфейсы оберток можно добавить любые методы, в реализациях выкинуть NotSupportedException, если СУБД по тем или иным причинам не поддерживает тип. Те интерфейсы которые объявлены в проекте будут использоваться одинаково, вне зависимости от того, какая реализация под капотом.
Я перечислил классы DbConnection/DbCommand. Да, через DbProviderFactory можно получить DbConnection, а через него DbCommand и т.д. Но я говорю вот о чем: в случае скажем с PostgreSQL не приводя DbDataReader к NpgsqlDataReader (http://www.npgsql.org/api/Npgsql.NpgsqlDataReader.html) невозможно получить например NpgsqlTimeSpan (функция NpgsqlDataReader.GetInterval). TimeSpan сейчас еще не поддерживается фреймворком. Но это как раз является причиной использования конкретных реализаций.
Вы описали "что" делается в статье. Но сама статья о том "как" это делается.
Как не написать "простыню" из if'ов при реализации сравнения.
Как сделать так, чтобы сравнение работало на всех возможных парах в рамках выбранной разрядной сетки. С доказательной базой.
Как сделать так, чтобы при сравнении не использовать разрядную сетку в 4 раза больше.
Как от решений неравенств и уравнений перейти сразу к компараторам. Эта часть может быть использована везде, где написание компаратора сводится к решению уравнений/неравенств.
Анализ максимумов (размер лабиринта) и (неявная) демонстрация простоты ее обоснования (по сравнению с float/double).
Смотрите, в Вашем примере не учтена накопительная ошибка вычисления, которая безусловно будет при сложении. Вот тут даже описано насколько может быть все плохо. Мои оценки выше по максимальной размерности лабиринта получены следующим образом.
Для float/double длины мантисс соответственно 23 и 53 бита.
Найдем значение когда при сложении дробная часть будет полностью отсутствовать в числе и игнорироваться при сложении. Это значения
и 
соответственно. Далее распишу только для float.
Полученное число есть верхняя граница длины пути в лабиринте. А как мы уже знаем кратчайший путь точно не больше количества всех клеток в лабиринте. Поэтому 8388608 - это площадь лабиринта. В случае квадратного лабиринта размеры будут ~2897x2897.
При полученных размерах лабиринта теоретически может возникнуть ситуация когда мы прибавляем корень из двух, а по факту прибавляется просто 1.
Насколько вычислительные ошибки влияют в первом и последующих двоичных знаках после запятой тоже можно выяснить, но тогда оценка будет еще меньше.
Можно конечно попытаться обосновать, что кратчайший путь в пустом лабиринте - это точно не проход по всем клеткам лабиринта. Но тогда надо как-то пытаться уточнять верхнюю границу и доказывать это.
Что мне нравится в способе с целыми числами: простая доказательная база, которая еще и легко масштабируется. А мне нравится когда что-то доказано, нежели получено экспериментами с написанием кода.
Дополнительным плюсом является сравнение на равенство при извлечении из очереди с приоритетом. В случае с double/float придется либо вводить точность сравнения, либо слепо обрабатывать такие вершины. В случае с составными числами - это просто операция ==.
Так или иначе, наличие нашей с Вами дискуссии свидетельствует о более сложной природе float и double по сравнению с целыми числами.
Отличие от рассмотрения большего количества соседей ведет к появлению "скачков". Даже если мы включим ходы конем, то это уже будет неэлементарное перемещение, так как при ходе конем есть промежуточные клетки, которые нужно пройти. При рассмотрении только 8 соседей никаких промежуточных клеток между ними не возникает.
По поводу окрестности, где ходы по всем 8 направлениям стоят одинаково. Разумеется такая "классическая" постановка тоже имеет место быть. Давайте рассмотрим, почему и диагональные ходы равные корню из двух тоже имеют место быть. Для начала придумаем легенду к этой задаче. Пусть по лабиринту ездит робот. Он не поворачивается, у него есть лишь механизм переключения колес по 4 направлениям. В каждом направлении есть прямая и обратная передача. Затраты энергии на переключение колес пренебрежительно малы. Затраты энергии на передвижение пропорциональны пройденному расстоянию.
А теперь рассмотрим следующий кусочек лабиринта (# - стена, . - пустота, p и q - опорные точки, там тоже пустота).
Рассмотрим следующие пути между p и q.
Вверх, 6 раз вправо, 3 вниз.
Вниз, 4 раз вниз-вправо (диагональ), вправо, вверх-вправо, 2 раза вверх.
Если по всем 8 направлениям стоимость пути одинаковая, то стоимость первого пути равна 10, а стоимость второго - равна 9. Второй путь короче первого.
. Первый путь короче второго.
Если же по диагоналям стоимость пути равна корню квадратному из двух, то длина первого пути равна 10, а длина второго - равна
Очевидно, что для задачи с роботом подходит именно второй подход.
По поводу того насколько быстро работают числа. В постановке задачи ничего не сказано про то, что это должно работать быстрее, чем float или double. Тем не менее? некоторые попытки сделать оптимизации присутствуют. В исходном коде есть похожий тест, можно из него сделать benchmark. Я, честно сказать, не пробовал.
По поводу точности: проблемы (кстати как раз вышеописаная) начнется всего скорее тогда, когда при сложении дробная часть начнет полностью отбрасываться. Для float это уже может случаться при размерах лабиринта 2897x2897. Для double 94906265x94906265. Я, честно сказать, досконально сейчас не проверял, может быть еще что-то упустил. Замечу, что понять максимумы с составными числами гораздо проще.
Просто оставлю это здесь (наивная рекурсия на python для Фибоначчи, накатал на скорую руку, извиняйте если что, файл fibonacci.py):
python -m timeit 'import fibonacci; fibonacci.fib(20)'
100000 loops, best of 3: 2.54 usec per loop
Понятно, что может характеристики машины не те, но что-то сомневаюсь, что время будет сильно варьироваться.
Почему Фибоначчи с замыканиями код производительный, а рекурсивный вычисляет n-2 число по сути два раза? Без мемоизации там же в дичайшее дерево разворачивается все с плачевной производительностью… И тут не проблема рекурсивных вызовов, а проблема их использования именно в таком исполнении.
В оригинальном комментарии это было просто «к слову». Как демонстрация задачи из множества «решение опирается на другой алгоритм» остается K-максимум в массиве.
yadi.sk/i/Qni2rzVc7BG1sA — то, что я знаю для прохождения алгоритмических секций (возможно даже список еще не совсем полный).
1) Сейчас на алгоритмических интервью в основном все-таки спрашивают задачи где надо придумать алгоритм (при этом можно не особо знать хоть какие-то алгоритмы вообще), либо «составить» эффективный алгоритм, благодаря знанию «алгоритма». Примерами здесь могут быть как раз та самая задача, упомянутая в статье про K-тый максимум (эта задача уже баян баянистый), который по сути опирается на знание работы быстрой сортировки. Либо, задачки на промоделировать что-то в лоб (только обойтись наименьшим количеством кода). Видел только один раз когда спрашивали написать почти напрямую алгоритм Дейкстры.
По поводу того, что задачу необязательно дорешивать: частично правда. Но нужно хотя бы словами успеть рассказать эффективный алгоритм.
2) Можно конечно бесконечно ныть, что алгоритмы не нужны. Можно попробовать их все-таки освоить (готовясь к интервью) и оглянуться на свой код, который когда-либо был реализован. Возможно, станет сюрпризом, что что-то можно было сделать проще, эффективнее, быстрее.
3) По поводу soft skills и behavior questions. В настоящее время рекрутеры снабжают информацией о базовых принципах компании. На каждый из этих принципов нужно подобрать (придумать в крайнем случае) историю. Встречный вопрос интервьюверу тут неуместен, так как он(а) не придумывал(а) историю, идя интервьювировать. В целом это несложное интервью, если готовы истории заранее. Главное распознать про какой принцип хотят поговорить интервьверы. Очень круто, если истории универсальные.
Мой опыт: 1 успешное собеседование в Яндекс, 2 успешных собеседования в Microsoft (Прага, Редмонд), 1 успешное собеседование в Google (Мюнхен).
1) компилируется минимум и функции просты до безобразия. Все, что можно не компилировать — не компилируется. Кроме того, кроме компиляцию создаются ещё некоторые вспомогательные структуры для конструирования как встроенных во фрейморк, так и кастомных запросов. Сгенерированные функции проверять каждый раз решарпером — думаю это лишнее, остальной код проверить конечно же можно.
2) их всего три и вряд ли предвидится больше.
3) не хочется никаких лишних действий кроме как использовать репозиторий и передать ему модель (в том числе унаследовать и добавить функции).
4) в силу природы отложенной инциализации репозиториев разогрев будет сущим пустяком по времени (я не думаю, что за один запрос будет использовано более 10 репозиториев).