Не могу согласиться.
Возьмем n = 2²⁰, тогда в худшем (и лучшем тоже) случае надо будет пройти (1+2+4+8...+2²⁰)*2 вагонов, чтобы убедиться, что мы выключили свет везде. Умножение на 2 — это проход туда и обратно. После чего надо сделать один полный проход с подсчетом. Количество слагаемых в скобках — lg(n). Каждое из слагаемых можно грубо принять за n (асимпотика же ¯\_(ツ)_/¯). Т.е. мы 2*lg(n) раз прошли n вагонов, чтобы убедиться в том, что обошли весь поезд + 1 раз прошли n вагонов для подсчета. Получается O(n*(1+2*lg(n))) или O(n*lg(n)).
Справедливости ради нижний асимптотический предел сложности такой же как и верхний с точностью до константы Ω(n*lg(n)) ⇒ Θ(n*lg(n)). А это может значить, что на больших и очень разреженных составах (почти везде свет выключен) алгоритм «в лоб» может работать лучше.
Решение в лоб:
Включаем в исходном вагоне свет. Идем в одну из сторон до тех пор, пока не встретим вагон со светом, попутно считая количество пройденных вагонов. Примем число пройденных вагонов за c. Выключаем в этом вагоне свет. Возвращаемся в обратную сторону на c шагов, чтобы оказаться в изначальном вагоне. Если свет в вагоне выключен, то число вагонов в поезде c, алгоритм завершен. Если свет в вагоне включен, то опять идем в произвольную сторону до первого вагона с включенным светом, считая вагоны.
Частный случай — 1 вагон. Включаем свет. Выходим из вагона в соседний и оказываемся в изначальном вагоне. c = 1. Выключаем свет. Возвращаемся на 1 вагон назад. Оказывамся в вагоне с выключенным светом => кол-во вагонов равно 1.
Асимптотическая сложность алгоритма:
O(n²) — везде свет включен;
Ω(n) — свет включен только в изначальном вагоне.
Для улучшения вычислительной сложности (не асимптотической) можно использовать не один вагон с включенным светом, а паттерн, например, из трех вагонов (включен, выключен. включен) и при нахождении такого же паттерна возвращаться назад на c вагонов и проверять.
А как определить, что ты уже все включил? Вот идешь ты по вагонам, включаешь свет. А потом 500 вагонов подряд свет включен. И какой вывод из этого делать? Во всех вагонах свет включен? Или же в 501 выключен? Пройти еще 500? А если и там включен, а в 1001 выключен? Когда остановиться и начать выключать?
Идея состоит в рекурсивном разбиении области на четыре части (квадранта) по отношению к центральной точке.
Как происходит процесс вычисления центральной точки в дереве квадрантов? Медианы по обеим осям? Половина разности максимального и минимального значений x и y? Или какой-то более сложный алгоритм? Как вычисляется центральная точка, если построить индекс по пустой таблице? Может ли получиться, что после заполнения таблицы, в которой уже присутствует sp-gist индекс, все точки будут в одном квадранте верхнего уровня, а 3 других будут пустыми?
По факту, сайты многих частных компаний, онлайн игр, крупных и даже мелких производителей озвучены в разы лучше, чем государственный ресурс.
А все потому, что государственные организации платят программистам значительно меньше, чем частные компании. Найти хороших специалистов на такую зарплату очень сложно. Соответственно и сидят там часто недавние студенты и люди, для которых работа «лишь бы была». Ни у тех ни у других обычно нет необходимых навыков.
Это не говоря уже о том, что для гос. организаций зачастую выполнение требований закона гораздо важнее конечного результата. Какой еще WCAG? Зачем проверять доступность с клавиатуры и со скринридером? В приказе №483 Минсвязи сказано, что на сайте должны быть кнопки для изменения размера и цвета шрифта, вот и делайте это. А удобно конечному пользователю или нет, мало кого волнует.
Зато объем потребления воды больше.
В случае решения ТС идет 3 раза заполенние по 3 литра и 1 раз выливание 5 литров.
В случае решения выше получаем 2 заполнения по 5 литров (на литр больше) и одно выливание 3 литров
Python 3.5.2 (v3.5.2:4def2a2901a5, Jun 25 2016, 22:01:18) [MSC v.1900 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> from elizabeth import Personal
>>> user = Personal('is')
>>> for _ in range(0, 9):
... print(user.full_name(gender='male'))
...
Traceback (most recent call last):
File "<stdin>", line 2, in <module>
File "C:\Users\mainj\AppData\Local\Programs\Python\Python35-32\lib\encodings\cp437.py", line 19, in encode
return codecs.charmap_encode(input,self.errors,encoding_map)[0]
UnicodeEncodeError: 'charmap' codec can't encode character '\xf0' in position 5: character maps to <undefined>
Нетекстовые данные (и текстовые на английском) нормально генерируются.
У сайта не должно быть возможности связать личность пользователя в режиме инкогнито с разным IP с VPN и без него. В случае быстрого отключения VPN, уровень заряда аккумулятора будет примерно одинаковым. Считав эту информацию, браузер передаст ее сайту. Два набора данных будут сопоставлены и можно будет сделать вывод, что пользователь один и тот же.
Странное решение. Мне кажется было бы разумнее запрашивать у пользователя разрешение на использование Battery Status API, а не удалять его полностью. А то следуя этой логике они должны вообще никогда не реализовывать ни одну из спецификаций сенсоров: Gyroscope Sensor Proximity Sensor Ambient Light Sensor Magnetometer Sensor Generic Sensor API
и кучу других спецификаций, дающих хоть какую-то информацию об устройстве, geolocation, mediastream, bluetooth (это я уже утрирую).
По ним ведь тоже в совокупности (да и по отдельности) можно делать определенные выводы о личности пользователя при отключении/смене VPN. Только вот в большинстве случаев (или во всех?), когда нужен доступ к каким-то дополнительным устройствам, то запрашивается (и скорее всего будет запрашиваться для нереализованных спецификаций) разрешение пользователя.
Так чем же Battery Status API отличается от обычного «сенсора уровня батареи»?
Upd: хотя я тут подумал, что их тоже можно описать короче (через смещение)…
Возьмем n = 2²⁰, тогда в худшем (и лучшем тоже) случае надо будет пройти (1+2+4+8...+2²⁰)*2 вагонов, чтобы убедиться, что мы выключили свет везде. Умножение на 2 — это проход туда и обратно. После чего надо сделать один полный проход с подсчетом. Количество слагаемых в скобках — lg(n). Каждое из слагаемых можно грубо принять за n (асимпотика же ¯\_(ツ)_/¯). Т.е. мы 2*lg(n) раз прошли n вагонов, чтобы убедиться в том, что обошли весь поезд + 1 раз прошли n вагонов для подсчета. Получается O(n*(1+2*lg(n))) или O(n*lg(n)).
Справедливости ради нижний асимптотический предел сложности такой же как и верхний с точностью до константы Ω(n*lg(n)) ⇒ Θ(n*lg(n)). А это может значить, что на больших и очень разреженных составах (почти везде свет выключен) алгоритм «в лоб» может работать лучше.
Включаем в исходном вагоне свет. Идем в одну из сторон до тех пор, пока не встретим вагон со светом, попутно считая количество пройденных вагонов. Примем число пройденных вагонов за c. Выключаем в этом вагоне свет. Возвращаемся в обратную сторону на c шагов, чтобы оказаться в изначальном вагоне. Если свет в вагоне выключен, то число вагонов в поезде c, алгоритм завершен. Если свет в вагоне включен, то опять идем в произвольную сторону до первого вагона с включенным светом, считая вагоны.
Частный случай — 1 вагон. Включаем свет. Выходим из вагона в соседний и оказываемся в изначальном вагоне. c = 1. Выключаем свет. Возвращаемся на 1 вагон назад. Оказывамся в вагоне с выключенным светом => кол-во вагонов равно 1.
Асимптотическая сложность алгоритма:
O(n²) — везде свет включен;
Ω(n) — свет включен только в изначальном вагоне.
Для улучшения вычислительной сложности (не асимптотической) можно использовать не один вагон с включенным светом, а паттерн, например, из трех вагонов (включен, выключен. включен) и при нахождении такого же паттерна возвращаться назад на c вагонов и проверять.
Как происходит процесс вычисления центральной точки в дереве квадрантов? Медианы по обеим осям? Половина разности максимального и минимального значений x и y? Или какой-то более сложный алгоритм? Как вычисляется центральная точка, если построить индекс по пустой таблице? Может ли получиться, что после заполнения таблицы, в которой уже присутствует sp-gist индекс, все точки будут в одном квадранте верхнего уровня, а 3 других будут пустыми?
А все потому, что государственные организации платят программистам значительно меньше, чем частные компании. Найти хороших специалистов на такую зарплату очень сложно. Соответственно и сидят там часто недавние студенты и люди, для которых работа «лишь бы была». Ни у тех ни у других обычно нет необходимых навыков.
Это не говоря уже о том, что для гос. организаций зачастую выполнение требований закона гораздо важнее конечного результата. Какой еще WCAG? Зачем проверять доступность с клавиатуры и со скринридером? В приказе №483 Минсвязи сказано, что на сайте должны быть кнопки для изменения размера и цвета шрифта, вот и делайте это. А удобно конечному пользователю или нет, мало кого волнует.
В случае решения ТС идет 3 раза заполенние по 3 литра и 1 раз выливание 5 литров.
В случае решения выше получаем 2 заполнения по 5 литров (на литр больше) и одно выливание 3 литров
Высота букв как и высота области размещения букв зависит от параметров шрифта.
Тут можно подробнее почитать
Нетекстовые данные (и текстовые на английском) нормально генерируются.
Странное решение. Мне кажется было бы разумнее запрашивать у пользователя разрешение на использование Battery Status API, а не удалять его полностью. А то следуя этой логике они должны вообще никогда не реализовывать ни одну из спецификаций сенсоров:
Gyroscope Sensor
Proximity Sensor
Ambient Light Sensor
Magnetometer Sensor
Generic Sensor API
и кучу других спецификаций, дающих хоть какую-то информацию об устройстве, geolocation, mediastream, bluetooth (это я уже утрирую).
По ним ведь тоже в совокупности (да и по отдельности) можно делать определенные выводы о личности пользователя при отключении/смене VPN. Только вот в большинстве случаев (или во всех?), когда нужен доступ к каким-то дополнительным устройствам, то запрашивается (и скорее всего будет запрашиваться для нереализованных спецификаций) разрешение пользователя.
Так чем же Battery Status API отличается от обычного «сенсора уровня батареи»?