Removing a char from String, what's a more efficient way to do this?

Question

I'm currently studying Python 2.7 from an online course. One of the problems is I have to remove a char from a string based from a list of chars.

What I did was:

def getAvailableLetters(letters):

    alphabet = string.ascii_lowercase
    reduced_alphabet = ''

    for char in alphabet:
        if char not in lettersGuessed:
            reduced_alphabet += char

    return reduced_alphabet

I've learned that there's no such thing as a string method to directly remove a char from a string as they are immutable, so I came up with this. I've successfully submitted a correct answer, but I'm not quite satisfied with it as I feel like there's a more efficient way to do it.

Because the answers there apply directly to your problem; replace `string.punctuation` with (a string created from) `lettersGuessed`. — Martijn Pieters, Nov 08 '13 at 12:18

Ashwini Chaudhary · Accepted Answer · 2013-11-08T12:15:03.883

7

Fastest way would be to use str.translate here:

>>> lettersGuessed = ['a', 'b', 'c']
>>> 'wedqwdasdasccdshjasdcas'.translate(None, ''.join(lettersGuessed))
'wedqwdsdsdshjsds'

if lettersGuessed is already a string then remove the ''.join call.

Timing results compared to str.join and filter, taken from @thefourtheye's solution:

def getAvailableLetters2(lettersGuessed):
    return string.ascii_lowercase.translate(None, lettersGuessed)

from timeit import timeit
print 'filter-->', timeit("getAvailableLetters('Welcome')", setup="from __main__ import getAvailableLetters")
print '.join-->', timeit("getAvailableLetters1('Welcome')",setup="from __main__ import getAvailableLetters1")
print 'trans-->', timeit("getAvailableLetters2('Welcome')",setup="from __main__ import getAvailableLetters2")

Output:

filter--> 6.49355100548
.join--> 4.02496357229
trans--> 0.69938109531

edited Nov 08 '13 at 12:15

answered Nov 08 '13 at 12:02

Ashwini Chaudhary

244,495
58
464
504

+1 I am wondering why `translate` is the fastest. Amazing. – thefourtheye Nov 08 '13 at 12:08
2

I too often forget about `translate` and how it is great for *removing* characters. – Martijn Pieters Nov 08 '13 at 12:09
@MartijnPieters Could you please tell me why `translate` is faster? How is it implemented internally? – thefourtheye Nov 08 '13 at 12:10
@thefourtheye http://stackoverflow.com/a/266162/846892 – Ashwini Chaudhary Nov 08 '13 at 12:11
2

@thefourtheye: C string magic; lookup tables in C operating directly on the string bytes. – Martijn Pieters Nov 08 '13 at 12:16
I already upvoted. Somebody please upvote this answer. This has to be at the top. – thefourtheye Nov 08 '13 at 12:18
@MartijnPieters [This](http://hg.python.org/cpython/file/0f48843652b1/Objects/bytesobject.c#l1481) could be that function? – thefourtheye Nov 08 '13 at 12:26
@hcwhsa, lost in speed) you're machine is faster too, my results were ~8.6, ~5.6, ~0.9 secs :) – alko Nov 08 '13 at 12:26
1

@thefourtheye: That is that function, for the Python 3 `bytes` type. The `str` (unicode) type also has one, albeit slightly different in implementation. – Martijn Pieters Nov 08 '13 at 12:29

thefourtheye · Answer 2 · 2013-11-08T11:59:32.723

You can use list comprehension like this, to filter out the characters which are in lettersGuessed

import string
def getAvailableLetters(lettersGuessed):
    return "".join([char for char in string.ascii_lowercase if char not in lettersGuessed])

print getAvailableLetters("Welcome")

Output

abdfghijknpqrstuvwxyz

Alternatively, you can use filter function like this

import string
def getAvailableLetters(lettersGuessed):
    return filter(lambda x: x not in lettersGuessed, string.ascii_lowercase)

print getAvailableLetters("Welcome")

Output

abdfghijknpqrstuvwxyz

Edit: Performance comparison

import string
def getAvailableLetters(lettersGuessed):
    return filter(lambda x: x not in lettersGuessed, string.ascii_lowercase)

def getAvailableLetters1(lettersGuessed):
    return "".join([char for char in string.ascii_lowercase if char not in lettersGuessed])

from timeit import timeit
print timeit("getAvailableLetters('Welcome')", setup="from __main__ import getAvailableLetters")
print timeit("getAvailableLetters1('Welcome')",setup="from __main__ import getAvailableLetters1")

Output on my machine

3.02976298332
2.00461006165

It shows that, list comprehension method beats filter method.

I suspect it's the `lambda` that kills the `filter()` performance here. For `filter(str.isupper, 'abcABC')` vs. `''.join([c for c in 'abcABC' if c.isupper()])`, `filter()` wins. — Martijn Pieters, Nov 08 '13 at 12:07
Using `functools.partial(operator.contains, lettersGuessed)` makes the filter faster than the `''.join()`. But `str.translate` still wins. — Martijn Pieters, Nov 08 '13 at 12:11

score 2 · Answer 3 · answered Nov 08 '13 at 11:55

The most efficient way is to use str.join() to turn a sequence of characters into a new string:

return ''.join([char for char in string.ascii_lowercase if char not in lettersGuessed])

This avoids creating a new string object every iteration of the loop; instead, the new string is created once.

Removing a char from String, what's a more efficient way to do this?

3 Answers3