Поиск  Пользователи  Правила  Войти
Форумы "Планета Excel" » Вопросы по Microsoft Excel (архив)
Страницы: 1
RSS
алгоритм большого числа уникальных перестановок
 
#1
29.12.2010 11:38:17
Добрый день! Может кто подскажет, как можно оптимизировать/изменить алгоритм.  
Есть алгоритм генерирующий случайные перестановки из большого числа элементов. Эл-тов в районе 200 (может быть и поболее). Перестановок необходимо сгенерировать ~ 100 млн уникальных комбинаций (повторяющиеся варианты должны отбрасываться сразу на этапе генерации - т.е. необходимо определить что такой вариант уже был).  
 Сейчас:  
1) Эл-ты хранятся в массиве.  
2) Переносим их в коллекцию элементов.  
3) По одному случайным образом их оттуда извлекаем - в итоге получаем перестановку в виде string.  
4) Затем эту строку пытаемся добавить в коллекцию комбинаций (т.е. соответсвенно понимаем, была ли такой вариант уже).  
5) Возвращаемся к п.2 - генерируем новую случайную комбинацию.  
В итоге ПРОБЛЕМА - для работы не хватает RAM - 2 ГБ ОЗУ в один прекрасный момент целиком забиваются коллекцией из полученных вариантов перестановок.  
Может у кого-нибудь есть идеи, как решить/обойти эту проблему?  
Да, элементы беру минимальной длины.
 
 
 
#2
29.12.2010 12:00:30
случайно получать номер комбинации, заносить в словарь.  
 
100млн целых чисел - 380Мб памяти  
 
по номеру восстанавливать саму комбинацию  
 
 
только охватит ли long все комбинации?
Живи и дай жить..
 
 
 
#3
29.12.2010 12:26:37
Да, в этом и проблема, что номеров получается не хватает.  
Я думал также над вариантами кодировки номера комбинации, но пока подходящего варианта нет.
 
 
 
#4
29.12.2010 12:39:23
1) разработать алгоритм перехода от одной комбинации к следующей,  
такой что при запуске алгоритма он переберёт все возможные комбинации и придёт к исходной.  
(алгоритмы с шагом 1 написать достаточно легко, а вот алгоритм для которого можно напрямую из комбинации(N) получить комбинацию(M>N) зная (M-N) нужно подумать)  
2) задавшись начальной комбинацией случайным образом генерируем шаг M-N так чтобы для 100 миллионов шагов последний номер  не превысил число уникальных комбинаций;  на каждом шаге записываем уникальную комбинацию.  
 
Аналог предлагаемого способа: задавшись углом  алфа таким, что только (10^8)*алфа/пи()  целое; с помошью поворотов на этот угол можно получить 2*10^8 уникальных углов (от 0 до 2*пи())
 
 
 
#5
29.12.2010 12:40:57
тогда так:  
 
получаем комбинацию, делим на части, по каждой части вычисляем номер, номер заносим в словарь..  
 
две части - 760Мб  
три - 1140  
4 - 1520  
 
 
должно хватить..
Живи и дай жить..
 
 
 
#6
29.12.2010 17:50:11
dl, на вскидку не понял, чем Ваше предложение может мне помочь, попытаюсь дома разобраться.  
 
слэн, насчет разбиения на части тоже сразу не могу представить себе алгоритм, ведь получается при этом надо хранить не только номер комбинации в этой части, но и какие именно элементы попали в эту часть (комбинацию)...
 
 
 
#7
30.12.2010 02:52:00
Ещё та тема :-) http://www.planetaexcel.ru/forum.php?thread_id=14026  
 
Предлагаю псевдослучайность.  
 
1. Выделить из 200 элементов 27 уникальных элемента.  
Остальные 173 элемента сохранить отдельно до выполнения п.4  
 
2. Представить каждый из 27 уникальных элементов одним битом, итого 27 бит.  
Если перебирать биты по порядку, то получим 2^27 = 134 217 728 уникальных вариантов, что больше заданных 100 млн., т.е достаточно:  
 
0000000 0000000000 0000000000 = число 0  
0000000 0000000000 0000000001 = число 1  
0000000 0000000000 0000000010 = число 2  
0000000 0000000000 0000000011 = число 3  
...  
1111111 1111111111 1111111101 = число 134 217 725  
1111111 1111111111 1111111110 = число 134 217 726  
1111111 1111111111 1111111111 = число 134 217 727  
 
3. Очевидно, что порядковые числа  (индексы) от нуля до 134 217 727 укладываются в 4-байтный тип Long и могли бы  быть сохранены в книге или файле, а по ним можно сгенерировать последовательность. Но нет  смысла в сохранении такого массива, так как одновременно элементы массива все равно не будут обрабатываться. Достаточно написать функцию, которая будет выдавать одну перестановку 27 уникальных элементов по (случайному) индексу от 0 до 134 217 727.  
 
4.  Что делать с оставшимися 173 элементами?  
Можно, например, дописывать их в неизменном, а лучше в произвольном порядке в конце уникальной 27 элементной комбинации. Тем самым гарантируется уникальность общей последовательности за счет 27 элементов  и некоторая псевдослучайность за счет добавления оставшихся элементов в случайном порядке.  
Если же 27 уникальных элемента не повторяются в оставшихся 173-х, то показатели случайности можно улучшить, распределяя в произвольном порядке 173 элемента между  уникальными 27, не меняя при этом очередность 27-ми уникальных.  
 
5. Предположим, что функции заказана комбинация 3 (передан параметр, равный 3-м).  
Функция возвратит 27 уникальных элементов в порядке:  
0000000 0000000000 0000000011  
и допишет в случайном порядке оставшиеся 173 элемента. (см.п.4)  
 
6. Если параметр не передается в функцию, то функция случайным образом формирует индекс в интервале от нуля до 134 217 727 и выдает соответствующую псевдослучайную комбинацию 200 элементов.
 
 
 
#8
30.12.2010 03:45:57
Перечитал внимательнее исходное сообщение, если речь идет об уникальных перестановках с Числом_элементов = 200 и Числом_выбранных_элементов=200, то так не получится.  
 
Не понятно, какого типа элементы - числовые (тип?) или текстовые (длина?), и какой тип результирующей комбинации (текст?).  
 
В общем случае лимит памяти можно обойти, сохраняя результаты в индексированной базе данных (не Excel).  
 
Результат комбинации можно также заменить на 32-битную контрольную сумму (числа Long). При этом, конечно, возможны совпадения контрольных сумм, что обычно не критично, так как маловероятно. Но если критично, то потребуется ещё и доп. учет совпадений.  
 
Контрольные суммы экономичнее хранить в отсортированном массиве.  
Новый элемент добавлять сразу в нужную позицию, раздвигая массив и сдвигая при необходимости элементы справа с помощью API функции копирования области памяти.    
А позиция в массиве заданной контрольной суммы при этом быстро ищется методом дихотомии (другие названия: деления отрезка пополам, бинарный поиск).
 
 
 
#9
30.12.2010 07:43:50
Речь идёт об отказе от проверки уникальности, поскольку алгоритм на каждом новом шаге гарантировано генерит комбинацию ранее не встречавшуюся.  
 
Есть алгоритм перебора(пошаговой генерации) всех перестановок из N элементов  
алгоритм(К) - К-ая уникальная комбинация.  
тогда    
К=1  
for i = 1 to требуемое_число_уник_комб  
M=случайное  
K = K + M  
комбинация(i) = алгоритм(К)  
end for  
 
Но подумав, есть одна проблема как случайно  более или менее равномерно выбрать  
16*10^8 чисел в интервале от 1 до 200! (насколько я понимаю выбрать К=199! +1 затруднительно)
 
 
 
#10
30.12.2010 08:49:23
{quote}{login=ZVI}{date=30.12.2010 02:52}{thema=}{post}  
 
Предлагаю псевдослучайность.  
 
{/post}{/quote}  
 
действительно для 16*10^8 комбинаций    
практически точно будет выполняться отношение  
N(K)/16*10^8=1/200  
где N(K) количество появление i-того элемента на к-том месте    
 
соответственно если вначале мы расставим 1 по 200 местам а потом из оставшихся элементов будем генерить уникальные комбинации то требования к памяти у нас  сразу же упадут в 200 раз  
 
то есть последовательно различным образом раставляя 4 элемента мы получим  
200*199*198*197 = 16*10^8 уникальных комбинаций  
дополняя каждую одной-двумя случайными перестановками из оставшихся элементов получим требуемое количество уникальных близких к случайным перестановок.    
 
2) для того чтобы получить действительно хорошо перемешанные перестановки (вобще говоря это интуитивно точного доказательства не имею)  
можно дополнить его алгоритмом случайного бросания шарика в 200 ящиков предложенным ZVI в теме про случайную комбинацию с заданной суммой  
 
а) два различных шарика бросаем в 200 ящиков 16*10^8 раз (помня что шарики не могут занимать один ящик)  
В результате получаем количество N(K) /K=1...200*199/ встречи комбинации с заданным положением этих двух шариков - K  
б)для каждой заданной перестановки K двух элементов генерим N(K) уникальных перестановок оставшихся элементов используя для проверки уникальности коллекцию.  
После генерации коллекцию очищаем и переходим к К+1 перестановке из двух элементов
 
 
 
#11
30.12.2010 09:04:34
Вероятность того что в 16*10^8 случайных перестановок из 200 элементов втретиться хотя бы две уникальные = 16*10^8/200!=1/196! =0,0000000000000000000000000000000....  
может и не заморачиваться проверкой.....
 
 
 
#12
30.12.2010 10:14:17
низзя :) надо строго
Живи и дай жить..
 
 
 
#13
30.12.2010 10:42:43
цикл датчика случайных чисел vba - 16 777 217
Живи и дай жить..
 
 
 
#14
30.12.2010 11:25:55
разбиваем 200 чисел на группы размером  
11  
13  
17  
19  
23  
29  
31  
37  
15  
5  
для каждой группы записываем цикл - отображение каждой группы на себя  
такое что    
S1 отображается  в S2  
S2 отображается  в S3  
.....  
S(k-1) отображается  в Sk  
Sk отображается  в S1; k размер группы  
В результате получаем перестановку А  
Но полученные элементы можно опять переставить с помощью этой же перестановки A: A*A=A^2  
можно доказать что все полученные перестановки А^k будут уникальны вплоть до    
k=5,03*10^11  
то есть построив одну перестановку  
можно последовательно её применяя получить 5,03*10^11 уникальных, но не случайных (элементы одной группы не меняются с элементами другой группы) перестановок
 
 
 
#15
30.12.2010 12:45:46
Уважаемые господа, всем спасибо за ответы.  
Dl, основная проблема не во времени генерации - с этим особых проблем вроде как нет. Проблема - как лучше хранить полученные комбинации.  
Нужны именно случайные перестановки. Образно говоря, чтобы данный алгоритм мог выдать инф-ю, сколько сгенерировано комбинаций и сколько из них уникальных.  
ZVI, по поводу вида элементов в данном случае это не принципиально (просто все они тоже уникальны) - на начальном этапе мы для работы можем заменить исходные элементы на те, которые нам удобнее для обработки-хранения (в данном случае для оценки, была ли уже комбинация) - а затем результат - одну (или несколько) комбинацию-перестановку представим в виде набора исходных элементов.  
У меня сейчас в рабочей версии элементы представлены в виде string длиной 2. Соотвестсвенно комбинация-перестановка - это тоже string, склеенный из исходных элементов.  
Да кстати, подскажите, пожалуйста, большая ли разница в занимаемой памяти при хранении комбинаций в коллекции и в словаре?  
ZVI, по поводу индексированной БД, может подскажите еще. Я просто рассматривал вариант ACCESS, но прочитал, что там один файл максимально может занимить 2 ГБ, т.е. по сути тоже получаем ограничение по памяти (или надо в данном случае использовать БД с подключением внешних источников-таблиц?).
 
 
 
#16
30.12.2010 13:13:40
да не обязательно access  
 
можно в обыкновенный файл.  
 
суть именно в индексировании - т.е. вы каким-либо способом по своим данным(полученная комбинация) сразу можете определить место в файле(во всяком случае сильно его ограничить) откуда его можно взять. открываете файл в бинарном моде,  
seek, считываете кусок файла, в котором точно содержится нужная информация(если она вообще есть). Далее бинарным поиском в памяти.  
 
а можно сразу взять файл по количеству возможных перестановок..  
 
ну эт я загнул..  :)
Живи и дай жить..
 
 
 
#17
30.12.2010 13:22:29
Разбиваем процесс на два этапа:сначала случайным образом выбираем комбинацию, а уже в комбинации выбираем перестановку. Поясню на маленьком примере.    
Имеем 10 элементов, нужно выбрать перестановку из 4 - общее число 5040 перестановок. При этом число комбинаций всего 210, а перестановок в каждой комбинации 24 (210*24=5040). Из комбинации возможно однозначно получить ее номер простой формулой; из номера также вожможно однозначно получить комбинацию, правда с используя маленький цикл. Массив из перестановок создать не сложно. Таким образом создаем массив Arr(209,23) As Boolean и простой проверкой по индексу элемента на True/False проверяем полученный вариант.  
Имхо, уменьшить объем занимаемой памяти уже не возможно, только если делать промежуточные выгрузки на лист.
 
 
 
#18
30.12.2010 13:24:15
Близкий к теме вопрос:  
если количество генерируемых элементов {x1..xn}в комбинации фиксировано, то является ли условие x1*x2..*xn=s0 признаком  их перестановки. Ноль конечно отбрасываем. Если да ,то на этапе генерации уже можно получить уникальные сочетания.
 
 
 
#19
30.12.2010 15:17:53
{quote}{login=Grin23}{date=30.12.2010 12:45}{thema=}{post}Уважаемые господа, всем спасибо за ответы.  
{/post}{/quote}  
 
Блин спасибо Вам за вопрос!  
На самом деле очень интересный вопрос, заставляющий вспомнить очень многое.  
По большому счёту Вам лучше всего на стадии реализации поможет ZVI.  
Но я думаю на уровне идей не угадаешь кто подскажет лучший вариант.  
Лишь бы у Вас было желание и умение осознать что лучше, и как лучшее использовать ещё лучше!  
 
С новым годом Планету!
 
 
 
#20
30.12.2010 15:19:17
предыдущий пост DL
 
 
 
Страницы: 1
Читают тему
Наверх