Jak NAJSZYBCIEJ pobrać dane z pliku?

0

Witam. Biorę pierwszy raz udział w olimpiadzie informatycznej. Jestem w trakcie rozwiązywania jednego z zadań. I wszystko ładnie pięknie wychodzi:) wyniki prawidłowe zarówna dla małych jak i dużych danych.

Program podczas testowania jest uruchamiany na zasadzie:
program.exe <dane.in >dane.out w konsoli

Dla małych danych program wykonuje się w 0.000s dla większych danych (mówie tu o łańcuchach znaków o długości do 1 000 000) już tak kolorowo nie jest:( wyniki ok ale czas duży;( dla naprawde wielkich danych dochodzi do 20s ;( gdzie limit wynosi 5s...

Do wczytywania używam zwykłego cin.. a dane zapisuje po prostu w tablicy charów..

No więc moje pytanie brzmi: Czy istnieje jakiś szybszy sposób na wczytanie danych?

0

Wywal cin i użyj scanf oraz fgets. A i tak najważniejsze jest algo.

0

Wyłącz synchronizację:
http://www.cplusplus.com/reference/iostream/ios_base/sync_with_stdio/

Ewentualnie możesz używać printf i scanf. GCC optymalizuje printfy i scanfy, tzn jeżeli masz np printf("%d\n", liczba); to GCC zamienia to wprost na kod, który wypisuje to co ma wypisywać, tak że ciąg "%d\n" jest w kodzie wynikowym niewykorzystywany.

0

Zdecydowanie tak, fread ze stdin do buforów o odpowiedniej wielkości (parę kb zwykle jest ok). Cin jest wygodny, szczególnie przy przeładowaniu operatorów dla własnych klas, ale szybkością to nie grzeszy, szczególnie bez optymalizacji (pamiętaj także, że cały STL jest przygotowany pod kompilację z włączoną optymalizacją). Chwilowo może pomóc wyłączenie synchronizacji ze stdio.

0

Jak użyc funkcji fread w moim przykładzie?

Sory za post pod postem ale nie wiem czemu mi to nie działa:

 unsigned int n;
    scanf("%u",&n);

    char name1[n+1],name2[n+1];
    fgets(name1,n,stdin);
    fgets(name2,n,stdin);

;(

0

Co znaczy "nie działa"? Spróbuj w fgets dać n+1
To też jest dyskusyjne(chociaż przy gcc zadziała):

char name1[n+1],name2[n+1];

No i nie licz na to, że zmiana sposobu wczytywania, aż tak skróci czas. Problem nie jest po stronie wczytywania, a algorytmu.

0

dodanie "n+1" nie pomaga;( chodzi to to ze uruchamiam program, in czeka na podane danych- funkcja scanf no i klikne np 3 i enter nastepnie znowu czeka na podanie danych 11 funkcja fgets podam jakis tam ciag a 2 funkcja fgets tak jakby sie nie wywoływała.

0

powiedz coś więcej o "dane.in", co tam siedzi? liczba i dwa być może nawet bardzo długie dwa wiersze ?

0

plik ma taka strukturę :

5
ABCDE
EDCBA

oczywiście o długości łańcuchów świadczy liczba i może ona wynosi max 1 000 000..

0

Wziąłeś pod uwagę to, że scanf nie pobiera '\n', więc pierwszy fgets bierze samo '\n'?

0

Nie wziĄłem, gdyż nigdy nie używałem tych funkcji... czy wrzucenie getchar() po scanfie pomoże? czy lepiej zrobi to inaczej?

0

czyli jedno scanf() i jedno fread() które czyta minimum 2*n+4 bajtów.

0

1 fread? ale jak wywołac ta funkcje żeby pierwszy napis wczytala do name1 a drugi do name2?
fread(name1,sizeof(char),2*n+4,stdin)???

0
    char name1[2000005];
    scanf("%d\n",&n); 
    fread(name1,1,2*n+5,stdin);
    char * name2; 
    name2= &name1[n]+1; // lub + 2 w windows, sprawdź
    name1[n]=name2[n]=0; 
0

Okej dzieki za pomoc:) lecz zrobiłem troszke inaczej i też jest okej ;D

unsigned int n;
    scanf("%u\n",&n);

    char name1[n+1],name2[n+1];
    fread(name1,1,n+1,stdin);
    fread(name2,1,n+1,stdin);
name1[n]=name2[n]='\0';

zabrakło "\n" w scanfie i temu pewnie 1 fread/fgets pobieral znak nowej lini..

0

Nie chce zakłada nowego tematu więc zadam pytanko jeszcze w tym;D a więc czy istnieje jakaś funkcja która sortuje elementy tablicy wzgledem innej tablicy?;D chodiz o to ze mamy 2 tablice, pierwszą: {4,9,7,8} a drugą {9,8,7,4} i czy instnieje taka funkcja ktora posortuje mi druga tablice dokladnie tak jak wyglada to w pierwszej?

Napisałem własną funkcje na to ale chcialbym porownac moj czas do tej funkcji zeby zobaczyc o ile jest ona szybsza od mojej ;d

0

Takiej funkcji na 99,9 % nie ma. Natomiast możesz zrobić tak (żeby sprawdzić, czy wszystkie cyfry występują z taką samą częstością):

int tempA[10]; // od 0..9, przechowuje ilosc wystapien cyfr 0..9 w tablicyA
dla każdej cyfry z tablicyA rób:
  tempA[tablicaA[i]]++;
int tempB[10]; // od 0..9, przechowuje ilosc wystapien cyfr 0..9 w tablicyB
dla każdej cyfry z tablicyB rób:
  tempB[tablicaB[i]]++;

if (zawartosc tempA i tempB sa rowne) {
  tablicaB = tablicaA; // albo kopiowanie zawartosci z A do B, zaleznie od potrzeby
}
0

Hmm skoro tak nie istnieje może ktoś zna jakiś sensowny algorytm na takie coś ;D

0

Ale o co dokładnie chodzi? Po co sortować, skoro można skopiować zawartość pierwszej tablicy do drugiej tablicy?

0
mto9 napisał(a)

Hmm skoro tak nie istnieje może ktoś zna jakiś sensowny algorytm na takie coś ;D

Masz sam to wymyślić, a poza tym nie masz tego sortować tylko policzyć najmniejszą ilość zamian bąbla jaka jest potrzebna do uzyskania z ciągu A ciągu B.

0

hmm wytłumaczę to na przykładzie:
przykładowo na wejscie wyglada:
ABCA
AACB
to wyjscie wyglada 3..

nalezy posortowaz napis 2 tak zeby wygladal jak napis 1 i wykonac jak najmniej ruchow, gdzie ruch to zamiana miedzy sąsiednimi elementami:
dla przykładu powyżej wyglada to tak:
ABCA-START
ABAC-1 RUCH
AABC-2 RUCHY
AACB- 3 RUCHY

moj algorytm jest okej daje prawidlowe wyniki ale tak jak mowilem przy duzych danych wykonnuje sie za wolno;( moze ktos ma jakis pomysl ;d ale chociaz zeby mnie jakos naprowadzil ;d

1

No i mamy ci robić zadanie z etapu olimpiady, który jeszcze trwa? Chyba się z fiu*em na głowy zamieniłeś.

0

moze ktos ma jakis pomysl ;d ale chociaz zeby mnie jakos naprowadzil ;d != No i mamy ci robić zadanie

0

Rzecz która cie zdecydowanie naprowadzi - http://pl.wikipedia.org/wiki/Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa (lepiej by było http://en.wikipedia.org/wiki/Computational_complexity_theory ale wątpię żeby czytanie Ci łatwo przyszło) - to znaczy wyjaśni Ci czemu twój algorytm działa za wolno.

Twój algorytm ma prawdopodobnie Θ(n2) jeśli nie Θ(n3) co dla dużych wartości nie ma szansy działać szybko.

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