scipy/scipy — pull request #3338 by pv (2014-02-16 22:43:09+00:00)
Title: ENH: sparse: speedup LIL matrix slicing

The current implementation for slicing LIL matrices is very pessimal. Replace it with a more optimal implementation.

Gives a factor of ~1/density speedup:
```
In []: A = rand(3000, 3000, density=1e-3, format="lil")

# Before
In []: %timeit A[::2,::-2]
1 loops, best of 3: 3.24 s per loop

# After
In [3]: %timeit A[::2,::-2]
100 loops, best of 3: 3.55 ms per loop
```
Gives speedups also for smaller slices:
```
# Before
In []: %timeit A[3,:]
100 loops, best of 3: 5.12 ms per loop
In []: %timeit A[:,3]
100 loops, best of 3: 16.3 ms per loop
In []: %timeit A[1:5,1:5]
1000 loops, best of 3: 304 µs per loop

# After
In []: %timeit A[3,:]
10000 loops, best of 3: 32.8 µs per loop
In []: %timeit A[:,3]
100 loops, best of 3: 5.25 ms per loop
In []: %timeit A[1:5,1:5]
10000 loops, best of 3: 42.2 µs per loop
```
(Column slices in LIL are still problematic, but that's due to the matrix format.)