Простые алгоритмы (готовые)

Обсуждение научных открытий, алгоритмов и инженерных новинок
Ответить
Artem.spb

Activity Автор
expert
expert
Сообщения: 1964
Зарегистрирован: 31 июл 2011, 23:05
Награды: 2
Репутация: 0
Версия LabVIEW: 12-18
Контактная информация:

Простые алгоритмы (готовые)

Сообщение Artem.spb »

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

Artem.spb

Activity Автор
expert
expert
Сообщения: 1964
Зарегистрирован: 31 июл 2011, 23:05
Награды: 2
Репутация: 0
Версия LabVIEW: 12-18
Контактная информация:

Re: Простые алгоритмы (готовые)

Сообщение Artem.spb »

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

Аватара пользователя
Kosist

Activity Gold
expert
expert
Сообщения: 1069
Зарегистрирован: 21 фев 2011, 23:44
Награды: 2
Репутация: 0
Версия LabVIEW: 2013-2020
Контактная информация:

Re: Простые алгоритмы (готовые)

Сообщение Kosist »

Круто! А я искал, что бы такого почитать..
Мы делили апельсин - много наших полегло...

Аватара пользователя
dadreamer

Activity Professionalism Автор
professor
professor
Сообщения: 3508
Зарегистрирован: 17 фев 2013, 16:33
Награды: 4
Репутация: 0
Версия LabVIEW: 2.5 — 2020
Контактная информация:

Re: Простые алгоритмы (готовые)

Сообщение dadreamer »

Похоже, в NI тоже читали эту книгу... :crazy:
Вложения
2020-04-13_19-46-37.jpg

Artem.spb

Activity Автор
expert
expert
Сообщения: 1964
Зарегистрирован: 31 июл 2011, 23:05
Награды: 2
Репутация: 0
Версия LabVIEW: 12-18
Контактная информация:

Re: Простые алгоритмы (готовые)

Сообщение Artem.spb »

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

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

Blackman

Activity
leader
leader
Сообщения: 931
Зарегистрирован: 17 янв 2016, 15:02
Награды: 1
Репутация: 0
Версия LabVIEW: 6.1,8.5,20
Контактная информация:

Re: Простые алгоритмы (готовые)

Сообщение Blackman »

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

Artem.spb

Activity Автор
expert
expert
Сообщения: 1964
Зарегистрирован: 31 июл 2011, 23:05
Награды: 2
Репутация: 0
Версия LabVIEW: 12-18
Контактная информация:

Re: Простые алгоритмы (готовые)

Сообщение Artem.spb »

Blackman писал(а):И что это дает???
то, что не будет происходить перестановка там, где она не требуется.
Лучше обратите внимание на число перестановок (N-1), функцию округления Round Toward -Inf и порядок перестановок (перемешивание) с конца массива :)
с числом мой косяк, лишних шагов наделал. С округлением порядок из-за пределов случайного числа, а направление перемешивания для перемешивания не имеет значения, но в моём случае начальная цель алгоритма - взять случайную выборку из массива (в общем случае - меньшего размера, чем массив), поэтому я иду с первого элемента и останавливаюсь, когда "перемешал" достаточное количество.

Blackman

Activity
leader
leader
Сообщения: 931
Зарегистрирован: 17 янв 2016, 15:02
Награды: 1
Репутация: 0
Версия LabVIEW: 6.1,8.5,20
Контактная информация:

Re: Простые алгоритмы (готовые)

Сообщение Blackman »

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

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

Artem.spb

Activity Автор
expert
expert
Сообщения: 1964
Зарегистрирован: 31 июл 2011, 23:05
Награды: 2
Репутация: 0
Версия LabVIEW: 12-18
Контактная информация:

Re: Простые алгоритмы (готовые)

Сообщение Artem.spb »

Blackman писал(а):Функция округления Round Toward -Inf и порядок перестановок (перемешивание) с конца массива - это соль алгоритма!!!
наверно, это соль другого алгоритма :)
В книге описано перемешивание с начала
photo_2020-04-14_17-16-36.jpg
По моему округление в моём случае правомерно, потому что я использую другой предел случайности:
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 длиной выборке в длине.
В чём принципиальная разница мешать с конца или начала?
В моей реализации, согласен, напутал с количеством повторов, но вот разницу в направлении движения не вижу.

Blackman

Activity
leader
leader
Сообщения: 931
Зарегистрирован: 17 янв 2016, 15:02
Награды: 1
Репутация: 0
Версия LabVIEW: 6.1,8.5,20
Контактная информация:

Re: Простые алгоритмы (готовые)

Сообщение Blackman »

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

Artem.spb

Activity Автор
expert
expert
Сообщения: 1964
Зарегистрирован: 31 июл 2011, 23:05
Награды: 2
Репутация: 0
Версия LabVIEW: 12-18
Контактная информация:

Re: Простые алгоритмы (готовые)

Сообщение Artem.spb »

Blackman писал(а):Применение rtn не дает равномерного (uniform) распределения. Вероятность 0 и верхнего значения в 2 раза меньше остальных значений диапазона.
Вот подстава, никогда не думал что я так обделяю граничные значения, спасибо за науку, придётся все проекты переделывать :)
rnd.PNG
В книге Int J= random number между i и max_i-1 -> . Поэтому перестановки идут снизу вверх, но сложнее вычислять значение J.
В Вашем алгоритме Int J= random number между 0 и (max_i-1)-i. Поэтому перестановки должны идти сверху вниз, проще вычисляется значение J.
у меня не -i, а +i, именно для того, чтобы получить "случайное" от i до max.
С тем, что случайное вычислять проще, согласен, что-то Род не подумал над тем, чтобы оптимизировать эту часть вычислений.

Blackman

Activity
leader
leader
Сообщения: 931
Зарегистрирован: 17 янв 2016, 15:02
Награды: 1
Репутация: 0
Версия LabVIEW: 6.1,8.5,20
Контактная информация:

Re: Простые алгоритмы (готовые)

Сообщение Blackman »

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

Аватара пользователя
IvanLis

Activity Professionalism Tutorials Gold Man of the year 2012
Автор
professor
professor
Сообщения: 4946
Зарегистрирован: 02 дек 2009, 17:44
Награды: 7
Репутация: 0
Версия LabVIEW: 2015, 2016
Откуда: СССР

Re: Простые алгоритмы (готовые)

Сообщение IvanLis »

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

Artem.spb

Activity Автор
expert
expert
Сообщения: 1964
Зарегистрирован: 31 июл 2011, 23:05
Награды: 2
Репутация: 0
Версия LabVIEW: 12-18
Контактная информация:

Re: Простые алгоритмы (готовые)

Сообщение Artem.spb »

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

Ответить

Вернуться в «Наука»