eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingMatching - rozszerzone porównanie dwóch posortowanych list
Ilość wypowiedzi w tym wątku: 6

  • 1. Data: 2016-05-20 15:46:17
    Temat: Matching - rozszerzone porównanie dwóch posortowanych list
    Od: Borneq <b...@a...hidden.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?


  • 2. Data: 2016-05-20 17:13:44
    Temat: Re: Matching - rozszerzone porównanie dwóch posortowanych list
    Od: Borneq <b...@a...hidden.pl>

    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


  • 3. Data: 2016-05-20 17:20:49
    Temat: Re: Matching - rozszerzone porównanie dwóch posortowanych list
    Od: "M.M." <m...@g...com>

    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


  • 4. Data: 2016-05-20 17:55:16
    Temat: Re: Matching - rozszerzone porównanie dwóch posortowanych list
    Od: Borneq <b...@a...hidden.pl>

    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);


  • 5. Data: 2016-05-20 19:14:46
    Temat: Re: Matching - rozszerzone porównanie dwóch posortowanych list
    Od: Borneq <b...@a...hidden.pl>

    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++;
    }



  • 6. Data: 2016-05-20 22:18:31
    Temat: Re: Matching - rozszerzone porównanie dwóch posortowanych list
    Od: "M.M." <m...@g...com>

    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

strony : [ 1 ]


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: