3
\$\begingroup\$

Goal: find total number of elements in a nested iterable of arbitrary depth. My shot:

import numpy as np

def deeplen(item, iterables=(list, tuple, dict, np.ndarray)):
    # return 1 and terminate recursion when `item` is no longer iterable
    if isinstance(item, iterables):
        if isinstance(item, dict):
            item = item.values()
        return sum(deeplen(subitem) for subitem in item)
    else:
        return 1

Naturally there are more iterables than shown, but these cover the vast majority of use cases; more can be added, with per-istance treatment if needed (e.g. dict), so the approach is extendable.

Any better approaches? Can be in: (1) performance; (2) readability; (3) generality (more iterables)


Performance test:

def test_deeplen(iters=200):
    def _make_bignest():
        arrays = [np.random.randn(100, 100), np.random.uniform(30, 40, 10)]
        lists = [[1, 2, '3', '4', 5, [6, 7]] * 555, {'a': 1, 'b': arrays[0]}]
        dicts = {'x': [1, {2: [3, 4]}, [5, '6', {'7': 8}] * 99] * 55,
                 'b': [{'a': 5, 'b': 3}] * 333, ('k', 'g'): (5, 9, [1, 2])}
        tuples = (1, (2, {3: np.array([4., 5.])}, (6, 7, 8, 9) * 21) * 99,
                  (10, (11,) * 5) * 666)
        return {'arrays': arrays, 'lists': lists,
                'dicts': dicts, 'tuples': tuples}

    def _print_report(bignest, t0):
        t = time() - t0
        print("{:.5f} / iter ({} iter avg, total time: {:.3f}); sizes:".format(
            t / iters, iters, t))
        print("bignest:", deeplen(bignest))
        print(("{} {}\n" * len(bignest)).format(
            *[x for k, v in bignest.items()
              for x in ((k + ':').ljust(8), deeplen(v))]))

    bignest = _make_bignest()
    t0 = time()
    for _ in range(iters):
        deeplen(bignest)
    _print_report(bignest, t0)
>> test_deeplen(1000)
0.02379 / iter (1000 iter avg, total time: 23.786); sizes:
bignest: 53676
arrays:  10010
lists:   13886
dicts:   17170
tuples:  12610
\$\endgroup\$
5
\$\begingroup\$

A possible solution can be implemented in terms of two different paradigms.

Look Before You Leap (LBYL)

You can test if an object supports a certain interface using collections.abc, where abc stands for Abstract Base Classes. The module provides the Iterable class. If an object is an instance of that class, it can be considered iterable. How the object handles this under the hood, we do not care for. This can be used to test for iterables.

Secondly, there is Mapping to detect types like dicts. This can go where you currently test for isinstance(item, dict).

Checking if an object supports what you plan on doing to or with it is the Look Before You Leap style. Unfortunately, this approach is slower than before. However, the loss in performance is justifiable in the face of the gained value. You can now support any iterable anyone can throw at you, and shift the responsibility of handling the actual iteration to them. Otherwise, you would have to add every conceivable iterable to iterables=(..). You already noticed that this is not feasible.

from collections.abc import Iterable, Mapping

def deeplen_lbyl(item):
    """Returns the number of non-iterable items in arbitrarily nested iterators.
    """
    if isinstance(item, Iterable) and not isinstance(item, str):
        if isinstance(item, Mapping):
            item = item.values()
        return sum(deeplen_lbyl(subitem) for subitem in item)
    else:
        return 1

Easier to ask for forgiveness than permission (EAFP)

This is an alternative approach, relying on just going ahead and letting things fail, then catching expected errors and handling them. It is often considered the Pythonic one. Its large advantage is its flexibility. If there is a large number of both allowed and disallowed situations, adding all allowed situations to some sort of whitelist (like isinstance) can be tedious. This is where the ABCs helped in the LBYL style above. The EAFP style does not rely on ABCs or probing for interfaces.

def deeplen_eafp(item):
    """Returns the number of non-iterable items in arbitrarily nested iterators.
    """
    try:
        iter(item)
    except TypeError:
        return 1

    if isinstance(item, str):
        return 1

    try:
        item = item.values()
    except AttributeError:
        pass

    return sum(deeplen_eafp(subitem) for subitem in item)

In the Iterable class description, it says that calling iter is the only save way of detecting an iterable. So this is what is done here. Note that there is also a different viewpoint to that.

TypeError is raised if the object did not like being iterated over.

Now, str passes both isinstance and iter checks, so the guard clause is needed here, too. It is required to avoid infinite recursion, since str would remain infinitely iterable.

If the values() attribute is not available, a Mapping-like object is not present. Accordingly, AttributeError is raised, and we keep the original item.

Performance

Python has, unlike other languages, cheap error handling. A try block is cheap if it does not raise an exception. However, the more we run into walls blindly, the more errors are thrown out the behind in the try blocks. This is slowing that approach down.


I did not touch your test_deeplen function. Using it, all three (yours and the two presented here) functions return the same output.

deeplen_lbyl and deeplen_eafp are equally slower than your function, in the ballpark:

deeplen_lbyl:
  0.02510 / iter (10 iter avg, total time: 0.251); sizes:
  bignest: 53676
  arrays:  10010
  lists:   13886
  dicts:   17170
  tuples:  12610

deeplen_eafp:
  0.02497 / iter (10 iter avg, total time: 0.250); sizes:
  bignest: 53676
  arrays:  10010
  lists:   13886
  dicts:   17170
  tuples:  12610

deeplen from question:
  0.01695 / iter (10 iter avg, total time: 0.170); sizes:
  bignest: 53676
  arrays:  10010
  lists:   13886
  dicts:   17170
  tuples:  12610
\$\endgroup\$
7
  • 1
    \$\begingroup\$ Quality answer. Follow-up: how do we know if "any" iterable will be accounted for correctly? Can't one make a custom type that is like dict in that, when iterated over, doesn't return 'values' - but unlike dict, values can't be accessed via .values()? \$\endgroup\$ – OverLordGoldDragon May 4 '20 at 20:13
  • \$\begingroup\$ Good question, I had similar concerns. I believe that the test for isinstance(..., Mapping) is not passed if values is not available in the first place. Having a mapping but not implementing the callable values attribute seems strange. I urge you to ask a new question about this! \$\endgroup\$ – Alex Povel May 5 '20 at 10:40
  • 1
    \$\begingroup\$ From a real use-case: arrays can be quite expensive for all our deeplen versions; the following gives a big speedup: if isinstance(item, np.ndarray): return item.size. (P.S. I ultimately went with your LBYL, for its clarity and generality) \$\endgroup\$ – OverLordGoldDragon May 18 '20 at 1:28
  • 1
    \$\begingroup\$ @OverLordGoldDragon On my machine, running it with 1000 does not change anything, and the relations between the three remain the same, see also here: repl.it/repls/SevereHonorableRelationalmodel \$\endgroup\$ – Alex Povel May 22 '20 at 13:30
  • 1
    \$\begingroup\$ Strange, I've even benchmarked on a Colab VM CPU - guess 'vanilla' does win on some machines after all. I originally included _deeplen_fast and _deeplen_full, former accessible via deeplen(fast=True) but dropped it after new benchmarks - guess it's an option worth noting. \$\endgroup\$ – OverLordGoldDragon May 22 '20 at 14:01
2
\$\begingroup\$

Below is a faster and more general algorithm than in posted alternatives:

import numpy as np
from collections.abc import Mapping

def deeplen(item):
    if isinstance(item, np.ndarray):
        return item.size
    try:
        list(iter(item))
    except:
        return 1
    if isinstance(item, str):
        return 1
    if isinstance(item, Mapping):
        item = item.values()
    return sum(deeplen(subitem) for subitem in item)

Advantages:

  1. Speed: .size for Numpy arrays is much faster than recursive-iterative len. Also, there isn't much performance difference between the original deeplen and current deeplen (if excluding .size advantage), but deeplen_lbyl is slowest by 40% (tested w/ iters=1000 on bignest).

  2. Generality: neither isinstance(, Iterable) nor try-iter are sufficient to determine whether item is 'truly' iterable; some objects (e.g. TensorFlow Tensor) support creating generators but not consuming them without dedicated methods for iterating. It does become a question of whose len we're measuring, since an arbitrarily-sized Tensor will count as 1 per above algorithm - if this isn't desired, then object-specific treatment is required.

Credit to @AlexPovel for originally suggesting try-iter and isinstance(, Mapping).

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Interesting! I know nothing of Tensor, but it not responding to the iter built-in is strange (as it's "the only reliable way to determine whether an object is iterable". But there's perhaps a reason I am unaware of. \$\endgroup\$ – Alex Povel May 22 '20 at 13:35
  • 1
    \$\begingroup\$ @AlexPovel Update #3 here gives some explanation; TL;DR - just like list and dict have different "access specifiers" (__getitem__), a Tensor has one of its own that has no Pythonic equivalent (not bracket-able), requiring a method. list(iter()) ensures item is Python-iterable - and if it isn't, deeplen will have trouble. \$\endgroup\$ – OverLordGoldDragon May 22 '20 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.