Veresk

*Lazarus *public
Короче, если надо при тестировании задать вопросов меньше, чем в наличии, то выбираем нужное количество случайных. Если нужно задать вопросов больше, чем есть в наличии, то задаём все что есть в случайном порядке, а потом добавляем сколько угодно повторов случайных. Код такой, надо бы его оптимизировать: pastebin.com

#1927882
from Psi+, 23 days ago

← All messages

Replies (25)

Post a reply (xmpp)

@lurker:
1 shuffle
2 loop through
#1927882/1
from web, 23 days ago
@Veresk:
@lurker матом не ругайся
#1927882/2
from Psi+, 23 days ago, in reply to /1
@lurker:
@Veresk 1 перемешать questions
2 questions [i++ % questions.length]
#1927882/3
from web, 23 days ago, in reply to /2
@Veresk:
@lurker дык я их и перемешиваю, а потом добиваю рандомом, если надо
#1927882/4
from Psi+, 23 days ago, in reply to /3
@lurker:
@Veresk я про For i:=1 to base+1 do
begin
quest_random[i] := tmarray [i];
end;
For i:=base to fake do
begin
quest_random[i] := random(base)+1;
end;

отчего бы не quest_random[i]:= tmparray[i mod tmparray.length] или как там в паскале
#1927882/5
from web, 23 days ago, in reply to /4
@murrrf:
А ты рассматривал идею того, что создаются два временных массива — массив исходных чисел, заполняемый прямой последовательностью, и массив флагов? Дальше из массива исходных чисел берется число в случайной позиции и пишется в результирующий массив, в массив флагов в этой позиции пишется единица. При каждом запросе числа со случайным индексом проверяем, не единица ли во флаге, если да, то ищем индекс ближайшего следующего флага, равного нулю, и берем число с этим индексом. После того, как массив флагов весь заполнится единицами — т.е., весь исходный массив скопирован в результирующий — сбрасываем все флаги в ноль и повторяем, пока результирующий массив не заполнится.
Эта идея позволяет одним и тем же путем заполнять результирующий массив любой длины, но вот оптимальна ли она с точки зрения затрат, не уверен.
#1927882/6
from WinHome, 23 days ago
@Veresk:
@murrrf не оптимальна, уже обсуждалось
#1927882/7
from Psi+, 23 days ago, in reply to /6
@Veresk:
@lurker ну я сделал то же самое, только вручную, кажется :-)
#1927882/8
from Psi+, 23 days ago, in reply to /5
@murrrf:
@Veresk А, значит, пропустил.
#1927882/9
from WinHome, 23 days ago, in reply to /7
@Veresk:
@murrrf наиболее быстро получается, всё-таки, спева заполнить, а потом перемешать массив, а не рандомить его. Как-то так :-)
#1927882/10
from Psi+, 23 days ago, in reply to /9
@murrrf:
@Veresk Это да, я задумался над тем, чтобы упростить заполнение конечного массива. А количество повторов в конечном массиве, если он длиннее исходного, как-то регламентируется?
#1927882/11
from WinHome, 23 days ago, in reply to /10
@Veresk:
@murrrf нет, просто закидываем рандомом. Он ведь может и в 10 раз длиннее быть, что там рекламентировать? Плюс ко всему, это явно извращенский способ проходить тест — с повторами вопросов, нефиг мудрить.
#1927882/12
from Psi+, 23 days ago, in reply to /11
@murrrf:
@Veresk Я так думаю, и эта идея уже обсуждалась и была отвергнута, но все же выскажу:) Берем исходный массив, прямой, перемешиваем его, пишем в конечный, пока один из двух массивов не кончится. Если конечный короче, то на этом все, если нет — еще раз перемешиваем исходный и снова копируем из него столько элементов, сколько до ближайшего конца массива. И так до полного заполнения конечного массива.
#1927882/13
from WinHome, 23 days ago, in reply to /12
@Veresk:
@murrrf тоже как вариант, кстати. Только во вложенных циклах я утону, как я написал — топорно, но сработает :-)
#1927882/14
from Psi+, 23 days ago, in reply to /13
@murrrf:
@Veresk Подправил твою функцию с использованием моего предложения с повторным перемешиванием — pastebin.com , погляди, имеет ли это смысл.
Кстати, а почему ты начинаешь динамические массивы с единицы?
#1927882/15
from WinHome, 23 days ago, in reply to /14
@Veresk:
@murrrf С единицы начинаю исключительно ради удобства: неудобно логически потом обрабатывать нулевой вопрос, хоть издохни. Гораздо проще считать 1...N, чем 0...N-1. Код ща гляну
#1927882/16
from Psi+, 23 days ago, in reply to /15
@Veresk:
@murrrf Да, думаю это взлетит, но есть пара заметок: циклы For стали вложенными, значит их ещё и много получится. А ещё нас в детстве учили, что while работает медленнее for. Впрочем, это всё равно быстрее, чем рандомить уникальные значения, как было 6 лет назад.
#1927882/17
from Psi+, 23 days ago, in reply to /15
@murrrf:
@Veresk Тут while, а не for, только ради наглядности, на самом деле и то, и другое годится. А вложенный цикл for из ArrayShuffle вызывается один раз за перебор всего исходного массива, так что сильного замедления дать не должен.
#1927882/18
from WinHome, 23 days ago, in reply to /17
@Veresk:
@murrrf В общем, вполне годный вариант! Надо бы как-то затестировать время выполения твоего и моего вариантов на тестах в 1000-2000 вопросов..
#1927882/19
from Psi+, 23 days ago, in reply to /18
@murrrf:
@Veresk У меня сейчас нет Лазаруса, есть только Дельфи 2006. Ты посчитай на своей машине тоже, а на моей вышло так. Самая медленная операция — вывод результата в memo8, когда она включена, при массивах исходном в 1000 элементов и конечном — в 3000 результаты десяти обсчетов примерно такие:
Veresk min = 1328
Veresk max = 1359
Veresk med = 1343
murrf min = 1328
murrf max = 1375
murrf med = 1354
А вот если ее выключить, то картина меняется разительно. Мне пришлось выставить 10 000 элементов в исходном и 3 000 000 в конечном, чтобы время выполнения одного обсчета стало отличаться от нуля. И в этом случае получается уже вот так:
Veresk min = 9
Veresk max = 16
Veresk med = 10
murrf min = 31
murrf max = 43
murrf med = 32
Кажется, я выбываю из состязания оптимизаторов в связи с неоптимальностью моего кода...
#1927882/20
from WinHome, 23 days ago, in reply to /19
@Veresk:
@murrrf а я хз как такой тест в лазарусе намыть ))) Но результат да, видимый, в 3 раза )) Правда, максимум входного массива 10 000, а выходного и того меньше )
#1927882/21
from Psi+, 23 days ago, in reply to /20
@murrrf:
@Veresk Кроссплатформенной функции для измерения длительности я не знаю, а под виндой есть винапишная функция GetTickCount, возвращающая время в миллисекундах от включения компа.
#1927882/22
from WinHome, 23 days ago, in reply to /21
@Veresk:
@murrrf думаю тут тоже что-то есть, надо будет курнуть, когда рефакторингом займусь
#1927882/23
from Psi+, 23 days ago, in reply to /22
@murrrf:
@Veresk Щас поставил входной в 10 000 и выходной в 5 000, результаты с выводом такие:
Veresk min = 2203
Veresk max = 2343
Veresk med = 2246
murrf min = 2218
murrf max = 2250
murrf med = 2239
В общем и целом, результаты близкие.
#1927882/24
from WinHome, 23 days ago, in reply to /23
@Veresk:
@murrrf в пределах статистики, ага
#1927882/25
from Psi+, 23 days ago, in reply to /24

Subscribe

Replies (25)

Messages