methods contest clear solution for First Word (simplified) by quarkov - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

methods contest solution in Clear category for First Word (simplified) by quarkov

def first_word(text):
    index = text.find(" ")
    return text[:index] if index != -1 else text


"""
It's worth to look at the performance of different methods under the same predefined conditions.
Let's check runtime of the 4 methods (10000 executions for each) defined below for the next 4 cases:
-a short str which contains space chars: "asdf we"*10;
-a short str which doesn't contain space chars: "asdfawe"*10;
-a long str which contains space chars: "asdf we"*100000;
-a long str which doesn't contain space chars: "asdf we"*100000.
############################################################################################################
from timeit import timeit as t


def first_word_1(text):
    return text.split(" ")[0]

print(t('first_word_1(x)', setup='x = "asdf we"*10', number=10000, globals=globals()))       #  ~11.7 ms
print(t('first_word_1(x)', setup='x = "asdfawe"*10', number=10000, globals=globals()))       #  ~6.1 ms
print(t('first_word_1(x)', setup='x = "asdf we"*100000', number=10000, globals=globals()))   #  ~90928.2 ms
print(t('first_word_1(x)', setup='x = "asdfawe"*100000', number=10000, globals=globals()))   #  ~5562.9 ms


def first_word_2(text):
    index = text.find(" ")
    return text[:index] if index != -1 else text
    
print(t('first_word_2(x)', setup='x = "asdf we"*10', number=10000, globals=globals()))       #  ~6.3 ms
print(t('first_word_2(x)', setup='x = "asdfawe"*10', number=10000, globals=globals()))       #  ~4.7 ms
print(t('first_word_2(x)', setup='x = "asdf we"*100000', number=10000, globals=globals()))   #  ~7.0 ms
print(t('first_word_2(x)', setup='x = "asdfawe"*100000', number=10000, globals=globals()))   #  ~2108.4 ms


def first_word_3(text):
    try:
        index = text.index(" ")
        return text[:index]
    except ValueError:
        return text

print(t('first_word_3(x)', setup='x = "asdf we"*10', number=10000, globals=globals()))       #  ~5.8 ms
print(t('first_word_3(x)', setup='x = "asdfawe"*10', number=10000, globals=globals()))       #  ~8.5 ms
print(t('first_word_3(x)', setup='x = "asdf we"*100000', number=10000, globals=globals()))   #  ~5.8 ms
print(t('first_word_3(x)', setup='x = "asdfawe"*100000', number=10000, globals=globals()))   #  ~2005.8 ms


def first_word_4(text):
    index = -1
    for pos, letter in enumerate(text):
        if letter == " ":
            index = pos
            break
    return text[:index] if index != -1 else text
    
print(t('first_word_4(x)', setup='x = "asdf we"*10', number=10000, globals=globals()))       #  ~13.1 ms
print(t('first_word_4(x)', setup='x = "asdfawe"*10', number=10000, globals=globals()))       #  ~71.1 ms
print(t('first_word_4(x)', setup='x = "asdf we"*100000', number=10000, globals=globals()))   #  ~13.1 ms
print(t('first_word_4(x)', setup='x = "asdfawe"*100000', number=10000, globals=globals()))   #  ~788793.7 ms
############################################################################################################
So what conclusions can be made from all of this?

1.Since every string is an instance of the string class, it's preferred to use its methods rather than implement
a new function which seems to be faster. It won't work faster in most of the cases. Compare first_word_2 and
first_word_4 for example.

2.Despite the fact first_word_1 (which uses .split() method) looks nice and concise it works worse with long strings
than first_word_2 and first_word_3 do(they use .find() and .index() methods respectively). Especially in case there are
lots of spaces in the text.

3.str.index() method works a bit faster than str.find() but only in case there is a space in the text. Otherwise it's
needed to handle an exception which takes some extra time. 

Thus, I'd use str.find() method in such kind of tasks.
"""

March 22, 2019

Comments:

Phil15 on March 27, 2019, 2:59 p.m.
I started timeit random tests before I see you already did it. But I test the current ten published functions (sometimes a bit changed). 1000 sentences from 1 to 100 words from 3 to 13 letters, tested 10000 times. Functions are sorted in order to have decreasing performances. <pre class='brush: python'>from timeit import timeit from random import randint L = [' '.join(''.join(chr(randint(97, 122)) for _ in range(randint(3, 13))) for _ in range(randint(1, 100))) for _ in range(1000)] funcs = """ from re import compile, split, search from operator import itemgetter, methodcaller def first_word1(text): index = text.find(' ') return text[:index] if index != -1 else text def first_word2(text): try: return text[:text.index(' ')] except ValueError: return text first_word3 = lambda text: text.split(maxsplit=1)[0] first_word4 = lambda text: text[:text.find(' ') % (len(text)+1)] first_word5 = lambda text: text[:(text+' ').index(' ')] compose = lambda g, f: lambda x: g(f(x)) first_word6 = compose(itemgetter(0), methodcaller('split', ' ', 1)) matcher = compile('(\\S+)\\s?').match def first_word7(text): return matcher(text)[1] def first_word8(text: str) -> str: return search(r"[a-zA-Z]+", text).group(0) first_word9 = lambda text: text.split()[0] expr10 = compile('\\W+') first_word10 = lambda t: split(expr10, t)[0] """ stmt = """ for s in L: first_word{}(s) """.format setup = funcs + f"L = {L}" for k in range(1, 11): res = timeit(stmt(k), setup, number=10000) print(f"first_word{k: <2} {round(res, 2): >6} seconds.") </pre> Results: <pre class='brush: python'>first_word1 2.73 seconds. first_word2 2.93 seconds. first_word3 3.83 seconds. first_word4 3.86 seconds. first_word5 4.11 seconds. first_word6 4.27 seconds. first_word7 4.37 seconds. first_word8 10.26 seconds. first_word9 29.88 seconds. first_word10 199.14 seconds. </pre>

quarkov on March 27, 2019, 3:59 p.m.
You might have come to the same conclusions hence=) I've not even considerd any re implementations because they work slower by default. It's very nice that you supplemented my comparison with your benchmarks, I believe it will serve the educational purposes well.

viktor.chyrkin on Nov. 1, 2022, 12:38 p.m.
my brain processor does not understand.

Phil15 on Nov. 1, 2022, 3:51 p.m.
If you have a question, I would answer.

viktor.chyrkin on Nov. 1, 2022, 8:42 p.m.
No you don't get it. To me this is Chinese. I don't understand it.

Phil15 on Nov. 1, 2022, 9:26 p.m.
Here, I compare timings of 10 "first_word" functions (that are solving this mission) on 1000 random sentences (between 1 and 100 words, each word has between 3 and 13 letters) to see which is more timely efficient (each timing is done 10000 times to significant timings to compare). For that, I use a module named "timeit" which contains a function "timeit" (same name) which take two strings (and optional parameters): - "stmt" which contain the code I want to time - "setup" which contains code that defines stuff for "stmt". I define the 10 functions there. - number=10000 implies that "stmt" is run 10000 times. Some functions may be tricky to understand. If this is still Chinese to you and if you still have no question, then I'm not sure you want to understand, which is fine by me.

Andrea_Fagerman on April 10, 2023, 9:51 p.m.
In def first_word1(text): index = text.find(' ') return text[:index] if index != -1 else text Why did you include if index != -1 else text?

veky on March 28, 2019, 7:31 p.m.
Everything you wrote can be excused, except "Thus". Seriously, if you're obsessed with milliseconds, you shouldn't write Python at all. You'll just be frustrated. There are much faster languages (where you can be obsessed about nanoseconds;).

quarkov on March 28, 2019, 8:41 p.m.
I can't see how exactly your speculations about my imaginary obsession might be related with my solution and benchmarks.

veky on March 29, 2019, 3:23 p.m.
When someone writes 70 lines of text about something without any external reason, my primary hypothesis is an obsession. Do you have alternative explanation?

quarkov on March 29, 2019, 5:11 p.m.
This section is called leave a code review, not leave a person review. If you do have anything else to say in regard of my code - go on. Otherwise this is a meaningless conversation.

veky on March 30, 2019, 8:40 a.m.
I think it's insightful that you did write your huge essay in code (comments). That makes it a valid target, right? :-) Ok, I get it. You want me to frame what I'm saying as just about the code. No problem. Here it goes: `str.find` is an incredibly old interface, going back to old days of C, where you didn't have much opportunity to return an out of band error. Almost all functions that had to read something (e.g. getc) returned -1 in case of failure. Standard library even #defined EOF as -1 to make such code easier to read. If -1 were a valid return value, usually the return value was reserved for error code, and some other way (an "out parameter", that is just a pointer with a convention) was used for the transfer of the real "return value". Python took that philosophy at a young and impressionable age when it didn't have one of its own. Comparing the result of find to -1 was the official way to even check if some string is a substring of another (`in` worked only for single chars). When Python grew older and started thinking with its own head, there were various initiatives to deprecate these functions (<a href="https://docs.python.org/2.4/lib/node111.html),">https://docs.python.org/2.4/lib/node111.html),</a> but for some reasons `find` stayed. (On the other hand, just look at how silly `atof` is---precisely because it's just copied from C into a world where there are much better ways to do things.) -1 doesn't make sense as a result for various reasons, one of biggest is that -1 is actually a valid index into a (nonempty) string. So someone naively expecting that `string[string.find(char)]` be char (or error if it can't be) will be disappointed. Also, the whole idea of "return type" (in Python, not in some other languages) is that all the possible returned values can be treated uniformly. For obvious reasons, that doesn't apply to that -1. (BTW, that's also the reason for "billion dollar mistake" of null pointers---it's not that null pointers are bad, it's that they are of the same type as regular pointers, suggesting wrongly that they can be treated uniformly with them.) If someone were to design such a function from scratch (without C influence), it would probably return None instead of -1. Luckily, we have an even better way: exceptions. If you want to me to locate something in the room, but it isn't in the room at all, that isn't really a return value, right? If you say "but I don't want to use exceptions, since they are slow", I sincerely want to know why you don't say "I don't want to use Python, since it is slow". Surely the programming language affects more than a few milliseconds you're talking about here. Yes, you can avoid for loops and write everything with while loops to avoid StopIteration handling, but that simply is not Pythonic. It's not using the language's full expressivity. Back to the code: .index is surely better, since it communicates at the level of the question. If we had a function that returned None (or str.NOTFOUND object) in case of absence, it would probably be ok too. But find is not that function. It is simply an atavism of a forgotten age, and a bug magnet.

quarkov on April 1, 2019, 7:20 p.m.
Thanks for such a detailed answer, really. These things aren't as obvious for me as for you. Perhaps, it's because I've started learning not so long ago. Very enlightening reading. Nonetheless, there are also .index and .split in that list of the methods that should be considered deprecated. Could you comment this? I agree on that such a behavior (returning -1 instead of None) looks irrational and can lead to a mistake (a bug magnet as you said). I even fell in this pitfall in the <a href="https://py.checkio.org/mission/between-markers-simplified/publications/quarkov/python-3/double-find/?ordering=most_voted&filtering=all">BetweenMarkers</a>. But it makes me silly because I knew the specs and I made a mistake, not the .find method. For this task text.find(" ") is handled properly, what's wrong in using even an old and possibly deprecated function? Sometimes you can hear somebody uses an archaic word in a conversation, but it's not a problem since (until) it can be understood. Regarding "I don’t want to use Python, since it is slow". Surely it's possible to use an asm =). But if we must use Python for any particular reason (e.i. it's a project's basic language) why wouldn't we use the fastest function?

veky on April 2, 2019, 5:32 a.m.
About the list of functions: sorry, I wasn't clear enough. That link was just meant to show that Python used to have many of its string functions modelled after C, and has in the meantime deprecated most of them (like `atof`). I can't seem to find a particular reason why `find` stayed, but the only discussions I can find point to the fact that its needed relatively early in one's development of Python knowledge, when you don't yet know about exceptions, but would like to do some elementary parsing of strings. (Similar reason as why Python strings have `isdigit`, so you don't have to handle the `ValueError` from `int()` if you want a user to input a natural number.) The best argument in favor of that theory is that lists (which are more advanced and for many people come after strings in learning Python) have only `.[r]index`, not `.[r]find`. In any case, surely the reason wasn't speed. <blockquote> But it makes me silly because I knew the specs and I made a mistake </blockquote> That's exactly my definition of a bug magnet. :-P Look, the days when such features were necessary in programming languages are long gone. [This has nothing to do with Python; every language wanting to be perceived as modern has to banish them, even <a href="http://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#in0-dont-panic">C++</a>.] Today, we prefer languages that gently nudge (or even discipline) you into writing the right thing. Yes, tigers and anacondas which can cost you a life roam lots of jungles on Earth, but there is no reason to have them in modern urban areas. [The fact is, it's more likely a given tiger will get you in the city since you don't expect it there. You fell for that mostly because you didn't expect such a bad design in a language such as Python.] <blockquote> But if we must use Python for any particular reason (e.i. it’s a project’s basic language) why wouldn’t we use the fastest function? </blockquote> That's exactly why I told you you'd be frustrated. Python works only if you want to use it, not if you think you have to use it. If you really think you'd be better off with asm, I can't see how you'll be happy with Python. The core values are so incompatible. It's like trying to sell Afrikaans (an immensely practical but horribly ugly language) to a native Japanese speaker. :-P Speed is not the only criterion. In modern environments, it's rarely relevant at all. (As opposed to algorithmic complexity, which is relevant much more often, but that's a digression.) What you're actually executing when running Python is layer upon layer upon layer of abstraction---surely just removing one of these layers would improve code execution speed many times, and would be much more profitable (if that is your goal) than trying to shave off a millisecond by aligning the tyres on a running car (which is mostly what you're doing above:). You mentioned asm: surely you know that on modern asms, e.g. in mobile phones, energy consumption and heat dissipation are much more pertinent problems than execution speed. Why wouldn't we use the most energy efficient function? Why not use the coolest [pun intended:] one? Of course, I'll tell you why. It's because the infrastructure to measure such effects is not something as readily available as a system clock. But "let's optimize this because we can easily measure it" is the same kind of fallacy as <a href="https://en.wikipedia.org/wiki/Streetlight_effect">searching for keys under the lamppost</a>. ;-)

JimmyCarlos on July 11, 2019, 4:20 p.m.
This is really interesting to see how the speed varies.

undead2k on April 2, 2020, 11:28 a.m.
Sorry for reviving an old thread, just trying to understand what is going on with firstword2 example code. Are we saying something like; index = text.find(" ") - "Find the first "space" character in the string and assign the index to var index" return text[:index] if index != -1 else text - We start but doing a string slice starting from 0 to index as long as index does not equal -1? Which would return the first word. Otherwise return the entire string? Is this the correct way to read what is going on? Thank you for posting so much detail and multiple ways of solving the same problem. I always find it fascinating that coding problems can usually be solved in so many ways.

quarkov on April 2, 2020, 12:20 p.m.
<blockquote> We start but doing a string slice starting from 0 to index as long as index does not equal -1? Which would return the first word. Otherwise return the entire string? </blockquote> Yes, you got it right. It's <a href="https://mail.python.org/pipermail/python-dev/2005-September/056846.html">python ternary expression</a> in action, a good way to shrink a regular if-else 4-liner statement into one line.

undead2k on April 30, 2020, 5:35 p.m.
Awesome, thank you for the reply and link! Shall have a read and learn :3

mailsiraj on Oct. 30, 2020, 4:31 a.m.
thanks a lot for the explanations

samhuawey on Dec. 4, 2020, 8:40 a.m.
return text.split(" ")[0] This should be faster return text.split()[0]

Tomas_Reves on March 14, 2022, 3:21 p.m.
far from being easy solution.

Lord_Spudnik on March 27, 2022, 4:48 p.m.
nice

Laverba0 on May 5, 2022, 10:47 p.m.
This is an elegant solution, but it definitely isn't clear.

viktor.chyrkin on Aug. 5, 2022, 6:28 p.m.
why is this the most liked solution?

morchi on Feb. 7, 2024, 12:16 p.m.
it's not an easy solution, but the intention of the comparison is definitly clear :)

Strings and Integers

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.