Как подсчитать вероятность?

Доброго времени суток.
Сделал программу, изменяющую фон рабочего стола ВыньДос на случайный файл из указанной директории. Сколько в ней файлов неизвестно. Может 1000000, а может 1. Решил сэкономить на памяти и выбрать случайный файл за один проход - первый файл запоминается с вероятностью 1 к 1, второй - 1 к 2, третий 1 к 3 и т.д. пока файлы не кончатся. Последний запомненный и есть выбранный. Сделал, а теперь жаба давит: у всех ли файлов одинаковая вероятность выбора?
Подскажите, пожалуйста, как считать вероятность? Всю башку сломал... Не ругайтесь, знаю, что в школе надо было учиться, но поздно пить боржоми...
Заранее спасибо.

Добавлено через 11 минут
Проблема решилась, удалите тему плз.

n-й файл - очевидно
P = 1/n
(n-1)-й - это когда он выбран, а n-й - нет.
P = (1/(n-1)) * (1 - 1/n) = 1/n
(n-2)-й - это когда он выбран, а (n-1)-й и n-й - нет.
P = (1/(n-2)) * (1 - 1/(n-1)) * (1 - 1/n) = 1/n
и т. д.
Вроде одинаковая получается.

0

Удалять-то зачем, познавательно.

1

Сообщение от Fedor666 Вроде одинаковая получается.

Вот именно ВРОДЕ. Без знания кол-ва файлов вы не рассчитаете правильно вероятность.
Т.е. надо так:
1. Считаем кол-во всех файлов в директории (пусть будет n).
2. Номер выбранного файла - случайное число от 1 до n.

Сообщение от Fedor666 Решил сэкономить на памяти

Ее много и не потребуется.

0

Питекантроп, ничего не вроде, все уже круто.

1

Хохол, если не лень, можете побробовать построить функцию распределения для вашего способа нахождения случайного файла, тогда будет ясно.

0

Питекантроп!

"1. Считаем кол-во всех файлов в директории (пусть будет n)."

В том-то и дело, что файлов может быть 1000000. За первый проход выясняешь количество файлов подходящих форматов, а на второй находишь файл с нужным номером - двойная работа! Или за первый проход запоминать их имена и поддиректории, но тогда требуется неизвестно сколько памяти.
Весь прикол в экономии паямти и времени, поскольку прога стартует из автозагрузки и отнимать ресурсы не имеет права.
Вот кстати http://fedfed.narod.ru/RWallpapers.7z (прошу не бить за ламерство)

0

Сообщение от Fedor666 За первый проход выясняешь количество файлов подходящих форматов, а на второй находишь файл с нужным номером - двойная работа! Или за первый проход запоминать их имена и поддиректории, но тогда требуется неизвестно сколько памяти

Это понятно.
Можно предложить такой вариант: при проходе запоминать количество файлов (в служебный файл писать), а вероятность определять исходя из предыдущего прохода.

0

Опять на месте танцы пляшем...
ДВА ПРОХОДА!!!
Прикол в том, что можно вычислить вероятность чего-то, не зная сколько этого "чего-то" заранее. Зачем усложнять нашу (и без того не легкую) жизнь, когда вот алгоритм. Если в нем ошибка, то обоснуйте.

0

Сообщение от Fedor666 Прикол в том, что можно вычислить вероятность чего-то, не зная сколько этого "чего-то" заранее.

Это как ???
Как вы себе представляете вероятность?

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

Учится никогда не поздно.
для начала можно перечитать теорию вероятностей

Сообщение от Fedor666 n-й файл - очевидно P = 1/n (n-1)-й - это когда он выбран, а n-й - нет. P = (1/(n-1)) * (1 - 1/n) = 1/n (n-2)-й - это когда он выбран, а (n-1)-й и n-й - нет. P = (1/(n-2)) * (1 - 1/(n-1)) * (1 - 1/n) = 1/n и т. д.

ничего не понял
но откуда взялась n???? это количество файлов
тогда первый проход подсчет количество файлов
можно создать отдельный файл(типа базы данных )куда с определенной переодичностью (или по файловым операциям по хукам) будет скидываться количество файлов в директории и еще какая информация и работать с ним

0

Со всем возможным уважением, но вы хотите стену проломить там, где надо комара прихлопнуть.
Нафига создавать отдельную Базу Данных с внутренними ссылками и индексами, когда задача стоит в выборе случайного файла из директории? Чем не нравится предложенный алгоритм? Быстро и качественно за ОДИН проход с экономией ресурсов решает проблему. Не ищу других способов, если есть притензии к этому алгоритму, то прошу высказываться конкретней: что именно вас не устраивает в этом алгоритме?

Добавлено через 21 минуту
ValeryS, теорию вероятности я знаю на отлично, но дробями считать не умею
Прикол в тему:
Собеседование при приеме на работу:
- Как у Вас с английским?
- Читаю свободно, но не перевожу.

0

Два прохода вовсе не затормозят систему, на 900-ом асусе мы шустро запускали WPF приложение с .net 4.0, а вы паритесь над скоростью и памятью подсчета файлов.
Писал как-то бекап утилиту на с++ с винапи, так она за 10 минут (стековым, не рекурсивным проходом) обходила 750 гиговый за*ранный на ~95% винт. И это с выводом на экран полного пути и с несколькими проверками каждого файла. Ваша программа будет во много раз быстрее этой. Откройте свойства предполагаемой папки, забитой вашими 100500 картинками, и посмотрите как быстро он посчитает количество - ваша программа будет раза в 5 быстрее (ибо ненадо считать обьем, менять лейбл, отрисовывать форму и т.д.)
Чтоб использовать минимум памяти нужно два прохода, как это оговаривалось ранее. Так даже получится самый точный результат. Проц работает намного быстрее чем вы думаете
Плюс к этому, при стартапе оси производительнсть мала и нагрузка вашей программы будет незаметна.
Но даже если и это не сгодится то количество картинок можно передавать аргументом в программу в строке автозапуска, которую программа будет редактировать перед каждым шатдауном оси. Как такой вариант?

А еще у меня такой вопрос: вам столь важна вероятность? Ведь числом 1/n файл не выбрать (если названия(пути) конечно не были заранее вогнаны в массив или список, тогда споры об оптимизации нахождения количества вообще не уместны ХД). Точнее, можно выбрать, но номером итерации цикла: запомнили количество картинок, рандомно вычеслили число от 0 до n ( пусть это будет m), в цикле вайл m-раз FindNextFile'им (с проверкой на формат, размер, что там еще нужно), достаем имя файла и ставим на десктоп.

Добавлено через 15 минут
еще навеяло: если в папке много разных документов, то оба раза у каждого файла проверять расширение, относительно остального алгоритма, достаточно ресурсоемко. можно "индексы" файлов хранить в списке типа инт, тогда наше m будет указывать на элемент в списке как на элемент-результат, в котором будет индекс самого файла, т.е. количество необходимых итераций цикла. В таком случае проверку на расширение будет делать только первый проход. А список из интов оч мало весит. Можете и вектор использовать, но лучше список, ибо добавлений в список будет 100500 раз, а поиск в списке - 1 раз. напомню что список можно найти в STL

0

Это не Вы, случайно, писали виндос?
А то у меня тормозит что-то...
Согласен, что процессор быстро считает, но зачем лишний раз его напрягать, когда можно все миром решить? Вы, пожалуйста, укажите на недостаток ДАННОГО алгоритма, а не предлагайте свой или докажите ошибочность ДАННОГО алгоритма и тогда уже предлагайте свои варианты.
Спасибо за учатие, очень приятно, что много людей откликнулось

0

к сожалению я не вижу в теме алгоритма, вижу только предложения.
формулы нахождения вероятности правильные, но если известно n. насчет нахождения n все здесь и беседуют. предоставьте нам полный алгоритм, или блок-схему, или исходник и вам укажут на недостатки алгоритма, а может даже подчеркнут какой-то особый креативный метод и похвалят.

Добавлено через 1 минуту
если тормозит ось, то наверняка уже нахватались гадости в авторан) правильно настроенные оси правильно работают, но не будем об этом, тема форума о другом.

Добавлено через 2 минуты

Сообщение от Fedor666 Вы, пожалуйста, укажите на недостаток ДАННОГО алгоритма, а не предлагайте свой или докажите ошибочность ДАННОГО алгоритма и тогда уже предлагайте свои варианты.

по отсутствии ДАННОГО алгоритма я предложил свой, а вы уже сравнивайте, где лучше, что не так.

0

Все просто: есть директория, в которой неизвестное количество файлов. Производим обход этой директории т.е. поиск первого файла, поиск следующего файла, поиск следующего файла и т.д. На каждый подходящий по формату файл, мы запоминаем его имя с вероятностью 1 к номеру текущего файла. Последний, который запомненный, и есть искомый. Вот и весь алгоритм см. подробней в начале темы. Весь фокус в том, чтобы не запоминать все имена и не обходить директорию дважды. Все уже сделано, вопрос только в правильности распределения вероятностей. Или предоставить исходник? Дело не в реализации, а в идее! Все таки, оказывается, возможно распределить вероятность, не зная заранее количества. Вот и весь вопрос.

0

задача: посчитать вероятность или правильно выбрать файл для вставки на десктоп? если первое, то да, 1 проход всего лишь нужен и у вас он реализован правильно. для второй задачи нужно или сохранять все пути или два прохода.

0

Сообщение от Fedor666 ValeryS, теорию вероятности я знаю на отлично,

Сообщение от Fedor666 Прикол в том, что можно вычислить вероятность чего-то, не зная сколько этого "чего-то" заранее.

На отлично от чего?

Сообщение от Fedor666 Нафига создавать отдельную Базу Данных с внутренними ссылками и индексами,

Сообщение от ValeryS можно создать отдельный файл(типа базы данных )

ключевое слово ТИПА
простейший вариант в файле только одно число-количество файлов

ты ведь так и не ответил откуда n ?
и возник второй вопрос как без ассоциации перевести число в имя файла?

Сообщение от Fedor666 Прикол в тему:

лучше этот
Вопрос: Какова вероятность выйдя на улицу встретить динозавра?
Мужской ответ: близка к 0.
Женский ответ: 1/2. Или встречу или не встречу.

1

Задача решена и так и так. На первой странице даже ссылку выложил уже на готовую программу. За один проход решается все две задачи. Были сомнения в правильности, что Я против учебников попер, но кажись халявно прокатило Скачай ~4 Кб, если увидишь глюки - пиши: fedfed@rambler.ru буду очень признателен.

Добавлено через 1 минуту
"n" это номер текущего файла.

Добавлено через 3 минуты
Перевести число в имя файла невозможно. Нужно опять обходить всю директорию по порядку, отсчитывая их. Но в моем случае, мы уже запомнили имя.

0

Сообщение от ValeryS ты ведь так и не ответил откуда n?

у него это видимо реализовано так:
итого n = found.

Сообщение от ValeryS и возник второй вопрос как без ассоциации перевести число в имя файла?

а для этого уже нужен или список путей сохраненных, или второй проход (с повторной проверкой расширения), или использовать список "порядковый номер результата" - "порядковый номер самого файла". "пор. ном. самого файла" - число пустых итераций FindNextFile(...) по выходу из цикла структура WIN32_FOUND_DATA, или как там она правильно называется, будет иметь при себе имя нужного файла.

1

Сообщение от Fedor666 Все таки, оказывается, возможно распределить вероятность, не зная заранее количества. Вот и весь вопрос.

Сообщение от Fedor666 Производим обход этой директории т.е. поиск первого файла, поиск следующего файла, поиск следующего файла и т.д. На каждый подходящий по формату файл, мы запоминаем его имя с вероятностью 1 к номеру текущего файла. Последний, который запомненный, и есть искомый.

а это не подсчет количество файлов???
и вообще я понял мы говорим по разному!!!
мой вариант (с файлом, можно и в памяти)
1 Ищем файлы
при этом подсчитываем их количество и запоминаем соответствие
1-первый файл
2-второй файл
.......................
грубо говоря создаем список
2 вычисляем номер выбраного файла
генератор случайных чисел от 1 до количества файлов
3 выбираем файл благодаря списку
Где 2 прохода???
причем первый шаг ты можешь размазать по времени работы всей системы(тогда файл)

равновероятность равна 1/n
(надеюсь мы равновероятностных событиях говорим?)
что ты и получил в первом посте(только как то хитро)
и вероятность(как таковая) здесь не нужна все сделает генератор

0

толку от ехе)) мы ж не тестировщики)) нам код предоставляй =Р

Добавлено через 4 минуты

Сообщение от ValeryS выбираем файл благодаря списку

не только имя файла, но и путь, путь максимум 260 символов, даже если ascii, это 260 байт, если файлов 100'000, то это 24 метра памяти, а задача у нас в том, чтоб как меньше памяти заюзать.

0