6
\$\begingroup\$

The code generates all combinations of filename with underscore _:

def filename_generator(name, path=''):
    names = []

    for i in range(len(name)):
        p = '_'.join([x for x in name[i:]]) + path

        names.append(name[:i] + p)
        names += filename_generator(name[:i], p)

    return sorted(list(set(names)))


for e in filename_generator('longlonglonglonglonglongname'):
    print(e)

Example:

Input:

name

Output:

n_a_m_e
n_a_me
n_am_e
n_ame
na_m_e
na_me
nam_e
name

My code works well, but very slowly. How can I optimize the algorithm?

\$\endgroup\$

migrated from stackoverflow.com Jul 1 '15 at 12:08

This question came from our site for professional and enthusiast programmers.

8
\$\begingroup\$

Note that there are 2n-1 different such names for a string of lengh n, as there can or can not be a _ between any two characters. For your long-long name that makes 134,217,728 variants!

Regardless of what algorithm you use, this will take a very long time. One way to work around this, depending on your actual use case, might be to use a generator function. This way, you do not need to calculate all the variants, if maybe you need just a few of them (maybe just enough to find one that does not yet exist?). For example, like this:

def filename_generator(name):
    if len(name) > 1:
        first, rest = name[0], name[1:]
        for rest2 in filename_generator(rest):
            yield first + rest2
            yield first + "_" + rest2
    else:
        yield name

Output:

>>> list(filename_generator("name"))
['name', 'n_ame', 'na_me', 'n_a_me', 'nam_e', 'n_am_e', 'na_m_e', 'n_a_m_e']

Or, building upon the idea by @jacdeh, using binary numbers to determine where to put a _.

def filename_generator(name):
    d = {"0": "", "1": "_"}
    for n in range(2**(len(name)-1)):
        binary = "{:0{}b}".format(n, len(name))
        yield''.join(d[s] + c for c, s in zip(name, binary))

Or similar, using bit shifting:

def filename_generator(name):
    for n in range(2**(len(name)-1)):
        yield ''.join(c + ("_" if n & 1<<i == 1<<i else "") for i, c in enumerate(name))

However, either both those implementation are pretty lousy, or it does not help much in the end: They are both about 10 times slower than the recursive function, according to timeit.

Here's some timing information, using IPython's %timeit magic method:

In [8]: %timeit filename_generator("longname")         # your original function
1000 loops, best of 3: 610 µs per loop
In [9]: %timeit list(filename_generator1("longname"))  # my recursive generator
10000 loops, best of 3: 22.5 µs per loop
In [10]: %timeit list(filename_generator2("longname")) # my binary generator
1000 loops, best of 3: 322 µs per loop
In [11]: %timeit partition_string("longname")          # Eric's binary function
1000 loops, best of 3: 200 µs per loop

Another possibility, as posted in comments, would be to use itertools.product to generate the "mask", similar to the binary number solution, but with less involved math.

from itertools import product, chain
def filename_generator4(name):
    for mask in product(("_", ""), repeat=len(name) - 1):
        yield ''.join(chain(*zip(name, mask + ("",))))

However, performance is about the same as for the binary solutions. I guess the bottleneck is the number of string concatenations: In the recursive solution, you "reuse" the partial solutions, while each of the latter solutions construct each solution "from scratch", so there are fewer total string concatenation in the recursive case. Not sure, though, so feel free to comment.

\$\endgroup\$
  • \$\begingroup\$ Can you repeat the timeit test with "longlongname" and "longlonglongname"? It would be interesting to get a sense of how these algorithms perform asymptotically. \$\endgroup\$ – Eric Appelt Jun 17 '15 at 13:26
  • \$\begingroup\$ @EricAppelt I tried filename_generator1 and filename_generator2 and both were about 16 times slower per 4 added characters (as could be expected, with 2^4=16 times as many combinations) \$\endgroup\$ – tobias_k Jun 17 '15 at 13:30
  • 1
    \$\begingroup\$ I guess one could also use : combinations_with_replacement(('_', ''), 2) or itertools.product. Not quite sure how it'd behave performance wise. \$\endgroup\$ – Josay Jul 1 '15 at 16:12
  • \$\begingroup\$ @Josay Good idea, much simpler than using binary numbers, but not faster. But maybe that's just a problem with my particular implementation... \$\endgroup\$ – tobias_k Jul 1 '15 at 17:59
2
\$\begingroup\$

This is a good place to use bitwise operations. Following the suggestion by @jacdeh, for a word such as "dogs" one can make a list of binary strings 000, 001, 010, ..., 111, and put underscores wherever there is a one.

However, you don't actually have to do any conversions, the integers from 0 to 2**len(word-1) ARE the binary strings that you want.

So you can just loop over all these integers, and for each integer, loop over the character positions in the string from 0 to len(word-1), and then check if 2**position has any bits in common with your current binary mask using the bitwise &.

Here is an example implementation:

def partition_string(name, delimiter='_'):
    partitions = []
    for mask in xrange(2**(len(name)-1)):
        part = ''
        for pos in xrange(len(name)-1):
            part = part + name[pos]
            if mask & 2**pos != 0:
                part = part + '_'
        part = part + name[len(name)-1]
        partitions.append(part)
    return partitions

for part in partition_string('dogs'):
    print(part)

Output:

dogs
d_ogs
do_gs
d_o_gs
dog_s
d_og_s
do_g_s
d_o_g_s
\$\endgroup\$
0
\$\begingroup\$

The sort in a recursive call is costing you time. This algorithm will be (much) faster:

Count the number of chars in your filename. So nrOfPossiblePositions for a dash equals number of chars - 1. Generate all numbers from 0 - (2 ^ nrOfPossiblePositions) - 1 Convert them to binary and store them in a list. Go through the list, inserting dashes at the position + 1 of the one's in your binary number, working backwards through your filename.

so e.g. 101010 means e_xa_mp_le

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you provide an actual implementation for this? I tried two ways to implement this (see my answer), but both turned out to be way slower... \$\endgroup\$ – tobias_k Jun 17 '15 at 12:47

Your Answer

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