Performance and complexity

Hi everyone,
I became intrigued with a problem that Mark Nelson posted to the list last week. Here is a link to the discussion.
The problem is simple: eliminate all the occurrences of the sequence (26, 20, 64) from a list. For example, given [1, 2, 26, 20, 64, 3, 26, 20, 64, 4], the result should be [1, 2, 3, 4].
Of all the solutions proposed, only the one proposed by Ruediger Keller worked:

def eliminate[@specialized(Byte) T : ClassManifest](xs: Array[T], 
slice: Seq[T]): Array[T] = { 
  val i = xs indexOfSlice slice 
  if(i == -1) xs else xs.take(i) ++ eliminate(xs.drop(i + slice.length), slice) 

} 
Daniel Sobral also offered a correct solution but it only works on Byte, so not really applicable here.
I became curious to see what kind of complexity the functional solution above is and how it compares to the trivial and linear imperative version (no need for Boyer-Moore, really):

  private static List<Integer> eliminate(List<Integer> value) {

    List<Integer> result = Lists.newArrayList();

    for (int i = 0; i < value.size(); i++) {

      if (value.get(i) == SLICE.get(0) && value.get(i + 1) == SLICE.get(1)

          && value.get(i + 2) == SLICE.get(2)) {

        i += 2;

      } else {

        result.add(value.get(i));

      }

    }

    return result;

  }

I decided to run a few benchmarks and the results were surprising. I tried with various sizes of elements (10k, 100k, 1M, 10M) and with a fixed number of sequences to remove from them (3).
The imperative version solves the problem for lists up to 10M of elements in a few milliseconds.
However, the Scala version above takes 2 seconds for 1000 elements and doesn't finish after a few minutes for 10k elements.
Can someone suggest additional functional solutions to this problem that can at least approach the linear performance of the imperative version?
Also, what are the complexities of these functional solutions?
-- Cédric

Hi everyone,
I became intrigued with a problem that Mark Nelson posted to the list last week. Here is a link to the discussion.
The problem is simple: eliminate all the occurrences of the sequence (26, 20, 64) from a list. For example, given [1, 2, 26, 20, 64, 3, 26, 20, 64, 4], the result should be [1, 2, 3, 4].
Of all the solutions proposed, only the one proposed by Ruediger Keller worked:

def eliminate[@specialized(Byte) T : ClassManifest](xs: Array[T], 
slice: Seq[T]): Array[T] = { 
  val i = xs indexOfSlice slice 
  if(i == -1) xs else xs.take(i) ++ eliminate(xs.drop(i + slice.length), slice) 

} 
Daniel Sobral also offered a correct solution but it only works on Byte, so not really applicable here.
I became curious to see what kind of complexity the functional solution above is and how it compares to the trivial and linear imperative version (no need for Boyer-Moore, really):

  private static List<Integer> eliminate(List<Integer> value) {

    List<Integer> result = Lists.newArrayList();

    for (int i = 0; i < value.size(); i++) {

      if (value.get(i) == SLICE.get(0) && value.get(i + 1) == SLICE.get(1)

          && value.get(i + 2) == SLICE.get(2)) {

        i += 2;

      } else {

        result.add(value.get(i));

      }

    }

    return result;

  }

I decided to run a few benchmarks and the results were surprising. I tried with various sizes of elements (10k, 100k, 1M, 10M) and with a fixed number of sequences to remove from them (3).
The imperative version solves the problem for lists up to 10M of elements in a few milliseconds.
However, the Scala version above takes 2 seconds for 1000 elements and doesn't finish after a few minutes for 10k elements.
Can someone suggest additional functional solutions to this problem that can at least approach the linear performance of the imperative version?
Also, what are the complexities of these functional solutions?
-- Cédric

Maybe you could optimize the fucntion it for tail call recursion

package eliminate

import scala.annotation.tailrec

object Main extends App {

@tailrec
def eliminate[@specialized(Byte) T : ClassManifest](acc: Array[T], xs:
Array[T], slice: Seq[T]): Array[T] = {
val i = xs indexOfSlice slice
i match {
case -1 => acc ++ xs
case _ => eliminate(acc ++ xs.take(i), xs.drop(i + slice.length),
slice)
}
}

val acc : Array[Byte] = Array.empty
val ar = List[Byte](1, 2, 26, 20, 64, 3, 26, 20, 64, 4).toArray
val sl = Seq[Byte](26, 20, 64)
val el = eliminate[Byte](acc, ar, sl)
println(el.toList)

}

This seems plenty fast (written quickly so variable names suffer):

def eliminate[A](seq: Seq[A], slice: Seq[A]): List[A] = {
val sliceList = slice.toList
def iter(xs: List[A], ys: List[A], result: List[A], fallback:
List[A]): List[A] = xs match {
case xs if ys.isEmpty => iter(xs, sliceList, result, result)
case Nil => fallback.reverse
case x :: xs if x == ys.head => iter(xs, ys.tail, result, x :: fallback)
case x :: xs =>
val newResult = x :: result
iter(xs, sliceList, newResult, newResult)
}
iter(seq.toList, sliceList, Nil, Nil)
}

Only tested with an Array[Byte] up to 1M, and it was just the original
10 digits repeated. Didn't time it, only tested within the REPL, but
it returns fast even if I convert the List back to an Array.

--
Derek Williams

Woops, little bug there. newResult should be built on fallback, not result.

Derek Williams

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am 20.07.2011 01:20, schrieb Derek Williams:
> Woops, little bug there. newResult should be built on fallback, not result.

and a second one:

eliminate (Seq(1, 2, 3, 4, 3, 4, 2, 5), Seq(3, 4, 2))
res168: List[Int] = List(1, 2, 3, 4, 3, 4, 2, 5)

easy to find, since I shortly thought a fast solution ... looking for a
3-element pattern from the back, and jumping length(pattern) forward, if
it doesn't match, but: The end of the pattern might match in the
beginning again.

def eliminate[A](seq: Seq[A], slice: Seq[A]): List[A] = {
val sliceList = slice.toList
def iter(xs: List[A], ys: List[A], result: List[A], fallback:
List[A]): List[A] = xs match {
case xs if ys.isEmpty => iter(xs, sliceList, result, result)
case Nil => fallback.reverse
case x :: xs if x == ys.head => iter(xs, ys.tail, result, x :: fallback)
case x :: xs =>
val newResult = x :: fallback
iter(xs, sliceList, newResult, newResult)
}
iter(seq.toList, sliceList, Nil, Nil)
}

I understood ^.

On Tue, Jul 19, 2011 at 8:41 PM, Stefan Wagner wrote:
> easy to find, since I shortly thought a fast solution ... looking for a
> 3-element pattern from the back, and jumping length(pattern) forward, if
> it doesn't match, but: The end of the pattern might match in the
> beginning again.

Good catch. I knew I was missing something. I actually had it checking
for that before and I must have "optimized" it away. This one works:

def eliminate[A](seq: Seq[A], slice: Seq[A]): List[A] = {
val sliceList = slice.toList
def iter(xs: List[A], ys: List[A], result: List[A], fallback:
List[A]): List[A] = xs match {
case xs if ys.isEmpty => iter(xs, sliceList, result, result)
case Nil => fallback.reverse
case x :: xs if x == ys.head => iter(xs, ys.tail, result, x ::
fallback)
case x :: xs if ys eq sliceList =>
val newResult = x :: result
iter(xs, sliceList, newResult, newResult)
case xs =>
iter(xs, sliceList, fallback, fallback)
}
iter(seq.toList, sliceList, Nil, Nil)
}

--
Derek Williams

... a local mutable variable is no big deal, but think twice before introducing a global one!

I should also say, there's really nothing wrong in just coding the imperative algorithm in Scala. It's not a sacrilege to use imperative code, in particular if it's inside a function. Sometimes it's the clearest way to express things. Many other times it is not.

Generally, it is much more important for a system that the interfaces are functional than that the implementations are. Or, put otherwise, a local mutable variable is no big deal, but think twice before introducing a global one!

For instance, if you look inside the scala.collection.immutable.List class you find that most methods use a local mutable ListBuffer and a while loop to fill it.
It's done this way to make these list operations not blow the stack for long lists.
So we have an imperative implementation that ensures good functional behavior on the outside. Compare with OCaml, where lists are purely functional but blow the stack for lists longer than some 1000's of elements.

Cheers

 -- Martin

My 2 cents.
def trimStart[A](slice:Seq[A],original:Seq[A]):Seq[A] = {     @scala.annotation.tailrec     def trimSt(sliceLeft:Seq[A],l:Seq[A]):Seq[A] = (sliceLeft,l) match {            case (Nil,_) => l           case (_,Nil) => original           case (h1::t1,h2::t2) => if(h1 == h2)  trimSt(t1,t2) else original       }      trimSt(slice,original) }
def removeOccurence[A](slice:Seq[A],original:Seq[A])= {  @scala.annotation.tailrec  def remove(leftOriginal:Seq[A],result:Seq[A]):Seq[A]=       trimStart(slice,leftOriginal) match{           case(h::tail) => remove(tail,h +: result)          case(Nil) => result.reverse      }      remove(original,Nil)  }
}
worth noting that you can use a buffer for the result in the second method instead of a Seq (Or even an immutable structure that allows adding elements to the end) so that you don't require the last result.reverse. Also I am sure it can be written with fewer lines, I just happen to be late for work :)
Sadek
On Wed, Jul 20, 2011 at 9:12 AM, martin odersky <martin.odersky@epfl.ch> wrote:

I should also say, there's really nothing wrong in just coding the imperative algorithm in Scala. It's not a sacrilege to use imperative code, in particular if it's inside a function. Sometimes it's the clearest way to express things. Many other times it is not.

Generally, it is much more important for a system that the interfaces are functional than that the implementations are. Or, put otherwise, a local mutable variable is no big deal, but think twice before introducing a global one!

For instance, if you look inside the scala.collection.immutable.List class you find that most methods use a local mutable ListBuffer and a while loop to fill it.
It's done this way to make these list operations not blow the stack for long lists.
So we have an imperative implementation that ensures good functional behavior on the outside. Compare with OCaml, where lists are purely functional but blow the stack for lists longer than some 1000's of elements.

Cheers

 -- Martin

--
www.sadekdrobi.com
ʎdoɹʇuǝ

I forgot a call :p
def trimStart[A](slice:Seq[A],original:Seq[A]):Seq[A] = {     @scala.annotation.tailrec     def trimSt(sliceLeft:Seq[A],l:Seq[A]):Seq[A] = (sliceLeft,l) match {            case (Nil,l) => trimStart(slice,l)           case (_,Nil) => original           case (h1::t1,h2::t2) => if(h1 == h2)  trimSt(t1,t2) else original        }       trimSt(slice,original)}
def removeOccurence[A](slice:Seq[A],original:Seq[A])= {  @scala.annotation.tailrec  def remove(leftOriginal:Seq[A],result:Seq[A]):Seq[A]=        trimStart(slice,leftOriginal) match{          case(h::tail) => remove(tail,h +: result)          case(Nil) => result.reverse      }      remove(original,Nil)   }

On Wed, Jul 20, 2011 at 10:06 AM, Sadache Aldrobi <sadek.drobi@gmail.com> wrote:

My 2 cents.
def trimStart[A](slice:Seq[A],original:Seq[A]):Seq[A] = {     @scala.annotation.tailrec     def trimSt(sliceLeft:Seq[A],l:Seq[A]):Seq[A] = (sliceLeft,l) match {            case (Nil,_) => l           case (_,Nil) => original           case (h1::t1,h2::t2) => if(h1 == h2)  trimSt(t1,t2) else original       }      trimSt(slice,original) }
def removeOccurence[A](slice:Seq[A],original:Seq[A])= {  @scala.annotation.tailrec  def remove(leftOriginal:Seq[A],result:Seq[A]):Seq[A]=       trimStart(slice,leftOriginal) match{           case(h::tail) => remove(tail,h +: result)          case(Nil) => result.reverse      }      remove(original,Nil)  }
}
worth noting that you can use a buffer for the result in the second method instead of a Seq (Or even an immutable structure that allows adding elements to the end) so that you don't require the last result.reverse. Also I am sure it can be written with fewer lines, I just happen to be late for work :)
Sadek
On Wed, Jul 20, 2011 at 9:12 AM, martin odersky <martin.odersky@epfl.ch> wrote:

I should also say, there's really nothing wrong in just coding the imperative algorithm in Scala. It's not a sacrilege to use imperative code, in particular if it's inside a function. Sometimes it's the clearest way to express things. Many other times it is not.

Generally, it is much more important for a system that the interfaces are functional than that the implementations are. Or, put otherwise, a local mutable variable is no big deal, but think twice before introducing a global one!

For instance, if you look inside the scala.collection.immutable.List class you find that most methods use a local mutable ListBuffer and a while loop to fill it.
It's done this way to make these list operations not blow the stack for long lists.
So we have an imperative implementation that ensures good functional behavior on the outside. Compare with OCaml, where lists are purely functional but blow the stack for lists longer than some 1000's of elements.

Cheers

 -- Martin

--
www.sadekdrobi.com
ʎdoɹʇuǝ

--
www.sadekdrobi.com
ʎdoɹʇuǝ

Like I said, if performance matters and the array is big, I would use the imperative solution. If simplicity and elegance matters, I think the most straightforward solution is to use pattern matching over lists:

 def elim(xs: List[Int]): List[Int] = xs match {
    case 26 :: 20 :: 64 :: rest => elim(rest)
    case x :: xs1 => x :: elim(xs1)
    case Nil => Nil
  }

Cheers

 -- Martin

Hi Martin,
Thanks, that's the most intuitive solution so far, although I see two slight problems with it: 1) it will only work if the slice is known at compile time and 2) it's not tail recursive, so it will most likely blow up the stack on big lists.
Unless I'm missing something?
-- Cédric




2011/7/20 martin odersky <martin.odersky@epfl.ch>

Like I said, if performance matters and the array is big, I would use the imperative solution. If simplicity and elegance matters, I think the most straightforward solution is to use pattern matching over lists:

 def elim(xs: List[Int]): List[Int] = xs match {
    case 26 :: 20 :: 64 :: rest => elim(rest)
    case x :: xs1 => x :: elim(xs1)
    case Nil => Nil
  }

Cheers

 -- Martin

On 21/07/11 06:35, martin odersky wrote:
> Like I said, if performance matters and the array is big, I would use
> the imperative solution. If simplicity and elegance matters, I think
> the most straightforward solution is to use pattern matching over lists:
>
> def elim(xs: List[Int]): List[Int] = xs match {
> case 26 :: 20 :: 64 :: rest => elim(rest)
> case x :: xs1 => x :: elim(xs1)
> case Nil => Nil
> }
>
> Cheers
>

Do you suggest working with Arrays? Or is there a better alternative?

At the defense of List, I have found prepending to a List, followed by reverse, to be faster than appending to most others, especially other immutable collections.

Derek Williams

On 21/07/11 15:14, Derek Williams wrote:
>
> Do you suggest working with Arrays? Or is there a better alternative?
>
This depends ultimately on all the operations required, including how
the "List" came to be in the first place. Certainly, prefix matching on
a cons list (or even a mutable list) for anything but a trivial data set
is not particularly noble and then measuring the performance is... a bit
ridonkulous.

A prefix tree (trie) may be more appropriate (of which there are many
variations), or perhaps even a Burkhard-Keller Tree (a bit of a stretch
there -- need to know all operations).

> At the defense of List, I have found prepending to a List, followed by
> reverse, to be faster than appending to most others, especially other
> immutable collections.
>
Scalaz 7 will include a list with O(1) cons and snoc (at the expense of
other operations). It took some gymnastics to get there though.

On Jul 20, 2011 11:19 PM, "Tony Morris" <tonymorris@gmail.com> wrote:
> Scalaz 7 will include a list with O(1) cons and snoc (at the expense of
> other operations). It took some gymnastics to get there though.

I'll definitely have to check that out, thanks Tony.

>
> --
> Tony Morris
> http://tmorris.net/
>
>

pE9PEw [at] mail [dot] gmail [dot] com" type="cite">

On Jul 20, 2011 11:19 PM, "Tony Morris" <tonymorris [at] gmail [dot] com" rel="nofollow">tonymorris@gmail.com> wrote:
> Scalaz 7 will include a list with O(1) cons and snoc (at the expense of
> other operations). It took some gymnastics to get there though.

I'll definitely have to check that out, thanks Tony.

>
> --
> Tony Morris
> http://tmorris.net/
>
>

-- 
Tony Morris
http://tmorris.net/

Hi Martin,
Thanks, that's the most intuitive solution so far, although I see two slight problems with it: 1) it will only work if the slice is known at compile time and 2) it's not tail recursive, so it will most likely blow up the stack on big lists.
Unless I'm missing something?