По сути мы столкнулись с наплывом самозванцев в науку, которые не стремятся к истине или служению человечеству, а стремятся к личной корыстной выгоде.
Многие тут говорили, что это следствие высокой конкуренции и низкого финансирования в науке, но мне кажется, что как раз наоборот — дело в высоком финансировании и большом престиже науки. Такие вещи всегда привлекают карьеристов, самозванцев и шарлатанов. Ведь там, где крутятся большие деньги, можно хорошо нагреть руки.
Я думаю, проблема решится сама собой в ходе катастрофы:
1) Деградация науки из-за наплыва самозванцев и шарлатанов продолжится.
2) Наступит момент, когда наука и учёные утратят авторитет в обществе. Из телевизора снова вылезут экстрасенсы и будут «заряжать банки». Политика и правящий класс в значительной мере прекратят финансирование науки из-за того, что это перестанет быть выгодным.
3) Положение учёных резко ухудшится. Это приведёт к массовому оттоку кадров. Но в первую очередь побегут корыстные карьеристы, приоритет которых — личная выгода, а не какая-то там абстрактная истина.
4) В науке останутся только энтузиасты-аскеты, которых деньги и престиж особо не интересуют, а интересует сама наука. Что-то подобное началу 90х годов в постсоветской науке, когда разбежался учёный и преподавательский состав, кроме приверженцев своего дела.
5) И вот эти энтузиасты сохранят знания и подготовят следующее поколение учёных, которые также пойдут в науку не за длинным рублём, а по призванию. Наука возродится на пепелище, как лес после пожара.
Поддерживаю. В своё время получал статьи на ревью. Какие-то мутные исследования, которые выглядят неинтересно и сомнительно. Разбираться в них детально — надо тратить много времени. И это неприятная работа. Отвлекает от основной работы — собственных разработок, опытов, обработки данных, оформления результатов. И написать негативный отзыв — это требует определённой жестокости. Зарубить чью-то работу, а ведь люди старались.
Смена работы тоже важный момент. Без этого никакими силами невозможно себя заставить. Если на каком-то месте работы скатился в «прокастинацию» — то никакими внутренними силами это не исправить. Ну разве если только начальство прищучит. Но почему-то оно, если сразу не прищучило — то и потом не трогает.
А о том, сколько конкретный сотрудник работает и сколько играет — на самом деле известно всем. Это видно, как ни «скрывайся».
Мне помогла смена работы и жёсткая самодисциплина с первого дня:
1) Никаких частных занятий в офисе. Только по работе. В том числе никаких игр и сайтов, никаких частных разговоров по мобилке. Если ждёшь компиляции или ещё чего-нибудь — значит ждёшь. Можно заняться другим рабочим делом, пойти сварить кофе или переговорить с коллегой.
В результате, приходя в офис, автоматически и без усилий вхожу в состояние потока на весь рабочий день и даже больше. И наоборот, дома, для каких-то личных проектов, с этим полная катастрофа. То сайты, то видосики, то игры.
В датчиках движения нет необходимости формировать изображение. Там достаточно одного пикселя. И пластиковая «оптика», возможно, играет там лишь роль защиты чувствительного элемента, а не линзы. От линзы ведь требуется не только пропускание излучения, но и его преломление.
Если там нужна оптика — то прибор инфракрасного видения не станет сильно дешевле. Ведь для дальнего инфракрасного света нужны линзы из германия, который дорогой.
Мне тоже в последнее время приходится реализовывать конечные автоматы. Главная проблема — это то, что программа не содержит описания набора состояний и переходов между ними в кратком и явном виде. Логика программы оказывается разбросанной по разным, слабо связанным между собой, частям. Вот эту бы проблему решить.
Рост хешрейта может происходить не только за счёт видеокарт, но и за счёт FPGA- и ASIC-плат. Причём те, кто эксплуатирует майнеры на этой базе, не особенно заинтересованы в распространении этой информации, ведь от этого в их нишу все ринутся, и прибыльность упадёт.
Вы правы, я ошибся. Конечно же, надо просматривать весь массив каждый раз, а не его часть, как мне первоначально показалось. Тогда, как вы и написали, будет O(n log n).
Хорошо, уточню, ошибся. Первый раз вы просматриваете n элементов, потом n/2, потом n/4 и т.д. Сумма 1+1/2+1/4+1/8+… = 2.
Так что максимальное суммарное количество элементов, которые придётся просмотреть, равно 2n. А это означает O(n), не так ли?
Если бы было O(n log n) — то были бы другие зависимости. Например, для n=10 потребовалось бы 10 итераций, для n=100 — 200 итераций, для n=1000 — 3000 итераций и т.д., то есть количество итераций растёт быстрее, чем const*n. Или, что то же самое, отношение количества итераций к n растёт неограниченно (хотя и медленно).
В вашем же случае неограниченного роста отношения количества итераций к n нет, отношение остаётся константой, не зависящей от n.
При использовании солнечной, ветровой, гидро- и прочей «возобновляемой» энергии необратимо расходуется водород на Солнце. Там его запасы тоже ограничены. Всё в этой вселенной конечно, увы.
Вот и получается O(n log n). log n итераций бинпоиска, каждая за O(n) вычисляет элемент ответа
По-моему здесь всё-таки сложность O(n), а не O(n log n), так как поиск по оставшейся половине требует просмотра каждый раз в 2 раза меньшего кол-ва элементов. И это существенно. Ведь сумма 1/2+1/4+1/8+… = 1. Общее количество просмотренных элементов не превысит n независимо от того, сколько раз алгоритм делил массив пополам.
вы дали ограничение по скорости и по памяти, но не сказали объем данных
Почему вы с таким упорством отрицаете O-нотацию? Вам уже десятки людей на неё указали, даже авторы задачи.
Там, где условие задачи неполное — надо его самостоятельно дополнять. Что мы знаем из условия? Что «Озон» хочет реализовать это решение для базы своих пользователей. Много ли пользователей у «Озона»? Наверное много, это большая фирма. Настолько ли много, что вся база не помещается в ОЗУ? Это вряд ли, так как такие задачи редко дают в качестве тестовых. В тестовых заданиях обычно идёт упор на академические знания.
А академические знания — это асимптотика и O-нотация.
И вот, в чём заключается её сила. Если алгоритмы O(n) могут отличаться друг от друга по скорости в разы или даже десятки раз — то O(n) от O(n^2) будет при больших n отличаться в тысячи, миллионы и миллиарды раз. Например, если при некотором большом n разные алгоритмы со сложностью O(n) выполняются 1, 5 и 10 минут каждый, то очень вероятно, что даже вылизанный и оптимизированный O(n^2) алгоритм будет работать неделями или месяцами. Здесь огромная разница, и «копейки» можно не считать.
Всегда можно найти такое n, что, начиная с него, любой наперёд заданный алгоритм O(n) будет работать быстрее, чем O(n^2).
k можно взять равным половине количества учётных записей пользователей. Найдя кол-во чисел, меньших k, можно установить, находится ли минимальный отсутствующий элемент в первой половине массива. Если да — то применить этот же алгоритм рекурсивно для первой половины массива. Если нет — то применить его для второй половины массива и т.д.
Очень хорошая идея, кстати. По-моему этот алгоритм имеет сложность O(n), а не O(n*log(n)). И по сравнению с другими описанными здесь алгоритмами с O(n), он по памяти имеет сложность O(1) и не портит исходный массив. Так что очень привлекательный алгоритм.
Я тоже думал предложить отложенный xor. Более того, несколько операций «шифрования» эквивалентны одной, у которой ключ — исключающее «или» от всех предыдущих ключей.
Проблема в том, что отложить xor можно только до следующего добавления, так как до и после ксорки минимальные свободные ID различаются.
В контексте исходной «озоновской» задачи можно попытаться ввести в структуру данных какие-нибудь инварианты, которые поддерживаются при её работе и облегчают выполнение операций.
В задаче требуется сделать только операции добавления и «шифрования». Оставим пока в стороне «шифрование» и рассмотрим только структуру данных с операцией добавления.
Если исходная база была пустой, то новый id пользователя всегда равен количеству уже зарегистрированных, и никакой поиск делать не надо. Таким образом, отсутствие пропусков в нумерации — это инвариант, которым можно воспользоваться.
Дырки в нумерации могли бы образоваться за счёт удаления пользователей, но удаление нас реализовать не просят. Возможно, это от «Озона» специальная ловушка, и они ожидают, что вы: 1) зададите вопрос, а точно ли им не нужно удаление; 2) по своей инициативе сделаете удаление.
Если делать удаление — то массив занятых id останется отсортированным. А в отсортированном случае можно найти пропуск быстрее, чем за O(n), а именно, за O(log(n)). Смотрим на средний элемент массива и проверяем, есть ли в первой половине пропуски. Критерий: values[n/2]>n/2. Если есть — ищем дальше в первой половине массива, в противном случае — во второй.
Таким образом, отсортированный массив id — это второй возможный инвариант.
Теперь рассмотрим «шифрование». Даже если в массиве id до «шифрования» не было пропусков — то после «шифрования» они появятся. Но операция «шифрования», вероятно, выполняется реже, чем добавление новых пользователей. Поэтому есть смысл делать сортировку массива id при «шифровании», тогда для поиска свободного id будем всегда иметь отсортированный массив занятых id.
Можно также попытаться воспользоваться свойствами операции «исключающее или» для облегчения сортировки. Подозреваю, что, если исходный массив был отсортирован, а потом все его элементы сложили по модулю 2 с константой — то отсортировать полученный массив можно быстрее, чем в общем случае.
По современным меркам, космическая станция длиной в 121м — это всё-таки многовато. Вся МКС не имеет такого линейного размера, а сколько лет она строилась.
Бороться не нужно? Соглашусь, но только по причине безнадёжности такой борьбы и неравенства сил. Внутренне же соглашаться с широким внедрением нерациональных подходов считаю близорукостью мышления.
Указанные явления суть не что иное, как обыкновенный догматизм. Буду знать, что нынче в моде сеттеры и геттеры. Ну а завтра им на смену придёт какая-нибудь другая «панацея». Технологии меняются, люди — нет.
Многие тут говорили, что это следствие высокой конкуренции и низкого финансирования в науке, но мне кажется, что как раз наоборот — дело в высоком финансировании и большом престиже науки. Такие вещи всегда привлекают карьеристов, самозванцев и шарлатанов. Ведь там, где крутятся большие деньги, можно хорошо нагреть руки.
Я думаю, проблема решится сама собой в ходе катастрофы:
1) Деградация науки из-за наплыва самозванцев и шарлатанов продолжится.
2) Наступит момент, когда наука и учёные утратят авторитет в обществе. Из телевизора снова вылезут экстрасенсы и будут «заряжать банки». Политика и правящий класс в значительной мере прекратят финансирование науки из-за того, что это перестанет быть выгодным.
3) Положение учёных резко ухудшится. Это приведёт к массовому оттоку кадров. Но в первую очередь побегут корыстные карьеристы, приоритет которых — личная выгода, а не какая-то там абстрактная истина.
4) В науке останутся только энтузиасты-аскеты, которых деньги и престиж особо не интересуют, а интересует сама наука. Что-то подобное началу 90х годов в постсоветской науке, когда разбежался учёный и преподавательский состав, кроме приверженцев своего дела.
5) И вот эти энтузиасты сохранят знания и подготовят следующее поколение учёных, которые также пойдут в науку не за длинным рублём, а по призванию. Наука возродится на пепелище, как лес после пожара.
А о том, сколько конкретный сотрудник работает и сколько играет — на самом деле известно всем. Это видно, как ни «скрывайся».
1) Никаких частных занятий в офисе. Только по работе. В том числе никаких игр и сайтов, никаких частных разговоров по мобилке. Если ждёшь компиляции или ещё чего-нибудь — значит ждёшь. Можно заняться другим рабочим делом, пойти сварить кофе или переговорить с коллегой.
В результате, приходя в офис, автоматически и без усилий вхожу в состояние потока на весь рабочий день и даже больше. И наоборот, дома, для каких-то личных проектов, с этим полная катастрофа. То сайты, то видосики, то игры.
Мне тоже в последнее время приходится реализовывать конечные автоматы. Главная проблема — это то, что программа не содержит описания набора состояний и переходов между ними в кратком и явном виде. Логика программы оказывается разбросанной по разным, слабо связанным между собой, частям. Вот эту бы проблему решить.
Так что максимальное суммарное количество элементов, которые придётся просмотреть, равно 2n. А это означает O(n), не так ли?
Если бы было O(n log n) — то были бы другие зависимости. Например, для n=10 потребовалось бы 10 итераций, для n=100 — 200 итераций, для n=1000 — 3000 итераций и т.д., то есть количество итераций растёт быстрее, чем const*n. Или, что то же самое, отношение количества итераций к n растёт неограниченно (хотя и медленно).
В вашем же случае неограниченного роста отношения количества итераций к n нет, отношение остаётся константой, не зависящей от n.
(с) Артур Блох, «Закон Мерфи»
По-моему здесь всё-таки сложность O(n), а не O(n log n), так как поиск по оставшейся половине требует просмотра каждый раз в 2 раза меньшего кол-ва элементов. И это существенно. Ведь сумма 1/2+1/4+1/8+… = 1. Общее количество просмотренных элементов не превысит n независимо от того, сколько раз алгоритм делил массив пополам.
Почему вы с таким упорством отрицаете O-нотацию? Вам уже десятки людей на неё указали, даже авторы задачи.
Там, где условие задачи неполное — надо его самостоятельно дополнять. Что мы знаем из условия? Что «Озон» хочет реализовать это решение для базы своих пользователей. Много ли пользователей у «Озона»? Наверное много, это большая фирма. Настолько ли много, что вся база не помещается в ОЗУ? Это вряд ли, так как такие задачи редко дают в качестве тестовых. В тестовых заданиях обычно идёт упор на академические знания.
А академические знания — это асимптотика и O-нотация.
И вот, в чём заключается её сила. Если алгоритмы O(n) могут отличаться друг от друга по скорости в разы или даже десятки раз — то O(n) от O(n^2) будет при больших n отличаться в тысячи, миллионы и миллиарды раз. Например, если при некотором большом n разные алгоритмы со сложностью O(n) выполняются 1, 5 и 10 минут каждый, то очень вероятно, что даже вылизанный и оптимизированный O(n^2) алгоритм будет работать неделями или месяцами. Здесь огромная разница, и «копейки» можно не считать.
Всегда можно найти такое n, что, начиная с него, любой наперёд заданный алгоритм O(n) будет работать быстрее, чем O(n^2).
Очень хорошая идея, кстати. По-моему этот алгоритм имеет сложность O(n), а не O(n*log(n)). И по сравнению с другими описанными здесь алгоритмами с O(n), он по памяти имеет сложность O(1) и не портит исходный массив. Так что очень привлекательный алгоритм.
Проблема в том, что отложить xor можно только до следующего добавления, так как до и после ксорки минимальные свободные ID различаются.
Можно даже сделать две «лопасти», вращающиеся в противоположные стороны, тогда не нужно будет тратить реактивное топливо на раскрутку и остановку.
В контексте исходной «озоновской» задачи можно попытаться ввести в структуру данных какие-нибудь инварианты, которые поддерживаются при её работе и облегчают выполнение операций.
В задаче требуется сделать только операции добавления и «шифрования». Оставим пока в стороне «шифрование» и рассмотрим только структуру данных с операцией добавления.
Если исходная база была пустой, то новый id пользователя всегда равен количеству уже зарегистрированных, и никакой поиск делать не надо. Таким образом, отсутствие пропусков в нумерации — это инвариант, которым можно воспользоваться.
Дырки в нумерации могли бы образоваться за счёт удаления пользователей, но удаление нас реализовать не просят. Возможно, это от «Озона» специальная ловушка, и они ожидают, что вы: 1) зададите вопрос, а точно ли им не нужно удаление; 2) по своей инициативе сделаете удаление.
Если делать удаление — то массив занятых id останется отсортированным. А в отсортированном случае можно найти пропуск быстрее, чем за O(n), а именно, за O(log(n)). Смотрим на средний элемент массива и проверяем, есть ли в первой половине пропуски. Критерий: values[n/2]>n/2. Если есть — ищем дальше в первой половине массива, в противном случае — во второй.
Таким образом, отсортированный массив id — это второй возможный инвариант.
Теперь рассмотрим «шифрование». Даже если в массиве id до «шифрования» не было пропусков — то после «шифрования» они появятся. Но операция «шифрования», вероятно, выполняется реже, чем добавление новых пользователей. Поэтому есть смысл делать сортировку массива id при «шифровании», тогда для поиска свободного id будем всегда иметь отсортированный массив занятых id.
Можно также попытаться воспользоваться свойствами операции «исключающее или» для облегчения сортировки. Подозреваю, что, если исходный массив был отсортирован, а потом все его элементы сложили по модулю 2 с константой — то отсортировать полученный массив можно быстрее, чем в общем случае.
То есть да, технически возможно, но очень дорого.
Бороться не нужно? Соглашусь, но только по причине безнадёжности такой борьбы и неравенства сил. Внутренне же соглашаться с широким внедрением нерациональных подходов считаю близорукостью мышления.
Указанные явления суть не что иное, как обыкновенный догматизм. Буду знать, что нынче в моде сеттеры и геттеры. Ну а завтра им на смену придёт какая-нибудь другая «панацея». Технологии меняются, люди — нет.