> I became intrigued with a problem that Mark Nelson posted to the list last
> week. Here is a link to the discussion<http://groups.google.com/group/scala-user/browse_thread/thread/f26f40...>
> .

> 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