Performance and complexity
Cédric Beust ♔
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)
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;
}
Josh Suereth
Rex Kerr
It's not hard to avoid those problems:
def eliminated[@specialized(Byte) T: ClassManifest](
xs: Array[T], slice: Seq[T], found: List[Array[T]] = Nil
): Array[T] = {
val i = xs indexOfSlice slice
else eliminated(xs.drop(i+slice.length), slice, xs.take(i) :: found)
}
--Rex
Dave
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] = {
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)
}
Derek Williams
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
Derek Williams
Woops, little bug there. newResult should be built on fallback, not result.
Derek Williams
Stefan Wagner
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 ^.
- --
Tschööö--->...Stefan
- ---------------------------
Don't visit my homepage at:
http://home.arcor-online.net/hirnstrom
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
iEYEARECAAYFAk4mQFcACgkQQeATqGpDnRqnUACfZ4FGGSyHweMO2aFwgdsCN4D0
KoIAnAwVGaUl5w+jCAET9TA7EAXZpbBO
=Cy+t
-----END PGP SIGNATURE-----
Derek Williams
> 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
martin odersky
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
Alex Cruise
... a local mutable variable is no big deal, but think twice before introducing a global one!
Sadache Aldrobi
www.sadekdrobi.com
ʎdoɹʇuǝ
Sadache Aldrobi
Sadache Aldrobi
martin odersky
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
Cédric Beust ♔
Germán Ferrari
Tony Morris
I mostly agree. If performance matters, and you are doing prefix
matching on a cons list, you might want to consider a more appropriate
data structure. This inappropriate use of data structures is completely
aside from the functional/imperative false dilemma.
http://paste.pocoo.org/show/443309/
--
Tony Morris
http://tmorris.net/
Derek Williams
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
Tony Morris
>
> Do you suggest working with Arrays? Or is there a better alternative?
>
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.
Derek Williams
On Jul 20, 2011 11:19 PM, "Tony Morris" <tonym...@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
It is similar to DList[1], which would unfortunately blow the stack for any large input, so is instead modelled with a pair of lists[2]. Mark Hibberd wrote most of it.
[1]
case class Endo[A](e: A => A)
case class DList[A](k: Endo[List[A]])
http://hackage.haskell.org/package/dlist
[2]
case class Endo[A](e: A => A)
case class Dequeue[A](pre: List[Endo[List[A]]], post: List[Endo[List[A]]])
martin odersky
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?
def elim(xs: List[Int], slice: Seq[Int]): List[Int] = xs match {
case _ if xs startsWith slice => xs drop slice.length
case x :: xs1 => x :: elim(xs1, slice)
case Nil => Nil
}
To come back to the original problem (long array, performance matters), I would simply fall back on an imperative solution, which is actually also pretty nice:
def elim(xs: Array[Byte], slice: Seq[Byte]): Array[Byte] = {
val buf = new ArrayBuffer[Byte]
var i = 0
while (i < xs.length)
if (xs startsWith (slice, i)) i += slice.length
else { buf += xs(i); i += 1 }
buf.toArray
}
Cheers
-- Martin