Coverage for /usr/lib/python3/dist-packages/scipy/sparse/_lil.py: 21%
299 statements
« prev ^ index » next coverage.py v7.4.4, created at 2025-06-14 15:25 +0200
1"""List of Lists sparse matrix class
2"""
4__docformat__ = "restructuredtext en"
6__all__ = ['lil_array', 'lil_matrix', 'isspmatrix_lil']
8from bisect import bisect_left
10import numpy as np
12from ._matrix import spmatrix, _array_doc_to_matrix
13from ._base import _spbase, sparray, issparse
14from ._index import IndexMixin, INT_TYPES, _broadcast_arrays
15from ._sputils import (getdtype, isshape, isscalarlike, upcast_scalar,
16 check_shape, check_reshape_kwargs)
17from . import _csparsetools
20class _lil_base(_spbase, IndexMixin):
21 """Row-based LIst of Lists sparse matrix
23 This is a structure for constructing sparse matrices incrementally.
24 Note that inserting a single item can take linear time in the worst case;
25 to construct a matrix efficiently, make sure the items are pre-sorted by
26 index, per row.
28 This can be instantiated in several ways:
29 lil_array(D)
30 with a dense matrix or rank-2 ndarray D
32 lil_array(S)
33 with another sparse matrix S (equivalent to S.tolil())
35 lil_array((M, N), [dtype])
36 to construct an empty matrix with shape (M, N)
37 dtype is optional, defaulting to dtype='d'.
39 Attributes
40 ----------
41 dtype : dtype
42 Data type of the matrix
43 shape : 2-tuple
44 Shape of the matrix
45 ndim : int
46 Number of dimensions (this is always 2)
47 nnz
48 Number of stored values, including explicit zeros
49 data
50 LIL format data array of the matrix
51 rows
52 LIL format row index array of the matrix
54 Notes
55 -----
56 Sparse matrices can be used in arithmetic operations: they support
57 addition, subtraction, multiplication, division, and matrix power.
59 Advantages of the LIL format
60 - supports flexible slicing
61 - changes to the matrix sparsity structure are efficient
63 Disadvantages of the LIL format
64 - arithmetic operations LIL + LIL are slow (consider CSR or CSC)
65 - slow column slicing (consider CSC)
66 - slow matrix vector products (consider CSR or CSC)
68 Intended Usage
69 - LIL is a convenient format for constructing sparse matrices
70 - once a matrix has been constructed, convert to CSR or
71 CSC format for fast arithmetic and matrix vector operations
72 - consider using the COO format when constructing large matrices
74 Data Structure
75 - An array (``self.rows``) of rows, each of which is a sorted
76 list of column indices of non-zero elements.
77 - The corresponding nonzero values are stored in similar
78 fashion in ``self.data``.
81 """
82 _format = 'lil'
84 def __init__(self, arg1, shape=None, dtype=None, copy=False):
85 _spbase.__init__(self)
86 self.dtype = getdtype(dtype, arg1, default=float)
88 # First get the shape
89 if issparse(arg1):
90 if arg1.format == "lil" and copy:
91 A = arg1.copy()
92 else:
93 A = arg1.tolil()
95 if dtype is not None:
96 A = A.astype(dtype, copy=False)
98 self._shape = check_shape(A.shape)
99 self.dtype = A.dtype
100 self.rows = A.rows
101 self.data = A.data
102 elif isinstance(arg1,tuple):
103 if isshape(arg1):
104 if shape is not None:
105 raise ValueError('invalid use of shape parameter')
106 M, N = arg1
107 self._shape = check_shape((M, N))
108 self.rows = np.empty((M,), dtype=object)
109 self.data = np.empty((M,), dtype=object)
110 for i in range(M):
111 self.rows[i] = []
112 self.data[i] = []
113 else:
114 raise TypeError('unrecognized lil_array constructor usage')
115 else:
116 # assume A is dense
117 try:
118 A = self._ascontainer(arg1)
119 except TypeError as e:
120 raise TypeError('unsupported matrix type') from e
121 else:
122 A = self._csr_container(A, dtype=dtype).tolil()
124 self._shape = check_shape(A.shape)
125 self.dtype = A.dtype
126 self.rows = A.rows
127 self.data = A.data
129 def __iadd__(self,other):
130 self[:,:] = self + other
131 return self
133 def __isub__(self,other):
134 self[:,:] = self - other
135 return self
137 def __imul__(self,other):
138 if isscalarlike(other):
139 self[:,:] = self * other
140 return self
141 else:
142 return NotImplemented
144 def __itruediv__(self,other):
145 if isscalarlike(other):
146 self[:,:] = self / other
147 return self
148 else:
149 return NotImplemented
151 # Whenever the dimensions change, empty lists should be created for each
152 # row
154 def _getnnz(self, axis=None):
155 if axis is None:
156 return sum([len(rowvals) for rowvals in self.data])
157 if axis < 0:
158 axis += 2
159 if axis == 0:
160 out = np.zeros(self.shape[1], dtype=np.intp)
161 for row in self.rows:
162 out[row] += 1
163 return out
164 elif axis == 1:
165 return np.array([len(rowvals) for rowvals in self.data], dtype=np.intp)
166 else:
167 raise ValueError('axis out of bounds')
169 def count_nonzero(self):
170 return sum(np.count_nonzero(rowvals) for rowvals in self.data)
172 _getnnz.__doc__ = _spbase._getnnz.__doc__
173 count_nonzero.__doc__ = _spbase.count_nonzero.__doc__
175 def __str__(self):
176 val = ''
177 for i, row in enumerate(self.rows):
178 for pos, j in enumerate(row):
179 val += f" {str((i, j))}\t{str(self.data[i][pos])}\n"
180 return val[:-1]
182 def getrowview(self, i):
183 """Returns a view of the 'i'th row (without copying).
184 """
185 new = self._lil_container((1, self.shape[1]), dtype=self.dtype)
186 new.rows[0] = self.rows[i]
187 new.data[0] = self.data[i]
188 return new
190 def getrow(self, i):
191 """Returns a copy of the 'i'th row.
192 """
193 M, N = self.shape
194 if i < 0:
195 i += M
196 if i < 0 or i >= M:
197 raise IndexError('row index out of bounds')
198 new = self._lil_container((1, N), dtype=self.dtype)
199 new.rows[0] = self.rows[i][:]
200 new.data[0] = self.data[i][:]
201 return new
203 def __getitem__(self, key):
204 # Fast path for simple (int, int) indexing.
205 if (isinstance(key, tuple) and len(key) == 2 and
206 isinstance(key[0], INT_TYPES) and
207 isinstance(key[1], INT_TYPES)):
208 # lil_get1 handles validation for us.
209 return self._get_intXint(*key)
210 # Everything else takes the normal path.
211 return IndexMixin.__getitem__(self, key)
213 def _asindices(self, idx, N):
214 # LIL routines handle bounds-checking for us, so don't do it here.
215 try:
216 x = np.asarray(idx)
217 except (ValueError, TypeError, MemoryError) as e:
218 raise IndexError('invalid index') from e
219 if x.ndim not in (1, 2):
220 raise IndexError('Index dimension must be <= 2')
221 return x
223 def _get_intXint(self, row, col):
224 v = _csparsetools.lil_get1(self.shape[0], self.shape[1], self.rows,
225 self.data, row, col)
226 return self.dtype.type(v)
228 def _get_sliceXint(self, row, col):
229 row = range(*row.indices(self.shape[0]))
230 return self._get_row_ranges(row, slice(col, col+1))
232 def _get_arrayXint(self, row, col):
233 row = row.squeeze()
234 return self._get_row_ranges(row, slice(col, col+1))
236 def _get_intXslice(self, row, col):
237 return self._get_row_ranges((row,), col)
239 def _get_sliceXslice(self, row, col):
240 row = range(*row.indices(self.shape[0]))
241 return self._get_row_ranges(row, col)
243 def _get_arrayXslice(self, row, col):
244 return self._get_row_ranges(row, col)
246 def _get_intXarray(self, row, col):
247 row = np.array(row, dtype=col.dtype, ndmin=1)
248 return self._get_columnXarray(row, col)
250 def _get_sliceXarray(self, row, col):
251 row = np.arange(*row.indices(self.shape[0]))
252 return self._get_columnXarray(row, col)
254 def _get_columnXarray(self, row, col):
255 # outer indexing
256 row, col = _broadcast_arrays(row[:,None], col)
257 return self._get_arrayXarray(row, col)
259 def _get_arrayXarray(self, row, col):
260 # inner indexing
261 i, j = map(np.atleast_2d, _prepare_index_for_memoryview(row, col))
262 new = self._lil_container(i.shape, dtype=self.dtype)
263 _csparsetools.lil_fancy_get(self.shape[0], self.shape[1],
264 self.rows, self.data,
265 new.rows, new.data,
266 i, j)
267 return new
269 def _get_row_ranges(self, rows, col_slice):
270 """
271 Fast path for indexing in the case where column index is slice.
273 This gains performance improvement over brute force by more
274 efficient skipping of zeros, by accessing the elements
275 column-wise in order.
277 Parameters
278 ----------
279 rows : sequence or range
280 Rows indexed. If range, must be within valid bounds.
281 col_slice : slice
282 Columns indexed
284 """
285 j_start, j_stop, j_stride = col_slice.indices(self.shape[1])
286 col_range = range(j_start, j_stop, j_stride)
287 nj = len(col_range)
288 new = self._lil_container((len(rows), nj), dtype=self.dtype)
290 _csparsetools.lil_get_row_ranges(self.shape[0], self.shape[1],
291 self.rows, self.data,
292 new.rows, new.data,
293 rows,
294 j_start, j_stop, j_stride, nj)
296 return new
298 def _set_intXint(self, row, col, x):
299 _csparsetools.lil_insert(self.shape[0], self.shape[1], self.rows,
300 self.data, row, col, x)
302 def _set_arrayXarray(self, row, col, x):
303 i, j, x = map(np.atleast_2d, _prepare_index_for_memoryview(row, col, x))
304 _csparsetools.lil_fancy_set(self.shape[0], self.shape[1],
305 self.rows, self.data,
306 i, j, x)
308 def _set_arrayXarray_sparse(self, row, col, x):
309 # Fall back to densifying x
310 x = np.asarray(x.toarray(), dtype=self.dtype)
311 x, _ = _broadcast_arrays(x, row)
312 self._set_arrayXarray(row, col, x)
314 def __setitem__(self, key, x):
315 if isinstance(key, tuple) and len(key) == 2:
316 row, col = key
317 # Fast path for simple (int, int) indexing.
318 if isinstance(row, INT_TYPES) and isinstance(col, INT_TYPES):
319 x = self.dtype.type(x)
320 if x.size > 1:
321 raise ValueError("Trying to assign a sequence to an item")
322 return self._set_intXint(row, col, x)
323 # Fast path for full-matrix sparse assignment.
324 if (isinstance(row, slice) and isinstance(col, slice) and
325 row == slice(None) and col == slice(None) and
326 issparse(x) and x.shape == self.shape):
327 x = self._lil_container(x, dtype=self.dtype)
328 self.rows = x.rows
329 self.data = x.data
330 return
331 # Everything else takes the normal path.
332 IndexMixin.__setitem__(self, key, x)
334 def _mul_scalar(self, other):
335 if other == 0:
336 # Multiply by zero: return the zero matrix
337 new = self._lil_container(self.shape, dtype=self.dtype)
338 else:
339 res_dtype = upcast_scalar(self.dtype, other)
341 new = self.copy()
342 new = new.astype(res_dtype)
343 # Multiply this scalar by every element.
344 for j, rowvals in enumerate(new.data):
345 new.data[j] = [val*other for val in rowvals]
346 return new
348 def __truediv__(self, other): # self / other
349 if isscalarlike(other):
350 new = self.copy()
351 new.dtype = np.result_type(self, other)
352 # Divide every element by this scalar
353 for j, rowvals in enumerate(new.data):
354 new.data[j] = [val/other for val in rowvals]
355 return new
356 else:
357 return self.tocsr() / other
359 def copy(self):
360 M, N = self.shape
361 new = self._lil_container(self.shape, dtype=self.dtype)
362 # This is ~14x faster than calling deepcopy() on rows and data.
363 _csparsetools.lil_get_row_ranges(M, N, self.rows, self.data,
364 new.rows, new.data, range(M),
365 0, N, 1, N)
366 return new
368 copy.__doc__ = _spbase.copy.__doc__
370 def reshape(self, *args, **kwargs):
371 shape = check_shape(args, self.shape)
372 order, copy = check_reshape_kwargs(kwargs)
374 # Return early if reshape is not required
375 if shape == self.shape:
376 if copy:
377 return self.copy()
378 else:
379 return self
381 new = self._lil_container(shape, dtype=self.dtype)
383 if order == 'C':
384 ncols = self.shape[1]
385 for i, row in enumerate(self.rows):
386 for col, j in enumerate(row):
387 new_r, new_c = np.unravel_index(i * ncols + j, shape)
388 new[new_r, new_c] = self[i, j]
389 elif order == 'F':
390 nrows = self.shape[0]
391 for i, row in enumerate(self.rows):
392 for col, j in enumerate(row):
393 new_r, new_c = np.unravel_index(i + j * nrows, shape, order)
394 new[new_r, new_c] = self[i, j]
395 else:
396 raise ValueError("'order' must be 'C' or 'F'")
398 return new
400 reshape.__doc__ = _spbase.reshape.__doc__
402 def resize(self, *shape):
403 shape = check_shape(shape)
404 new_M, new_N = shape
405 M, N = self.shape
407 if new_M < M:
408 self.rows = self.rows[:new_M]
409 self.data = self.data[:new_M]
410 elif new_M > M:
411 self.rows = np.resize(self.rows, new_M)
412 self.data = np.resize(self.data, new_M)
413 for i in range(M, new_M):
414 self.rows[i] = []
415 self.data[i] = []
417 if new_N < N:
418 for row, data in zip(self.rows, self.data):
419 trunc = bisect_left(row, new_N)
420 del row[trunc:]
421 del data[trunc:]
423 self._shape = shape
425 resize.__doc__ = _spbase.resize.__doc__
427 def toarray(self, order=None, out=None):
428 d = self._process_toarray_args(order, out)
429 for i, row in enumerate(self.rows):
430 for pos, j in enumerate(row):
431 d[i, j] = self.data[i][pos]
432 return d
434 toarray.__doc__ = _spbase.toarray.__doc__
436 def transpose(self, axes=None, copy=False):
437 return self.tocsr(copy=copy).transpose(axes=axes, copy=False).tolil(copy=False)
439 transpose.__doc__ = _spbase.transpose.__doc__
441 def tolil(self, copy=False):
442 if copy:
443 return self.copy()
444 else:
445 return self
447 tolil.__doc__ = _spbase.tolil.__doc__
449 def tocsr(self, copy=False):
450 M, N = self.shape
451 if M == 0 or N == 0:
452 return self._csr_container((M, N), dtype=self.dtype)
454 # construct indptr array
455 if M*N <= np.iinfo(np.int32).max:
456 # fast path: it is known that 64-bit indexing will not be needed.
457 idx_dtype = np.int32
458 indptr = np.empty(M + 1, dtype=idx_dtype)
459 indptr[0] = 0
460 _csparsetools.lil_get_lengths(self.rows, indptr[1:])
461 np.cumsum(indptr, out=indptr)
462 nnz = indptr[-1]
463 else:
464 idx_dtype = self._get_index_dtype(maxval=N)
465 lengths = np.empty(M, dtype=idx_dtype)
466 _csparsetools.lil_get_lengths(self.rows, lengths)
467 nnz = lengths.sum(dtype=np.int64)
468 idx_dtype = self._get_index_dtype(maxval=max(N, nnz))
469 indptr = np.empty(M + 1, dtype=idx_dtype)
470 indptr[0] = 0
471 np.cumsum(lengths, dtype=idx_dtype, out=indptr[1:])
473 indices = np.empty(nnz, dtype=idx_dtype)
474 data = np.empty(nnz, dtype=self.dtype)
475 _csparsetools.lil_flatten_to_array(self.rows, indices)
476 _csparsetools.lil_flatten_to_array(self.data, data)
478 # init csr matrix
479 return self._csr_container((data, indices, indptr), shape=self.shape)
481 tocsr.__doc__ = _spbase.tocsr.__doc__
484def _prepare_index_for_memoryview(i, j, x=None):
485 """
486 Convert index and data arrays to form suitable for passing to the
487 Cython fancy getset routines.
489 The conversions are necessary since to (i) ensure the integer
490 index arrays are in one of the accepted types, and (ii) to ensure
491 the arrays are writable so that Cython memoryview support doesn't
492 choke on them.
494 Parameters
495 ----------
496 i, j
497 Index arrays
498 x : optional
499 Data arrays
501 Returns
502 -------
503 i, j, x
504 Re-formatted arrays (x is omitted, if input was None)
506 """
507 if i.dtype > j.dtype:
508 j = j.astype(i.dtype)
509 elif i.dtype < j.dtype:
510 i = i.astype(j.dtype)
512 if not i.flags.writeable or i.dtype not in (np.int32, np.int64):
513 i = i.astype(np.intp)
514 if not j.flags.writeable or j.dtype not in (np.int32, np.int64):
515 j = j.astype(np.intp)
517 if x is not None:
518 if not x.flags.writeable:
519 x = x.copy()
520 return i, j, x
521 else:
522 return i, j
525def isspmatrix_lil(x):
526 """Is `x` of lil_matrix type?
528 Parameters
529 ----------
530 x
531 object to check for being a lil matrix
533 Returns
534 -------
535 bool
536 True if `x` is a lil matrix, False otherwise
538 Examples
539 --------
540 >>> from scipy.sparse import lil_array, lil_matrix, coo_matrix, isspmatrix_lil
541 >>> isspmatrix_lil(lil_matrix([[5]]))
542 True
543 >>> isspmatrix_lil(lil_array([[5]]))
544 False
545 >>> isspmatrix_lil(coo_matrix([[5]]))
546 False
547 """
548 return isinstance(x, lil_matrix)
551# This namespace class separates array from matrix with isinstance
552class lil_array(_lil_base, sparray):
553 pass
555lil_array.__doc__ = _lil_base.__doc__
557class lil_matrix(spmatrix, _lil_base):
558 pass
560lil_matrix.__doc__ = _array_doc_to_matrix(_lil_base.__doc__)