The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion Performance and complexity

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Jul 19 2011, 5:21 pm
From: Josh Suereth <joshua.suer...@gmail.com>
Date: Tue, 19 Jul 2011 17:21:51 -0400
Local: Tues, Jul 19 2011 5:21 pm
Subject: Re: [scala-user] Performance and complexity

Your Java version doesn't abstract over the size of the slice.

I'm working on a better scala version, but part of the pain is avoiding the
scala.Stream class right now.   I should have something shortly.

- Josh

2011/7/19 Cédric Beust ♔ <ced...@beust.com>

> Hi everyone,

> I became intrigued with a problem that Mark Nelson posted to the list last
> .

> 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 {

>       }

>     }

>     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