3
\$\begingroup\$

I need to filter Turkish words according to vovel alternation rules. For example -ler is plural but can have form of -lar thus I use metaphonemes for these transitive allomorphs as vovel_dict in my algorithm.

There is only one condition not to alternate vovel it's 'ken' which excluded. I wrote this but it takes too much runtime do you have any suggestions?

def char_filter(morph):
    char_dict = {'d': 'D', 't': 'D', 'a': 'A', 'e': 'A', 'ı': 'H', 'i': 'H', 'u': 'H', 'C': 'C', 'g': 'G', 'k': 'G'}
    res = []
    res1 = []
    flag = []

    if 'ken' in morph:
        flag.append([morph.rindex('ken'), ['k','e','n']])

    for i in morph:
        res2 = i
        if i in char_dict:
            res2 = i.upper()
        res1.append(res2)

    if len(flag) > 0:
        for z in flag:
            res1[z[0]:z[0]+3] = z[1]
    res.append(string.join(res1, sep=''))
    return res[0]
\$\endgroup\$
7
\$\begingroup\$

Naming

res, res1, res2? These names convey absolutely no meaning. flag? Sounds like some sort of boolean value to me; but you assign it a list. i, z? one-letter variable names are essentially used for integer indices, not characters or… what is z already… oh, a list.

Even morph sounds badly chosen, I’m laking a bit of context here to fully understand it, I guess, but I would have used origin_string or something alike.

Control flow

if len(flag) > 0:
    for z in flag:
        # do something

is twice as much complicate than it should be. Once because if len(flag) > 0 can be written if flag: empty container are considered False in a boolean context. And once again because the if is not needed: for z in flag will be a no-op if flag is an empty container.

Also, since you’re not modifying morph and the only thing you store in flag (if any) is [morph.rindex('ken'), ['k','e','n']], why not get rid of flag and directly use that list in the last part of your computation?

def char_filter(morph):
    char_dict = {'d': 'D', 't': 'D', 'a': 'A', 'e': 'A', 'ı': 'H', 'i': 'H', 'u': 'H', 'C': 'C', 'g': 'G', 'k': 'G'}
    res = []
    res1 = []

    for i in morph:
        res2 = i
        if i in char_dict:
            res2 = i.upper()
        res1.append(res2)

    if 'ken' in morph:
        i = morph.rindex('ken')
        res1[i:i+3] = ['k','e','n']
    res.append(string.join(res1, sep=''))
    return res[0]

Data structures

Most of the data structures you use are not suited to your needs. Why storing only one string as the first item of res if you extract it right after having assigned it. Store the string directly in res intead of res[0]. Better: do not use res and return the string right after building it, you’re not making any other use of res anyway:

return ''.join(res1)

Also note the prefered syntax for join which is an operator of the separator string.

You’re also building a dictionary in char_dict but never using the values stored into it, only checking for the existence of keys. Two possibilities:

  • either you have a bug and need to use res2 = char_dict[i] instead of res2 = i.upper();
  • or you just need to simplify the data structure and only store the characters that you want to test against. A list, a string or a set are better fit for this task.

I will consider the second option.

The last thing to note is that this collection will not be changed between calls so we can safely define it outside of the function to avoid building a new one each time we call char_filter.

A little bit on pythonic constructs

some_list = []
for variable in some_collection:
    value = some_function(variable)
    some_list.append(value)

Is better written with a list-comprehension: more readable and faster.

some_list = [some_function(variable) for variable in some_collection]

Proposed improvements

SPECIAL_CHARS = 'dtaeıiuCgk'

def char_filter(origin_string):
    filtered_letters = [char.upper() if char in SPECIAL_CHARS else char
                        for char in origin_string]

    if 'ken' in origin_string:
        i = origin_string.rindex('ken')
        filtered_letters[i:i+3] = ['k','e','n']

    return ''.join(filtered_letters)
\$\endgroup\$
  • \$\begingroup\$ Thanks for your proposal, I already did some improvements on i.upper() as you suggested. I'm gonna implement your proposed improvement and share the runtime difference in 3 days because a 10000 iteration on huge data still processing and this is a small and most slow part of it. \$\endgroup\$ – Skumyol Nov 15 '15 at 16:21
  • \$\begingroup\$ I think in this case dict is better then str, as SPECIAL_CHARS's data type. Where set is the best. As set and dict both have \$O(1)\$ lookup, where str has \$O(n)\$. Thanks to Python's TimeComplexity page. \$\endgroup\$ – Peilonrayz Nov 17 '15 at 19:47
  • \$\begingroup\$ @JoeWallis Agreed. frozenset are best but string is not so bad. Better than list of characters (for character lookups). On my mind dicts are not right for this purpose since they store additional data that are unneeded here. Anyway, I mentionned set in the post but used a string in the final code excerpt for readability. \$\endgroup\$ – 301_Moved_Permanently Nov 17 '15 at 20:10
  • \$\begingroup\$ @MathiasEttinger I forgot about frozenset, silly me. In this case the data type doesn't really matter, but what's so bad about a list? To me both list and str are as bad, is it just strings internal immutability? Also set('dtaeıiuCgk') and frozenset('dtaeıiuCgk') are both readable... \$\endgroup\$ – Peilonrayz Nov 17 '15 at 20:35
  • \$\begingroup\$ @JoeWallis I think that's because strings are only made of chatacters and lists might contain any types. I'll try to find back the source of my claim, if possible. \$\endgroup\$ – 301_Moved_Permanently Nov 17 '15 at 20:39
0
\$\begingroup\$

I compared two codes actually I expected @MathiasEttinger's proposal to be faster(it looks beatiful) but when I run test script several times. I see my bad looking codes are faster do you have any idea why ? Below both functions, test loops and results:

def char_filter(morph):
char_dict = {'d': 'D', 't': 'D', 'a': 'A', 'e': 'A', 'ı': 'H', 'i': 'H', 'u': 'H', 'C': 'C', 'g': 'G', 'k': 'G'}
res = []
res1 = []
flag = []

if 'ken' in morph:
    flag.append([morph.rindex('ken'), ['k','e','n']])

for i in morph:
    res2 = i
    if i in char_dict:
        res2 = char_dict[i]
    res1.append(res2)

if len(flag) > 0:
    for z in flag:
        res1[z[0]:z[0]+3] = z[1]
res.append(string.join(res1, sep=''))
return res[0]

This is right version what is proposed

def char_filter1(origin_string):
char_dict = {'d': 'D', 't': 'D', 'a': 'A', 'e': 'A', 'ı': 'H', 'i': 'H', 'u': 'H', 'C': 'C', 'g': 'G', 'k': 'G'}
filtered_letters = [char_dict[char] if char in char_dict.keys() else char
                    for char in origin_string]

if 'ken' in origin_string:
    i = origin_string.rindex('ken')
    filtered_letters[i:i+3] = ['k','e','n']

return ''.join(filtered_letters)

Test Function

measure=0
start_time1 = time.time()
for i in range(500000):
    a=char_filter1('gidiyolarkendegeliyor')
print a
print("--- %s seconds ---" % (time.time() - start_time1))
measure += (time.time() - start_time1)
print measure/500000
measure=0

start_time = time.time()

for i in range(500000):
    a=char_filter('gidiyolarkendegeliyor')
print a
print("--- %s seconds ---" % (time.time() - start_time))
measure += (time.time() - start_time)
print measure/500000

And resulted as:

--char_filter1- 8.44659018517 seconds ---

1.68932442665e-05

--char_filter- 6.04725313187 seconds ---

1.20945320129e-05

\$\endgroup\$
  • \$\begingroup\$ I’m a bit late on this one, but you’re basically adding useless work by calling char_dict.keys() for the lookup. You can call char_dict.get(char, char) to achieve the same functionality than your ternary operator. Lastly, move the definition of char_dict outside of the function, it will save time too. \$\endgroup\$ – 301_Moved_Permanently Jan 6 '16 at 13:13

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.