Что такое «накладные расходы»?

150

Я студент в области компьютерных наук, и я часто слышу слово «накладные расходы», когда речь идет о программах и видах. Что это значит точно?

yuudachi
источник
27
сколько «лишних вещей» нужно сделать, чтобы что-то получить. Например, если мне нужно загрузить проект из 37 классов только для того, чтобы напечатать «Hello World», я бы посчитал, что это слишком много.
Scunliffe
1
@ doug65536 На самом деле все наоборот. =)
Юкио Фукузава

Ответы:

178

Это ресурсы, необходимые для настройки операции. Это может показаться не связанным, но необходимым.

Это как когда тебе нужно куда-то ехать, тебе может понадобиться машина. Но было бы очень сложно получить машину, чтобы ехать по улице, так что вы можете хотеть идти пешком. Тем не менее, накладные расходы будут стоить, если вы собираетесь по всей стране.

В информатике иногда мы используем автомобили, чтобы идти по улице, потому что у нас нет лучшего пути, или не стоит тратить время на то, чтобы «научиться ходить».

corsiKa
источник
84
Похожая аналогия будет летать. Самолеты намного быстрее, чем машины, но накладные расходы на регистрацию в аэропорту, безопасность и т. Д. Делают машины лучшим вариантом для более коротких расстояний.
FogleBird
s / drive / go / (Если вам нужно ехать куда-то, вы обычно не решаете идти ...
RCIX
1
@ inf3rno Ирония? Как мы доберемся до нашей машины? Мы гуляем. И мы можем полностью дойти до нашей машины. Мы не можем дойти до пункта назначения, даже если он ближе, чем наша машина.
CorsiKa
Если бы я сказал, что пишу Java-код с низкими издержками, как бы вы интерпретировали это с точки зрения определения «ресурсов, необходимых для установки операции». Мой код не требует особой настройки?
совершиландройдер
Что ж, вам нужно включить компьютер или сервер, вы должны загрузить операционную систему и все драйверы, вы должны запустить процесс Java, вы должны включить JVM, вы должны загрузить все свои классы, вы необходимо синхронизировать буфер ввода-вывода с консолью, чтобы вы могли сделать свой «привет мир». Но, пожалуйста, расскажите мне больше о кодировании с низкими издержками.
CorsiKa
40

Значение слова может сильно различаться в зависимости от контекста. Как правило, используются ресурсы (чаще всего память и процессорное время), которые не вносят непосредственного вклада в ожидаемый результат, но требуются используемой технологией или методом. Примеры:

  • Затраты протокола : кадры Ethernet, IP-пакеты и сегменты TCP имеют заголовки, для TCP-соединений требуются пакеты квитирования. Таким образом, вы не можете использовать всю полосу пропускания, которую аппаратное обеспечение способно для ваших реальных данных. Вы можете уменьшить накладные расходы, используя пакеты большего размера, а UDP имеет меньший заголовок и не имеет рукопожатия.
  • Затраты памяти на структуру данных : связанному списку требуется как минимум один указатель для каждого элемента, который он содержит. Если элементы имеют такой же размер, что и указатель, это означает 50% -ую нагрузку на память, тогда как массив может потенциально иметь 0% -ую дополнительную нагрузку.
  • Затраты на вызов метода : хорошо разработанная программа разбита на множество коротких методов. Но каждый вызов метода требует настройки фрейма стека, копирования параметров и адреса возврата. Это представляет нагрузку на процессор по сравнению с программой, которая выполняет все в одной монолитной функции. Конечно, добавленная ремонтопригодность делает его очень стоящим, но в некоторых случаях чрезмерные вызовы методов могут оказать существенное влияние на производительность.
Майкл Боргвардт
источник
Похоже, слово имеет одинаковое значение во всех этих примерах (необходимо для выполнения задачи, но не всегда связано с выполнением этого напрямую)
RCIX
Перегрузка памяти структуры данных: с большинством распределителей памяти это даже хуже, чем это. Каждое возвращаемое значение mallocимеет встроенные служебные данные в 8 байтов из-за распределителя (в предположении, что классический 32-разрядный компьютер) состоит из размера блока и защитных значений. И это еще до того, как вы задумаетесь о гранулярности распределения. Поэтому односвязный список простых 4-байтовых целых чисел будет иметь накладные расходы 75%; массивы намного лучше (если вам не нужна быстрая вставка в середине), потому что они могут иметь накладные расходы один раз (или меньше, если массив не выделяется динамически).
Donal Fellows
19

Вы устали и больше не можете работать. Вы едите еду. Энергия, потраченная на поиски пищи, ее получение и потребление, потребляет энергию и накладные расходы!

Накладные расходы - это что-то напрасное, чтобы выполнить задачу. Цель состоит в том, чтобы сделать накладные расходы очень очень маленькими.

В информатике, скажем, вы хотите напечатать число, это ваша задача. Но сохранение номера, настройка дисплея для его печати и вызов подпрограмм для его печати, а затем доступ к номеру из переменной - все это накладные расходы.

Лаз
источник
17

Википедия рассказала нам :

В информатике издержками обычно считается любая комбинация избыточного или косвенного времени вычислений, памяти, полосы пропускания или других ресурсов, необходимых для достижения конкретной цели. Это особый случай инженерных накладных расходов.

Мэтью Джонс
источник
4
Но если этого не произойдет, вы исправите WikiPedia, а затем сделаете такой же пост здесь.
SamGoody
11

Накладные расходы обычно зависят от количества дополнительных ресурсов (памяти, процессора, времени и т. Д.), Которые занимают различные алгоритмы программирования.

Например, накладные расходы на вставку в сбалансированное двоичное дерево могут быть намного больше, чем та же самая вставка в простой связанный список (вставка займет больше времени, потребует больше вычислительной мощности, чтобы сбалансировать дерево, что приведет к более длительному воспринимаемому времени работы на Пользователь).

Джастин Нисснер
источник
5

Под накладными расходами программиста понимаются те системные ресурсы, которые потребляются вашим кодом, когда он работает на платформе предоставления данных с заданным набором входных данных. Обычно этот термин используется в контексте сравнения различных реализаций или возможных реализаций.

Например, мы могли бы сказать, что конкретный подход может привести к значительным перегрузкам ЦП, в то время как другой может повлечь за собой дополнительные затраты памяти, а другой может быть взвешен с нагрузкой на сеть (например, повлечь за собой внешнюю зависимость).

Давайте приведем конкретный пример: вычислим среднее (среднее арифметическое) набора чисел.

Очевидный подход состоит в том, чтобы перебрать входные данные, сохраняя промежуточный итог и счет. Когда встречается последнее число (сигнализируемое EOF «конец файла», или некоторым значением часового, или некоторой кнопкой GUI, что угодно), то мы просто делим общее количество на количество входов, и все готово.

Этот подход почти не требует затрат ресурсов процессора, памяти или других ресурсов. (Это тривиальная задача).

Другой возможный подход заключается в том, чтобы «убрать» входные данные в список. переберите список, чтобы вычислить сумму, а затем разделите ее на количество действительных элементов в списке.

Для сравнения этот подход может привести к произвольным объемам памяти.

В конкретной неудачной реализации мы могли бы выполнить операцию суммирования, используя рекурсию, но без исключения хвоста. Теперь, в дополнение к накладным расходам памяти для нашего списка, мы также вводим накладные расходы стека (который является другим видом памяти и часто является более ограниченным ресурсом, чем другие виды памяти).

Еще одним (возможно, более абсурдным) подходом будет размещение всех входных данных в некоторой таблице SQL в СУБД. Затем просто вызовите функцию SQL SUM для этого столбца этой таблицы. Это переносит накладные расходы нашей локальной памяти на какой-либо другой сервер и приводит к накладным расходам сети и внешним зависимостям от нашего выполнения. (Обратите внимание, что удаленный сервер может иметь или не иметь каких-либо определенных накладных расходов памяти, связанных с этой задачей - например, он может немедленно выгнать все значения в хранилище).

Гипотетически можно было бы рассмотреть реализацию над каким-то кластером (возможно, чтобы было возможно усреднение триллионов значений). В этом случае любое необходимое кодирование и распределение значений (сопоставление их с узлами) и сбор / сопоставление результатов (сокращение) будут засчитываться как издержки.

Мы также можем говорить о накладных расходах, вызванных факторами, выходящими за рамки собственного кода программиста. Например, компиляция некоторого кода для 32- или 64-разрядных процессоров может повлечь за собой большие издержки, чем можно было бы увидеть для старой 8-разрядной или 16-разрядной архитектуры. Это может быть связано с большими перегрузками памяти (проблемы с выравниванием) или загрузкой ЦП (когда ЦП вынужден корректировать порядок битов или использовать невыровненные инструкции и т. Д.) Или и тем, и другим.

Обратите внимание, что дисковое пространство, занимаемое вашим кодом, его библиотеками и т. Д., Обычно не называется «накладными расходами», а называется «занимаемая площадь». Кроме того, базовая память, которую использует ваша программа (без учета какого-либо набора данных, который она обрабатывает), также называется ее «площадью».

Джим Деннис
источник
3

Издержки - это просто большее время, затрачиваемое на выполнение программы. Пример ; когда мы вызываем функцию, и ее управление передается туда, где она определена, а затем выполняется ее тело, это означает, что мы заставляем наш ЦП проходить долгий процесс (сначала передавая управление другому месту в памяти, а затем выполняя там и тогда передача управления обратно в прежнее положение), следовательно, это занимает много времени производительности, следовательно, накладные расходы. Наши цели состоят в том, чтобы уменьшить эти издержки путем использования встроенного во время определения функции и времени вызова, которое копирует содержимое функции при вызове функции, следовательно, мы не передаем элемент управления в другое место, но продолжаем нашу программу в строке, следовательно, встроенной ,

Мусаиб
источник
2

Вы могли бы использовать словарь. Определение то же самое. Но чтобы сэкономить ваше время, накладные расходы - это работа, необходимая для продуктивной работы. Например, алгоритм работает и выполняет полезную работу, но для его работы требуется память. Это распределение памяти занимает время, и не имеет прямого отношения к выполняемой работе, поэтому накладные расходы.

Ян Рамин
источник
1

Вы можете проверить Википедию . Но в основном, когда больше действий или ресурсов используются. Например, если вы знакомы с .NET, у вас могут быть типы значений и ссылочные типы. У ссылочных типов есть накладные расходы памяти, поскольку они требуют больше памяти, чем типы значений.

Инкогнито
источник
1

Конкретным примером издержек является различие между «локальным» вызовом процедуры и «удаленным» вызовом процедуры.

Например, в классическом RPC (и многих других удаленных средах, таких как EJB) вызов функции или метода выглядит одинаково для кодера, будь то локальный вызов в памяти или распределенный сетевой вызов.

Например:

service.function(param1, param2);

Это обычный метод или удаленный метод? Из того, что вы видите здесь, вы не можете сказать.

Но вы можете себе представить, что разница во времени выполнения между двумя вызовами является существенной.

Таким образом, хотя реализация ядра будет «стоить одинаково», связанные с этим «накладные расходы» будут совершенно другими.

Уилл Хартунг
источник
1

Думайте о накладных расходах как о времени, необходимом для управления потоками и координации между ними. Обременительно, если у потока недостаточно задач. В таком случае накладные расходы превышают сэкономленное время за счет использования потоков, а код занимает больше времени, чем последовательный.

Анас
источник
-2

это что-то, кроме самих данных, т.е. флаги tcp, заголовки, crc, fcs и т. д.

Родни Ручи
источник