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

Доброго времени суток.
Сделал программу, изменяющую фон рабочего стола ВыньДос на случайный файл из указанной директории. Сколько в ней файлов неизвестно. Может 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

Так мы же при проходе, когда проверяем вероятность, уже имя запоминаем!? И более ничего не нужно уже.

Считать количество файлов, что бы генерить случайное число от 0 до n, это один хлостой проход!

Мой вариант:
Первый файл мы запоминаем с вероятностью 1 к 1, второй 1 к 2, третий 1 к 3 и т.д. до конца. Последний, который запомнили, и есть тот самый случайный.
Если вероятности одинаковые, то зачем лес городить?
Скажите, чем такой подход плох?

Код, к сожелению, на ассемблере, там что смотреть? Дело не в коде а в ИДЕЕ!!!

0

Сообщение от Vitam1n не только имя файла, но и путь, путь максимум 260 символов,

имя в файла(полное) в Винде подразумевает вот такую запись
C:\dir1\dir2\file.xz
FindFirstFile/FindNextFile
выдает в этом формате

1

Сообщение от Vitam1n у него это видимо реализовано так: C++ 1 2 3 4 5 6 7 8 9 float P = 1; int found = 0; do {  if (...) // проверка на расширение  {  P *= 1 / ++found;  } }while(FindNextFile(...)); итого n = found.

все равно оптимальней посчитать именно количество, а потом 1 / колисество. так вычислений меньше.

1

Есть константа MAX_PATH называется, она и содержит максимально допустимую длину имени файла вместе с путем.

Vitam1n, вычислений меньше - не согласен, а работы с тормозным жестким диском в 1,5 раза в среднем меньше это точно!

0

Сообщение от ValeryS имя в файла(полное) в Винде подразумевает вот такую запись C:\dir1\dir2\file.xz FindFirstFile/FindNextFile выдает в этом формате

в структуре, передаваемой по ссылке в эти функции храниться само название файла. я с ней работал мес назад.

Добавлено через 48 секунд

Сообщение от Fedor666 Последний, который запомнили, и есть тот самый случайный.

он будет просто последний. рандомным выбором картинки, судя по описанию, и не пахнет

Добавлено через 32 секунды

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

вот она на х86 машинах равна 260

Добавлено через 21 секунду

Сообщение от Fedor666 Код, к сожелению, на ассемблере, там что смотреть?

что мы, асм код не видели ни разу?

0

Сообщение от Fedor666 Первый файл мы запоминаем с вероятностью 1 к 1, второй 1 к 2, третий 1 к 3 и т.д. до конца. Последний, который запомнили, и есть тот самый случайный.

как ты их собираешься выбирать???
и вероятности надо будет править у всех файлов

Сообщение от Fedor666 Если вероятности одинаковые, то зачем лес городить?

я тоже интересуюсь???

Сообщение от Fedor666 Дело не в коде а в ИДЕЕ!!!

вот идею то мы и не поняли
напиши на псевдо коде или блок схему??

Сообщение от Fedor666 Так мы же при проходе, когда проверяем вероятность, уже имя запоминаем!? И более ничего не нужно уже.

дальше что мы будем делать с этой вероятностью????

Сообщение от Fedor666 Первый файл мы запоминаем с вероятностью 1 к 1, второй 1 к 2, третий 1 к 3 и т.д. до конца. Последний, который запомнили, и есть тот самый случайный.

кажется я врубился
ты создаешь тот же список но так чтоб враги не дагадались

0

Сообщение от Fedor666 Vitam1n, вычислений меньше - не согласен, а работы с тормозным жестким диском в 1,5 раза в среднем меньше это точно!

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

0

Сообщение от Fedor666 Последний, который запомнили, и есть тот самый случайный.

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

Это как стыкуется

0

Вот алгоритм, а то уже передрались все

Ищем первый файл
Цикл
Проверяем расширение
Если подходит то
Count++
Генерим случайное число
Делим его на Count
Если остаток 0 то
Запоминаем имя и путь
КонецЕсли
КонецЕсли
Ищем следующий файл
КонецЦикла


Список не создается. Просто новое имя сохраняется поверх старого. И фсе...

1

Сообщение от Fedor666 Вот алгоритм, а то уже передрались все Ищем первый файл Цикл Проверяем расширение Если подходит то Count++ Генерим случайное число Делим его на Count Если остаток 0 то Запоминаем имя и путь КонецЕсли КонецЕсли Ищем следующий файл КонецЦикла

эм..


10кб ехе. точна асм? )

дык если сгенерируется 12345, а каунт будет равен 1, то при делении остаток будет равен 0 и путь сохраниться. толк от вычислений. алгоритм в целом неудачный. имхо. уже человек 10 говорят вам как надо было делать. 1 делим на общее количесто = вероятность выбора одного файла у каждого файла из всех. нужный файл узнаем = rand(0,n); переходим и ставим...

1

Сообщение от Fedor666 Если остаток 0 то Запоминаем имя и путь

а если не 0???
первый файл мы всегда запомним
второй фифти фифти
третий одна треть
и т.д
или ты заменяешь имя файла
тогда ГУД
но будет зависеть от генератора
может случайное число тоже один раз генерить???

1

Случайное число на каждый файл свое. Это уже какие-то оскарбления пошли
Точно асм, там более половины это иконка и ресурсы.
P.S. Это ж не системный драйвер?!

0

точна, иконка много жрет (((.
может алгоритм и работает, но поверхностный взгял говорит о том, что файлы будут выбраны некоторые из первых, что уже в принципе не верно.
еще раз повторюсь: ищем файлы нужного расширения и сохраняем их последовательный номер, генерируем ранломное число от 0 до "всего файлов", переходим по рандомному числу к последовательному нмеру файла. переходим к файлу и делаем с ним все что нужно. минимум памяти и намного меньше вычислений процом, обращений к диску на ~25% больше чем у вас, но результат будет верным.

предлагать написать это на си не буду, ибо если вы на асме пишете, то мое предложение будет слегка неуместным)

0

Практика сделана, теория подтвердилась математически.
Что Вы как коршуны набросились на ребенка? Типа, не делай так, а делай так! Опчем речь? Одна философия! Есть конкретная идея и я хотел узнать Ваше мнение конкретно по ней, а Вы на нее забили и тычите мне свои варианты...
Тема была: "Просчет вероятности", а Вы мне: "Что поделить, какой размер, куда пойти"...

Все, ухожу я от Вас. И не постите более ничего

0

Vitam1n,
Ты не понял
смотри
1 файл запишем всегда
2 файл перепишет первый с вероятностью 1/2(соответственно первый останется с той же вероятностью)
3 перепишет предыдущий с вероятностью 1/3
................................
как раз на первый взгляд событие равноверотно для всех файлов
но при генерации при каждой итерации случайного числа по моему возникнет перекос
число нужно генерить один раз
возникает вопрос о инициализации генератора
иначе получим то что при каждом запуске программы будет генерится одно и тоже число

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

Сообщение от Fedor666 Случайное число на каждый файл свое. Это уже какие-то оскарбления пошли

не понял????
твоя запись

Если подходит то Count++ Генерим случайное число Делим его на Count

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

Сообщение от Fedor666 Практика сделана, теория подтвердилась математически. Что Вы как коршуны набросились на ребенка?

"Народ! хочет разобраться" (с) "Операция Ы"

1

Число обязано генерироваться каждый раз новое по-любому. Для этого используется rdtsc, возвращающее количество прошедших тактов с момента запуска компа и предыдущее значение. Хотел сначала использовать РСЛОС или конгруэнтный генератор, но нафиг тут такие сложности? Формула расчета вероятности выложена. Что не так???

0

Сообщение от ValeryS 1 файл запишем всегда 2 файл перепишет первый с вероятностью 1/2(соответственно первый останется с той же вероятностью) 3 перепишет предыдущий с вероятностью 1/3

1 файл всегда если он 1,
2 файл с вероятностью 1/2 если файлов два.
3 файл с вероятность 1/3 если файлов три

да, прийдя до последнего мы найдем вероятность общую для всех, я с этим согласен. программа рабочая - с этим тоже согласен. результаты подтвердились - еще лучше. но алгоритм очень кривой.
100к файлов по вашему алгоритму это 100к рандомов, это 100к делений 1/n (с потерей точности, ибо цифер после запятой фиксированное количество), а потом 100к умножений этих ДРОБНЫХ чисел. одно только умножение происходит за тактов равное величине второго операнда. деление в 10 раз дольше. толку от ассамблера ноль если кривой алгоритм. я же предложил 100к инкрементов выолняемых за 1 такт и одно деление 1/количество в допустим 100 тактов. 1 проход с инкрементом и 1 деление. и тот же результат.

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

Добавлено через 7 минут
выбор 1 яблока из мешка в котором 100 яблок. у каждого яблока 1/100 быть выбранным.
федор, ты делаешь так:
вытащили яблоко,
это у нас какое по счету?
1 делим на порядок...ага...умножаем на то что раньше посчитали...ага...запоминаем...
вытащили следующее яблоко.
это у нас какое по счету?
1 делим на порядок...ага...умножаем на то что раньше посчитали...ага...запоминаем...
и так сто раз.

как делаю я:
достали яблоко, раз
достали яблоко, два
достали яблоко, три
...
сто яблок? ага 1 делим на сто....ага...запомнили...

0

Сообщение от Fedor666 Число обязано генерироваться каждый раз новое по-любому

"это пощему еще"

Сообщение от Vitam1n (с потерей точности, ибо цифер после запятой фиксированное количество),

какая точность ??? проверяется делится число на число или нет.
целочисленая арифметика

Сообщение от Vitam1n потом 100к умножений этих ДРОБНЫХ чисел

это ты где увидел???

1

Какие дробные числа? Только целочисленное деление DIV. И потом счего нам такты считать, если мы в цикле API FindNextFile вызываем? Оптимизация неуместна

0

Сообщение от Vitam1n сто яблок? ага 1 делим на сто....ага...запомнили...

надо выбрать файл а не подсчитывать вероятность

1