Emhyr Temat założony przez niniejszego użytkownika |
Pomoc w optymalizacji własnego rozwiązania » 2015-12-07 23:40:12 Cześć, Mam do zrealizowana zadanie, którego treść wkleiłem poniżej w postaci obrazka. Jeszcze niżej znajduje się kod programu który napisałem. Kod działa (dla poprawnych danych wejściowych daje odpowiednie rezultaty), wydaje mi się też, że nie jest najgorszy, ale nie jest niestety wystarczająco optymalny. Zrealizowany jest w oparciu o "zapętloną" listę jednokierunkową. Pomóżcie i powiedzcie, co mógłbym zmienić, aby ten program wykonywał się szybciej? Edit: c - liczba w ciągu na którą wskazuje POS Kod (po poprawkach): #include <stdio.h> #include <stdlib.h>
typedef struct n { int value; struct n * next; } node;
typedef struct { node * begin; node * end; node * pos; int size; } list;
list * addToList( list * l, int i );
void processList( list * l, int numberOfOperations );
void printList( list * l );
void movePOSRight( list * l, int i );
void makeOperR( list * l );
void makeOperX( list * l );
int main( int argc, char ** argv ) { int numberOfOperations = 0; int x = 0; list * l = malloc( sizeof( * l ) ); l->size = 0; l->begin = l->end = l->pos = NULL; if( scanf( "%d", & x ) == 1 ) { numberOfOperations = x; while( scanf( "%d", & x ) == 1 ) { l = addToList( l, x ); } if( l->size != 0 ) { processList( l, numberOfOperations ); } } printList( l ); return 0; }
list * addToList( list * l, int i ) { if( l->begin == NULL ) { l->begin = malloc( sizeof( l->begin ) ); l->begin->value = i; l->pos = l->end = l->begin->next = l->begin; } else { l->end->next = malloc( sizeof( l->end->next ) ); l->end->next->value = i; l->end->next->next = l->begin; l->end = l->end->next; } l->size++; return l; }
void processList( list * l, int numberOfOperations ) { while( numberOfOperations-- ) { if( l->pos->value % 2 == 0 ) { makeOperR( l ); } else { makeOperX( l ); } } }
void printList( list * l ) { int i; node * n; if( l == NULL || l->size == 0 ) { printf( "-1" ); return; } n = l->pos; printf( "%d", n->value ); n = n->next; for( i = 1; i < l->size; i++ ) { printf( " %d", n->value ); n = n->next; } }
void makeOperX( list * l ) { node * tmp = l->pos->next; l->pos->next = malloc( sizeof( l->pos->next ) ); l->pos->next->next = tmp; l->pos->next->value = l->pos->value - 1; l->size++; movePOSRight( l, l->pos->value ); }
void makeOperR( list * l ) { int i = l->pos->next->value; l->pos->next = l->pos->next->next; l->size--; movePOSRight( l, i ); }
void movePOSRight( list * l, int i ) { i = i % l->size; while( i-- ) { l->pos = l->pos->next; } }
|
|
mateczek |
» 2015-12-08 00:24:59 czyli mamy ciąg liczb naturalnych np 21,23,32,4353,54,5454,4545,76575,87686 i chcesz usunąć czwarty element?? pos=4 czyli element o watości (54) co dalej z tym wskaźnikiem ?? Ja nie rozumie pojęcia o c elementów w prawo ?? #include <iostream> #include<vector> using namespace std;
int main() { vector < int > c = { 21, 23, 32, 4353, 54, 5454, 4545, 76575, 87686, 43, 4343, 43 }; vector < int >::iterator poss = c.begin() + 4; c.erase( poss ); poss += 3; for( int i: c ) cout << i << " "; cout << endl; }
|
|
Emhyr Temat założony przez niniejszego użytkownika |
» 2015-12-08 00:55:29 @mateczek Jeśli obecne POS to 4, czyli tutaj wartość 54, to przy operacji R kasujemy element 5, czyli 5454 i przesuwamy POS o 54 miejsca, czyli o tyle jaka jest liczba na pozycji POS. Jeśli ta liczba jest większa niż długość ciągu to "zapętlamy". |
|
darko202 |
» 2015-12-08 13:18:47 1. > nie jest niestety wystarczająco optymalny jeśli znasz ilość przesunąć to zastosował bym for a nie while np. while( t-- ) { // zbędne badanie warunku i odejmowanie pos = pos->next; lub while( operNum-- )
2. wydaje mi się że w i zapamiętujesz liczbę np. 5 odejmując nie przenosisz informacji o przechowywanej liczbie (zmieniasz ją) pos->next->i = pos->i - 1; // teraz będzie 4
to jest chyba błąd
3. masz metodę addToList to nie twórz kolejnej tej samej funkcjonalności makeOperX() { ... pos->next = malloc( sizeOfStruct );
4. w programie nie widzę obsługi wejścia (założenie )
5. używasz zmiennych globalnych to zła praktyka, gdyż prowadzi do trudnych do ustalenia błędów programu void addToList( int i ) { ... n->next = k; // k brana z skądś -
6. do obsługi tego problemu lista (zapętlona) nie jest zła ale radziłbym Ci stworzyć dobrą klasę z tego co masz i dopiero potem z niej korzystać w main
Powodzenia :) |
|
Emhyr Temat założony przez niniejszego użytkownika |
» 2015-12-09 20:00:37 @darko202
1.pętla for będzie szybsza niż while? też musiałbym inkrementować/dekrementować, żeby liczyła ile razy ma przesunąć
2.Tu jest ok. Ustawiam jako następnik pos'a pos->i-1 a sam pos->i zostawiam bez zmian
3.moja metoda addToList służy do dodawania na koneic listy przy wczytywaniu danych, potem k, czyli koniec, wskazuje na poczatek i lista jest już zapetlona natomiast w makeOperX() tzreba wstawić element pomiędzy
4. jest w mainie scanfem
5. pomyślałem, że użycie zmiennych globalnych poprawi szybkość działanie programu, bo nie będzie przekazywania parametrów
6. program powinien być w czystym C, a najlepiej C89 :/
Każda milisekunda się liczy... |
|
darko202 |
» 2015-12-10 08:51:27 od 2. sugerowałem się chyba pierwszeństwem operatorów opisanym np. na https://msdn.microsoft.com/pl-pl/library/126fe14k.aspx-> grupa 2 - grupa 6 pos->i-1 w świetle tego pierwszeństwa moim zdaniem wykonuje się inaczej niż piszesz. od 5. przekazuj do funkcji zmienne przez wskaźnik i zapomnij o używaniu zmiennych globalnych (uznaj to za dobrą praktykę) funkcja/procedura powinna być autonomiczną częścią (mini programem) w tej chwili w funkcjach nie wiadomo co faktycznie jest robione 7. > Każda milisekunda się liczy... poszukałbym jeszcze w takich miejscach * i += 1 jest szybsze niż i = i + 1 co z %= ? t = t % size; * podobnie chyba movePOSRight( pos->next->i ); od t = pos->next->i; //zbędne tworzenie zmiennej movePOSRight( t ); * const sizeOfStruct = = sizeof( node ); pos->next = malloc( sizeOfStruct ); od sizeOfStruct = sizeof( node ); pos->next = malloc( sizeOfStruct ); * funkcje inline od zwykłych funkcji 8. rezerwujesz pamięć ale jej nie zwalniasz |
|
Monika90 |
» 2015-12-10 11:32:42 Nazwa te zmiennej sizeOfStruct nie odpowiada rzeczywistości, a program ma niezdefiniowane zachowanie. Zresztą, dlaczego ta zmienna w ogóle istnieje? |
|
Emhyr Temat założony przez niniejszego użytkownika |
» 2015-12-10 21:55:08 @Monika90 Rzeczywiście głupio zrobione, zmienna skasowana. Dzięki!
@darko202 2. W świetle tego pierwszeństwa pobierana jest wartość pos->i i następnie od niej odejmowana jest wartość 1. Wszystko jest więc w porządku. Nie chcę modyfikować pos->i. Potrzebna mi wartość pos->i zmniejszona o 1 dalej.
5. Wiem, wstydzę się, że to było tak napisane ;) Teraz poprawiłem.
7. Poprawiłem trochę. > funkcje inline od zwykłych funkcji Inline'y będą działać szybciej?
8. Wiem, że powinienem zwalniać pamięć w makeOperR(), bo kasuję tam element z listy, ale zwalnianie pamięci wydłuży mi czas działania programu.
Dzięki za kolejne uwagi ;)
Wrzuciłem poprawiony kod, szybkość wykonywania w zasadzie bez zmian. Co jeszcze mógłbym poprawić? |
|
« 1 » 2 |