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

[photon]

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

[Mihaylo]

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

Понятно, что чем меньше памяти расходуется и чем меньше процессорного времени, тем лучше, но на практике что-то более критично, а что-то менее.

С точки зрения практики, меня интересует примерно такой быстрый "прикид в уме": я рассматриваю работающий алгоритм и хочу изменить соотношение ресурсов памяти и процессора путем каких-то изменений. Допустим, я хочу уменьшить расходование памяти на $O(n^2)$, могу ли я ожидать замедление вычислений на $O(n)$ или $O(n\log n)$ или даже $O(1)$? Или будет замедление $o(n^2)$ и хоть ты тресни? Я сейчас не знаю никаких ограничений снизу и сверху.

[photon]

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

[B@R5uk]

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

Простой пример: на МК с аппаратным умножением преобразование байта в строку десятичных цифр можно решить в несколько умножений, вычитаний и двоичных сдвигов, а на МК без умножителя приходится крутить циклы, вычитая сотни и десятки, чтобы реализовать деление с остатком на 100 и на 10.

В более серьёзных процессорах (на персональных ЭВМ в том числе) наличие кэширования и его особенности могут накладывать свои требования на алгоритм.

И да, когда речь заходит про ресурсы памяти и процессора, забудьте про нотации о-малое, о-большое! Они годны только в теории, когда размеры памяти и время работы ничем не ограничены. На практике же гораздо важнее константа перед степенью сложности, поскольку алгоритм с линейной сложностью может работать на порядок быстрее, чем алгоритм с логарифмической сложностью, просто потому что константа меньше и данные не на столько велики, чтобы логарифмический выигрыш проявил себя. И разница в расходе памяти в 7,9 КБ и 8,1 КБ может оказаться причиной отказа от "хорошего" алгоритма в пользу "плохого" просто потому что "мест больше нет, хотя студент умный".

[Pavia]

Mihaylo
Как говорит мой шеф пол-потолок-палец. Никто пока что не проводил такую оценку.
Если хотите то постройте её сами. Да придётся рассмотреть куча алгоритмов и их оценок. Но что делать?
Возьмите:
1) Кнута Искусство программирования.
2) Грегори Р., Кришнамурти Е. Безошибочные вычисления: методы и приложения
3) Поищите оценки для алгоритмов регулярных-выражений.
4) АСМ Сборник алгоритмов. Не уверен что там оценка есть.
5) Ещё радужные-таблицы.
6) Алгоритмы ЦОС и обработки изображений.
7) Алгоритмы оптимизации.

-- Пт июн 21, 2019 16:37:31 --

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

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

Тут вот есть лекция на эту тему https://www.youtube.com/watch?v=SSLwGLu ... e=youtu.be

[Munin]

B@R5uk в сообщении #1400565 писал(а):

Простой пример: на МК с аппаратным умножением преобразование байта в строку десятичных цифр можно решить в несколько умножений, вычитаний и двоичных сдвигов, а на МК без умножителя приходится крутить циклы, вычитая сотни и десятки, чтобы реализовать деление с остатком на 100 и на 10.

А что на что умножается? Потому что умножение на 10 делается из тех же сложений и сдвигов.

B@R5uk в сообщении #1400565 писал(а):

И да, когда речь заходит про ресурсы памяти и процессора, забудьте про нотации о-малое, о-большое! Они годны только в теории

Мда? Ну-ну.

[Mihaylo]

B@R5uk в сообщении #1400565 писал(а):

И разница в расходе памяти в 7,9 КБ и 8,1 КБ может оказаться причиной отказа от "хорошего" алгоритма в пользу "плохого"

Вы правы только в случае конкретного железа. Можно будет радоваться ускорению работы алгоритма с 7 до 5 минут. Но если планируется распространение кода на неопределенные платформы, то останется осадок на душе.

[_Ivana]

B@R5uk в сообщении #1400565 писал(а):

Простой пример:

Ага, но все равно вот здесь post660328.html мне и писали что это

arseniiv в сообщении #660393 писал(а):

Кошмар!

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

Chifu в сообщении #660438 писал(а):

А делить на 10 не судьба?

и т.п.

[photon]

Pavia в сообщении #1400571 писал(а):

-- Пт июн 21, 2019 16:37:31 --

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

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

Тут вот есть лекция на эту тему https://www.youtube.com/watch?v=SSLwGLu ... e=youtu.be

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

[Mihaylo]

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

Известен факт, что сложность любого алгоритма сортировки по вычислению $o(n \log n)$ при условии, что элементарной операцией алгоритма является сравнение двух элементов массива.

Устойчивые алгоритмы:
Пузырьковая сортировка (Bubble sort): сложность вычислений $o(n^2)$, используемая память $o(1)$.
Сортировка перемешиванием (Cocktail sort): сложность вычислений $o(n^2)$, используемая память $o(1)$.
Сортировка вставками (Insertion sort): сложность вычислений $o(n^2)$, используемая память $o(1)$.
Сортировка с помощью двоичного дерева (Tree sort): сложность вычислений $o(n \log n)$, используемая память $o(n)$.
Сортировка слиянием (Merge sort): сложность вычислений $o(n \log n)$, используемая память $o(n)$.
Сортировка Timsort: сложность вычислений $o(n \log n)$, используемая память $o(n)$.

Неустойчивые алгоритмы:
Пирамидальная сортировка (Heapsort): минимальная, максимальная и средняя сложность вычислений $o(n \log n)$, используемая память $o(1)$.
Быстрая сортировка (Quicksort): средняя сложность вычислений $o(n \log n)$, в худшем случае $o(n^2)$, используемая память $o(n)$. Примечание: при использовании $O(n)$ дополнительной памяти, можно сделать сортировку устойчивой.

[photon]

Только приведенные сложности и оценки памяти ничего не говорят о реальных затратах на массивах конечной длины. Все эти оценки позволяют корректно сравнивать производительность алгоритмов только при $n\to\infty$

[Pavia]

Mihaylo

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

Известен факт, что сложность любого алгоритма сортировки по вычислению $o(n \log n)$ при условии, что элементарной операцией алгоритма является сравнение двух элементов массива.

Это не так.
Да и у вас везде $o$-малое, когда как то что вы написали это $O$-большое.

Вы ещё поразрядную сортировку забыли
Поразрядную сортировка (RadixSort): сложность вычислений $O(n)$, используемая память $O(n)$.

[podih]

В развивающихся ЯП нужность оптимизации на низком уровне стремится к нолю.
Команда $sort(ArrB)$ профессионально минимальна. Обычному программисту искать свои алгоритмы сортировки глупо. То же касается графики. а тем более, работу с длинными целыми и матричные операции. Последние как раз завязаны на память, но доморощенная оптимизация и там ни к чему. Время на разработку и ошибки, ошибки, ошибки.

[photon]

podih в сообщении #1400763 писал(а):

Обычному программисту искать свои алгоритмы сортировки глупо.

Это не так. Например, вам надо отсортировать данные типа uchar. Стандартный std::sort() даст $O(n\log n)$, в то время как зная, что возможные значения целочисленные в диапазоне от $0$ до $255$, программист отсортирует за $O(n)$.

[Munin]

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

Только приведенные сложности и оценки памяти ничего не говорят о реальных затратах на массивах конечной длины. Все эти оценки позволяют корректно сравнивать производительность алгоритмов только при $n\to\infty$

С одной стороны, это, конечно, формально верно. С другой стороны, даже и при $n\to\infty,$ извините меня, два алгоритма с $O(n\log n)$ будут вести себя по-разному, и снова потребуются оценки более точные и реалистичные. (На самом деле, для алгоритмов сортировки все перечисленные оценки верны с заменой $o$-малого на $O$-большое.)

А с третьей стороны, внезапно, оказывается, что бесконечность начинается уже с сотни, тысячи, миллиона. А иногда даже с четырёх. (На 4 элементах quicksort выигрывает у bubble sort.)