Re: Ranges

[Ted Zlatanov <tzz@lifelogs.com>]

On Wed, 07 Jan 2004, larsi@gnus.org wrote:

> Ted Zlatanov <tzz@lifelogs.com> writes:
> 
>>> Inversion list Range list  Full list 
>>> (2 5 7 8)      ((2 . 4) 7) (2 3 4 7)
>>
>> Right.  Inversion lists are as compact as ranges, but have some
>> nicer features - insertion and deletion of items from the inversion
>> list is, I think, simpler and faster code than ranges.
> 
> In this example, it's one cons cell more.  :-)

For short ranges (less than 4 items per interval, I think), it's
better to use explicit article numbers than almost anything else.  The
example was not very good to show why inversion lists should be used.

I'll show the sequence in a more real-life situation, and see if you
think inversion lists may be useful.  I'll use a list of 1000 items
that can be on or off.

start with () = all items are off; below is the running state as 1 or
0; also I include the range representations

set items 5, 20, 80-100 on
(5 6 20 21 80 101)
 1100111000111000 

range: (5 20 21 (80 . 100))

set items 100-1000 on
(5 6 20 21 80 100 100 101 101 1001); consolidate to
 110011100011100001111000011110000

(5 6 20 21 80 1001)
 11001110001110000

range: (5 20 21 (80 . 1000))

set items 21-79 on
(5 6 20 21 21 80 80 1001); consolidate to
 11001110001110001110000

(5 6 20 1001)
 11001110000

range: (5 (20 . 1000))

set items 50, 500, 999 off

(5 6 20 50 51 500 501 999 1000 1001)
 1100111000111000011110000111110000

range: (5 (20 . 49) (51 . 499) (501 . 1000))

So yes, this is far less intuitive than ranges.  I think, however,
that it may be faster for operations.  If you think it's worthwhile, I
can try adding gnus-range.el functions that use inversion lists and we
can benchmark them.

For a start, here's the gnus-member-of-invlist function, much simpler
than gnus-member-of-range:

(defun gnus-member-of-invlist (number list)
  (let (state)
    (while (and list
		(>= number (car list)))
      (setq state (not state))
      (setq list (cdr list)))
    state))

I found that it was slower to search this way:

(benchmark-run-compiled 50000 (gnus-member-of-invlist 800 '(5 6 20 50 51 500 501 999 1000 1001)))
(2.5340199999999995 10 3.791519999999963)
(benchmark-run-compiled 50000 (gnus-member-of-range 800 '(5 (20 . 49) (51 . 499) (501 . 1000))))
(0.4903200000000001 10 4.371743000000038)

I may have missed something in the gnus-member-of-invlist
implementation, I'm not sure.  I'm not well-versed in the internal
Emacs implementation of lists, so maybe there's a better way of
storing the inversion list.  Vectors may work - with the advantages
of binary searching and an easy distinction from ranges, which can
still be stores as lists.

The code for the other gnus-range.el functions will also be
significantly shorter using inversion lists, though I'm not sure if
they will be faster - I'd need to benchmark.

Ted