Miejsca zerowe funkcji kwadratowej


(Julek94) #1

Witam.

Mam do napisania krótki program w konsoli obliczający miejsca zerowe funkcji kwadratowej (ax^2 + bx + c). Od razu piszę, że nie mam z tym żadnego problemu, chcę się tylko zapytać o jedną rzecz, a mianowicie, który z pomysłów jest bardziej wydajny.

Wpadłem na pomysł, że po pobraniu parametrów a, b i c od użytkownika zamiast liczyć od razu deltę, to mogę sprawdzić parametr b:

Jeśli b == 0, to sprawdzamy a i c, jeśli mają takie same znaki, to delta ujemna i bez żadnych obliczeń wypisujemy, że brak rozwiązań, jeśli któreś z nich to zero, to delta jest zero i liczymy jedno miejsce zerowe, a jeśli zaś mają różne znaki, to delta dodatnia i liczymy oba miejsca zerowe.

Jeśli b != 0 -> to już wtedy liczymy deltę, sprawdzamy czy nie jest mniejsza od zera, jeśli tak, to brak rozwiązań, jeśli 0, to obliczamy jedno miejsce zerowe, jeśli większa od zera, to liczymy 2 miejsca zerowe.

Ten sposób jest dłuższy, ale obliczenia wykonujemy tylko wtedy, kiedy są potrzebne, jeśli funkcja nie ma miejsc zerowych, to nie robimy żadnych działań, co na chłopski rozum wydaje mi się bardziej wydajne.

Można też się nie bawić i od razu policzyć deltę, sprawdzić jej znak i obliczyć jedno lub dwa miejsca zerowe, bądź wypisać, że brak miejsc zerowych, jednak w tym przypadku, za każdym razem wykonujemy co najmniej jedno obliczenie.

Wiem, że w takim małym programie nie będzie to miało znaczenia, ale chcę się nauczyć pisać możliwie jak najbardziej WYDAJNE, a co za tym idzie - możliwie jak najszybsze w działaniu aplikacje poczynając od właśnie takich małych, najprostrzych programów.

Tak więc pytanie brzmi: który ze sposobów jest bardziej wydajny/szybszy?

Wiem, że niechętnie pomagacie ludziom, którzy najbardziej to by chcieli, żebyście całą aplikację napisali za nich, bo oni ,,nie rozumieją", ale ja zadaję pytanie czysto teoretyczne, bo od strony kodowej problemów nie będzie :slight_smile:

Z góry dzięki za odpowiedzi

Pozdrawiam.


(Zulowski) #2

Bardzo ciężko powiedzieć co będzie wydajniejsze, bo ... kompilator podczas swojej pracy zrobi swoje, i zoptymalizuje kod, sam osobiście pisał bym z tym warunkiem if.


(Julek94) #3

Dzięki za odpowiedź, ale temat do dyskusji wciąż pozostaje otwarty. Ponieważ Zulowskiemu trudno powiedzieć, to może ktoś będzie miał odmienne zdanie i będzie bardziej pewien :slight_smile:


(Tomek Matz) #4

@Disin

Twoim zadaniem jako programisty jest wymyślanie takich algorytmów, które są wydajne. Jednak w przypadku tego programu nie ma potrzeby kombinowania. Wyliczanie miejsc zerowych funkcji kwadratowej nie jest złożoną operacją. Jeśli chcesz coś w tym programie optymalizować to co najwyżej ilość linijek kodu, nic więcej :slight_smile: Sprawdzaj tylko, czy a jest różne od 0, bo jeśli nie jest to masz do czynienia z funkcją liniową. Jeśli jest, to od razu licz deltę.


(Julek94) #5

Niby racja, choć mówię, żeby w przyszłości pisać złożone, wydajne algorytmy/programy, to muszę pojąć w jaki sposób napisać coś wydajnego, bo potem przy większych projektach dajmy na to - owszem napiszę, ale będzie to powolne, niby działa, ale będzie się dało napisać dużo wydajniej. Dlatego chciałem zobaczyć już od najmniejszego programu jaka metoda jest szybsza - czy trochę dłuższa, ale nie wykonująca obliczeń za każdym razem, czy krótsza, ale za to wykonująca obliczenia za każdym razem


(Tomek Matz) #6

Jeśli chcesz potestować wydajność swoich algorytmów, to możesz sobie porozwiązywać zadania ze spoj-a http://pl.spoj.pl/problems/latwe/. Każde zadanie ma ograniczony czas w jakim ma zostać znalezione rozwiązanie.

PS Poprawiłem babola w poprzednim komentarzu :slight_smile:


(Julek94) #7

dzięki, przyda się :slight_smile:


(Zulowski) #8

Chodzi też o to, że w takim czymś to ciężko co kolwiek zoptymalizować, weź pod uwagę np sortowania tablic, masz tablice 1000 elementów, i tu już jest znaczenie czy będziesz to sortować bombelkowo czy quicksortem :slight_smile:

Tu już będzie miało znaczenie to, co sam napiszesz.

Jako programista masz pisać kod, który nie będzie niepotrzebnie robił zbędnych rzeczy (dlatego lepiej z tym warunkiem), a do tego, musisz starać się przewidzieć wszystkie możlwości działania programu, resztę zostawia się kompilatorom i optymalizacji przez nie dokonywanych.

Jeżeli "na prawdę" potrzebujesz super wydajnych programów -> asembler.

Dodatkowo chodziło mi, że ciężko powiedzieć co będzie szybciej, bo to zależy TYLKO i wyłącznie od tego, jakie dane będziesz wprowadzał, jeżeli masz 100 przykładowych funkcji, w których nigdy nie ma b=0; to druga będzie w tedy ... szybsza, a jak będziesz miał ileś tam tych danych z b=0; to już się okazuje, że lepsza jest pierwsza wersja.

Idz na informatykę na studia, w początkowych latach są prowadzone przedmioty typu "algorytmy i struktury danych", tam się pouczysz o złożonościach obliczeniowych, i tak Ci to zbrzydnie, że już nigdy nie będziesz się zastanawiał "wstawić tego ifa czy nie, jak będzie szybciej" :smiley:


(somekind) #9

Ta dłuższa może nie wykonuje obliczeń za każdym razem, ale ma za to więcej instrukcji warunkowych. Pytanie, co jest szybsze - obliczenia czy warunki, obstawiam, że w tym przypadku to pierwsze.

Jeśli chcesz się dowiedzieć, która z tych dwóch wersji jest szybsza, to napisz obie, a potem zmierz czas wywołania każdej z nich. To lepszy i szybszy sposób niż szukanie wróżki na forum.

Jeśli chodzi o to, która metoda jest szybsza, to jak już zauważył kolega wyżej, trzeba wziąć pod uwagę przypadki, dla których jedna zadziała lepiej niż druga. Gdybyś miał milion funkcji do rozwiązania, o których wiesz, że dla 80% z nich b jest różne 0, to wtedy możesz dobierać lepszy algorytm dla takiego zbioru danych. W zasadzie nigdy nie ma tak, że jakiś algorytm jest ogólnie lepszy. (Z wyjątkiem algorytmów zupełnie złych.)

Taki program IMHO jest bez sensu do bawienia się w optymalizację. Proste programy, w których można się tym zająć, to wyznaczanie elementów ciągu Fibonacciego albo poszukiwanie liczb pierwszych.


(Julek94) #10

Dzięki za odpowiedzi.

@Zulowski:

Na razie jeszcze LO, ale o studiach informatycznych już myślałem :slight_smile:

Temat chyba wyczerpany, można zamknąć

Pozdrawiam