numpy sparse array for ragged arrays

[zeffii]

faux sparse might work for numba, not tried.

from sverchok.utils.console_print import console_print as prin
import numpy as np

m = [[0, 1, 2], [0, 1, 2, 3, 4], [4, 5, 6], [0, 4, 5, 6, 7, 8]]

def get_max_dims(array):
    """ return num rows and length of longest row """
    return len(array), max(map(len, array))

def make_sparse_nan_matrix(array):
    f = get_max_dims(m)
    M = np.full(f, np.nan)

    for idx, x in enumerate(M):
        rsize = len(m[idx])
        M[idx][:rsize] = m[idx]
    return M

prin(make_sparse_nan_matrix(m))

prints

[[ 0.  1.  2. nan nan nan]
 [ 0.  1.  2.  3.  4. nan]
 [ 4.  5.  6. nan nan nan]
 [ 0.  4.  5.  6.  7.  8.]]

[zeffii]

import functools
import operator
import numpy as np
from dataclasses import dataclass

m = [[0, 1, 2], [0, 1, 2, 3, 4], [4, 5, 6], [0, 4, 5, 6, 7, 8]]

@dataclass
class PolyList(list):
    array: list

    def get_max_dims(self):
        """ return num rows and length of longest row """
        return len(self.array), max(map(len, self.array))

    @property
    def loops(self):
        flat = np.array(functools.reduce(operator.iconcat, self.array, []))
        
        start_indices, end_indices = [], []
        add_start, add_end = start_indices.append, end_indices.append
        
        sum_state = 0
        for row in self.array:
            add_start(sum_state)
            sum_state = sum_state + len(row)
            add_end(sum_state)

        return flat, np.vstack((start_indices, end_indices)).T
    
    @property
    def sparse_matrix(self):
        f = self.get_max_dims()
        M = np.full(f, np.nan)

        for idx, x in enumerate(M):
            rsize = len(m[idx])
            M[idx][:rsize] = m[idx]
        return M
            
        
mpl = PolyList(m)
prin(mpl.sparse_matrix)
flatlist, starts_ends = mpl.loops
prin(starts_ends)    

for idx_range in np.nditer(starts_ends.T, flags=['external_loop'], order='F'):
    prin(flatlist[idx_range[0]:idx_range[1]])

shows

[[ 0.  1.  2. nan nan nan]
 [ 0.  1.  2.  3.  4. nan]
 [ 4.  5.  6. nan nan nan]
 [ 0.  4.  5.  6.  7.  8.]]

[[ 0  3]
 [ 3  8]
 [ 8 11]
 [11 17]]

[0 1 2]
[0 1 2 3 4]
[4 5 6]
[0 4 5 6 7 8]

the nan-padded matrix allows running np.apply_along_axis(my_function, axis=1, arr=my_matrix))

[zeffii]

def my_function(row):
    row_without_nans = row[~np.isnan(row)]
    return sum(row_without_nans)

k = np.apply_along_axis(my_function, axis=1, arr=mpl.sparse_matrix)
prin(k)

[Durman]

It would be nice to have some practice simple example which would use the data structure, probably something like an analyzer function wich calculates face areas or something like that, and to make comparison of performance between current Python implementation and new one.

[zeffii]

yeah and it would make a difference whether the polygon list has:

• all triangles
• all quads
• mostly triangles and some quads
• mostly quads and some triangles
• triangles / quads / ngons (in various distributions.. including mostly pentagons and one giant 20gon or something)

leads me to think a composite datatype would also be worth experimenting with, sorting the polygon indices by length, then making CompositePolyList(mixed_polygons) . While we put a lot of effort in preserving index consistency, clearly there are usecases/objects that don't need it, and there are nodes which don't do this, (or can't sanely do this without performance penalty), it can be optional depending on the situation.

mixed = CompositePolyList(mixed_polygons)
mixed.tris
mixed.quads
mixed.ngons  #PolyList
mixed.index_remapper

it would need to produce considerable speedup, and must offer built-in convenience functions for iteration/applying functions, but then for true convenience i'd probably want to pass coordinates too, resulting in a SvMeshObject class/and socket. We always seem to come back to this.