在Haskell中解决Google Code Jam的"最小标量产品"

Question

为了准备即将推出的Google Code Jam,我开始研究一些问题.这是我尝试过的一个练习题:

http://code.google.com/codejam/contest/32016/dashboard#s=p0

这是我当前的Haskell解决方案的要点:

{-
- Problem URL: http://code.google.com/codejam/contest/32016/dashboard#s=p0
-
- solve takes as input a list of strings for a particular case
- and returns a string representation of its solution.
-}

import Data.List    

solve :: [String] -> String
solve input = show $ minimum options
    where (l1:l2:l3:_) = input
          n = read l1 :: Int
          v1 = parseVector l2 n
          v2 = parseVector l3 n
          pairs = [(a,b) | a <- permutations v1, b <- permutations v2]
          options = map scalar pairs

parseVector :: String -> Int -> [Int]
parseVector line n = map read $ take n $ (words line) :: [Int]

scalar :: ([Int],[Int]) -> Int
scalar (v1,v2) = sum $ zipWith (*) v1 v2

这适用于提供的示例输入,但在小输入上死于内存不足错误.增加最大堆大小似乎什么都不做,但让它无限期地运行.

我的主要问题是如何优化它,以便它实际上将返回一个解决方案,而不是将-O标志传递给ghc,我已经完成了.

Answer 1

改进算法是最重要的.目前,您可以对两个列表进行置换,并提供总共(n!)^2要检查的选项.您只需要列出其中一个列表.这不仅应该减少时间复杂度,还应该大大减少空间使用.并确保将其minimum替换为严格的最小值(因为它应该优化,因为您采用Ints 的最小列表,编译-ddump-rule-firings并检查"minimumInt").如果不是,请使用foldl1' min而不是最小值.

我刚检查过:

Large dataset

T = 10
100 ? n ? 800
-100000 ? xi, yi ? 100000

为此,您需要一个更好的算法.100!约为9.3*10 ¹⁵⁷,在你检查了100个元素的所有排列的可测量部分之前,宇宙将长期存在.您必须通过查看数据来构建求解排列.为了找出解决方案的样子,研究一些小的输入以及哪些排列实现了那些最小的标量积(看看Cauchy-Bun'akovskiy-Schwarz不等式也不会受到影响).

Answer 2

我想出的解决方案：

{-
- Problem URL: http://code.google.com/codejam/contest/32016/dashboard#s=p0
-
- solve takes as input a list of strings for a particular case
- and returns a string representation of its solution.
-}

import Data.List  

solve :: [String] -> String
solve input = show result
    where (l1:l2:l3:_) = input
          n = read l1 :: Int
          v1 = parseVector l2 n
          v2 = parseVector l3 n
          result = scalar (sort v1) (reverse $ sort v2)

parseVector :: String -> Int -> [Integer]
parseVector line n = map read $ take n $ (words line) :: [Integer]

scalar :: [Integer] -> [Integer] -> Integer
scalar v1 v2 = sum $ zipWith (*) v1 v2 :: Integer

这似乎给出了正确的答案，并且速度快了几个数量级。我猜的诀窍是，在阅读此类问题时，不要只从字面上理解“排列”这个词。