|
Hello everyone,
I need to compute the intersection of two (or more) sets. I will use C or C++, but STL algorithms are not enabled to be used. I have Googled, but it seems that there are only union algorithms and no intersection algorithms.
It is not my homework, and it is my interest to improve the application I am working on now. Does anyone have any reference materials or any ideas of how to design the intersection operation of sets efficiently.
thanks in advance,
George
|
|
|
|
|
The first thing to do is sort the sets, like:
int set1[7] = {5, 2, 0, 2, 8, 7, 5};
int set2[7] = {2, 8, 8, 7, 0, 9, 9};
qsort(set1, 7, sizeof(int), compare);
qsort(set2, 7, sizeof(int), compare);
...
int compare( const void *arg1, const void *arg2 )
{
return *(int *) arg1 - *(int *) arg2;
}Now you can compare the items in the first set with the items in the second set, making a note of the matches. If the current item in the first set is less than the current item in the second set, go to the next item in the first set. If the current item in the first set is greater than the current item in the second set, go to the next item in the second set. Otherwise the two numbers match so add the item to the third (output) set, and go to the next item in both the other two sets. Make sense?
"The largest fire starts but with the smallest spark." - David Crow
|
|
|
|
|
Thank you DavidCrow!
Your method is great! I am wondering whether I can do some further improvements. I think we can check the size of each set, then we can use the elements in smaller set to find the matched ones in the bigger set (or vice versa?), which can improve the performnace -- but I am not sure about it. Do you have any comments?
regards,
George
|
|
|
|
|
George_George wrote: I think we can check the size of each set, then we can use the elements in smaller set to find the matched ones in the bigger set (or vice versa?), which can improve the performnace -- but I am not sure about it. Do you have any comments?
Just have your for/while loop check for remaining items in both sets. Something like:
while (there_are_items_in_set1 && there_are_items_in_set2)
...
"The largest fire starts but with the smallest spark." - David Crow
|
|
|
|
|
Use STL. The following calculates a set intersection:
Here's a complete example I had laying around:
----------------------------------------------
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
const char* g_Names1[] = {"Joe", "Paul", "Simon", "Steve", "Karl"};
const char** g_Names1Begin = &g_Names1[0];
const char** g_Names1End = &g_Names1[sizeof(g_Names1)/sizeof(g_Names1[0])];
const char* g_Names2[] = {"Paul", "Kate", "Oleg"};
const char** g_Names2Begin = &g_Names2[0];
const char** g_Names2End = &g_Names2[sizeof(g_Names2)/sizeof(g_Names2[0])];
struct CharLess
{
bool operator()(const char* p1, const char* p2) const
{
return strcmp(p1, p2)<0;
}
};
int main(int argc, char* argv[])
{
typedef vector<const char*> VEC;
VEC v1(g_Names1Begin, g_Names1End);
VEC v2(g_Names2Begin, g_Names2End);
sort(v1.begin(), v1.end(), CharLess());
sort(v2.begin(), v2.end(), CharLess());
set_intersection(
v1.begin(), v1.end(),
v2.begin(), v2.end(),
ostream_iterator<const char*>(cout, "\n"),
CharLess()
);
return 0;
}
Steve
|
|
|
|
|
Thank you Steve,
I noticed that you are using STL built-in algorithm set_intersection. Do you have any ideas of how to implement it efficient without STL? I need to save footprint on my device. Thank you!
regards,
George
|
|
|
|
|
Your fears that using STL will bloat your program are not well founded. You can check out the source code for set_intersection by looking in the file <algorithm>: it contains a for loop and two if. With STL you only pay for what you use. Note that the algorithm requires the data to be sorted thus you must count the code for the sort algorithm also.
Steve
|
|
|
|
|
Hi Steve,
I am developing on embedded device. So if I need to use C++, I have to port C++ runtime library to this platform, right (actually, I prefer C)? And it will both,
- Increase my working time;
- Increase the footprint to hold C++ runtime library (for example .so files on Linux).
Have I answered your question?
regards,
George
|
|
|
|
|
None of the algorithms I used (sort or set_intersection) use or have any need for the C runtime library. There is no distinct C++ runtime library. The only CRT function used is the one I introduced: strcmp (ignoring the functions I used to write the output to the console). None of what you say need be true. In general using STL will decrease your working time and will have not have a detrimental effect on the footprint of your EXE. Most of your fears are superstition.
Steve
|
|
|
|
|
Sorry Steve,
Maybe I have not make myself understood enough. I mean I prefer C. But in order to use sort or set_intersection, I have to use C++ runtime library. Correct?
regards,
George
|
|
|
|
|
George_George wrote: But in order to use sort or set_intersection, I have to use C++ runtime library. Correct?
This is not the case. Both sort and set_intersection are both just short inline functions with no dependencies on any runtime libraries. Have a look at the algorithm header file. In fact most or STL is like this. These are exceptions such as the stream and locale classes.
Steve
|
|
|
|
|
He's a version which sorts the array in-place without using a vector:
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
const char* g_Names1[] = {"Joe", "Paul", "Simon", "Steve", "Karl"};
const char** g_Names1Begin = &g_Names1[0];
const char** g_Names1End = &g_Names1[sizeof(g_Names1)/sizeof(g_Names1[0])];
const char* g_Names2[] = {"Paul", "Kate", "Oleg"};
const char** g_Names2Begin = &g_Names2[0];
const char** g_Names2End = &g_Names2[sizeof(g_Names2)/sizeof(g_Names2[0])];
struct CharLess
{
bool operator()(const char* p1, const char* p2) const
{
return strcmp(p1, p2)<0;
}
};
int main(int argc, char* argv[])
{
sort(g_Names1Begin, g_Names1End, CharLess());
sort(g_Names2Begin, g_Names2End, CharLess());
set_intersection(
g_Names1Begin, g_Names1End,
g_Names2Begin, g_Names2End,
ostream_iterator<const char*>(cout, "\n"),
CharLess()
);
return 0;
}
Steve
|
|
|
|
|
Hi Steve,
To me, it is the same -- since I am trying to remove STL/C++ and implement it by myself. I am looking for an efficient implementation -- there are a couple of sets and each contains a lot of data. Any comments or ideas?
regards,
George
|
|
|
|
|
If you really want to re-invent the wheel copy STL's code - all the source is there. After looking at the code in question you'll realise you should have just used it as is. You'll have a hard time matching STL's efficiency.
Steve
|
|
|
|
|
Thank you Steve,
STL's set_intersection is very efficient? Why? Does it have any special designs?
regards,
George
|
|
|
|
|
Which is the last Window Message when a Window is being destroyed?
WM_CLOSE<br />
WM_DESTROY<br />
WM_QUIT
Are there other messages when a Window is destroyed?
---
With best regards,
A Manchester United Fan
The Genius of a true fool is that he can mess up a foolproof plan!
-- modified at 3:14 Thursday 1st June, 2006
|
|
|
|
|
|
Thanks....
---
With best regards,
A Manchester United Fan
The Genius of a true fool is that he can mess up a foolproof plan!
|
|
|
|
|
I wonder if the two are the same in coding and result?
FILWY
|
|
|
|
|
|
the VC6 compiler was released before the last standard was official, so it is really not compliant to the C++ language standard.
if you have the choice between VC6 and VC2003, prefer VC2003
TOXCCT >>> GEII power
[VisualCalc 3.0 updated ][Flags Beginner's Guide new! ]
|
|
|
|
|
for mfc, they r almost same. but for atl, they r quite different,and not compatible. I perfer vc7.1, the compiling speed, the compiled file sizes r smaller. and especially, the codes look more perfect than doing it with vc6.
life is like a box of chocolate,you never know what you r going to get.
|
|
|
|
|
A thread created by using AfxBeginThread(RUNTIME_CLASS(CClientHandler));
can be end/destroyed by using AfxEndThread(..) , would it be called from inside of same thread.
If the AfxEndThread will end the thread then would the object created inside of that thread will also be destroyed?
Thanks
Regards.
|
|
|
|
|
AfxEndThread must be called from within the thread you wish to stop.
Steve
|
|
|
|
|
would this stop release all the memory that the thread and its members objects have occupied
Regards.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
