Какие ресурсы «экономить» при алгоритмизации?

Question

[Urukhayy]

Допустим есть некая задача. И естественно для решения этой задачи можно найти множество путей. Также естественно, что нужно найти самый оптимальный путь.

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

Comments

[Freeman]

Язык какой, интерпретируемый или компилируемый? Переходите на компилируемый.

Answer 1

[Максим Кудрявцев]

Задача "экономить" технические мощности встает в трех случаях:

1. Вы Марк Цукерберг и Вашему Facebook не хватает мощностей всех датацентров для нормального функционирования
   
2. Вы программируйте тостер/утую/кофеварку и т.п. где в принципе ресурсов нет
   
3. Вы мазохист и используйте шаг 0,000000001 в методе приближения чего-либо
   

С моей точки зрения, написанный Вами код должен в первую очередь быть понятен другому разработчику, он должен легко читаться, возможно, расширяться. Если клиент стоит перед выбором "Нанять разработчика за 1к у.е./месяц или арендовать под свой проект еще один сервер за 250 у.е./месяц", то я сомневаюсь что он выберет первый вариант, кроме случая №1 из списка выше.

Comments

[Shetani]

Сервер в тостере/утюге/кофеварке - очень оригинальное решение XD

[pi314]

Если задача встает, когда вашему Фейсбуку уже не хватает мощностей, то а) это - не Фейсбук, и б) Вы - не Цукерберг :)

Answer 2

[Дмитрий Энтелис]

В 99% случаев надо экономить ресурс под названием "время программиста".
А в оставшемся 1% - исходить из реальной задачи и реальных условий по объему данных, имеющимся аппаратным ресурсам и требуемому быстродействию.

Answer 3

[Mrrl]

Если вы хотите экономить память, то проблема будет не в переменных, а в больших структурах (списки, массивы, словари...). Мне чаще всего встречаются такие ситуации:
- память в обмен на время. Запоминать результаты или вычислять заново? Иногда здесь удаётся обменять экспоненциальное время на полиномиальное, или уменьшить степень полинома на 1 или на 2. Но чаще выигрыш идёт только в константу раз (хотя в узком месте это может быть немаловажно). Впрочем, иногда вычислить функцию оказывается быстрее, чем найти её значение в таблице - так что надо такие оптимизации проверять.
- замена обработки большого массива в памяти на послойную обработку (когда очередной фрагмент/строка/двумерный слой трёхмерного массива... вычисляется, обрабатывается, а уже ненужный слой забывается). Здесь память экономится за счёт серьёзного усложнения кода - приходится писать всякие конвейеры. Зато появляется шанс сэкономить ещё и время с помощью параллельной обработки.
- хранение данных, которые должны быть в памяти, в упакованном виде. Трудно читать, очень трудно писать, код усложняется, время теряется. Но появляется шанс уложиться в 3 ГБ и остаться в 32-битном режиме (если это важно).
- хранение в памяти против чтения из файла. Либо будет теряться время, либо усложняться код (если сумеете воспользоваться асинхронным чтением/записью).
- в тяжелых случаях - экономия байтов кода (это если пишете на ассемблере). Может пригодиться, если действительно пишете сервер для кофеварки. Но возможно, здесь лучше попытаться поставить процессор помощнее.

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

Comments

[Urukhayy]

А можете вкратце и своими словами описать подробней про экспоненциальное и полиномиальное время?)

[Mrrl]

Например, такая дурацкая задача:
Последовательность X строится так, что X[n] - наименьшее натуральное число, которое делится на [sqrt(n)] и не встречается в этой последовательности раньше (что-то вроде 1,2,3,4,6,8,10,12,9,15,18...)
Требуется найти n-й элемент.
Если у нас есть память O(n), то всё просто - просматриваем предыдущие элементы, выбираем из них те, которые удовлетворяют условию, сортируем, берём первое число, которое условию удовлетворяет, но в отсортированной последовательности отсутствует. Получается примерно O(n^2*log(n)) операций (для этой задачи - даже меньше). Но если последовательность хранить негде, то её предыдущие элементы придётся вычислять. А для их вычисления - вычислять ещё более ранние. Получается примерно 2^n операций, а то и n! (ведь для поиска дырки перевычислять последовательность придётся несколько раз).
Возможно, у этой задачи есть математическое решение, для которого достаточно конечной памяти. Но первое условие всегда можно заменить на что-нибудь посложнее.

Answer 4

[ivkol]

вот цитата из книги по js:

Я заостряю на этом внимание оттого, что слишком много начинающих программистов хватаются за эффективность даже в мелочах. Результат получается больше, сложнее и часто не без ошибок. Такие программы дольше писать, а работают они часто не сильно быстрее. Основное правило, которое уже не раз повторяли, и с которым я полностью согласен – не беспокойтесь насчёт быстродействия, пока вы точно не уверены, что программа тормозит. Если так, найдите те части, которые работают дольше всех, и меняйте там элегантность на эффективность.

Answer 5

[Saboteur]

Задача программиста не писать алгоритмы, а решать конкретные задачи, посредством написания алгоритмов.

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

Answer 6

[Сергей Протько]

и увеличить при этом количество переменных

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

Да и вообще, все очень зависит от языка программирования и компилятора.

По самим алгоритмам можно только предсказать сложность на очень больших объемах данных и исходить из этого.

Answer 7

[FoxInSox]

Когда как, зависит от случая.