Co to jest „narzut”?

149

Jestem studentem informatyki i często słyszę słowo „nad głową”, jeśli chodzi o programy i ich rodzaje. Co to dokładnie oznacza?

yuudachi
źródło
27
ile „dodatkowych rzeczy” trzeba zrobić, aby coś uzyskać. np. jeśli muszę załadować projekt klasy 37 tylko po to, aby wydrukować „Hello World”, uznałbym to za duży narzut.
scunliffe
1
@ doug65536 Właściwie jest na odwrót. =)
Yukio Fukuzawa

Odpowiedzi:

177

To zasoby wymagane do skonfigurowania operacji. Może się to wydawać niezwiązane, ale konieczne.

To tak, jakbyś musiał gdzieś jechać, możesz potrzebować samochodu. Ale zmuszenie samochodu do jazdy po ulicy wymagałoby dużego wysiłku, więc warto iść pieszo. Jednak koszty ogólne byłyby tego warte, gdybyś jechał przez kraj.

W informatyce czasami jedziemy po ulicy samochodami, ponieważ nie mamy lepszego sposobu lub nie warto poświęcać czasu na „naukę chodzenia”.

corsiKa
źródło
84
Podobna analogia to latanie. Samoloty są znacznie szybsze niż samochody, ale obciążenie związane z odprawą na lotnisku, ochroną itp. Sprawia, że ​​samochody są lepszą opcją na krótsze odległości.
FogleBird
s / drive / go / (Jeśli chcesz jechać gdzieś, gdzie zwykle nie decydujesz się na spacer ...
RCIX
1
@ inf3rno Ironia? Jak dojeżdżamy do naszego samochodu? Chodzimy. I możemy całkowicie dojść ... do naszego samochodu. Nie możemy dojść do celu, nawet jeśli jest bliżej niż nasz samochód.
corsiKa
Gdybym miał powiedzieć, że piszę kod Java o niskim nakładzie pracy, jak byś to zinterpretował pod względem definicji „zasobów wymaganych do skonfigurowania operacji”. Mój kod nie wymaga dużej konfiguracji?
popełnionyandroider
Cóż, musisz włączyć komputer lub serwer, musisz załadować system operacyjny i wszystkie sterowniki, musisz odpalić proces Java, musisz włączyć JVM, musisz załadować wszystkie swoje zajęcia, musisz musisz zsynchronizować bufor IO z konsolą, abyś mógł zrobić swój „hello world”. Ale proszę, powiedz mi więcej o kodowaniu niskiego narzutu.
corsiKa
40

Znaczenie tego słowa może się znacznie różnić w zależności od kontekstu. Ogólnie rzecz biorąc, to zasoby (najczęściej pamięć i czas procesora) są używane, które nie mają bezpośredniego wpływu na zamierzony rezultat, ale są wymagane przez używaną technologię lub metodę. Przykłady:

  • Narzut protokołu : ramki Ethernet, pakiety IP i segmenty TCP mają nagłówki, połączenia TCP wymagają pakietów uzgadniania. W związku z tym nie można wykorzystać całej przepustowości, jaką sprzęt jest w stanie wykorzystać dla rzeczywistych danych. Możesz zmniejszyć obciążenie, używając większych rozmiarów pakietów, a protokół UDP ma mniejszy nagłówek i nie wymaga uzgadniania.
  • Narzut pamięci struktury danych : połączona lista wymaga co najmniej jednego wskaźnika dla każdego elementu, który zawiera. Jeśli elementy mają taki sam rozmiar jak wskaźnik, oznacza to 50% narzut pamięci, podczas gdy tablica może potencjalnie mieć 0% narzut.
  • Narzut wywołania metod : dobrze zaprojektowany program jest podzielony na wiele krótkich metod. Ale każde wywołanie metody wymaga ustawienia ramki stosu, skopiowania parametrów i adresu zwrotnego. Stanowi to obciążenie procesora w porównaniu z programem, który wykonuje wszystko w pojedynczej funkcji monolitycznej. Oczywiście dodatkowa łatwość konserwacji sprawia, że ​​jest to bardzo tego warte, ale w niektórych przypadkach nadmierne wywołania metod mogą mieć znaczący wpływ na wydajność.
Michael Borgwardt
źródło
Brzmi, jakby słowo miało to samo znaczenie we wszystkich tych przykładach (konieczne do wykonania zadania, ale nie zawsze związane z wykonywaniem go bezpośrednio)
RCIX
Ponownie narzut pamięci w strukturze danych: w przypadku większości alokatorów pamięci jest jeszcze gorzej. Każda wartość zwracana przez mallocma wbudowany narzut 8 bajtów ze względu na alokator (zakładając klasyczną maszynę 32-bitową) składający się z rozmiaru bloku plus wartości ochronne. I to zanim jeszcze pomyślisz o szczegółowości alokacji. Lista połączonych pojedynczo prostych 4-bajtowych liczb całkowitych będzie zatem miała narzut 75%; tablice są znacznie lepsze (chyba że potrzebujesz szybkiego wstawienia w środku), ponieważ mogą mieć jeden narzut (lub mniej, jeśli tablica nie jest przydzielana dynamicznie).
Donal Fellows
19

Jesteś zmęczony i nie możesz więcej pracować. Jesz jedzenie. Energia wydatkowana na szukanie pożywienia, zdobywanie go i jedzenie pochłania energię i jest nad głową!

Narzut jest czymś zmarnowanym, aby wykonać zadanie. Celem jest, aby narzuty były bardzo małe.

W informatyce powiedzmy, że chcesz wydrukować liczbę, to jest twoje zadanie. Ale przechowywanie numeru, ustawienie wyświetlacza w celu jego wydrukowania i wywoływanie procedur, aby go wydrukować, a następnie dostęp do numeru ze zmiennej to wszystko narzut.

Laz
źródło
17

Wikipedia nas omawia :

W informatyce ogólnie uważa się , że narzut jest dowolną kombinacją nadmiernego lub pośredniego czasu obliczeniowego, pamięci, przepustowości lub innych zasobów, które są wymagane do osiągnięcia określonego celu. Jest to szczególny przypadek kosztów inżynierskich.

Matthew Jones
źródło
4
Ale gdyby tak się nie stało, naprawiłbyś WikiPedia, a następnie zrobiłbyś ten sam wpis tutaj.
SamGoody
11

Narzut zwykle odnosi się do ilości dodatkowych zasobów (pamięci, procesora, czasu itp.), Które zajmują różne algorytmy programowania.

Na przykład, narzut wstawiania do zbalansowanego drzewa binarnego może być znacznie większy niż tego samego wstawiania do prostej listy połączonej (wstawianie zajmie więcej czasu, zużyje więcej mocy obliczeniowej, aby zrównoważyć drzewo, co skutkuje dłuższym postrzeganym czasem operacji przez użytkownik).

Justin Niessner
źródło
5

Narzut programisty odnosi się do tych zasobów systemowych, które są zużywane przez twój kod, gdy działa na podanej platformie na danym zestawie danych wejściowych. Zwykle termin ten jest używany w kontekście porównywania różnych implementacji lub możliwych implementacji.

Na przykład możemy powiedzieć, że określone podejście może powodować znaczne obciążenie procesora, podczas gdy inne może powodować większe obciążenie pamięci, a jeszcze inne może obciążać obciążenie sieci (i pociągać za sobą na przykład zależność zewnętrzną).

Podajmy konkretny przykład: Oblicz średnią (średnią arytmetyczną) zbioru liczb.

Oczywistym podejściem jest zapętlenie wejść, zachowując bieżącą sumę i licznik. Kiedy napotkamy ostatnią liczbę (sygnalizowaną przez "koniec pliku" EOF lub jakąś wartość wartowniczą, albo jakiś przycisk GUI, cokolwiek), po prostu dzielimy całość przez liczbę wejść i gotowe.

Takie podejście nie powoduje prawie żadnego narzutu w postaci procesora, pamięci lub innych zasobów. (To trywialne zadanie).

Innym możliwym podejściem jest „siorbanie” danych wejściowych na listę. powtórz listę, aby obliczyć sumę, a następnie podziel ją przez liczbę prawidłowych elementów z listy.

Dla porównania, takie podejście może powodować dowolne ilości narzutów pamięci.

W szczególnie złej implementacji możemy wykonać operację sumowania przy użyciu rekurencji, ale bez eliminacji ogonów. Teraz, oprócz narzutu pamięci dla naszej listy, wprowadzamy również narzut stosu (który jest innym rodzajem pamięci i często jest bardziej ograniczonym zasobem niż inne formy pamięci).

Jeszcze innym (prawdopodobnie bardziej absurdalnym) podejściem byłoby wysłanie wszystkich danych wejściowych do jakiejś tabeli SQL w RDBMS. Następnie po prostu wywołuj funkcję SUMA SQL w tej kolumnie tej tabeli. Powoduje to przeniesienie narzutu naszej pamięci lokalnej na inny serwer i powoduje obciążenie sieci i zewnętrzne zależności od naszego wykonania. (Zwróć uwagę, że zdalny serwer może, ale nie musi, mieć określony narzut pamięci związany z tym zadaniem - na przykład może natychmiast wypchnąć wszystkie wartości do pamięci).

Hipotetycznie można rozważyć implementację na jakimś klastrze (prawdopodobnie w celu umożliwienia uśrednienia bilionów wartości). W takim przypadku wszelkie niezbędne kodowanie i dystrybucja wartości (mapowanie ich do węzłów) oraz zbieranie / zestawianie wyników (redukcja) liczy się jako narzut.

Możemy również mówić o narzutach ponoszonych przez czynniki wykraczające poza własny kod programisty. Na przykład kompilacja jakiegoś kodu dla procesorów 32- lub 64-bitowych może wiązać się z większym narzutem niż w przypadku starej architektury 8- lub 16-bitowej. Może to wiązać się z większym narzutem pamięci (problemy z wyrównaniem) lub obciążeniem procesora (gdy procesor jest zmuszony do dostosowania kolejności bitów lub używa instrukcji nie wyrównanych itp.) Lub obu.

Zwróć uwagę, że miejsce na dysku zajmowane przez Twój kod i jego biblioteki itp. Nie jest zwykle określane jako „obciążenie”, ale raczej jest nazywane „śladem”. Również pamięć podstawowa, którą zużywa twój program (bez względu na zbiór danych, które przetwarza) jest również nazywana jego „śladem”.

Jim Dennis
źródło
3

Narzut to po prostu więcej czasu na wykonanie programu. Przykład; kiedy wywołujemy funkcję i jej kontrola jest przekazywana tam, gdzie jest zdefiniowana, a następnie jej treść jest wykonywana, oznacza to, że zmuszamy nasz procesor do pracy przez długi proces (najpierw przekazujemy kontrolę w inne miejsce w pamięci, a następnie wykonujemy tam przekazanie kontroli z powrotem do poprzedniej pozycji), w konsekwencji zajmuje dużo czasu, stąd narzut. Naszym celem jest zmniejszenie tego narzutu poprzez użycie inline podczas definiowania funkcji i czasu wywoływania, które kopiuje zawartość funkcji przy wywołaniu funkcji, dlatego nie przekazujemy kontroli do innej lokalizacji, ale kontynuujemy nasz program w linii, stąd inline .

Musaib
źródło
2

Możesz użyć słownika. Definicja jest taka sama. Aby jednak zaoszczędzić czas, praca nad głową jest wymagana do wydajnej pracy. Na przykład algorytm działa i wykonuje pożyteczną pracę, ale wymaga pamięci do wykonania swojej pracy. Ta alokacja pamięci wymaga czasu i nie jest bezpośrednio związana z wykonywaną pracą, dlatego jest narzutem.

Yann Ramin
źródło
1

Możesz sprawdzić Wikipedię . Ale głównie wtedy, gdy wykorzystuje się więcej działań lub zasobów. Podobnie jak jeśli znasz .NET, możesz mieć typy wartości i typy odwołań. Typy odwołań mają narzut pamięci, ponieważ wymagają więcej pamięci niż typy wartości.

Incognito
źródło
1

Konkretnym przykładem narzutu jest różnica między „lokalnym” wywołaniem procedury a „zdalnym” wywołaniem procedury.

Na przykład w klasycznym RPC (i wielu innych zdalnych strukturach, takich jak EJB), wywołanie funkcji lub metody wygląda tak samo dla kodera, niezależnie od tego, czy jest to wywołanie lokalne, w pamięci, czy rozproszone wywołanie sieciowe.

Na przykład:

service.function(param1, param2);

Czy to normalna metoda, czy metoda zdalna? Z tego, co tu widzisz, nie możesz powiedzieć.

Ale możesz sobie wyobrazić, że różnica w czasach wykonania między dwoma wezwaniami jest dramatyczna.

Tak więc, chociaż podstawowa implementacja będzie „kosztować tyle samo”, związane z nią „koszty ogólne” są zupełnie inne.

Will Hartung
źródło
1

Pomyśl o narzutach jako o czasie wymaganym do zarządzania wątkami i koordynacji między nimi. Jest to obciążenie, jeśli wątek nie ma wystarczających zadań do wykonania. W takim przypadku koszty ogólne przewyższają oszczędność czasu dzięki zastosowaniu wątków, a kod zajmuje więcej czasu niż kod sekwencyjny.

Anas
źródło
-2

to wszystko inne niż same dane, tj. flagi tcp, nagłówki, crc, fcs itp.

Rodney Rouchy
źródło