Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Pomoc w optymalizacji własnego rozwiązania

Ostatnio zmodyfikowano 2015-12-11 13:39
Autor Wiadomość
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

Treść zadania
Treść zadania

Kod (po poprawkach):
C/C++
#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;
    }
}
P-141599
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 ??
C/C++
#include <iostream>
#include<vector>
using namespace std;

int main()
{
    vector < int > c = { 21, 23, 32, 4353, 54, 5454, 4545, 76575, 87686, 43, 4343, 43 }; //jakiś ciąg liczb naturalnych
    vector < int >::iterator poss = c.begin() + 4; // pos na 4 element
    c.erase( poss ); // usunięcie 4 elementu
    poss += 3; //teraz wskaźnik na 8 element - dla przykładu
    for( int i: c ) cout << i << " "; cout << endl; // wyświetlenie wektora - element 54 został usunięty !!!
}
P-141601
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".
P-141604
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 :) 
P-141607
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...
P-141677
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

P-141702
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?
P-141707
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ć?
P-141736
« 1 » 2
  Strona 1 z 2 Następna strona