Языки програмирования (скриптовые) (Кому что нравится)

[Hephaestus]

преждевременные оптимизации == зло.

Не вполне. Если есть явно неудачная конструкция, то её лучше исправить/изменить сразу же, пока она перед глазами, а не потом искать/думать, где косяк.

Всё вышеперечисленное умеет компилятор делать.

Компилятор чего? Я ж говорю, рассуждения ведутся без привязки к языку.

ВНЕЗАПНО: да.

Неужели? И без них можно обойтись?
Я, конечно, не сишник, я больше имел дело с Pascal, там например, даже динамический массив не сделать без явного использования указателей (в некоторых других языках можно). И соответственно, любые вещи, требующие динамического выделения памяти (графика, например), подразумевают использование указателей.
Полагаю, что в Сях подобная ситуация. Или нет?
Как работать с данными, размер которых заранее неизвестен?

[Hephaestus]

это не важно. Всё равно это зло. Время тратить нужно на оптимизацию алгоритма.

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

[Bizdelnick]

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

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

Я где-то на форуме рассказывал о своём опыте с системой Гарант. Там была не слишком удачная схема обновления баз.
Так вот поначалу тоже было - не всё ли равно, отработает за 40 минут или за 1 час? Пустяки.
Но когда база разрослась, этот 1 час превратился в 4-5 часов. И разница в 20 минут превратилась в разницу в пару часов.
Так что здесь нельзя заранее сказать, как оно заработает в других условиях, и как окупится затраченное время.

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

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

Не надо подменять причину и следствие. Если можно сэкономить существенное время - то стоит браться за оптимизацию, если нет - то и фиг с ней.

Я не такую оптимизацию имел в виду, когда говорил об использовании сдвигов вместо умножения/деления.
Дело в том, что умножение/деление относятся к "тяжелым" операциям.
А сдвиг - это не просто умножение/деление на 2. Это может быть умножение/деление на 1073741824, например, что не совсем одно и то же.
Поэтому сдвиг всегда намного быстрее. Если в программе много "тяжелых" вычислений - то таким видом оптимизации пренебрегать не стоит.

Почти что согласен, но с одной поправкой: не если в программе много "тяжёлых" вычислений, а если они занимают ощутимую долю времени выполнения программы (с числом строк кода, в которых они встречаются, это абсолютно никак не коррелирует). И основные оптимизации - это, в первую очередь, всё-таки отимизация алгоритмов. Потому что как ни заменяй "тяжёлые" операции "лёгкими" в алгоритме n^2, он всё равно останется n^2.

А в чём здесь оптимизация, можно узнать?

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

[Hephaestus]

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

Я всё-таки подразумевал оптимизацию, позволяющую сэкономить время порядка секунды и более.
Когда я вынес за пределы цикла проверку условия с формулой, функция стала работать быстрее даже на глаз, то есть там высвободилось полсекунды или чуть больше на каждый вызов этой функции.
Несколько процессорных тактов (из Вашего примера) - это слишком мало в рамках десктопного приложения, инициализация переменной гораздо важнее, ИМХО.

[Bizdelnick]

Я всё-таки подразумевал оптимизацию, позволяющую сэкономить время порядка секунды и более.
Когда я вынес за пределы цикла проверку условия с формулой, функция стала работать быстрее даже на глаз, то есть там высвободилось полсекунды или чуть больше на каждый вызов этой функции.
Несколько процессорных тактов (из Вашего примера) - это слишком мало в рамках десктопного приложения, инициализация переменной гораздо важнее, ИМХО.

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

[Hephaestus]

Я говорил главным образом о Вашем примере с заменой деления/умножения на степени двойки битовым сдвигом.

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

Кстати, вот с этим

Потому что как ни заменяй "тяжёлые" операции "лёгкими" в алгоритме n^2, он всё равно останется n^2.

я не совсем согласен.
Есть рекомендации заменять возведение в степень умножением (в определенных ситуациях).

Кроме того, в языке просто может не быть оператора степени (тот же Pascal).
Припоминается случай, когда по условиям задачи студенту дана была сложная формула (в виде системы уравнений). В качестве языка предполагался Pascal (ну, кто бы сомневался).
Одним из условий было там было x^2.

Если решать задачу "в лоб" и просто закодить формулу как есть, то нужно делать возведение в степень.
Студент так и хотел сделать.
Но Pascal не имеет оператора возведения в степень.
Нужно либо сочинять свою функцию, либо использовать математическую библиотеку, где есть функция Power(x,y), возводящая x в степень y.
Однако если отбросить вариант "решение в лоб" и освободиться от "рамок формулы" (в том смысле, что не надо пытаться её воспроизвести дословно), то находится простое и очевидное решение: x^2==x*x.
Так неужели функция возведения в степень (не важно - своя или готовая) будет быстрее и экономнее оператора умножения? Не говоря уже о том, что для готовой функции целую библиотеку цеплять надо.
Это к разговору о том, что n^2 всегда останется n^2. Вот, не всегда. Далеко не всегда.

[azsx]

в теме Решено: обработка большого текстового файла (в тм числе там вы упоминали гарант всуе) рассматривался вариант как делать выборки из файла в 53 гб (1+ млрд строк).
В программе букварикс (только под виндой) реализован более оптимальный алгоритм выборки, который победил сразу все варианты сканов кеев. То есть они лучше не потому, что улучшили работу утилиты grep на несколько тактов за каждый проход, а потому, что изменили сам алгоритм выборок (я догадываюсь как, могу написать если любопытно). Таким образом они 0,5- млрд строк обрабатывают в реальном времени.
Вопрос, надо ли улучшать производительность grep? Ответ - неизвестно, так как утилита обрабатывает на максимуме для hdd винта (проц круче диска).
Вопрос, надо ли изменять алгоритмы на более производительные? Ответ - ДА!
----------------
может правильнее так. Мы живем в капиталистическом мире, где работникам платят за проделанную работу. Хозяину лавочки выгоднее получить от программиста абы как работающее решение завтра и моментально зарядить продукт на продажу. Менее выгодно получить более чем хорошее решение через неделю и начать продажи через неделю. Совершенно не выгодно получить хорошее и оптимизированное решение через месяц! Хозян сильнее работников.

[/dev/random]

Кстати, вот с этим

Потому что как ни заменяй "тяжёлые" операции "лёгкими" в алгоритме n^2, он всё равно останется n^2.

я не совсем согласен.
Есть рекомендации заменять возведение в степень умножением (в определенных ситуациях).

Bizdelnick имел в виду, что если алгоритм выполнялся за O(n²), то после замены операций на более лёгкие он всё равно будет выполняться за O(n²).

[Bizdelnick]

Ну, я думаю, вы согласитесь с тем, что битовый сдвиг всегда быстрее умножения/деления на степень двойки?

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

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

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

Код: Выделить всё

a = 0;

Код: Выделить всё

a = '\0';

и

Код: Выделить всё

a = NULL;

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

[Bizdelnick]

Мы живем в капиталистическом мире, где работникам платят за проделанную работу. Хозяину лавочки выгоднее получить от программиста абы как работающее решение завтра и моментально зарядить продукт на продажу. Менее выгодно получить более чем хорошее решение через неделю и начать продажи через неделю. Совершенно не выгодно получить хорошее и оптимизированное решение через месяц!

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

[azsx]

но и конторы, работающие по схеме "сделал и забыл", долго не живут.

типа майкрософт, совсем уже поплохело бедняжкам

[Bizdelnick]

типа майкрософт

Да нет, они таки допиливают свой софт (если не забрасывают его как бесперспективный). Сравните WinVista и Win7. Во многих случаях, правда, они ещё и добавляют реализацию новых офигительных идей (сравните Win7 и Win8), чем основательно портят впечатление.

[azsx]

Сравните WinVista и Win7

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

[drBatty]

Hephaestus
1. Без привязки к яп лучше НЕ менять умножение на сдвиг. К примеру, сложную формулу можно вычислить на аппаратных double, что и происходит на практике. Но сдвиг double не имеет смысла, а сл-но нужно много времени на перевод. Сдвиги нужны были в конце прошлого века, когда процессоры умели только целые, и компиляторы были тупые.
2. Указатели нужны только в крайнем случае, обычно это лишняя сущность.
3. Есть разное возведение в степень, если мы возводим в целую, это другая операция. Но она редко нужна, многочлены считают по схеме Горнера, без степеней.

[drBatty]

это не важно. Всё равно это зло. Время тратить нужно на оптимизацию алгоритма.

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

Вот и надо делать в общем виде. Если есть время и желание, можно сделать дополнительную реализацию под конкретный процессор. Вот только я вам совет дам: сравните скорость реализаций, в большинстве случаев 'общая' будет быстрее 'оптимизированной'. Компиляторы сейчас умные, и тривиальные оптимизации делают намного лучше вас, особенно учитывая вашу склонность к легендам и мифам из прошлого века.

[Hephaestus]

Bizdelnick имел в виду, что если алгоритм выполнялся за O(n^2), то после замены операций на более лёгкие он всё равно будет выполняться за O(n^2).

Боюсь, уважаемые собеседники, вы меня не поняли.
Алгоритм может выполняться за O(n^2), но если кодер не сообразил, что можно сделать x*x*x*x вместо x^4, да ещё не имея в арсенале возведения в степень, затолкал туда функцию, да ещё (не приведи, Кнут) самодельную, то в результате может получиться значительно больше, чем O(n^2).
Не надо решать "в лоб", не надо кодить, как Бог на душу положит, надеясь, что компилятор всё исправит.
Вот о чём я говорил.

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

Что касается сдвига вместо умножения/деления и пр., о чём я писал выше - это просто примеры, на что можно обратить внимание. Я нигде не говорил, что этим нужно непременно пользоваться.
Понятно, что решение принимается по ситуации, на то программеру и голова дана.

[Bizdelnick]

Не следует думать, что это мои фантазии.
Я сейчас с таким сталкиваюсь, разбирая чужой код, по роду своей деятельности.

Я тоже сталкиваюсь. И с другим сталкиваюсь тоже. Один пример: для сортировки списка по хитрому принципу использовалась конструкция из трёх вложенных циклов с двумя goto внутри, причём выход из внешнего цикла был возможен только по goto. Я не знаю, насколько эффективным был этот алгоритм, я просто не осилил разобраться, как он работал, и почему при некоторых условиях выхода из цикла не происходило, и программа зависала. Помедитировав над сим безобразием пару часов, плюнул и переписал этот кусок кода полностью. Возможно, с ущербом для эффективности, не знаю (хотя вряд ли, потому что вместо трёх вложенных циклов стало два). По крайней мере он теперь работает, и это главное. А кроме того, стало возможно понять, как он работает, глядя на код. Так нужно было делать с самого начала: написать простую и понятную реализацию, не особо думая о производительности. Её можно и потом оптимизировать.

[drBatty]

Боюсь, уважаемые собеседники, вы меня не поняли.
Алгоритм может выполняться за O(n^2), но если кодер не сообразил, что можно сделать x*x*x*x вместо x^4, да ещё не имея в арсенале возведения в степень, затолкал туда функцию, да ещё (не приведи, Кнут) самодельную, то в результате может получиться значительно больше, чем O(n^2).
Не надо решать "в лоб", не надо кодить, как Бог на душу положит, надеясь, что компилятор всё исправит.
Вот о чём я говорил.

Не следует думать, что это мои фантазии.

нет, это именно ваши фантазии. x*x*x*x менять ни на что не нужно, нужно думать об алгоритме, где такое встретилось. И помнить, что школьная математика — не совсем программирование, и даже совсем не программирование.

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

код в студию!

Что касается сдвига вместо умножения/деления и пр., о чём я писал выше - это просто примеры, на что можно обратить внимание. Я нигде не говорил, что этим нужно непременно пользоваться.

этим вообще не нужно пользоваться.

можно сделать x*x*x*x

PS: кстати, Кнут советовал перевести показатель степени в двоичную систему. Например 7я степень это

Код: Выделить всё

(x^2)^2 * x^2 * x

так самое быстрое.

И четвёртая будет быстрее не как x*x*x*x, а как

Код: Выделить всё

t=x*x;
y=t*t;

при этом компилятор выкидывает лишнюю переменную t.

[Hephaestus]

код в студию!

Код я наизусть не помню, буду на работе - опубликую.
Оно Вам надо?

Речь идёт о СУБД FoxPro, задача в данном случае - удалить из таблицы записи-дубли. При этом обрабатывается всего одно поле.

Изначально было примерно так:
Идём на первую запись.
Запоминаем номер и значение
Проходим по таблице вниз, ищем дубли.
Нашли - удаляем
Идём на вторую запись...
Ну и т.д.
Функция там получилась довольно длинная.

Я сделал проще:
Помечаем на удаление все записи
Строим униальный индекс
Снимаем пометку на удаление
Упаковываем.
Это буквально четыре команды, причем штатных - ни тебе функций, ни циклов, ни условий.

[drBatty]

Hephaestus
В данном конкретном случае вы изменили алгоритм, использовали встроенные средства СУБД. Мимо кассы, с тем же успехом вы могли-бы рассказать про замену совковой лопаты на штыковую. Я совершенно не понимаю вашей экстраполяции.

Зыж алсо первый алгоритм имеет сложность O(n*n), второй O(n*log(n)). Но второй требует O(n) памяти.

[Hephaestus]

Я совершенно не понимаю вашей экстраполяции.

Не понимаете - не надо. Мне это безразлично.

[drBatty]

Я совершенно не понимаю вашей экстраполяции.

Не понимаете - не надо. Мне это безразлично.

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