Mam porównywać kolejno liczby składające się z 30 cyfr. Zrobiłem to na dwóch tablicach. W pierwszej dane wejściowe, w drugiej dane wyjściowe. Wykorzystałem do tego stringi i kolejno porównywałem pierwszy element z każdym elementem z drugiem tablicy, potem drugi element z pierwszej tablicy z każdym elementem z drugiej tablicy. Co można zrobić aby ten program działał szybciej i nie wykonywał aż tylu operacji?
0
0
Strasznie zamotane. Co jest w tych tablicach? Liczby czy kolejne literki już po zamienieniu na string?
Co to znaczy porównywać liczby? Masz 2 liczby, sprawdziłeś że pierwsza jest mniejsza niz druga i co dalej?
0
Tak właśnie robię.
0
Chodzi o to, że mam dwie tablicy stringów, a w nich bezpośrednią liczby ale w ciągach znaków. W stringach mam jakby liczby.
Porównuje potem te stringi za pomocą funkcji bibliotecznej ze sobą.
0
Tak, ale chce to zrobić jeszcze jakoś szybciej, da się w jednej pętli?
3
W jakiej pętli? O czym w ogóle mówisz? Porównanie 2 stringów wygląda tak:
if (string1 < string2)
Nie ma żadnej pętli.
Więc może napisz co chcesz osiągnąć całościowo, bo w tej chwili to jest rozmowa głuchego z niemym.
0
Wrzuć może lepiej kod, bo takie zadania mają z reguły złożoność liniową i jestem niesamowicie ciekaw, jak zaprojektowałeś taki prosty program z O(n^2).
0
for(int i = 0; i < n; ++i)
{
bool zmienna = 0; // okresla czy w drugim pliku tekstowym pojawila sie ta liczba co w 1 pliku.
for(int j = 0; j < n; ++j)
{
if(tablica2[i].compare(tablica[j]) == 0)
{
zmienna = 1;
break;
}
}
0
Jezus Maria. Nie musisz trzymać każdej cyfry w oddzielnym stringu, a w te tablicy. Możesz trzymać całą liczbę trzymać w jednym stringu i porównywać je za pomocą wbudowanych metod.
0
No ale jak mam sporo tych liczb to jak je w jedną zmienną zapiszę. Jak muszę jedną porównać z każdą z drugiej tablicy.
0
Generalnie możesz posortować obydwie tablice i wtedy jeśli np. masz taki plik:
1111
1133
1144
2200
To sprawdzanie czy istnieje liczba 1122 nie będzie wymagało przelecenia po wszystkich ciągach, tylko dwóch (pierwszy, drugi i dalej już nie ma sensu, bo wiesz na 100%, że skoro jest posortowane, to tam nie będzie).
Ew. jakieś drzewo sufiksowe...
0
Skąd wiadomo, że liczby 1122 nie będzie w drugiej tablicy?
0
Z jednej tablicy bierzesz te liczby i sprawdzasz czy nie ma ich w drugiej, c'nie?
No to w takim razie ja Ci podałem sposób na samo sprawdzanie :P
Natomiast pesymistyczna złożoność tego rozwiązania i tak jest około-kwadratowa.
0
w drugiej tablicy są inne liczby niż w pierwszej.
0
http://4programmers.net/Forum/C_i_C++/257860-porownanie_kazdego_elementu_tablicy_z_inna
Masz tu kilka rozwiązań. Rozwiązanie z ptaszkim akurat jest słabe, bo O(n2).
0
Wybitny Kaczor napisał(a):
w drugiej tablicy są inne liczby niż w pierwszej.
Masz dwa zbiory z liczbami, nazwijmy je A oraz B.
Aktualnie robisz tak, że dla każdej liczby ze zbioru A sprawdzasz, czy nie istnieje w zbiorze B przeszukując dla każdego elementu A cały zbiór B.
Moje podejście zakłada, że A oraz B są posortowane i generalnie nie różni się wiele od Twojego - też dla każdej liczby ze zbioru A sprawdzam czy nie istnieje ona w zbiorze B, lecz dzięki założeniu tego, że są to listy posortowane, nie trzeba sprawdzać każdej liczby od początku do końca zbioru, co przedstawiłem Ci wcześniej (można by wręcz się pokusić o jakiś binary search).
0
Myślę że się da. Pewny jednak będę gdy pokażesz przykłady tych "stringo-liczb" :-) Teraz nie wiadomo czy np. zawierają znaki (+/-), czy jest coś po przecinku (albo kropce), czy są zera wiodące itp..
Przykład proszę...
0
nie ma przecinków, liczby są same dodatnie.
0
Jeśli najpierw posortuje dwie tablice to wyjdzie jedna pętla for? Za bardzo nie rozumiem jak to zrobić z tym sortowaniem.
0
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// Obowiązuje dla ASCII...
// Grr... wyraźnie prosiłem o przykład danych... :-/
// Zakładam że:
// - obydwa stringi mają tyle samo znaków,
// - nie ma niespodzianek w postaci zer wiodących
// - nie ma znaków (+/-)
int compare_str_numbers(const string& str1, const string& str2) {
auto iterator_pair = mismatch(cbegin(str1), cend(str1), cbegin(str2));
if(*iterator_pair.first < *iterator_pair.second) {
return -1;
} else if(*iterator_pair.first > *iterator_pair.second) {
return 1;
}
return 0;
}
int main(void) {
string s1 = "12000000003123121115378874011235571";
string s2 = "12000000003123121115378874011235572";
cout << compare_str_numbers(s1, s2) << endl;
}
0
Tylko ja chciałem to sam napisać, a nie korzystać z bibliotek algorytmu.
0
Jak to z tym sortowaniem? Wtedy jest jedna pętla? Bo jakoś za bardzo nie rozumiem.
0
Nie, z sortowaniem nadal masz dwie pętle, lecz wykonują się one krócej, przez co generalnie algorytm powinien być wydajniejszy na dłuższą metę.