Bug in interval equality?

[Rüdiger Klaehn]

Hi All,

am I doing something wrong, or is there a bug in interval equality? I would expect that if(a.toString == b.toString), then a == b. 

From looking at the debugger, r1 is Above with flags = 0, and r2 is Above with flags = 2.

Cheers,

Rüdiger

---

Code:

  @Test

  def testIntervalUnion() : Unit = {

    val a = Interval("[14, 44)")

    val b = Interval("(76, ∞)")

    val r1 = Interval("[14, ∞)")

    val r2 = a union b

    println(r1) 

    println(r2)

    require(r1 == r2)

  }

Output:

[14, ∞)

[14, ∞)

java.lang.IllegalArgumentException: requirement failed

[Rüdiger Klaehn]

Here is some more weirdness with Interval.union:

scala> import spire.math._

import spire.math._

scala> import spire.implicits._

import spire.implicits._

scala> Interval.empty[Long]

res1: spire.math.Interval[Long] = (Ø)

scala> Interval.empty[Long] union Interval.point(1L)

res2: spire.math.Interval[Long] = [1]

scala> Interval.empty[Long] union Interval.above(1L)

res3: spire.math.Interval[Long] = (0, ∞)

[Erik Osheim]

On Sun, Dec 21, 2014 at 12:05:16PM -0800, Rüdiger Klaehn wrote:
> am I doing something wrong, or is there a bug in interval equality? I would
> expect that if(a.toString == b.toString), then a == b.

It looks to me like this is a bug -- the "same" interval is ending up
with different flags in the uppder bound. I will try to get a test
written for this tonight and you can verify the fix.

Thanks for catching this!

-- Erik

[Erik Osheim]

Another bug! I'll try to fix this as well.

Thanks for all your help! Sorry you are running into bugs.

-- Erik

[Erik Osheim]

Hi Rüdiger,

Which version of Spire are you running? We're about to do a 0.9.0
release which contains many improvements to the Interval type (and bug
fixes) by Denis Rosset. It looks to me like both of these issues work
as expected in master.

Given these bugs, I will try to get a 0.9.0 release tagged if you can
confirm that 'master' works for you.

Thanks,

-- Erik

[Rüdiger Klaehn]

Hi Erik,

Thanks for the quick feedback!

Just in case you are wondering why I am using intervals so heavily: I
have written a data structure for non-overlapping interval sets of
primitive types: https://github.com/rklaehn/intervalset

It is very fast and efficiently supports all operations that you need
to define a boolean algebra (and, or, not, xor). The downside is of
course that it only works for things that can be converted into a long
while preserving order.

I will try if I can write something with acceptable performance that
does not have this limitation, but it will never be as fast.

Would you be interested in having something like this in spire? I
think it would make a nice addition.

Cheers,

Rüdiger

[Rüdiger Klaehn]

I am using 0.8.2, the latest version from maven. I noticed that there
is quite a bit of difference from master when looking at the code.

[Erik Osheim]

On Mon, Dec 22, 2014 at 12:48:51AM +0100, Rüdiger Klaehn wrote:
> Just in case you are wondering why I am using intervals so heavily: I
> have written a data structure for non-overlapping interval sets of
> primitive types: https://github.com/rklaehn/intervalset
>
> It is very fast and efficiently supports all operations that you need
> to define a boolean algebra (and, or, not, xor). The downside is of
> course that it only works for things that can be converted into a long
> while preserving order.
>
> I will try if I can write something with acceptable performance that
> does not have this limitation, but it will never be as fast.
>
> Would you be interested in having something like this in spire? I
> think it would make a nice addition.

Hi Rüdiger,

That looks really interesting! I'd love to have something like that
available in Spire, either in a subproject or in core. Please keep me
posted on your progress with making the sets generic -- it would be
great if they were able to support SafeLong as well (although of
course I understand the performance concerns). It would be good to be
able to put a number on the speed penalty: is it 2x slower? 5x?

I'lll email the list once I've released Spire-0.9.0, and I'll make
sure to CC you.

As you saw there will be some changes between 0.8.2 and 0.9.0. When I
send the release announcement I will include a comprehensive list, but
one change which will affect you is that we renamed BooleanAlgebra[A]
to Bool[A].

Sincerely,

-- Erik

[Rüdiger Klaehn]

Am Montag, 22. Dezember 2014 03:46:25 UTC+1 schrieb Erik Osheim:

On Mon, Dec 22, 2014 at 12:48:51AM +0100, Rüdiger Klaehn wrote:
> Just in case you are wondering why I am using intervals so heavily: I
> have written a data structure for non-overlapping interval sets of
> primitive types: https://github.com/rklaehn/intervalset
>
> It is very fast and efficiently supports all operations that you need
> to define a boolean algebra (and, or, not, xor). The downside is of
> course that it only works for things that can be converted into a long
> while preserving order.
>
> I will try if I can write something with acceptable performance that
> does not have this limitation, but it will never be as fast.
>
> Would you be interested in having something like this in spire? I
> think it would make a nice addition.

Hi Rüdiger,

That looks really interesting! I'd love to have something like that
available in Spire, either in a subproject or in core. Please keep me
posted on your progress with making the sets generic -- it would be
great if they were able to support SafeLong as well (although of
course I understand the performance concerns).

There is now a generic version of IntervalSet that only requires an Order instance for T. It is called IntervalSeq, whereas the trie-based implementation has been renamed to IntervalTrie. Here is a demo of the generic version:

$ sbt console

scala> import IntervalSeq._

import IntervalSeq._

scala> (above(Rational(1,3)) | below(Rational(-4,7))) ^ point(Rational(17,5))

res0: com.rklaehn.interval.IntervalSeq[spire.math.Rational] = (-∞, -4/7);(1/3, 17/5);(17/5, ∞)

scala> ~res0

res1: com.rklaehn.interval.IntervalSeq[spire.math.Rational] = [-4/7, 1/3];[17/5]

scala> 

 

It would be good to be
able to put a number on the speed penalty: is it 2x slower? 5x?

It is a completely different data structure, so the performance characteristics are very different. There is a benchmark for both implementations. The biggest limitation of the array-based implementation is that it is O(N) when combining small (n=1 or 2) and large sets, whereas the Trie-based implementation is O(log(N)) in these cases. 

But overall the array-based implementation is doing pretty well. In particular, it will do close to the theoretical optimum number of comparisons, so if you have a type such as Rational for which the comparison is potentially expensive, the array-based implementation will have no big performance penalty relative to a hypothetical tree-based implementation.

I will add some notes about the implementation to the repository soon.