Sortowanie C++


(Sui64) #1

Witam...

Mam do napisania większy program który robi różne dziwne rzeczy z dużym ( kilkaset MB) plikiem tekstowym. Między innymi ma on sortować zawarty w nim tekst; mój problem polega na tym że to mnie przerosło... ma to działać dość szybko a wyniki zapisywać do innego pliku. I tutaj moja prośba mógłby mi ktoś napisać chociaż funkcję która otworzy ten plik i posortuje go alfabetycznie? będę bardzo wdzięczny za kawałek kodu bo teoretycznie wszystko wiem jak zrobić ale jak zaczynam pisać to zaczynają się schody... pozdrawiam :wink:


(Krakers87) #2

Jesteś niepoważny. Nawet nie wiadomo co w tym pliku jest.


(Sui64) #3

w pliku jest np książka "Pan Tadeusz" nie mówię że to na pewno ona chodzi po prostu o duży plik tekstowy...


(Bartoszlenar) #4

posortuje co?

slowa? wiersze? znaki?

jak juz prosisz o pomoc to sprecyzuj o co ci chodzi.


(Sui64) #5

program ma posortować tekst (słowa) zgodnie z alfabetem (polskim)... ma to działać w miarę szybko a wynik ma być zapisany w nowym pliku... wszystko jedno czy to użytkownik wprowadzi nazwę pliku źródłowego i docelowego czy będą one nadane od górnie nie ma to znaczenia.. nie wiem co jeszcze mogłem pominąć...


(Jedras121) #6

Moim skromnym zdaniem nikt przy zdrowych zmysłach by nie kazał sortować pliku tekstowego o rozmiarze kilku lub więcej MB. Nawet najszybszy algorytm będzie to robił bardzo wolno.


(Pawel Wys) #7
#include 

#include 

#include 

using namespace std;

int main(){

   vectorV;

   int n;

   cout<<"Podaj liczbę słów"<
   cin>>n;

   string>>a;

   for (int i=1;i<=n;i++){

        cin>>a;

        V.push_back(a);

   }

   sort(V.begin(),V.end());

   for (int i=0; i
        cout<
   }

  cout<
  return 0;

}

Program działa, ale nie wczytuje danych z plików:P

Wystarczy że zastąpisz wczytywanie z konsoli wczytywaniem z plików

poczytaj o klasie do wczytywania z plików na stronie http://www.cplusplus.com/reference/iostream/fstream/

W sumie kilkuset megabajtowy plik powinien posortować w kilkanaście minut - kilkadziesiąt minut, ale szybciej się raczej nie da.

P.S.: Nie wiem czy program zadziała (mogą być literówki).


(Sui64) #8

no zgadzam się z Tobą... jednak znalazł się ktoś kto wpadł na genialny pomysł posortowania książki...;/ nie wiem tylko po co... oprócz tego program ma też policzyć wszystkie słowa i wyodrębnić wskazane ... z tym sobie poradziłem ale sortowanie mnie przerosło...


([alex]) #9

sailor1989 , nie podałeś dużo rzeczy:

  • [*:1fqsfqbb]Czym oddzielone są te słowa?[*:1fqsfqbb]Czy w pliku wynikowym mają pojawić się również duplikaty?[*:1fqsfqbb]Czy ma to być case-sensitive czy nie?

Dla małych plików najprościej wstawiając kolejne wczytane słowa do vector tak aby wektor był posortowany, potem całość zapisujesz.

Dla średnich plików lepiej zamiast vector'a użyć RB_tree.

Dla dużych (nie mieszczących się w pamięci) najlepiej użyć merge sort używając plików tymczasowych.


(Sui64) #10

oo dzięki bardzo może cos z tego urodzę... a moze ktoś jeszcze ma jakiś pomysł na ten problem?

-- Dodane 04.11.2009 (Śr) 20:09 --

alex co do oddzieleń słów są to przecinki kropki średniki no i białe znaki ogólnie wszystkie możliwości... w pliku docelowym dobrze by było jakby się pojawiły tez duplikaty co do c-s moim zdaniem nie ma to większego znaczenia bo to jest sortowanie alfabetyczne...

NIe rozumiem tylko o co Ci chodzi z tymi plikami tymczasowymi nigdy się z tym nie spotkałem...


([alex]) #11

Wpisz w google "merge sort", google nie gryzie.


(Sui64) #12

może i nie gryzie ale też nie tłumaczy w jasne dla mnie sposób... nie mam zielonego pojęcia jak mogć to zastosować w moim programie...;/


([alex]) #13
  1. Wczytujesz po dwa słowa, sortujesz je i zapisujesz do pliku A1, następne dwa posortowane słowa do pliku B1, następne znowu do A1

  2. Wczytujesz po jednym słowie z plików A1 i B1 mniejsze z nich dopisujesz do pliku A2 i doczytujesz z odpowiedniego pliku z tym że doczytać z tego samego pliku można tylko raz (z tymi wczytanymi na początku 2), w sumie do A2 poleci 4 słowa, potem to samo dla B2. Po zakończeniu pliki A1,B1 nie potrzebne - do skasowania

  3. dokładnie to samo co poprzednio tylko że doczytać z pliku można 3 razy (z tymi wczytanymi na początku 4), do plików A3 i B3 poleci po 8 słów. Pliki A2,B2 - do skasowania.

  4. wczytujesz max 8, poleci po 16 do A4+B4, kasujemy A3+B3

  5. wczytujesz max 16, poleci po 32 do A5+B5, kasujemy A4+B4

no itd dopóki nie okaże się że wszystko jest w pliku AN (który już będzie posortowany).

Jeżeli mądrze zarządzać plikami to potrzebujesz tylko 4 dodatkowe pliki (jak nie są potrzebne to kasujesz).

W ten sposób możesz posortować pliki o dowolnym rozmiarze (nawet kilkadziesiąt TERA bajtów, byle by na dysku starczyło miejsca), dostęp tylko sekwencyjny.


(Sui64) #14

dzięki za pomoc.... ale chyba jednak będę szukał trochę łatwiejszej metody bo z tą do końca życia nie dam rady..;/ ale dzięki serdeczne :wink:


([alex]) #15

To nie jest takie trudne na jakie wygląda, wystarczy trochę się zastanowić.


(Sempai) #16

Tak sobie właśnie myślałem na tym i właściwie, gdyby wywalić wszystkie niepotrzebne znaki: '.', ":", ";", itp. to słowa rozdzielony były by spacjami. Wtedy trzeba by otworzyć plik i zamieniać kolejno każdą linijkę na tablice (dzieląc ją po każdej spacji). W PHP to jest rewelacyjnie proste (funkcja explode). Kiedyś napisałem coś takiego w C, ale nie mogę znaleźć plików. Jeśli założyć, że odczytujesz po jednej linijce z pliku, sortujesz wyrazy i gdzieś zapisujesz wynik (byle nie w RAMie) to spoko, takie coś zadziała. Po przejściu pętli dostaniesz posortowane słowa w każdej linijce. Jeśli za to chcesz sortować cały plik, to tablica może mieć więcej niż 65535 elementów co może doprowadzić do problemów (nie pamiętam jakie jest max elementów w tablicy, ale chyba właśnie 65535 lub mniej). Chyba, że będziesz sortować po 2 linijki max (wtedy to ma sens). Kiedyś sortowałem znaki w pliku i to jest naprawdę proste i działa nawet dla większych plików, ale sortowanie słów... Zresztą po jaką chol... to komu? Rozumiem robienie statystyki ile razy dane słowo występuje w pliku, to zadanie jest lekko chore.

Zresztą plik "kilkaset mega"? "Pan Tadeusz" zajmie max kilka megabajtów...

Chyba że by posortować wszystkie słowa które występują w pliku, ale bez powróżeń. Wtedy trzeba napisać funkcję wyodrębniającą unikatowe słowa (bez powtórzeń). Czyli jak masz: "Ala głaska swojego kota po brzuchu. Kot lubił jak się go głaska po brzuchu."

to unikatowe słowa to: Ala, głaska, swojego, kota, po, brzuchu, lubił, jak, się, go

I tak wyodrębnione słowa można później posortować za pomocą Quicksort lub innej optymalnej metody.


(Sui64) #17

no ok dzięki za te wskazówki jednak bardziej by mi sie przydał kawałek kodu który sotruje... co do "Pana Tadeusza" to masz rację nie jest on zbyt duży ale program ma sortować duże pliki... nie mogę sobie z tym poradzić po prostu...;/