Efficiently check if an array is jagged

Perhaps not the most efficient but it works nicely in numpy. and will short circuit as soon as one of the conditions is False. If the first three conditions are True, we have no choice but to iterate through the rows.

Thankfull, all will shortcircuit as soon as one of the iterations is False so it won't check all the rows if it doesn't have to.

def jagged(x):
    x = np.asarray(x)
    return (
        x.dtype == "object"
        and x.ndim == 1
        and isinstance(x[0], list)
        and not all(len(row) == len(x[0]) for row in x) 
    )

If you wan't to squeeze more efficieny out, it's actually performing the len(x[0]) every iteration of the all part but this is probably inconsequential and this is a lot more legible than the alaternative which would have you write out the whole if statement.

First what you show are lists, not arrays (but more on that later):

In [305]: alist1 = [[1, 2], [3, 4, 5]]                                                   
In [306]: alist2 = [[1, 2], [3, 4], [5, 6], [[7], [8]]]                                  

Mixed len at the first level is a simple and obvious test

In [307]: [len(i) for i in alist1]                                                       
Out[307]: [2, 3]

but it's not enough with the 2nd example:

In [308]: [len(i) for i in alist2]                                                       
Out[308]: [2, 2, 2, 2]

Making an array from list1 produces a 1d object dtype:

In [310]: np.array(alist1)                                                               
Out[310]: array([list([1, 2]), list([3, 4, 5])], dtype=object)

list2 is 2d, but still object dtype:

In [311]: np.array(alist2)                                                               
Out[311]: 
array([[1, 2],
       [3, 4],
       [5, 6],
       [list([7]), list([8])]], dtype=object)

np.array is not the most efficient tool; while compiled, it does have to evaluate the nest list at least down to the level where it finds the discrepency.

If the list isn't ragged, at any level, the result is a numeric dtype:

In [321]: alist3 = [[1, 2], [3, 4], [5, 6], [7, 8]]                                      
In [322]: np.array(alist3)                                                               
Out[322]: 
array([[1, 2],
       [3, 4],
       [5, 6],
       [7, 8]])

If the list elements are arrays, there can be a further result - a broadcasting error. This is results when the first dimensions match, but the differences are in the lower level(s).

In sum, if it is already a numpy array, then object is a good indicator, especially if you were expecting a numeric dtype. If the lowest level elements might themselves be objects (other than lists) this won't help. In both the list1 and list2 cases, some or all of the lowest level elements are objects - lists.

If it's a list of lists, then recursive evaluation of the len is probably the way to go. But only time tests can prove that this is better than np.array(alist).

Apologies if I phrased the question too vaguely, but I need a solution much more general than only for the given (list of integer list) examples.

I'm still guessing there might be a better solution, but here is a significant improvement that definitely does not duplicate the input in memory:

def really1d(arr):
    if np.ndim(arr) != 1:
        return False
    if len(arr) == 0:
        return True
    if np.any(np.vectorize(np.ndim)(arr)):
        return False
    return True


def flatlen(arr):
    # NOTE: If you know your base types are NOT iterable (e.g. not `str`, or `dict`, etc)
    # Then you might be able to get away with:
    # if not np.iterable(arr):

    # This will work for my cases (catching possible `str` and `dict` types)
    if np.isscalar(arr) or isinstance(arr, dict):
        return 1

    if really1d(arr):
        return len(arr)

    return np.sum([flatlen(aa) for aa in arr])


def isjagged(arr):
    if np.isscalar(arr) or (np.size(arr) == flatlen(arr)):
        return False
    return True

Here's a different way to approach to the problem. It aims for a bit more generality (no numpy assumptions) and code simplicity. It ignores the efficiency issue that you raised a few times: it does not flatten or copy the data, but it does contruct a parallel data structure to make the test for jaggedness easy.

def simplified(xs):
    # Takes a value and returns it in recursively simplfied form.
    # Array-like values (list, tuple, str) become tuples.
    # All other values (and single characters) become None.
    if isinstance(xs, (list, tuple)):
        return tuple(simplified(x) for x in xs)
    elif isinstance(xs, str):
        return tuple(None for x in xs)
    else:
        return None

def is_jagged(xs):
    # Takes a simplified value.
    # Non-jagged structures will have the same form at the top level.
    return len(set(xs)) > 1

Demo:

tests = (
    # Non-jagged.
    (False, []),
    (False, [[], [], []]),
    (False, [1, 2, 3]),
    (False, [[1, 2], [3, 4]]),
    (False, [[1, 2], [3, 4], [5, 6], [7, 8]]),
    (False, ('ab', 'cd')),
    (False, (['ab', 'cd', 'ef'], ('gh', 'ij', 'kl'))),
    # Jagged.
    (True, [1, 2, [3, 4]]),
    (True, [[1, 2], [3, 4, 5]]),
    (True, [[1, 2], [3, 4], [5, 6], [[7], [8]]]),
    (True, ('ab', 'cdefg')),
)
fmt = '\nInput:      {}\nSimplified: {}\nIs jagged:  {} [{}]'
for exp, xs in tests:
    sim = simplified(xs)
    isj = is_jagged(sim)
    msg = fmt.format(xs, sim, isj, 'ok' if isj == exp else 'DOH')
    print(msg)

Output:

Input:      []
Simplified: ()
Is jagged:  False [ok]

Input:      [[], [], []]
Simplified: ((), (), ())
Is jagged:  False [ok]

Input:      [1, 2, 3]
Simplified: (None, None, None)
Is jagged:  False [ok]

Input:      [[1, 2], [3, 4]]
Simplified: ((None, None), (None, None))
Is jagged:  False [ok]

Input:      [[1, 2], [3, 4], [5, 6], [7, 8]]
Simplified: ((None, None), (None, None), (None, None), (None, None))
Is jagged:  False [ok]

Input:      ('ab', 'cd')
Simplified: ((None, None), (None, None))
Is jagged:  False [ok]

Input:      (['ab', 'cd', 'ef'], ('gh', 'ij', 'kl'))
Simplified: (((None, None), (None, None), (None, None)), ((None, None), (None, None), (None, None)))
Is jagged:  False [ok]

Input:      [1, 2, [3, 4]]
Simplified: (None, None, (None, None))
Is jagged:  True [ok]

Input:      [[1, 2], [3, 4, 5]]
Simplified: ((None, None), (None, None, None))
Is jagged:  True [ok]

Input:      [[1, 2], [3, 4], [5, 6], [[7], [8]]]
Simplified: ((None, None), (None, None), (None, None), ((None,), (None,)))
Is jagged:  True [ok]

Input:      ('ab', 'cdefg')
Simplified: ((None, None), (None, None, None, None, None))
Is jagged:  True [ok]

There is a super simple way that can be done in a line.. just one line. It's not perfect, but it's super simple.

You can do that using np.array. If all elements of the nested-list have the same shape, the dimensions of the resulting array will be more than one dimension. But if just one element has a different number of elements, the returned array will be of one dimension.

See this example for more understanding:

>>> import numpy as np
>>> lst = [[1, 2], [3, 4, 5]]
>>> arr = np.array(lst)
>> arr.shape
(2,)
>>> arr.dtype
object

>>> lst = [[0, 1, 2], [3, 4, 5]]
>>> arr = np.array(lst)
>>> arr.shape
(2, 3)
>>> arr.dtype
int64

So, your function will be written in just one line like so:

def isjagged(lst):
    return len(np.array(lst).shape) == 1

NOTE: Of course this will only work on nested-lists

EDIT

As said by @Ch3steR, this solution will work with simple nested-list and it won't work for a little bit complicated ones like this one: [[1, 2], [3, 4], [5, 6], [[7], [8]]].

So, I think this could be a nicer solution:

def isjagged(lst):
    return np.array(lst).dtype == 'object'