代码之家 › 专栏 › 技术社区 › stack0114106

scala-foldLeft用序列号填充连续的零间隙

functional-programming scala

stack0114106 · 技术社区 · 6 年前

我有一个左折叠的特殊箱子

scala> val nums = List(1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1)
nums: List[Int] = List(1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1)

我需要通过用序列号(即2、3、4)填充连续零来获得输出。

所需输出:

List(1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 5, 1, 1)

我实际上需要把它应用到一个列表中[(string,int)]

从

List(("a",1),("b",1),("b",0),("a",1),("a",0),("a",0),("d",1),("d",0),("d",0),("c",1),("c",0), ("c",0), ("c",0), ("c",0), ("d",1), ("a",1))

至所需输出

List(("a",1),("b",1),("b",2),("a",1),("a",2),("a",3),("d",1),("d",2),("d",3),("c",1),("c",2), ("c",3), ("c",4), ("c",5), ("d",1), ("a",1))

我正在尝试下面的列表[int],但出现了错误

scala> nums.foldLeft(List[Int]())( (m:List[Int],n:Int) => { val p = if(n==0) m.last+1 else n; m.++ List(p) })
<console>:26: error: missing argument list for method ++ in class List
Unapplied methods are only converted to functions when a function type is expected.
You can make this conversion explicit by writing `$plus$plus _` or `$plus$plus(_)(_)` instead of `$plus$plus`.
       nums.foldLeft(List[Int]())( (m:List[Int],n:Int) => { val p = if(n==0) m.last+1 else n; m.++ List(p) })
                                                                                                ^

scala>

如何解决这个问题并将逻辑应用于list[(string,int])?.

3 回复 | 直到 6 年前

Markus Appel 6 年前

m.++ List(p) 不是有效的scala语法。应该是 m ++ List(p) .

但是你也可以用接线员 :+ .

示例(仅包括两者 Int 和 (String, Int) ):

val stringsAndNums = List(
  ("a",1),("b",1),("b",0),("a",1),("a",0),("a",0),("d",1),("d",0),("d",0),("c",1),("c",0), ("c",0), ("c",0), ("c",0), ("d",1), ("a",1)
)

// Without strings

val nums = stringsAndNums.map{case (a: String, b: Int) => b} 

println(
  nums.foldLeft(
    List[Int]()
  )(
    (m: List[Int], n: Int) => {

      val p = if(n == 0) m.last + 1 else n

      m :+ p
    }
  )
)

// With strings

println(
  stringsAndNums.foldLeft(
    List[(String, Int)]()
  )(
    (m: List[(String, Int)], n: (String, Int)) => {

      val p = if(n._2 == 0) (n._1, m.last._2 + 1) else n

      m :+ p
    }
  )
)

结果:

List(1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 5, 1, 1)
List((a,1), (b,1), (b,2), (a,1), (a,2), (a,3), (d,1), (d,2), (d,3), (c,1), (c,2), (c,3), (c,4), (c,5), (d,1), (a,1))

Try it out!

Eastsun 6 年前

实际上,方法 scanLeft 比 foldLeft 对于这个问题。这里是:

为了 List[Int] :

scala> val nums = List(1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1)
nums: List[Int] = List(1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1)

scala> nums.scanLeft(0){ (r, n) => if(n == 0) r + 1 else n }.tail
res1: List[Int] = List(1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 5, 1, 1)

为了 List[(String Int)] :

scala> val xs = List(("a",1),("b",1),("b",0),("a",1),("a",0),("a",0),("d",1),("d",0),("d",0),("c",1),("c",0), ("c",0), ("c",0), ("c",0), ("d",1), ("a",1))
xs: List[(String, Int)] = List((a,1), (b,1), (b,0), (a,1), (a,0), (a,0), (d,1), (d,0), (d,0), (c,1), (c,0), (c,0), (c,0), (c,0), (d,1), (a,1))

scala> xs.scanLeft(("", 0)){ case((_, r), (c, n)) => (c, if(n == 0) r+1 else n) }.tail
res2: List[(String, Int)] = List((a,1), (b,1), (b,2), (a,1), (a,2), (a,3), (d,1), (d,2), (d,3), (c,1), (c,2), (c,3), (c,4), (c,5), (d,1), (a,1))

如果第一个数字为零,这个解决方案甚至可以工作,@markus appel的解决方案在这种情况下也不能工作。

Tom 6 年前

请注意 slow 版本是 O(n^2) 由于对 .last (即 O(n) 名单上)

def slow(list: List[(String, Int)]): List[(String, Int)] =
  list.foldLeft(List[(String, Int)]()) {
    (m: List[(String, Int)], n: (String, Int)) => {
      val p = if (n._2 == 0) (n._1, m.last._2 + 1) else n
      m :+ p
    }
  }

你可以得到一个 o(n) 通过将列表附加到头部并在结尾处反转来构建解决方案:

def fast(list: List[(String, Int)]): List[(String, Int)] =
  list.foldLeft(List[(String, Int)]()) {
    (m: List[(String, Int)], n: (String, Int)) => {
      val p = if (n._2 == 0) (n._1, m.head._2 + 1) else n
      p +: m
    }
  }.reverse

在我的计算机上,对于一个32000大小的列表,快速变量需要18毫秒,而慢速变量需要6秒。