如何制作多个数字的倍数排序列表? [英] How to make a sorted list of multiples for several numbers?
问题描述
我在处理Haskell类的作业时遇到了麻烦.我已经解决了此任务的部分问题:我必须编写一个函数,该函数接受一个Int并使用该Int的倍数创建一个无限列表.
I'm having trouble with an assignment from my Haskell class. I have already solved a partial problem of this task: I have to write a function that takes an Int and creates an infinite list with the multiples of that Int.
function :: Int -> [Int]
function d = [d*x | x <- [1..]]
控制台:
ghci> take 10 (function 3)
给予
[3,6,9,12,15,18,21,24,27,30]
在第二个任务中,我必须扩展该函数,以便它接受一个数字列表,并将该列表的每个值用作因子(以前是d).例如:
In the second task I have to extend the function so that it accepts a list of numbers and uses each value of that list as a factor (d previously). For example:
ghci> take 10 (function [3, 5])
应该给
[3,5,6,9,10,12,15,18,20,21]
已经尝试过类似列表理解
Already tried a list comprehension like
function d = [y*x | y <- [1..], x <- d]
但是该函数以未排序的形式返回列表:
but the function returns the list in an unsorted form:
[3,5,6,10,9,15,12,20,15,25]
我们得到了应该使用Haskell的模函数的提示,但是我不知道如何确切地进行操作.你对我有个好建议吗?
We got the tip that we should use the modulo function of Haskell, but I have no real idea how to proceed exactly. Do you have a good tip for me?
推荐答案
我只有一个班轮.
import Data.List (nub)
f xs = nub [x|x<-[1..], d<-xs, x `mod` d == 0]
take 10 $ f [3,5] -- [3,5,6,9,10,12,15,18,20,21]
从结果列表中,
运行时应为O(n²+ n * d). nub 以O(n²)运行.摆脱它会很好.
runtime should be O(n² + n*d) from the resulting list. The nub runs in O(n²). Would be nice to get rid of it.
g xs = [x |x<-[1..], let ys = map (mod x) xs in 0 `elem` ys]
这执行得还不错.它应该以O(n * d)运行.我也有这个版本,我认为它的性能至少和 g 一样好,但是显然它的性能比 f 好,但比 g 差./p>
This performs pretty ok. It should run in O (n*d). I also have this version which I thought performs at least as well as g, but apparently it performs better than f and worse than g.
h xs = [x |x<-[1..], or [x `mod` d == 0 |d<-xs] ]
我不确定为什么或是懒惰的,据我所知,它运行速度较慢的任何原因都没有.当您增加输入列表的长度时,它尤其不能很好地缩放.
I am not sure why that is, or is lazy as far as I can tell and I don`t see any reason why it should run slower. It especially does not scale as well when you increase the length of the input list.
i xs = foldr1 combine [[x, x+x ..] |x<- sort xs]
where
combine l [] = l
combine [] r = r
combine l@(x:xs) r@(y:ys)
| x < y = (x: combine xs r)
| x > y = (y: combine l ys)
| otherwise = (x: combine xs ys)
不再是一个班轮,而是我能想到的最快的班轮.我不能百分百地确定,如果您左右折叠并且事先对输入列表进行排序,为什么它对运行时有如此大的影响?但是,由于以下原因,它不会对结果产生影响:
Not a one liner anymore, but the fastest I could come up with. I am not a hundred percent sure why it makes such a big difference on runtime if you right or left fold and if you sort the input list in advance. But it should not make a difference on the result since:
commutative a b = combine [a] [b] == combine [b] [a]
我认为在将递归函数折叠到输入系数的倍数的无穷列表上时,完全想到这个问题是很疯狂的.
I find it completely insane to think about this Problem in terms of folding a recursive function over a list of endless lists of multiples of input coefficients.
在我的系统上,它仍然比这里使用Data.List.Ordered提供的另一种解决方案慢大约10倍.
On my System it is still about a factor of 10 slower than another solution presented here using Data.List.Ordered.
这篇关于如何制作多个数字的倍数排序列表?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!