6 ms·
The fastest way to detect a vowel in a string
- deleted 1y ago[deleted]
- layer8 1y agoThis doesn’t even cover strings like “fly” and “naïve”. ;)
- cenamus 1y agoYeah, should be called "how to detect aeiou in a string".
- zerocrates 1y agowell... it'll work for naïve. twice over, even
- s09dfhks 1y agoWhat am I missing about fly
- ninkendo 1y agoThe article thinks aeiou are all the vowels, and forgets about y.
- SwiftyBug 1y agoIs y considered a vowel in English? In my native language it is not.
- tough 1y agosame, i is a vowel, y is a consonant TIL: When y forms a diphthong—two vowel sounds joined in one syllable to form one speech sound, such as the "oy" in toy, "ay" in day, and "ey" in monkey—it is also regarded as a vowel. Typically, y represents a consonant when it starts off a word or syllable, as in yard, lawyer, or beyond.
- adrian_b 1y agoIn English it is pretty much unpredictable whether Y is a vowel or a consonant. While for older English words there is a complex set of rules mentioned by another poster for determining whether Y is a vowel, as mentioned by yet another poster, English also includes more recent borrowings from languages with other spelling rules for Y. At its origin, Y was a vowel, not a consonant. It was added to the Latin alphabet for writing the front rounded vowel that is written "ü" in German, "u" in French or "y" in Scandinavian languages. It is very unfortunate that in English, and in some other languages that have followed English, Y has been reassigned to write consonant "i". This has created a lot of problems due to the mismatches between the spelling rules of different languages. The rule that is most consistent with the older usage would have been to use J for consonant "i", like in German and other languages inspired by it. However in many Romance languages the pronunciation of consonant "i" has changed in time, leading to other 3 phonetic values for the letter J, like in English (i.e. Old French), like in French/Portuguese and like in Spanish. So the result is that both for Y and for J there are great differences in pronunciation between the European languages, and the many words using such letters that have been borrowed between languages create a lot of complexity in spelling rules.
- tough 1y agoThank you for the extended explanation, really interesting stuff!
- nemomarx 1y agoThe list of vowels in American English is "A E I O U and sometimes Y" as taught to school children. It would be a vowel in Ypsilanti for example.
- horsawlarway 1y agoSometimes. Which is actually part of why I clicked into the article - I expected it to get into the complexity of trying to detect if 'y' was a vowel as part of the search, and instead got a mostly banal python text search article. You can see the technical rules for when 'Y' is a vowel in english here: https://www.merriam-webster.com/grammar/why-y-is-sometimes-a-vowel-usage#:~:text=Y%20is%20considered%20to%20be,a%20syllable%3A%20system%2C%20borborygmus. https://www.merriam-webster.com/grammar/why-y-is-sometimes-a... Y is considered to be a vowel if… The word has no other vowel: gym, my. The letter is at the end of a word or syllable: candy, deny, bicycle, acrylic. The letter is in the middle of a syllable: system, borborygmus.
- lcnPylGDnU4H9OF 1y agoI dunno about those rules; there are exceptions. Yttrium. Yggdrasil. Probably others, but those from off the top of my head. I think the best way to define when Y is a vowel is when it's not a consonant. Basically, if you make the sound that Y represents in the word "yes", it's a consonant. Otherwise, it's a vowel. (At least, no exceptions come to mind.)
- DougN7 1y agoWow, how would you code that?!
- lcnPylGDnU4H9OF 1y agoHeh, good question. I’d probably use a heuristic like what’s discussed in this thread and hope that it works. :D
- holycrapwhodat 1y agohttps://www.youtube.com/watch?v=1_it0G2KcrM https://www.youtube.com/watch?v=1_it0G2KcrM
- layer8 1y agoIt depends on the word, and possibly even on dialect. There isn’t a 1:1 mapping between characters and vowels. Vowels are fundamentally a phonetic concept, not a graphemic one. This is also why Unicode doesn’t have a “vowel” character property. Otherwise you could use a regex like `\p{Vowel}`.
- csb6 1y agoYes, this is true. Many people seem to think of words as written text and not as spoken words, so they focus on analyzing the characters is a word and not how it sounds. I had a linguistics professor say something like “Writing is parasitic on speech”
- mystified5016 1y agoY and W are sometimes used as vowels. They are technically consonants, but in some cases produce a vowel sound. The rule in English is not "all true words contain a vowel" it's that all words contain a vowel sound. Except the ones that don't, because English is a very messy language.
- IAmBroom 1y agoHmm...
- xigoi 1y agoLetters are not vowels; sounds are vowels. The letter Y sometimes represents a vowel sound and sometimes a consonant sound.
- luma 1y agoIf your approach to "the fastest way to do x" starts with writing some python, you're already not taking the assignment seriously.
- tines 1y agoI think it’s reasonable to use algorithmic complexity as a definition for “fast”.
- kiru_io 1y agoCan you elaborate or show a better way?
- tough 1y agoRust, Go, C?
- fedsocpuppet 1y agojulia> using Random, BenchmarkTools julia> function isvowel(c) idx = (c | 0x20) - Int('a') return (0x00104111 & (1 << idx)) != 0 end julia> hasvowel(str) = any(c -> isvowel(Int(c)), str) julia> @btime hasvowel(s) setup=(s=randstring("bcdfghjklmnpqrstvwxyzBCDFGHJKLMNPQRSTVWXYZ0123456789", 10)) 15.739 ns (0 allocations: 0 bytes) false some 77 thousand times faster
- ninkendo 1y ago
- deleted 1y ago[deleted]
- DannyB2 1y agoAssume use of 8 bit characters. Declare a constant 256 entry array pre-filled with all False except for the five (or six) vowel characters. This is baked into the code and not initialized at runtime. Now for each character c in the input string, simply do an array index and see if it is true (a vowel) or not. This avoids either five conditionals, or a loop over the string 'aeiou'. The vowel test is constant time regardless of the character value.
- masklinn 1y agoIn Python this is going to be slow, as you’ll have a ton of Python code in your hot loop. It’s also going to be even more broken than TFA if any non-ascii character is present in the string.
- guluarte 1y agoneed to add a bloom filter
- ok_dad 1y ago> The regex methods are unbelievably fast regardless of string length. I immediately pinned regex as the winner, and here is why: In Python, you can almost always count on specialized functionality in the stdlib to be faster than any Python code you write, because most of it has probably been optimized in CPython by now. Second, I have to ask, why would someone think that regular expressions, a tool specifically designed to search strings, would be slower than any other tool? Of course it's going to be the fastest! (At least in a language like Python.)
- Kranar 1y agoBut it's not the fastest, it's actually incredibly slow and in general regexs are very slow. The key insight is that string processing in Python is very slow, and that regex here outperforms everything else because it's the only approach that is implemented in C. With that insight it should follow that using another implementation in C should outperform even the regex, and indeed the following simple Python method that this article for whatever reason ignored vastly outperforms everything: def contains_vowel_find(s): for c in "aeiouAEIOU": if s.find(c) != -1: return True return False That's because s.find(c) is implemented in C. In my benchmark this approach is 10 times faster than using a regex: https://gist.github.com/kranar/24323e81ea1c34fb56aff621f6c09e65 https://gist.github.com/kranar/24323e81ea1c34fb56aff621f6c09...
- azhenley 1y agoVery nice find (pun intended). I added an update at the end with your solution and a link to this comment.
- jonstewart 1y agoThe more you learn about regexes, the more you learn that you can’t make general statements about their performance. Performance is contingent upon the engine, its algorithms, its implementation, the patterns, and the input.
- ok_dad 1y agoI've always found regexes to do a string search faster than other methods, but there is always more to learn! Thanks for the lesson today.
- deleted 1y ago[deleted]
- jonstewart 1y ago[flagged]
- kazinator 1y agoIdea: let's nerd-snipe one of those, and then you can have their office.
- azhenley 1y agoWe are hiring.
- shruggedatlas 1y agoThis comment seems needlessly unkind
- deleted 1y ago[deleted]
- mystified5016 1y agoThings don't have to be complicated or pretty to be fast or good. For a UTF-8 or ASCII (English) string: for(char c in string) if(c & 1 == 0) continue; switch(c & 0x1F) case(a & 0x1F) return true; //a or A case(e & 0x1F) return true; //e or E case(i & 0x1F) return true; //i or I case(o & 0x1F) return true; //o or O case(u & 0x1F) return true; //u or U default continue; Checking for consonants is about as free as it gets. 50-70% of characters in English text are consonants. By checking one bit, you can eliminate that many checks across the whole string. This should also more or less apply to any text encoding; this technique comes from an artifact of the alphabet itself. It just so happens that all English vowels (including Y and W) fall on odd indices within the alphabet. Characters aren't magic! They're just numbers. You can do math and binary tricks on them just like you would with any other primitive type. Instead of thinking about finding letters within a string, sometimes you get better answers by asking "how do I find one of a set of numbers within this array of numbers?". It seems to me that a lot of programmers consider these to be entirely disjoint problems. But then again, I'm an embedded programmer and as far as I'm concerned characters are only ever 8 bits wide. String problems are numeric problems for me. While I don't want to discourage people from exploring problem spaces, do understand that the problem space of ASCII has been trodden to the bedrock. Many problems like "does this string contain a vowel" have been optimally solved for decades. Your explorations should include looking at how we solved these problems in the 20th century, because those solutions are likely still extremely relevant.
- pjz 1y agoThe problem with the 'characters are just numbers' approach is that they're not _just_ numbers.. with the advent of unicode, they're _sequences of numbers_... so bytes thus can mean different things when part of a a sequence than when standalone. That said, since they're numbers, we should use the most efficient checks for them... which are likely vectorized SIMD assembly instructions particular to your hardware. And which I've seen no one mention.
- glangdale 1y agoYes, that's it. Vectorized SIMD annihilates this problem, a space I've been working in since 2006 and it wasn't all that new even then. A close second would be a heavily optimized (pipelined and less branchy) table or bitvector lookup. Doing anything that involves lots of control flow, like the grandparent post, will be slow as a wet week with our without bit manipulation tricks due to the inherently unpredictable nature of the branches (subject to our input).
- deleted 1y ago[deleted]
- glangdale 1y agoTo paraphrase Arthur Dent, "this must be a strange new usage of the word 'fastest' with which I am not previously familiar". The fastest way to detect a vowel in a string on any reasonable architecture (Intel or AMD equipped with SIMD of some kind) is using 3-4 instructions which will process 16/32/64 (depends on SIMD length) bytes at once. Obviously access to these will require using a Python library that exposes SIMD. Leaving SIMD aside, a flat byte array of size 256 will outperform a bitmap since it's always faster to look up bytes in an array than bits in a bitmap, and the size is trivial.
- windward 1y agoI don't think the size is trivial, it's 4 times the cache length on x64
- glangdale 1y agoI'm not sure what you mean here. A single cache line is 64B, and this table would thus occupy 4 cache lines, but typical x86 cache sizes are 32K or for more recent cores 48K. Whether consuming 1/512th or 1/768th of your level 1 cache is excessive is a value judgement, but most people wouldn't think so.
- Rendello 1y agoA few years ago I came across the article "SIMD-friendly algorithms for substring searching". The "Generic SIMD" section into and example is small and quite understandable. I modified it to implement an LZ77 sliding window in Zig.* http://0x80.pl/notesen/2016-11-28-simd-strfind.html http://0x80.pl/notesen/2016-11-28-simd-strfind.html * Or rather, I tried my best. I burnt out on that project because I kept jumping back and forth between making a proper DEFLATE implementation or something bespoke. The SIMD stuff was really tough and once I got it "working", I figured I got all I needed from the project and let it go. https://github.com/rendello/compressor/blob/dev/src/str_match.zig https://github.com/rendello/compressor/blob/dev/src/str_matc...
- okibry 1y agoLOL. I found that take time to find amazon affiliate link on this blog is so funny.
- deleted 1y ago[deleted]
- absurdo 1y agoWaiting for a few follow-ups: “What every programmer should know about vowels” “You and your vowels” “What the vowels have wrought” “We’re hiring! Vowels (YC 26)” And last but not least: “Things I Won’t Work With: Vowels”
- haiku2077 1y ago"Falsehoods programmers believe about vowels"