• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Znalezienie liczby nabliższej do sredniej - możliwa optymalizacja?

VPS Starter Arubacloud
0 głosów
301 wizyt
pytanie zadane 7 lipca 2017 w C i C++ przez marcingrychtol Obywatel (1,490 p.)
edycja 18 lipca 2017 przez marcingrychtol

Cześć!

Napisałem program wskazujący wśród podanych 5 liczb tę, która jest najbliższa średniej z tych liczb. Ogólnie program działa prawidłowo na przypadkach wskazanych w kursie C++, chciałbym jednak się dowiedzieć, czy można go jeszcze jakoś zoptymalizować, lub czy wręcz nie popełniłem gdzieś czegoś bardzo karkołomnego? Pozwolę sobie chyłkiem zaznaczyć, że jestem w połowie kursu konsolowego, przez co proszę o dostosowanie rad w miarę możliwości ;)

Idea działania programu jest taka:

1. Wprowadzam liczby do tablicy za pomocą pętli, od razu robiąc ich sumę, aby później wyliczyć z niej średnią.

2. Do drugiego rzędu tablicy wprowadzam wartości bezwzględne różnicy pomiędzy podaną liczbą, a średnią. Popularnie mówiąc, wpisuję sobie w drugim rzędzie "moduły", aby na ich podstawie poznać która liczba jest najbliżej średniej - ta z najniższym modułem.

3. Ponieważ mogą wystąpić maksymalnie dwie liczby różne od siebie, które są tak samo blisko średniej, do wypisania wyników tworzę tablicę dwukomórkową.

4. Pętlą sprawdzam, która liczba ma najniższy moduł. Jednocześnie przy wystąpieniu takiego samego modułu sprawdzam, czy liczba jest taka sama czy różna - dla różnych liczb zapełniam obie komórki tablicy z wynikami. Tworzę pomocniczą zmienną "int podwojny" na zasadzie wskaźnika true/false, wg którego program wypisze jedną lub dwie liczby.

5. Na koniec daję kilka warunków, które dla dwóch liczb wypiszą je w kolejności od najmniejszej.

Chciałem jeszcze wprowadzić tablicę dynamiczną, ale na razie powiedzmy ze program przewiduje wprowadzenie jedynie 5 liczb :)

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    cout << "podaj 5 liczb" << endl;

    float tablica [5][2], suma=0, srednia;

    for (int i=0; i<5; i++)
    {
        cin>>tablica[i][0];
        suma+=tablica[i][0];
    }

    srednia=suma/5;
    cout<<"srednia wynosi: "<<srednia<<endl;

    float m[2], modul;
    int podwojny=0;

    for (int i=0; i<5; i++)
    {
        tablica[i][1]=abs(tablica[i][0]-srednia);

        if (i==0)
        {
            m[0]=tablica[i][0];
            modul=tablica[i][1];
        }

        else if ((tablica[i][1]==modul)&&(tablica[i][0]!=m[0]))
        {
            m[1]=tablica[i][0];
            podwojny=1;
        }

        else if (tablica[i][1]<modul)
        {
            m[0]=tablica[i][0];
            modul=tablica[i][1];
            podwojny=0;
        }
    }

    cout<<"najblizsza sredniej liczba to: ";
    if ((podwojny==1)&&(m[0]<m[1])) cout<<m[0]<<" i "<<m[1];
    else if ((podwojny==1)&&(m[0]>m[1])) cout<<m[1]<<" i "<<m[0];
    else cout<<m[0];

    cout<<endl;



    return 0;
}

 

2 odpowiedzi

+2 głosów
odpowiedź 20 lipca 2017 przez mokrowski Mędrzec (155,460 p.)

Szczególne optymalizacje dla 5 wartości tak prostego algorytmu nie mają zbytniego sensu. Głównym powodem jest brak precyzyjnej możliwości obserwowania efektów pracy. W każdym uruchomieniu możesz mieć nieco inny sposób pracy systemu operacyjnego co wpłynie na wykonane pomiary. Lepiej zrobić to dla większej ilości próbek.

W skrajne przypadki tego algorytmu to:

  1. Znalezienie 1 liczby zbliżonej do średniej.
  2. Znalezienie wszystkich liczb zbliżonych do średniej.

Ten drugi przypadek zajdzie w przypadku wpisania do kontenera identycznych wartości.

Optymalizacja algorytmu może przebiegać w kilku a nie 1 wymiarze. To bardzo zależy od projektu ale te wymiary to np.

  • Szybkość wykonania lub szybkość dostarczenia pierwszych (nawet cząstkowych) wyników
  • Zajętość pamięci
  • Intensywność wykorzystania urządzeń I/O
  • Wymagana dokładność wyników
  • Skalowalność danego algorytmu
  • Wykorzystanie zasobów sprzętowych
  • ...

Chciałeś mieć inspirację do własnych poszukiwań więc radzę zacząć zapoznania się z algorytmem accumulate(...) który tu użyty, wykona większość prac. Później wrzucę proponowane rozwiązanie. Urlop rządzi się swoimi prawami :-)

0 głosów
odpowiedź 18 lipca 2017 przez d0n Mądrala (6,440 p.)
Praktycznie ciężko mówić o optymalizacji takiego problemu, ponieważ dla każdego elementu w tablicy wykonywana jest jedna operacja (wczytanie) i jedna operacja(porównanie). O takich programach mówi się, że działają liniowo i np. w tym wypadku da się udowodnić, że szybciej się nie da.
Jeżeli przerobić mocno problem - powiedzmy że dostajemy posortowana(!) tablice liczb, a potem ich średnią, to można wtedy użyć wyszukiwania binarnego, ale i tak wczytywanie danych było by liniowe, więc wszelkie optymalizacje na współczesnym sprzęcie dały by minimalną różnicę.
W skrócie: Nie da się szybciej, ponieważ każdy element trzeba "obejrzeć" i nawet jakby było ich milion program wykonał by się w dziesiętnych częściach sekundy

Tyle jeśli chodzi o opisany przez Ciebie sposób, kod jest usunięty, więc się nie wypowiem ;/
komentarz 18 lipca 2017 przez marcingrychtol Obywatel (1,490 p.)
wkleiłem kod z powrotem
komentarz 18 lipca 2017 przez bartolinciu Dyskutant (7,580 p.)
Możnaby też odrobinę to zoptymalizować zagłębiając się bardziej w szczegóły działania programu na poziomie procesora. Ale wtedy byłaby to oszczędność pewnie rzędu kilkunastu, kilkudziesięciu cykli
komentarz 19 lipca 2017 przez marcingrychtol Obywatel (1,490 p.)
Jakieś wskazówki? Już nawet nie chodzi o to, czy będę to poprawiać, ale zawsze jakieś słowa kluczowe naprowadzą mnie na ciekawy temat do rozważenia :)
komentarz 19 lipca 2017 przez bartolinciu Dyskutant (7,580 p.)
Generalnie jak chcesz bawić się w optymalizację, to przede wszystkim musisz tworzyć kod tak, aby dawać komputerowi jak najmniej zadań do wykonania. Fakt, dzisiejsze kompilatory wykonują wiele pracy za ciebie, ale niektóre rzeczy musisz zrobić sam. Na przykład dobre umiejscowienie instrukcji warunkowych czy sprawdzania błędów, albo dobra kolejność warunków w if'ie.
komentarz 20 lipca 2017 przez d0n Mądrala (6,440 p.)
W kompilatorach często znajduje się opcja optymalizacji kodu na niskim poziomie (w gcc i MinGw jest to flaga -O2 i flaga -O3, z czego -O2 jest w 100% bezpieczna, a -O3 może czynić program wadliwym lub "nieprzenośnym" na inny komputer). W wielu przypadkach te flagi przyspieszaja wykonanie programu, natomiast tutaj mowimy o 5 liczbach, więc... sensowne przyspieszenie prawdopodobnie nie istnieje

Podobne pytania

0 głosów
2 odpowiedzi 1,154 wizyt
pytanie zadane 24 stycznia 2018 w C i C++ przez Furgix Początkujący (480 p.)
0 głosów
4 odpowiedzi 219 wizyt
pytanie zadane 22 lipca 2015 w C i C++ przez heartagram Obywatel (1,770 p.)
0 głosów
1 odpowiedź 1,008 wizyt
pytanie zadane 2 maja 2018 w C i C++ przez XSPACE Użytkownik (690 p.)

92,455 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...