Mergring two string Arrays

[Sreedharamurthy K]

Hi,

I've two string arrays A & B. One of it is sorted B. A is not sorted. Now I
want array A to be same as array B. So I was thinking the following is the
right way:

for (elements in B)
check if the element exists in A
if it exists, go to the next element
else add this element

for (elements in A)
check if the element exists in B
if it exists, go to the next element
else remove this element

Is there a better way to do this to reduce the number of string comparion;
doing it faster??

Sorry if it is trivial and has been answered earlier. I searched a little
but could not find any relevant ones...
TIA.
-- Sree

 

[Sreedharamurthy K]

being specific in the logic:

for (elements in B) {
check if the element exists in A
if it exists, go to the next element
else add this element to A
}

for (elements in A) {
check if the element exists in B
if it exists, go to the next element
else remove this element from A
}

-- Sree

 

[CBFalconer]

I've two string arrays A & B. One of it is sorted B. A is not
sorted. Now I want array A to be same as array B. So I was
thinking the following is the right way:

The condition of B doesn't matter. Just copy A into B.

 

[Malcolm McLean]

Hi,

I've two string arrays A & B. One of it is sorted B. A is not sorted. Now
I want array A to be same as array B. So I was thinking the following is
the right way:

for (elements in B)
check if the element exists in A
if it exists, go to the next element
else add this element

for (elements in A)
check if the element exists in B
if it exists, go to the next element
else remove this element

Is there a better way to do this to reduce the number of string comparion;
doing it faster??

Sorry if it is trivial and has been answered earlier. I searched a little
but could not find any relevant ones...
TIA.

B is sorted, so call bsearch to find if each element in A exists in B, in
O(log N) time. Then if you find the element, flag it (there may be
complications if you allow duplicate elements). Then any unflagged elements
remaining in B do not exist in A.

 

[Sreedharamurthy K]

Thanks. I guess this will definitely improve!!

 

[Eric Sosman]

Sreedharamurthy K wrote On 08/02/07 16:56,:

Hi,

I've two string arrays A & B. One of it is sorted B. A is not sorted. Now I
want array A to be same as array B. So I was thinking the following is the
right way:

for (elements in B)
check if the element exists in A
if it exists, go to the next element
else add this element

for (elements in A)
check if the element exists in B
if it exists, go to the next element
else remove this element

Is there a better way to do this to reduce the number of string comparion;
doing it faster??

Sorry if it is trivial and has been answered earlier. I searched a little
but could not find any relevant ones...

Throw the old contents of `A' away and copy `B' to `A'.

 

[Sreedharamurthy K]

Thx. Easiest, I know... That would be my last resort... I wanted to know
if I could get it without have to recreate the entire array A from B.

 

[Eric Sosman]

Sreedharamurthy K wrote:

(.ereh dexiF) !GNITSOP-POT POTS ESAELP

> Thx. Easiest, I know... That would be my last resort... I wanted to know
> if I could get it without have to recreate the entire array A from B.

Instead of a single O(|B|) call to memcpy(), you prefer
to indulge in an O(|B| * |A|) procedure? That's like buying
a bigger car so you can carry home more lottery tickets.

 

[Malcolm McLean]

Sreedharamurthy K wrote:

(.ereh dexiF) !GNITSOP-POT POTS ESAELP



Instead of a single O(|B|) call to memcpy(), you prefer
to indulge in an O(|B| * |A|) procedure? That's like buying
a bigger car so you can carry home more lottery tickets.

You were right.
I had imagined that the the order in A would need to be preserved or
something, but in fact it is just a copy job.