Timeline for A C++ program to check if a string is a pangram
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 17, 2021 at 11:52 | comment | added | Null |
@Occhima A const reference for the argument makes a little more sense than a pointer in this case, but a pointer would be better than passing by value since it also would avoid the unnecessary string copy. For discussions about pointers vs. references see Pointer vs. Reference and When to use references vs. pointers.
|
|
| Mar 17, 2021 at 8:51 | comment | added | Peter Cordes |
Edward and @TobySpeight: forgot to link Howard Hinnant's comments on when a bit-vector is useful - isocpp.org/blog/2012/11/on-vectorbool. He agrees that vector<bool> was a poor choice of name for it, but it has its uses, and a standard library with good specializations for it can go fast checking or counting many bits at once for stuff like std::find.
|
|
| Mar 17, 2021 at 8:50 | comment | added | A T |
"instead of calling std::any_of at the end (a loop through possibly all 26 elements of the std::vector<bool>) you can call the constant-time"… technically O(26)=O(1) 😝
|
|
| Mar 17, 2021 at 8:49 | comment | added | Peter Cordes |
Modern x86 CPUs have byte granularity for cache writes so char would definitely be best, to make checking all 26 bytes cheaper. (One or two SIMD loads to get all the data back. Probably pad to array<char,32> so the compiler can check all 32 bytes for non-zero with one AVX1 vptest ymm (maybe after setting array[26..31] to one? hmm, non-trivial to handle the padding), or SSE2 maybe two overlapping 16-byte loads that span the whole 26 bytes, ANDing them together, then check that they're all non-zero. Anyway, storing a 1 is cheap, esp on ISAs with indexed addressing modes.
|
|
| Mar 17, 2021 at 8:44 | comment | added | Peter Cordes |
On some non-x86 microarchitectures, even std:array<int,26> could be better, more likely to allow higher throughput commit to L1d cache from the store buffer without needing an internal RMW cycle in the L1d cache to modify a byte in a word if the store buffer couldn't merge multiple writes to the same word into one commit. Are there any modern CPUs where a cached byte store is actually slower than a word store?
|
|
| Mar 17, 2021 at 8:41 | comment | added | Peter Cordes |
@Edward: Yup, vector<bool> has is place, and that place is for large data sets, like a prime sieve or something. For this case, std::bitset<32> could be good to enable quick checking (setting is only quick on systems that have something like x86's bts reg, reg to implement reg |= 1<<reg efficiently), or std::array<char, 26> (where memory indexing makes setting cheap, without any data dependency between elements. i.e. setting an A doesn't have to wait for a store to arr['B'-'A'] to complete.)
|
|
| Mar 17, 2021 at 8:00 | comment | added | Edward |
@TobySpeight std::vector<bool> is often faster in my testing. See codereview.stackexchange.com/q/117880/39848
|
|
| Mar 17, 2021 at 0:02 | comment | added | Occhima |
Hey @Null, thanks for your contribuition. I've seen some people using pointers to iterate through things in C++, that's really new to me and i've seem some posts in SO about using pointers just when you really need them. Do you think it would be more useful passing a string pointer sas argument to the isPangram function?
|
|
| Mar 16, 2021 at 22:05 | comment | added | G. Sliepen |
Using a std::unordered_set here is very inefficient. The vector<bool> is better, but best would be a std::bitset<26>, and then you can call std::bitset::all() to check if all letters of the alphabet are present.
|
|
| Mar 16, 2021 at 17:59 | comment | added | Toby Speight |
std::vector<bool> often trips people up because despite its name, std::vector<bool> is not a standard container, having a subtly different interface, and performance issues, too. Although counter-intuitive, std::vector<char> is almost always a better choice for storing booleans.
|
|
| Mar 16, 2021 at 17:49 | history | answered | Null | CC BY-SA 4.0 |