Соотношение между ресурсами памяти и ресурсами процессора

[Mihaylo]

Часто в компьютерной науке при разработке алгоритмов применяется принцип "пожертвование памятью в угоду быстродействию" или противоположное "экономия памяти за счет процессорных ресурсов". Эти принципы применяются неформально, точнее даже интуитивно.
А существует ли формальная закономерность между памятью и быстродействием для данного конкретного алгоритма? Может хотя бы в виде неравенства какого-то?

[Munin]

Обычно этот принцип означает, что один алгоритм заменяется на другой алгоритм. (Или структура данных на другую структуру данных.)

[EUgeneUS]

Цитата:

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

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

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

[Mihaylo]

Да, значит взаимозависимости более точной нет, чем нижеследующей?
Если больше памяти, то (возможно) меньше процессорного времени.

[EUgeneUS]

Mihaylo

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

[dobrichev]

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

[Mihaylo]

dobrichev в сообщении #1399575 писал(а):

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

Это понятно. Получается, если мы расходуем o(n) дополнительной памяти и, допустим, при этом экономим o(n) процессорного времени, то может оказаться так, что мы до этого тратили o(1) памяти и o($n^2$) времени, то решение неэффективно при больших n.

А может ли использование o(1) дополнительной памяти вызвать эффект o(n) или o($n \cdot \log n$) по процессорному времени? (Естественно, нужно полагать, что первый алгоритм должен быть "прошедшим отбор", "в меру эффективным" - нужно еще какой-то термин для этого ввести...)

[Sender]

Mihaylo в сообщении #1399646 писал(а):

А может ли использование o(1) дополнительной памяти вызвать эффект o(n) или o($n \cdot \log n$) по процессорному времени?

Если такой алгоритм есть, то обычно он и применяется. И, кстати, поаккуратнее с $O$-нотацией. $o$ - это совсем не то же самое, что $O$.

[SergeyGubanov]

Mihaylo в сообщении #1399553 писал(а):

Часто в компьютерной науке при разработке алгоритмов применяется принцип "пожертвование памятью в угоду быстродействию" или противоположное "экономия памяти за счет процессорных ресурсов". Эти принципы применяются неформально, точнее даже интуитивно.
А существует ли формальная закономерность между памятью и быстродействием для данного конкретного алгоритма? Может хотя бы в виде неравенства какого-то?

Известен объём L1 кэша и его пропускная способность. Известен объём L2 кэша и его пропускная способность. Известен объём L3 кэша и его пропускная способность. Известен объём оперативной памяти на локальной NUMA ноде и её пропускная способность. Известен объём оперативной памяти на других NUMA нодах и кросс-нума-нодовая пропускная способность. Известна стоимость всех кэшмисов. Известна глубина очередей загрузки/сохранения/испольнения. Известно сколько операций с плавающей точкой может выполнить процессор за секунду. Известно какие операции могут быть выполнены процессором за один такт одновременно. И много чего ещё известно для каждого конкретного компьютера. Вот это вот всё и превращается в "неравенство какое-то", которое нужно учитывать при оптимизации.

[Mihaylo]

Sender в сообщении #1399654 писал(а):

Если такой алгоритм есть, то обычно он и применяется.

Вот о чем я и говорю. Получается все-таки есть некоторое ограничение роста, но только при условии, что исходный (улучшаемый) алгоритм "достаточно эффективный". Если дать этому понятию "достаточно эффективный алгоритм" некоторое формальное определение, то можно в итоге получить некоторое соотношение?
Можно ли, затратив O(n) дополнительной памяти, получить эффект по быстродействию О($n^2$)?

Sender в сообщении #1399654 писал(а):

И, кстати, поаккуратнее с $O$-нотацией. $o$ - это совсем не то же самое, что $O$.

Да, в данном случае видимо следует применять О-большое.

SergeyGubanov в сообщении #1399686 писал(а):

Вот это вот всё и превращается в "неравенство какое-то", которое нужно учитывать при оптимизации.

С точными неравенствами неинтересно. Хотелось бы что-нибудь более фундаментальное, в О/о-нотациях.

[arseniiv]

Mihaylo в сообщении #1399792 писал(а):

Если дать этому понятию "достаточно эффективный алгоритм" некоторое формальное определение, то можно в итоге получить некоторое соотношение?

Я склоняюсь к тому, что написал EUgeneUS: все возможные соотношения — следствия практики, и потому как минимум эфемерны, и вместо их изучения полезнее изучать более непосредственно связанные с практикой вещи.

-- Пн июн 17, 2019 23:47:29 --

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

[upgrade]

Предположем все решения известны. Тогда на их хранение требуется пространство адресов и пространство данных. Чем длиннее адрес, тем большему количеству решений можно присвоить уникальный адрес и меньше количество шагов алгоритма требуется для поиска решения в ячейке памяти, но самих ячеек хранения тогда нужно больше. Если адрес один на все решения, то требуется поиск решения среди множества решений внутри ячейки памяти.
Как узнать - а решение ли мы нашли, другой уже вопрос.

[photon]

Mihaylo в сообщении #1399646 писал(а):

Получается, если мы расходуем o(n) дополнительной памяти и, допустим, при этом экономим o(n) процессорного времени

Так не бывает. У вас получается, что устремив расходы памяти в бесконечность, считать ничего не придется.

Понятно, что чем меньше памяти расходуется и чем меньше процессорного времени, тем лучше, но на практике что-то более критично, а что-то менее. Например, если какой-то алгоритм обрабатывает приходящие в реалтайме картинки, то жестким требованием может быть время обработки не более скольких-то миллисекунд, при этом из каких-то других соображений может быть требование, например, не использовать GPU и вообще все считать в одном потоке. Если стоит задача уложиться, скажем, в 50мс, то будет 40 или 20 мс уже не критично, а вот если получается 100мс, но можно снизить время втрое, увеличив потребление памяти, то может быть и в 50 раз больше памяти окажется приемлемым.

[_Ivana]

photon в сообщении #1400354 писал(а):

У вас получается, что устремив расходы памяти в бесконечность, считать ничего не придется.

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

[upgrade]

Входные данные станут фактически адресом хранения результата работы с ними алгоритма.