Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Find if elements of one array are present in the other and return a boolean array

Reply
Thread Tools

Find if elements of one array are present in the other and return a boolean array

 
 
Shalini
Guest
Posts: n/a
 
      01-09-2004
Hi ,
Is the code below efficient??

bool *isElement(char **a1,long lengtha1,char **a2,long lengtha2){
charQuickSort(a2, 0, (lengtha2-1));
bool *tag=(bool*)calloc(lengtha1,sizeof(bool));

int i,j;
for(j = 0; j < lengtha1; j++){
for(i = 0; i < lengtha2;i++){
if(strcmp(a1[j],a2[i])==0){
tag[j]=true;
// printf("%d\n",tag[j]);
break;
}
if(strcmp(a1[j],a2[i])<0 || (i == (lengtha2-1))){
tag[j] = false;
// printf("%d\n",tag[j]);
break;
}
}
}

return(tag);
}


void charQuickSort(char **vals, int l, int r)
{
int i,j,m;
char **v=(char **)calloc(1,sizeof(char *));
char **t=(char **)calloc(1,sizeof(char *));

if(r > l)
{
m = (r+l)/2;
if(strcmp(vals[m] ,vals[r])<0)
{
if(strcmp(vals[l] ,vals[m])<0)
{
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[m];
vals[m] = t[0];
//vals[m] = strdup(t);
}
else if (strcmp(vals[l] ,vals[r])<0)
{
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[l];
vals[l] = t[0];
//vals[l] = strdup(t);
}
}
else
{
if(strcmp(vals[l] ,vals[m])>0)
{
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[m];
vals[m] = t[0];
//vals[m] = strdup(t);
}
else if (strcmp(vals[l], vals[r])>0)
{
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[l];
vals[l] = t[0];
//vals[l] = strdup(t);

}
}
v[0]=vals[r];
// strcpy(v,vals[r]);
i = l-1;
j = r;
do {

for(i++; strcmp(vals[i], v[0])<0 && i <= r; i++) {
// printf("%d ",i);
}
/*for(i++; strcmp(vals[i], v)<0 && i <= r; i++) {
//printf("%d ",i);
}*/

for(j--; strcmp(vals[j],v[0])>0 && j > l; j--);
// for(j--; strcmp(vals[j],v)>0 && j > l; j--);
t[0]=vals[i];
// strcpy(t,vals[i]);
vals[i] = vals[j];
vals[j] = t[0];
//vals[j] = strdup(t);

}
while( j > i);
vals[j] = vals[i];
vals[i] = vals[r];
vals[r] = t[0];
//vals[r] = strdup(t);
charQuickSort(vals, l, i-1);
charQuickSort(vals,i+1,r);
}

}
 
Reply With Quote
 
 
 
 
Brian Genisio
Guest
Posts: n/a
 
      01-09-2004
Shalini wrote:

> Hi ,
> Is the code below efficient??
>
> bool *isElement(char **a1,long lengtha1,char **a2,long lengtha2){
> charQuickSort(a2, 0, (lengtha2-1));
> bool *tag=(bool*)calloc(lengtha1,sizeof(bool));
>
> int i,j;
> for(j = 0; j < lengtha1; j++){
> for(i = 0; i < lengtha2;i++){
> if(strcmp(a1[j],a2[i])==0){
> tag[j]=true;
> // printf("%d\n",tag[j]);
> break;
> }
> if(strcmp(a1[j],a2[i])<0 || (i == (lengtha2-1))){
> tag[j] = false;
> // printf("%d\n",tag[j]);
> break;
> }
> }
> }
>
> return(tag);
> }
>
>
> void charQuickSort(char **vals, int l, int r)
> {
> int i,j,m;
> char **v=(char **)calloc(1,sizeof(char *));
> char **t=(char **)calloc(1,sizeof(char *));
>
> if(r > l)
> {
> m = (r+l)/2;
> if(strcmp(vals[m] ,vals[r])<0)
> {
> if(strcmp(vals[l] ,vals[m])<0)
> {
> t[0]=vals[r];
> //strcpy(t,vals[r]);
> vals[r] = vals[m];
> vals[m] = t[0];
> //vals[m] = strdup(t);
> }
> else if (strcmp(vals[l] ,vals[r])<0)
> {
> t[0]=vals[r];
> //strcpy(t,vals[r]);
> vals[r] = vals[l];
> vals[l] = t[0];
> //vals[l] = strdup(t);
> }
> }
> else
> {
> if(strcmp(vals[l] ,vals[m])>0)
> {
> t[0]=vals[r];
> //strcpy(t,vals[r]);
> vals[r] = vals[m];
> vals[m] = t[0];
> //vals[m] = strdup(t);
> }
> else if (strcmp(vals[l], vals[r])>0)
> {
> t[0]=vals[r];
> //strcpy(t,vals[r]);
> vals[r] = vals[l];
> vals[l] = t[0];
> //vals[l] = strdup(t);
>
> }
> }
> v[0]=vals[r];
> // strcpy(v,vals[r]);
> i = l-1;
> j = r;
> do {
>
> for(i++; strcmp(vals[i], v[0])<0 && i <= r; i++) {
> // printf("%d ",i);
> }
> /*for(i++; strcmp(vals[i], v)<0 && i <= r; i++) {
> //printf("%d ",i);
> }*/
>
> for(j--; strcmp(vals[j],v[0])>0 && j > l; j--);
> // for(j--; strcmp(vals[j],v)>0 && j > l; j--);
> t[0]=vals[i];
> // strcpy(t,vals[i]);
> vals[i] = vals[j];
> vals[j] = t[0];
> //vals[j] = strdup(t);
>
> }
> while( j > i);
> vals[j] = vals[i];
> vals[i] = vals[r];
> vals[r] = t[0];
> //vals[r] = strdup(t);
> charQuickSort(vals, l, i-1);
> charQuickSort(vals,i+1,r);
> }
>
> }



Here is pseudocode for a very similar problem I needed to solve... I
solved it in O(nln), where your solution is O(n^2).

Problem: Given Arrays A1 and A2, find if there exist any in common
Solution:

1. Sort A1 with an O(nln) search. *hint... QuickSort is O(n^2) in worst
case, so it is not really the best, if you have a lot of numbers.... You
can do better, usually

2. For every item in A2 (O(n)), do a binary search for the item in A1
(O(ln), since it is sorted).

Each step is O(nln), which gives an O(nln) solution.

That is the fastest that I know how to solve the problem.
Brian



 
Reply With Quote
 
 
 
 
Brian Genisio
Guest
Posts: n/a
 
      01-09-2004
Brian Genisio wrote:

> Shalini wrote:
>
>> Hi ,
>> Is the code below efficient??
>>
>> bool *isElement(char **a1,long lengtha1,char **a2,long lengtha2){
>> charQuickSort(a2, 0, (lengtha2-1));
>> bool *tag=(bool*)calloc(lengtha1,sizeof(bool));
>>
>> int i,j;
>> for(j = 0; j < lengtha1; j++){
>> for(i = 0; i < lengtha2;i++){
>> if(strcmp(a1[j],a2[i])==0){
>> tag[j]=true;
>> // printf("%d\n",tag[j]);
>> break;
>> }
>> if(strcmp(a1[j],a2[i])<0 || (i == (lengtha2-1))){
>> tag[j] = false;
>> // printf("%d\n",tag[j]);
>> break;
>> }
>> }
>> }
>>
>> return(tag);
>> }
>>
>>
>> void charQuickSort(char **vals, int l, int r)
>> {
>> int i,j,m;
>> char **v=(char **)calloc(1,sizeof(char *));
>> char **t=(char **)calloc(1,sizeof(char *));
>>
>> if(r > l) {
>> m = (r+l)/2;
>> if(strcmp(vals[m] ,vals[r])<0)
>> {
>> if(strcmp(vals[l] ,vals[m])<0)
>> {
>> t[0]=vals[r];
>> //strcpy(t,vals[r]);
>> vals[r] = vals[m];
>> vals[m] = t[0];
>> //vals[m] = strdup(t);
>> } else if (strcmp(vals[l]
>> ,vals[r])<0) {
>> t[0]=vals[r];
>> //strcpy(t,vals[r]);
>> vals[r] = vals[l];
>> vals[l] = t[0];
>> //vals[l] = strdup(t);
>> }
>> } else
>> {
>> if(strcmp(vals[l] ,vals[m])>0)
>> {
>> t[0]=vals[r];
>> //strcpy(t,vals[r]);
>> vals[r] = vals[m];
>> vals[m] = t[0];
>> //vals[m] = strdup(t);
>> } else if (strcmp(vals[l],
>> vals[r])>0)
>> {
>> t[0]=vals[r];
>> //strcpy(t,vals[r]);
>> vals[r] = vals[l];
>> vals[l] = t[0];
>> //vals[l] = strdup(t);
>>
>> }
>> }
>> v[0]=vals[r];
>> // strcpy(v,vals[r]);
>> i = l-1;
>> j = r;
>> do {
>>
>> for(i++; strcmp(vals[i], v[0])<0 && i <= r; i++) {
>> // printf("%d ",i);
>> }
>> /*for(i++; strcmp(vals[i], v)<0 && i <= r; i++) {
>> //printf("%d ",i);
>> }*/
>>
>> for(j--; strcmp(vals[j],v[0])>0 && j > l; j--);
>> // for(j--; strcmp(vals[j],v)>0 && j > l; j--);
>> t[0]=vals[i];
>> // strcpy(t,vals[i]);
>> vals[i] = vals[j];
>> vals[j] = t[0];
>> //vals[j] = strdup(t);
>>
>> } while( j > i);
>> vals[j] = vals[i];
>> vals[i] = vals[r];
>> vals[r] = t[0];
>> //vals[r] = strdup(t);
>> charQuickSort(vals, l, i-1);
>> charQuickSort(vals,i+1,r);
>> }
>> }

>
>
>
> Here is pseudocode for a very similar problem I needed to solve... I
> solved it in O(nln), where your solution is O(n^2).
>
> Problem: Given Arrays A1 and A2, find if there exist any in common
> Solution:
>
> 1. Sort A1 with an O(nln) search. *hint... QuickSort is O(n^2) in worst
> case, so it is not really the best, if you have a lot of numbers.... You
> can do better, usually
>
> 2. For every item in A2 (O(n)), do a binary search for the item in A1
> (O(ln), since it is sorted).
>
> Each step is O(nln), which gives an O(nln) solution.
>
> That is the fastest that I know how to solve the problem.
> Brian
>


After looking again, I did not give you a solution for the problem you
put out... sorry.

To clarify... quicksort cannot guarantee efficiency, so I would use
something else.... possibly a randomized quicksort, which is better for
the average time, but is still worst case O(n^2)

For your problem, I have a better solution (for speed efficiency)...

Sort BOTH arrays using an O(nln) sort.
Move pointers in both arrays, since they are both sorted... Using
integers, you can see, you can compare both in a _single scan. The same
is true for string compares.

1 3 4 6 7 10
1 2 5 6 7 9 10

This solution will solve your problem in O(nln), which beats your
current solution of O(n^2)

Brian

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Subtle difference between boolean value and boolean comparison? Metre Meter Javascript 7 08-06-2010 08:40 PM
find if an array has any element present in another array Charanya Nagarajan Ruby 6 04-30-2009 11:14 AM
difference between 'boolean' and 'java.lang.Boolean' J Leonard Java 4 01-19-2008 02:56 AM
OS present but not present. XPD NZ Computing 4 04-11-2007 11:22 PM
Schema: express that "@a present if and only if @b present", where @a, @b are attributes Ralf Wahner XML 5 12-24-2003 11:37 AM



Advertisments