我是一位Haskell初学者,试图通过解决一些在线测验/问题集来学习更多有关该语言的知识。问题/问题相当冗长,但是其中一部分需要代码才能找到将给定列表分为两个(几乎)相等(按和)子列表的数字。给定[1..10]答案应为7,因为1+2+..7 = 28&8+9+10 = 27这就是我实现它的方式-- partitions list by ypartishner :: (Floating a) => Int -> [a] -> [[[a]]]partishner 0 xs = [[xs],[]]partishner y xs = [take y xs : [drop y xs]] ++ partishner (y - 1) xs-- finds the equal sumfindTheEquilizer :: (Ord a, Floating a) => [a] -> [[a]]findTheEquilizer xs = fst $ minimumBy (comparing snd) zipParty where party = (tail . init) (partishner (length xs) xs) -- removes [xs,[]] types afterParty = (map (\[x, y] -> (x - y) ** 2) . init . map (map sum)) party zipParty = zip party afterParty -- zips partitions and squared diff betn their sums给定(last . head) (findTheEquilizer [1..10])输出:7对于50k附近的数字,效果很好λ> (last . head) (findTheEquilizer [1..10000]) 7071.0当我放入列表中包含70k个元素的列表时,麻烦就开始了。计算需要永远。那么,我必须在代码中进行哪些更改以使其更好地运行,还是必须更改整个方法?我猜是晚了,但是我不确定该怎么做。 最佳答案 在我看来,实现非常混乱。例如,partishner似乎构造了一个a列表列表,其中,据我所知,这里的外部列表包含具有两个元素的列表:“左侧”元素列表和该列表在“右边”的元素。结果,这将花费O(n2)来构造列表。通过使用超过2个元组的列表,这也是“不安全的”,因为列表可以(尽管在这里可能是不可能的)不包含任何元素,一个元素或两个以上元素。如果您在其中一个功能中犯了错误,将很难找出该错误。在我看来,实现“扫描算法”可能会更容易:我们首先计算列表中所有元素的总和。如果我们决定在该特定点进行分割,则这是“右侧”的值,接下来我们开始从左向右移动,每次从右侧的总和中减去该元素,然后将其添加到左侧的总和中。我们可以每次评估分数的差异,例如:import Data.List(unfoldr)sweep :: Num a => [a] -> [(Int, a, [a])]sweep lst = x0 : unfoldr f x0 where x0 = (0, sum lst, lst) f (_, _, []) = Nothing f (i, r, (x: xs)) = Just (l, l) where l = (i+1, r-2*x, xs)例如:Prelude Data.List> sweep [1,4,2,5][(0,12,[1,4,2,5]),(1,10,[4,2,5]),(2,2,[2,5]),(3,-2,[5]),(4,-12,[])]因此,如果我们选择在第一个分割点处分割(在第一个元素之前),则右边的总和要比左边的总和12高;如果我们选择在第一个元素之后的分割,则是右边的总和()比左侧的总和(11)高10。然后,我们可以使用1获得这些拆分中的最小值:import Data.List(minimumBy)import Data.Ord(comparing)findTheEquilizer :: (Ord a, Num a) => [a] -> ([a], [a])findTheEquilizer lst = (take idx lst, tl) where (idx, _, tl) = minimumBy (comparing (abs . \(_, x, _) -> x)) (sweep lst)然后,我们获得minimumBy :: (a -> a -> Ordering) -> [a] -> a的正确值:Prelude Data.List Data.Ord Data.List> findTheEquilizer [1..10]([1,2,3,4,5,6,7],[8,9,10])或7万:Prelude Data.List Data.Ord Data.List> head (snd (findTheEquilizer [1..70000]))49498上面的方法并不理想,可以更优雅地实现,但我将其保留为练习。关于list - Haskell-将列表分成两个具有最接近总和的子列表,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/53191190/
10-09 20:27
查看更多