Haskell(强大的长)回文检查

Question

我正在努力解决臭名昭着的H-99问题,我正在解决问题#6(找出列表是否是回文).据我所知,大多数解决方案在合理的短名单上都能很好地运作.现在我如何编写一个函数来测试一个很长的列表是否是回文,例如,

let ll = [1..10000000] ++ [10000000, 10000000-1..1] ++ [7]

我(天真或许)试图像这样测试它:

isPalindrome [] = True
isPalindrome [_] = True
isPalindrome [x,y] = x==y
isPalindrome (x:xs) = isPalindrome [x,last xs] && (isPalindrome $ init xs)

我假设,如果isPalindrome [x,last xs]评估False,&&将不会评估昂贵的右侧.

我描述了上面的内容,这是它产生的结果:

Mon Jun 30 18:33 2014 Time and Allocation Profiling Report  (Final)

   h99 +RTS -p -RTS

total time  =        1.29 secs   (1292 ticks @ 1000 us, 1 processor)
total alloc = 2,720,050,200 bytes  (excludes profiling overheads)

COST CENTRE  MODULE  %time %alloc

main         Main     95.6  100.0
isPalindrome Main      4.4    0.0

                                                          individual     inherited
COST CENTRE     MODULE                  no.     entries  %time %alloc   %time %alloc

MAIN            MAIN                     43           0    0.0    0.0   100.0  100.0
 CAF            Main                     85           0    0.0    0.0   100.0  100.0
  main          Main                     86           1   95.6  100.0   100.0  100.0
   isPalindrome Main                     87           2    4.4    0.0     4.4    0.0
 CAF            GHC.Conc.Signal          84           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Encoding          77           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Encoding.Iconv    75           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Handle.FD         68           0    0.0    0.0     0.0    0.0
 CAF            GHC.Show                 63           0    0.0    0.0     0.0    0.0

我从中推断出问题所在last xs,可能需要xs计算整体.如果是这样,有解决方法吗？或者只是执行[a..b]那是贪心的？

谢谢.

Answer 1

正如你猜测的那样,last xs问题是 - 它将在列表的长度上占用线性时间,并强制立即生成整个列表([a..b]是懒惰的,与一般的Haskell列表一样).所以你的isPalindrome函数总共是二次时间.

对于一个天真的实现,我会开始xs == reverse xs,它具有正确的渐近行为(线性)但是相对较高的常数因子,并且最终会在列表reverse末尾的内存中有两个完整的列表副本并开始产生结果.

你可以通过查看length然后在中途分割列表,或者在一次通过中做一些更聪明的事情来改进这种方法.

但是我认为对于更好的行为,你需要切换数据结构 - 我会看一些像Data.Deque或者Data.Sequence.