PD>В общем, могу согласиться, что какие-то правила, наверное, существуют. Плохо лишь то, что их толком сформулировать — получается плохо.
Правила ровно одни: мозг.
Синклер тебе открытым текстом написал про тот же С++:
PD>Именно. Зная структуру данных и алгоритм, сделаю вывод. Увижу массив и линейный цикл — сделаю вывод, что O(N).
Не угадал. Дальше что?
Увидел не массив, а некую структуру CCustomList. Увидел не цикл, а некий вызов типа std::sort(). Какой будет O()?
Так же и тут. Ты видишь не цикл, а работу каких-то структур. Что ты решил сделать? Выключить мозг и что-то орать с пеной у рта.
PD>Отсюда большой риск получить весьма (пусть не настолько, как в этом примере) неэффективный код. Если эти правила будут где-то внятно изложены, если любой учебник по LinQ будет их содержать, тогда, наверное, можно будет как-то иначе к этому относиться.
Эти правила изложены в любом учебнике по алгоритмам. В частности — в секции «как определить сложность алгоритма». Но да, тебе же всегда все очевидно!!
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Ну что же, все верно. Ошибку в укор тебе ставить не буду, конечно. Правда, тот факт, что ее никто не заметил , пока не было произведено сравнение с экспериментом, тоже кое о чем говорит...
Не надо выдавать желаемое за действительное!
... << RSDN@Home 1.2.0 alpha 5 rev. 43>>
Re[25]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>У меня нет ни малейшего желания занииматься разбором твоей софистики. Ты прекрасно понимал, что речь там шла отнюдь не о случаях доступа через operator[],а о прямой индексации в стиле С, в противном случае мы имеем вызов функции operator[] внутри цикла, а это надо учитывать, если ее реализация не O(1). Равно как и все остальное. Суть выводов это никак не меняет.
Ну конечно же меняет. Я на всякий случай напомню, что "прямая индексация в стиле С" выглядит в С++ ровно так же, как и вызов функции operator[]. Поэтому без анализа того, что там за a, и что там за i, и что там за sort никаких выводов делать нельзя.
Более того, современные компиляторы достаточно умны, чтобы в вырожденных случаях вообще выкинуть весь этот цикл из программы, если это не влияет на семантику.
Ну так вот во всех современных языках программирования ситуация обстоит ровно так же: нужно понимать, что именно происходит, чтобы давать хоть какие-то априорные оценки временных характеристик.
Даже в ассемблере у тебя нет никаких гарантий, что банальный add не вызовет пейджинг, который будет стоить тебе не 2 такта, а 3-15 миллисекунд.
Поэтому взрослые люди не рассуждают о том, "как не сделать ошибок", а пользуются профайлером.
После нескольких месяцев, проведённых с профайлером в руках, даже ты, Павел, сможешь навскидку определять узкие места в Linq — выражениях.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[32]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, MxMsk, Вы писали:
MM>Здравствуйте, netch80, Вы писали:
N>>Ну да. Постфактум уже что-то объяснили — после того, как я нашёл, что именно надо объяснить. MM>Лично у меня, как и у многих других, просто не было желания тратить время на дальнейшее разбирательство в коде. Знаешь почему? Потому что было очевидно, что Павлу этого не надо. Вот когда ты включился, тогда появилась заинтересованность.
Шорт побьери. Извини, но мне это тоже нужно (по крайней мере пока у меня нет никаких дел ни с дотнетом, ни с LINQ), так что категорически просю пардону за обманутые ожидания.
The God is real, unless declared integer.
Re[26]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, Sinclair, Вы писали:
S>Ну так вот во всех современных языках программирования ситуация обстоит ровно так же: нужно понимать, что именно происходит, чтобы давать хоть какие-то априорные оценки временных характеристик. S>Даже в ассемблере у тебя нет никаких гарантий, что банальный add не вызовет пейджинг, который будет стоить тебе не 2 такта, а 3-15 миллисекунд. S>Поэтому взрослые люди не рассуждают о том, "как не сделать ошибок", а пользуются профайлером.
Я согласен с Павлом — ты тут гонишь софистику.
Потому что независимо от пользы профайлера (она, конечно, есть) предсказание того, что конкретный алгоритм потребует кубических затрат, помогает понять, пригоден он тут или нет. Факторы типа пейджинга могут ухудшить производительность в таких случаях, но не улучшить.
S>После нескольких месяцев, проведённых с профайлером в руках, даже ты, Павел, сможешь навскидку определять узкие места в Linq — выражениях.
Этот опыт в результате формализуем словами? Если нет — то это несерьёзно, потому что мистика и магия. Если да — его можно формализовать и в этом был исходный вопрос ветки обсуждения.
The God is real, unless declared integer.
Re[27]: ответ на вопрос: Почему новые программы работают меделнно
S>>Ну так вот во всех современных языках программирования ситуация обстоит ровно так же: нужно понимать, что именно происходит, чтобы давать хоть какие-то априорные оценки временных характеристик. S>>Даже в ассемблере у тебя нет никаких гарантий, что банальный add не вызовет пейджинг, который будет стоить тебе не 2 такта, а 3-15 миллисекунд. S>>Поэтому взрослые люди не рассуждают о том, "как не сделать ошибок", а пользуются профайлером.
N>Я согласен с Павлом — ты тут гонишь софистику. N>Потому что независимо от пользы профайлера (она, конечно, есть) предсказание того, что конкретный алгоритм потребует кубических затрат, помогает понять, пригоден он тут или нет. Факторы типа пейджинга могут ухудшить производительность в таких случаях, но не улучшить.
Да нет там никакой софистики.
Дворкин утверждает: я завсегда смогу одним взглядом взглянув на алгоритм, сказать его сложность.
Sinclair: да нифига ты не можешь, если точно не знаешь, что именно участвуетв алгоритме. Даже на простейших алгоритмах может оказаться, что ВНЕЗАПНО a[i] — это не доступ по индексу, а имеет экспоненциальную сложность, и любая оценка алгоритма летит побоку.
Дворкин, естественно, не желает этого понять. Ты, видать, тоже
Аналогично для примера с LINQ'ом. Даже по грубым прикидкам алгоритм квадратичный. Для точной оценки надо разбираться во всех участвуемых в алгоритме структурах. А что, это когда-то было по-другому для других языков/технологий?
на C++. Ты можешь утверждать, что там — линейная сложность? Или какая-либо сложность? Нет, конечно. Но да, во всем виноваты «неформализуемые подходы оценки LINQ'а»
N> Этот опыт в результате формализуем словами?
Эти правила изложены в любом учебнике по алгоритмам. В частности — в секции «как определить сложность алгоритма».
Ops>>Точно, думать не нужно, главное клепать. Это случайно не твою программу для UPS на 800М недавно обсуждали? MM>Прикольно, что ты не отвечаешь за свои слова, да еще и размениваешься на такие беспонтовые уколы, пытаясь навесить на меня чужие ошибки.
Я не отвечаю за свои слова? Можно ссылку или цитату? Насчет уколов — извиняюсь, буду молча сносить. MM>Позиционируешь себя знатоком, а в итоге демонстрируешь неумение прочитать текст и углубиться в суть решений, принятых в менеджед языках.
Вообще-то текст я прочитал, но пока вижу преимущества иммутабельных строк в основном в защите от дурака, ленящегося писать const. MM>Только детсадовские каменты про клепание и неумение думать, выдающие лишь отсутствие каких либо весомых аргументов.
Как в том посте, на который я отвечал?
Переубедить Вас, к сожалению, мне не удастся, поэтому сразу перейду к оскорблениям.
Re[28]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, Mamut, Вы писали:
M>Да нет там никакой софистики. M>Дворкин утверждает: я завсегда смогу одним взглядом взглянув на алгоритм, сказать его сложность. M>Sinclair: да нифига ты не можешь, если точно не знаешь, что именно участвуетв алгоритме. Даже на простейших алгоритмах может оказаться, что ВНЕЗАПНО a[i] — это не доступ по индексу, а имеет экспоненциальную сложность, и любая оценка алгоритма летит побоку.
Ну да. А завтра туда свалится метеорит, и оно вообще перестанет работать.
Вы оба начали придумывать какие-то совершенно мифические ситуации, которые при нормальном проектировании не работают. В частности, если мы говорим о массиве, и нет безумной давки в памяти, то доступ к элементу массива как a[i] имеет сложность O(1). И оценки алгоритма должны исходить именно из этого: в пределах условий его применимости оценки, полученные на основании анализа алгоритма, должны быть адекватны тому, что происходит в реальности.
И применяемые средства должны быть такими, чтобы не было проблем по коду сделать анализ оценки затрат.
M>Дворкин, естественно, не желает этого понять. Ты, видать, тоже
Я могу понять, что кто-то работает в совершенно ненормальных условиях или ненормально использует имеющиеся средства. Например, для какой-нибудь сортировки в стиле qsort это тривиально получить, пытаясь просортировать в памяти объём данных, больший, чем объём оперативной памяти — вот тут начинается жесточайший пейджинг-своппинг и время растёт в тысячи раз. Но оценка такого будет уже не оценкой сложности алгоритма, а комплексной оценкой эффективности решения, что совсем другое. И вот вы путаете эти две оценки.
M>Возбмем абсолютно аналогичный код
на C++. Ты можешь утверждать, что там — линейная сложность? Или какая-либо сложность? Нет, конечно. Но да, во всем виноваты «неформализуемые подходы оценки LINQ'а»
Я не знаю такой C++, извини. Приведи код на Python, Erlang или C, тогда я тебе расскажу про него.
N>> Этот опыт в результате формализуем словами?
M>
M>Эти правила изложены в любом учебнике по алгоритмам. В частности — в секции «как определить сложность алгоритма».
Эти правила из учебника надо проецировать на конкретные особенности реализации (или наоборот, кого на что). И я говорю именно о правилах такого проецирования, а не об азах из учебника. Для обычного императивного языка они известны. Для LINQ их надо описывать заново, и Павлу непонятно, как это делать и на основании чего.
The God is real, unless declared integer.
Re[29]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, netch80, Вы писали:
N>Здравствуйте, Mamut, Вы писали:
M>>Да нет там никакой софистики. M>>Дворкин утверждает: я завсегда смогу одним взглядом взглянув на алгоритм, сказать его сложность. M>>Sinclair: да нифига ты не можешь, если точно не знаешь, что именно участвуетв алгоритме. Даже на простейших алгоритмах может оказаться, что ВНЕЗАПНО a[i] — это не доступ по индексу, а имеет экспоненциальную сложность, и любая оценка алгоритма летит побоку.
N>Ну да. А завтра туда свалится метеорит, и оно вообще перестанет работать. N>Вы оба начали придумывать какие-то совершенно мифические ситуации, которые при нормальном проектировании не работают.
Не мы оба, а Дворкин, который поступил ваккурат с заветом Икемефулы: нести знамя шуточного кода как доказательство чего-то там на протяжении двух лет.
N>В частности, если мы говорим о массиве, и нет безумной давки в памяти, то доступ к элементу массива как a[i] имеет сложность O(1). И оценки алгоритма должны исходить именно из этого: в пределах условий его применимости оценки, полученные на основании анализа алгоритма, должны быть адекватны тому, что происходит в реальности. N>И применяемые средства должны быть такими, чтобы не было проблем по коду сделать анализ оценки затрат.
Кто-то хоть слово говорит против этого? Цитаты, ссылки в студию. Более того, практически сразу про этот код было сказано: никто так не будет извращаться для написания суммы элементов в массиве.
M>>Дворкин, естественно, не желает этого понять. Ты, видать, тоже
N>Я могу понять, что кто-то работает в совершенно ненормальных условиях или ненормально использует имеющиеся средства. Например, для какой-нибудь сортировки в стиле qsort это тривиально получить, пытаясь просортировать в памяти объём данных, больший, чем объём оперативной памяти — вот тут начинается жесточайший пейджинг-своппинг и время растёт в тысячи раз. Но оценка такого будет уже не оценкой сложности алгоритма, а комплексной оценкой эффективности решения, что совсем другое. И вот вы путаете эти две оценки.
на C++. Ты можешь утверждать, что там — линейная сложность? Или какая-либо сложность? Нет, конечно. Но да, во всем виноваты «неформализуемые подходы оценки LINQ'а»
N>Я не знаю такой C++, извини. Приведи код на Python, Erlang или C, тогда я тебе расскажу про него.
Обыкновенный C++ Только ВНЕЗАПНО для него уже нельзя так просто, с наскока, оценить сложность
N>>> Этот опыт в результате формализуем словами?
M>>
M>>Эти правила изложены в любом учебнике по алгоритмам. В частности — в секции «как определить сложность алгоритма».
N>Эти правила из учебника надо проецировать на конкретные особенности реализации (или наоборот, кого на что). И я говорю именно о правилах такого проецирования, а не об азах из учебника. Для обычного императивного языка они известны. Для LINQ их надо описывать заново, и Павлу непонятно, как это делать и на основании чего.
На основании мозга.
Дворкин утверждает, например:
Я и не утверждаю, что с линком нельзя написать более или менее эффективно. Но вот без него написать столь неэффективно попросту нельзя.
Нужны какие-то правила, какие-то основания, чтобы эту голову применить. Для императивного кода они довольно просты — определите зависимость t=O(N) для вашего кода и подумайте, нельзя ли найти алгоритм с лучшей зависимостью. quicksort vs. bubble и т.д.
А здесь каким правилам следовать ?
Абсолютно тем же правилам, что и при разборе сложности императивного кода, что до Дворкина и до тебя, видать, пытается донести Синклер. LINQ — это не какие-то новые магические алгоритмы, неизвестно, откуда взявшиеся. Это все те же алгоритмы, можно вон книжку Кормана взять почитать, если что
оценка времени даже линейного цикла базируется на некотором знании о том, как этот цикл реализуется компилятором. То же самое и с Linq. Чтобы оценить сложность, нужно понимать, во что компилируются соответствующие методы. Как правило, имеем те же O(N). Более высокая сложность может получиться при наличии вложенных вызовов. В сущности, те же самые правила
Когда я вижу for(int i = 0; i < N; i++) я понимаю, во что это выльется, причем даже не обязан знать ассемблер. Тут как ни компилируй, а хуже O(N) быть не может. Как же мне определить , вот что выльется вызов Linq ?
Против чего Синклер уже сказал, что что-то уверждать даже для простейших циклах можно лишь для простейших случаев. Как только ты заменяешь простой доступ по индексу в массиве на какую-то собственную структуру данных, все твои размышления об алгоритме летят в трубу. Не так ли? И уже надо изучать, что делает та самая структура, не? Иначе якобы O(N) выльется в O(N^2) на ровном месте.
Так почему же ни Дворкин ни ты не собираетесь использовать такой же подход к Linq'у? Ведь видно же, что используются структуры, сложнее, чем банальный for. Берешь, читаешь гугл на предмет этих структур и делаешь разумные предположения.
Что именно тебе формализовать? Кормана? Необходимость использовать мозг? Необходимость исследования поведения структур на предмет их поведения? Что именно?
Здравствуйте, Ops, Вы писали:
Ops>>>Точно, думать не нужно, главное клепать. Это случайно не твою программу для UPS на 800М недавно обсуждали? MM>>Прикольно, что ты не отвечаешь за свои слова, да еще и размениваешься на такие беспонтовые уколы, пытаясь навесить на меня чужие ошибки. Ops>Я не отвечаю за свои слова? Можно ссылку или цитату? Насчет уколов — извиняюсь, буду молча сносить.
Какая тебе нужна ссылка? Ты посмотри на разговор. Вбрасываешь одно за другим, тебе объясняют, почему это неверно, но ты признать этого не можешь, а продолжаешь набрасывать. Потому и не отвечаешь. Ляпнул и забыл.
MM>>Позиционируешь себя знатоком, а в итоге демонстрируешь неумение прочитать текст и углубиться в суть решений, принятых в менеджед языках. Ops>Вообще-то текст я прочитал, но пока вижу преимущества иммутабельных строк в основном в защите от дурака, ленящегося писать const.
Ну правильно. Чего писать, что лажаешь, проще обозвать других дураками. На всякий случай, гений, при желании никто не запрещает тебе в managed использовать мутабельные строки. Взял StringBuilder и вперед — меняй сколько влезет.
Re[29]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, netch80, Вы писали:
N>Эти правила из учебника надо проецировать на конкретные особенности реализации (или наоборот, кого на что). И я говорю именно о правилах такого проецирования, а не об азах из учебника. Для обычного императивного языка они известны. Для LINQ их надо описывать заново, и Павлу непонятно, как это делать и на основании чего.
А знаешь, что интересно: Linq — это ведь имитация ФП. Linq — это императивный код, написанный на императивном C#. Так вот и получается, что оценка Linq — это оценка сложности императивного кода, и Павел должен был сам показать класс, а не ждать этого от других. Впрочем, весь этот спор очень типичен. Сначала, засчет шуточного примера, был создан мир, в котором Linq отстой, а потом было предложено доказать, что он не отстой. Жалею, что повелся на это в очередной раз.
Re[19]: ответ на вопрос: Почему новые программы работают мед
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Возможно, ты и прав, но все эти отличия примерно те же, что и для ранней версии С++ (BC++ 2.0) vs версии времен BC++5.0.
Как минимум перегрузки сильно усложняют компилятор, а никаких изменений в этом плане между 2 и 5 версие борладовского С++ не было.
Re[10]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, Ops, Вы писали:
Ops>Вообще-то текст я прочитал, но пока вижу преимущества иммутабельных строк в основном в защите от дурака, ленящегося писать const.
У мутабельных строк есть огромное преимущество — их гораздо реже приходится копировать, и не надо синхронизовывать многопоточный доступ.
Дурак с const тут ни при чём — семантика const в принципе не позволяет выразить иммутабельность.
Простейшая штука — метод, получивший строку в начале исполнения, и выполнивший с ней некоторую проверку, хочет полагаться на то, что результат проверки не изменится. Никакими const этого добиться нельзя; придётся делать копию (которая скорее всего не нужна). Иммутабельную строку можно использовать в качестве ключа в коллекциях. Мутабельную — нельзя. И это только верхушка айсберга.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[11]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, Sinclair, Вы писали:
S>У иммутабельных строк есть огромное преимущество — их гораздо реже приходится копировать, и не надо синхронизовывать многопоточный доступ.
Очепятка.
Re: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, newCL, Вы писали:
CL>И так повсюду: везде и всюду такты и байты расходуются ниначто, т.е. выделяется память там, где её выделять не нужно, и делается то, что делать не нужно.
чушь это все. такты и байты расходуются ниначто там, где пользователь этого незаметит. А в критичных моментах берется в руки профайлер, и все подобные вещи вычищаются.
Re[4]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, Ночной Смотрящий, Вы писали:
НС>Здравствуйте, newCL, Вы писали:
CL>>Это всё равно глупо, т.к. в большинстве случаев байты получают для скармливания алгоритмам хэширования/криптования или отправляются по сети, или в файл пишутся
НС>Переключаешься в unsafe и вперед, если уверен что получишь существенный выигрышь в перформансе.
In order for C# to compile unsafe code, the application must be compiled with /unsafe
Зарубят сразу — корпоративный код никто так компилировать не захочет.
Мне в своё время пришлось доказывать необходимость использования PInvoke.
Всё сказанное выше — личное мнение, если не указано обратное.
Re: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, hattab, Вы писали:
PD>Возможно, ты и прав, но все эти отличия примерно те же, что и для ранней версии С++ (BC++ 2.0) vs версии времен BC++5.0.
Не помню 2-й BC++, но даже во времена 5-го такого количества шаблонов, как сейчас, не было. Интересно, 5-й хотя бы одну библиотеку из буста скомпилирует?
Переубедить Вас, к сожалению, мне не удастся, поэтому сразу перейду к оскорблениям.
Re[5]: ответ на вопрос: Почему новые программы работают меделнно
