Pytanie Lepszy algorytm do znalezienia średniej [zamknięty]


Robię ćwiczenie z książki programowania Książka o C . Ćwiczenie sugeruje, że aby znaleźć średnią z grupy liczb, algorytm:

avg += (x - avg) / i;

jest lepszy niż:

sum += x;
avg = sum / i;

"x" jest zmienną używaną do przechowywania numerów wejściowych. Sugeruje również, oprócz zapobiegania przepełnieniu, pierwszy algorytm ma inne korzyści niż drugi algortim, czy ktoś może mi pomóc? Dzięki!


16
2018-06-03 13:15


pochodzenie


Heh. Wydaje mi się, że mam tutaj pierwszą kopię tej książki, tuż przy moim biurku. W którym rozdziale to jest? - T.E.D.
pierwszy rozdział, ćwiczenie 17. - Oliver
kontrargument --- druga metoda ignorowania przepełnień jest (prawdopodobnie) szybciej (dla miliardów operacji) ponieważ wykonywany jest tylko 1 podział :) - pmg
@pmg Just Awesome comment.other następnie przepełnienie, dlaczego powinniśmy wybrać I'st metodę. Nie można usunąć z odpowiedzi wysłanych przez facetów tutaj. - Algorithmist
@pmg Może brakuje mi czegoś, ale w jaki sposób pierwsza metoda wykonuje dwa podziały? - Michael Mior


Odpowiedzi:


Zakładam, że mówimy tutaj o arytmetyzacji zmiennoprzecinkowej (w przeciwnym razie "lepsza" średnia będzie straszna).

W drugiej metodzie wynik pośredni (sum) będzie rosnąć bez ograniczeń, co oznacza, że ​​ostatecznie stracisz precyzję low-end. W pierwszej metodzie wynik pośredni powinien pozostać w przybliżeniu zbliżony do danych wejściowych (zakładając, że dane wejściowe nie mają ogromnego zakresu dynamicznego). co oznacza, że ​​lepiej zachowa precyzję.

jednak, Mogę sobie to wyobrazić jako i staje się coraz większy, wartość (x - avg) / i będzie coraz mniej dokładny (relatywnie). Ma także wady.


9
2018-06-03 13:39



+1 mógłbyś wyjaśnić "stracić precyzję low-end". I który z nich musimy użyć. - Algorithmist
@Algorytm: Rozważ strukturę reprezentacji zmiennoprzecinkowej; za mantysa i wykładnik potęgowy. Mantysa reprezentuje dokładność, tj. Cyfry znaczące, i jest ich stała liczba. W miarę jak twoje liczby będą rosły, wykładnik zacznie się zwiększać, co oznacza, że ​​twoje znaczące cyfry zaczynają oddalać się od punktu binarnego. - Oliver Charlesworth
Jak widzę, problem z (x - avg) / i jest tylko częściowo spowodowane przez i coraz większe. The (x - avg) sama część jest również problemem, jeśli wiele liczb jest zbliżonych do średniej, ponieważ odejmowanie pobliskich liczb zmiennoprzecinkowych traci dokładność. - j_random_hacker


Jest to lepsze w tym sensie, że oblicza średnią bieżącą, tj. Nie musisz mieć wszystkich swoich liczb z góry. Możesz to obliczyć w miarę upływu czasu lub w miarę, jak liczby stają się dostępne.


4
2018-06-03 13:20



Będziesz w stanie obliczyć każdą przyrostową średnią w stałym czasie, w przeciwieństwie do O (N) - pepsi
Dzięki! Powiedział: "W tym ćwiczeniu kontynuujesz pracę, którą wykonałeś w poprzednim ćwiczeniu. Jeśli uruchomisz program better_average pobierający dane wejściowe z pliku zawierającego zwykłe liczby, to pierwszy algorytm i drugi algorytm wydają się tworzyć identyczne Odpowiedź Znajdź sytuację, w której tak nie jest, to jest demonstruj eksperymentalnie, że lepsza średnia jest naprawdę lepsza, nawet gdy suma się nie przepełnia. Czy możesz mi powiedzieć, która sytuacja by to spowodowała? - Oliver
-1: Oba są w stanie obliczyć średnią bieżącą. - Oliver Charlesworth


Ten ostatni algorytm jest szybszy od poprzedniego, ponieważ trzeba wykonać operacje n (w rzeczywistości to ostatnie wymaga wykonania operacji 2 * n). Ale prawdą jest, że pierwszy zapobiega przepełnieniu. Na przykład, jeśli masz zestaw 1000 numerów: 4000000 * 250, 1500000 * 500, 2000000 * 500, całkowita suma wszystkich liczb całkowitych będzie wynosić 2'750.000.000, ale górna granica typu danych c ++ int to 2 147 483 647. Tak więc mamy do czynienia w tym przypadku z problemem przepełnienia. Ale jeśli wykonasz pierwszy algorytm, będziesz w stanie poradzić sobie z tym problemem.

Polecam więc, abyś użył pierwszego algorytmu, jeśli prawdopodobnie wystąpi przepełnienie, w przeciwnym razie doda tylko dodatkowe operacje. Jeśli zdecydujesz się użyć pierwszego tak czy inaczej, polecam używanie typu o większym zakresie.


1
2018-06-03 13:39



Najprawdopodobniej będzie to arytmetyka zmiennoprzecinkowa. Tak więc rozważania dotyczące przelania są zwykle nieistotne. - Oliver Charlesworth
Właściwie to prawda - Jesufer Vn


Ok, odpowiedź nie leży w przepełnieniu sumy (ponieważ jest wykluczone), ale jak powiedział Oli w "utracie precyzji low-end". Jeśli średnia z sumowanych liczb jest o wiele większa niż odległość każdej liczby od średniej, drugie podejście spowoduje utratę bitów mantysy. Ponieważ pierwsze podejście polega tylko na wartościach względnych, nie cierpi z tego powodu.

Tak więc każda lista liczb, która jest większa niż, powiedzmy, 60 milionów (dla zmiennoprzecinkowych pojedynczej precyzji), ale wartości nie różnią się o więcej niż 10, powinna pokazać to zachowanie.

Jeśli używasz spławów podwójnej precyzji, średnia wartość powinna być znacznie wyższa. Lub delty znacznie niższe.


1
2018-06-03 15:33



Uwaga: pamiętaj, że twoje wartości są reprezentowalne w wybranej przez ciebie precyzji. Następnie dodaj wystarczającą liczbę wartości na liście. - David Winant


Bardzo podobają mi się druga metoda (sumowanie w pętli i dzielenie na końcu) i mogę zidentyfikować drugą metodę znacznie szybciej niż pierwsza.

Różnice w wydajności, jeśli występują, są nieistotne.

A jeśli suma wartości przepełni wystarczająco duży typ danych, prawdopodobnie będziesz mieć więcej problemów niż obliczanie średniej.


1
2018-06-03 13:47



Różnice liczbowe mogą być istotne. To właśnie ten rodzaj rozważań prowadzi do algorytmu sumowania Kahana i tym podobnych. - Oliver Charlesworth
+1 Oli: upewniając się, że jest to wyraźnie powiedziane - metoda dzielenia po sumie jest bardziej niezawodna (przekroczenie limitu) - pmg


sum += x;
avg = sum / i;

W powyższym kodzie założymy, że mamy liczby jako 10000,20000, czyli liczby zawierające dużą liczbę cyfr, wtedy suma wartości może przekroczyć jej wartość MAX, co nie ma miejsca w przypadku I, ponieważ suma jest zawsze dzielona przez liczbę elementy przed przechowywaniem w nim.

Chociaż ze względu na duże typy danych obecne w języku programowania może to nie stanowić problemu

Eksperci mówią: "Użyj typu danych zgodnie z Twoją aplikacją i wymaganiami".


0
2018-06-03 13:25



PO powiedział "obok zapobiegania przelewaniu się" - pepsi


Jak o obliczaniu w ten sposób, zakładając, że ints są w tablicy ?:

sum += x[i] / N; rem += x[i] % N;
avg = sum + rem/N;

Gdyby N jest duży (0xFFFFF) i x[i] są tak małe rem dodaje do 0xFFFF (największa wartość int), co może się zdarzyć.


-3
2017-10-22 23:47