Новое состояние в неограниченном поколении последовательности Хемминга
(это захватывающе!) Я знаю, предмет хорошо известен. Уровень техники (как на Хаскеле, так и на других языках) для эффективной генерации неограниченной возрастающей последовательности чисел Хэмминга, без дубликатов и без пропусков, долгое время был следующим (AFAIK - и, кстати, он эквивалентен оригинальному коду Эдсгера Дейкстры. тоже):
hamm :: [Integer]
hamm = 1 : map (2*) hamm `union` map (3*) hamm `union` map (5*) hamm
where
union a@(x:xs) b@(y:ys) = case compare x y of
LT -> x : union xs b
EQ -> x : union xs ys
GT -> y : union a ys
Вопрос, который я задаю, заключается в том, можете ли вы найти способ сделать его более эффективным в какой-либо значительной мере? Это все еще современное состояние или действительно возможно улучшить его, чтобы он работал в два раза быстрее и с лучшими эмпирическими порядками роста?
Если ваш ответ " да", пожалуйста, покажите код и обсудите его скорость и эмпирические порядки роста по сравнению с вышеупомянутым (он работает примерно с ~ n^1.05 .. n^1.10 за первые несколько сотен тысяч произведенных номеров). Кроме того, если он существует, может ли этот эффективный алгоритм быть расширен до получения последовательности гладких чисел с любым заданным набором простых чисел?
4 ответа
Если постоянное ускорение(1) считается значительным, я могу предложить значительно более эффективную версию:
hamm :: [Integer]
hamm = mrg1 hamm3 (map (2*) hamm)
where
hamm5 = iterate (5*) 1
hamm3 = mrg1 hamm5 (map (3*) hamm3)
merge a@(x:xs) b@(y:ys)
| x < y = x : merge xs b
| otherwise = y : merge a ys
mrg1 (x:xs) ys = x : merge xs ys
Вы можете легко обобщить это, чтобы сгладить числа для данного набора простых чисел:
hamm :: [Integer] -> [Integer]
hamm [] = [1]
hamm [p] = iterate (p*) 1
hamm ps = foldl' next (iterate (q*) 1) qs
where
(q:qs) = sortBy (flip compare) ps
next prev m = let res = mrg1 prev (map (m*) res) in res
merge a@(x:xs) b@(y:ys)
| x < y = x : merge xs b
| otherwise = y : merge a ys
mrg1 (x:xs) ys = x : merge xs ys
Он более эффективен, потому что этот алгоритм не создает дубликатов и использует меньше памяти. В вашей версии, когда число Хемминга рядом h производится часть списка между h/5 а также h должно быть в памяти. В моей версии только часть между h/2 а также h полного списка, и часть между h/3 а также h из 3-5 списков должен быть в памяти. Поскольку 3-5-список намного более разреженный, а плотность k-гладких чисел уменьшается, этим двум частям списка требуется гораздо меньше памяти, чем большей части полного списка.
Некоторые моменты времени для двух алгоритмов для создания kth число Хэмминга, с эмпирической сложностью каждой цели относительно предыдущей, исключая и включая время GC:
k Yours (MUT/GC) Mine (MUT/GC)
10^5 0.03/0.01 0.01/0.01 -- too short to say much, really
2*10^5 0.07/0.02 0.02/0.01
5*10^5 0.17/0.06 0.968 1.024 0.06/0.04 1.199 1.314
10^6 0.36/0.13 1.082 1.091 0.11/0.10 0.874 1.070
2*10^6 0.77/0.27 1.097 1.086 0.21/0.21 0.933 1.000
5*10^6 1.96/0.71 1.020 1.029 0.55/0.59 1.051 1.090
10^7 4.05/1.45 1.047 1.043 1.14/1.25 1.052 1.068
2*10^7 8.73/2.99 1.108 1.091 2.31/2.65 1.019 1.053
5*10^7 21.53/7.83 0.985 1.002 6.01/7.05 1.044 1.057
10^8 45.83/16.79 1.090 1.093 12.42/15.26 1.047 1.084
Как видите, коэффициент между временем MUT составляет около 3,5, но время GC не сильно отличается.
(1) Ну, это выглядит постоянным, и я думаю, что оба варианта имеют одинаковую вычислительную сложность, но я не вытащил карандаш и бумагу, чтобы доказать это, и не собираюсь этого делать.
В общем, теперь, когда Даниэль Фишер дал свой ответ, я могу сказать, что я столкнулся с этим недавно, и я думаю, что это захватывающее развитие, поскольку классический код был известен целую вечность, начиная с Дейкстры.
Даниэль правильно определил избыточность поколения дубликатов, которые затем должны быть удалены, в классическом варианте.
Счета за оригинальное открытие (AFAIK) переходит к участнику Rosettacode.org Ledrug, по состоянию на 2012-08-26. И, конечно же, независимое открытие Даниэля Фишера здесь (2012-09-18).
Немного переписан, этот код:
import Data.Function (fix)
hamm = 1 : foldr (\n s -> fix (merge s . (n:) . map (n*))) [] [2,3,5]
с обычной реализацией слияния,
merge a@(x:xs) b@(y:ys) | x < y = x : merge xs b
| otherwise = y : merge a ys
merge [] b = b
merge a [] = a
Это дает примерно 2.0x - 2.5x a ускорение по сравнению с классической версией.
Ну, это было проще, чем я думал. Это сделает 1000 Хеммингов за 0,05 секунды на моем медленном ПК дома. Этим днем на работе, и более быстрые времена ПК менее чем 600 выходили как ноль секунд.
Это взять Хеммингс из Хеммингс. Это основано на том, чтобы делать это быстрее всего в Excel.
Я получал неправильные номера после 250000, с Int, Числа очень быстро растут, поэтому Integer должен быть использован, чтобы быть уверенным, потому что Int ограничен.
mkHamm :: [Integer] -> [Integer] -> [Integer] -> [Integer]
-> Int -> (Integer, [Int])
mkHamm ml (x:xs) (y:ys) (z:zs) n =
if n <= 1
then (last ml, map length [(x:xs), (y:ys), (z:zs)])
else mkHamm (ml++[m]) as bs cs (n-1)
where
m = minimum [x,y,z]
as = if x == m then xs ++ [m*2] else (x:xs) ++ [m*2]
bs = if y == m then ys ++ [m*3] else (y:ys) ++ [m*3]
cs = if z == m then zs ++ [m*5] else (z:zs) ++ [m*5]
Тестирование,
> mkHamm [1] [2] [3] [5] 5000
(50837316566580,[306,479,692]) -- (0.41 secs)
> mkHamm [1] [2] [3] [5] 10000
(288325195312500000,[488,767,1109]) -- (1.79 secs)
> logBase 2 (1.79/0.41) -- log of times ratio =
2.1262637726461726 -- empirical order of growth
> map (logBase 2) [488/306, 767/479, 1109/692] :: [Float]
[0.6733495, 0.6792009, 0.68041545] -- leftovers sizes ratios
Это означает, что эмпирический порядок роста этого кода времени выполнения выше квадратичного (~n^2.13 как измерено, интерпретировано, по подсказке GHCi).
Кроме того, размеры трех свисающих перепроизводимых сегментов последовательности каждый ~n^0.67 т.е. ~n^(2/3),
Кроме того, этот код не ленив: доступ к первому элементу результирующей последовательности возможен только после вычисления самого последнего.
Код уровня техники в вопросе является линейным, перепроизводит ровно 0 элементов после интересующей точки и, по сути, ленив: он сразу начинает создавать свои числа.
Таким образом, хотя это значительное улучшение по сравнению с предыдущими ответами этого автора, оно все же значительно хуже, чем оригинал, не говоря уже о его улучшении, как в двух верхних ответах.
12.31.2018
Только самые лучшие люди обучают. @Will Ness также является автором или соавтором 19 глав на GoalKicker.com "Haskell for Professionals". Бесплатная книга - это сокровище.
Я перенес идею о функции, которая будет делать это, как это. Я был напуган, потому что думал, что это будет запутанно и связано с логикой, как в некоторых современных языках. Я решил начать писать и был поражен тем, насколько легко Хаскелл делает реализацию даже плохих идей.
У меня не было трудностей при создании уникальных списков. Моя проблема в том, что списки, которые я создаю, плохо заканчиваются. Даже когда я использую диагонализацию, они оставляют остаточные значения, что делает их использование ненадежным в лучшем случае.
Вот переработанный список 3-х и 5-х без остатка в конце. Диагонализация заключается в уменьшении остаточных значений, а не в устранении дубликатов, которые никогда не включаются.
g3s5s n=[t*b|(a,b)<-[ (((d+n)-(d*2)), 5^d) | d <- [0..n]],
t <-[ 3^e | e <- [0..a+8]],
(t*b)<=(3^(n+6))+a]
ham2 n = take n $ ham2' (drop 1.sort.g3s5s $ 48) [1]
ham2' o@(f:fo) e@(h:hx) = if h == min h f
then h:ham2' o (hx ++ [h*2])
else f:ham2' fo ( e ++ [f*2])
twos список может быть создан со всеми 2^e умножается на каждый из 3s5s но когда личность 2^0 включается, то, в общем, это Хэммингс.
Ну, я не смог опубликовать свой последний ответ на подобный вопрос, потому что он был помечен как дубликат из-за этого вопроса.
Итак, теперь, к этому вопросу. Я все еще думаю, что лучше всего пересечь и упорядочить сет, чтобы не приходилось компенсировать нет.
Я нашел свой no2s3s5s функция полезна для этого тоже. Смешно что no2s3s5s начинается с 11. no2s3s5s просто рассчитывает определенным образом.
Это `no2s3s5s'
no2s3s5s = scanl (\b a -> a + b) 11 $ cycle [2,4,2,4,6,2,6,4]
Это производит главным образом простые числа, с 11 до 97 есть только 49,77 и 91, которые не просты, страшные 7s. Используется в hamseq вместо простых чисел. Виноват.
hamseq n = [ b | b <- [1..n], all (>0) [mod b f | f <- take (div b 2) (7:no2s3s5s)]]
hamseq 729
производит [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50, 54,60,64,72,75,80,81,90,96,100,108,120,125,128,135,144,150,160,162,180,192,200,216,225,240,243,250,256,270,288,300,320,324,360,375,384,400,405,432,450,480,486,500,512,540,576,600,625,640,648,675,720,729]
@ Уилл Несс, я в буквальном смысле слова. Я никогда не думал о создании этого списка с параметром 77. Мой плохой.
Но здесь
hamseq n = take n $ [ b | b <- [1..], all (>0) [mod b f | f <- take (div b 2) (7:no2s3s5s)]]
Вопрос здесь Как найти список всех чисел, кратных только степеням 2, 3 и 5? the-list-of-all-numbers-that-are-multiples-of-only-powers-of-2 Тогда, я теперь не уверен, что вопрос, помеченный как дубликаты, нуждается в полномочиях или кратных числах. Я путаю способ легко.
Взятие чисел непосредственно из целых чисел исключает сортировку и объединение. Взяв дельты из списка кратных 2,3 и 5, для первых нескольких сотен вы заметите, что шаблон дельт повторяется каждые (22 из) 30. Вы можете использовать этот шаблон в scanl и cycle шаблона.
take 77 $ scanl (\b a -> a+b) 2 $ cycle [1,1,1,1,2,1,1,2,2,1,1,2,2,1,1,2,1,1,1,1,2,2]
Это создает этот список [2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30,32,33,34,35,36,38,39,40,42,44,45,46,48,50,51,52,54,55,56,57,58,60,62,63,64,65,66,68,69,70,72,74,75,76,78,80,81,82,84,85,86,87,88,90,92,93,94,95,96,98,99,100,102,104,105]
Я использую инверсию этого списка, который использует гораздо более короткий шаблон, потому что там очень мало простых чисел.
@ Уилл Несс Я обнаружил, что каждый новый номер кандидата на статус Хэмминга, который может быть равномерно разделен любым из [2,3,5], имеет частное в списке построенных чисел Хэмминга. Это исключает mergeи unionING. Он не использует кратные или другие факторы. Он использует только сгенерированный список Хэмминга. Но это все еще не быстро.
Я разместил это на CodeReview, и Макс Талдыкин показал мне, как Data.Set функции намного быстрее, чем elem но все еще нет, где рядом с линейной, как указано выше.
Я проанализировал 2,3,5 кратного списка Хэмминга. Если вы возьмете все 2-х кратные и все нечетные мультипликаторы 3-х, единственное, что останется из 5-ти, которые не являются дубликатами, это, например, отношение 15 в 6,103,515,625, которое может быть рекурсивно вычислено с базовым регистром 1 и умножьте предыдущее значение на 5 для следующего значения.
Первый параметр - это список чисел Хэмминга, меньший 10, второй параметр - это базовый список, из которого можно нарисовать числа кандидатов. Логика будет работать в foldl что тоже медленно. Создание обратного списка сокращает время поиска, поскольку кандидат Хэмминга находится в конце списка, который необходимо добавить, если его частное находится в списке.
-- foldl (\b a -> let d = divm a [2,3,5] in if elem d b then b++[a] else b) [1,2,3,4,5,6,8,9] [10..n]
hamx ls (x:xs)
| even x && elem (div x 2) ls = hamx (x:ls) xs
| mod x 3 == 0 && elem (div x 3) ls = hamx (x:ls) xs
| mod x 5 == 0 && elem (div x 5) ls = hamx (x:ls) xs
| null xs = ls
| otherwise = hamx ls xs