C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Vector question Goto page 1, 2  Next          C++Talk.NET Forum Index -> C++ language (comp.lang.c++) View previous topic :: View next topic   Author Message Kitty Guest Posted: Sun Aug 29, 2004 4:51 am    Post subject: Vector question Hi, everyone. Given a vector<int>, what is the fastest way to find out whether there is a repeated element in it? The result is just "true" or "false". Thanks. Kitty Back to top Jon Bell Guest Posted: Sun Aug 29, 2004 5:28 am    Post subject: Re: Vector question In article <413160ad$1_2 (AT) rain (DOT) i-cable.com>, Kitty <No spam> wrote: Quote: Given a vector<int>, what is the fastest way to find out whether there is a repeated element in it? The result is just "true" or "false". Thanks. I'd construct an empty set<int>, then walk through the vector, processing each element in turn. If the element is in the set already, stop and return 'true'; otherwise insert the element into the set and continue. If you reach the end of the vector without finding any duplicates, return 'false'. -- Jon Bell <jtbellm4h (AT) presby (DOT) edu> Presbyterian College Dept. of Physics and Computer Science Clinton, South Carolina USA Back to top Siemel Naran Guest Posted: Sun Aug 29, 2004 5:58 am    Post subject: Re: Vector question "Kitty" <No spam> wrote Quote: Given a vector<int>, what is the fastest way to find out whether there is a repeated element in it? The result is just "true" or "false". Thanks. Sounds like an interview question. There are many answers, each with tradeoffs. Jon's method uses additional memory, but is fast time wise (time is N*O(lg(N), space is O(N)), and easy to write too -- that's important too because software that is easier to write and maintain pays off long term, though this rarely comes up in interviews (though it should). You can also not use additional memory, but sacrifice time (time would be O(N^2), space is O(1)). And each method has its own varations, such as set or hashtable, type of hash function if a hash, set or sorted vector, vector or list, etc, etc. Back to top Siemel Naran Guest Posted: Sun Aug 29, 2004 6:39 am    Post subject: Re: Vector question "Casper" <casper (AT) jbr (DOT) dk> wrote Quote: In a similar problem, I use a different approach due to the fact that jon's solution is not an option as it consumes too much memmory. I use a modified qsort and in the comparation part if two sucessive elements are the same, I return true. This is slow with small lists but fast with huge datasets (30.000+ as in my application takes about 100ms) but require no additional memmory! A good solution, I think the fastest possible without using extra space. But it changes the original vector. Can you think of a way to do it without changing the original? Back to top Kai-Uwe Bux Guest Posted: Sun Aug 29, 2004 6:48 am    Post subject: Re: Vector question "Kitty" <No spam> wrote: Quote: Hi, everyone. Given a vector<int>, what is the fastest way to find out whether there is a repeated element in it? The result is just "true" or "false". Thanks. Kitty Here are three obvious ways of using standard algorithms. These solutions have the advantage that they are easy to understand. The second one could avoid copying if it was allowed to modify the sequence in the first place. #include <vector> #include <set> #include <iostream> template < typename ConstIter > bool has_dublicates_a ( ConstIter from, ConstIter to ) { typedef typename std::iterator_traits< ConstIter >::value_type value_type; typedef typename std::set< value_type > set_type; typedef typename set_type::size_type size_type; size_type i = 0; set_type s; for ( ConstIter iter = from; iter != to; ++iter ) { ++ i; s.insert( *iter ); // this test could also be done after the loop: if ( s.size() != i ) { return( true ); } } return( false ); } template < typename ConstIter > bool has_dublicates_b ( ConstIter from, ConstIter to ) { typedef typename std::iterator_traits< ConstIter >::value_type value_type; typedef typename std::vector< value_type > vector_type; vector_type v ( from, to ); std::sort( v.begin(), v.end() ); return( std::adjacent_find( v.begin(), v.end() ) != v.end() ); } int main( int argn, char ** args ){ std::vector< int > a; std::vector< int > b; for ( int i = 0; i < 10; ++i ) { a.push_back( i ); b.push_back( i ); b.push_back( i ); } std::cout << has_dublicates_a( a.begin(), a.end() ) << " " << has_dublicates_a( b.begin(), b.end() ) << "n"; std::cout << has_dublicates_b( a.begin(), a.end() ) << " " << has_dublicates_b( b.begin(), b.end() ) << "n"; } As for speed, I would suggest a method based on the "partition by exchange" idea underlying quicksort, possibly modified like introsort to avoid O(N^2) worst case runtime. But that idea has been mentioned in another posting already. Best Kai-Uwe Bux Back to top Alex Vinokur Guest Posted: Sun Aug 29, 2004 7:56 am    Post subject: Re: Vector question "Kitty" <No spam> wrote Quote: Hi, everyone. Given a vector<int>, what is the fastest way to find out whether there is a repeated element in it? The result is just "true" or "false". Thanks. Kitty See the thread titled "If vector contains only different elements" at http://groups.google.com/groups?threadm=2ggfjgF2aipdU1%40uni-berlin.de -- Alex Vinokur http://mathforum.org/library/view/10978.html http://sourceforge.net/users/alexvn Back to top Kai-Uwe Bux Guest Posted: Sun Aug 29, 2004 8:00 am    Post subject: Re: Vector question Siemel Naran wrote: Quote: "Casper" <casper (AT) jbr (DOT) dk> wrote In a similar problem, I use a different approach due to the fact that jon's solution is not an option as it consumes too much memmory. I use a modified qsort and in the comparation part if two sucessive elements are the same, I return true. This is slow with small lists but fast with huge datasets (30.000+ as in my application takes about 100ms) but require no additional memmory! A good solution, I think the fastest possible without using extra space. I agree that this is probably the fastest solution using comparisons. Given that the question was for vector<int>, there could be a linear time solution. Here is a (messy) draft of something like that. The idea is to do partition by exchange based on the even/odd distinction (note that dublicates have the same parity). So in one pass, we put all the even elements to the left of all the odd elements. During the same pass, shift down by one bit. Now, we return true if there is a dublicate in the left segment or in the right segment. Farther down in the recursion, we can sometimes return true just based on the length of the segment: if we have shifted so many times that all values are in [0..15], then any segment of length 17 is bound to contain dublicates. The run time for the worst case should be O( N * bit_length<int> ). #include <vector> #include <iostream> #include <kubux/sequenceio> typedef std::vector< unsigned int > Uvector; void print_range ( u_int* from, u_int* to ) { std::cerr << "[ "; while ( from <= to ) { std::cerr << *from << " "; ++from; } std::cerr << "]"; } bool has_dublicates_helper ( u_int* from, u_int* to, u_int max ) { // WARNING, range is closed: [from,to] print_range( from, to ); if ( to <= from ) { return( false ); } if ( max < to - from ) { return( true ); } u_int* low = from; u_int* high = to; while ( true ) { while ( ( low < high ) && ( *low % 2 == 0 ) ) { *low >>= 1; ++low; } while ( ( low < high ) && ( *high % 2 != 0 ) ) { *high >>= 1; --high; } // either ( low == high ) or ( *high is even ) if ( low < high ) { // *low is odd and *high is even std::swap( *low, *high ); } else { break; } } std::cerr << std::endl; print_range( from, to ); std::cerr << std::endl; // low == high; if ( *low % 2 == 0 ) { *low >>= 1; return( has_dublicates_helper( from, low, max >> 1 ) Quote: | has_dublicates_helper( high+1, to, max >>1 ) ); } else { *low >>= 1; return( has_dublicates_helper( from, low-1, max >> 1 ) Quote: | has_dublicates_helper( high, to, max >>1 ) ); } } bool has_dublicates ( Uvector u_vect ) { // this makes a copy return( has_dublicates_helper( &u_vect[0], &u_vect[ u_vect.size()-1 ], std::numeric_limits< unsigned int >::max() ) ); } int main( int argn, char ** args ){ Uvector a; Uvector b; for ( int i = 0; i < 10; ++i ) { a.push_back( i ); b.push_back( i ); b.push_back( i ); } std::cout << has_dublicates( a ) << " " << has_dublicates( b ) << "n"; } Quote: But it changes the original vector. Can you think of a way to do it without changing the original? Same here, I do not see how to avoid that. Best Kai-Uwe Bux Back to top Casper Guest Posted: Sun Aug 29, 2004 9:28 am    Post subject: Re: Vector question In a similar problem, I use a different approach due to the fact that jon's solution is not an option as it consumes too much memmory. I use a modified qsort and in the comparation part if two sucessive elements are the same, I return true. This is slow with small lists but fast with huge datasets (30.000+ as in my application takes about 100ms) but require no additional memmory! /Casper Kitty wrote: Quote: Hi, everyone. Given a vector<int>, what is the fastest way to find out whether there is a repeated element in it? The result is just "true" or "false". Thanks. Kitty Back to top Conrad Weyns Guest Posted: Sun Aug 29, 2004 12:14 pm    Post subject: Re: Vector question "Siemel Naran" <SiemelNaran (AT) REMOVE (DOT) att.net> wrote Quote: "Casper" <casper (AT) jbr (DOT) dk> wrote In a similar problem, I use a different approach due to the fact that jon's solution is not an option as it consumes too much memmory. I use a modified qsort and in the comparation part if two sucessive elements are the same, I return true. This is slow with small lists but fast with huge datasets (30.000+ as in my application takes about 100ms) but require no additional memmory! A good solution, I think the fastest possible without using extra space. But it changes the original vector. Can you think of a way to do it without changing the original? If time is not an issue, perhaps this will do? bool has_duplicates(vector<int> const& i_Ints) { for ( std::vector<int>::const_iterator cit = i_Ints.begin(); cit != i_Ints.end(); ) { int i = *cit++; std::vector<int>::const_iterator jit = cit; while (jit != i_Ints.end()) if (*jit++ == i) return true; } return false; } cheers, Conrad Weyns Quote: Back to top Kitty Guest Posted: Sun Aug 29, 2004 12:17 pm    Post subject: Re: Vector question The most important thing is to keep elements in the same positions after processing. That is sorting-like algorithm is not allowed. "Kitty" <No spam> ¦b¶l¥ó news:413160ad$1_2 (AT) rain (DOT) i-cable.com ¤¤¼¶¼g... Quote: Hi, everyone. Given a vector<int>, what is the fastest way to find out whether there is a repeated element in it? The result is just "true" or "false". Thanks. Kitty Back to top Daniel T. Guest Posted: Sun Aug 29, 2004 3:14 pm    Post subject: Re: Vector question In article <413160ad$1_2 (AT) rain (DOT) i-cable.com>, "Kitty" <No spam> wrote: Quote: Given a vector<int>, what is the fastest way to find out whether there is a repeated element in it? The result is just "true" or "false". Thanks. People have given great answers to the question asked, but I want to take another tack... Another way would be to not allow repeated elements in the vector in the first place, this can be done by wrapping the vector in a class that checks during insertion to make sure the element isn't already there... Back to top Casper Guest Posted: Mon Aug 30, 2004 4:20 am    Post subject: Re: Vector question This also sounds like a good idea, a kind of sorted vector using binary search. But then again, this comes awfully close to the functionality of a hash map which would be the ultimate solution speed wize though: if a collision happens, you've got yourself a duplet instance. Again maybe if you give a bit more info as to the size, content and use of the vector? /Casper Daniel T. wrote: Quote: In article <413160ad$1_2 (AT) rain (DOT) i-cable.com>, "Kitty" <No spam> wrote: Given a vector<int>, what is the fastest way to find out whether there is a repeated element in it? The result is just "true" or "false". Thanks. People have given great answers to the question asked, but I want to take another tack... Another way would be to not allow repeated elements in the vector in the first place, this can be done by wrapping the vector in a class that checks during insertion to make sure the element isn't already there... Back to top Siemel Naran Guest Posted: Mon Aug 30, 2004 11:38 pm    Post subject: Re: Vector question "Conrad Weyns" <weyns (AT) online (DOT) no> wrote Quote: "Siemel Naran" <SiemelNaran (AT) REMOVE (DOT) att.net> wrote in message If time is not an issue, perhaps this will do? bool has_duplicates(vector<int> const& i_Ints) { for ( std::vector<int>::const_iterator cit = i_Ints.begin(); cit != i_Ints.end(); ) { int i = *cit++; std::vector<int>::const_iterator jit = cit; while (jit != i_Ints.end()) if (*jit++ == i) return true; } return false; } Very good. Remember though to handle the special case of a vector of one element. Back to top Siemel Naran Guest Posted: Mon Aug 30, 2004 11:52 pm    Post subject: Re: Vector question Kai-Uwe Bux <jkherciueh (AT) gmx (DOT) net> wrote in message Quote: Siemel Naran wrote: I agree that this is probably the fastest solution using comparisons. Given that the question was for vector<int>, there could be a linear time solution. Here is a (messy) draft of something like that. The idea is to do partition by exchange based on the even/odd distinction (note that dublicates have the same parity). So in one pass, we put all the even elements to the left of all the odd elements. During the same pass, shift down by one bit. Now, we return true if there is a dublicate in the left segment or in the right segment. Farther down in the recursion, we can sometimes return true just based on the length of the segment: if we have shifted so many times that all values are in [0..15], then any segment of length 17 is bound to contain dublicates. The run time for the worst case should be O( N * bit_length<int> ). This sounds reasonable, though I've not looked at the details carefully. But with N typically equal to 32 or 64, would it be too slow? Quote: #include <vector #include #include typedef std::vector< unsigned int > Uvector; void print_range ( u_int* from, u_int* to ) { std::cerr << "[ "; while ( from <= to ) { std::cerr << *from << " "; ++from; } std::cerr << "]"; } bool has_dublicates_helper ( u_int* from, u_int* to, u_int max ) { // WARNING, range is closed: [from,to] print_range( from, to ); if ( to <= from ) { return( false ); } if ( max < to - from ) { return( true ); } u_int* low = from; u_int* high = to; while ( true ) { while ( ( low < high ) && ( *low % 2 == 0 ) ) { *low >>= 1; ++low; } while ( ( low < high ) && ( *high % 2 != 0 ) ) { *high >>= 1; --high; } // either ( low == high ) or ( *high is even ) if ( low < high ) { // *low is odd and *high is even std::swap( *low, *high ); } else { break; } } std::cerr << std::endl; print_range( from, to ); std::cerr << std::endl; // low == high; if ( *low % 2 == 0 ) { *low >>= 1; return( has_dublicates_helper( from, low, max >> 1 ) || has_dublicates_helper( high+1, to, max >>1 ) ); } else { *low >>= 1; return( has_dublicates_helper( from, low-1, max >> 1 ) || has_dublicates_helper( high, to, max >>1 ) ); } } bool has_dublicates ( Uvector u_vect ) { // this makes a copy return( has_dublicates_helper( &u_vect[0], &u_vect[ u_vect.size()-1 ], std::numeric_limits< unsigned int >::max() ) ); } int main( int argn, char ** args ){ Uvector a; Uvector b; for ( int i = 0; i < 10; ++i ) { a.push_back( i ); b.push_back( i ); b.push_back( i ); } std::cout << has_dublicates( a ) " " has_dublicates( b ) "n"; } But it changes the original vector. Can you think of a way to do it without changing the original? Same here, I do not see how to avoid that. You can for for the O(N^2) algorithm, as in the other post. Back to top Kai-Uwe Bux Guest Posted: Tue Aug 31, 2004 12:41 am    Post subject: Re: Vector question Siemel Naran wrote: Quote: Kai-Uwe Bux <jkherciueh (AT) gmx (DOT) net> wrote in message Siemel Naran wrote: I agree that this is probably the fastest solution using comparisons. Given that the question was for vector<int>, there could be a linear time solution. Here is a (messy) draft of something like that. The idea is to do partition by exchange based on the even/odd distinction (note that dublicates have the same parity). So in one pass, we put all the even elements to the left of all the odd elements. During the same pass, shift down by one bit. Now, we return true if there is a dublicate in the left segment or in the right segment. Farther down in the recursion, we can sometimes return true just based on the length of the segment: if we have shifted so many times that all values are in [0..15], then any segment of length 17 is bound to contain dublicates. The run time for the worst case should be O( N * bit_length<int> ). This sounds reasonable, though I've not looked at the details carefully. But with N typically equal to 32 or 64, would it be too slow? Well, uhm, yes. I thought of that too: In order for ( N * bit_length<int> ) to be faster than O( N * log(N) ), one would have to have N > MAX_INT. That is usually a very unreasonable assumption. However, the difference to a suitably modified qsort is that this gives you a good *worst case*, which is still quadratic for qsort. Nonetheless, I found empirically that template < typename ConstIter > bool has_dublicates ( ConstIter from, ConstIter to ) { typedef typename std::iterator_traits< ConstIter >::value_type value_type; typedef typename std::vector< value_type > vector_type; vector_type v ( from, to ); std::sort( v.begin(), v.end() ); return( std::adjacent_find( v.begin(), v.end() ) != v.end() ); } is strictly faster than the even/odd partitioning scheme; and I would expect that in many implementations of std::sort(), quicksort has been replaces by introsort or something similar, which would guarantee an O( N * log(N) ) worst case, too. Moreover, there is one consideration that should be taken most seriously: What will typically be the case, dublicates or not? If the algorithm will most often encounter dublicate-free sequences, then it makes sense to optimize for proving that no dublicates occur. If typically the sequence will have dublicates, the algorithm should try to find those as quickly as possible. I realized that even/odd partitioning scheme sucks in this regard because dublicates are not found until towards the end. This is where the real strength of std::set<> based solutions lies: template < typename ConstIter > bool has_dublicates_a ( ConstIter from, ConstIter to ) { typedef typename std::iterator_traits< ConstIter >::value_type value_type; typedef typename std::set< value_type > set_type; typedef typename set_type::size_type size_type; size_type i = 0; set_type s; for ( ConstIter iter = from; iter != to; ++iter ) { ++ i; s.insert( *iter ); // this test could also be done after the loop: if ( s.size() != i ) { return( true ); } } return( false ); } This flags dublicates early on. However, it is about 10 times slower in proving that there are no dublicates. Maybe, one could speed up the process by using an array of 256 sets -- one for each possible value of the low-order byte. Best Kai-Uwe Bux Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ language (comp.lang.c++) All times are GMT Goto page 1, 2  Next Page 1 of 2   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.