Об этом можно и написать на сайте — так и так, есть плагин к VS и standalone, etc… А то сейчас страница скачивания вводит в заблуждение. Когда я последний раз пробовал PVS, этого не было.
Лично я за 4 года использования clang понял, что статический анализ кода на сях/плюсах мне не нужен. Я не говорю, что он не нужен никому, я говорю, что он не нужен лично мне. Я пишу на C/C++ уже более 10 лет, причем пишу на нем в основном только low-level структуры данных/алгоритмы, драйвера какие-нибудь и т.д. Учитывая специфику решаемых задач, почти всё время уходит на мыслительный процесс, а не на написание кода. Ошибки в коде конечно же бывают, но для того, чтобы их найти, нужен глубокий человеческий анализ и понимание алгоритма. Статические анализаторы находят только совсем очевидные вещи, учитывая, с какой скоростью я пишу код и как обдумываю каждую строчку, у меня таких ошибок просто не возникает. Статический анализ полезен только в проектах, где пишут мало осмысленный код с огромной скоростью (в основном это десктопные приложения на плюсах, вроде той же миранды).
Приглашаю незамедлительно скачать PVS-Studio и попробовать его на своём проекте.
У вас на сайте вообще нигде (кроме страницы скачивания) не написано, что это всего лишь плагин к Visual Studio, хотя используется громкое название «статический анализатор PVS-Studio». Нужена как минимум standalone-версия, чтобы можно было по-быстрому проверить проект и не ставить ради одной проверки Visual Studio. А ещё неплохо бы иметь не только кросс-IDE версию, но и кросс-платформенную, чтобы под Linux и OSX можно было проверять.
Как вы думаете если у нескольких миллионов пользователей за несколько лет в этом месте ничего не падало, то каковы шансы что этот указатель окажется NULL?
Хорошая логика. Важна не вероятность, а то, что это может случиться. Если подушка безопасности не помогает в большинстве аварий, то зачем нужна подушка безопасности… хм?
А откуда Вы знаете, что у пользователей не падает в этом месте? У вас посылаются coredump-ы после каждого падения? Вроде для программ вроде Miranda это не типично.
Ну не знаю, глядя на современное программирование, и на то, что делают 99% программистов, сомневаюсь, что там нужен какой-то особый склад ума. Все так сильно хотят приобщить себя к математикам и унизить гуманитариев… На самом деле, у программиста с математиком столько же общего, сколько у сантехника с математиком (в плане мышления). Вообще, что за глупость — разделять мышление на гуманитарное и техническое. Это миф, нет здесь четкой границы. Из программистов ближе всего к математикам люди, которые занимаются криптографией, комп. графикой и олимпиадники/алгоритмисты, но это как раз тот 1%. И вообще математики — это не элита, это просто математики.
Хорошая статья, иллюстрации сделаны шикарно — видно, старались. Я помню мне на втором курсе универа, на экзамене, в качестве одного из вопросов как раз попалась персистентная очередь :)
Всё, осознал. От противного доказывается. Предположим, что после удаления получилась неслучайная последовательность. Тогда исходная неслучайна (она получается добавлением одного случайного элемента).
В вашем примере понятно: любая последовательность равновероятна, а всего возможных последовательностей 2^12. Сумма вероятностей 1, значит вероятность всех последовательностей 1/2^12. «Из той же серии» — не понятно. Почему при удалении первого элемента случайной последовательности мы получаем случайную последовательность? Докажите.
Если немного приблизиться к терверу, то проблема в том, что вы рассматриваете каждый шаг как независимое событие, а на самом деле они таковыми не являются, ибо выборка без возврата (если с возвратом — тогда можно было бы). Т.е., ваш инвариант
1. Колода карт со случайным порядком расположения черных и красных карт
нарушается сразу же после извлечения первой карты из колоды и далее ничего уже утверждать нельзя. А вы пытаетесь повторить то же самое для неслучайной колоды.
Не обязательно было это расписывать, проблема не в этом :)
Вы же понимаете разницу между этими двумя определениями?
Оптимальный алгоритм — алгоритм, который с наибольшей вероятностью угадывает цвет карты на каждом шаге (шаги рассматриваются независимо).
Оптимальный алгоритм — алгоритм, который угадывает максимальное количество карт на всех шагах в сумме.
Так вот, чтобы завершить доказательство, вы должны доказать, что эти 2 утверждения эквивалентны. Вы доказали для первого, но ведь нам-то нужен второй, так ведь?
Представьте себе такую задачу: в матрице N*N выбрать N элементов так, чтобы никакие 2 не лежали на одной строке или столбце и их сумма была максимальна. Можно в каждой строке просто выбирать максимальный элемент, это будет простейший жадный алгоритм. Но можно привести множество примеров, когда этот алгоритм находит ответ неверно и можно другим набором выбрать сумму больше. Так что жадная стратегия требует обоснования.
Более подробно про задачу — http://habrahabr.ru/post/63982/, http://ru.wikipedia.org/wiki/Венгерский_алгоритм
Не понятно, почему взвешенная выборка проигрывает такому методу. При взвешенной выборке мы делаем выбор в пользу красного с вероятностью z/x, чёрного — y/x. И ещё непонятка: почему, если y=z, мы всегда выбираем один и тот же цвет? Нужно показать, что это не влияет на результат (или влияет?).
Это не доказательство. Вы утверждаете, что не существует алгоритма, который угадает больше. Мне не очевидно, почему в результате достигается оптимальная стратегия. Также не очевидно, почему жадная стратегия работает, вы это никак не обосновали.
Очень интересно увидеть доказательство этого факта. Этот алгоритм имеет название? После тестов выяснилось, что он угадывает чуть лучше, чем мой алгоритм. Правда я хотел смоделировать реального человека, а не максимизировать количество угаданных карт.
Разгадка — я почти полностью скопировал ваш код на PHP, а он на каждом прогоне одно и то же число вычисляет. В итоге в ответе это самое число и есть. Непонятно, зачем вы $times раз одно и то же считаете.
Я немного переборщил с алгоритмом. У нас ведь всего два вида карт, поэтому там достаточно просто хранить количество оставшихся красных и чёрных. И тогда не нужны никакие перестановки на префиксе и вообще второй массив не нужен.
Ради интереса написал свой и оба ваших алгоритма на C++. Прогнал 10000 раз тесты. Мой вывел 28.112, а ваш (второй) ровно 31 (первый, понятно, примерно 26 всегда выводит). Запускал несколько раз, ваш всегда больше угадывает (примерно 29-34, у меня стабильно 28-29). Ещё у меня вызвало подозрение то, что хотя я и считаю всё в double-ах, ваш алгоритм всегда почему-то даёт целое число. Это очень странный эффект.
UPD: Попробовал после каждого прогона мешать колоду, теперь выводит дробное, стабильно 30.0-30.5.
Вот код: мой вариант, ваш.
Я описал алгоритм, который на каждом шаге учитывает, какие карты остались в колоде. Т.е., если остались 2 чёрных и 5 красных, то вероятности выбрать чёрную и красную соответственно: 2/7 и 5/7. А не 50%, как происходит у вас. Я не уверен, но мне кажется, что это более приближённый алгоритм к реальному человеку.
Ваш алгоритм верен, но он не соответствует реальному поведению человека в этой ситуации. Я же хотел найти реальную цифру, т.е. если бы играл человек, который осознанно делает выбор. Допустим, если кто-то вытащил 26 подряд чёрных, он знает, что осталось 26 красных, и далее выбирать чёрные уже смысла нет. А в вашем случае он всё равно продолжает выбирать с вероятностью 50% чёрные.
Ваш алгоритм верен, но я не понимаю, что он призван продемонстрировать. Ведь довольно очивидно, что получится примерно 26, т.е. 50%, если выбирать всегда с равной вероятностью.
я не понимаю, к чему вы привели алгоритм случайного перемешивания «карт»
Этот алгоритм в процессе работы генерирует случайные перестановки на префиксе, что нам и надо. В конце получается случайная перестановка на префиксе A[0..N] (N — размер массива), т.е. на всём массиве.
Возможно я не понял ваш алгоритм. Вот смотрите: допустим вы уже 5-й раз подряд выбрали красную карту. В колоде осталось 5 красных и 1 белая. Какова в вашем случае вероятность выбрать белую, и влияет ли как-то на это тот факт, что до этого 5 раз была красная?
У вас на сайте вообще нигде (кроме страницы скачивания) не написано, что это всего лишь плагин к Visual Studio, хотя используется громкое название «статический анализатор PVS-Studio». Нужена как минимум standalone-версия, чтобы можно было по-быстрому проверить проект и не ставить ради одной проверки Visual Studio. А ещё неплохо бы иметь не только кросс-IDE версию, но и кросс-платформенную, чтобы под Linux и OSX можно было проверять.
А откуда Вы знаете, что у пользователей не падает в этом месте? У вас посылаются coredump-ы после каждого падения? Вроде для программ вроде Miranda это не типично.
нарушается сразу же после извлечения первой карты из колоды и далее ничего уже утверждать нельзя. А вы пытаетесь повторить то же самое для неслучайной колоды.
Вы же понимаете разницу между этими двумя определениями?
Так вот, чтобы завершить доказательство, вы должны доказать, что эти 2 утверждения эквивалентны. Вы доказали для первого, но ведь нам-то нужен второй, так ведь?
Представьте себе такую задачу: в матрице N*N выбрать N элементов так, чтобы никакие 2 не лежали на одной строке или столбце и их сумма была максимальна. Можно в каждой строке просто выбирать максимальный элемент, это будет простейший жадный алгоритм. Но можно привести множество примеров, когда этот алгоритм находит ответ неверно и можно другим набором выбрать сумму больше. Так что жадная стратегия требует обоснования.
Более подробно про задачу — http://habrahabr.ru/post/63982/, http://ru.wikipedia.org/wiki/Венгерский_алгоритм
Ради интереса написал свой и оба ваших алгоритма на C++. Прогнал 10000 раз тесты. Мой вывел 28.112, а ваш (второй) ровно 31 (первый, понятно, примерно 26 всегда выводит). Запускал несколько раз, ваш всегда больше угадывает (примерно 29-34, у меня стабильно 28-29). Ещё у меня вызвало подозрение то, что хотя я и считаю всё в double-ах, ваш алгоритм всегда почему-то даёт целое число. Это очень странный эффект.
UPD: Попробовал после каждого прогона мешать колоду, теперь выводит дробное, стабильно 30.0-30.5.
Вот код: мой вариант, ваш.
Ваш алгоритм верен, но я не понимаю, что он призван продемонстрировать. Ведь довольно очивидно, что получится примерно 26, т.е. 50%, если выбирать всегда с равной вероятностью.
Этот алгоритм в процессе работы генерирует случайные перестановки на префиксе, что нам и надо. В конце получается случайная перестановка на префиксе A[0..N] (N — размер массива), т.е. на всём массиве.