Комментарии 345
От сильного стажёра или инженера уровня L3 я ожидаю, что он сможет справиться с двоичным поиском за час
От синьора стоит ожидать что он вообще не будет заморачиваться с двоичным поиском. Потому что в условии задачи про скорость работы ничего не сказано.
При текущих исходных данных бинарка не только не нужна, но и вредна. В скорости работы и потраченных ресурсах разница будет ничтожна при текущем n (и, скорее всего, линейный поиск окажется и быстрее и менее жручим, чем бинарный при таком малом значении n). А вот читаемость и поддерживаемость кода ухудшится, задача займет дополнительное время на ненужный функционал, который, может быть, никогда не пригодится.
Первый вопрос, который бы задал я, это - а зачем нам это всё, какую цель мы преследуем и какие сроки имеем? И уже из ответа проистекало бы всё остальное.
От хорошего инженера ждут что код соответствует принципам:
reliability
scalability
compliance with requirements
Видно что первые два принципа похожи на NFR (non-functional requirements), но при этом они как бы вне техзадания (3й пункт), в котором может быть куча требований. Потому что любой код по умолчанию обязан быть надежным и скейлиться (учитывать time/../space complexity) если в требованиях явно не указано обратное.
Это всё решается дополнительным "if (n<32)"
В скорости работы и потраченных ресурсах разница будет ничтожна при текущем n (и, скорее всего, линейный поиск окажется и быстрее и менее жручим, чем бинарный при таком малом значении n).
В питоне линейный поиск - 0.070, приведенный автором "примитивный" - 0.053. При тысяче прогонов с x от 1 до 25
А разве пример на питоне?
На самом деле, вопрос правильный, так-как в Питоне фигурные скобки - это set.
Опс, Исправили, пока я писал?
переписал на питоне. Постарался один в один. Разумеется список, а не массив.
Список на питоне, это далеко не массив в С/С++/С# и т.п. Для питона почти всегда двоичный поиск будет быстрее.
Переписал на C++. 25 млн вызовов функции (также на входе x от 1 до 25):
линейный - 0.72 - 0.74
бинарный - 1.39 - 1.40
А в оригинале у автора кажется JS. Но на него я переписывать не буду :)
Что и требовалось доказать.
Кстати, автор не удосужился даже указать, на каком языке примеры.
У автора код на языке С.
Почему-то для себя решил, что под "автором" понимается Джоэл Спольски - создатель той книги, на которую ссылается цитируемый товарищ. Так вот, Спольски, действительно, сначала практиковал, в основном, язык C, ибо начинал карьеру в Microsoft, значась в команде, работающей над встроенным в Excel скриптовым языком.
А в приведенном фрагменте кода есть служебные слова "function" и "var", которых я не припоминаю в C.
Еще код похож на PHP, но там переменные начинаются со знака $ и, кроме того, длина массива вычисляется как count($arr) (или sizeof($arr)), а вовсе не как $arr.length.
При текущих исходных данных бинарка не только не нужна, но и вредна.
Про размер входного массива ничего не сказано же. Или я что-то пропустил? Ожидается, что вы как раз выясните все ограничения.
Вроде бы 10 элементов размер...
Где? Это тестовый пример на котором задачу объясняли, реальный размер входных данных не написан. Как раз и ожидается, что один из первых ваших вопросов будет про реальные входные данные.
Тогда уж и сортировку никто не гарантирует.
"Массив, фигурирующий в задаче, составлен нарочно таким образом, чтобы не включать 0 и отрицательные числа – это не добавило бы к решению задачи ровным счетом ничего. Элементов в массиве 11, что дает нам пространство индексов от 0 до 10. 10 легко делится на 2, поэтому среднюю точку можно определить без проблем – это число 12"
Т.е. он даже тесткейсы подбирает под исходный набор данных.
При текущих исходных данных бинарка не только не нужна, но и вредна. В скорости работы и потраченных ресурсах разница будет ничтожна при текущем n (и, скорее всего, линейный поиск окажется и быстрее и менее жручим, чем бинарный при таком малом значении n)
Не правда. Часто даже навороченный логарифмический алгоритм оказывается быстрее линейного при очень маленьких ограничениях. Например, вот тут уже при n=4 хитрый алгоритм оказывается быстрее. Я мерял.
Тут же самый примитивный бинарный поиск с одним сравнением. Для заданных 11 чисел бин поиск 100% быстрее. Потом, ничего не мешает написать отдельный вариант для коротких массивов и выбирать, какой из двух запускать в рантайме.
Да откуда же сколько ресурсов возьмется на написание всех этих версий, а главное на их поддержку?
Если вам действительно важна производительность во всех случаях, то написать 2-3 разных алгоритма - не проблема. Если же вам достаточно, что ваша программа не станет вдруг падать при внезапном повышении нагрузки, то пишите только бинпоиск и не парьтесь.
Вначале пишут что-бы работало, а потом уже профилируют и рефакторят узкие места. В SAP по крайней мере. Не думаю что в разработке для реального мира выделяют в три раза больше рабочего времени для написания двух-трех разных алгоритмов. Поэтому никто не будет писать двоичный поиск для разового поиска в небольших данных, а если и будут, то только там, где обычный будет ощутимо медленно работать.
В начале решают, что вообще и как будут писать. Выбор правильного алгоритма - это не преждевременная оптимизация. Да, обычно не пишут несколько версий, а пишут самый оптимальный алгоритм. А уже потом, если надо, допиливают с несколькими вариантами.
Если делать не так, то у вас будет тормозить вообще все равномерно.
В идеальном мире? В реальном qsort никто руками не пишет. И оптимальный по производительности это не оптимальный вообще.
И бинпоиск для поиска в массиве никто не пишет, использут какой-нибудь lower_bound из стандартной библиотеки. Но вот когда бинпоиск нужен для поиска по ответу, когда у вас и массива-то никакого нет вообще - его приходится писать руками. Плюс на интервью хочется, все-таки, посмотреть как кандидат решает сложную задачку. Особенно в фаанге-то. Потому что какой-нибудь джон переложить выпускники курсов "мидл с нуля за 2 месяца" еще смогут, а вот что-то посложнее - уже нет. Поэтому приходится заставлять кандидата делать что-то интересное, даже если ему придется делать это редко (а ему придется, в гугле-то, по личному опыту заявляю).
Просто знай, что я уже раз в 20-й натыкаюсь на тебя в разных статьях и везде плюсую. Ты как воин света в одиночку защищаешь саму необходимость думать в программировании. Везде сплошные антиалгоритмисты. Никогда не думал, что доживу до этого момента, когда 99% программистов будут отрицать алгоритмы как явление...
когда у вас и массива-то никакого нет вообще - его приходится писать
Нет, именно для этого существует абстракция итераторов и STL. lower_bound / partition_point работает на random access итераторах за O(logN) (и forward итераторах с нюансами, но это тут неважно).
random access range очень легко выдумать например из последовательности чисел
В реальном мире"программисты" вроде тебя до сих пор думают, что используется qsort из коробки. Меня даже на собеседовании один тимлид спрашивал про qsort в java collections, на что я ему ответил: там нет qsorta, я не проверял, но я точно могу сказать что это не qsort хотя у обоих сложность O(nlogn). На что он возмутился и утверждал, что qsort. Потом он погуглил и удивлённо обнаружил, что я прав. Откуда я знал? Да хз, просто для меня было очевидно, что при прочих равных надо использовать устойчивую сортировку, и в коробке не может быть qsort так как это неустойчивая сортировка. Но "программисты" не знают зачастую о свойствах устойчивости.
ЗЫ на работу меня тогда естественно не взяли. Задача на собеседовании - ответить достаточно хорошо, но чуть хуже чем интервьюер))
Насколько я помню, там double pivot introspecting sort. Который суть всё тот же qsort, только с оптимизациями.
Да у них в актуальном JDK даже файл реализующий алгоритм называется DualPivotQuicksort.java
Видимо, перепутали. В комментарии речь о коллекциях, а не arrays
Кто и что перепутал?
Тот же List.sort в реализации по умолчанию делегирует всё Arrays.sort.
У ArrayList.sort есть оптимизированная реализация, но вся оптимизация заключается в вызове Arrays.sort без лишних копирований.
Ну а Arrays.sort делегирует всё DualPivotQuicksort.sort
Да уж... Перечитайте ещё раз. Потом можете погуглить, хотя уверен уже многократно пытались. На крайний случай открыть IDE. Шучу, ничего не надо, оставлю просто скриншот о сортировке в Collections. И заметь акцент о стабильности. Можешь попутно погуглить, что это.
Ну и что ваш скриншот вообще доказывает-то? (Кстати, научитесь делать скриншоты меньше, смотреть картинку на весь монитор совсем не интересно)
Я-то, в отличии от вас, в исходники OpenJDK смотрел:
Можете минусовать до талого))) Но если не видите своей ошибки, после того как трижды ткнули, то тут уже ничего не поделать. Даже собственные ссылки, которые беспорядочно нагуглили, не проверили. Ну хотя бы откройте свою же ссылку про Collections.sort или про List.sort и почитайте, наконец, хотя бы java-doc в своих же приведенных ссылках кроме последих двух:
This implementation is a stable, adaptive, iterative mergesort
Еще раз: mergesort. От себя добавлю: MERGESORT
Все же дам подсказку: есть такая штука в Java - перегрузки. Ищите свою ошибку.
Там, по идее, не гарантируется, что это именно mergesort - в частности, Arrays::sort(Object[]), который вызывается из List.sort, может использовать либо mergesort, либо timsort. А вот условие устойчивости прописано явно, да.
Там в этих перегрузках чёрт ногу сломит. Да, вы правы, нужная перегрузка и правда использует TimSort, являющийся разновидностью mergesort. Было бы ещё чудесно, если бы вы сразу написали об этом, а не кидали загадочные скриншоты.
Нет, вначале выясняют, какого размера коллекция придет в проде.
Некорректный пример для полигона. Там куча других операций при поиске делается, которые перекрывают скорость доступа к собственно элементу массива.
Зависит от языка.
На компилируемом 11 значений влезут в кэш процессора и обыщутся быстрее хитрых. Эмпирически есть две границы - 8 и 32 элемента.
Вплоть до 8 сортировать можно хоть пузырьком. А вплоть до 32 искать можно хоть линейно. И только потом начинает вмешиваться О большое.
Я ниже привел результат бенчмарка. С 4 элементов бинпоиск быстрее. Если его вылизать, то, наверное, даже с 3.
Как-раз синьор таки должен сам спросить у интервьюера все параметры задачи, которые явно не прописаны. А которые прописаны - уточнить, правильно ли он их понял. Это тоже показывает уровень. Да, если в результате выяснится, что речь не идёт о гигабайтах данных, то можно и перебором решить. А если задача должна масштабироваться, то алгоритм уже другой. А если супер-масштабироваться, то опять другой. Но всё это идеальный синьор в вакууме должен выяснить и рассказать сам. В том то и суть правильного собеседования.
Уточнить на каком языке должен быть написан алгоритм, на каком устройстве запускаться и т.д. Т.е. времени на само написание кода у него уже и не останется. Зато будет отличное подробнейшее ТЗ для джунов.
Как будто что-то плохое... )) В идеале задача и должна быть так поставлена, чтобы по ТЗ её уже любой джун мог запрограммировать )) Суть синьора во многом именно в том, чтобы хорошо декомпозировать и описать задачу. А что касается языка, то на таких собесах бывает вообще пишут код на псевдокоде в нотепаде. Потому что по конкретному языку и его теории - это отдельное собеседование, а тут про алгоритмы.
Да, правильный синьер должен интервьюера загнать в тупик, ну или схантить на худой конец.
От сеньора стоит ожидать как минимум замечание, что типы параметров не определены и а.length вполне может выкинуть исключение, так же как и а[i], и любая операция сравнения (больше, равно, меньше), если эти операции не определены для данного переданного типа.
Автору: не хватает как минимум еще двух тестов - с передачей неправильных типов для первого и второго параметров.
Неправильно;)
Синьор должен перед решением уточнить, что от него хотят, или, для чего и где это будет использоваться.
Если предположить, что поиск нужен по этому конкретному предложенному массиву (а это можно предположить из объяснения решения от автора, но я бы уточнил у интервьювера), то не надо тут ни логарифмов, ни O(N). Задача решается за O(1): готовим массив из 21 элементов с ответами. Выходы за границы (0 и 21) обрабатываем отдельно.
Кроме того, массив для бинарного поиск должен быть упорядочен, а потому, надо его предварительно сортировать. В общем бинарный поиск чисто для теоретиков. Действительно ни один вменяемый сеньор этой фигнёй заниматься не станет.
Я вам в другой ветке уже ответил. Повторю тут, чтобы у читающих не возникало ложного мнения вашей правоты.
Применяется весьма часто.
Ваш ответ не имеет ничего общего с реальностью к сожалению.Потому я даже не стал ваш ответ комментировать.
Тут 2/3 комментаторов знают что бинарный поиск чисто теоретическая задача, оторванная от реальности, а вы своё всё пытаетесь всем внушить.
Нет, вы не правы совершенно, бинарный поиск действительно не применяется на практике, что отметил не только я. Можете хоть 1000 минусов мне поставить - это ваш уровень.
нам когда в детстве давали олимпиадные задачи (решением которых был бинарный поиск) так заодно (для корректности) указывали на то, что массив сразу упорядочен, и главная задача найти искомый элемент за наименьшее число итераций.
Потому да, решали бинарным поиском, и чисто для "галочки". С тех пор (а это почти 30 лет в IT) мне этот бинарный поиск ни разу нигде не пригодился, от слова совсем. Нет никаких прикладных задач, где он бы мог помочь.
Нет, специально под него сортирнуть массив, можно конечно, но зачем?
Есть другие, более быстрые способы поиска, и прежде всего индексирование (в т.ч. использование хэшей и словарей.)
Наверное, я туповат, но формулировка "ближайшее наименьшее число" не очень ясна. Может, стоило написать "ближайшее число, которое меньше или равно заданному"? По крайней мере, судя по тест-кейсам, предполагается именно это. Эх, не быть мне L5, "некоторые просто не понимают, чего я от них добиваюсь" )
формулировка "ближайшее наименьшее число" не очень ясна.
Она вообще какая-то противоречивая. Т.к. оба определения - и "ближайшее", и "наименьшее",- по тексту совершенно равноправны. Хотя по смыслу нужно наименьшее из ближайших. При обратном приоритете вообще ничего не получится - наименьшее в это массиве всегда первое, вне зависимости от чего-либо (при условии, что массив соответствует условию).
Я бы, наверное, сказал "наибольшее число, не превышающее заданное".
Т.к. оба определения - и "ближайшее", и "наименьшее",- по тексту совершенно равноправны. Хотя по смыслу нужно наименьшее из ближайших
Так вроде приоритет правильно указан - сперва ближайшее, потом среди ближайших наименьшее, если есть равноправно удаленные ближайшие.
Так вроде приоритет правильно указан - сперва ближайшее, потом среди ближайших наименьшее, если есть равноправно удаленные ближайшие.
По правилам русского языка - всё с точностью до наоборот. Если считать определения неоднородными, то первое относится к комбинации второго определения и существительного. И получается "ближайшее из наименьших". А поскольку в сортированном [по возрастанию] массиве "наименьшее число" - это без вариантов первое число массива, то дополнительное "ближайшее" вообще лишено смысла, ибо ему приходится выбирать гарантированно из одного варианта. Ну или из ничего, если массив пуст.
Эта нелогичность и заставляет считать определения однородными.
В случае же неоднородных определений должно быть написано наоборот - "наименьшее ближайшее число". Тогда всё ровно - ближайших либо одно, либо два, и из них наименьшее.
Впрочем, по смыслу эти определения и правда неоднородны, ибо рассматривают разные свойства числа - "ближайшее" рассматривает местоположение, а "наименьшее" - значение.
Да и метрику расстояния не задали. Вообще не понятно, что он от людей хотел)
ну вот для числа 13, ближайшее наименьшее будет 12, а не 14.
А для числа 8, ближайшее наименьшее будет 9 (а не 6)
Я по-прежнему не понимаю, почему для 2 ближайшее наименьшее найдено не будет, а для 22 - пожалуйста. В остальном вы правы, моя переформулировка не является верной.
Нужно найти число, которое
а) меньше или равно входному
И
б) содержится в массиве
Если входное число (22) превышает максимальный элемент (21), то очевидно, что максимальный элемент и будет ответом.
Если входное число (2) меньше минимального элемента (3), то очевидно, что массив не содержит искомого числа, значит ответ == -1
Нужно найти число, которое
а) меньше или равно входному
Это откуда такое? Читаем задание:
которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки.
Ткните мне пальцем в требование, чтобы результат не превышал заданное число... я лично такого требования не нахожу. А потому кейс
f(a, 2) = -1 // Число слишком мало и выходит за границы массива
лично мне кажется не соответствующим исходному заданию. Для переданного числа 2 ближайшее, и оно же наименьшее, одно - это число 3, первый элемент массива. И ошибки - как-то не видно. Так что откуда -1 в ответе - ну совсем непонятно.
Впрочем, это вполне обычное состояние, когда по мере решения задача начинает обрастать кучей дополнительных и не озвученных в исходном задании условий. А уж для заданий программисту, особенно поставленных в рабочем порядке, это вообще скорее норма, чем исключение.
Ткните мне пальцем в требование, чтобы результат не превышал заданное число... я лично такого требования не нахожу.
Я так понял русскоязычную формулировку, а дальнейший текст это подтвердил. Оригинальная (англоязычная) формулировка мне нравится меньше, но примеры всё же позволяют [мне] догадаться. Хотя, да, я бы всё равно уточнил.
Возможно, формулировка специально дана в таком виде, чтобы посмотреть на реакцию кандидата.
В оригинале
Define a function f(a, x) that returns x, the next smallest number, or -1 for errors.
И в моём восприятии это даже хуже, чем "ближайшее наименьшее число"
Define a function f(a, x) that returns x, the next smallest number, or -1 for errors.
я бы написал return x, x - 1 , в задании ведь нигде не сказано, что число должно браться из a. Потом бы мне не дали оффер, и я написал бы статью о интервьерах, которым не нравится, что их ловят на неточных заданиях )))
Потому что нормальная формулировка - next smaller element. А тут просто вообще от балды написано.
просто ваш английский видимо слишком запутан ассоциацией что next это всегда следующий. А в оригинале это просто соседний, неважно в какую сторону. Girl next door, это не обязательно она живет справа.
Как по мне, в задании указано: "Определите функцию f(a, x), которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки. " - функция должна возвращать два числа: "Х" и "ближайшее наименьшее число" или "-1" в случае ошибки. Явно же не указано, что возврат подразумевает одно из чисел.
То есть f(a, 12) = 12, 10
Так там ещё
У нас есть массив, отсортированный по возрастанию
a = […]
напишите f(a, x)
Поэтому мы пошлём null
f(null, x) = -1 // Неверные аргументы
А можно туда и колбэк послать? Не говоря ещё и про сортировку
Согласен. Тоже задумался что надо сделать, пока результаты выполнения ниже не прочитал.
Определите функцию f(a, x), которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки.
Изи
f(a,x) = x
В следующий раз не ленитесь.
Find X
Разворачивая вашу мысль для тех, кто не понял:
В задании вообще ничего не сказано о том, что возвращаемый результат функции должен быть элементом массива. Кое-как об этом можно догадаться по тестовым примерам, но, мягко говоря, с трудом.
И, например, совершенно не очевидно что f(a,2)=-1 - на первый взгляд f(a,2)=2 вполне валидно. Из условия задачи вообще не следует, что х за пределами массива является ошибкой.
Абсолютно верно, а вообще нельзя получить верное решения задавая не верный вопрос.
PS: я бы сказал задающему такую задачу что что к Вас ошибка в примерах и пускай сам думает в чем трабла.
К сожалению, в реальности вы в неравных условиях. Задающий задачу уже работает в Гугл, получает огромную зарплату и имеет ещё более огромное ЧСВ, не умея корректно формулировать элементарную задачу. А получение вами работы зависит от абсолютно субъективного мнения этого самого задающего о вас.
Тут как посмотреть, не только компания выбирает работника, но и работник выбирает где ему работать.
Ну и в больших компаниях заведено правило фидбека на интервьюера даже если ты не прошёл.
не умея корректно формулировать элементарную задачу
Почему вы решили, что не умеет, а не делает это специально? В обычной ситуации задачи тоже часто недоформулированы и содержат двусмысленные формулировки. И как раз смотрят, в том числе, на то, как человек себя поведет - добъётся ясности или побежит программировать как понял, выдав не то, что нужно, в итоге. Если программист на интервью получил задачу, ничего не спросил и пошёл писать код, это жирнейший минус и, скорее всего, проваленное интервью.
Даже странно, что в такой длинной статье не указано это самое быстрое и соответствующее ТЗ решение. Может это ловушка и на самом деле он нанимает только тех, кто так отвечает?
f(a, 2) = -1 // Число слишком мало и выходит за границы массива
f(a, 22) = 21 // Число слишком велико и выходит за границы массива
f(a, 3) = 3 // Левая граница массива
f(a, 21) = 21 // Правая граница массива
А при чём тут вообще границы массива? Предметная область не определена. Формулировка задания ни полслова о границах не говорит. Получается, что либо задание не соответствует задаче (иначе откуда такая забота о границах?), либо финально от кандидата требуют не "реши задачу". а "угадай, что я задумал".
f([], x) = -1 // Массив пуст
Ну вообще-то у нас есть начальное условие "У нас есть массив, отсортированный по возрастанию". Кто бы мне рассказал, как может быть сортирован пустой массив.
Как правило, после небольших подсказок, кандидат приходит к следующему списку
Интересно, почему кейс с несоответствием первого аргумента рассмотрен, а второго - нет..
с пустым массивом ещё ладно, он проходит проверку на source == source.sorted()
но вот когда просят тест-кейс на невалидные типы данных, типа nullable при лайвкодинге на языках с null-safety - это вообще странно. но такое наблюдаю часто.
Это от шизы и не знания SOLID конкретно буквы S. Часто вижу что люди не могут осознавать что эти принципы можно применить даже к методу. В случае написания алгоритма я предполагаю что обязанности проверок данных лежит на коде выше.
Защитное программирование говорит, что все входные параметры надо обязательно проверить, если только это не сказывается на быстродействии; так что незнание буквы S тут ни при чём.
Проверка на null в языке с null-safety - это либо просто шиза, либо привычка работать с устаревшим кодом, либо привычка работать с коллегами, которые проверки null-safety обходят.
защитное программирование разве не предписывает проводить проверки на стыке систем и библиотек, а не в каждой функции?
а ещё есть принцип garbage in - garbage out - когда странно ожидать от кода адекватного поведения, если вызывающая сторона сама передаёт фигню вместо данных.
В общем, считаю, что тут вопрос религии, каким делать контракт, и конфессию на собесе можно уточнить, но за неуточнение я бы точно не списывал балл разрабу в данной конкретной задаче.
Пустой массив вполне себе отсортирован, на нем установлено отношение порядка.
Для него работает правило "каждый последующий элемент не меньше предыдущего".
каждый последующий элемент не меньше предыдущего
В такой формулировке получается, что в пустом массиве существует некий "предыдущий". Поэтому лучше так: "каждый элемента массива не меньше всех предыдущих"
Не получается.
Квантор всеобщности на пустом множестве даёт истину.
Ну вы серьезно!? Да, я некорректно выразился, думал, что это очевидно и поэтому написал небрежно. Я имел ввиду если в массиве множество предыдущих элементов пусто. При этом сам то массив может быть и не пустым, а состоять из одного элемента, например.
Как вы будете применять квантор всеобщности в этом случае?
Зато вас заплюсовали, местная аудитория поражает своей глубиной мышления, и умением проверять массивы на граничные случаи)))
Так же. Формулировка "каждый последующий [...] предыдущего [...]" означает применение квантора всеобщности к множеству последовательных пар индексов.
У массива из одного элемента это множество такое же пустое как и у пустого массива.
Вы берете массив из одного элемента, применяет к нему рекуррентно правило "каждый последующий элемент не меньше предыдущего" уже на первом же шаге у вас существует последующий элемент - это единственный элемент массива*, а значит, чтобы массив был отсортирован должен существовать предыдущий, а его не существует.
(*) В противном случае надо отдельно определить, является ли первый элемент массива последующим или нет, и вообще по-хорошему надо определить, что такое последующий элемент. Вот вы наверное считаете, что первый элемент не может быть последующим, но это не очевидно и зависит от договоренностей.
P.S. экой вы, батенька, токсик. Минусовать в математическом споре о трактовках понятий - это сильно.
Формулировка "каждый последующий [...] предыдущего [...]" означает применение квантора всеобщности к множеству последовательных пар индексов
Ну только если только в такой трактовке про "последовательные пары индексов". Ну это уже какое то домысливание... Тогда лучше так и прописать условие, что "для всех последовательных пар индексов выполняется..." И ещё определить что такое последовательная пара. В общем либо неоднозначность, либо сильное переусложнение формулировки. Поэтому лучше пользоваться формулировкой "каждый элемент не меньше всех предыдущих " тут нет никаких неоднозначностей и домысливаний.
Но ведь в нём каждый элемент имеет неопределёное значение. А для неопределённых значений неопределена операция "<".
Нельзя так свободно пользоваться отрицанием под квантором всеобщности. Отрицание превращает его в квантор существования.
Иными словами, если вы желаете указать, что к неопределённым элементам неприменима операция "<".- вам надо предъявить такой элемент, недостаточно сказать что они там все такие.
Ну я чисто с практической точки зрения.
irb(main):005> a = []
irb(main):006> a[0] < a[1]
(irb):6:in `<main>': undefined method `<' for nil:NilClass (NoMethodError)У вас в массиве нет 0 и 1 элементов, с чего вы вообще пытаетесь их сравнить? Условие "каждый последующий элемент не меньше предыдущего" ничего не требует относительно элементов с индексами 0 и 1 на пустом массиве.
Число практически пройдитесь по пустому массиву циклом и проверьте это условие в цикле.
У вас в массиве нет 0 и 1 элементов, с чего вы вообще пытаетесь их сравнить?
Так и я о том же. "каждый последующий элемент не меньше предыдущего". Как это понимать в случае с пустым массивом?
Условие "каждый последующий элемент не меньше предыдущего" ничего не требует относительно элементов с индексами 0 и 1 на пустом массиве.
КМК, это требует как минимум, их наличия. Если их нет, то какие могут быть дальнейшие рассуждения о них?
Иначе ведь к такому массиву одновременно применимо и условие "каждый последующий элемент не больше предыдущего".
Число практически пройдитесь по пустому массиву циклом и проверьте это условие в цикле.
Чисто практически это невозможно.
a.each_index { |i| puts a[i] < a[i+1] }
=> []Иначе ведь к такому массиву одновременно применимо и условие "каждый последующий элемент не больше предыдущего".
Совершенно верно. Поэтому пустой массив (как и массив из одного элемента) является отсортированным независимо от критерия сортировки - по возрастанию ли, по убыванию или с произвольным нетривиальным компаратором, неважно.
Чисто практически это невозможно.
Ну как же "невозможно", если вы ровно это и сделали в коде ниже? (Другой вопрос, что этот код не совсем верен, потому как на реальном отсортированном массиве в конце будет проверка something < nil, которая выбросит ошибку)
Ну как же "невозможно", если вы ровно это и сделали в коде ниже?
Разве? Я только попытался. Блок не выполнялся даже, значит проход по массиву не осуществлён.
Другой вопрос, что этот код не совсем верен, потому как на реальном отсортированном массиве в конце будет проверка
something < nil, которая выбросит ошибку
На заполненном массиве да, он не сработает. Но для пустого массива этот блок вообще не имеет смысла, так что без разницы на сколько верен там код.
Блок не выполнялся даже, значит проход по массиву не осуществлён.
Ну как это не осуществлён? Цикл же завершился. А то, что в нём не было ни одной итерации - это уже несущественно.
Вы с ним по разному смотрите на формулировку "каждый элемент ...". Он считает, что должен существовать хотя бы один элемент массива, к которому правило было бы успешно применено, а вы - нет.
Лично мне импонирует его вариант, а не ваш, ибо в случае с вашим любой пустой массив подходит под любую арбитрарную формулировку, например "каждый элемент массива должен присылать мне по 100 биткоинов". И пустой массив, по вашему мнению, это вполне реализует, что выглядит довольно абсурдно.
И тем не менее, математически это именно так - любое утверждение с квантором всеобщности (т.е. "каждый элемент имеет свойство X") тривиально верно для пустого множества, а значит, и для пустого массива.
Да, но чтобы в подтверждение своих слов можно было приводить некую математическую теорию, нужно сперва обоюдно договориться, что в контексте дискуссии это дозволено делать. Я бы, например, на такое определение не согласился, т.е. у меня свои собственные взгляды на логику.
И не только у меня, например, в шарповом фреймворке linq функция All() (да и Any() тоже) пошлет эту вашу математику нафиг, если в перечислении не будет ни одного элемента.
А разговор то наш алгоритмический гораздо ближе к программированию, нежели к математике.
И не только у меня, например, в шарповом фреймворке linq функция All() (да и Any() тоже) пошлет эту вашу математику нафиг, если в перечислении не будет ни одного элемента.
Да ну?
var seq = new int[0];
Console.WriteLine($"All: {seq.All(x => x > 0)}"); // true
Console.WriteLine($"Any: {seq.Any(x => x > 0)}"); // falseВсё в полном соответствии с правилами исчисления предикатов.
А при чём тут вообще границы массива?
Просто типовая ошибка у начинающего будет на пограничных случаях. Когда, скажем, все элементы больше или все элементы меньше. На то собственно тесты и нужны, чтобы покрывать всякие хитрые кейсы.
от кандидата требуют не "реши задачу". а "угадай, что я задумал".
Собственно на любом собеседовании так. Нарочито дают размытое объяснение, чтобы выяснить насколько кандидат в состоянии прояснить ситуацию задавая правильные вопросы. Очень полезный навык в разработке.
как может быть сортирован пустой массив.
А что не так? Пустой массив всегда отсортирован.
Интересно, почему кейс с несоответствием первого аргумента рассмотрен, а второго - нет..
Кажется интервьювер немного дурачок странный
Я когда начинал читать - то ожидал не два уровня, а побольше. Что на первом решают в лоб за один проход. На втором - двоичным поиском, а на третьем какая-нибудь магия вроде кода Грея или еще какой-то малоизвестной штуки. Увы, ожидания не оправдались.
Определите функцию f(a, x), которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки.
По формулировке вообще непонятно, что нужно сделать.
Я не совсем знаю, как именно у вас проходит собеседование, но по хорошему стоит предпреждать кандидатов об алгоритмической секции, т.к. много людей могут реализовать бинарный поиск, но по памяти это могут сделать довольно мало людей, т.к. по сути это бесполезное для работы знание. С тем же успехом можно просить людей реализовать быстрое преобразование Фурье или поиск в глубину/ширину. Да это покажет что собеседник разбирается в алгоритмах. Я согласен, что человек должен был бы сказать что тут нужно применить бинарный поиск и написать возможные тест кейсы, но на мой взгляд полезнее увидеть что человек понимает алгоритм и если что сможет его реализовать, а не просто выписать заученное решение с литкода, но если вы разрешаете гуглить во время собесов то это скорее норм, т.к. большую часть кода человек будет брать из готовых источников, либо хотя бы из готовых формул или схем
Я сам узнал об этом вопросе от коллеги из Google.
Я бы не хотел обижать, но для faang такие вопросы норма, т.к. они очень хорошо платят + есть шанс вырасти до зп 500к$+ и у них еще явно прописаны рекомендации для подготовки кандидатов. У нас во многих компаниях (не во всех), тоже тащат алгоритмическую практику, но кандидат узнает на собесе и само собой многие отсеиваются, т.к. ты пришел поговорить о работе, а тебя просят красно-черное и свою очередь, а ты последний раз сталкивался с таким на паре 10 лет назад и тебя не предупреждали что это будет нужно на собесе, ну как бы не совсем нормальное отношение к кандидату. В целом как бы собеседующий определяет вопросы, но по факту вы так можете потерять реально много подходящих кандидатов, но если вакансия просто для поиска хороших кадров, а работа не горит, то наверное такое "допустимо" делать
Надо вводить Литкод в ежедневную привычку, как зарядку. Проснулся - завтрак, урок в Дуолинго и задача в Литкод, а потом уже за работу)
реализовать надо максимально сложно и за один час! Предварительно самостоятельно догадавшись, что же реально хотел получить автор.
Внимание вопрос. Чего же реально хотел получить автор? Работника? Или мнение о себе, как о лице, даже не способного адекватно поставить задачу, и назначить на её решение адекватный срок реализации (точно уж не час).
Я не совсем знаю, как именно у вас проходит собеседование, но по хорошему стоит предпреждать кандидатов об алгоритмической секции
Это же собеседование в гугл. Там еще рекрутер выдает ссылку на книжки и курсы:
За время работы в Google я провёл более двух сотен интервью.
Довольно интересно, что вы рассматриваете в тест кейсах null в качестве некорректных данных, но не рассматриваете очевидный кейс - неотсортированный массив. А если массив проверять, то вся магия бинарного поиска сразу ломается, ибо проверка исходных данных все равно займет O(n). Поэтому применение бинарного поиска одновременно с проверкой всех граничных условий не имеет смысла - вы либо уверены в своих данных, либо нет.
Интересно послушать умников, на счет указания уже отсортированного массива в условиях задачи.
Как по мне - доверять такому можно, только если ты сам предварительно отсортировал его (как вариант получил из базы с order by).
Если данных мало - я бы еще раз его отсортировал для гарантии, а если много...
тем более: лопатить цифры неделю, чтобы потом оказалось, что входные данные были не нормализированы.
Ну, не обязательно. Бывают ситуации когда в одних данных мы уверены, а вот в других нет.
Как пример - массив мы получили из подконтрольной нам БД, отсортированный по индексу, и мы довольно уверенны в том что там нормальная сортировка. А другие параметры получили из реста, и тут нам прилететь может все что угодно.
Да на любой простой задачке можно на собеседовании развернуть такую кучу вопросов, уточнений и даже придирок, что это ничем не будет отличаться от описанной. Так что задача может быть в принципе любой, главное это разговоры вокруг про условия, про способы решения, про ревью и тесты, про производительность и другие особенности ну и т. д.
я бы начал искать с середины массива:
def find(a, x):
if not isinstance(a, list) or not len(a):
return -1
pos = len(a) // 2
step = 1
res = -1
if a[pos] > x:
step = -1
else:
res = a[pos]
while True:
pos += step
if pos == -1 or pos == len(a):
break
if a[pos] <= res:
return res
if a[pos] <= x and a[pos] > res:
res = a[pos]
return res
или на js:
function find(a, x) {
if (!Array.isArray(a) || a.length === 0) {
return -1;
}
let pos = a.length >> 1;
let step = 1;
let res = -1;
if (a[pos] > x) {
step = -1;
} else {
res = a[pos];
}
while (true) {
pos += step;
if (pos === -1 || pos === a.length) {
break;
}
if (a[pos] <= res) {
return res;
}
if (a[pos] <= x && a[pos] > res) {
res = a[pos];
}
}
return res;
}
А ваше решение имеет проблемы:
// про плюсы отбития блоков пустыми строками вы похоже не слышали
function f(f, a) {
// а что если здесь не массив а объект?
// кроме того условие и код в одну строчку это плохой стиль
if (a == null || a.length == 0) return -1;
// Общепринятая семантика это result, а не answer
// и почему var, а не let?
var answer = -1;
var low = 0;
var high = a.length — 1;
while(low <= high) {
// Нафига Math.floor? Битовый сдвиг проще: (low + high) >> 1
// и как то сложно, я таки не понимаю зачем это делать в цикле.
var mid = Math.floor((low + high) / 2);
if (a[mid] == x) {
return x;
}
// нафига тут else если перед ним return?
else if (a[mid] < x) {
answer = a[mid];
low = mid + 1;
} else {
high = mid — 1;
}
}
return answer;
}
В итоге я бы вас не взял с таким решением
Вы это серьёзно? Предлагаете заменить логарифмический алгоритм на линейный из-за проблем с … оформлением?! Да ещё и разновидности "вкусовщина"?
про плюсы отбития блоков пустыми строками вы похоже не слышали
От чего отбивать-то его предлагаете? Это ж начало блока кода...
кроме того условие и код в одну строчку это плохой стиль
Пока код короткий - сойдёт.
Если перенести тело на следующую строчку - то окажется, что не писать фигурные скобки - плохой стиль, а если написать ещё и фигурные скобки - это будет три строки на, в общем-то, избыточную проверку.
и почему var, а не let?
let при определённом положении звёзд может оказаться медленнее, в этом году даже пришлось стандарт править чтобы у браузеров появился шанс это замедление убрать.
Не то чтобы это замедление было и правда важно, но и считать использование var чем-то плохим в критичном к производительности коде не стоит.
Нафига Math.floor? Битовый сдвиг проще: (low + high) >> 1
Вот тут вы правы, Math.floor - тяжёлая операция, не фиг её делать лишний раз.
и как то сложно, я таки не понимаю зачем это делать в цикле.
А вот этого высказывания уже я не понимаю. low и high меняются между итерациями цикла, где ещё можно вычислить mid?
нафига тут else если перед ним return?
Чтобы подчеркнуть альтернативность трёх веток кода.
я нигде не предлагал заменить предложенный алгоритм на мой. Просто написал простой алгоритм который первый пришел в голову, а потом рассмотрел предложенное решение. Не надо выдумывать.
код должен легко читаться, отбивки помогают этому, и это прописано в довольно большем количестве коудстайлов. Если человек не думает о читатебельности этого кода, я бы не стал его брать
дополнительный нестинг усложняет читабельность, это всем известный факт который указан в книках по рефакторингу.
Вы так и не ответили, откуда именно вы собрались отбивать функцию f.
дополнительный нестинг усложняет читабельность, это всем известный факт который указан в книках по рефакторингу.
Это всего лишь вкусы авторов книг по рефакторингу.
я имел в виду отбитие блоков внутри функции.
хорошая практика что любой блок который занимает более одной строки отбивается пустыми строками. Хорошая практика никогда не писать if (foo) return 1, читается проще.
Как-то так:function f(x, a) {
if (!Array.isArray(a) || a.length === 0) {
return -1;
}
let result = -1;
let low = 0;
let high = a.length — 1;
let mid;
while (low <= high) {
mid = (low + high) >> 1;
if (a[mid] == x) {
return x;
}
if (a[mid] < x) {
result = a[mid];
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
Обратите внимание, что я также вынес объявление mid за пределы цикла.
P.S. Ну да, авторы руководств по рефакторингу дураки, а вы нет.
Отбивать цикл от переменных цикла - глупо, это один логический блок.
Из трёх альтернативных веток кода отбивать одну от двух других - тоже глупо. Вы же блок if от else не отбили? Тогда почему ветка ==x оказалось отбита от ветки <x?
С необходимостью отбить return result; я бы тоже поспорил, это логическое завершение цикла.
Осталось два места где можно поставить пустые строки - после входной проверки размера массива, и после вычисления mid. Но вторую я бы тоже не ставил, поскольку она разорвёт пополам единый цикл, и вообще вычисление mid можно считать частью последующего сравнения.
PS иронично, что в попытке указать другим на недостатки в оформлении кода, вы упустили из своего кода все отступы.
так. еще раз по пунктам.
в приведенном решении есть несколько проблем:
1) код плохо читается
2) нет проверки на то что входное значение может быть не только null но и чем угодно, например объектом или строкой
3) использован тяжелый метод Math.floor
4) одна из переменных объявлена внутри цикла, что лишние
5) код не универсален, следовало бы оформить его чтобы мможно было переиспользовать с любым компаратором.
Поэтому конечно я бы не стал брать автора. То что я бы его не взял исключительно из-за нечитаемости кода, это ваши выдумки
p.s. и да, вы придрались к парсеру хабра, а не ко мне.
код плохо читается
Код читается достаточно хорошо для понимания. Можно и лучше, но приведённого автором оформления достаточно.
Для сравнения, ваш код из комментария чуть выше читается ужасно. И нефиг гнать на парсер Хабра, его синтаксис и раньше был не сильно сложным в освоении, а уж в WYSIWYG-то редакторе лепить подобные отмазки должно быть стыдно.
одна из переменных объявлена внутри цикла, что лишние
Почему? В какой книге по рефакторингу вы вычитали, что объявлять переменные внутри цикла - плохо?
код не универсален, следовало бы оформить его чтобы мможно было переиспользовать с любым компаратором
Этот пункт вы вообще только сейчас упомянули.
В редакторе код выглядел нормально и там были отступы. Даже при последующем редактировании. Кроме того вы спросили где бы я добавил пустые строки, я вам показал. Так что ваши придирки к отсутствию индентации не имеют никакого отношения к обсуждаемому предмету.
Потому что нефиг рассчитывать на оптимизатор, я хз будет ли он выделять память для переменной каждый раз или сможет оптимизировать и вынести выделение памяти за пределы цикла. Это база, мой друг.
Я не пишу на js и с утра не было времени чекнуть есть ли там готовый метод findLast в js и если нет писать его реализацию. А он есть и соответственно весь этот код превращается в велосипед.
Потому что нефиг рассчитывать на оптимизатор, я хз будет ли он выделять память для переменной каждый раз или сможет оптимизировать и вынести выделение памяти за пределы цикла. Это база, мой друг.
А вот если бы использовали var - такого вопроса бы не стояло.
А вообще, звучит не как "база", а как глупость.
Ну зачем мы меня заставляете объяснять базовые вещи?
Использование var потенциально может привести к багам, если кто-то будет дорабатывать эту функции и заюзает переменную mid выше цикла и не обратит внимание на то что она используется где-то там в ниже в цикле и будет соответсвенно ожидать то значение которое было туда записано до цикла.
references:
https://hackernoon.com/why-you-shouldnt-use-var-anymore-f109a58b9b70
https://dev.to/mindninjax/stop-using-var-for-declaring-variables-2p3a
Вы так пишете, как будто с вынесенным из цикла let не будет точно такой же проблемы.
И да, иронично что по первой из ваших ссылок во всех примерах кода весь код записан в одну строку. Видимо, тоже парсер Хабра виноват.
ну вот вам пример
function foo() {
var x = 1;
const arr = [1, 2, 3, 4, 5];
for (let i = 0; i < 5; i++) {
var x = arr[i];
}
console.log(x);
}
function bar() {
let x = 1;
const arr = [1, 2, 3, 4, 5];
for (let i = 0; i < 5; i++) {
let x = arr[i];
}
console.log(x);
}
foo();
bar();
$ node 1.js
5
1
А теперь вынесите-ка let из второго цикла, чтобы память лишнюю не выделять!
function bar() {
let x = 1;
const arr = [1, 2, 3, 4, 5];
let x;
for (let i = 0; i < 5; i++) {
x = arr[i];
}
console.log(x);
}
$ node 1.js
1.js:5
let x;
^
SyntaxError: Identifier 'x' has already been declared
т.е. не получится допустить баг, будет показана явная ошибка при запуске, что я и имел в виду
Вот только что именно сделает тот самый гипотетический абсолютно невнимательный человек, который эту ошибку увидит? Использует ли он другое имя для переменной, или просто удалит строку let x;?
нормальный человек использует другую переменную, потому что ошибка максимальна ясна и понятна.
про других я не скажу, может быть всякое.
А вот кейс с var плох тем что var x = something; может назначаться не всегда, а быть еще и завернута в if, который срабатывает только при каких-то редких обстоятельствах, так что код с ошибкой пройдет и ручное тестирование, и автотесты если они не покрывают тот самый редкий if и выстрелит у вас в продакшине. Лично подтверждаю что видел не один такой случай.
Вы сейчас пишете про какой-то загадочный абстрактный код, в то время как обсуждается конкретный бинарный поиск.
я думал мы обсуждаем почему не стоит использовать var, поскольку вы написали "А вот если бы использовали var - такого вопроса бы не стояло."
я сейчас потестировал код предложенный автором на node v14 которая была под рукой. Так вот, если заменить var на let, он работает быстрее.
что касается бинарного поиска, то вот вам мой вариант, он медленнее чем код автора, но наверное если потратить чуть больше времени, можно сделать его быстрее
function find(a, x) {
if (!Array.isArray(a) || a.length === 0) {
return -1;
}
let result = -1;
let len = a.length;
let pos = len >> 1;
while (pos < len) {
if (a[pos] == x) {
return x;
}
if (a[pos] < x) {
result = a[pos];
pos += ((len - pos) >> 1) || 1;
continue;
}
if (pos > 0) {
len = pos;
pos >>= 1;
} else {
break;
}
}
return result;
}
в общем вот вам код которым и который я тестировал:
отсутствие ошибок и корректность метода тестирования не гарантирую, я просто развлекался в свбодное время
// Orignal version but with bits shift
function fv0(a, x) {
if (a == null || a.length == 0) return -1;
var answer = -1;
var low = 0;
var high = a.length - 1;
while(low <= high) {
var mid = (low + high) >> 1;
if (a[mid] == x) {
return x;
} else if (a[mid] < x) {
answer = a[mid];
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
// Let's use let instead of var
function fv1(a, x) {
if (a == null || a.length == 0) return -1;
let answer = -1;
let low = 0;
let high = a.length - 1
while(low <= high) {
let mid = (low + high) >> 1;
if (a[mid] == x) {
return x;
} else if (a[mid] < x) {
answer = a[mid];
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
// Let's declare mid outside of loop
function fv2(a, x) {
if (a == null || a.length == 0) return -1;
let answer = -1;
let low = 0;
let high = a.length - 1
let mid;
while(low <= high) {
mid = (low + high) >> 1;
if (a[mid] == x) {
return x;
} else if (a[mid] < x) {
answer = a[mid];
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
// My version
function fv3(a, x) {
if (!Array.isArray(a) || a.length === 0) {
return -1;
}
let result = -1;
let len = a.length;
let pos = len >> 1;
while (pos < len) {
if (a[pos] == x) {
return x;
}
if (a[pos] < x) {
result = a[pos];
pos += ((len - pos) >> 1) || 1;
continue;
}
if (pos > 0) {
len = pos;
pos >>= 1;
} else {
break;
}
}
return result;
}
// Let's test
let a = [];
let t0 = 0;
let t1 = 0;
let t2 = 0;
let t3 = 0;
for (let i = 0; i < 1000000; i++) {
for (j = 0; j < 1000; j++) {
a[j] = Math.round(Math.random() * 100);
}
a.sort((a, b) => {
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
})
let x = Math.round(Math.random() * 100);
let startTime = Date.now();
let r0 = fv0(a, x);
let endTime = Date.now();
t0 += (endTime - startTime);
startTime = Date.now();
let r1 = fv1(a, x);
endTime = Date.now();
t1 += (endTime - startTime);
startTime = Date.now();
let r2 = fv2(a, x);
endTime = Date.now();
t2 += (endTime - startTime);
startTime = Date.now();
let r3 = fv3(a, x);
endTime = Date.now();
t3 += (endTime - startTime);
if (r3 != r0) {
console.error(a.join(','), 'x=' + x, 'author=', r0, 'me=', r3);
}
}
console.log("original version", t0);
console.log("original version with let", t1);
console.log("original version with declared mid outside of the loop", t2);
console.log("my version", t3);
OUTPUT:
original version 83
original version with let 71
original version with declared mid outside of the loop 52
my version 61
немножко переделал свой код:
function fv3(a, x) {
if (!Array.isArray(a) || a.length === 0) {
return -1;
}
let result = -1;
let len = a.length;
let pos = len >> 1;
while (pos < len) {
if (a[pos] == x) {
return x;
}
if (a[pos] < x) {
result = a[pos];
pos += ((len - pos) >> 1) || 1;
} else if (pos > 0) {
len = pos;
pos >>= 1;
} else {
return result;
}
}
return result;
}и прогнал 2000000 итераций для строки размером 2000, в этот раз версия с let внутри цикла, как ни странно, оказалась быстрее всех, первая версия которая приходит в голову это особенности GC
original version 143
original version with let 116
original version with declared mid outside of the loop 123
my version 120
Тут числа от запуска к запуску прыгают чуть ли не в полтора раза, их бесполезно сравнивать.
хорошо, я немного переделал бенчмарк чтобы он работал быстрее и надежнее добавил еще один вариант. Таки получается что var всегда медленнее чем let:
// Orignal version but with bits shift
function fv0(a, x) {
if (a == null || a.length == 0) return -1;
var answer = -1;
var low = 0;
var high = a.length - 1;
while(low <= high) {
var mid = (low + high) >> 1;
if (a[mid] == x) {
return x;
} else if (a[mid] < x) {
answer = a[mid];
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
// Let's user let instead of var
function fv1(a, x) {
if (a == null || a.length == 0) return -1;
let answer = -1;
let low = 0;
let high = a.length - 1
while(low <= high) {
let mid = (low + high) >> 1;
if (a[mid] == x) {
return x;
} else if (a[mid] < x) {
answer = a[mid];
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
// Let's declare mid outside of loop
function fv2(a, x) {
if (a == null || a.length == 0) return -1;
let answer = -1;
let low = 0;
let high = a.length - 1
let mid;
while(low <= high) {
mid = (low + high) >> 1;
if (a[mid] == x) {
return x;
} else if (a[mid] < x) {
answer = a[mid];
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
// Let's declare mid outside of loop and initialize it
function fv3(a, x) {
if (a == null || a.length == 0) return -1;
let answer = -1;
let low = 0;
let high = a.length - 1
let mid = 0;
while(low <= high) {
mid = (low + high) >> 1;
if (a[mid] == x) {
return x;
} else if (a[mid] < x) {
answer = a[mid];
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
// My version
function fv4(a, x) {
if (a == null || a.length == 0) {
return -1;
}
let result = -1;
let len = a.length;
let pos = len >> 1;
while (pos < len) {
if (a[pos] == x) {
return x;
}
if (a[pos] < x) {
result = a[pos];
pos += ((len - pos) >> 1) || 1;
} else if (pos > 0) {
len = pos;
pos >>= 1;
} else {
return result;
}
}
return result;
}
// Let's test
let a = [];
let t0 = 0;
let t1 = 0;
let t2 = 0;
let t3 = 0;
let t4 = 0;
let startTime;
let endTime;
for (j = 0; j < 4096; j++) {
a[j] = Math.round(Math.random() * 1000);
}
a.sort((a, b) => {
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
})
for (let i = 0; i < 100000000; i++) {
let x = Math.round(Math.random() * 1000);
startTime = Date.now();
let r0 = fv0(a, x);
endTime = Date.now();
t0 += (endTime - startTime);
startTime = Date.now();
let r1 = fv1(a, x);
endTime = Date.now();
t1 += (endTime - startTime);
startTime = Date.now();
let r2 = fv2(a, x);
endTime = Date.now();
t2 += (endTime - startTime);
startTime = Date.now();
let r3 = fv3(a, x);
endTime = Date.now();
t3 += (endTime - startTime);
startTime = Date.now();
let r4 = fv4(a, x);
endTime = Date.now();
t4 += (endTime - startTime);
if (r4 != r0) {
console.error(a.join(','), 'x=' + x, 'author=', r0, 'me=', r4);
}
}
console.log("original version", t0);
console.log("original version with let", t1);
console.log("original version with declared mid outside of the loop", t2);
console.log("original version with declared and initizalized mid outside of the loop", t3);
console.log("my version", t4);
node 1.js && node 1.js && node 1.js && node 1.js && node 1.js
original version 6730
original version with let 6398
original version with declared mid outside of the loop 6236
original version with declared and initizalized mid outside of the loop 6704
my version 7701
original version 6846
original version with let 6405
original version with declared mid outside of the loop 6326
original version with declared and initizalized mid outside of the loop 6493
my version 7682
original version 7000
original version with let 6448
original version with declared mid outside of the loop 6250
original version with declared and initizalized mid outside of the loop 6497
my version 7528
original version 6988
original version with let 6422
original version with declared mid outside of the loop 6395
original version with declared and initizalized mid outside of the loop 6508
my version 7566
original version 6887
original version with let 6373
original version with declared mid outside of the loop 6310
original version with declared and initizalized mid outside of the loop 6608
my version 7677
вот автора такого решения я бы наверное взял :)
https://habr.com/ru/companies/ispsystem/articles/779224/#comment_26248196
2) нет проверки на то что входное значение может быть не только null но и чем угодно, например объектом или строкой
Ну тогда уж надо проверить, что это массив чисел, и что он отсортирован по возрастанию.
вообще в последних версиях js есть метод findLast, так что еще один минус автору за изобретение велосипеда. И даже если метода нет, то возможно не стоило выпендриваться, а стоило писать что-то (я не тестировал но кажется должно работать):
const findLastIndex = (array, comparator) => {
// или любой алгоритм по вкусу
for (let i = array.length - 1; i >= 0; i--) {
if (comparator(array[i])) {
return i;
}
}
return -1;
}
function find(a, x) {
if (!Array.isArray(a) || a.length === 0) {
return -1;
}
const result = a[findLastIndex(a, i => i <= x)];
return result == undefined ? -1 : result;
}findLast - O(n).
а вот это действительно печально.
Вот версия для всех случаев, сложность O(log N), точнее кажется O(log2 N) поскольку мы ищем строго первый или последний элемент в массиве в котором значения могут повторяться, в оригнальном алгоритме который автор видимо списал из википедии ищеться первое попавшеся значение, поэтому там действительно O(log N)
// arr: An array that must be sorted in ascending order.
// cmp: A comparator function(a) or a target value.
//
// The comparator function should be defined to take a single argument 'a'
// and compare it internally:
// It should return -1 if 'a' is less than a reference value;
// It should return 0 if 'a' is equal to a reference value;
// It should return 1 if 'a' is greater than a reference value;
//
// If 'cmp' is not a function, it is treated as a target value against
// which elements of 'arr' are compared.
function createComparator(x) {
return function(a) {
if (a < x) {
return -1;
}
if (a > x) {
return 1;
}
return 0;
}
};
function _getComparator(arg) {
if (typeof arg === 'function') {
return arg;
}
return createComparator(arg);
}
function findLastIndexEqual(arr, cmp) {
cmp = _getComparator(cmp);
let len = arr.length;
let pos = len >> 1;
let result = -1;
let start = 0;
while (pos >= start && pos < len) {
if (cmp(arr[pos]) === 0) {
result = start = pos;
pos += (len - pos) >> 1 || 1;
} else if (cmp(arr[pos]) > 0) {
len = pos;
pos = start + (((pos - start) >> 1) || pos - 1);
} else {
pos += (len - pos) >> 1 || 1;
}
}
return result;
}
function findLastIndexLessOrEqual(arr, cmp) {
cmp = _getComparator(cmp);
let len = arr.length;
let pos = len >> 1;
let result = -1;
let start = 0;
while (pos >= start && pos < len) {
if (cmp(arr[pos]) <= 0) {
result = start = pos;
pos += (len - pos) >> 1 || 1;
} else {
len = pos;
pos = start + (((pos - start) >> 1) || pos - 1);
}
}
return result;
}
function findLastIndexLess(arr, cmp) {
cmp = _getComparator(cmp);
let len = arr.length;
let pos = len >> 1;
let result = -1;
let start = 0;
while (pos >= start && pos < len) {
if (cmp(arr[pos]) < 0) {
result = start = pos;
pos += (len - pos) >> 1 || 1;
} else {
len = pos;
pos = start + (((pos - start) >> 1) || pos - 1);
}
}
return result;
}
function findFirstIndexEqual(arr, cmp) {
cmp = _getComparator(cmp);
let len = arr.length;
let pos = len >> 1;
let result = -1;
let start = 0;
while (pos >= start && pos < len) {
if (cmp(arr[pos]) === 0) {
result = pos;
len = pos;
pos = start + (((pos - start) >> 1) || pos - 1);
} else if (cmp(arr[pos]) > 0) {
len = pos;
pos = start + (((pos - start) >> 1) || pos - 1);
} else {
start = pos;
pos += (len - pos) >> 1 || 1;
}
}
return result;
}
function findFirstIndexGreaterOrEqual(arr, cmp) {
cmp = _getComparator(cmp);
let len = arr.length;
let pos = len >> 1;
let result = -1;
let start = 0;
while (pos >= start && pos < len) {
if (cmp(arr[pos]) >= 0) {
result = pos;
len = pos;
pos = start + (((pos - start) >> 1) || pos - 1);
} else {
start = pos;
pos += (len - pos) >> 1 || 1;
}
}
return result;
}
function findFirstIndexGreater(arr, cmp) {
cmp = _getComparator(cmp);
let len = arr.length;
let pos = len >> 1;
let result = -1;
let start = 0;
while (pos >= start && pos < len) {
if (cmp(arr[pos]) > 0) {
result = pos;
len = pos;
pos = start + (((pos - start) >> 1) || pos - 1);
} else {
start = pos;
pos += (len - pos) >> 1 || 1;
}
}
return result;
}Если оно O(n), никто не мешает закодить нечто вроде такого, у меня это заняло два часа. Нужно еще два часа потратить чтобы убрать лишние итерации, но мне честно говоря лень. Но факт то что написать бинарный поиск с компараторами это не проблема. Использовать с осторожностью, тестировал каждый кейс на рандомных строках длинной 400 символов со значениям [0..99] и рандомных значениях x в тех же пределах, в качестве эталона использовал простейший перебор, для каждого кейса делал 1 000 000 итераций, вроде ошибок не нашлось.
// Array must be sorted in asending order
// Comparator must return:
// < 0 if value less than expected;
// 0 if value is equal to excepted
// > 0 if value is greater than expected
function findLastIndexEqual(arr, cmp) {
let len = arr.length;
let pos = len >> 1;
let result = -1;
while (pos > -1 && pos < len) {
if (cmp(arr[pos]) === 0) {
result = pos;
pos += (len - pos) >> 1 || 1;
} else if (cmp(arr[pos]) > 0) {
len = pos;
pos = pos >> 1 || pos - 1;
} else {
pos += (len - pos) >> 1 || 1;
}
}
return result;
}
function findLastIndexLessOrEqual(arr, cmp) {
let len = arr.length;
let pos = len >> 1;
let result = -1;
while (pos > -1 && pos < len) {
if (cmp(arr[pos]) <= 0) {
result = pos;
pos += (len - pos) >> 1 || 1;
} else {
len = pos;
pos = pos >> 1 || pos - 1;
}
}
return result;
}
function findLastIndexLess(arr, cmp) {
let len = arr.length;
let pos = len >> 1;
let result = -1;
while (pos > -1 && pos < len) {
if (cmp(arr[pos]) < 0) {
result = pos;
pos += (len - pos) >> 1 || 1;
} else {
len = pos;
pos = pos >> 1 || pos - 1;
}
}
return result;
}
function findFirstIndexEqual(arr, cmp) {
let len = arr.length;
let pos = len >> 1;
let result = -1;
while (pos > -1 && pos < len) {
if (cmp(arr[pos]) === 0) {
result = pos;
len = pos;
pos = pos >> 1 || pos - 1;
} else if (cmp(arr[pos]) > 0) {
len = pos;
pos = pos >> 1 || pos - 1;
} else {
pos += (len - pos) >> 1 || 1;
}
}
return result;
}
function findFirstIndexGreaterOrEqual(arr, cmp) {
let len = arr.length;
let pos = len >> 1;
let result = -1;
while (pos > -1 && pos < len) {
if (cmp(arr[pos]) >= 0) {
result = pos;
len = pos;
pos = pos >> 1 || pos - 1;
} else {
pos += (len - pos) >> 1 || 1;
}
}
return result;
}
function findFirstIndexGreater(arr, cmp) {
let len = arr.length;
let pos = len >> 1;
let result = -1;
while (pos > -1 && pos < len) {
if (cmp(arr[pos]) > 0) {
result = pos;
len = pos;
pos = pos >> 1 || pos - 1;
} else {
pos += (len - pos) >> 1 || 1;
}
}
return result;
}
function createComparator(x) {
return function(a) {
if (a < x) {
return -1;
}
if (a > x) {
return 1;
}
return 0;
}
};
a = [ 3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21 ];
console.log(a[findLastIndexLessOrEqual(a, createComparator(12))]);
console.log(a[findLastIndexLessOrEqual(a, createComparator(13))]);
console.log(a[findLastIndexLessOrEqual(a, createComparator(2))]);
console.log(a[findLastIndexLessOrEqual(a, createComparator(22))]);
console.log(a[findLastIndexLessOrEqual(a, createComparator(3))]);
console.log(a[findLastIndexLessOrEqual(a, createComparator(21))]);
в этом году даже пришлось стандарт править чтобы у браузеров появился шанс это замедление убрать.
Расскажите подробней?
Так, я ошибся, стандарт ещё не правили. Но собираются.
Это из сентябрьского митинга TC39: презентация, протокол
Summary
Years after ES6, let and const still commonly cause performance regressions vs var, and transpilers do not implement TDZ. The result is that let and const are avoided in shipped JS code.
Generally, if the committee cares about its features being adoptable, these sorts of 5+-year retrospectives will be important.
SYG proposes treating some or all cases of TDZ as simply evaluating to undefined, as var does.
Most of the committee agreed with the goal of ensuring that features like this are adoptable in practice, but there was no consensus on whether semantics changes to support that are needed.
Conclusion
A proposal may be formed on this topic in the future
Если я правильно понял, то это касается только не инициализованных значений объявленных с помощью let?
Напрямую это касается переменных, объявленных через let посреди блока, но использованных в замыкании до этого момента:
const fn = () => console.log(x);
// fn() - ошибка
let x = 5;
fn(); // а так нормальноНо вот сама возможность подобного обращения и необходимость её отслеживать может повлиять хоть вообще на все переменные, тут всё зависит от глупости оптимизатора.
и на этом основании вы выше посоветовали не использовать let вместо var?
На этом основании я посоветовал не спешить переписывать все var на let.
ну потестируйте код автора сами с var и let, и скажите есть там проблемы с производительность в случае let? Я вот потестировал не нашел никаких проблем. Также я вам объяснил почему var лучше не использовать и даже ссылки дал на материалы по этому поводу, а вы даже отвечать не стали. Судя по всему в жизни вы человек крайне не приятный и мне чет стало совсем неприятно с вами общаться. На этом прощаюсь и желаю вам поумнеть и стать добрее.
Вот тут вы правы, Math.floor - тяжёлая операция, не фиг её делать лишний раз.
Но и складывать индексы идея не лучшая, может возникнуть переполнение. Об этом в статье написано.
p.s не сразу понял что под простейшей реализацией автор все таки имел в виду двоичный поиск. и также не сразу понял что перевод. также я я не имел в виду что мое решение лучше, я его написал до того как прочитал код в качестве начального варианта который должен быть быстрее простого перебора.
Если бы я дальше работал бы над кодом то разумеется получился бы бинарый поиск
и получилось бы в итоге у меня что-то типа такого:
function find(a, x) {
if (!Array.isArray(a) || a.length === 0) {
return -1;
}
let result = -1;
let len = a.length;
let pos = len >> 1;
while (pos < len) {
if (a[pos] == x) {
return x;
}
if (a[pos] < x) {
result = a[pos];
pos += (len - pos) >> 1 || 1;
continue;
}
if (pos > 0) {
len = pos;
pos >>= 1;
} else {
break;
}
}
return result;
}Этот алгоритм попросту неправильный, вы теряете левую границу и в итоге делаете лишние итерации.
мне кажется вы ошибаетесь, посмотрите пожалуйста вот этот мой коммент https://habr.com/ru/companies/ispsystem/articles/779224/comments/#comment_26245396 - я там в сравниваю результаты на рандомных данных с результатами оригинального алгоритма предложенного автором, расхождений в результатах функции не выявляется
Если вы считаете что алгоритм таки неверный, предложите тесткейс который это докажет. Если все так как вы говорите, это должно быть легко
понял о чем вы, действительно там есть лишние итерации
или например вот так тоже неплохо
function fv4o(a, x) {
let result = -1;
let end = (a || []).length;
let start = 0;
let pos = end >> 1;
while (pos < end && result != x) {
if (a[pos] > x) {
end = pos;
pos = ((end - start) >> 1) + start;
continue;
}
result = a[pos];
start = pos;
pos = ((end - start) >> 1 || 1) + start;
}
return result;
}
ок, таки нашел время и сделал версию которая меня вроде устраивает, но еще можно поработать и оптимизировать
function fv4o(a, x) {
if (a == null || a.length == 0) {
return -1;
}
let result = -1;
let end = a.length;
let start = 0;
let pos = end >> 1; // Relative position
let abspos = pos; // Absolute position
let item = 0;
while (abspos < end) {
item = a[abspos];
if (item == x) {
return x;
}
if (item <= x) {
result = item;
start = abspos;
} else {
end = abspos;
}
pos = (end - start) >> 1 || 1;
abspos = pos + start;
}
return result;
}
Поскольку практически все ваши “претензии” автору основаны на ваших же вкусовых предпочтениях, я не буду устраивать критику этой “критике”, это пустое. Но о том, что бросилось в глаза, таки спрошу:
// а что если здесь не массив а объект?
Возьмём в качестве примера код, который используется буквально везде — стандартную библиотеку C. Выбирайте на свой вкус, самые популярные — BSD libc, GNU glibc, musl. Загляните в исходный код практически любой функции модуля string.h.
Вот несколько примеров:
char *
strcat(char * __restrict s, const char * __restrict append)
{
char *save = s;
for (; *s; ++s);
while ((*s++ = *append++));
return(save);
}
int
strcmp(const char *s1, const char *s2)
{
while (*s1 == *s2++)
if (*s1++ == '\0')
return (0);
return (*(const unsigned char *)s1 - *(const unsigned char *)(s2 - 1));
}
char *
strdup(const char *str)
{
size_t len;
char *copy;
len = strlen(str) + 1;
if ((copy = malloc(len)) == NULL)
return (NULL);
memcpy(copy, str, len);
return (copy);
}Не смущает, что нигде не проверяется, являются ли “строками” входящие “строки”? Если хотите, могу очень доступно объяснить, почему не проверяется.
А в вашем коде я вижу одну из причин того, почему многие современные приложения такие “тяжёлые”, веб-страницы с тремя параграфами текста и парой кнопок грузят свои десятки мегабайт по несколько секунд, и прочий code bloating. Ваш код делает работу, которая никому не нужна, которой не было в ТЗ, вы не делаете отличий между generic-кодом и частным случаем, вы возводите свои весьма поверхностные представления о безопасности кода в безумный абсолют “все параметры всех функции должны быть проверены на всё”.
В итоге я бы вас не взял с таким решением
я пока не опубликовал финальное решение. то что в посте указано то что входной параметр массив или null я не заметил, это довольно странное условие в случае js. Но кстати его код проверяет еще и на undefined не очевидным образом, чего не было в условиях задачи. По поводу libc я не скажу что это хороший код, там много трэша. Вот посморите на getaddrinfo, https://codebrowser.dev/glibc/glibc/sysdeps/posix/getaddrinfo.c.html, разве это похоже на хороший код? Но даже там условия и циклы часто отбиты.
По поводу
if (foo ) {
}
явные начало и конец блока лучше чем не явные, читать проще и меньше ошибок в итоге
А теперь сравните с кодом из скажем ZFS https://github.com/openzfs/zfs/blob/master/module/avl/avl.c
По поводу кода предложенного автором - там вообще нет ни одной отбивки, все единым блоком кода. То есть явные проблемы с читаемостью. Даже в ваших примерах из glibc есть отбивки
и вообще разве отбивки это основное? Там блин var!!! и Math.floor!!!. Этого уже достаточно кмк
Вот вам мой допиленный вариант:
function fv4o(a, x) {
if (a == null || a.length == 0) {
return -1;
}
let result = -1;
let end = a.length;
let start = 0;
let relpos = end >> 1; // Relative cursor position from start
let abspos = relpos; // Absolute cursor position
let item;
while (abspos < end) {
item = a[abspos];
if (item == x) {
return x;
}
if (item <= x) {
result = item;
start = abspos;
} else {
end = abspos;
}
relpos = (end - start) >> 1 || 1;
abspos = relpos + start;
}
return result;
}ну вот вам еще такое решение
function fv4o(a, x) {
let result = -1;
let end = (a || []).length;
let start = 0;
let pos = end >> 1;
while (pos < end && result != x) {
if (a[pos] > x) {
end = pos;
pos = ((end - start) >> 1) + start;
continue;
}
result = a[pos];
start = pos;
pos = ((end - start) >> 1 || 1) + start;
}
return result;
}
}
Хорошее решение на мой взгляд выглядело бы как-то так:
https://habr.com/ru/companies/ispsystem/articles/779224/#comment_26248196
Не смущает, что нигде не проверяется, являются ли “строками” входящие “строки”?
А как это вообще проверить в C?
нафига тут else если перед ним return?
А если однажды код изменится и там будет не return? Если одно условие должно исключать другое, лучше "пере", чем "недо".
Конечно, я не про конкретно этот случай с простым условием, а вообще.
// Нафига Math.floor? Битовый сдвиг проще: (low + high) >> 1
А разве low + high тут в общем случае не могут вылезти за пределы int32?
тут вы правы.
js он реально местами странноватый
4294967290 + 4294967295
8589934585 // переполнения нет
4294967290 >> 1
-3 // переполнение есть
но как оказывается есть специальные битовые операторы о которых я не был в курсе >>> и <<<:
(4294967290 + 4294967290) >>> 1
2147483642
что тоже как ни странно дает неправильный результат.
Вот так вроде ок
(4294967290>>>1) + (4294967290>>>1)
Так вы потеряли единицу при сложении нечётных чисел.
И если на больших числах эта единица ни на что не влияет, то вот при попытке найти середину между 1 и 3 у вас получается 1. А серединой между 1 и 1 и вовсе оказывается 0, хорошо хоть при тройных ветвлениях такая середина никогда не вычисляется.
Правильная формула приведена в статье, её только поправить надо:
low + (high — low) >>> 1;Оператор >>> тоже даёт переполнение. Присмотритесь внимательнее, разве похоже число 2147483642 на середину между 4294967290 и 4294967290?
Вся разница в том, что >> интерпретирует левый операнд как знаковый, а >>> - как беззнаковый. Кстати, они этот оператор не придумали, а взяли из Java.
Штука в том что вообще number - это 64-битовое число с плавающей точкой, но для побитовых операций он приводится к int32. Т.е. целочисленное деление на 2 побитовым сдвигом возможно без потерь только если делимое (его целая часть) влезает в 32 бита.
Согласно спекам array.length является uint32, тогда выходит сумма двух индексов массива может выйти за 32 бита.
Я бы использовал Math.trunc((low + high) / 2 ), в статье используется Math.floor что для положительного числа даст тот же результат (индексы же - значит положительное), но по-моему это хуже с точки зрения семантики .
Исходя из посталвенных условий это скорее задача для определения нахождления кандидата на 1 волне с вами и угадывает ли он что вы от него хотите.
Я в другом подобном обсуждении уже писал, что когда у вас, как у FAANG, за воротами очередь кандидатов стоит и когда у вас десятки тысяч сотрудников - можно позволить себе отбирать тех, на одной волне с командой. А потом уже смотреть как они код писать умеют.
В итоге собрать гомогенную команду в которой все радостно думают одинаково, совершают одинаковые ошибки, и не способны их друг у друга заметить. Все получают триста какосеков, а сайты с текстом и двумя картинками потом грузятся по 7 секунд.
Пока это не влияет на бизнес - нет проблемы (ну кроме как для пользователей). А у гугла бизнес идет хорошо т.к. они заняли определенную нишу и по факту никто туда уже влезть не может. А свежие идеи они покупают вместе с командами. Т.е. изнутри инновации не особо нужны.
Бизнес гугла настолько большой, что им уже нет разницы, ничего из разработки не будет на него влиять в короткой перспективе. Если они уволят всех разрабов и наймут курицу с отрубленной головой которая бегает по клавиатуре, бизнес будет приносить прибыль еще очень долго.
Что, возвращаясь к топику, не добавляет уверенности в том что их рекрутерские практики хороши и их надо копировать.
Порой, по разным причинам, мы получаем друг от друга ложные или неточные сигналы.
И далее по тексту выясняется, что от интервьюера все сигналы по умолчанию кошерные, а не прав может быть только кандидат.
Тут многие в примерах смело используют функцию вычисления длины массива, но в некоторых языках это уже просмотр всего массива.
Тогда это уже не массив. Это или нуль-терминэйтед стринг или связный список или еще что-то, но не массив.
В С как раз массив так и хранят как нуль-терминетед последовательность указателей. Иногда. Но можно и не так.
Но если часто что-то сортировать, то наверно лучше хранить в дереве или еще как. И тогда задачка станет совсем другой. ))
Я всегда думал что в С массив это указатель на первый элемент. И никаких нуль терминетед и в помине нет, что malloc выдаст так и будет.
Вы со строками путаете. Нет никаких нул-терминаторов в массиве. Даже если у вас двумерный массив указателями на указатели - передают везде размер массива.
Чем должен оканчиваться массив интов в вашем представлении? Хуем моржовым?
Зачем вы продолжаете спорить о том, в чём явно не разбираетесь?
int result = a.LastOrDefault(n => n < x);
if (result == 0) result = -1;
return result
Кажется, я уложился в 30 строчек.
Делать сходу двоичный поиск, без требований - это признак незрелости программиста. Premature optimization.
Оптимизация делается ТОЛЬКО по результатам замеров и профилирования. Иначе алгоритмы усложняются и код становится нечитаемым. А читаемость кода для львиной части кода гораздо важнее скорости.
Можно даже в одну строку (плюс корректная обработка нулей в исходном массиве).
a.LastOrDefault(n => n <= x, -1);
Выбор алгоритма - это не преждевременная оптимизация. Если везде все писать как попало, то у профайлер вам ничего не покажет - будет равномерно тормозить вообще все чуть-чуть не тривиальное.
Автор почему-то подразумевает что двоичный поиск априори лучше тупого перебора в лоб, что может быть совсем даже и не так. Если массив целиком влезает в кеши, да даже если и не целиком, то вполне может оказаться что перебор отрабатывает быстрее двоичного поиска, который будет постоянно сбрасывать кеш если данных много, или просто будет более громоздким и менее понятным чем перебор, а работать так-же по скорости, при небольшом размере массива.
Только вот двоичный поиск редко когда требует больше записей в кеше чем поиск линейный, так что если он и окажется медленнее - то уж точно не из-за кеша.
Зато двоичный поиск генерирует кэш промахи и сбивает логику префетчинга, а на этом часто весь перформанс и умирает. Подобное надо бенчить на конкретных продовых данных.
Кеш-промахи и префетчинг тут точно ни при чём.
Повторюсь, есть крайне мало ситуаций, в которых линейному поиску потребовалось бы затронуть меньше памяти. А значит, все эти эффекты могут лишь уменьшить выгоду от двоичного поиска, но никак не сделать его хуже линейного.
Вот с чем правда у двоичного поиска плохо - так это с предсказанием переходов. Условный оператор внутри цикла попросту непредсказуем, он будет останавливать конвейер в среднем на каждой второй итерации (а попытка спекулятивно исполнить обе ветки быстро упрётся в тот же выбор уже на следующей итерации).
Есть же branch-free реализации бин-поиска. Даже тут на хабре статью видел как-то.
Вы про тернарный оператор вместо if?
Нет. Суть в том, что размер отрезка каждый раз делиться на 2, а вот начало смещается в середину или нет в зависимости от условия. Можно математическую формулу с умножением на bool делать, можно выбирать значение из массива по индексу 0 или 1. Но это не особо эффективно будет, хоть ветвлений и нет. Самое быстрое - заставить компилятор какой-нибудь cmov использовать.
Подобное надо бенчить на конкретных продовых данных
Боюсь не получится найти такие данные, где binary search проиграет. Разве что если там 3-5 элементов в массиве.
Если массив целиком влезает в кеши, да даже если и не целиком, то вполне может оказаться что перебор отрабатывает быстрее двоичного поиска, который будет постоянно сбрасывать кеш если данных много
У вас нестыковка в суждении.
На маленьких массивах рулит обычный перебор из-за простоты тела цикла и из-за спекулятивных вычислений. На больших рулит логарифмическая асимптотика. А кэш может склонить чашу весов только на пограничных объёмах, если они окажутся больше размера кэша (что вряд ли возможно для данной задачи на современных процессорах).
Ещё большую роль играет сочетание двух вещей: необходиомость сортировки перед поиском и предполагаемое число поисков. Если сортировать надо, и число запросов невелико, то даже на больших объёмах данных гораздо быстрее будет нужное количество раз линейно поискать (бонусом, простые данные типа чисел очень сильно ускоряются векторными инструкциями).
Двоичный поиск быстрее уже при 4-5 элементах в массиве.
В общем хоть меня и удивляет популярность такой достаточно простой задачи, но я сначала дошел до условия, решил задачку, а потом продолжил читать. Не думал, что мое наивное решение и будет тем самым, которое ожидает автор статьи. Но хочу показать свое решение в коментах, так как оно оригинально тем, что сделано на WL:
f[arr : {a1_Integer, ___Integer}, x_Integer, default_Integer : -1] /; x < a1 := default
f[arr : {___Integer, an_Integer}, x_Integer, default_Integer : -1] /; x >= an := an
f[arr : {__Integer}, x_Integer, default_Integer : -1] :=
With[{halfLen = Round[Length[arr]/2]},
If[arr[[halfLen]] < x,
f[arr[[halfLen + 1 ;; ]], x, arr[[halfLen]]],
f[arr[[ ;; halfLen]], x, default]
]
]
f::argex = "Argument exception";
f[args___] := (Message[f::argex]; Defer[f[args]])
На скриншоте код и результаты тестов. Результаты не уместились, но тестов больше чем в самой статье, т.е. они те же самые, а еще включают то, что не было учтено.
Тоже подумал сразу про что-то в роде паттерн-матчинг)
__Integer&args___
Какой замечательный язык. У этих ___ (3 штуки аж) есть какая-то история?
Да, конечно. Это такой синтаксис шаблонов/паттернов/образцов в WL. Во многих языках программирования, в которых есть паттерн-матчинг есть такая штука как wildcard. То есть "_". Так вот в WL шаблоны могут состоять из разных вариаций wildcard. Вот несколько примеров. Сравнение происходит при помощи функции MatchQ[expression, pattern]:
MatchQ[x, _] == True (*одиночное подчеркивание - все что угодно*)
MatchQ[f[x], f[_]] == True (*это значит выражение слева это f с любым аргументом*)
MatchQ[f[x, y], f[_]] == False
MatchQ[f[], f[_]] == False
MatchQ[f[1, 2, 3, 4], f[__]] == True (*два подчеркивания от одного до бесконечности элементов*)
MatchQ[f[], f[__]] == False
MatchQ[f[], f[___]] == True
MatchQ[f[x], f[___]] == True
MatchQ[f[x, y, z], f[___]] == True (*три подчеркивания любое число элементов от 0 до беконечности*)
Кроме трех вариантов wildcard есть еще возможность указывать диапазон количества элементов или конкретное значение, но это я оставлю на потом. И так мы рассмотрели возможность матчить произвольное выражение с шаблоном, который соответствует одному "чему угодно", одному и более или нулю и более штук "чего угодно". Но что если я хочу чтобы это было не что угодно, а только выражения/объекты с определенными типами? Тогда после подчеркивания я могу напрямую указать этот тип. Как понять какой тип у выражения в языке с динамической типизацией? При помощи функции Head. Это значит что
Head[1] == Integer
Head[1.0] == Real
Head[1/3] == Rational
Head[1 + I] == Complex
Head["string"] == String
Head[x] == Symbol
Head[f[x]] == f
Head[f[x][y][z]] == f[x][y]
Head[Head[f[x][y][z]]] == f[x]
И я могу взять любой результат, который возвращает Head и вставить его сразу после одного/двух/трех символов подчеркивания. То есть вот так:
MatchQ[1, _Integer] == True
MatchQ[1.5, _Integer] == False
То есть это wildcard с проверкой типов, но не все так просто.
Вот например как можно проверить что у нас массив только целых:
MatchQ[{1, 2, 3, 4}, {__Integer}] == True
А вот так я могу проверить, что у меня есть массив где сначала идут целы числа, потом рациональные, а потом комплексные. При этом комплексных может не быть совсем
MatchQ[{1, 2, 3, 1/3, 1/5, 1/7, I, I/3}, {__Integer, __Ratonal, ___Complex}] == True
MatchQ[{1, 2, 1/5}, {__Integer, __Ratonal, ___Complex}] == True
А еще wildcard можно связать с именем вот так:
MatchQ[f[1], f[x_]] == True
В MatchQ это бесполезно, но в функции, которая вытаскивает что-то по шаблону - это полезно:
Cases[{f[1]}, f[x_] :> x] (* => {1} *)
Т.е. выше я связал значение 1 из выражения с символом x и смог извлечь это значение. Если использовать несколько подчеркиваний, то будет вот так:
Cases[{f[1, 2, 4]}, f[x__] :> {x}] (* => {{1, 2, 4}}*)
Это небольшая часть паттерн матчинга в WL но нам пока достаточно. Теперь перейдем к главному - шаблоны можно использовать в в определениях функций, т.е. создав функцию вот так:
f[x_] := x + 1
Я говорю математике о том, что как только она встречает выражение, которое матчится с:
MatchQ[f[1], f[x_]] == True
То сразу же происходит замена на правую часть определения функции - т.е. на x + 1. Определив так функция - я отсекаю все шаблоны, которые не матчатся с шаблоном f[x_]. Вызвав функцию на том, что не матчится ни с одним из шаблонов, которые были определены - ядро WL вернет результат ввода как есть. Т.е. например:
f[x_, y_] := x + y
f[1, 2, 3] (* => f[1, 2, 3] без изменений*)
Ну и возвращаясь к примеру из моего комментария выше шаблон
f[arr: {a1_Integer, ___Integer}, x_Integer] /; x < a1 := ...
Означает, что функция определена только на последовательности аргументов, которая представляет из себя:
Первый аргумент список, где первый элемент списка обязательно целое число, а дальше может быть от нуля до бесконечности только целы чисел. Но я не стал писать a__Integer, чтобы связать ТОЛЬКО первый элемент списка с переменной a1, а не всю последовательность.
Второй аргумент - просто целое число.
После знака
/;идет условие, которое может использовать связанные переменные
Если у вас возникнут вопросы после моего объяснения или я объяснил слишком запутанно - то напишите пожалуйста, я готов ответить на любые вопросы!
Спасибо за такой развёрнутый ответ (лови плюс в карму). Я думал это просто дичь уровня "исторически так получилось, что разные пласты костылей наложились друг на друга", а тут целая механика чего-то вроде variadic arguments в Typescript, только на стероидах.
Спасибо большое за оценку моих трудов =)
Кстати мой любимый книжный пример - это сортировка пузырьком при помощи шаблонов:
{5, 4, 2, 6, 3, 2} //.
{fst___, x_Integer, y_Integer, rst___} :>
{fst, y, x, rst} /; x > y
//.- сокращение для ReplaceRepeated - функция которая выполняет повторяющуюся замену:>- правило замены/;- дополнительное условие для замены, но не обязательное
В итоге этот код на первом шаге делает следующее. Берет весь список и сравнивает его с образцом:
MatchQ[{5, 4, 2, 6, 3, 2}, {fst___, x_Integer, y_Integer, rst___}] /; x > y
связываются fst = <ничего>; x = 5; y = 4; rst = 2, 6, 3, 2. Оказывается что 5 > 4, тогда условие выполнено и на место исходного списка вставляется:
{fst = <ничего>, y = 4, x = 5, rst = 2, 6, 3, 2} == {4, 5, 3, 6, 3, 2}
Далее этот процесс повторяется, но теперь первый и второй элемент не проходят условие и происходит новое связывание: fst = 4; x = 5; y = 2; rst = 6, 3, 2 и т.д. пока не окажется так, что заменять ничего.
А с чего автор решил, что двоичный поиск будет быстрее, чем векторные SIMD инструкции? К тому же даже с двухканальным доступом к памяти, не говоря уже о четырехканальном, считать такой массив последовательно будет быстрее, чем прыгать по нему двоичным поиском.
А код на Javascript точно сможет задействовать векторные SIMD инструкции?
Кажется нет, можно только если через WASM достучаться до SIMD, лет 10 назад был пропосал на SIMD расширение, но его вскоре выпилили.
Если не уверены, станет ли WASM использовать конкретные SIMD инструкции, можете проверить тут. Или воспользоваться внешней библиотекой. Например, Tensorflow, где эти инструкции точно поддерживаются.
А причём тут WASM? Речь-то шла про поиск в обычном массиве Javascript.
JS - это язык. А чем и куда он компилируется Вы не указали. Значит для Вас это значение не имеет. Вот и компилируйте, например, в WASM, если хотите поддержку SIMD инструкций. К тому же я Вам предложил альтернативу в виде Tensorflow, которая уж точно SIMD использует.
Понятно, что на ESP32 не только JS, но даже C/C++ SIMD инструкции использовать никакой компилятор не станет. Потому что там их просто нет )
Вот я и не пойму, чего Вы хотите. Машинные инструкции возникают только после компиляции. От языка же их использование не зависит вообще - только от компилятора.
Приведите хоть один компилятор JS, способный задействовать SIMD-инструкции в простом цикле линейного поиска по массиву.
А пока вы не привели такого примера - ваш комментарий выглядит полной чушью.
Во-первых, компиляторов JS просто не существует, максимум есть JIT.
Во-вторых, нет абсолютно никакого смысла компилировать JS в WASM. WASM - это технология, позволяющая исполняться коду на разных языках в браузерах, но JS браузеры умеют исполнять и без неё.
В-третьих, чтобы задействовать SIMD-инструкции, нужно как минимум обеспечить гомогенность массива (что уже сложно в JS), а дальше нужно использовать либо явные языковые интринсики (которых в JS нет), либо автовекторизацию (про которую я в JS ни разу не слышал).
компиляторов JS просто не существует
нет абсолютно никакого смысла компилировать JS в WASM.
У Вас раздвоение личности? Мало того, что пишете от том, что нет смысла компилировать тем, чего не существует, так еще и хотите использование SIMD - но не хотите один из вариантов, когда они будут использованы. )))
как минимум обеспечить гомогенность массива
Или, как я написал изначально, воспользоваться TensorFlow. Если бы Вы эту фразу сумели прочитать, то поняли бы, что в этом случае массив будет хранится в формате вектора TF, пригодного к обработке не только SIMD, но и GPU
компиляторов JS просто не существует, максимум есть JIT
Node.js как раз и обеспечивает высокую производительность, благодаря компиляции напрямую в машинный код средствами V8.
Вы заблуждаетесь. V8 не использует при исполнении JS-программ байт-код или любой промежуточный код.
Это даже на Хабре подробно рассматривалось.
Если хотите изменить общепринятую терминологию, то рекомендую начинать не здесь, а, например, с обсуждения в Википедии:
"JIT-компиляция — технология увеличения производительности программных систем, использующих байт-код, путём компиляции байт-кода в машинный код или в другой формат непосредственно во время работы программы.
Вы путаете использование промежуточного байт-кода при компиляции, как в LLVM или V8, и интерпретацию байт-кода (JIT).
Ладно, убедили, что в некоторых случаях при выполнении кода, скомпилированного baseline компилятором, V8 может ради оптимизации переключаться на интерпретацию. Но мне не кажется, что это меняет суть дела, так как эта интерпретация все равно производится через оптимизирующий компилятор TurboFan и только для hot функций.
Байт-код тут ни при чём. Технология JIT - это компиляция кусков кода в машинный код по требованию, когда до них доходит исполнение.
Есть там промежуточный байт-код или нет - не важно, это деталь реализации.
В JS не используется simd и вряд ли будет. Можете посмотреть SE, там в основном негативные ответы. В общем ближайшее к JS где это можно - WASM
А через TensorFlow чем плохо? Если массив будет сразу в формате вектора, то должно быть все просто прекрасно.
если я не ошибаюсь там компиляция в webgl. Просто так не попишешь, пересылка очень ресурсозатратная туда и обратно. Выигрыш будет только при достаточно большом количестве данных для расчета.
А окей там завезли WASM backend
Ошибаетесь. Через WebAssembly есть поддержка SIMD для JS https://blog.tensorflow.org/2020/09/supercharging-tensorflowjs-webassembly.html?m=1
Бинпоиск будет абсолютно точно быстрее. Потому что всегда можно вместо проверки восьми чисел SIMD-ом, просто посмотреть на одно последнее, чтобы понять, а надо ли все восемь пропустить. А бинпоиск еще больше чисел пропустит и еще меньше проверок сделает. Плюс, в SIMD-решении обработка хвостов короче регистра. И даже если вы совсем извернетесь и как-то симдом будете искать одно нужное число из заданных 8, то там явно больше одной операции. Надо получить результат векторного сравнения, найти среди результата самый правый 0 или 1. А потом еще отдельно проверить, а вдруг искомое число в следующем блоке. И эти проверки да на каждой восьмерке чисел.
посмотреть на одно последнее
И вот тут у Вас сразу же возникает два цикла обращения к памяти вместо одного, даже при двухканальном доступе к ней. На более длинном массиве и с четыреханальной памятью можно так пролететь по производительности уже в четыре(!) раза.
Если сопоставить время цикла доступа с памяти с производительностью кеша CPU, то дальше уже и сравнивать будет нечего.
И вот тут у Вас сразу же возникает два цикла обращения к памяти вместо одного
Нет! Вместо того, читать и сравнивать 8 чисел через симд, даже если это все параллелизируется по всем каналам памяти и происходит за одну операцию доступа к памяти и сравнения, это не быстрее, чем посмотреть только на одно 8-ое число.
Если сопоставить время цикла доступа с памяти с производительностью кеша CPU,
На больших массивах бинпоиск, очевидно, будет на порядки быстрее. Потому что там во много раз меньше обращений к памяти, пусть каждое из них и будет помедленнее в бинпоиске. А еще сильно меньше сравнений.
На маленьких массивах доступ к памяти итак будет быстр в обоих случаях, потому что оно все целиком загрузиться в кеш еще на первом обращении к памяти.
посмотреть только на одно 8-ое число.
А с чего Вы взяли, что посмотрев только одно число, решите задачу в общем случае?
На больших массивах двоичный поиск точно будет эффективней, так как избавит от необходимости вообще читать из памяти бОльшую часть массива. А когда весь массив может быть считан за одно многоканальное чтение из памяти - двоичный поиск может только навредить, приведя к лишним циклам обращения к памяти.
целиком загрузиться в кеш еще на первом обращении к памяти.
Если Вы обратились изначально к числу не в первом машинном слове, то далеко не факт. Зависит от выравнивания. И если потребуется обращение к первому машинному слову, возникнет ещё один цикл обращения к памяти.
Именно по этой причине в GCC qsort() не использует quicksort алгоритм для массивов короче четырех машинных слов. Выгодней считать его в кеш целиком одним обращением к памяти.
А с чего Вы взяли, что посмотрев только одно число, решите задачу в общем случае?
Ну вот как ваше предполагаемое SIMD решение работает? Читает весь массив по 8 чисел SIMD операциями и сравнивает их с искомым. Потом смотрит на массив результата и как-то за счет этого вычисляет тут ли есть искомый индекс. Как его можно ускорить: смотрим на каждое 8-ое число, за счет этого вычисляем, если в этой 8-рке искомый индекс. Это будет быстрее.
А когда весь массив может быть считан за одно многоканальное чтение из памяти - двоичный поиск может только навредить, приведя к лишним циклам обращения к памяти.
Нет, он и в двоичном поиске будет считан за одну операцию с памятью, потому что там весь массив - 64 байта условных и считается за раз при первом же обращении к памяти.
Если Вы обратились изначально к числу не в первом машинном слове, то далеко не факт.
Ну хорошо. Допустим. Тогда бинпоиск + обращение к 0-вому числу в массиве перед ним всегда будет не медленнее SIMD решения. Без этого 0-вого обращения, оно будет быстрее для массивов от 8 чисел.
Ну вот как ваше предполагаемое SIMD решение работает? Читает весь массив по 8 чисел SIMD операциями и сравнивает их с искомым.
Это Вы придумали. А я решаю задачу из статьи. Где у меня положительные числа меньшие 255. Unsigned byte. И длина массива меньше 64 элементов, 512 бит. Поэтому я гружу в 512-битный регистр весь массив и одной командой VPCMPUB нахожу искомое значение.
Где в условии это сказано? Там есть один пример входных данных, но в условии это a - параметр функции. И уже в примерах есть и пустой массив и даже null вместо a.
Далее, вы не одной командой находите искомое значение - вы получите маску из 0 и 1. До 64 бит. И вам надо в этой маске найти крайний 0, или 1.
Потом, ну заменим 8 на 64, все мои рассуждения остаются в силе.
Найти первый установленный бит - ещё одна машинная команда. Итого, у меня три машинных команды. А теперь попрошу Ваш код на ассемблере в студию. Вот и сравним.
Найти первый установленный бит - ещё одна машинная команда
Есть такая команда для симд регистров? Так что еще мов какие-то будут. Плюс отдельная проверка на не найденный ни один установленный бит.
Ну ладно. Согласен, в некотором очень узком диапазоне размера входных данных SIMD будет побыстрее.
Есть такая команда для симд регистров?
VPLZCNTQ
И я сразу говорил, что выигрыш будет именно на предложенном в задании массиве. Однозначно на массиве размером свыше 512 бит (64 байта) выиграет двоичный поиск.
Кстати, посчитал, на массиве любого размера, как только остаток при двоичном поиске оказывается меньше 512 бит (в большинстве случаев, даже 1024 бита), на завершающем этапе SIMD быстрее, чем продолжение двоичного поиска.
Задача крайне похожа на ту, которую даёт thinkcell. Только там на плюсах и надо написать такой контейнер поверх std::map. Функция поиска тривиальная, а вот со вставкой надо повозиться.
Первый вопрос: уверены ли мы, что массив всегда отсортирован? Если есть чисто теоретический шанс, что нет - то это влечет целую кучу других вопросов
Второй вопрос: штатная ли ситуация - получение пустого массива? Если да, то я бы предложил подумать про вариант с двумя разными кодами возврата, чтобы вызывающей программе было проще различать ситуацию пустого массива и слишком маленького числа. Если, конечно, функция готовится для новой системы, а не рефакторит уже имеющуюся с жестко зафиксированным интерфейсом
Третий вопрос: типичный размер массива? В зависимости от этого, двоичный поиск может быть бессмысленным. Или, наоборот, не-двоичный...
Четвертый вопрос: насколько часто входное значение будет меньше min или больше max? Если это достаточно типичная ситуация, а размер массива сильно ненулевой, то я бы сделал две эти проверки еще на входе
Пятый вопрос: а как часто будет использоваться функция, и должна ли она работать за разумное время, или же это одноразовый кейс и важнее простота кода и скорость его отладки? С учетом этого, обсужу с интервьюером выбор алгоритма решения
Ну а уже после этого займусь кодированием, то есть напишу "обертку", внутри которой вызову чуть подправленную функцию из своей собственной библиотеки. Так как по какому-то недоразумению там
уже есть такая процедура
которая решает почти в точности эту задачу, только не с числами, а с датами ;-) Правда, мне там придется добавить integer в качестве допустимого входного типа, так как я пишу на фортране, и у меня нет обобщенного типа - все варианты надо расписывать явно. А дата сейчас в силу legacy-причин оформлена, как структура, а не как число. Соответственно, все операторы сравнения перегружены для работы с этой структурой. Так что в код функции заглянуть все же придется ;-)
У нас есть массив, отсортированный по возрастанию.
a = [ 3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21 ];Определите функцию f(a, x), которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки.
...
Не нужно быть семи пядей во лбу, доктором математических наук, чтобы осмыслить его – поэтому вопрос достаточно честный ко всем кандидатам. Кроме того, его не требуется дополнительно объяснять – а это занимало бы драгоценные минуты нашего собеседования.
может я конечно тупой, но из поставленной задачи не понятно, что же автор хочет получить на выходе. Что за ближайшее наименьшее число ?
f(a, 12) = 12
почему для 12 ближайшее наименьшее число 12, а не 10 ?
Примерно понимая, чего от тебя хотят на собесе, перебор вариантов был такой:
Перебор значений в лоб: запорят за сложность (жрет cpu);
Можно откусывать левый/правый слайс и кормить им рекурсию: запорят за объем памяти + рекурсия на ровном месте (более сложный код);
Ну ок, тогда оперируем слайсами через индексы. Более оптимального ничего не придумал.
Тесты must have. Хоть наколеночные - любые.
Python code as is (не причесывал)
a = [3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21]
NEGATIVE = -1
def middle(x, y):
delta = y - x
return int(x + delta / 2) if delta > 1 else x
def f(arr, x):
return find_near(arr, x) if arr and isinstance(arr, list) else NEGATIVE
def find_near(arr, x):
start, end = 0, len(arr)
while end - start > 1:
middle_idx = middle(start, end)
mid_val = a[middle_idx]
if mid_val == x:
start = middle_idx
break
elif mid_val > x:
end = middle_idx
else:
start = middle_idx
val = arr[start]
return val if val <= x else NEGATIVE
if __name__ == '__main__':
class EmptyObj:
pass
payload = [
[a, 12, 12],
[a, 13, 12],
[a, 2, -1],
[a, 22, 21],
[a, 3, 3],
[a, 21, 21],
[[], 1, -1],
[None, 1, -1],
[EmptyObj(), 1, -1],
]
for a, val, exp_val in payload:
res = f(a, val)
print(f"f({a}, {val}) = {res} (exp: {exp_val})")
assert res == exp_valЧем понравилось: абсолютно не надо готовиться. Задача вполне достойная, состоит из элементарных сущностей и не надо повторять вычернутые алгоритмы и структуры.
Вот прям унес бы к себе, но мы не мучаем по часу на 1 задачку. :( А тут со стрессом час запросто уйдет. У меня ушло 35 минут без какой-либо подготовки [и чтения статьи, разумеется], но я дома и был спокоен, как удав. )
12 лет прошло, как пропагандирую отказ от задачек, неужели с ходом лет до людей так и не дошло, насколько это неэффективная трата времени? Я еще понимаю когда так отсеивают кандидатов гиганты, заставляя HRов рассылать задачки, но блин тратить свое личное время каждый раз на то, чтобы в сути "подбросить кубик"?
Неужели есть кто-то, кому нравится час сидеть уставившись в ноутбук, чтобы не отвлекать кандидата или лезть к кандидату в голову "а ты тооооочно проверил всееее варианты инпууута?".
- люблю на выходных решать задачки литкода
- несу презервативы и трудовой договор
Наверняка, многие еще не дочитав задачку, знают, что, в сути хочет увидеть ее автор. Почему не получить устный ответ и не потратить 50 минут на что-то другое?
этот гугл: моего отца так нанимали, меня так нанимали и я так нанимать буду! они от шариков в боинге и чугунных люков, сравнительно не так и давно откзались. :)
ps тоже считаю, что задачку можно написать кодом, псевдокодом, голосом или рисунком. не вижу проблем продолжить диалог и накидать вопросов дальше.
Если честно, вообще не понимаю зачем всё это в 2024 году. Это та же проблема калькулятора. Нас в третьем классе учили решать сложные арифметические задачи. При этом насмерть запрещали пользоваться калькулятором. Что в итоге? Я прочитал "Вы должно быть шутите, мистер Фейнман" и удивился тому, как это применимо в жзини. Я могу прикинуть, сколько будет треть от 25000. Да, это всё круто. Но когда дело доходит до дела, я лучше возьми в руки калькулятор. Или ещё лучше - excel spreadsheet, там даже проще.
Так же и подобные задачи в современном мире решаются просто запихиванием этого в чатГПТ.
def f(a, x):
if not a or x is None:
return -1
left, right = 0, len(a) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if a[mid] <= x:
result = a[mid]
left = mid + 1
else:
right = mid - 1
return result if result != -1 else -1
# More complicated test cases
test_cases = [
([100, 200, 300, 400, 500, 600, 700, 800, 900, 1000], 350),
([1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33], 28),
([10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500], 350),
([100, 1000, 10000, 100000, 1000000, 10000000], 555555),
([3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60], 28),
([5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100], 77),
([10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200, 250, 300, 350, 400, 450, 500, 550, 600, 650, 700, 750, 800, 850, 900, 950, 1000], 875),
([1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97, 100], 83),
([2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, 101], 66),
([10, 110, 210, 310, 410, 510, 610, 710, 810, 910, 1010, 1110, 1210, 1310, 1410, 1510, 1610, 1710, 1810, 1910, 2010], 2000)
]
# Running the test cases
test_results = [(array, x, f(array, x)) for array, x in test_cases]
test_results
Array: [100, 200, 300, 400, 500, 600, 700, 800, 900, 1000], x = 350, Result: 300
Array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33], x = 28, Result: 27
Array: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500], x = 350, Result: 300
Array: [100, 1000, 10000, 100000, 1000000, 10000000], x = 555555, Result: 100000
Array: [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60], x = 28, Result: 27
Array: [5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100], x = 77, Result: 75
Array: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200, 250, 300, 350, 400, 450, 500, 550, 600, 650, 700, 750, 800, 850, 900, 950, 1000], x = 875, Result: 850
Array: [1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97, 100], x = 83, Result: 82
Array: [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, 101], x = 66, Result: 65
Array: [10, 110, 210, 310, 410, 510, 610, 710, 810, 910, 1010, 1110, 1210, 1310, 1410, 1510, 1610, 1710, 1810, 1910, 2010], x = 2000, Result: 1910
Могу ли я сесть, и написать это сам? Да, вполне. На самом деле, могу сказать, что я бы потратил на это пару часов. Язык бы был другой, но какая разница. Но работа у меня почасовая, с упором на закрытые тикеты. Тратить два часа на такой алгоритм мне вообще будет бесполезно.
Хорош ли алгоритм ГПТшки? Не знаю, наверное нет. Тут все говорят об edge cases, и готовы устраивать дебаты по поводу этих кейсов. Но ты никогда не узнаешь, что у тебя есть edge cases, пока не посмотришь на приходящие данные. У тебя не может быть сферических коней в ваккуме. А когда ты их определишь, то можно тот же код запизнуть в ГПТ, и сказать ему поправить этот код.
Подобные вопросы сейчас - это как вычисление квадратного корня из двух тысяч без калькулятора. Да, могу. Но не буду. Ибо это не надо. Знать - знаю. Но действовать по этому поводу - бесполезно.
Это как чувак, который снял видео о том, как сделать куринный сендвич с нуля. Он пол-года выращивал всё от начала до конца. Начиная с пшеницы и курицы, заканчивая сбором морской воды, чтобы выделить соль. После сбора всех ингридиентов сам приготовил хлеб, и нарезал овощи. А после - заснял свою реакцию на камеру. И в итоге он сказал "Так себе", и со слезами выключил трансляцию. Он потратил толи три, толи шесть тысяч долларов на то, чтобы поддерживать ферму в рабочем состоянии и выращивать ингридиенты. Так делать можно, но мы этим не занимаемся, ибо мы уже изобрели способы делать это лучше и намного более эффективно.
Так же и подобные задачи в современном мире решаются просто запихиванием этого в чатГПТ.
Очень плохая идея. Никогда не спрашивайте у этих нейросеток что-то по теме, в которой вы не эксперт. Они вам очень убедительно и правдоподобно нагалюционируют бред, и вы никак этого не сможете заметить. И баг в таком сгенеренном коде будете искать неделями.
Очень даже неправильный подход. ГПТ как раз и был тренирован на открытых данных из Реддита и Стака. Эта штука понарешала столько подобных задач, что ему уже тошнить начинает.
Попробуйте.
То, чего эта штука решать не умеет - это нетиповые реальные задачи, которые возникают у тебя в проде, когда ты пытаешься соеденить NEC SV9500 и Asterisk, или пытаешься загрузить проприетарную прошивку на самодельный принтер.
А все эти сферические кони в вакуме для ГПТ как орешки.
Очень смешно. А еще в этих открытых данных наверняка все расписано про кулинарию. И тем не менее эти нейросетки считают, что яйца можно расплавить.
Попробуйте
Пробовал. Иногда дело выдает. Иногда очень правдоподобный бред. Например, я попросил его найти максимум среди k последних элементов в потоке данных, а он нашел k-ый максимальный среди всех. И та и другая задачи - с литкода. И если ему переформулировать задачу вот прям как там написано (sliding window max), то он выдает решение. Если своими словами написть - нет.
Еще пробовал задачу, которую сам решал по работе и сейчас на интервью спрашиваю. Она фактически как задача с литкода, только не баянистая. Вообще бред получил в ответ.
Еще спрашивал по работе, например, как можно через виндовое апи MediaFoundation проверить, а не используется ли камера другим приложением. Оно выдумывает несуществующие классы и методы. Или еще хуже, выдумывает несуществующее поведение. Тогда код компилируется но делает не то, что ожидается. Но при этом красиво аргументирует и даже ссылки на документацию дает (правда по ссылкам написано совсем не то). Не справилось даже после подсказок, какой интерфейс использовать. А ведь это очень попсовая задача - гуглиться за 5 минут с примерами и кодом.
Если вот именно ваша задача достаточное количество раз именно в той или очень близкой формулировке встретилась в этих открытых данных, да еще там решения были правильные (вы, может быть, удивитесь, но бездумно копировать код со Стака - тоже плохая идея), то вам повезло. Если вам не повезло, то сеть не скажет "я не знаю". Она не способна это сделать по построению. Она вам нагалюционирует очень правдоподобный бред. Который вы, не будучи специалистом никак не разберете.
Реализация переусложнена, поэтому содержит пляски с бубном. А еще там есть опасность переполнение получить при расчете mid.
def f(a, x):
l, r = -1, len(a)
while r - l > 1:
mid = l + (r - l) // 2
if a[mid] <= x:
l = mid
else:
r = mid
return a[l] if l >= 0 else -1
Не запускал, но всё должно работать.
Рекомендуется к прочтению вот это
f([], x) = -1 // Массив пуст
Вот это я вообще не понял. У нас массив не может быть пуст по определению. У нас входные данные - это константа.
А уж если решили закладываться на валидацию всего и вся, то:
Если вопрос звучит как "напишите функцию", а не "реализуйте алгоритм", то будет ли считаться читерством вариант просто использовать функцию bisect.bisect_right() из стандартной питоновской библиотеки?
Нет, если сможете на словах объяснить как он работает. В моей предыдущей компании был список задач на позицию дата инженера. Одна из задач заключалась в удалении дублирующих записей из данных. В рекомендациях был пункт о достаточности решений вида sort -u или distinct() из спарка, если кандидат мог объяснить как они работают. В той компании кодинг интервью требовали от кандидата решить минимум одну задачу и сильно продвинуться во второй. Быстрый ответ на один из вопросов сильно упрощал прохождение интервью.
Есть еще крутая тактика говорить интервьюверу, что вы точно знаете решение задачи. Иногда, интервьювер принимает решение без кодинга после пары уточняющих вопросов. Я терпеть не могу задачи на графы, потому что для них долго писать юнит тесты. А еще я часто делаю ошибки в max-flow алгоритме при обновлении остаточной матрицы. Если мне попадается задача на граф, я стараюсь сразу сказать, что знаю решение, назвать алгоритм и сложность. Пока не срабатало 2 раза из где-то 10. В Убере была усложненная версия задачи уровня хард и усложнение сильно меняло решение, я, кстати, не смог его в итоге решить за час потому что потратил много времени на первую идею. Еще один раз была задача на определение является ли граф деревом, интервьювер из Reddit не знал о UnionFind. Он даже с тестами не верил, что решение работает. Не знаю, как он меня оценил, но я получил оффер. В остальных случаях тактика работала как магия. Но есть шанс получить более сложную задачу второй потому, что времени много остается.
Требования к функции делают её непригодной к использованию в реальной жизни: невозможно отличить ошибку от найденного значения.
f([-1], 0) == -1
Если бы возвращала индекс вместо значения, то имела бы право на существование.
Мне кажется, если это в более мягкой форме выразить во время собеседования, то это жирный плюс в оценке кандидата. Пока тут устраивают нелепые срачи var vs let или рассуждают про кеш-промахи, нормальная сигнатура функции - это действительно важная вещь. Элемент продуктового мышления.
в условии задачи было, что все числа положительные
Самый простой и, при этом, быстрый метод это составление таблицы с выходными данными. Там можно ещё и оптимизировать по типу данных. Например, если диапазон значений в char, или short укладывается.
Для небольших не константных таблиц - динамическое обновление/генерация выходной таблицы.
И только для больших и не константных массивов, если к данным никак не применить хеши, то бинарный поиск.
Ну нанимайте теперь каждого второго школьника в гугл =). С этой задачей справится почти кто угодно. А вообще, стоит заранее уточнить, какие в среднем значения n: на относительно маленьких, как в примере, дв поиск будет или не сильно быстрее, или даже дольше. Заморачиваться с O(), как по мне, стоит только если в условии сказаны ограничения для n, а их особо-то и нет 🫠
Двоичный поиск быстрее уже с 4-5 чисел в массиве.
Я бы сказал с 20-30, но я на C++ программирую
Я же даже результаты бенчмарка выкладывал: https://habr.com/ru/companies/ispsystem/articles/779224/comments/#comment_26254520
Бинпоиск быстрее уже с 4 элементов. И да, это на C++.
В четвертой строке решения начальному значению лучше присвоить не 0, а значение нулевого элемента массива.
Почему никто не говорит о банальной возможной оптимизации границ поиска.
Если разница между первым числом в массиве и искомым (df=x-a[min]) меньше чем число элементов в массиве, то правая граница будет не на последнем элементе, а на расстоянии df от первого элемента. Слева границу можно подвинуть таким же образом. И делать это на каждой итерации двоичного поиска, а в некоторых случаях и вместо него
А почему вы решили, что числа в масиве уникальные? Про это ни слова не сказано.
В вашем варианте сложность всё равно будет O(log n), но код будет тяжелее читать и понимать. Это нужно обосновать, иначе получим такую же преждевременную оптимизацию, как у автора, с выходом из цикла по условию
a[mid] == x.
Хорошим вопросом был бы "а для какого количества чисел требуется такой поиск в массиве?". И тут возникает простор для индексации массива, например, BRIN
Я эту задачку решал намного дольше часа, с прочтением вики по двоичному поиску.
При этом она решается, по нормальному за 5 (пять) минут.
/**
* Задачка для собеседования
*/
class Scratch {
public static void main(String[] args) {
int[] a = {3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21};
int f = 1;
int i = Arrays.stream(a)
.filter(e -> e <= f)
.max()
.orElse(-1);
System.out.println(i);
}
}
Скажите, меня не возьмут в программисты?
У меня сходу с рекурсией так получилось, наверняка можно покороче:
def f(l, num):
while True:
if not isinstance(l, list) or len(l) == 0:
return -1
center = len(l) // 2
left_part, right_part = l[:center], l[center:]
if num < right_part[0]:
if len(left_part) == 0:
return -1
if num >= left_part[-1]:
return left_part[-1]
return f(left_part, num)
else:
if len(right_part) == 1:
return right_part[0]
return f(right_part, num)
У вас тут проблема, что из-за слайсов это решение работает за O(n). Весь бинпоиск абсолютно бесполезен получается. Из-за накладных расходов - это даже медленнее самого наивного решения одним циклом. Корректное рекурсивное решение должно принимать исходный неизменный массив и 2 границы текущего отрезка.
вот если на собесе я должен додумывать условия задачи и стаивть доп вопросы, это значит, что компания которая меня собеседует очень плохо знает что такое аналитики и зачем они нужны, если собес на позицию программиста, то задача должна быть четкой, не надо на меня перекладывать работу, которую вы делаете плохо
Мне грустно смотреть, что кандидатов оценивают по каким-то прикладным задачам. А ещё хуже, если по каким-то фичам языка. За собеседование нужно понять, как кандидат мыслит, насколько он понимает то, что говорит. Если это есть, то он обучится всему легко, а текущая задача... ну в 99% ты поюзаешь стандартную библиотеку, а когда понадобится своё решение, ты его найдешь/почитаешь и реализуешь, что опять связано в первую очередь с "уровнем мозгов"
Как это сделать в промышленных масштабах, когда соискателей за забором очередь, уходящая за горизонт?
В самом начале 90-х, когда я занимался локализацией американской ERP под российские реалии, соискателей тоже было у нас огромное количество. Вот только на первом же собеседовании предлагалось выполнить за месяц разработку трудоемкостью часов на 100 за $300 ($3 в час тогда это были неплохие деньги). Если задача не будет выполнена за месяц - не получишь ни копейки. Статус ежедневный и отношения по его результатам могут быть прерваны в любой момент. Опять таки без выплаты вознаграждения. Подавляющее большинство кандидатов, ознакомившись с таким предложением, отсекали сами себя. Очень многие отсекались в первые же дни на статусах. Из выполнивших задание и получивших вознаграждение, немногие, по результатам оценки качества выполненного задания, получали на тех же условиях второе задание, уже требовавшее более глубоких знаний проблемной части (GAAP). Я, собственно говоря, туда именно так и попал. У меня уже был опыт разработки на CXL, и я взял самое сложное задание - на разработку оконного визуального редактора алфавитно-цифровых форм пользовательского интерфейса. Тоже алфавитно-цифрового - под DOS, так как вся эта ERP тогда тоже была под DOS. А уже с модулем консолидации справился совсем легко, так как имел к тому времени не только техническое, но и экономическое высшее образование.
Естественно, выдача подобных заданий и контроль за их выполнением требовала немного больших усилий, чем пять-шесть часов собеседований. Но качество фильтра явно оказывалось выше, а результаты тестов имели практическую ценность в разрабатываемом программном продукте.
Не могу утверждать, что это точно лучшая альтернатива, чем решение не имеющих практическую ценность для работодателя задач с литкода. Но могу утверждать, что этот фильтр хорошо работал. Пробивались именно те, кто действительно очень хотел там работать и точно мог решать именно те задачи, которые требовались для разрабатываемого программного продукта. Даже с весьма высокоуровневыми постановками непосредственно от клиента.
А ещё хуже, если по каким-то фичам языка. За собеседование нужно понять, как кандидат мыслит, насколько он понимает то, что говорит.
То есть просить кандидата "А как вы мыслите?" "А вы понимаете, что говорите?"
Для собеседований как раз и нужно и можно спрашивать про фичи, алгоритмы, прикладные задачи и в процессе этого смотреть как кандидат мыслит и понимает ли что он говорит.
Все интервьюверы собственно имеют свой какой-то набор вопросов, в котором они хорошо разбираются, но хорошие интервьюверы как раз не смотрят на ответы в виде "кандидат ответил да или нет", а как раз смотрят каким образом кандидат подходит к решению проблемы, то есть как он мыслит и понимает ли он задачу и понимает ли он что он делает.
Определите функцию f(a, x), которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки.
Это повод уйти с собеседования. Какое тестовое задание на собеседовании, такие и технические задания будут после трудоустройства.
1. "ближайшее наименьшее" - что за бред?Возможные варианты: "ближайшее", "ближайшее меньшее" или "наименьшее".
2. Не определён случай ошибки. Чего вы вообще хотите?
Как в анекдоте про "Хочу хомячка!". А потом разработчику предъявляют, что написал не так как задумано. Или, что медленно работает потому, что вынужден бегать с уточняющими вопросами на ровном месте.
Реализовать древовидный поиск конечно можно. Только зачем он? Тем более тут.
Перебора выше крыши и нет заморочек
Программиста красит как раз простота решения и соответственно надёжность и скорость работы выбранного алгоритма
надёжность и скорость работы выбранного алгоритма
Ну так "древовидный поиск" (по уму называемый "бинарный поиск") как раз и имеет на порядки более высокую скорость работы.
В данном случае - нет. Массив слишком мал. Переписал код на C++. 25 млн вызовов функции (на входе x от 1 до 25):
линейный - 0.72 - 0.74
бинарный - 1.39 - 1.40
Не знаю, что вы там намеряли. Вот мой бенчмарк.
(Правда, чтобы сравнивать со стандартной реализацией я ищу не ближайший меньше, а самый левый больше-равный. Фактически, тоже самое, но +1).
Уже при 4 элементах в массиве бинпоиск чуть-чуть выигрывает. При 16 элементах - он быстрее уже почти в 2 раза. При 128 - в 5 раз. И это самая тупая-в-лоб реализация. Если ее подтюнить, то можно еще ускорить.
Результаты
---------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
---------------------------------------------------------------------------------------------
Linear_bn/1/iterations:100000000 9.36 ns 9.38 ns 100000000 sum=1
Linear_bn/2/iterations:100000000 10.6 ns 10.6 ns 100000000 sum=50M
Linear_bn/3/iterations:100000000 11.9 ns 12.0 ns 100000000 sum=100M
Linear_bn/4/iterations:100000000 13.3 ns 13.3 ns 100000000 sum=150M
Linear_bn/5/iterations:100000000 13.3 ns 13.3 ns 100000000 sum=150M
Linear_bn/6/iterations:100000000 15.9 ns 15.9 ns 100000000 sum=250M
Linear_bn/7/iterations:100000000 12.9 ns 12.7 ns 100000000 sum=133.333M
Linear_bn/8/iterations:100000000 18.9 ns 18.9 ns 100000000 sum=350M
Linear_bn/16/iterations:100000000 30.5 ns 30.5 ns 100000000 sum=750M
Linear_bn/32/iterations:100000000 52.2 ns 51.9 ns 100000000 sum=1.55G
Linear_bn/64/iterations:100000000 101 ns 101 ns 100000000 sum=-1.14497G
Linear_bn/128/iterations:100000000 187 ns 187 ns 100000000 sum=2.05503G
Binary_bn/1/iterations:100000000 11.0 ns 11.1 ns 100000000 sum=1
Binary_bn/2/iterations:100000000 11.8 ns 11.7 ns 100000000 sum=50M
Binary_bn/3/iterations:100000000 12.5 ns 12.7 ns 100000000 sum=100M
Binary_bn/4/iterations:100000000 12.9 ns 12.8 ns 100000000 sum=150M
Binary_bn/5/iterations:100000000 13.3 ns 13.3 ns 100000000 sum=150M
Binary_bn/6/iterations:100000000 14.2 ns 13.9 ns 100000000 sum=250M
Binary_bn/7/iterations:100000000 14.1 ns 14.1 ns 100000000 sum=133.333M
Binary_bn/8/iterations:100000000 14.2 ns 14.2 ns 100000000 sum=350M
Binary_bn/16/iterations:100000000 16.0 ns 15.9 ns 100000000 sum=750M
Binary_bn/32/iterations:100000000 18.4 ns 18.4 ns 100000000 sum=1.55G
Binary_bn/64/iterations:100000000 20.9 ns 20.9 ns 100000000 sum=-1.14497G
Binary_bn/128/iterations:100000000 24.3 ns 24.4 ns 100000000 sum=2.05503G
LB_bn/1/iterations:100000000 41.6 ns 41.6 ns 100000000 sum=1
LB_bn/2/iterations:100000000 46.6 ns 46.6 ns 100000000 sum=50M
LB_bn/3/iterations:100000000 46.8 ns 46.9 ns 100000000 sum=100M
LB_bn/4/iterations:100000000 48.8 ns 48.8 ns 100000000 sum=150M
LB_bn/5/iterations:100000000 49.5 ns 49.5 ns 100000000 sum=150M
LB_bn/6/iterations:100000000 49.5 ns 49.4 ns 100000000 sum=250M
LB_bn/7/iterations:100000000 49.2 ns 49.4 ns 100000000 sum=133.333M
LB_bn/8/iterations:100000000 50.5 ns 50.5 ns 100000000 sum=350M
LB_bn/16/iterations:100000000 54.7 ns 54.5 ns 100000000 sum=750M
LB_bn/32/iterations:100000000 59.2 ns 59.2 ns 100000000 sum=1.55G
LB_bn/64/iterations:100000000 65.7 ns 65.5 ns 100000000 sum=-1.14497G
LB_bn/128/iterations:100000000 71.0 ns 71.1 ns 100000000 sum=2.05503G
Код (нужен gbenchmark)
int Linear(const std::vector<int>& a, int x) {
for (int i = 0; i < a.size(); ++i) {
if (a[i] >= x) return i;
}
return a.size();
}
int Binary(const std::vector<int>& a, int x) {
int l = 0;
int r = a.size() - 1;
int ans = a.size();
while (l <= r) {
int m = l + (r - l) / 2;
if (a[m] >= x) {
ans = m;
r = m-1;
}
else {
l = m+1;
}
}
return ans;
}
int Lower_Bound(const std::vector<int>& a, int x) {
return std::distance(a.begin(), lower_bound(a.begin(), a.end(), x));
}
void Linear_bn(benchmark::State& state) {
std::vector<int> a(state.range(0));
std::iota(a.begin(), a.end(), 0);
int sum = 0;
int idx = 1;
for (auto _ : state) {
sum += Linear(a, idx);
idx = (idx * 37+1) % state.range(0);
}
state.counters["sum"] = sum;
}
void Binary_bn(benchmark::State& state) {
std::vector<int> a(state.range(0));
std::iota(a.begin(), a.end(), 0);
int sum = 0;
int idx = 1;
for (auto _ : state) {
sum += Binary(a, idx);
idx = (idx * 37+1) % state.range(0);
}
state.counters["sum"] = sum;
}
void LB_bn(benchmark::State& state) {
std::vector<int> a(state.range(0));
std::iota(a.begin(), a.end(), 0);
int sum = 0;
int idx = 1;
for (auto _ : state) {
sum += Lower_Bound(a, idx);
idx = (idx * 37+1) % state.range(0);
}
state.counters["sum"] = sum;
}
BENCHMARK(Linear_bn)->DenseRange(1, 7)->RangeMultiplier(2)->Range(8,128)->Iterations(100000000);
BENCHMARK(Binary_bn)->DenseRange(1, 7)->RangeMultiplier(2)->Range(8, 128)->Iterations(100000000);
BENCHMARK(LB_bn)->DenseRange(1, 7)->RangeMultiplier(2)->Range(8, 128)->Iterations(100000000);
BENCHMARK_MAIN();Интересное наблюдение: std::lower_bound очень неоптимизирован. Но и он быстрее линейного поиска при 60 элементах.
Загнал Ваши функции в свой цикл (25 миллионов прогонов, х циклически меняется от 1 до 25) применительно к конкретному массиву. Получилось
линейный - 0.42 - 0.45
бинарный - 0.47 - 0.50
Приведите весь код, пожалуйста. Очевидное объяснение различий было бы в том, что у вас меряется не среднее время работы, а лучшее - вроде как число x выбирается близким к началу. Линейный поиск быстро находит, а бинарный всегда работает примерно одинаковое время.
Но вы написли, что меняете x циклически... Поэтому очень интересно на код посмотреть.
Hidden text
int Linear(const int a[], int x) {
int ans = sizeof(a);
for (int i = 0; i < ans; ++i) {
if (a[i] >= x) return i;
}
return ans;
}
int Binary(const int a[], int x) {
int l = 0;
int r = sizeof(a) - 1;
int ans = sizeof(a);
while (l <= r) {
int m = l + (r - l) / 2;
if (a[m] >= x) {
ans = m;
r = m-1;
}
else {
l = m+1;
}
}
return ans;
}
int main()
{
int a[11] {3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21};
int sum = 0;
for(int idx {1}; idx < 25000000; idx++) {
sum += Linear(a, idx%25+1);
}
return sum;
}
Лоооооол, ну кто ж так массивы передаёт! У вас же a - указатель, и sizeof(a) - всегда либо 4, либо 8 в зависимости от разрядности.
Вот и ваша ошибка:
warning: ‘sizeof’ on array function parameter ‘a’ will return size of ‘const int*’ [-Wsizeof-array-argument]
У вас там фактически n=4 всегда. И ваши измерения почти совпадают с моими.
закинул длину в функцию отдельной переменной (да, я не плюсист), что дало для бинарного 0.87-0.89, для линейного 0.53-0.55
Код в студию! Вместе с тем, как вы меряете время, пожалуйста.
Ваши данные вообще не бьются со здравым смыслом. Линейный алгоритм при увеличении размера почти не замедлился (с 0.45 до 0.55), а логарифмический - замедлился почти в 2 раза (с 0.50 до 0.89).
Да вы что?
Вообще-то бинарный поиск никогда не относился к классическому программированию вообще никак. Сами догадаетесь почему? Нет?
И скорость работы "на порядки" высокую он имеет только на специальных массивах.
Отвечу на свой же вопрос. Бинарный поиск работает только на упорядоченных массивах.
А для этого массивы сначала надо упорядочить. А потому алгоритм бинарного поиска может быть быстрее только в специальных синтетических тестах, но никак не на практике.
Ибо, повторюсь, для его корректной работы сначала надо упорядочить массив, и только потом в нём что-то искать. Если массив "хаотичен", то бинарном поиском в нём можно найти только фигу, можно даже не одну.
По итогу сложность алгоритма + время сортировки массива + время бинарного поиска, не оставляют никаких шансов бинарному поиску в реальности. Обычный перебор позволяет найти искомые ключи за один полный проход любого (неупорядоченного) массива.
Во. Даже тут на хабре есть описание работы бинарного поиска.
Решение задач с использованием алгоритма бинарного поиска
И в ней русским по белому написано:
Для начала несколько слов о самом алгоритме. Задача, которую он решает, может быть сформулирована следующим образом: "найти в отсортированном массиве индекс элемента, значение которого соответствует заданному". Обычно массив отсортирован по возрастанию и в данной заметке мы будем предполагать, что это так и есть.
Потому "быстрый" (бинарный) поиск на практике не применяется. Эта задача показывает больше уровень таких вот интервьюеров, очень далеко отрывающихся от реальных задач, и глубоко уходящих в теорию и олимпиадные задачи. Именно к олимпиадным задачам бинарный поиск всегда и относился.
А для этого массивы сначала надо упорядочить. А потому алгоритм бинарного поиска может быть быстрее только в специальных синтетических тестах
Ну нет. Еще он работает, если вам надо много-много раз поискать в одном и том же наборе данных. Что не такая уж и редкость. Неужели вам сложно представить ситуацию, когда данные меняются редко, а читаются часто? Тогда стоимость сортировки размазывается по всем запросам и стремиться к нулю. Потом, данные иногда можно получать уже отсортированными (как в алгоритме нахождения максимальной возрастающей подпоследовательности).
Потому "быстрый" (бинарный) поиск на практике не применяется.
Да ладно. То, что вы его нигде не применяете, не значит, что это так. Вот вам несколько десятков применений в том же хромиуме.
Далее, очень частое применение бинпоиска вовсе даже не для поиска в отсортированном массиве, а для дихотомии по ответу. У вас вообще нет массива - он виртуальный. Вы ищите значение входного параметра, которое обращает в 0 некоторую монотонную функцию. Вот пример из хромиума.
главное, что я вынес из этой работы — проводить качественные собеседования очень непросто. Все дело в сигналах, которые мы посылаем и получаем. И у интервьюера, и у самого кандидата есть меньше часа, чтобы выложиться на полную. Порой, по разным причинам, мы получаем друг от друга ложные или неточные сигналы
Потому что мурыжить не надо людей! Задавая вопросы не по теме изображая из себя ботаника, потому что из-за комплексов хочется самоутвердится, а нечем, и вот начинается выпендреж знаниями (видео этих интервьюеров - ни внешности, ни добра в глазах, ни сил физических)
Вопрочы по тебе людям западвайте, не занимайтесь абстрактной ерундой с псевдо-воображаемыми экзаменами под воздействием синдрома вахтера.
Эх, студенты-студенты.
Вот решение:
f(a,x)
{
return x>0?a[x-1]:-1;
}
Так оно обычно в жизни.
Массив, фигурирующий в задаче, составлен нарочно таким образом, чтобы не включать 0 и отрицательные числа – это не добавило бы к решению задачи ровным счетом ничего. Элементов в массиве 11, что дает нам пространство индексов от 0 до 10. 10 легко делится на 2, поэтому среднюю точку можно определить без проблем – это число 12. Оно находится ровно посередине списка – это наш первый тест-кейс. А следующий пример, число 13, требует провести поиск уже в другой половине элементов. Все эти маленькие тонкости будут направлять интервью в нужное русло.
Из этого описания можно подумать, что массив фиксирован. А если так, то самым оптимальным по количеству кода, времени его написания, и по быстродействию будет это решение:
int f(int const x) {
static int const LUT[]{3, 4, 4, 6, 6, 6, 9, 10, 10, 12, 12, 14, 15, 15, 17, 17, 19, 19};
if(x < 3) return -1;
if(x >= 21) return 21;
return LUT[x - 3];
}
Моя любимая задачка по программированию для кодинг-интервью