sortowanie napisow trwa zbyt dlugo

Witam serdecznie.
Mój problem wyglada tak:
Mam tablice stringów w ktorej zapisane jest około 3 500 nr IP ... a moim zadaniem jest wypisac 10 nr ip które powtarzaja sie najczesciej. Stworzylem funkcje, która to robi ale dziala strasznie wolno. Najpier dane IP sortuje, aby nie byly porozrzucane tylko powtarzaly sie w obrebie swojego IP, nastepnie przypisuje do nowej tablicy tylko IP ktore sie nie powtarzaja a nastepnie sprawdzam ile razy kazde IP sie powtarza w tej pierwotnej tablicy (czyli szukam maximow) , a potem wypisuje 10 najwiekszych... sposob bardzo pokretny i zlozony.. dziala strasznie dlugo...
Zna moze ktos lepsze rozwiazanie?
Nie chodzi mi o gotowy kod, tylko o jakis algorytm..

Olas386 napisał(a)

Witam serdecznie.
przypisuje do nowej tablicy tylko IP ktore sie nie powtarzaja a nastepnie sprawdzam ile razy kazde IP sie powtarza w tej pierwotnej tablicy (czyli szukam maximow)

Nie do końca rozumiem.
Jak już posortujesz IP to wystarczy raz przeszukać posortowaną tablicę aby wyznaczyć 10 najczęściej pojawiających się wyników(w osobnej tablicy trzymasz 10 najlepszych wyników i jak trafisz na jakiś lepszy to aktualizujesz). A jeżeli chcesz jeszcze szybciej to możesz zmienić reprezentacje IP z stringa na long longa.

Rzeczywiście nie ma sensu zapisywac niepowtarzajacych sie IP do nowej tablicy (a bylo to po to, aby sprawdzic ile razy, kazda wartosc IP powtarza sie w tej pierwotnej tablicy, to tak jakbym w jednej tablicy mial wypisane litery alfabetu i sprawdzal ile razy kazda litera powtarza sie w pierwotnej tablicy - potem szukalem najczesciej powtarzajacej sie, wypisywalem ja i zmienialem wartosc na 0 i szukalem nastepnej najwiekszej - - - taki sposob mi przyszedl do glowy)

Ale fakt faktem tablica jest duza (te nr IP z tablicy najpierw przypisywalem z pliku txt, wiec juz w ogole caly proces troche trwa) i calosc troszeczke sie muli ale na mniejszych plikach dziala znacznie szybciej.
Dzieki za pomoc

tak w ogole to najdluzej trwa sortowanie, gdyby dalo sie ten proces jakos przyspieszyc to calosc dzialalaby szybciej

a sortuje w ten sposob

for(int j=0; j<wartosc; j++) //wartosc to wielkosc tablicy w ktorej sa nr IP
{
if(tablica[j]<tablica[j+1])
{
pomocnicza=tablica[j];
tablica[j]=tablica[j+1];
tablica[j+1]=pomocnicza;
}
}
probowalem na rozne sposoby to sortowac, ale tylko ten przynosil odpowiednie rezultaty

Źle sortujesz. Użyj sort() z STL.
Możesz pokazać cały kod to Ci go usprawnię.
A jak zmienisz reprezentację IP ze stringa na long longa to sortowanie też się przyspieszy znacznie.
U mnie na komputerze wczytanie 3500 IP do tablicy stringów zajmuje 0,02 sekundy...

fstream wejscie;
string tablica[100000],nowa[1000000],pomocnicza;
int max=0,t,x=0,wartosc,r=0,ilosc[100000];

wejscie.open(source); //wczytuje moj plik przekazany przez zmienna source
if(wejscie.fail())
{cout<<"Nie znaleziono pliku."<<endl; exit(1);}
else
{
while(getline(wejscie,linie))
{
wejscie>>tablica[x]; //zapisywanie do tablicy pierwszych wyrazow
x++; //kazdej linii (czyli IP)
wartosc=x;
}

for(int i=0; i<wartosc;i++)
{
	for(int j=0; j<wartosc; j++)	//sortowanie
	{
		if(tablica[j]<tablica[j+1])
		{
			pomocnicza=tablica[j];
			tablica[j]=tablica[j+1];
			tablica[j+1]=pomocnicza;
		}
	}
}
	

for(int i=0,j=0; i<wartosc; i++)
	{
	if(tablica[i]==tablica[i+1]) ilosc[j]++;   //zwiekszanie wartosci jezeli sa takie same
	if(tablica[i+1]!=tablica[i]) j=i+1;      
	}
for(int b=0; b<10; b++)
{
	for(int i=0; i<wartosc ; i++)
	{
		if(ilosc[i]>max) {max=ilosc[i]; t=i;}	//znajdowanie najczesciej wywolywanego IP
	}
cout<<tablica[t]<< "                              wystapilo "<< max<< " razy"<<endl;
ilosc[t]=0;
max=0;				//zmniejszanie wartosci max do min i znajdowanie
	}	
		

}wejscie.close();

Zamiast:

        for(int i=0; i<wartosc;i++)
        {
                for(int j=0; j<wartosc; j++)        //sortowanie
                {
                        if(tablica[j]<tablica[j+1])
                        {
                                pomocnicza=tablica[j];
                                tablica[j]=tablica[j+1];
                                tablica[j+1]=pomocnicza;
                        }
                }
        }

Daj:

sort(tablica,tablica+wartosc)

Musisz jeszcze dołączyć:

#include <algorithm>

Nie rozumiem dokładnie wczytywania.
Jeżeli będzie jeszcze za wolno to można zmienić reprezentacje IP. Kompilujesz z optymalizacją?

Dziekuje Ci bardzo!!
Dziala super i znacznie szybciej, wlasciwie od razu jest wynik...
A co do wczytywania pliku , to ta funkcja wypisujaca 10 IP znajduje sie w osobnym pliku .cpp ,char *source to u mnie char *argv , zamiast argv[2] wpisuje source

Program jest pisany pod linuxem i calos polecenia musze wpisywac w jednej linijce. np
./program [-x] <opcje> <nazwa pliku ".log">

w zaleznoci od parametru -x oraz opcji (bo przy parametrze -f mam filtrowanie) moja nazwa pliku albo jest zapisana w argv[2] - gdy nie ma parametro arv[3]- dla wszystkich parametrow oprocz filtrowania badz [atgv4]-dla parametru -f

zreszta to wszystko juz nie wazne, bo program dziala jak nalezy =D jeszcze raz dzieki !