5
\$\begingroup\$

I'm trying to run the method below against a very large corpus and I need to optimize/reduce the run time for this method as it already takes up about 6 seconds to execute.

Requirements:

  1. Check the word only consist of alphabets, hyphen and apostrophe
  2. First character of word must be alphabet
  3. Last character of word must be alphabet or apostrophe only
  4. Use of re library (regex) strictly not allowed

def delUnknownChar(w):
    wf = []
    for c in w:
        if (c == "'" or c == "-" or c.isalpha()):
            wf.append(c)

    w = "".join(wf)
    wf.clear()

    if (len(w) > 1):
        while(not w[0].isalpha()):
            w = w[1:]

        while (w[-1] == "-"):
            w = w[:-1]

        return w
    else:
        return None

string1 = delUnknownChar("-'test'-")
print(string1)

Output will be test' The code above will take about 5 seconds to run.

If I change lines 2-7 of the code to this line:

w = "".join(c for c in w if c == "'" or c == "-" or c.isalpha())

The runtime somehow increases by 1 more second.

Does anyone here have a better idea or an improved optimized way to check for this at a much faster speed?

\$\endgroup\$
2
  • \$\begingroup\$ If that exact program takes 5 s to run, I suppose your Python takes 5 s to start, for some reason. Or, did you mean it takes 5 s to run it for all words in your corpus? \$\endgroup\$ Nov 7 '14 at 19:12
  • \$\begingroup\$ 50k calls to the same func is done in ~2.3 seconds: repl.it/38c \$\endgroup\$
    – jsanc623
    Nov 7 '14 at 21:49
2
\$\begingroup\$

Possible performance improvements

  • w = w[:-1] is probably inefficient since it asks to perform a copy of every element of the list minus one. del w[-1] is the idiomatic way to delete the last element of a list.

  • You probably have more characters in a string corresponding to isalpha than characters exactly equal to "'" or "-". Therefore, you may notice speed improvements by checking isalpha before the other two conditions.

  • You could create a table containing all the values of isalpha plus "'" and "*" and then check whether a character is in this table. However, I don't think that it can bring you significant speed improvements, unless you filter with a dedicated str method that may be optimized (replace for example).

Style

A few notes about style:

  • Please, don't put parenthesis around the while condition, that goes against the Python style guide (PEP8).

  • Same goes for if.

\$\endgroup\$
4
  • \$\begingroup\$ Hi @Morwenn, thanks for the tip! Oops I just realized that I made that mistake (too used in programming c# and java lol) I tried to adopt first point you mentioned which is del but the word processed is of string type and not list type. For the second point yes it makes perfect sense! Oh my why didn't I think of that hah! Gonna attempt the last point now \$\endgroup\$ Nov 8 '14 at 3:23
  • 1
    \$\begingroup\$ By moving isalpha to the front of the condition, time saved was about 1.5sec! wow! \$\endgroup\$ Nov 8 '14 at 3:26
  • \$\begingroup\$ @python1010101 Bottom line: when you need speed and have a lot of conditions, try to check for the most common case first :) \$\endgroup\$
    – Morwenn
    Nov 8 '14 at 11:26
  • \$\begingroup\$ is testing c in ('-','*') any faster than the two explicit tests? \$\endgroup\$
    – pjz
    Nov 10 '14 at 4:13
1
\$\begingroup\$
while(not w[0].isalpha()):
    w = w[1:]

By the time execution reaches this piece of code, all characters that are not alphabetic or -' are already removed. So at this point, instead of checking not .isalpha, it will be more efficient to check if the character is - or ' like this:

while w[0] == "'" or w[0] == '-':
    w = w[1:]

The name of the method is not great. delUnknownChar sounds like "delete unknown characters", but that doesn't describe very well what this method does. Your requirements are more complex than just removing characters. Something like sanitize_text, or normalize_input would be better.


The variable names w and wf are not great:

  • letters instead of wf would be better
  • word instead of w would be better

There is a requirement you forgot to include in your description: the word must be longer than 1 character.

You should add the requirements as the docstring of the method.

\$\endgroup\$
1
  • \$\begingroup\$ Indeed you make a point there!(: Thanks for the improvements. I will add them in! \$\endgroup\$ Nov 8 '14 at 3:32
0
\$\begingroup\$

All of this depends very much on your input, so assuming you have full Unicode input and therefore can't use str.translate or any other of the C-based functions, which would probably be way faster, (or rewrite in a different implementation/language) I'd first rewrite to:

def delUnknownChar(w):
    w = [c for c in w if c == "'" or c == "-" or c.isalpha()]

    if len(w) == 0:
        return None

    for i in range(len(w)):
        if w[i].isalpha():
            w = w[i:]
            break

    for i in range(len(w)-1, -1, -1):
        if w[i] != "-":
            w = w[:i+1]
            break

    return "".join(w)

So first find the valid range, then do the subscript once and also do the conversion to a string only once. Not much of a speedup I'm afraid.

The other attempt was to do the same but more radically, essentially avoiding unnecessary conversion:

def deleteUnknownCharacters(word):
    l = len(word)

    start = None
    for i in range(l):
        if word[i].isalpha():
            start = i
            break

    if start == None:
        return None

    end = None
    for i in range(l-1, -1, -1):
        c = word[i]
        if c == "'" or c.isalpha():
            end = i
            break
        elif i <= start:
            break

    if start == None:
        return None

    result = [c for c in word[start:end+1] if c == "'" or c == "-" or c.isalpha()]

    if len(result) == 0:
        return None

    return "".join(result)

This can be faster depending on your input and is otherwise somewhat equal from what I can tell.

\$\endgroup\$
0
\$\begingroup\$

The answer is:

Use C, even if it takes some setup:

def delUnknownChar(w):
    badchars = ''.join( c for c in set(w) if not c.isalpha() and not c in ("'", "-") )                                                                               
    w = w.translate(None, badchars)

    if len(w) == 0:
        return None

    for i in range(len(w)):
        if w[i].isalpha():
            w = w[i:]
            break

    for i in range(len(w)-1, -1, -1):
        if w[i] != "-":
            w = w[:i+1]
            break

    return "".join(w)

Note that this depends heavily on the variety in your corpus, but that given a reasonable .isalpha() function it should even work with unicode. Also: much credit to @ferada, from whom I cribbed all but the first two lines of this function.

\$\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.