Генерирование перестановок и реальность

[bin]

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

[Munin]

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

[bin]

Munin в сообщении #915326 писал(а):

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

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

[Munin]

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

[bin]

(Munin)

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

[Munin]

(Оффтоп)

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

[Pavia]

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

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

[bin]

Pavia в сообщении #915540 писал(а):

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

Для какого $n$? В сетке много генераторов перестановок на CUDA, но только испытывали их для малых $n$.

Pavia в сообщении #915540 писал(а):

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

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

[upgrade]

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

[bin]

upgrade в сообщении #915574 писал(а):

Вы уверены что нужны прямо все перестановки?

К сожалению, уверен. То, что нужны все перестановки - это медицинский математический факт.

[Pavia]

bin в сообщении #915568 писал(а):

Для какого $n$? В сетке много генераторов перестановок на CUDA, но только испытывали их для малых $n$.

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

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

[mustitz]

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

[upgrade]

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

[bin]

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

Цитата:

в задачах проектирования дискретных схем на базе программируемых больших интегральных схем с матричной структурой возникает [подобная] задача

Я не знаком с литературой по проектированию интегральных схем, но подумал, что вдруг здесь кто знаком, и подскажет мне источник с реальными цифрами.