2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Генерирование перестановок и реальность
Сообщение05.10.2014, 16:11 
Аватара пользователя


22/09/09

1907
Алгоритмы генерирования всех $n!$ перестановок $n$-элементного множества приводятся во многих книгах - нпр., Липский, Комбинаторика для программистов. При этом автор отмечает, что за 18 часов даже самая быстрая машина не сможет получить все перестановки для $n=14$. Со времени, как были написаны эти строки, прогресс ВТ ушел далеко вперед. Но каков практически разумный "предел" на сегодня? Кто знает недавние публикации, где бы говорилось, что такой-то суперкомпьютер сгенерировал все перестановки за 18 часов для такого-то $n$? Или что с применением технологии CUDA удалось получить все $n!$ перестановок за 18 дней? Я спрашиваю о реальных кем-то полученных результатах: даже для книги рекордов вряд ли кто будет загружать мощный компьютер или вычислительный кластер 18 месяцев и более - подождать год, и ту же работу можно будет проделать гораздо быстрее на более быстром "железе".

 Профиль  
                  
 
 Re: Генерирование перестановок и реальность
Сообщение05.10.2014, 16:28 
Заслуженный участник
Аватара пользователя


30/01/06
72407
Намного проще взять известную вычислительную сложность генерации перестановок, и поделить её на известные бенчмарки и флопсы.

 Профиль  
                  
 
 Re: Генерирование перестановок и реальность
Сообщение05.10.2014, 18:33 
Аватара пользователя


22/09/09

1907
Munin в сообщении #915326 писал(а):
Намного проще взять известную вычислительную сложность генерации перестановок, и поделить её на известные бенчмарки и флопсы.
О какой сложности речь? О теоретической? - Она факториал от $n$. Было предложено очень много алгоритмов, и их различные реализации сильно отличаются по скорости. Кроме того, не все алгоритмы хорошо распараллеливаются. Некоторые при этом имеют особенности, например, один из возможных практических подходов был опубликован в Известиях Томского политехнического университета, 2004. Там интенсивно используется арифметика многократной точности, что порождает определенные сомнения в его эффективности. К сожалению, сравнения с другими алгоритмами в этой публикации не приводится. Да и с 2004 г. прошло много времени. Возможно, для моей практической задачи и потребуются сравнения, чтобы сделать окончательный выбор, но прежде чем затевать такое исследование, стоит спросить: м.б. кто-то его уже недавно сделал и опубликовал результаты? Зачем без необходимости дублировать уже сделанную работу? (Причем работу немаленькую.) Кроме того, известно, что генерация всех перестановок нужна для ряда практических задач самых разных областей. Если где-то уже используется такая генерация, то появляется практический довод за предполагаемое решение моей задачи: там уже используется, несмотря на немалые затраты машинного времени, а моя задача ничем не хуже, значит, и тут можно использовать аналогичный подход ;-)

 Профиль  
                  
 
 Re: Генерирование перестановок и реальность
Сообщение05.10.2014, 18:48 
Заслуженный участник
Аватара пользователя


30/01/06
72407
Хорошо ещё, что вы не просите публикацию с уже готовыми нагенерированными перестановками...

 Профиль  
                  
 
 Re: Генерирование перестановок и реальность
Сообщение05.10.2014, 19:06 
Аватара пользователя


22/09/09

1907

(Munin)

И массив памяти, чтобы хранить $20!$ перестановок ;-)

 Профиль  
                  
 
 Re: Генерирование перестановок и реальность
Сообщение05.10.2014, 19:42 
Заслуженный участник
Аватара пользователя


30/01/06
72407

(Оффтоп)

На бумаге, в журнале. А то несолидно. А тут рецензент, просмотрит список, может, ошибки заметит...

 Профиль  
                  
 
 Re: Генерирование перестановок и реальность
Сообщение05.10.2014, 22:01 
Аватара пользователя


31/10/08
1244
В принципе ничего не мешает распараллелить перебор на CUDA. Думаю весь перебор уложиться в считанные минуты.

Вот только помимо самого перебора нужно эти данные ещё и обработать, а это тоже надо делать параллельно. Вот только никто не может гарантировать что обработка будет хорошо параллелиться.

 Профиль  
                  
 
 Re: Генерирование перестановок и реальность
Сообщение05.10.2014, 23:20 
Аватара пользователя


22/09/09

1907
Pavia в сообщении #915540 писал(а):
В принципе ничего не мешает распараллелить перебор на CUDA. Думаю весь перебор уложиться в считанные минуты.
Для какого $n$? В сетке много генераторов перестановок на CUDA, но только испытывали их для малых $n$.
Pavia в сообщении #915540 писал(а):
Вот только помимо самого перебора нужно эти данные ещё и обработать, а это тоже надо делать параллельно. Вот только никто не может гарантировать что обработка будет хорошо параллелиться.
В случае моей задачи можно гарантировать. Есть уже простые решения. Потоки работают совершенно независимо, не нужно никаких промежуточных обменов данными. Каждый поток использует любые из всех перестановок (т.е. перестановки, сгенерированные в данном потоке) и выдает компактный результат (вектор размером $<n^2$ с небольшими целочисленными координатами), а потом по завершении всех потоков эти результаты от потоков сравниваются, и выбирается минимальный. Здесь проблем нет.

 Профиль  
                  
 
 Re: Генерирование перестановок и реальность
Сообщение05.10.2014, 23:29 


07/08/14
4231
Вы уверены что нужны прямо все перестановки?
В обработке данных мусорной информации - которую можно было не обрабатывать, много бывает.

 Профиль  
                  
 
 Re: Генерирование перестановок и реальность
Сообщение05.10.2014, 23:54 
Аватара пользователя


22/09/09

1907
upgrade в сообщении #915574 писал(а):
Вы уверены что нужны прямо все перестановки?
К сожалению, уверен. То, что нужны все перестановки - это медицинский математический факт.

 Профиль  
                  
 
 Re: Генерирование перестановок и реальность
Сообщение06.10.2014, 05:31 
Аватара пользователя


31/10/08
1244
bin в сообщении #915568 писал(а):
Для какого $n$? В сетке много генераторов перестановок на CUDA, но только испытывали их для малых $n$.

Для n=15 в лучшем случае 16. Перебор всех перестановок будет менее часа.

Вот только я пока не видел задачи где реально нужны перестановки. перебор долгий, а результат выигрыша менее 1%

 Профиль  
                  
 
 Re: Генерирование перестановок и реальность
Сообщение06.10.2014, 10:39 


10/04/12
706
Задача: цивилизация пермукрейзи обеспокоилось проблемой генерации всех перестановок. Был создан специальный процессор, который генерирует одну перестановку за один такт. При этом была достигнута частота процессора 2 GHz. Каждый процессор имеет 2048 ядер, возможна архитектура Cross-fire из четырех таких процов. Какое число $n$ будет достигнуто пермукрейзи на одном компьютере за день? месяц? год? сто лет? Ответить на эти же вопросы в предположении, что для вычислений будет использован кластер из 1_000_000 компьютеров.

 Профиль  
                  
 
 Re: Генерирование перестановок и реальность
Сообщение06.10.2014, 11:32 


07/08/14
4231
$1$ килобайт данных - это строка из $8 192$ символов $1$ и $0$.
перебор на $1000$ миллиардах $1 000 000 000 $ ГГц процессоров по $1 000 000 000$ переборов за такт займет слишком большое время

 Профиль  
                  
 
 Re: Генерирование перестановок и реальность
Сообщение06.10.2014, 17:47 
Аватара пользователя


22/09/09

1907
Я спрашивал о свежих результатах, полученных на реальных машинах, а не о выдуманных.
Н.Е. Тимошевская из Томского гос. университета в упомянутой статье утверждает:
Цитата:
в задачах проектирования дискретных схем на базе программируемых больших интегральных схем с матричной структурой возникает [подобная] задача
Я не знаком с литературой по проектированию интегральных схем, но подумал, что вдруг здесь кто знаком, и подскажет мне источник с реальными цифрами.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: choocha


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group