algorithm - Haskell:库存跨度算法

Question

我正在尝试在 Haskell 中实现“stock span problem”。这是我想出的解决方案。想看看是否有任何其他惯用的方法来做到这一点。这是 O(n^2) 算法 (?) 并使用堆栈，我们可以将其变为 O(n)。任何指向可以使用的其他高阶函数的指针都是值得赞赏的。

import Data.List (inits)

type Quote = Int
type Quotes = [Quote]
type Span = [Int]

stockSpanQuad :: Quotes -> Span
    stockSpanQuad [] = []
    stockSpanQuad xs = map spanQ (map splitfunc  (tail $ inits xs))
      where
          spanQ (qs, q) = 1 + (length $ takeWhile (\a -> a <= q) (reverse qs))
          splitfunc xs = (init xs, last xs)

Answer 1

您提供的链接包含一个使用堆栈数据结构的解决方案。每种语言的示例都会改变堆栈，使用带索引的数组并按索引访问数组的元素。所有这些操作在 Haskell 中都不是很常见。

让我们考虑以下解决方案:

type Quote = Int
type Quotes = [Quote]
type Span = [Int]

stockSpanWithStack :: Quotes -> Span
stockSpanWithStack quotes = calculateSpan quotesWithIndexes []
  where
    quotesWithIndexes = zip quotes [0..]
    calculateSpan [] _ = []
    calculateSpan ((x, index):xs) stack =
      let
        newStack = dropWhile (\(y, _) -> y <= x) stack
        stockValue [] = index + 1
        stockValue ((_, x):_) = index - x
      in
        (stockValue newStack) : (calculateSpan xs ((x, index):newStack))

让我们将它与 Python 解决方案进行比较:

# Calculate span values for rest of the elements
for i in range(1, n):

    # Pop elements from stack whlie stack is not
    # empty and top of stack is smaller than price[i]
    while( len(st) > 0 and price[st[0]] <= price[i]):
        st.pop()

    # If stack becomes empty, then price[i] is greater
    # than all elements on left of it, i.e. price[0],
    # price[1], ..price[i-1]. Else the price[i]  is
    # greater than elements after top of stack
    S[i] = i+1 if len(st) <= 0 else (i - st[0])

    # Push this element to stack
    st.append(i)

对于堆栈解决方案，我们需要带有索引的元素。可以这样模仿:

quotesWithIndexes = zip quotes [0..]

报价列表递归迭代，而不是在每次循环迭代中修改堆栈，我们可以使用修改后的值调用函数:

calculateSpan ((x, index):xs) stack =

Python 中的以下行(弹出堆栈中小于当前值的元素):

while( len(st) > 0 and price[st[0]] <= price[i]):
    st.pop()

可以在 Haskell 中重写为:

newStack = dropWhile (\(y, _) -> y <= x) stack

以及股票值(value)的计算:

S[i] = i+1 if len(st) <= 0 else (i - st[0])

可以解释为:

stockValue [] = index + 1
stockValue ((_, x):_) = index - x

下面说，修改变量的状态并不常见，比如 S[i] = ... 或 st.append(i)。但是我们可以使用新的堆栈值递归调用该函数并将当前结果添加到它之前:

(stockValue newStack) : (calculateSpan xs ((x, index):newStack))

从技术上讲，我们在列表的开头压入并删除列表的第一个元素，因为这是在 Haskell 中使用列表的惯用且性能更高的方式。