11
\$\begingroup\$

I have the following problem statement:

Modify a given list such that one specific element is "weaved" into that list.

Examples if the element is 'module':

  • [] remains []
  • ['a'] remains ['a']
  • ['a', 'b'] becomes ['a', 'module', 'b']
  • ['a', 'b', 'c'] becomes ['a', 'module', 'b', 'module', 'c']

I solved it using the following code in Python 3.4:

@staticmethod
def __weave_element_into_list(element, values: list) -> list:
    """
    Weaves an element into a given list.

    Examples if the element is 'module':
     - Input [] remains [].
     - Input ['a'] remains ['a'].
     - Input ['a', 'b'] becomes ['a', 'module', 'b'].
     - Input ['a', 'b', 'c'] becomes ['a', 'module', 'b', 'module', 'c'].
     - etc.

    :param element: The element to weave into the list
    :param values:  The original list
    :return:    The list with element weaved into it.
    """
    copy_list = list(values)
    if len(copy_list) <= 1:
        return copy_list
    i = 1
    while i < len(copy_list):
        copy_list.insert(i, element)
        i += 2
    return copy_list

Is there a better (more Pythonic?) solution to it and is "weaving" the correct operation here?

\$\endgroup\$
  • 1
    \$\begingroup\$ Where's the rest of the class? What context is this used in? \$\endgroup\$ – jonrsharpe May 31 '15 at 12:33
11
\$\begingroup\$

The function could be replaced with this line:

return list(chain.from_iterable(zip(values, [element] * len(values))))[:-1]

Essentially, zipping values with another list of the same size containing element in all values, flattening the zip, and chopping off the end.

About your original implementation, instead of this:

if len(copy_list) <= 1:
    return copy_list

This is more Pythonic:

if not copy_list:
    return copy_list

I'm also wondering if this needs to be a @staticmethod. Since it's a pure function, I'd just call it weave. Here's the complete implementation with doctests:

from itertools import chain


def weave(element, values: list) -> list:
    """
    >>> weave('module', [])
    []
    >>> weave('module', ['a'])
    ['a']
    >>> weave('module', ['a', 'b'])
    ['a', 'module', 'b']
    >>> weave('module', ['a', 'b', 'c'])
    ['a', 'module', 'b', 'module', 'c']

    :param element: The element to weave into the list
    :param values: The original list
    :return: The list with element weaved into it.
    """
    return list(chain.from_iterable(zip(values, [element] * len(values))))[:-1]

I see @jonrsharpe beat me to the doctests. To add something new, another way to run doctests:

python -m doctest yourfile.py

Update

Originally I proposed this one-liner:

return sum(zip(values, [element] * len(values)), ())[:-1]

But that turns out to be a bad idea. This other discussion is also illuminating.

\$\endgroup\$
  • \$\begingroup\$ Using sum(lst, ()) instead of flatten borders on obfuscation \$\endgroup\$ – Caridorc May 31 '15 at 21:06
  • 1
    \$\begingroup\$ @Caridorc you're absolutely right, thanks for picking on it. I updated my post with a different solution, and some related links at the bottom. \$\endgroup\$ – janos May 31 '15 at 21:30
  • \$\begingroup\$ Consider zip_longest(values, repeat(element, max(len(values) - 1, 0))) — this avoids the unnecessary allocation of the list of elements, and it avoids the unnecessary copy due to the [:-1]. \$\endgroup\$ – Gareth Rees Jun 1 '15 at 13:44
7
\$\begingroup\$

Firstly, you can make the examples into doctests, so that you can actually run them to check the function works:

class Class:  # or whatever it's called

    @staticmethod
    def __weave_element_into_list(element, values: list) -> list:
        """
        Weaves an element into a given list.

        Examples:

            >>> Class._Class__weave_element_into_list('module', [])
            []
            >>> Class._Class__weave_element_into_list('module', ['a'])
            ['a']
            >>> Class._Class__weave_element_into_list('module', ['a', 'b'])
            ['a', 'module', 'b']
            >>> Class._Class__weave_element_into_list('module', ['a', 'b', 'c'])
            ['a', 'module', 'b', 'module', 'c']

        :param element: The element to weave into the list
        :param values: The original list
        :return: The list with element weaved into it.
        """
        copy_list = list(values)
        if len(copy_list) <= 1:
            return copy_list
        i = 1
        while i < len(copy_list):
            copy_list.insert(i, element)
            i += 2
        return copy_list


if __name__ == '__main__':
    import doctest
    doctest.testmod()

Now, note how awkward it is to have to call Class._Class__weave_element_into_list, due to the "name mangling" invoked by the leading double underscore in the method name. Per the style guide, this should only be used:

To avoid name clashes with subclasses

instead if you want the method to be considered 'private':

Use one leading underscore only for non-public methods and instance variables.

Without seeing the rest of your code it's also hard to say why you've made this a method, rather than just a standalone function.


Your weave operation works exactly like the join method for str:

>>> ' module '.join('')
''
>>> ' module '.join('a')
'a'
>>> ' module '.join('ab')
'a module b'
>>> ' module '.join('abc')
'a module b module c'

so perhaps that would be a better term to adopt for it.

\$\endgroup\$
  • 2
    \$\begingroup\$ I don't understand why you are bothering with a class at all... in Python, it is perfectly fine for a function to just be a function. \$\endgroup\$ – Adam Jun 1 '15 at 3:45
  • 1
    \$\begingroup\$ @codesparkle that's a better comment for the OP than for me! \$\endgroup\$ – jonrsharpe Jun 1 '15 at 6:15
7
\$\begingroup\$

Haskell calls this function intersperse.

In Python, loops where you manually increment the index tend to be awkward. I propose the following solution:

import itertools

def intersperse(element, iterable):
    def alternation():
        for item in iterable:
            yield element
            yield item
    return list(itertools.islice(alternation(), 1, None))

islice() is just a handy way to drop the first element of the result. You could also write it this way without itertools:

def intersperse(element, iterable):
    def alternation():
        for item in iterable:
            yield element
            yield item
    result = alternation()
    next(result, None)
    return list(result)

Your __weave_element_into_list() has a scalability problem: inserting elements into the middle of a list requires a lot of work to shift all subsequent items. The weave() function proposed in Rev 2 of @janos's answer involved even more copying, since tuples are immutable; the revision in Rev 3 has much better performance characteristics.

Benchmark:

import timeit

functions = ('intersperse', 'weave2', 'weave3', '__weave_element_into_list')
print('length  ' + ' '.join('{:12s}'.format(f) for f in functions))
for length in [0, 1, 10, 100, 1000, 10000]:
    print('{0:6d}  '.format(length) +
          ' '.join('{: >3.10f}'.format(
              timeit.timeit("f('alligator', range({}))".format(length),
                            setup="from __main__ import {} as f".format(f),
                            number=100)) for f in functions))

Result:

length  intersperse  weave2       weave3       __weave_element_into_list
     0  0.0002215109 0.0001669568 0.0002566511 0.0000781892
     1  0.0002748552 0.0002680188 0.0003487850 0.0001115086
    10  0.0003961320 0.0003857883 0.0004681549 0.0005727541
   100  0.0019150120 0.0054596220 0.0015901779 0.0048249909
  1000  0.0183790531 0.3636222179 0.0120774899 0.0711144698
 10000  0.1597181219 41.7615168821 0.1375140301 3.6747105517
\$\endgroup\$

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.