- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
public class factorial {
public static void main(String[] args) {
boolean run = true;
long count = 2142;
long last_count=0;
while (run) {
if (ispand(count)) {
if (isprime(count)) {
System.out.println(count);
last_count=count;
}
}
if((count+"").length()>7){
System.out.println("Largest prime can be :"+last_count);
System.exit(1);
}
count++;
}
}
public static boolean ispand(long num) {
String text = num + "";
for (int i = 1; i <= text.length(); i++) {
if (!text.contains(i + "")) {
return false;
}
}
return true;
}
public static boolean isprime(long num) {
if (num == 1) {
return false;
} else {
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
}
return true;
}
}
Follow us!
Работает миллисекунды даже в ghci... Что тут делать 2 секунды - я не знаю :)
>reverse $ sort $ map makeNumber $ permutations [1..7]
Не хочу злорадствовать, но наверняка reverse $ sort тяжелые операции и от этого никакая ленивость и AsParallel не спасёт.
В моём варианте достаточно, как Вы уже указали ранее, взять первое значение.
Ну а так, согласен, sort тут лишний, достаточно сделать правильный permutations (стандартный выдает их в каком-попало порядке).
sum $ map makeNumber $ sort $ permutations [1..10]
22.91с, 4.6Гб
sum $ map makeNumber $ ordPermutations [1..10]
5.88c, 5.2Гб
Хуясе! Это используемая память?! Та нахуй он тогда нужен этот Хацкель.
У меня даже жаба n=11 на приведенном мною алгоритме:
2.5с, память - неощутимо (пару метров).
Притом что по объему кода примерный паритет теплая ламповая императивщина заруливает ваши функцианалы в глубокий минус.
Байтоитоебы снова побеждают.
Предсказуемо.
> меньше пары метров для ленивой версии.
А, ясно. Меня несколько шокировали цифры.
Всё-равно n=10 у меня за 100мс. Агрумент о том что списки произвольной длины, а int всего 32 бита не катит, потому что уже на 20! железо просто помрет.
есть еще stream fusion - соединяет list-produces и consumer в одну ф-ию, будет сравнимо с С.
Ну и всегда (когда списки только как промежуточные) можно в рекурсивном виде записать, только очень некрасиво получится.
Но вот одна действительно хорошая оптимизация - нахождение наибольшего неиспользуемого символа (позиция первого нулевого бита), чтобы сократить кол-во итераций.
Тут можно либо битовую магию применить, либо юзать заранее просчитанные таблицы.
10 бит - 1024 состояния, не так уж много. В L1 запросто влезет. Тогда вплотную подходим к O(n!)
Сравните, например, main = print $ length (permutations [1..11]) для двух вариантов.
Хотя, возможно, их нельзя сравнивать напрямую - т.к. они решают немного разные задачи - permutations генерит перестановки в произвольном порядке, а ordPermutations в строго заданном.
P.S. попробую придумать версию пооптимальней.
Пожалуй, главное чтоб коэффициент не вы рос быстрее, чем n*log n (оверхед sort). Вроде не выходит.
Сборщик мусора очень рад Хацкелу.
http://ideone.com/IByI4
Проверятся как быстро создается список, length считает длину, посчитанное сразу в мусор. (оригинальный был 25% на [1..9], при больших - меньше)
Поясните, пожалуйста, почему он должен работать на порядок дольше?
P.S. В контексте задачи про pandigital primes он явно быстрее прошлой версии с reverse + sort + permutations т.к. ленив и не генерирует лишних перестановок, после того как будет найдено первое решение.
Раз написали так, значит, нужно сравнить с permutations в целом, а не в контексте данной задачи.
Для _данной_ задачи ваш вариант подходит, но в ответе 765 впереди, из 7! остается 24 варианта -- можно писать абы как, лишь бы лениво.
Это n! итераций.
В рекурсивном способе, чтобы не было дубликатов, нужно либо проверять использовалось/не использовалось как это сделал я, либо удалять из списка (порождением нового).
В любом случае думаю где-то в районе n^n проверок (итераций).
(Забыл, что еще оригинальный permutations может быть хуже n! - swap на списках затруднен).
А в треде - неоптимальное говно, ибо я вчера писал первое что пришло в голову.
>swap на списках затруднен
Не гораздо трудней, чем удалить из него один элемент :)
Как я и думал. Базовый Swap и иногда Reverse подсписка.
PS> Тестьте!
http://rosettacode.org/wiki/Sorting_algorithms/Permutation_sort#Haskell
Неупорядоченный :(
Попробую реализовать алгоритм из вики.
сырой код, абы как:
корректность проверял так:
take 120 (iterate next [5,4..1]) == map reverse (sort $ permutations [1,2,3,4,5])
на [1..10] быстрее, чем у [color=blue]bormand[/blue] main = print $ length (ordPermutations [1..10])
А вот какой вывод сделать не знаю: не уверен, что смогу оценить сложность изкоробочного permutations.
1. swap-версия с апплета (по сути, то что я предлагал тут: http://govnokod.ru/10361#comment139237)
Аналог вот этого http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_ order
2. оптимизированная вариация 3-го пункта (с массивом позиций младшего нулевого бита)
3. первоначальная версия с битами на быструю руку
n=12
1. 4313ms
2. 10500ms
3. 30391ms
n=11
1. 734ms
2. 875ms
3. 2359ms
n=10
1. 31ms
2. 78ms
3. 203ms
Разница между 1 и 2 ~ 2.5 раза. Но на N=11 - странный результат, запускал трижды - повторяется.
PS.Что интересно версия с Integer[] m_Val работает в два раза медленней, чем примитивные типы: new int[m_Max];
Вот вам и автобоксинг.
1. 734ms
А сегодня запустил:
1. 360ms
Теперь всё стало на места, смотрите, в обоих методах зависимость от n! линейная:
10500ms/875ms=12 (ровно!)
875ms/78ms=11.2
4313ms/360ms=11.99
360/31=11.6
Хм.. n! + цена сортировки n! (log n!) должны сверху ограничивать оценки сортированных перестановок.
O(n! n (log n)), n (log n) - верхняя оценка коэф. разницы.
Да. Это я загнул.
Посчитал кол-во итераций с своем алгоритме ~ 2*(n-1)*n!
Всё потому что это не таки тупой брутфорс n^n и скип ненужных веток присутствует:
if ((mask & 1<<j)==0);
http://ideone.com/NJpzU
время: 0.09s
Built-in Function: int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
На интеле она должна выполняться за 1 машинную команду. Жаль, что этой функции нет в стандарте.
В любом случае как еще улучшать алгоритмически я не знаю.
И выходит рвет даже haskell unordered permutations.
Ну это в пределе при n->∞
Кстати через разложение e в сумму обратных факториалов как раз и доказывают, что оно иррациональное.
Вот, чтоб было понятней что я ниже написал - пикча e^x в ряд Тейлора.
http://upload.wikimedia.org/wikipedia/ru/math/f/5/5/f551e394956f5458a059c2b041a4fbfb.png
при x=1
Да, Вы абсолютно правы. Просто я тогда чето затупил, и подумал на ln(n), вместо e.
Я думал и пришел к такой же формуле независимо.
>равно n!*e-1
Именно! Но это n!*e предел при n->∞.
При n=0 и n->∞ Сумма(1/n!) -> e
Q.E.D
c = a - ((a >> 1) & 0x55555555);
c = ((c >> 2) & 0x33333333) + (c & 0x33333333);
c = ((c >> 4) + c) & 0x0F0F0F0F;
c = ((c >> 8) + c) & 0x00FF00FF;
неизбежен.
filter чем не устроил?
>т.к. все остальные делятся на 3
Вот это не понял.
Если мы берем все 10 цифр - то их сумма будет 45, она делится на 3 => по признаку делимости на 3 все эти числа делятся на 3. По тому же принципу отлетают все диапазоны кроме 1..7 и 1..4.
>все 10 цифр
=)
Что при n=10 составляет 9864100
Если считать вырожденный случай в виде всех значений деревом, то можно обойтись и n!
Формально это тоже префиксное дерево, но с глубиной 2.
Но Вы же сами пишете, что дерево - "префиксное".
Зы. транслит.ру посчитал, что правильно писать "пощитал" :)
Тогда квадрат 9 на 9 :)
Но это, по определению, не префиксное дерево.
>пощитал
Тоже так иногда пейшу.
10 ведь минимально достаточно.
> это ориентированный граф
Циклов нет, значит дерево. Но требование префиксности, как уже отмечал, не выполняется.
Если в средних слоях брать по 10 - то получим лишние пути, которые не являются перестановками.
> Циклов нет, значит дерево. Но требование префиксности, как уже отмечал, не выполняется.
Да, согласен, это не префиксное дерево.
Если сгруппировать эти узлы по множеству чисел, входящих в пути к ним, то получим C(10,5) = 252 группы по 5! = 120 узлов.
К каждой группе мы прицепляем оставшиеся 5! = 120 суффиксов.
В применении к генерации перестановок - получается, что нужно сгенерить C(10,5) подмножеств. А затем для каждого из них сгенерить по 5! перестановок элементов подмножества, и 5! перестановок оставшихся элементов и взять их декартово произведение.
Как-то так.
В комментах к коду написано что это менее эффективная версия L-алгоритма из книги Кнута.
n: 9 10 11
fasc2B_algorithm_L: 0.124с 1.27с 14.757с
permutations: 0.03с 0.20с 1.938с
мой тупой однострочник: 0.29с 3.13с 35.639с
К сожалению, результаты L-алгоритма отличаются от моего в константное число раз (2.4). Поэтому рискну предположить, что в языке с иммутабельными данными понизить сложность алгоритма уже не получится, только выиграть в константе.
Результаты теста на print $ length:
n: 9 10 11 12
permutations: 0.03 0.20 1.938 22.329
новый генератор: 0.02 0.358 2.485 15.371
К сожалению пример с вычислением длины для этого генератора совсем не показателен.
n: 9 10 11
permutations: 0.151 2.077 30.32
perms: 0.21 2.8666 34.08
Определенно, ленивость надо обходить, хотел заметить, но вы сами написали.
BTW, вы смотрели http://govnokod.ru/10361#comment139267 ?
Потом форсировал через (sum . map sum) вроде быстрее оригинального (по идее еще неплохо было бы вычитать из всех время для такого генератора: replicate (product [1..length xs]) xs)
Для n=9
Ваш вариант - 0.09с (1.2% GC)
perms - 0.15с (49% GC)
replicate - 0.01с (3.3% GC)
Для n=10
Ваш вариант - 0.94с (1.1% GC)
perms - 1.41с (45% GC)
replicate - 0.06с (1.7% GC)
Для n=11
Ваш вариант - 11.43с (1.0% GC)
perms - 11.23с (15% GC)
replicate - 1.28с (1.1% GC)
Странно, но при росте n perms начинает догонять ваш вариант. Жаль, что для 12 ждать уже слишком долго.
Все-таки ваш первый вариант по соотношению кол-во кода / производительность неплох, и его легко можно улучшить раз в два: http://haskell.1045720.n5.nabble.com/String-permutation-td3190999.html (последний пост)
Ага, согласен, производительность на хаскеле хрен измеришь. То GC вмешается, то поленится раскрыть что-то, то фаза луны не та...
>Все-таки ваш первый вариант по соотношению кол-во кода / производительность неплох, и его легко можно улучшить раз в два
Ага, их вариант selections интересный и краткий.
"генератор"-"то, что форсирует"-"длина списка", для ordPermutations опустил n=9
ваш perms обозвал subs, dumb - то что предлагал выше вычитать.
Можно делить sum на n! / n! n / n! (log n0) / n! n (log n) и смотреть графики: что больше на прямую похоже. Но как то уже лень), да и выборка маловата.
Я об таком думал, но только как бы еще закешировать маленькие перестановки.
Это что же получается. Новый сортированный генератор работает быстрее родного в Хацкеле, да еще и несортированного.
Проверьте, пожалуйста, на своей машине мой первый вариант на С:
>http://www.govnokod.ru/10361#comment139219
У меня сопоставимые цифры - 2-3 секунды при n=11.
$ g++ -O2 1.cpp
$ time ./a.out
39916800
real 0m2.933s
user 0m2.932s
sys 0m0.000s