В тексте есть упоминание гитхаба, но ссылки на проект нигде нет. Возможно, ссылка есть только в карточке публикации в ленте, но не в самом тексте. Я нагуглил вот это: https://github.com/SystemSoftware2/PearKernel
А вообще, ОС на питоне? Лол что? Вы серьезно?
Это не ОС. В лучшем случае, это хлипенькая очередь задач.
Как-то этот "простой" ответ идет вразрез с моим опытом.
Бывают исключения, а также когнитивные искажения.
А любой алгоритм/программа - это также еще и функция.
А еще это набор символов, тьюринг машина и много чего еще. Натягивать сову на глобус, конечно, можно, но зачем? Алгоритм и программа - почти синонимы, это самое точное и близкое описание (вы не просто так у себя в комментарии эти два слова через черту написали, как-будто это взаимозаменяемые понятия).
Не любая функция - программа, многие программы весьма сложно, а некоторые вообще невозможно описать в виде функции. Тут и побочные эффекты, и недетерменированность и многопоточность и много чего еще ломает такую абстракцию. А главное, почти весь функциональный анализ работает с непрерывными объектами: там и функции на множестве вещественных чисел и сами функции непрерывные почти везде. А те функции, которыми можно представить редкие программы - они дискретные. Функциональный анализ тут не применим. А вот дискретная математика - вполне. Поэтому она так пересекается с computer science.
С другой стороны, если вы пишите на функциональном языке программирования - вам пригодятся базовые знания лямбда исчисления.
Ответ прост: чтобы заметить, что вам нужны алгоритмы, вам надо эти алгоритмы на достаточно хорошем уровне знать.
Очень многие задачи на том же литкоде имеют наивное медленное решение, состоящее в тупо переводе с человеческого языка на язык программирования.
Когда же у программиста не задача на литкоде, а надо запилить фичу в проекте, то он у себя в голове додумывает, что надо сделать, и переводит это на язык программирования, получая наивное решение. Как таковая алгоритмическая задача вообще не воспринимается задачей, потому что она возникает как решение для бизнес-задачи. Дополнительно думать, какой алгоритм тут применить без насмотренности и навыков даже не возникнет идеи.
Вообще, любая программа (если только не на HTML /s) - это алгоритм по определению. Работа программиста - писать алгоритмы. Алгоритмы нужны всем и всегда. Распределение сложности алгоритмов разное в разных областях и чаще смещено в сторону простых алгоритмов, да. Но областей, где сложные алгоритмы вообще ни разу не нужны ничтожно мало, гораздо меньше чем, кажется.
Если у нас очень много номеров, и куда меньше диапазонов, то бинпоиск, похоже, побыстрее-то будет.
Нет, "слияние" будет всегда быстрее бинпоиска. Потому что это O(N+M), а бинпоиск это O(N + M log N). Если уж делать "За O(n) считаем maxB_i", то можно сразу же за O(M) пройтись и по всем точкам-запросам. Плюс не надо все B сохранять. Идея алгоритма одна и та же, но бинпоиск позволяет делать это online. "Слияние" работает только offline, но зато быстрее и требует меньше памяти.
Этоже не бинпоиск. Для бинпоиска надо, чтобы по текущему отрезку из середины было точно понятно, что искомая точка, если и лежит в каком-то отрезке, то точно в том, что слева или справа. Чтобы можно было выкинуть из рассмотрения одну половину всех отрезков.
Если отрезки упорядочены по началу, то может быть ситуация [1, 35] [10, 20] [30, 40]. И вот точка 25 лежит в первом отрезке - надо от отрезка [10, 20] идти влево, а точка 37 лежит в последнем отрезке, так что от [10, 20] надо идти вправо. И вот как вы по [10, 20] можете понять, что надо идти влево для 25 и вправо для 37? Никак. Точно такая же ситуация может быть, если отрезки упорядочить по концам или серединам
Слияние, да, можно заставить работать, но там чуть сложнее. Надо отсортировать отрезки по началам и помнить самый правый конец из пока что встреченных. Поддерживается инвариант, что от текущего начала до этого конца все покрыто. Если точка раньше начала отрезка - она не покрыта, если она от начала до конца (возможно предыдущего отрезка) - то она внутри. Иначе переходим к следующим отрезкам, пока начало не станет больше точки и смотрим, вдруг она станет покрыта чем-то.
Это похоже на приведенный мною алгоритм, но уже что-то другое более концептуально сложное.
На собесе, по крайней мере в фаангах, никогда не попросят написать кучу. Надо будет догадаться, что тут надо использовать кучу и правильно ее применить. А дальше можно использовать стандартную реализацию (например, priority_queue в C++). Более того, вы можете даже забыть какой там именно интерфейс, перепутать параметры или забыть, как методы называются. Если вы просто объясните, что есть вот такая структура данных, работает вот на таком принципе, вроде есть в стандартной библиотеке, но я не помню деталей, вам все зачтут и даже минусов не поставят скорее всего. Можно просто в комментариях написать, какой вы предполагаете у класса из библиотеки интерфейс и так его и использовать.
Более того, если вы начнете кучу на интервью писать, грамотный интервьювер вас остановит, чтобы вы не тратили на это время.
Это обратная сторона интервью без IDE. У вас нет автодополнения, но никто и не требует чтобы ваш код даже компилировался.
Тоже делается сортировкой и слиянием, если отрезки не пересекаются. Если первый номер в списке 1 входит в отрезок в начале списка 2, вы нашли вхождение, выкидывайте номер. Если первый номер левее начала первого отрезка, тоже выкидывайте номер из списка 1 (этот номер не входит в отрезки). Если первый номер правее конца первого отрезка - выкидывайте отрезок. "Выкидывайте" тут - это сдвиг указателя/индекса в списке. Делайте циклом while, пока хотя бы один список не кончился.
Если отрезки пересекаются, то и бинпоиск по отрезкам сделать нельзя.
Еще, если отрезки всегда задаются префиксом (т.е. вида XXX0...0-XXX9...9), то можно все отрезки загрузить в структуру данных бор (trie) по префиксам. Надо только. Потом искомые номера в этом боре искать, если дошли до финальной вершины (в которой один из префиксов закончился) - номер входит в отрезок, если перехода по следующей цифре нет - номера в отрезках нет. Это будет даже быстрее сортировки.
Пока не очень понял задачу, но если у вас есть список новых номеров в файле и список старых номеров, и надо найти пересечение, и оба списка сортированные, то самое быстрое и простое решение - выполнить операцию слияния, как в сортировке слиянием: Берете первые номера из двух списков, если они равны - вы нашли пересечение, перейдите к следующим номерам в обоих списках. Иначе сдвиньте указатель в том списке, где меньший из номеров. Это один цикл while и внутри сравнение двух номеров.
Если списки не сортированы, то возможно будет быстрее отсортировать меньший список и искать в нем бинпоиском. Или еще лучше, использовать хеш-таблицу.
Но, похоже вы там квадратичное решение соптимизировали, там что угодно быстрее будет.
В отборочных этапах чемпионата участвовало 9,8 тысяч человек из 50 стран
Но чемпионат называется РУкод и:
В соревновании участвовало 35 команд из России, Беларуси и Кыргызстана.
А также:
по решению Правительства России чемпионат получил международный статус.
Точно там из 50 стран участвовали 10 тысяч человек, или кто-то где-то что-то напутал или даже приукрасил для статуса? Просто какие-то нью-васюки получаются.
Еще раньше была смешная задачка, на которой все нейросети валились: Есть 8 монет: 7 маленьких и одна большая. Большая весит больше мелких монет, все мелкие - идентичные. Как мне найти большую монету?
Тут нейросетка коррелирует задачу с задачами на взвешивания, даже при том, что в условии ничего про весы не дано, а ответ лишь "посмотрите на размер монеты". Еще можно размер поменять на цвет или номинал.
Еще иногда срабатывала задача про осла, козу, волка и лодку, только в лодку помещаются все, но нейросеть выдает известное решение с маленькой лодкой.
Это потому, что у нейросети нет логики. Она лишь изображает логические рассуждения, потому что получившийся поток токенов статистически похож на то, что она уже видела. К сожалению, эти галлюцинации достаточно часто срабатывают, чтобы созадвать вау-эффект и высокие ожидания сильного ИИ.
протоколы безопасности, стабильность соединения, потери пакетов и т.п.
Вы совсем не правы. Все эти перечисленные проблемы уже решаются WebRTC на стороне браузера во всех сущуствующих продуктах для видео/аудио звонков через браузер.
Все, что ему нужно от сервера - это один раз в начале передать строку SDP между хостами, STUN сервер для пробития NAT, да TURN сервер, если дырки в NAT проковырять не получается. Можно на STUN и забить и использовать только TURN. И простой JS скрипт для запуска WebRTC (это называется PeerConnection) умещается на пару экранов неминифицированного JS кода.
Более сложный бакенд, вроде Microsoft Teams, Google Meet нужен только если вы хотите устраивать конференции с несколькими участниками. Тут уже нужен Selective Forwarding Unit вместо TURN сервера, да и логика клиента будет сильно сложнее. Но этот случай не рассматривается тут и во всех этих "миллионах продуктов на гитхабе".
Обычное деление в столбик тоже использует только вычитание и сдвиги. Вычитание ничем принципиально от сложения не отличается.
Имеет очевидное доказательство корректности.
У вас не самое простое доказательство. Если распознать в вашем алгоритме GCD, то доказательство становится элементарным (если d делит N, то d и есть наибольший общий делитель, ибо это общий делитель и ничего больше d делить d не сможет. И наоборот, если d общий делитель - то N уже делиться на d по определению).
а малым размером схемы в ПЛИС и простотой потоковой обработки.
Ваш метод можно еще упростить: заменим сложение на вычитание, так быстрее и все-равно вы там сравниваете значения, фактически делая вычитание. Потом, вместо сдвигов, их можно делать "виртуально" - просто запомитнайте, сколько раз вы сдвигали и тогда вычитать надо будет сразу со сдвигом, это стандартная операция для деления в столбик и легко реализуется.
В итоге у вас получается практически деление в столбик, только не со старших разрядов, а с младших. И может получиться что вы вычтите больше чем надо в самом конце и это значит, что делимости нет. Если в конце получится 0 - делимость есть.
В итоге метод ничем не проще самого простого деления в столбик.
Очень странная структура. Она работает быстро только для весьма равномерно распределенных ключей во всем диапазоне значений, что на практике далеко не всегда бывает. В противном случае там почти гарантирована линейная сложность из-за длинной цепочки коллизии.
В тексте есть упоминание гитхаба, но ссылки на проект нигде нет. Возможно, ссылка есть только в карточке публикации в ленте, но не в самом тексте. Я нагуглил вот это: https://github.com/SystemSoftware2/PearKernel
А вообще, ОС на питоне? Лол что? Вы серьезно?
Это не ОС. В лучшем случае, это хлипенькая очередь задач.
Бывают исключения, а также когнитивные искажения.
А еще это набор символов, тьюринг машина и много чего еще. Натягивать сову на глобус, конечно, можно, но зачем? Алгоритм и программа - почти синонимы, это самое точное и близкое описание (вы не просто так у себя в комментарии эти два слова через черту написали, как-будто это взаимозаменяемые понятия).
Не любая функция - программа, многие программы весьма сложно, а некоторые вообще невозможно описать в виде функции. Тут и побочные эффекты, и недетерменированность и многопоточность и много чего еще ломает такую абстракцию. А главное, почти весь функциональный анализ работает с непрерывными объектами: там и функции на множестве вещественных чисел и сами функции непрерывные почти везде. А те функции, которыми можно представить редкие программы - они дискретные. Функциональный анализ тут не применим. А вот дискретная математика - вполне. Поэтому она так пересекается с computer science.
С другой стороны, если вы пишите на функциональном языке программирования - вам пригодятся базовые знания лямбда исчисления.
Ответ прост: чтобы заметить, что вам нужны алгоритмы, вам надо эти алгоритмы на достаточно хорошем уровне знать.
Очень многие задачи на том же литкоде имеют наивное медленное решение, состоящее в тупо переводе с человеческого языка на язык программирования.
Когда же у программиста не задача на литкоде, а надо запилить фичу в проекте, то он у себя в голове додумывает, что надо сделать, и переводит это на язык программирования, получая наивное решение. Как таковая алгоритмическая задача вообще не воспринимается задачей, потому что она возникает как решение для бизнес-задачи. Дополнительно думать, какой алгоритм тут применить без насмотренности и навыков даже не возникнет идеи.
Вообще, любая программа (если только не на HTML /s) - это алгоритм по определению. Работа программиста - писать алгоритмы. Алгоритмы нужны всем и всегда. Распределение сложности алгоритмов разное в разных областях и чаще смещено в сторону простых алгоритмов, да. Но областей, где сложные алгоритмы вообще ни разу не нужны ничтожно мало, гораздо меньше чем, кажется.
Да, вы правы, если номеров сильно больше отрезков, бинпоиск будет лучше.
Нет, "слияние" будет всегда быстрее бинпоиска. Потому что это O(N+M), а бинпоиск это O(N + M log N). Если уж делать "За O(n) считаем maxB_i", то можно сразу же за O(M) пройтись и по всем точкам-запросам. Плюс не надо все B сохранять. Идея алгоритма одна и та же, но бинпоиск позволяет делать это online. "Слияние" работает только offline, но зато быстрее и требует меньше памяти.
Этоже не бинпоиск. Для бинпоиска надо, чтобы по текущему отрезку из середины было точно понятно, что искомая точка, если и лежит в каком-то отрезке, то точно в том, что слева или справа. Чтобы можно было выкинуть из рассмотрения одну половину всех отрезков.
Если отрезки упорядочены по началу, то может быть ситуация [1, 35] [10, 20] [30, 40]. И вот точка 25 лежит в первом отрезке - надо от отрезка [10, 20] идти влево, а точка 37 лежит в последнем отрезке, так что от [10, 20] надо идти вправо. И вот как вы по [10, 20] можете понять, что надо идти влево для 25 и вправо для 37? Никак. Точно такая же ситуация может быть, если отрезки упорядочить по концам или серединам
Слияние, да, можно заставить работать, но там чуть сложнее. Надо отсортировать отрезки по началам и помнить самый правый конец из пока что встреченных. Поддерживается инвариант, что от текущего начала до этого конца все покрыто. Если точка раньше начала отрезка - она не покрыта, если она от начала до конца (возможно предыдущего отрезка) - то она внутри. Иначе переходим к следующим отрезкам, пока начало не станет больше точки и смотрим, вдруг она станет покрыта чем-то.
Это похоже на приведенный мною алгоритм, но уже что-то другое более концептуально сложное.
На собесе, по крайней мере в фаангах, никогда не попросят написать кучу. Надо будет догадаться, что тут надо использовать кучу и правильно ее применить. А дальше можно использовать стандартную реализацию (например, priority_queue в C++). Более того, вы можете даже забыть какой там именно интерфейс, перепутать параметры или забыть, как методы называются. Если вы просто объясните, что есть вот такая структура данных, работает вот на таком принципе, вроде есть в стандартной библиотеке, но я не помню деталей, вам все зачтут и даже минусов не поставят скорее всего. Можно просто в комментариях написать, какой вы предполагаете у класса из библиотеки интерфейс и так его и использовать.
Более того, если вы начнете кучу на интервью писать, грамотный интервьювер вас остановит, чтобы вы не тратили на это время.
Это обратная сторона интервью без IDE. У вас нет автодополнения, но никто и не требует чтобы ваш код даже компилировался.
Тоже делается сортировкой и слиянием, если отрезки не пересекаются. Если первый номер в списке 1 входит в отрезок в начале списка 2, вы нашли вхождение, выкидывайте номер. Если первый номер левее начала первого отрезка, тоже выкидывайте номер из списка 1 (этот номер не входит в отрезки). Если первый номер правее конца первого отрезка - выкидывайте отрезок. "Выкидывайте" тут - это сдвиг указателя/индекса в списке. Делайте циклом while, пока хотя бы один список не кончился.
Если отрезки пересекаются, то и бинпоиск по отрезкам сделать нельзя.
Еще, если отрезки всегда задаются префиксом (т.е. вида XXX0...0-XXX9...9), то можно все отрезки загрузить в структуру данных бор (trie) по префиксам. Надо только. Потом искомые номера в этом боре искать, если дошли до финальной вершины (в которой один из префиксов закончился) - номер входит в отрезок, если перехода по следующей цифре нет - номера в отрезках нет. Это будет даже быстрее сортировки.
Я не автор, но у меня есть статья как раз об этом: https://habr.com/ru/articles/962688/
Пока не очень понял задачу, но если у вас есть список новых номеров в файле и список старых номеров, и надо найти пересечение, и оба списка сортированные, то самое быстрое и простое решение - выполнить операцию слияния, как в сортировке слиянием: Берете первые номера из двух списков, если они равны - вы нашли пересечение, перейдите к следующим номерам в обоих списках. Иначе сдвиньте указатель в том списке, где меньший из номеров. Это один цикл while и внутри сравнение двух номеров.
Если списки не сортированы, то возможно будет быстрее отсортировать меньший список и искать в нем бинпоиском. Или еще лучше, использовать хеш-таблицу.
Но, похоже вы там квадратичное решение соптимизировали, там что угодно быстрее будет.
Вот где - в фаангах, и в частности, в гугле. Посмотрте, у меня несколько статей на эту тему.
Но чемпионат называется РУкод и:
А также:
Точно там из 50 стран участвовали 10 тысяч человек, или кто-то где-то что-то напутал или даже приукрасил для статуса? Просто какие-то нью-васюки получаются.
Еще раньше была смешная задачка, на которой все нейросети валились: Есть 8 монет: 7 маленьких и одна большая. Большая весит больше мелких монет, все мелкие - идентичные. Как мне найти большую монету?
Тут нейросетка коррелирует задачу с задачами на взвешивания, даже при том, что в условии ничего про весы не дано, а ответ лишь "посмотрите на размер монеты". Еще можно размер поменять на цвет или номинал.
Еще иногда срабатывала задача про осла, козу, волка и лодку, только в лодку помещаются все, но нейросеть выдает известное решение с маленькой лодкой.
Это потому, что у нейросети нет логики. Она лишь изображает логические рассуждения, потому что получившийся поток токенов статистически похож на то, что она уже видела. К сожалению, эти галлюцинации достаточно часто срабатывают, чтобы созадвать вау-эффект и высокие ожидания сильного ИИ.
Кажется не совсем - гвоздь вращается вокруг штыря не в ту сторону. Или это моя зрительная нейронка сбоит?
Вы совсем не правы. Все эти перечисленные проблемы уже решаются WebRTC на стороне браузера во всех сущуствующих продуктах для видео/аудио звонков через браузер.
Все, что ему нужно от сервера - это один раз в начале передать строку SDP между хостами, STUN сервер для пробития NAT, да TURN сервер, если дырки в NAT проковырять не получается. Можно на STUN и забить и использовать только TURN. И простой JS скрипт для запуска WebRTC (это называется PeerConnection) умещается на пару экранов неминифицированного JS кода.
Более сложный бакенд, вроде Microsoft Teams, Google Meet нужен только если вы хотите устраивать конференции с несколькими участниками. Тут уже нужен Selective Forwarding Unit вместо TURN сервера, да и логика клиента будет сильно сложнее. Но этот случай не рассматривается тут и во всех этих "миллионах продуктов на гитхабе".
Дело в том, что оно тут не выдало аргументов по факту, а лишь сгаллюционировало убедительно смотрящуюся, но бессмысленную и лишенную ценности отрыжку.
Это бред. У вас там есть сравнение и ветвление.
Вообще ни на чем не основанное утверждение. Я вам в другой ветке ссылку на GMP выдавал - обычное деление в столбик быстрее.
А может и не дать.
ИИ выхлоп ощущается в этом вашем комментарии. Не надо так.
Обычное деление в столбик тоже использует только вычитание и сдвиги. Вычитание ничем принципиально от сложения не отличается.
У вас не самое простое доказательство. Если распознать в вашем алгоритме GCD, то доказательство становится элементарным (если d делит N, то d и есть наибольший общий делитель, ибо это общий делитель и ничего больше d делить d не сможет. И наоборот, если d общий делитель - то N уже делиться на d по определению).
Ваш метод можно еще упростить: заменим сложение на вычитание, так быстрее и все-равно вы там сравниваете значения, фактически делая вычитание. Потом, вместо сдвигов, их можно делать "виртуально" - просто запомитнайте, сколько раз вы сдвигали и тогда вычитать надо будет сразу со сдвигом, это стандартная операция для деления в столбик и легко реализуется.
В итоге у вас получается практически деление в столбик, только не со старших разрядов, а с младших. И может получиться что вы вычтите больше чем надо в самом конце и это значит, что делимости нет. Если в конце получится 0 - делимость есть.
В итоге метод ничем не проще самого простого деления в столбик.
Очень странная структура. Она работает быстро только для весьма равномерно распределенных ключей во всем диапазоне значений, что на практике далеко не всегда бывает. В противном случае там почти гарантирована линейная сложность из-за длинной цепочки коллизии.
Ниже написал. Инвариант - у вас сохраняется GCD(X,d) (исключая степень двойки). Этого действительно достаточно для проверки на делимость.