| Paul <pepstein5@gmail.com>: Oct 31 07:34AM -0700 Below is my code for determining if a given sequence of distinct integers has a decreasing subsequence of length 3. Is there a standard range-based approach for writing for(int i = 2; i < x.size(); ++ i) Thanks. (Of course, any comments on the code are welcome.) I'd be surprised if it's wrong because I've tested it quite a bit. Paul // A permutation being a riffle shuffle is equivalent to there being no decreasing // subsequence of length 3. All cards are assumed distinct. bool isRiffleShuffle(const std::vector<int>& cards) { if(cards.size() < 3) return true; // Keep track of the "largest" decreasing subsequence of length 2 // and whether such a sequence exists. int maximum = std::max(cards[0], cards[1]); int afterPeak; bool decreasing2 = cards[1] < cards[0]; if(decreasing2) afterPeak = cards[1]; for(int i = 2; i < cards.size(); ++i) { const int card = cards[i]; if(decreasing2 && card < afterPeak) return false; if(card > maximum) maximum = card; else { if(!decreasing2 || card > afterPeak) afterPeak = card; decreasing2 = true; } } return true; } |
| "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Oct 31 04:17PM +0100 On 31.10.2018 15:34, Paul wrote: > Below is my code for determining if a given sequence of distinct > integers has a decreasing subsequence of length 3. > Is there a standard range-based approach for writing for(int i = 2; i < x.size(); ++ i) Not yet, as far as I know. But see below. Before getting to that, however, I suggest compiling with the highest practical warning levels. For g++ (and presumably clang, since it was designed as drop-in replacement) that means `-Wall -pedantic-errors -std=c++17`, and for Visual C++ 2017 (and presumably Intel, ditto) that means `/W4 /D _CRT_SECURE_NO_WARNINGS /D _STL_SECURE_NO_WARNINGS`. Then you'd discover that the following way of writing the loop, for( int i = 2, n = cards.size(); i < n; ++i ) ... both avoids warnings and guarantees performance. > { > const int card = cards[i]; > if(decreasing2 && card < afterPeak) Visual C++ 2017 with `/W4` says, p:\temp\foo.cpp(22) : warning C4701: potentially uninitialized local variable 'afterPeak' used Upping the warning level can be really useful, not just for writing loops with efficient execution, but also for correctness. > } > return true; > } --------------------------------------------------------------------- #include <algorithm> #include <vector> struct Start_offset{ int value; }; template< class It > class It_range { It m_first; It m_after; public: auto begin() const -> It { return m_first; } auto end() const -> It { return m_after; } It_range( const It first, const It after ): m_first( first ), m_after( after ) {} It_range( const It first, const It after, const Start_offset offset = {0} ): m_first( first + offset.value ), m_after( after ) {} }; #include <iostream> #include <iterator> // std::(begin, end) #include <numeric> // std::iota #define $items( c ) std::begin( *&c ), std::end( c ) auto main() -> int { using namespace std; vector<int> cardinals( 7 ); iota( $items( cardinals ), 1 ); // Output "3 4 5 6 7". // Using C++17 template parameter deduction from constructor args. for( const int i : It_range( $items( cardinals ), Start_offset{ 2 } ) ) { cout << i << ' '; } cout << endl; } --------------------------------------------------------------------- Cheers!, - Alf |
| "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Oct 31 04:20PM +0100 On 31.10.2018 16:17, Alf P. Steinbach wrote: > m_after( after ) > {} > }; Oh, instead of `+` should use whatever that std:: function is called, that behaves appropriately for random access and forward iterators. Sorry, - Alf |
| Ralf Goertz <me@myprovider.invalid>: Oct 31 04:23PM +0100 Am Wed, 31 Oct 2018 07:34:33 -0700 (PDT) > } > return true; > } "afterPeak" is not initialized if cards[1]>cards[0]. BTW does that mean it is 0? Seems not to be the case since using "g++ -O6 -Wall" on the following program always prints 1 regardless of the value of argc but it doesn't warn about 'x' being used uninitialized. #include <iostream> int main(int argc, char *argv[]) { int x; if (argc>1) x=1; std::cout<<x<<"\n"; } |
| Ralf Goertz <me@myprovider.invalid>: Oct 31 04:35PM +0100 Am Wed, 31 Oct 2018 16:17:02 +0100 > -std=c++17`, and for Visual C++ 2017 (and presumably Intel, ditto) > that means `/W4 /D _CRT_SECURE_NO_WARNINGS /D > _STL_SECURE_NO_WARNINGS`. Hm, in the example given in my answer to the op g++ remains silent with "g++ -Wall -pedantic-errors". Using -O0 prints 0 using -O2 prints 1 when argc is 1. #include <iostream> int main(int argc, char *argv[]) { int x; if (argc>1) x=1; std::cout<<x<<" "<<argc<<"\n"; } |
| Paul <pepstein5@gmail.com>: Oct 31 08:53AM -0700 On Wednesday, October 31, 2018 at 3:24:00 PM UTC, Ralf Goertz wrote: > if (argc>1) x=1; > std::cout<<x<<"\n"; > } afterPeak is only relevant when decreasing2 is true and afterPeak is only used when decreasing2 is true. However, it is correct that the compiler doesn't know that no uninitialised variables are being read. When I tested a few minutes ago, afterPeak was initialised to 7274116 rather than 0. I don't see a problem here. Paul |
| scott@slp53.sl.home (Scott Lurndal): Oct 31 04:12PM > if (argc>1) x=3D1; > std::cout<<x<<"\n"; >} The initial value of 'x' is simply whatever value is in memory at the stack location assigned to x. This may often be zero, but is not guaranteed to be (e.g. if a bunch of shared objects are loaded in the crt before calling 'main', then it's likely that 'x' is reusing a memory location). |
| Louis Krupp <lkrupp@nospam.pssw.com.invalid>: Oct 31 02:06PM -0600 On Wed, 31 Oct 2018 07:34:33 -0700 (PDT), Paul <pepstein5@gmail.com> wrote: > } > return true; >} Note that decreasing2, once set to true, is never set to false. There's a simpler (or at least shorter) way to do it that lets you use a range-based for loop: === #include <iostream> #include <limits> #include <vector> bool IsRiffleShuffle(const std::vector<int>& cards) { auto n_decreasing = 0; auto prev_card = std::numeric_limits<int>::min(); for (auto card : cards) { if (card < prev_card) { // Two decreasing cards indicates a decreasing subsequence // of 3 if (++n_decreasing == 2) return false; } else n_decreasing = 0; prev_card = card; } return true; } int main() { std::cout << std::boolalpha << IsRiffleShuffle({}) << "\n"; std::cout << std::boolalpha << IsRiffleShuffle({1, 2, 3}) << "\n"; std::cout << std::boolalpha << IsRiffleShuffle({3, 2, 1}) << "\n"; std::cout << std::boolalpha << IsRiffleShuffle({3, 2, 2}) << "\n"; std::cout << std::boolalpha << IsRiffleShuffle({3, 4, 2}) << "\n"; } === |
| legalize+jeeves@mail.xmission.com (Richard): Oct 31 08:16PM [Please do not mail me a copy of your followup] "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> spake the secret code >Then you'd discover that the following way of writing the loop, > for( int i = 2, n = cards.size(); i < n; ++i ) >... both avoids warnings and guarantees performance. Is the performance claim really legitimate? Is there any compiler that isn't going to lift this loop invariant out of the loop for you when optimizations are turned on? I find doing this just makes the code less clear and introduces a variable that can be accidentally (or "cleverly") modified when you didn't intent for it to be modified. -- "The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline> The Terminals Wiki <http://terminals-wiki.org> The Computer Graphics Museum <http://computergraphicsmuseum.org> Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com> |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment