LabVIEW Portal

В описании раздела "обсуждение алгоритмов", а обсуждения не наблюдается :)
Я (в том числе пользуясь сложившейся ситуацией) подтягиваю теор. базу, изучаю "Алгоритмы" авторства Р. Стивенса.
Буду сюда порой выкладывать интересные (и IMHO полезные алгоритмы)

Первым будет рандомизатор.
Бывала необходимость взять случайный набор из неслучайного массива, и решал эту задачу я кривыми способами. А оказывается, всё давно придумали.
Рандомизатор работает в двух режимах: перемешивает весь массив, или выдаёт случайную выборку заданного размера из него.
В приложении - исходники на 15 Есть универсальная мешалка, а есть специализированные для I32/dbl

Круто! А я искал, что бы такого почитать..

Похоже, в NI тоже читали эту книгу...

dadreamer писал(а):Похоже, в NI тоже читали эту книгу...

и тоже недавно :)
в 16 такого ещё нет.

Я бы внутренний кейс оптимизировал - функция перестановки имеет вход T/F, неравенство индексов туда можно подать

Artem.spb писал(а):Я бы внутренний кейс оптимизировал...

И что это дает???
Лучше обратите внимание на число перестановок (N-1), функцию округления Round Toward -Inf и порядок перестановок (перемешивание) с конца массива :)

Blackman писал(а):И что это дает???

то, что не будет происходить перестановка там, где она не требуется.

Лучше обратите внимание на число перестановок (N-1), функцию округления Round Toward -Inf и порядок перестановок (перемешивание) с конца массива :)

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

Функция округления Round Toward -Inf и порядок перестановок (перемешивание) с конца массива - это соль алгоритма!!!

Теперь массив с двумя элементами не перемешивается :)
Для выборки указывается требуемое число перестановок (N-1), где N-длина выборки, а дальше или array subset cо смещением в индексе или split array или delete from array c длиной выборке в длине.

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 длиной выборке в длине.

В чём принципиальная разница мешать с конца или начала?
В моей реализации, согласен, напутал с количеством повторов, но вот разницу в направлении движения не вижу.

Применение 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 конечного массива.

Blackman писал(а):Применение rtn не дает равномерного (uniform) распределения. Вероятность 0 и верхнего значения в 2 раза меньше остальных значений диапазона.

Вот подстава, никогда не думал что я так обделяю граничные значения, спасибо за науку, придётся все проекты переделывать :)

В книге Int J= random number между i и max_i-1 -> . Поэтому перестановки идут снизу вверх, но сложнее вычислять значение J.
В Вашем алгоритме Int J= random number между 0 и (max_i-1)-i. Поэтому перестановки должны идти сверху вниз, проще вычисляется значение J.

у меня не -i, а +i, именно для того, чтобы получить "случайное" от i до max.
С тем, что случайное вычислять проще, согласен, что-то Род не подумал над тем, чтобы оптимизировать эту часть вычислений.

Согласен. В последней редакции J + i :)

Я уже не совсем понимаю о чем спор...
Если о производительности алгоритма, то это одно, если о равномерности перемешивания, то другое.
Я например, если необходимо выполнить случайный выбор из конечного числа вариантов, делаю следующее. Но сразу оговорюсь, что производительность меня не интересует, например выбор 10 вопросов тестируемому из 100 возможных или определить последовательность представления 10 вопросов, т.е. меня особо не интересует 1 мс или 10 мс на это потребуется.
1. Генерирую случайный массив в пределах -1..1 используя Uniform White Noise длиной допустим в 100 раз больше числа вариантов.
2. Строю гистограмму, причем количество интервалов равно количеству вариантов.
3. Сортирую варианты согласно частоте в гистограмме.
Вариант не самый быстрый, но проверенный и дает гарантированный результат.
Часто приходится моделировать или тестировать и уже натыкался на ситуацию описанную Blackman, для ее обхода делал +1 к количеству вариантов, а потом из сгенерированного числа -0,5 и уже после этого округление.

IvanLis писал(а):Я уже не совсем понимаю о чем спор...

мы не ищем а просто обсуждаем ошибки в моей реализации :)