Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #28613 > unrolled thread

Matching - rozszerzone porównanie dwóch posortowanych list

Started byBorneq <borneq@antyspam.hidden.pl>
First post2016-05-20 15:46 +0200
Last post2016-05-20 13:18 -0700
Articles 6 — 2 participants

Back to article view | Back to pl.comp.programming

Contents

  Matching - rozszerzone porównanie dwóch posortowanych list Borneq <borneq@antyspam.hidden.pl> - 2016-05-20 15:46 +0200
    Re: Matching - rozszerzone porównanie dwóch posortowanych list Borneq <borneq@antyspam.hidden.pl> - 2016-05-20 17:13 +0200
      Re: Matching - rozszerzone porównanie dwóch posortowanych list "M.M." <mmarszik@gmail.com> - 2016-05-20 08:20 -0700
        Re: Matching - rozszerzone porównanie dwóch posortowanych list Borneq <borneq@antyspam.hidden.pl> - 2016-05-20 17:55 +0200
          Re: Matching - rozszerzone porównanie dwóch posortowanych list Borneq <borneq@antyspam.hidden.pl> - 2016-05-20 19:14 +0200
            Re: Matching - rozszerzone porównanie dwóch posortowanych list "M.M." <mmarszik@gmail.com> - 2016-05-20 13:18 -0700

#28613 — Matching - rozszerzone porównanie dwóch posortowanych list

FromBorneq <borneq@antyspam.hidden.pl>
Date2016-05-20 15:46 +0200
SubjectMatching - rozszerzone porównanie dwóch posortowanych list
Message-ID<nhn4f9$d67$1@node2.news.atman.pl>
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?

[toc] | [next] | [standalone]

#28614

FromBorneq <borneq@antyspam.hidden.pl>
Date2016-05-20 17:13 +0200
Message-ID<nhn9j8$i1r$1@node2.news.atman.pl>
In reply to#28613
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

[toc] | [prev] | [next] | [standalone]

#28615

From"M.M." <mmarszik@gmail.com>
Date2016-05-20 08:20 -0700
Message-ID<41188837-396f-41ff-983d-fd516cb6bd3e@googlegroups.com>
In reply to#28614
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

[toc] | [prev] | [next] | [standalone]

#28616

FromBorneq <borneq@antyspam.hidden.pl>
Date2016-05-20 17:55 +0200
Message-ID<nhnc15$khu$1@node2.news.atman.pl>
In reply to#28615
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);

[toc] | [prev] | [next] | [standalone]

#28617

FromBorneq <borneq@antyspam.hidden.pl>
Date2016-05-20 19:14 +0200
Message-ID<nhngm6$p2c$1@node2.news.atman.pl>
In reply to#28616
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++;
	}

[toc] | [prev] | [next] | [standalone]

#28618

From"M.M." <mmarszik@gmail.com>
Date2016-05-20 13:18 -0700
Message-ID<f27bfdb4-0561-45b4-a230-b9e143ae0fa2@googlegroups.com>
In reply to#28617
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

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web