Mam fazę przygotowania:
vector<int> vecA;
vector<int> vecB;
srand(1000);
for (int i = 0; i < 16; i++) vecA.push_back(rand() % 20);
for (int i = 0; i < 12; i++) vecB.push_back(rand() % 20);
sort(vecA.begin(), vecA.end());
sort(vecB.begin(), vecB.end());

Algorytm:
int i1 = 0, i2 = 0;
while (i1 < vecA.size() && i2 < vecB.size())
{
if (vecA[i1] < vecB[i2])
{
printf("w pierwszym %d\n", vecA[i1]);
i1++;
}
else if (vecA[i1] > vecB[i2])
{
printf("w drugim %d\n", vecB[i2]);
i2++;
}
else
{
printf("w obu %d\n", vecA[i1]);
i1++;
i2++;
}
}
printf("dokończenie A\n");
while (i1 < vecA.size())
{
printf("w pierwszym %d\n", vecA[i1]);
i1++;
}
printf("dokończenie B\n");
while (i2 < vecB.size())
{
printf("w drugim %d\n", vecB[i2]);
i1++;
}

Dobre do porównywania czy w obu katalogach te same pliki na przykład,
ale: gdy mamy: 0 0 1 2 4 4 7 oraz 1 4 5 5 6 8
to wtedy wypisze:
w pierwszym 2
w obu 4
w pierwszym 4
w drugim 5

pierwszą czwórkę kwalifikując do "w obu", drugą do "w pierwszym", a mi
tym razem chodzi o to by wypisywać tylko w obu, wszystkie powtarzające
się elementy, czyli ma wypisać:
w obu 4
w obu 4

Jak należy zmodyfikować algorytm?

do góry

W dniu 20.05.2016 o 15:46, Borneq pisze:
> if (vecA[i1] < vecB[i2])
> {
> printf("w pierwszym %d\n", vecA[i1]);
> i1++;
> }
> else if (vecA[i1] > vecB[i2])
> {
> printf("w drugim %d\n", vecB[i2]);
> i2++;
> }

Dwa pliki:

0 1 5 8 9 11 11 15 17 17 20 25

1 1 1 3 4 4 8 8 8 11 16 17 17 17 25

0 < 1 - czyta pierwszy plik
1 = 1 - wypisuje że w obu
zapamiętuje pozycję w obu, czyta oba
5 > 1 ale 1=poprzednia pozycja w obu, więc wypisuje 1 z drugiej listy
czyta drugi plik
5 > 1 wypisuj 1 z drugiej listy
5 > 3 czyta drugi plik
5 > 4 czyta drugi plik
5 > 4 czyta drugi plik
5 < 8 - czyta pierwszy plik
8 = 8 zapamiętuje klucz 8

czyli trzeba mieć flagę: ostatnio był w obu

do góry

On Friday, May 20, 2016 at 5:13:45 PM UTC+2, Borneq wrote:
> W dniu 20.05.2016 o 15:46, Borneq pisze:
> > if (vecA[i1] < vecB[i2])
> > {
> > printf("w pierwszym %d\n", vecA[i1]);
> > i1++;
> > }
> > else if (vecA[i1] > vecB[i2])
> > {
> > printf("w drugim %d\n", vecB[i2]);
> > i2++;
> > }
>
> Dwa pliki:
>
> 0 1 5 8 9 11 11 15 17 17 20 25
>
> 1 1 1 3 4 4 8 8 8 11 16 17 17 17 25
>
> 0 < 1 - czyta pierwszy plik
> 1 = 1 - wypisuje że w obu
> zapamiętuje pozycję w obu, czyta oba
> 5 > 1 ale 1=poprzednia pozycja w obu, więc wypisuje 1 z drugiej listy
> czyta drugi plik
> 5 > 1 wypisuj 1 z drugiej listy
> 5 > 3 czyta drugi plik
> 5 > 4 czyta drugi plik
> 5 > 4 czyta drugi plik
> 5 < 8 - czyta pierwszy plik
> 8 = 8 zapamiętuje klucz 8
>
> czyli trzeba mieć flagę: ostatnio był w obu

Ja bym trzymał ostatni wczytany element. Wczytuję tam gdzie jest
najmniejszy (albo największy, zależy jak były posortowane) element.

Jeśli to działa na pamięci RAM, to wersja z hash-table może
zadziałać szybciej niż z sortowaniem.


Pozdrawiam

do góry

W dniu 20.05.2016 o 17:20, M.M. pisze:
> Jeśli to działa na pamięci RAM, to wersja z hash-table może
> zadziałać szybciej niż z sortowaniem.

Zrobiłem tak:
int i1 = 0, i2 = 0;
int valueBoth = 0;
bool lastBoth = false;
while (i1 < vecA.size() && i2 < vecB.size())
{
if (vecA[i1] < vecB[i2])
{
if (lastBoth)
{
if (vecA[i1] == valueBoth)
printf("match - pierwsza lista %d\n", vecA[i1]);
else
lastBoth = false;
}
i1++;
}
else if (vecA[i1] > vecB[i2])
{
if (lastBoth)
{
if (vecB[i2] == valueBoth)
printf("match - druga lista %d\n", vecB[i2]);
else
lastBoth = false;
}
i2++;
}
else
{
printf("match - dwie listy %d\n", vecA[i1]);
valueBoth = vecA[i1];
lastBoth = true;
i1++;
i2++;
}
}
printf("dokończenie A\n");
while (i1 < vecA.size())
{
if (lastBoth)
{
if (vecA[i1] == valueBoth)
printf("match - pierwsza lista %d\n", vecA[i1]);
else
lastBoth = false;
}
i1++;
}
printf("dokończenie B\n");
while (i2 < vecB.size())
{
if (lastBoth)
{
if (vecB[i2] == valueBoth)
printf("match - druga lista %d\n", vecB[i2]);
else
lastBoth = false;
}
i2++;
}

Mam dwie pomocnicze zmienne, nie wystarczy valueBoth, które na początku
trzeba by inicjować na +maxint (nawet to nie pewne, bo co gdy w tablicy
się pojawi maxint?) ale porównanie z bool lastBoth jest znacznie szybsze
niż valueBoth, które będzie kluczem i trzeba będzie użyć strcmp()


A to przykładowe dane:
vecA.push_back(0);
vecA.push_back(1);
vecA.push_back(5);
vecA.push_back(8);
vecA.push_back(9);
vecA.push_back(11);
vecA.push_back(11);
vecA.push_back(15);
vecA.push_back(17);
vecA.push_back(17);
vecA.push_back(20);
vecA.push_back(25);
vecA.push_back(25);

vecB.push_back(1);
vecB.push_back(1);
vecB.push_back(1);
vecB.push_back(3);
vecB.push_back(4);
vecB.push_back(4);
vecB.push_back(8);
vecB.push_back(8);
vecB.push_back(8);
vecB.push_back(11);
vecB.push_back(16);
vecB.push_back(17);
vecB.push_back(17);
vecB.push_back(17);
vecB.push_back(25);

do góry

W dniu 20.05.2016 o 17:55, Borneq pisze:
> Zrobiłem tak:
> while (i1 < vecA.size() && i2 < vecB.size())

Ale potrzebne wersja strumieniowa, która jednak się różni, bo każdy
odczyt ze strumienia oznacza zwiększenie indeksu.
Potrzebne flagi , czy bufor aktualny czy pusty.

int i1 = 0, i2 = 0;
int valueBoth = 0;
bool lastBoth = false;
int recA; int recB;
bool recAEmpty = true;//get ustawia na false, odczyt z bufora na true
bool recBEmpty = true;
while ((i1 < vecA.size() || !recAEmpty) && (i2 < vecB.size() ||
!recBEmpty) )
{
if (recAEmpty)
{
recA = vecA[i1]; i1++;
recAEmpty = false;
}
if (recBEmpty)
{
recB = vecB[i2]; i2++;
recBEmpty = false;
}
if (recA < recB)
{
if (lastBoth)
{
if (recA == valueBoth)
printf("match - pierwsza lista %d\n", recA);
else
lastBoth = false;
}
recAEmpty = true;
}
else if (recA > recB)
{
if (lastBoth)
{
if (recB == valueBoth)
printf("match - druga lista %d\n", recB);
else
lastBoth = false;
}
recBEmpty = true;
}
else
{
printf("match - dwie listy %d\n", recA);
valueBoth = recA;
lastBoth = true;
recAEmpty = true;
recBEmpty = true;
}
}
printf("dokończenie A\n");
while (i1 < vecA.size())
{

recA = vecA[i1]; i1++;
if (lastBoth)
{
if (recA == valueBoth)
printf("match - pierwsza lista %d\n", recA);
else
lastBoth = false;
}
i1++;
}
printf("dokonczenie B\n");
while (i2 < vecB.size())
{
recB = vecA[i2]; i2++;
if (lastBoth)
{
if (recB == valueBoth)
printf("match - druga lista %d\n", recB);
else
lastBoth = false;
}
i2++;
}

do góry

On Friday, May 20, 2016 at 7:14:47 PM UTC+2, Borneq wrote:
> W dniu 20.05.2016 o 17:55, Borneq pisze:
> > Zrobiłem tak:
> > while (i1 < vecA.size() && i2 < vecB.size())

A tak jak poniżej, dla dowolnej ilości wektorów?

isEnd( vec[] ) {
int i=0;
while( i<vec.size() && vec[i].isEnd() )
i++;
return i==vec.size();
}

getMin( vec[] ) {
min = -1 ;
for( i=0 ; i<vec.size() ; i++ ) {
if( vec[i].isEnd() )
continue;
if( min == -1 )
min = i;
else if( vec[min].next() > vec[i].next() )
min = i;
}
return vec[min].getNext();
}

for( i=0 ; i<vec.size() ; i++ )
sort( vec[i] );

val1 = getMin( vec );
while( ! isEnd( vec ) ) {
val2 = getMin( vec );
if( val1 == val2 )
print val1;
val1 = val2;
}


Pozdrawiam

do góry