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?

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