Простые алгоритмы (готовые)
-
- professor
- Сообщения: 3406
- Зарегистрирован: 31 июл 2011, 23:05
- Награды: 2
- Версия LabVIEW: 12-18
- Благодарил (а): 49 раз
- Поблагодарили: 176 раз
- Контактная информация:
Простые алгоритмы (готовые)
В описании раздела "обсуждение алгоритмов", а обсуждения не наблюдается :)
Я (в том числе пользуясь сложившейся ситуацией) подтягиваю теор. базу, изучаю "Алгоритмы" авторства Р. Стивенса.
Буду сюда порой выкладывать интересные (и IMHO полезные алгоритмы)
Я (в том числе пользуясь сложившейся ситуацией) подтягиваю теор. базу, изучаю "Алгоритмы" авторства Р. Стивенса.
Буду сюда порой выкладывать интересные (и IMHO полезные алгоритмы)
-
- professor
- Сообщения: 3406
- Зарегистрирован: 31 июл 2011, 23:05
- Награды: 2
- Версия LabVIEW: 12-18
- Благодарил (а): 49 раз
- Поблагодарили: 176 раз
- Контактная информация:
Re: Простые алгоритмы (готовые)
Первым будет рандомизатор.
Бывала необходимость взять случайный набор из неслучайного массива, и решал эту задачу я кривыми способами. А оказывается, всё давно придумали.
Рандомизатор работает в двух режимах: перемешивает весь массив, или выдаёт случайную выборку заданного размера из него.
В приложении - исходники на 15 Есть универсальная мешалка, а есть специализированные для I32/dbl
Бывала необходимость взять случайный набор из неслучайного массива, и решал эту задачу я кривыми способами. А оказывается, всё давно придумали.
Рандомизатор работает в двух режимах: перемешивает весь массив, или выдаёт случайную выборку заданного размера из него.
В приложении - исходники на 15 Есть универсальная мешалка, а есть специализированные для I32/dbl
- Вложения
-
- randomisation15.zip
- (43.12 КБ) 155 скачиваний
-
Kosist
- expert
- Сообщения: 1236
- Зарегистрирован: 21 фев 2011, 23:44
- Награды: 2
- Версия LabVIEW: 2013-2020
- Благодарил (а): 23 раза
- Поблагодарили: 30 раз
- Контактная информация:
Re: Простые алгоритмы (готовые)
Круто! А я искал, что бы такого почитать..
Мы делили апельсин - много наших полегло...
-
- professor
- Сообщения: 3406
- Зарегистрирован: 31 июл 2011, 23:05
- Награды: 2
- Версия LabVIEW: 12-18
- Благодарил (а): 49 раз
- Поблагодарили: 176 раз
- Контактная информация:
Re: Простые алгоритмы (готовые)
и тоже недавно :)dadreamer писал(а):Похоже, в NI тоже читали эту книгу...
в 16 такого ещё нет.
Я бы внутренний кейс оптимизировал - функция перестановки имеет вход T/F, неравенство индексов туда можно подать
-
- leader
- Сообщения: 932
- Зарегистрирован: 17 янв 2016, 15:02
- Награды: 1
- Версия LabVIEW: 6.1,8.5,20
Re: Простые алгоритмы (готовые)
И что это дает???Artem.spb писал(а):Я бы внутренний кейс оптимизировал...
Лучше обратите внимание на число перестановок (N-1), функцию округления Round Toward -Inf и порядок перестановок (перемешивание) с конца массива :)
-
- professor
- Сообщения: 3406
- Зарегистрирован: 31 июл 2011, 23:05
- Награды: 2
- Версия LabVIEW: 12-18
- Благодарил (а): 49 раз
- Поблагодарили: 176 раз
- Контактная информация:
Re: Простые алгоритмы (готовые)
то, что не будет происходить перестановка там, где она не требуется.Blackman писал(а):И что это дает???
с числом мой косяк, лишних шагов наделал. С округлением порядок из-за пределов случайного числа, а направление перемешивания для перемешивания не имеет значения, но в моём случае начальная цель алгоритма - взять случайную выборку из массива (в общем случае - меньшего размера, чем массив), поэтому я иду с первого элемента и останавливаюсь, когда "перемешал" достаточное количество.Лучше обратите внимание на число перестановок (N-1), функцию округления Round Toward -Inf и порядок перестановок (перемешивание) с конца массива :)
-
- leader
- Сообщения: 932
- Зарегистрирован: 17 янв 2016, 15:02
- Награды: 1
- Версия LabVIEW: 6.1,8.5,20
Re: Простые алгоритмы (готовые)
Функция округления Round Toward -Inf и порядок перестановок (перемешивание) с конца массива - это соль алгоритма!!!
Теперь массив с двумя элементами не перемешивается :)
Для выборки указывается требуемое число перестановок (N-1), где N-длина выборки, а дальше или array subset cо смещением в индексе или split array или delete from array c длиной выборке в длине.
Теперь массив с двумя элементами не перемешивается :)
Для выборки указывается требуемое число перестановок (N-1), где N-длина выборки, а дальше или array subset cо смещением в индексе или split array или delete from array c длиной выборке в длине.
-
- professor
- Сообщения: 3406
- Зарегистрирован: 31 июл 2011, 23:05
- Награды: 2
- Версия LabVIEW: 12-18
- Благодарил (а): 49 раз
- Поблагодарили: 176 раз
- Контактная информация:
Re: Простые алгоритмы (готовые)
наверно, это соль другого алгоритма :)Blackman писал(а):Функция округления Round Toward -Inf и порядок перестановок (перемешивание) с конца массива - это соль алгоритма!!!
В книге описано перемешивание с начала По моему округление в моём случае правомерно, потому что я использую другой предел случайности:
x = Round Toward -Inf (N*rnd)
x = Round Toward Nearest ((N-1)*rnd)
я где-то ошибся в этом предположении?
чёрт :)Теперь массив с двумя элементами не перемешивается :)
придётся постановить, что этот алгоритм работает для массивов размера от 3 :)
Меня запутало название "верхняя граница". Судя по пределам случайного числа это всё же индекс, тогда надо второй -1 убрать.
В чём принципиальная разница мешать с конца или начала?Для выборки указывается требуемое число перестановок (N-1), где N-длина выборки, а дальше или array subset cо смещением в индексе или split array или delete from array c длиной выборке в длине.
В моей реализации, согласен, напутал с количеством повторов, но вот разницу в направлении движения не вижу.
-
- leader
- Сообщения: 932
- Зарегистрирован: 17 янв 2016, 15:02
- Награды: 1
- Версия LabVIEW: 6.1,8.5,20
Re: Простые алгоритмы (готовые)
Применение rtn не дает равномерного (uniform) распределения. Вероятность 0 и верхнего значения в 2 раза меньше вероятности для остальных значений диапазона.
В книге Int J= random number между i и max_i-1 -> . Поэтому перестановки идут снизу вверх, но сложнее вычислять значение J.
В Вашем алгоритме Int J= random number между 0 и (max_i-1)-i. Поэтому перестановки должны идти сверху вниз, проще вычисляется значение J.
Для Вашего алгоритм легко проверить, например для массива с тремя элементами, что элемент в индексе 1 исходного массива никогда не будет элементом в индексе 2 конечного массива.
В книге Int J= random number между i и max_i-1 -> . Поэтому перестановки идут снизу вверх, но сложнее вычислять значение J.
В Вашем алгоритме Int J= random number между 0 и (max_i-1)-i. Поэтому перестановки должны идти сверху вниз, проще вычисляется значение J.
Для Вашего алгоритм легко проверить, например для массива с тремя элементами, что элемент в индексе 1 исходного массива никогда не будет элементом в индексе 2 конечного массива.
-
- professor
- Сообщения: 3406
- Зарегистрирован: 31 июл 2011, 23:05
- Награды: 2
- Версия LabVIEW: 12-18
- Благодарил (а): 49 раз
- Поблагодарили: 176 раз
- Контактная информация:
Re: Простые алгоритмы (готовые)
Вот подстава, никогда не думал что я так обделяю граничные значения, спасибо за науку, придётся все проекты переделывать :)Blackman писал(а):Применение rtn не дает равномерного (uniform) распределения. Вероятность 0 и верхнего значения в 2 раза меньше остальных значений диапазона.
у меня не -i, а +i, именно для того, чтобы получить "случайное" от i до max.В книге Int J= random number между i и max_i-1 -> . Поэтому перестановки идут снизу вверх, но сложнее вычислять значение J.
В Вашем алгоритме Int J= random number между 0 и (max_i-1)-i. Поэтому перестановки должны идти сверху вниз, проще вычисляется значение J.
С тем, что случайное вычислять проще, согласен, что-то Род не подумал над тем, чтобы оптимизировать эту часть вычислений.
-
IvanLis
- guru
- Сообщения: 5467
- Зарегистрирован: 02 дек 2009, 17:44
- Награды: 7
- Версия LabVIEW: 2015, 2016
- Откуда: СССР
- Благодарил (а): 28 раз
- Поблагодарили: 88 раз
Re: Простые алгоритмы (готовые)
Я уже не совсем понимаю о чем спор...
Если о производительности алгоритма, то это одно, если о равномерности перемешивания, то другое.
Я например, если необходимо выполнить случайный выбор из конечного числа вариантов, делаю следующее. Но сразу оговорюсь, что производительность меня не интересует, например выбор 10 вопросов тестируемому из 100 возможных или определить последовательность представления 10 вопросов, т.е. меня особо не интересует 1 мс или 10 мс на это потребуется.
1. Генерирую случайный массив в пределах -1..1 используя Uniform White Noise длиной допустим в 100 раз больше числа вариантов.
2. Строю гистограмму, причем количество интервалов равно количеству вариантов.
3. Сортирую варианты согласно частоте в гистограмме.
Вариант не самый быстрый, но проверенный и дает гарантированный результат.
Часто приходится моделировать или тестировать и уже натыкался на ситуацию описанную Blackman, для ее обхода делал +1 к количеству вариантов, а потом из сгенерированного числа -0,5 и уже после этого округление.
Если о производительности алгоритма, то это одно, если о равномерности перемешивания, то другое.
Я например, если необходимо выполнить случайный выбор из конечного числа вариантов, делаю следующее. Но сразу оговорюсь, что производительность меня не интересует, например выбор 10 вопросов тестируемому из 100 возможных или определить последовательность представления 10 вопросов, т.е. меня особо не интересует 1 мс или 10 мс на это потребуется.
1. Генерирую случайный массив в пределах -1..1 используя Uniform White Noise длиной допустим в 100 раз больше числа вариантов.
2. Строю гистограмму, причем количество интервалов равно количеству вариантов.
3. Сортирую варианты согласно частоте в гистограмме.
Вариант не самый быстрый, но проверенный и дает гарантированный результат.
Часто приходится моделировать или тестировать и уже натыкался на ситуацию описанную Blackman, для ее обхода делал +1 к количеству вариантов, а потом из сгенерированного числа -0,5 и уже после этого округление.
Знание нескольких принципов освобождает от знания многих фактов!
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
-
- professor
- Сообщения: 3406
- Зарегистрирован: 31 июл 2011, 23:05
- Награды: 2
- Версия LabVIEW: 12-18
- Благодарил (а): 49 раз
- Поблагодарили: 176 раз
- Контактная информация:
Re: Простые алгоритмы (готовые)
мы не ищем а просто обсуждаем ошибки в моей реализации :)IvanLis писал(а):Я уже не совсем понимаю о чем спор...