Zlicznie różniących się elementów tablicy
Ostatnio zmodyfikowano 2017-01-25 17:31
vizzars Temat założony przez niniejszego użytkownika |
Zlicznie różniących się elementów tablicy » 2017-01-25 11:54:22 Witam,
Mam do napisania program który liczy ile jest różnych znaków w tablicy i za cholerę nie mogę wpaść na rozwiązanie:
Funkcja: int f1(char napis[]) zwraca w wyniku z ilu różnych znaków składa się napis.
Np.: f1(„Ala ma kota”) =8 (Ala Mkot)
Gdy sprawdzam konkretny element z poprzednimi, nie bardzo to wychodzi.
|
|
mateczek |
» 2017-01-25 13:27:16 #include<iostream>
#include<set>
using namespace std;
int main( void )
{
string napis = "aaaaaa bbbbb";
set < char > litery;
for( char znak: napis )
litery.insert( znak );
cout << litery.size() << endl;
}
lub kasycznie #include<iostream>
using namespace std;
int main( void )
{
string napis = "aaaaaa bbbbbBBBB";
bool tablica[ 255 ] { 0 };
for( char znak: napis )
tablica[ znak ] = true;
int licznikLiter = 0;
for( int i = 0; i < 255; i++ ) {
if( tablica[ i ] ) licznikLiter++;
}
cout << licznikLiter << endl;
}
|
|
mokrowski |
» 2017-01-25 15:40:10 1. Nie lepiej unordered_set zamiast tego set? Tu nie ma wymogu posortowania co robi domyślnie set. 2. Można rozważyć użycie count() z <algorithm> do zliczenia unikalnych znaków. 3. Jeszcze jeden sposób rozwiązania zadania: a) posortowanie liter napisu b) zrobienie na tych posortowanych literach unique() c) zwrócenie wielkości wynikowego kontenera Ten ostatni sposób (3) raczej najwolniejszy ale jeśli potrzebny byłby gdzieś dalej kontener z unikalnymi literami to można go także brać pod uwagę. |
|
pekfos |
» 2017-01-25 16:47:55 | 1. Nie lepiej unordered_set zamiast tego set? Tu nie ma wymogu posortowania co robi domyślnie set. |
Bez przeprowadzenia testów wydajnościowych, nie ma co tego rozważać. A jeśli liczy się wydajność, to żaden z tych dwóch kontenerów nie jest preferowanym rozwiązaniem w tym przypadku. Co rozumiesz przez set "domyślnie sortuje"? Przechowuje dane posortowane, więc jeśli liczysz ten efekt uboczny struktury danych jako sortowanie, to zawsze sortuje, a jeśli nie, to nigdy nie sortuje. 3. Jeszcze jeden sposób rozwiązania zadania:
a) posortowanie liter napisu
b) zrobienie na tych posortowanych literach unique()
c) zwrócenie wielkości wynikowego kontenera
Ten ostatni sposób (3) raczej najwolniejszy ale jeśli potrzebny byłby gdzieś dalej kontener z unikalnymi literami to można go także brać pod uwagę. |
Zgadza się, to jest sposób, ale tylko jako sztuka dla sztuki. Nie ma powodu, by przechowywać wszystkie dane w pamięci, gdy wystarczy przez nie przelecieć. A nawet jeśli dane już są w pamięci, to musisz zrobić kopię, by to posortować. Zupełnie niepraktyczne. |
|
mokrowski |
» 2017-01-25 17:15:46 @pefkos/@pekfos <- wybrać pasujące: Bardzo proszę czytaj ze zrozumieniem. Ja wiem że set sortuje przy każdym wstawieniu a unordered_set nie i TO miałem na myśli (na marginesie można oczywiście zmienić predykat tegoż sortowania) Każdy z kontenerów ma swoje właściwości i zestaw zachowań. @mateczek podał przykłady gdzie zwróciłem uwagę na różnicę set <-> unordered_set i bardzo dobrze że takie rozwiązanie pokazał bez względu na mikro-optymalizacje które można (lub celowe by było) tu realizować. W ostatnim swoim zdaniu także wyraźnie napisałem co sądzę o proponowanym (3) rozwiązaniu i czy/kiedy należy wziąć go pod uwagę. Czyniąc założenie że string z napisem można zmodyfikować, operacja sortowania, wykonania unique i zwrócenia wielkości powstałego kontenera nie wymaga alokowania dodatkowych danych na kopię tegoż kontenera.
Dla mnie EOT bo znów się dowiem że miałem coś innego na myśli :-/
|
|
pekfos |
» 2017-01-25 17:31:58 | @pefkos: Bardzo proszę czytaj ze zrozumieniem. |
:) |
|
| « 1 » |