Pull to refresh
  • by relevance
  • by date
  • by rating

О всемогущем рандоме

Interfaces *
image

Умный shuffle для плееров



В топике хотелось бы поделиться мыслями насчет того, каким должно быть «случайное воспроизведение» в плеерах (особенно это касается портативных плееров типа iPod)
Сам я являюсь владельцем iPod touch и постоянно пользуюсь им в машине, подключая его через AUX к магнитоле.
Фирма Apple изобрела какой-то «умный плейлист» — так называемый genius, но он как-то использует интернет и мнения других пользователей itunes.

Хотелось бы слышать и слушать именно то, что хочется слышать. Под катом собственно суть идеи.
Читать дальше →
Total votes 77: ↑64 and ↓13 +51
Views 6.7K
Comments 80

У Microsoft не получается предлагать браузеры в случайном порядке

Development for Windows *
На хабре уже писали о модуле выбора браузера для европейских пользователей: «Модуль выбора браузеров появляется в качестве обновлений Windows. Сразу показывается пять самых популярных (Apple Safari, Google Chrome, Microsoft Internet Explorer, Mozilla Firefox и Opera). Причем в случайном порядке.»

Как выяснили ребята со словацкого сайта DSL.sk, у модуля большие проблемы именно со случайным порядком вывода браузеров. Страница, с помощью которой предпологается выполнять требования Евросоюза, не выводит список браузеров в случайном порядке, как предполагалось. Вместо общепринятых алгоритмов используется наихудший вариант реализации перемешивания списка браузеров через сортировку массива с функцией сравнения, возвращающей случайный результат. Из-за этого вместо равновероятного размещения браузеров в списке получается смещённое. Таким образом, для IE вероятность оказаться на последнем месте первой страницы почему-то оказалась наибольшей (~50%)! Однако при этом он всегда показывается изначально на первом месте, и только после окончания «перемешивания» меняет своё местоположение. Что интересно, указанный выше алгоритм выдаётся первым при поиске по «javascript randomize array» как в google, так и в bing :)

image

Технические подробности расследования (на английском).

P.S.: Как подсказал naum код на странице поправили.
Total votes 107: ↑74 and ↓33 +41
Views 802
Comments 65

Интересное поведение RANDOM в zsh

Lumber room
Прочитав про Парадокс Монти-Холла, решил написать скриптик, который смоделирует несколько тысяч раз этот эксперимент (до того как увидел эти реализации).
Во время тестирования кусочков кода наткнулся на интересное поведение RANDOM в оболочке моего linux-а.
Как известно, RANDOM — такая переменная, которая принимает псевдослучайное значение от 0 до 32k.
Сколько раз из 10000 — RANDOM будет нечетным?
ну примерно 5000 раз… Проверим?
% for i in {1..10000} ; do test $(( RANDOM % 2 )) -eq 1 && echo 1 ; done | wc -l
4985

А если еще раз выполню эту команду, снова получу 4985? Вроде не должно.
Однако всё зависит от оболочки, в которой мы работаем.
Читать дальше →
Total votes 7: ↑7 and ↓0 +7
Views 424
Comments 6

Идеальный эксперт или гороскопы на службе ERP

Abnormal programming *
А вы пробовали когда-то делать системный анализ гороскопов? Я пробовал и нашел, что все эти советы дает Капитан Очевидность и они носят универсально-рекомендательный характер.
Например: Хабролюдям сегодня стоит приложить усилия для успешного завершения начатого дела, это может принести успех, но остерегайтесь возможных ДТП, особенно после обеда.

Разберем этот пример. В пятницу очень хорошо закончить запланированный этап работы, чтоб отдыхать со спокойной совестью. А вести себя внимательно на дорогах — это актуально всегда.

Так вот, однажды один владелец крупной компании захотел себе ERP. Но не простую, как у всех, а которая реально помогает управлять предприятием. Вводишь в нее цифры — а она говорит тебе, что надо сделать.

Казалось бы, идея не реальная, но… Я вспомнил за программу генерации гороскопов. Только вместо дней недели меня интересовала дисперсия по введенным числам, а точнее говоря — прибыль (или убыток) компании на этап ввода данных.
Читать дальше →
Total votes 57: ↑55 and ↓2 +53
Views 1.5K
Comments 39

Псевдослучайно vs. По-настоящему Случайно

Algorithms *
Translation
Ниже перевод статьи Бо Аллена отсюда.

Простой наглядный пример

Однажды я наткнулся на Random.org, классный сервис генератора настоящих случайных чисел. Разница между генератором настоящих случайных чисел (ГНСЧ) и генератором псевдослучайных чисел (ГПСЧ) в том, что ГНСЧ использует непредсказуемые физические средства для генерации чисел (например шумы атмосферы), а ГПСЧ использует математические алгоритмы (полностью производимые компьютером). Об этом можно более подробно узнать на Random.org (англ.) и в Википедии (англ.).
Читать дальше →
Total votes 74: ↑62 and ↓12 +50
Views 26K
Comments 96

Играемся с изображениями в Python

Python *Image processing *
Tutorial
В этой статье я хотел бы разобрать различные способы преобразования изображений с помощью Python. Для примеров я решил взять несколько наиболее известных. В статье не будет ничего сложного, она ориентированна в основном на новичков.
Картинка для испытаний:


Читать дальше →
Total votes 86: ↑65 and ↓21 +44
Views 218K
Comments 49

Генератор энтропии Seeder 1.1 существенно уменьшает лаги на Android-устройствах

Interfaces *
В старых версиях Android некоторые системные компоненты и JVM активно считывали большие объёмы случайных чисел из псевдоустройства /dev/random. Это устройство предоставляет интерфейс к системному генератору случайных чисел (ГСЧ), который выводит шумы из драйверов устройств и других источников в «хаотичный» пул. На старых версиях Android иногда возникали проблемы с наполнением пула случайных чисел. В случае опустошения пула возникали лаги UI, пока пул не наполнялся. В новых версиях Android проблему с лагами UI решили, но не до конца: всё-таки иногда возникают характерные задержки.

Многие пользователи считали, что лаги интерфейса объясняются недостаточной производительностью CPU, на самом деле это не так. Проблема именно в истощении пула случайных чисел.

Один из разработчиков с форума XDA-Developers перекомпилировал rngd, так что пул случайных чисел каждую 1 секунду пополняется из пула псевдослучайных чисел /dev/urandom. Результат — потрясающее ускорение интерфейса Android с почти полным исчезновением лагов! Chrome, карты и другие тяжеловесные приложения теперь мгновенно переключаются между задачами.
Читать дальше →
Total votes 116: ↑95 and ↓21 +74
Views 137K
Comments 216

Генерация случайных чисел в .NET

.NET *C# *
Sandbox
Перевод статьи Random numbers широко известного в узких кругах Джона Скита. Остановился на этой статье, так как в своё время сам столкнулся с описываемой в ней проблемой.


Просматривая темы по .NET и C# на сайте StackOverflow, можно увидеть бесчисленное множество вопросов с упоминанием слова «random», в которых, по сути, поднимается один и тот же извечный и «неубиваемый» вопрос: почему генератор случайных чисел System.Random «не работает» и как это «исправить». Данная статья посвящена рассмотрению данной проблемы и способов её решения.
Читать дальше →
Total votes 43: ↑37 and ↓6 +31
Views 113K
Comments 23

Оптимизируем, оптимизируем и еще раз оптимизируем

Java *
По долгу службы мне периодически приходится пользоваться профайлером, так как требования к производительности серверов задокументированы и не могут опускаться ниже определенного уровня. Помимо некоторых очевидных архитектурных изменений и решений частенько находятся повторяющиеся места от модуля к модулю, от одного проекта к другому, которые создают дополнительную нагрузку на виртуальную машину, которыми и хочу поделиться.
Так уж случилось, что на глаза чаще всего попадался код работы с Date потому с него и начнем:

Date

Не один десяток раз я имел возможность наблюдать, как во время обработки одного запроса от пользователя в нескольких разных местах создается новый объект даты. Чаще всего цель одна и та же — получить текущее время. В простейшем случае это выглядит так:

    public boolean isValid(Date start, Date end) {
        Date now = new Date();
        return start.before(now) && end.after(now); 
    }

Казалось бы — вполне очевидное и правильное решение. В принципе, да, за исключением двух моментов:
  • Использовать Date сегодня в java — уже, пожалуй, моветон, учитывая тот факт, что почти все методы в нем уже Deprecated.
  • Нету смысла создавать новый объект даты, если вполне можно обойтись примитивом long:

    public boolean isValid(Date start, Date end) {
        long now = System.currentTimeMillis();
        return start.getTime() < now && now < end.getTIme(); 
    }


SimpleDateFormat

Очень часто в веб проектах возникает задача перевести строку в дату или наоборот дату в строку. Задача довольно типичная и чаще всего выглядит так:

    return new SimpleDateFormat("EEE, d MMM yyyy HH:mm:ss Z").parse(dateString);

Это правильное и быстрое решение, но если серверу приходится парсить строку на каждый пользовательский реквест в каждом из сотен потоков — это может ощутимо бить по производительности сервера в виду довольно тяжеловесного конструктора SimpleDateFormat, да и помимо самого форматера создается множество других объектов в том числе и не легкий Calendar (размер которого > 400 байт).

Ситуацию можно было бы легко решить, сделав SimpleDateFormat статическим полем, но он не является потокобезопасным. И в конкурентной среде легко можно словить NumberFormatException.

Вторая мысль — использовать синхронизацию. Но это таки довольно сомнительная вещь. В случае большой конкуренции между потоками, мы можем не просто не улучшить производительность но и ухудшить.

Но решения есть и их как минимум 2:
  • Старый, добрый ThreadLocal — cоздаем SimpleDateFormat для каждого потока 1 раз и переиспользуем для каждого последующего запроса. Данный подход поможет ускорить парсинг даты в 2-4 раза за счет избежания создания объектов SimpleDateFormat на каждый запрос.
  • Joda и ее потокобезопасный аналог SimpleDateFormat — DateTimeFormat. Хоть йода в целом и медленнее дефолтного Java Date API в парсинге дат они идут наравне. Несколько тестов можно глянуть тут.

Читать дальше →
Total votes 50: ↑38 and ↓12 +26
Views 23K
Comments 34

«Человеческая» энтропия для генератора случайных чисел

Cryptography *.NET *Algorithms *
Sandbox
Лишь вследствие нашей слабости, вследствие нашего невежества случайность для нас существует

А. Пуанкаре

Чем больше люди постигали тайны Вселенной, тем ближе они приближались к той точке незнания, в которой их предки все приписывали богам. Теперь это называется – случайность. И хотя Эйнштейн не верил в случайность – он говорил «Бог не играет в кости», – он в числе первых из списка: Эйнштейн, Шредингер, Лаплас…

В наш век цифровых технологий и огромной роли информации в развитии человечества защита информации – актуальнейшая задача. Технологическое решение этой задачи предполагает привлечение «случайности», а именно – генерацию случайных чисел. При этом от качества используемых генераторов напрямую зависит качество получаемых результатов. Это обстоятельство подчёркивает известный афоризм Роберта Р. Кавью из ORNL: «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая».
Читать дальше →
Total votes 19: ↑10 and ↓9 +1
Views 16K
Comments 28

Быстрый выбор случайных значений из больших таблиц MySQL по условию

SQL *Big Data *
Sandbox
Задача выбора случайных строчек из таблицы довольно часто возникает перед разработчиками.
В случае, если используется СУБД MySQL, обычно она решается примерно следующим способом:

SELECT *
FROM users
WHERE role_id=5
ORDER BY rand()
LIMIT 10


Такой код работает крайне медленно для больших таблиц.
Если в запросе не нужно использовать WHERE или таблица небольшая, есть эффективные решения, например habrahabr.ru/post/54176 или habrahabr.ru/post/55864.
Но готовых решений для большой таблицы и необходимости фильтровать по условию, получая при каждом запросе новые значения, я не нашел, поэтому описание моего способа под катом.
Читать дальше →
Total votes 20: ↑12 and ↓8 +4
Views 33K
Comments 18

Уязвимость в MACROSCOP (устранена с версии 1.9.72)

Information Security *Cryptography *.NET *
Sandbox
Я давно увлекаюсь информационной безопасностью, но одно дело – понимание поверхностной логики работы программного обеспечения, и совершенно другое – понимание логики его внутренней реализации. Внешне любая программа может выглядеть замечательно и гармонично, создавая иллюзию полной безопасности и защищённости, но стоит углубиться, копнуть глубже, и на поверхности окажутся нелицеприятные факты, которые могут привести к взлому системы и, в конечном счёте, к утечке или потере данных, а также временным и финансовым потерям. Причиной наличия уязвимости в приложении может быть как банальная невнимательность, катастрофическая нехватка времени, алгоритмическая или архитектурная сложность, незнание особенностей работы или реализации стороннего API, так и корыстный умысел. Зачастую сложно судить о том, что конкретно могло послужить причиной возникновения той либо иной уязвимости, но более важным моментом является скорость реакции разработчиков по её устранению.

Сегодня же пойдёт речь об уязвимости, обнаруженной мной в процессе знакомства с программным комплексом для IP-камер MACROSCOP от резидента технопарка «Сколково» компании ООО «Сателлит» (г. Пермь). MACROSCOP является именно программным комплексом, так как в состав решения входит целый ряд приложений: серверная и «всё в одном» часть для операционных систем семейства Microsoft Windows (от развития Linux решения разработчики недавно отказались), клиентская часть для Windows, Android, iOS и Windows Phone, конфигуратор, программа подключения Web-камер, проигрыватель файлов собственного формата, программа локального просмотра и резервного копирования архива, программа мониторинга состояния системы, различные интеллектуальные модули, а также приложения для интеграции с некоторыми сторонними системами и широкие возможности по интеграции с любым программным обеспечением посредством SDK. В MACROSCOP много плюсов и, тем не менее, он не лишён недостатков, чему можно посвятить отдельную статью: ведь не всегда разработчики афишируют отрицательные стороны своего продукта.

Пора переходить к сути дела
Total votes 24: ↑22 and ↓2 +20
Views 11K
Comments 4

os.urandom, CPython, Linux и грабли

Python *


Хочу поведать поучительную историю ошибки в реализации функции urandom из модуля os в CPython на UNIX-подобных ОС (Linux, Mac OS X, etc.).

Цитата из документации по тройке:
Return a string of n random bytes suitable for cryptographic use.

This function returns random bytes from an OS-specific randomness source. The returned data should be unpredictable enough for cryptographic applications, though its exact quality depends on the OS implementation. On a Unix-like system this will query /dev/urandom, and on Windows it will use CryptGenRandom().
Документация по двойке добавляет:
New in version 2.4.
Другими словами, к примеру, под Linux, urandom читает и возвращает байты из системного устройства /dev/urandom. Напомню, что в этой ОС существуют два типичных устройства-источника энтропии: /dev/random и /dev/urandom. Как известно, первое устройство «медленное» и блокирующее, а второе «быстрое», и вопреки распространенному мнению, оба они криптостойкие источники (псевдо-)случайных чисел. Сразу скажу, КДПВ к статье отношения не имеет и речь пойдёт совсем не о криптографии, безопасности и об OpenSSL с Heartbleed-ом.

Казалось бы, как можно ошибиться в реализации столь простой рутины? Как это часто бывает, дооптимизировались…
Читать дальше →
Total votes 64: ↑59 and ↓5 +54
Views 20K
Comments 26

Проблемы при использовании Math.random()

Mail.ru Group corporate blog Website development *Cryptography *JavaScript *Algorithms *
Translation
image

В английском есть такая аббревиатура — TIFU. Привести здесь её точное значение мы не можем, но вы без труда найдёте его в Сети. А после «литературной обработки» TIFU можно перевести как «сегодня я всё испортил». В контексте этого поста данная фраза относится к использованию функции Math.random() в JavaScript-движке V8. Хотя случилось это не сегодня, а пару лет назад. Да и дров я наломал не по своей вине, корень зла таится в самой этой функции.

«Многие генераторы случайных чисел, используемые сегодня, работают не слишком хорошо. Разработчики обычно стараются не вникать, как устроены такие подпрограммы. И часто бывает так, что какой-то старый, неудовлетворительно работающий метод раз за разом слепо перенимается многими программистами, которые зачастую просто не знают о присущих ему недостатках»

Дональд Кнут, «Искусство программирования», том 2.

Надеюсь, что к концу этого поста вы согласитесь с двумя утверждениями:

  • Мы были идиотами, поскольку использовали генератор псевдослучайных чисел в V8, не понимая его ограничений. И если очень лень, то безопаснее использовать криптографически стойкие генераторы псевдослучайных чисел.
  • В V8 необходима новая реализация Math.random(). Работу текущего алгоритма, кочующего от одного программиста к другому, нельзя считать удовлетворительной из-за слабой, неочевидной деградации, часто встречающейся в реальных проектах.

Хочу подчеркнуть, что сам движок V8 — замечательный продукт и его создатели очень талантливы. Я ни в коей мере не обвиняю их. Просто эта ситуация иллюстрирует, насколько сильно влияют на процесс разработки даже небольшие нюансы.
Читать дальше →
Total votes 81: ↑77 and ↓4 +73
Views 41K
Comments 38

Создаём аппаратный генератор случайных чисел

Development for Linux *
Я хочу представить вашему вниманию программно-аппаратный вариант получения случайных чисел. Забегая вперёд, скажу, что данный вариант не единственный, и этот пост открывает мою небольшую серию статей о получении, генерации и изучении случайных чисел, или точнее сказать просто случайностей.



Читать дальше →
Total votes 162: ↑159 and ↓3 +156
Views 52K
Comments 104

Casual-заготовки под Swift

Development for iOS *Development of mobile applications *Game development *
image

Привет, братья во swift-e. Пришлось и мне освоить сей птичий язык, и нет лучшего способа для обучения, чем сделать программный продукт, работающий на потрепанном iPhone. Меня давно кусала изнутри сложная математическая головоломка, а тут раз! И вдруг свифт. Представленный код местами выглядит смешно, но понятно. Сам алгоритм игры я обсуждать не буду, он слишком сложен для местных модераторов, не умеющих в уме разделить 111 на 3. А вот примеры полезных функций для разработчиков casual game — пожалуйста, обсудим.
Читать дальше →
Total votes 27: ↑19 and ↓8 +11
Views 12K
Comments 14

Программирование генератора случайных чисел на Ethereum

Cryptography *Entertaining tasks Algorithms *Mathematics *Solidity *

image


При разработке смарт-контрактов на Ethereum обычно считается что полагаться на хеш блока как источник рандомности ненадежно, так как майнер может влиять на результат, подбирая хеш блока (см. Private Information and Randomness, How do you get a random number in a contract?)


Насколько в действительности велика возможность для майнера увеличить свои шансы на выигрыш в игре в которой нужно угадать хеш блока c определенным номером (или некое число производимое от хеша блока)?

Читать дальше →
Total votes 16: ↑14 and ↓2 +12
Views 12K
Comments 15

Неслучайная случайность, или Атака на ГПСЧ в .NET

Контур corporate blog Information Security *Cryptography *.NET *C# *
Random numbers should not be generated with a method chosen at random.
— Donald Knuth

Копаясь как-то в исходниках одного сервиса в поисках уязвимостей, я наткнулся на генерацию одноразового кода для аутентификации через SMS. Обработчик запросов на отправку кода упрощённо выглядел так:


class AuthenticateByPhoneHandler
{
    /* ... */

    static string GenerateCode() => rnd.Next(100000, 1000000).ToString();

    readonly static Random rnd = new Random();
}

Проблема видна невооруженным глазом: для генерации 6-тизначного кода используется класс Random — простой некриптографический генератор псевдослучайных чисел (ГПСЧ). Займёмся им вплотную: научимся предсказывать последовательность случайных чисел и прикинем возможный сценарий атаки на сервис.


Потокобезопасность


Кстати, заметим, что в приведённом фрагменте кода доступ к статическому экземпляру rnd класса Random из нескольких потоков не синхронизирован. Это может привести к неприятному казусу, который можно часто встретить в вопросах и ответах на StackOverflow:


Читать дальше →
Total votes 72: ↑71 and ↓1 +70
Views 16K
Comments 31

Функция random() у гуглобота работает абсолютно детерминированно

Search engines *JavaScript *Search engine optimization
Translation
Я проводил некоторые эксперименты, как Googlebot разбирает и рендерит JavaScript, и наткнулся на несколько интересных вещей. Первое — то, что функция Math.random() в Googlebot выдаёт полностью детерминированные серии чисел. Я написал маленький скрипт, который использует этот баг для точной идентификации гуглобота:


Источник

При первом вызове Math.random() из гуглобота результат всегда будет 0,14881141134537756, второй вызов всегда вернёт 0,19426893815398216. Скрипт по ссылке выше просто использует эту информацию для идентификации бота Google, хотя немножко обфусцирует свои действия, чтобы они не выглядели слишком произвольными.
Читать дальше →
Total votes 56: ↑55 and ↓1 +54
Views 22K
Comments 20
1