Jak porównać dwa wektory?

0

Jak najtaniej porównać dwa wektory intów? Oba mają ten sam rozmiar. Chcę tylko jak najszybciej sprawdzić czy sekwencja liczb jest identyczna w obu. std::equal() czy operatorem porównania?

0

Oblicz hashe, jak wyjdą równe to są równe (zakładając, że masz wiele takich porównań w planie).

2

Może lepiej opisz dokładnie jaki masz problem.
Dlaczego potrzebujesz tego porównania i dlaczego uważasz, że standardowy operator porównania nie jest dostatecznie dobry.

0

std::equal() czy operatorem porównania?

Operatorem porównania. Takowy operator dostaje całe pamięci do porównania więc używając ich możesz się spodziewać ekwiwalentu memcmp, co potwierdza napisany na szybko, niedoskonały benchmark https://quick-bench.com/q/TJVSMUp0zBuXXPDWWefufq5Fq1A

0

#include <iostream>
#include <vector>
#include <random>

std::random_device rd;

int main() {
    std::vector<int> deck1{4,5,2,5,3,1,4,1,2,3,1,3,4,0,2,0,1,5,4,3,2,0,0,5};
    std::vector<int> deck2{0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5};
    for (uint64_t repetition=0;repetition<1000000000000; repetition++)
    {
        shuffle(deck2.begin(), deck2.end(), rd);
        if (deck1==deck2)
            std::cout << "Tak, za: " << repetition << " razem" << "\n";
    }
    std::cout << "Koniec";
    std::cin.get();
    return 0;
}

Po godzinie tasowania talii deck2 program nie wylosował sekwencji z deck1. Z rachunku prawdopodobieństwa jestem cienki jak barszcz.

0

Dla mniejszych tablic działa, więc pewnie za mało powtórzeń: https://godbolt.org/z/neMr6ajzo

3891532908
Tak, za: 0 razem
2252884352
3291673630
1763740559
Tak, za: 3 razem
3876415575
952409269
3368736769
2458722453
551803985
3440206268
4081640880
3

Permutacja z powtórzeniami: https://www.naukowiec.org/wiedza/matematyka/permutacje-z-powtorzeniami_804.html
U góry 24! = 620448401733239439360000
Na dole 4! ^6 = 191102976
Czyli: 3246670537110000 kombinacji.

 3,246,670,537,110,000
     1,000,000,000,000 <- twoich pętli obrotów jest

Czyli jeszcze ~3 245 godzin i powinieneś dostać pozytywny wynik.

Nie biorę odpowiedzialności za poprawność wyliczeń

edycje: trochę się rypnąłem w obliczeniach

0

Ja jeszcze dodam, że nawet bardzo optymistycznie licząc że jedna iteracja to 10ns (to będzie 100 cykli procesora 10GHz), to czas wykonania tej pętli for to prawie 3 godziny.
Ergo po godzinie straciłeś cierpliwość, a nie to że program się skończył.

0

Tak a propos, czy w docelowym programie też będziesz mieć powtórzenia?
Czy masz jakieś ograniczenia na te liczby wewnątrz wektora?

0

To mój stary program, gra w "Wojnę". Przy 24 kartach w talii zdarzają się nieskończone partie. Już go kiedyś pokazywałem w sekcji "opinie i recenzje".

#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <random>
#include <queue>

std::random_device rd;

class Wojna
{
    int how_many_cards;
    std::vector<int> deck;
    std::queue<int> Player_A;
    std::queue<int> Player_B;
    std::vector<int> table[2];

    void ShuffleDeck()
    {
        int how_many_figures = how_many_cards / 4;
        for (int i = 0; i < how_many_cards; i++) deck.push_back(i % how_many_figures);
        std::shuffle(deck.begin(), deck.end(), rd);
    }

    void HandOutCards()
    {
        for (int i = 0; i < (how_many_cards / 2); i++) Player_A.push(deck[i]);
        for (int i = (how_many_cards / 2); i < how_many_cards; i++) Player_B.push(deck[i]);
    }

    void LayCards()
    {
        if ((!Player_A.empty()) && (!Player_B.empty())) {
            table[0].push_back(Player_A.front());
            Player_A.pop();
            table[1].push_back(Player_B.front());
            Player_B.pop();
        }
    }

    void ShiftCards(std::queue<int> & Player, int winner)
    {
            while (!table[winner].empty())
            {
                Player.push(table[winner][0]);
                table[winner].erase(table[winner].begin());
            }
            while (!table[!winner].empty())
            {
                Player.push(table[!winner][0]);
                table[!winner].erase(table[!winner].begin());
            }
    }

    void Compare()
    {
        if ((!table[0].empty()) && (!table[1].empty()))
        {
             if ( (table[0].back()) > (table[1].back()) )
                ShiftCards(Player_A, 0);

            if ( (table[0].back()) < (table[1].back()) )
                ShiftCards(Player_B, 1);

            if ((table[0].size() > 0)&&(table[1].size() > 0))
                if ( (table[0].back()) == (table[1].back()) )
                    LayCards();
        }
    }

public:
    Wojna(int ile_kart) : how_many_cards(ile_kart){};
    void Graj() {
        const uint64_t how_many_rounds{10000000};
        int clashes{0};
        int clashes_max{0};
        int clashes_avg{0};
        uint64_t clashes_sum{0};
        uint64_t winner_A{0}, winner_B{0};
        for (uint64_t rounds = 0; rounds < how_many_rounds; rounds++)
        {
            ShuffleDeck();
            HandOutCards();
            while (!Player_A.empty() && !Player_B.empty())
            {
                clashes++;
                LayCards();
                Compare();
            }
            if (Player_A.empty()) winner_A++;
            if (Player_B.empty()) winner_B++;
            if (rounds % (600000 / how_many_cards) == 0)    std::cout << "Gracz A wygral "
            << winner_A << " razy" << "\t" "Gracz B wygral " << winner_B
            << " razy\tclashes_max: " << clashes_max << "\tclashes_avg: " << clashes_avg << "\n";
            deck.clear();
            while (!Player_A.empty()) Player_A.pop();
            while (!Player_B.empty()) Player_B.pop();
            table[0].clear();
            table[1].clear();
            clashes_sum+=clashes;
            clashes_avg = double(clashes_sum) / (double)rounds;
            if (clashes_max < clashes) clashes_max=clashes;

            clashes=0;
        }
        std::cout << winner_A << "\t" << winner_B << "    Na koniec\n";
    }
};



int main() {
    int ile_kart{0};
    do
    {
        std::cout << "Podaj liczbe kart podzienla przez 4\n";
        std::cin >> ile_kart;
    }while  (ile_kart % 4);
    while (std::cin.get() != '\n') continue;
    Wojna wojna(ile_kart);
    clock_t start, stop;
    double czas;
    start = clock();
    wojna.Graj();
    stop = clock();
    czas = (double)(stop - start) / CLOCKS_PER_SEC;
    std::cout << "Czas wykonania: " << czas << std::endl;
    std::cin.get();
    return 0;
}


0

Czyli nie może być powtórek?

0

Przy wylosowanej sekwencji 4 - 5 - 2 - 5 - 3 - 1 - 4 - 1 - 2 - 3 - 1 - 3 - 4 - 0 - 2 - 0 - 1 - 5 - 4 - 3 - 2 - 0 - 0 - 5 partia się nie kończy. Przy kilku innych też.

0

Nie chce mi się analizować kodu, czy jest istotna kolejność kart na rękach graczy?

0

Jeśli gracz, który wygrał starcie zbiera karty "od spodu" wtedy cała partia gry się kończy, zaś jeśli zbiera "od dołu" wtedy bardzo często partia jest nieskończona.

0

Wykres.jpg

Tak się rozkładają ilości starć w partiach gry.

0

Wyczytałem w internecie, że ktoś matematycznie obliczył, że każda partia "Wojny" musi się skończyć. Więc coś pewnie spieprzyłem. Nie zawracajmy sobie tym głowy. Ja to tylko tak dla jaj napisałem bo mi się nudziło. Wesołych Świąt.

1

Wg mnie:

  • nie używaj szuffle tylko next_permutation() ale ta podpowiedź już chyba padła wcześniej.
  • Zamiast vector<> zrób własną listę cykliczną opartą na array<>

@enedil,
Nie zupełnie:

#include <iostream>
#include <array>
#include <vector>
using namespace std;

int main()
{
	array<int,3> a;
	cout<<sizeof(a)<<endl;
	array<int,5> b;
	cout<<sizeof(b)<<endl;
	vector<int> c(3);
	cout<<sizeof(c)<<endl;
	vector<int> d(5);
	cout<<sizeof(d)<<endl;
    return 0;
}

array "siedzi" na stosie.

1 użytkowników online, w tym zalogowanych: 0, gości: 1