Здравствуйте, Evgeny.Panasyuk, Вы писали:
V>>Линейный он лишь для случая одновременного поиска и сдвига элементов массива. V>>В этом случае он представляет из себя разновидность пузырьковой сортировки. EP>Это не разновидность пузырьковой сортировки.
Извини, но сравнение и обмен строго с соседним элементом — это характеристика сортировок из семейства пузырьковой.
Не помнишь, почему сортировка названа "пузырьковой"?
Блин, да я когда-то лабы делал по разным модификациям пузырьковых сортировок, а тут некоторые утверждают, что она только одна. ))
Аналогично по сортировкам слиянием — мы их штук пять-шесть проходили (если склероз не изменяет). А на визуализации я вижу лишь один из вариантов.
V>>Если же сначала найти необходимую позицию, а затем сдвинуть все необходимые элементы за раз, то так может оказаться эффективней. EP>Может, не спорю что есть вариант с двоичным поиском, и что у него есть область применения. Я говорю что обычно он линейный.
"Обычно" — это из-за std::sort, что ле? ))
Там, как раз, всё очень необычно, а весьма специфично для специфичного этапа сортировки.
V>>В std::sort идет линейный поиск по той причине, которую уже многократно обсуждали на этом сайте — до, примерно, 16-ти элементов на современных процессорах выгодней искать элемент линейно, а не двоичным поиском. EP>В том числе и по этой причине.
На самом деле только по этой причине.
Как раз для поиска в маленьких массивах использование линейного поиска — обычно.
EP>Там вообще говоря swap использовать не выгодно — там нет необходимости менять каждый соседний элемент между собой. Оптимальнее переместить текущий элемент в temp, все остальные переместить вправо, а потом переместить temp в левый край. Это операция ЕМНИП rotate_by_one.
Об этом и речь, чтобы не производить на каждом шаге сравнение с перестановкой. Но искать-то выгодней двоично, а не линейно, для массива из более 16-ти элементов на современных машинах!
V>>Похоже, что в тех реализациях, что ты представляешь — пузырьковая сортировка отработает N! (факториал) раз независимо от исходных данных. )) EP>Очень смешно. Пузырьковая сортировка квадратична в худщем случае.
Вот как раз не смешно. Самый простой вариант пузырьковой сортировки отрабатывает фиксированное кол-во раз, независимо от содержимого массива:
for(int end = size - 1, end > 0, end--)
for(int i = 0; i < end; i++)
swap_if_needed(array[i], array[i+1]);
Чуть меньше, чем квадратичная, не?
Я же тебе намекаю уже многократно, что пузырьковая сортировка — это целое семейство алгоритмов.
EP>>>Покажи реализацию без лишнего прохода, или хотя бы дай ссылку на код. V>>Стандартная и есть без лишнего прохода. EP>Код в студию, иначе наш спор не разрешится.
В западной литературе шейкерную выделяют в отдельный вид сортировки, нам же её давали как разновидность пузырьковой.
Более того, самих разновидностей шейкерной как минимум три. Визуализация шейкерной сортировки на видео — самая неэффективная, ы-ы-ы.
В одной из разновидностей шейкерной запоминают последнее место обмена, при движении вперед это будет верхняя граница, при движении назад аналогично обнаруживается нижняя граница. Т.е. сужение диапазона на каждом проходе будет происходить не на 1 элемент (как на видео), а до фактического места последнего обмена.
В еще одной разновидности шейкерной можно запоминать не только последнее место обмена, но и первое, храня информацию о границах отсортированных областей по краям массива (отсортированным не в том смысле, что элементы на своих местах уже, а в том смысле, что они упорядочены в пределах своей области).
Код тривиальный, но длинный, открывать студию и писать не буду. ))
Вербально как-то так:
1. движение вперед от нижней до верхней границы неотсортированной области, поиск первой пары для обмена, запоминание нижней границы отсортированного диапазона (минус одна позиция от текущей); если обмена не было — выход.
2. продолжаем движение вперед, обмен при необходимости, запоминание верхней границы отсортированного диапазона.
3. сравнение с первым элементом из отсортированной области, при необходимости продолжаем "всплытие" (в любом случае, запомненная на предыдущем шаге граница не изменяется).
4. движение назад аналогично, потом goto 1.
На каждом шаге у нас "всплывает" максимальный (или "тонет" минимальный) элемент из неотсортированной области к её краю, т.е. применяется обычный пузырёк; на границе отсортированной области алгоритм меняется — мы движемся лишь до тех пор, пока необходим обмен.
Здравствуйте, Serginio1, Вы писали:
_>>Сайты удобнее делать на скриптовых языках. А что такое "учетные системе массовых задач"?. S> Учетные системы ERP это ERP Microsoft Dynamics,SAP, Oracle E-Business Suite ну и конечно 1С.
Я в курсе что такое ERP (их кстати намного больше, причём как наших закрытых, так и иностранных opensource). Просто не думал, что это можно так расшифровать на русский. )))
S>По поводу сайтов, то Asp.Net MVC очень востребована. Мало того сейчас серверная часть больше похожа на HTTP сервис, где выдается начальная страница, а с клиента через AJAX данные подгружаются ввиде Json и вся работа по построению DOM лежит на клиенте с помощью AJAX и JS библиотек
1. Раз всё делается на JS, то тогда причём тут собственно .net?
2. Такая схема уже много лет как используется во всех остальных языках. Например у нас сайты работают именно так, только на сервере при этом отвечает на ajax запросы Питон (и без всякого asp естественно).
_>>Да, всё верно. Именно из-за этого факта и существуют такие вещи как Java/C#. И как раз сейчас в связи со стагнацией в росте производительности процессоров, ростом мобильного рынка (где вообще печаль с производительностью) и начинающейся модой на "интернет вещей" (а туда вообще даже сами платформы jvm/clr не лезут по нормальному, не говоря уже о какой-то производительности) в этом вопрос возможны существенные корректировки. S> Ну сейчас идут по пути распараллеливания кода. Кстати многие сортировки можно распараллелить.
Распараллеливание может быть актуально (собственно только в этом направление и есть прогресс в последнее время) для серверных решений. А для всего остального, из выше перечисленного, это абсолютно не актуально.
S> Вот посмотри мои разработки http://infostart.ru/profile/82159/public/ S>Большинство сделаны для связи 1С с внешним миров и со связью из внешнего мира с 1С. Я ими активно пользуюсь. И посмтори сколько комментариев и какие. S>Народ просто не понимает о чем речь. И вместо использования готовых компонентов для хэширования использует побитовые операции на 1C. S>http://forum.infostart.ru/forum86/topic136695/ S>http://infostart.ru/public/99739/ А ты говоришь про скорость
Скорость безусловно нужна. На своём уровне. В данном случае она нужна в языке, на котором написана сама платформа 1C (надеюсь ты в курсе, на чём она написана?). Ситуация полностью аналогичная раскладу браузер (все написаны на C++) и JS в нём. Ну точнее аналогично ситуации с браузерами 15 летней давности — с тех пор JS оптимизировался, обзавёлся JIT'ом и почти догнал по скорости C#/Java. Интересно, а в 1C не планируют такого же? )
S>Народ в большинстве случаев варится в своем тесном мирке. Разработка SQL серверов и Вэб серверов весьма нетривиальная задача, которая для среднестатистического программиста далека как Марс от Земли.
SQL сервер действительно не простая вещь (если конечно хочется нормального быстродействия), хотя вполне подъёмная. Только вот даже если заняться таким, то будут очень сомнительны перспективы выхода на рынок. А вот например NoSQL решения (которые во многих случаях совсем не проще) появляются вокруг как грибы. Как раз потому, что данный рынок ещё только формируется.
Что же касается http-серверов, то это достаточно тривиальная вещь, которую частенько реализуют заново в разных проектах. Более того, есть множество гораздо более сложных вещей, которыми заняты "среднестатистические программисты". К примеру любая современная онлайновая игрушка на порядок сложнее.
Да, кстати, а авторы того же 1C — они значит с Марса всё же? )))
Здравствуйте, Ikemefula, Вы писали:
PM>>В заголовок новости не поместилась информация о том, что они: PM>>
PM>> оптимизировали работу с памятью (а память по факту уже давно является многоуровневой системой кэшей) PM>> запустили user-space TCP/IP стек для определенного вида сетевых карт PM>> и пока не полностью реализовали все функции PM>>PM>>У меня есть сомнения, что первые 2 пункта легко реализуемы в управляемых средах (не знаю, добавили ли уже в Java value types)
I>То есть, язык ни при чём. Чтд.
Буквы не читай, сообщения пиши. Или я что-то пропустил и языки Java/C# умеют работать без JVM/CLR
Почитайте на досуге как авторы LMAX героически боролись (и вроде бы продолжают бороться) с JVM — пытаясь выровнять данные по границе кэш-линии; как затюнинговать сборку мусора, чтобы система не замерзала в неподходящий момент (и перезапускать всё разв в сутки в конечном итоге)
Короче, сплошной <троллейбус из буханки хлеба.jpeg>
Здравствуйте, alex_public, Вы писали:
_>Здравствуйте, Serginio1, Вы писали:
_>>>Сайты удобнее делать на скриптовых языках. А что такое "учетные системе массовых задач"?. S>> Учетные системы ERP это ERP Microsoft Dynamics,SAP, Oracle E-Business Suite ну и конечно 1С.
_>Я в курсе что такое ERP (их кстати намного больше, причём как наших закрытых, так и иностранных opensource). Просто не думал, что это можно так расшифровать на русский. )))
S>>По поводу сайтов, то Asp.Net MVC очень востребована. Мало того сейчас серверная часть больше похожа на HTTP сервис, где выдается начальная страница, а с клиента через AJAX данные подгружаются ввиде Json и вся работа по построению DOM лежит на клиенте с помощью AJAX и JS библиотек
_>1. Раз всё делается на JS, то тогда причём тут собственно .net?
Ну например есть TypeScript. Да и серверную часть тоже нужно писать на Asp.Net mvs писать запросы к базе итд. Клиентская часть далеко не все.
_>2. Такая схема уже много лет как используется во всех остальных языках. Например у нас сайты работают именно так, только на сервере при этом отвечает на ajax запросы Питон (и без всякого asp естественно).
А где же высокоскоростной C++?
_>>>Да, всё верно. Именно из-за этого факта и существуют такие вещи как Java/C#. И как раз сейчас в связи со стагнацией в росте производительности процессоров, ростом мобильного рынка (где вообще печаль с производительностью) и начинающейся модой на "интернет вещей" (а туда вообще даже сами платформы jvm/clr не лезут по нормальному, не говоря уже о какой-то производительности) в этом вопрос возможны существенные корректировки. S>> Ну сейчас идут по пути распараллеливания кода. Кстати многие сортировки можно распараллелить.
_>Распараллеливание может быть актуально (собственно только в этом направление и есть прогресс в последнее время) для серверных решений. А для всего остального, из выше перечисленного, это абсолютно не актуально.
Ну почему. Сейчас все пишется через await, Ajax ы. Это конечно не System.Threading.Tasks.Parallel но ассинхронные вычисления.
Но мы то говаорим о вытеснении C++ более медленных платформ.
S>> Вот посмотри мои разработки http://infostart.ru/profile/82159/public/ S>>Большинство сделаны для связи 1С с внешним миров и со связью из внешнего мира с 1С. Я ими активно пользуюсь. И посмтори сколько комментариев и какие. S>>Народ просто не понимает о чем речь. И вместо использования готовых компонентов для хэширования использует побитовые операции на 1C. S>>http://forum.infostart.ru/forum86/topic136695/ S>>http://infostart.ru/public/99739/ А ты говоришь про скорость
_>Скорость безусловно нужна. На своём уровне. В данном случае она нужна в языке, на котором написана сама платформа 1C (надеюсь ты в курсе, на чём она написана?). Ситуация полностью аналогичная раскладу браузер (все написаны на C++) и JS в нём. Ну точнее аналогично ситуации с браузерами 15 летней давности — с тех пор JS оптимизировался, обзавёлся JIT'ом и почти догнал по скорости C#/Java. Интересно, а в 1C не планируют такого же? )
Да какая разница на чем написана сама платформа, а то с какой скоростью работает интерпретатор. До сих пор основная часть нагрузки идет на сервере.
Например в свое время при работе в терминалах очень тормозила печать при слабой связи. На толстом клиенте сделал связь по Tcp/IP и передавал данные по которым уже строил печатные формы. Трафик сократился в тысячи раз. Но пока 1С в управляемых формах формирует печатную форму на сервере.
Там даже не ввели замыканий http://its.1c.ru/docs/v8nonmodal/
S>>Народ в большинстве случаев варится в своем тесном мирке. Разработка SQL серверов и Вэб серверов весьма нетривиальная задача, которая для среднестатистического программиста далека как Марс от Земли.
_>SQL сервер действительно не простая вещь (если конечно хочется нормального быстродействия), хотя вполне подъёмная. Только вот даже если заняться таким, то будут очень сомнительны перспективы выхода на рынок. А вот например NoSQL решения (которые во многих случаях совсем не проще) появляются вокруг как грибы. Как раз потому, что данный рынок ещё только формируется.
_>Что же касается http-серверов, то это достаточно тривиальная вещь, которую частенько реализуют заново в разных проектах. Более того, есть множество гораздо более сложных вещей, которыми заняты "среднестатистические программисты". К примеру любая современная онлайновая игрушка на порядок сложнее.
Ты путаешь сервисы с серверами. Мы говорим об IIS, апаче https://ru.wikipedia.org/wiki/%D0%A1%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2%D0%B5%D0%B1-%D1%81%D0%B5%D1%80%D0%B2%D0%B5%D1%80%D0%BE%D0%B2
_>Да, кстати, а авторы того же 1C — они значит с Марса всё же? )))
Они отличаются от среднестатистических программистов. Еще раз повторю, что есть рынок на котором требуются решения задач.
Есть рынок средств и программистов с разной квалификацией итд. И побеждает тот кто предлагает лучшее по критерию цена качество время
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Здравствуйте, Serginio1, Вы писали:
EP>>>>>>>А причём востребованность? S>>>>>> При том, что пишут на тех языках на которых удобнее и нужна меньшая квалификация, EP>>>>>Пишут что? В каких случаях? Удобнее для чего? S>>>> Удобнее для написания сайтов, учетных систем массовых задач. EP>>>И? Это единственные существующие задачи? S>> Такими задачами занимаются большинство программистов.
EP>ОК, дальше-то какой вывод?
Вывод ниже. Есть рынок задач и средств их выполнения. Побеждают те которые могут предложить лучшее соотношение цена качество время
S>>>> Еще раз повторю формулу экономической целесообразности S>>>>(стоимость разработки) + (стоимость железа) для достижения одинаковой вычислительной мощности EP>>>ОК, повторил, что ты этим хочешь сказать? (причем это одна из возможных формул, а не единственная) EP>>>Да, целесообразность тоже нужно учитывать, с этим не спорю — кроме этого ты что-то ещё подразумевал? S>> К тому, что нужны специалисты со снанием конкретного языка.
EP>Когда как. Бывает заказчику всё равно какой там язык, главное результат.
Еще раз соотношение цена качество время
S>>Какова доля программистов С++ в программистском мире?
EP>Не знаю, но уж точно не маленькая. И не только из-за его скорости или других удобств, например у него самый широкий из mainstream охват по платформам, и например есть ещё и legacy.
Традиционно в авангарде — Java-разработчики, последние 5-6 лет это была самая востребованная категория ИТ-специалистов, также как и программисты на С++/C#: в количественном отношении рынок нуждается в них более всего.
При этом в последние годы самыми высокооплачиваемыми программистами были мобильные разработчики: средний уровень их зарплат рос гораздо быстрее, чем у других категорий. Но итоги 2014 года показывают, что в этом сегменте рынка труда в ИТ-сфере наметились перемены, и существенные. Он остывает, кадровый дефицит в сфере мобильной разработки во многом преодолен, и темпы роста зарплат пошли на снижение.
Более всего на рынке разработки ценятся Java-девелоперы. Средний уровень их зарплаты составляет 95 500 рублей, а выросли они за год примерно на 26%. Второе место по уровню дохода занимают Android-разработчики, но самые «хлебные» времена для этой категории программистов миновали. Рост зарплат здесь невелик – всего 12% в год. Еще хуже перспективы у разработчиков приложений для iOS. Их средняя зарплата составляет 80500 рублей, и выросла она за год всего на 6%.
Относительно спокойны могут быть девелоперы, которые специализируются на C# и С++. Первые получают в среднем 82000 рублей, при этом рост зарплат в прошлом году составил 24%. Вторые «стоят» дешевле, 80000 рублей, а уровень их дохода подрос на 18%.
По данным Superjob.ru, наиболее востребованными в 2012 году были разработчики, особенно — опытные (JAVA). Так же в 2012 году среди разработчиков были востребованы веб разработчики C#, PHP. Второе место по востребованности на рынке труда продолжают занимать специалисты службы поддержки. Третье место по праву занимают тестировщики.
В 2013 году аналитики прогнозировали рост спроса на ИТ-специалистов на фоне умеренного увеличения численности соискателей, сохранение дефицита программистов и разработчиков. Причем самыми востребованными программистами остаются специалисты, пишущие на «1С» и PHP. Также на рынке ИТ-кадров ожидался опережающий другие рынки рост зарплатных предложений.
S>>А задач таких полно. И нужна скорость решения, а не скорость выполнения.
EP>С этим никто не спорил, и в общем-то это очевидные вещи.
S>>У меня куча отчетов где скорость новых быстрее раз в 10. S>>Но например этот отчет бухгалтер делает раз в месяц. И он может подождать даже пол часа, занимаясь другой работой.
EP>Бывают и такие варианты. EP>А бывают и другие, например бухгалтер генерирует отчёт, потом проверяет его, исправляет ошибки, и опять запускает — и так может быть несколько раз. EP>Или например инженер делает расчёт, ждать результата он может долго скажем день, но при этом бОльшая доступная вычислительная мощность переходит в качество — он может сделать более густую расчётную сетку, произвести большее количество нелинейных расчётов и т.д. и т.п.
Ты меня не читаешь. Я говорю, что ускоряю скорость отчетов в 100 раз. Все довольны, но иногда прихожу к буху и спрашиваю каким отчетом пользутесь, а они говоря, что по привычке старым. При этом это не доли секунд, а пол часа.
S>>Иногда нужно быстро решить задачу, а сколько она будет выполняться не имеет значения.
EP>Расшифруй.
Есть задача и её решить нужно еще вчера. Берешь и решаешь задачу без оглядки на выбор более оптимальных алгоритмов, языков. Нужна скорость разработки. S>> поскипано. Это все понятно. Я не стал выводить выкладки. Понятно, что факторов очень много.
EP>Много, и тормоза отнюдь не двукратные.
Правильно, значительно меньше при правильном написании алгоритма. Все твои примеры это выбор самого плохого подбора алгоритма.
S>>Кстати по поводу использования структур. S>>http://rsdn.ru/forum/dotnet/415352.1
Смысл в том, что если прошла сборка мусора, то джит собирает 0 поколения, а старые поколения если ссылки на них не менялись не трогает. А вот для если они менялись, то он их помечает и в итоге происходят тормоза. Поэтому Хэш таблицы например сделаны на массиве структур. Но при этом и сборщики мусора совершенствуются
EP>А я вообще забыл упомянуть тормоза от GC, это отдельная тема. Тормоза для pointer semantics style есть даже без учёта бОльшей нагрузки на GC. EP>И если активно использовать pointer semantics в C++ — то и там появятся точно такие же тормоза как и в Java/C#/etc: пример
— заменили плотно упакованные элементы, на структуру ссылочного вида — в результате разница по скорости 208.6x, и это без учёта работы менеджера памяти. EP>Но в C++ default это value semantics, и там его намного легче использовать чем в языках заточенных под pointer semantics.
Тормоза от GC зависят от задач. В большинстве случаев сбор мусора, это просто сдвиг указателя конца кучи на начало.
Не все так однозначно. S>>Это EP>>>>>Во-первых, это всего лишь один вариант целесообразности. Например железо может быть уже на миллионах устройств клиентов — и вместо покупки нового девайса, они пойдут к конкурентам, софт которых работает на текущем железе, пусть и стоимость его разработки была выше. S>> Или если таких приложений будет 1-2 он уйдет к тем у кого 1000-100000.
EP>Не понял этого тезиса.
Да в том, что нужна скорость разработки и количество специалистов которые могут решить эти задачи. Если таких специалистов оочень мало, то будут побеждать те языки где сложность входа значительно меньше. Как ты думаешь, что проще для изучения 1С++ или 1С?
S>>Везде нужна экономическая целесообразность. Поэтому и существуют С++,С# и 1С.
EP>Нужна, я этого не отрицал.
S>>>>В реальных приложениях занятость процессора очень далека до 100%. Большинство время уходит на ожидание запроса к SQL, HTTP запроса, итд. EP>>>Старая шарманка "всё в базу упираются" EP>>>У меня в продукте вообще нет никакой никакого SQL и никаких HTTP, не надо проецировать какие-то свои личные задачи на всех, и делать далеко идущие выводы S>> И какова занятость процессора в твоих приложениях?
EP>Это надо у клиентов спросить, так как это библиотека EP>А вообще не понятно к чему вопрос про занятость, даже если он в среднем занят на доли процента, это не делает не нужным быстрое железо, и быстрый софт. EP>Например женщина в среднем вынашивает ребёнка в течении скажем 2% от продолжительности своей жизни, размазать этот процент по всем годам никак не получится, и она не сможет родить ребёнка через день после зачатия
Они нужны. Но у них своя ниша.
S>>>>Заметь, что в браузерах победил JS. Опять же какая разница для пользователя в ожидании 0.1 или 0.2 секунды. EP>>>ASM.JS достаточно быстрый. Я даже выше приводил ссылку. C++ скомпилированный в ASM.JS обогнал C# в своей родной среде практически в два раза EP>>>JavaScript, в веб-браузере, Карл! S>> В итоге все зависит от компилятора. Например TS тоже транслируется в JS и ничто не мешает транслировать в более оптимальный. Здесь проблема не языков а компиляторов которые совершенствуются.
EP>Как раз таки проблема в языках, об этом и речь. Высокоуровневый C++ быстрый отнюдь не только потому что для него оптимизаторы лучше, а во многом потому что в самом языке есть бесплатные, или практически бесплатные абстракции и высокоуровневые инструменты.
В C# еще больше. Посмотри на тот же Code First и Linq. Я без слез не могу смотреть на код С++ которые через COM вызывают 1С работая с Idispatch.
S>>>> Берем какую то задачу и программируем. Зная ЗП среднестатистического программиста вычисляем стоимость. Затем берем тесты и вычисляем стоимость железа для достижения одинакового результата. EP>>>Дальше-то ты какой вывод делаешь? S>> Вывод в том, что существование тех или иных языков или платформ вызвано не только скоростью выполнения
EP>В целом да, а в частности нет. Например сделали язык заточенный под скорость, потому что нужна скорость — вопрос, чем вызвано его существование?
Тем, что у него есть своя ниша. А вот какова емкость этой ниши?
S>>А количество специалистов зависит от сложности выполнения той или иной задачи и зарплаты за её выполнение. И так по кругу. Рынок рулит
EP>Дальше что? Это накладывает вето на любое сравнение скорости на разных языках?
Это ничего не наклавдывает. Эволюция говорит о том есть борьба и единство противоположностей. Нужна конкуренция и из неё рождаются новые языки и платформы. Именно по этому развивается С++,С#,Java питон и 1С
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, vdimas, Вы писали:
V>>>Линейный он лишь для случая одновременного поиска и сдвига элементов массива. V>>>В этом случае он представляет из себя разновидность пузырьковой сортировки. EP>>Это не разновидность пузырьковой сортировки. V>Извини, но сравнение и обмен строго с соседним элементом — это характеристика сортировок из семейства пузырьковой. V>Не помнишь, почему сортировка названа "пузырьковой"?
Я же говорю, что при повороте swap не нужен — это точно не пузёрок.
V>Блин, да я когда-то лабы делал по разным модификациям пузырьковых сортировок, а тут некоторые утверждают, что она только одна. ))
Тебе сказали что описанный тобой вариант это shaker sort. Утверждений того что пузырьковая только одна — не было.
V>Аналогично по сортировкам слиянием — мы их штук пять-шесть проходили (если склероз не изменяет). А на визуализации я вижу лишь один из вариантов.
Естественно там далеко не все разновидности. Сортировку слияниям кстати хорошо разбирает Степанов в своей книге Elements of Programming.
V>>>Если же сначала найти необходимую позицию, а затем сдвинуть все необходимые элементы за раз, то так может оказаться эффективней. EP>>Может, не спорю что есть вариант с двоичным поиском, и что у него есть область применения. Я говорю что обычно он линейный. V>"Обычно" — это из-за std::sort, что ле? )) V>Там, как раз, всё очень необычно, а весьма специфично для специфичного этапа сортировки.
Обычно — это значит типичный код реализации.
EP>>Там вообще говоря swap использовать не выгодно — там нет необходимости менять каждый соседний элемент между собой. Оптимальнее переместить текущий элемент в temp, все остальные переместить вправо, а потом переместить temp в левый край. Это операция ЕМНИП rotate_by_one. V>Об этом и речь, чтобы не производить на каждом шаге сравнение с перестановкой.
Не, как раз из-за того что бывает выгодней производить и сравнение и перемещения одновременно — то эти два этапа сливают. А выгодно потому что условных операций / ветвей меньше — достаточно дать гарантию что в самом начале есть guard element, тогда на каждой итерации достаточно одного вызова предиката сравнения, без проверки выхода за пределы массива.
V>Но искать-то выгодней двоично, а не линейно, для массива из более 16-ти элементов на современных машинах!
Порог есть, действительно, но обычным двоичным поиском в общем случае будет поиск места вставки во всём оставшемся левом массиве. Если же каждый элемент недалеко от своего места — то линейный поиск может быть выгоднее, ещё и за счёт меньшего количества сравнений, и за счёт отсутствия рандомных скачков далеко по памяти.
V>>>Похоже, что в тех реализациях, что ты представляешь — пузырьковая сортировка отработает N! (факториал) раз независимо от исходных данных. )) EP>>Очень смешно. Пузырьковая сортировка квадратична в худщем случае. V>Вот как раз не смешно. Самый простой вариант пузырьковой сортировки отрабатывает фиксированное кол-во раз, независимо от содержимого массива.
С квадратичной сложностью, а не факториалом
V>Я же тебе намекаю уже многократно,
Ты ошибся, и видимо осознал это. Но вместо того чтобы признать это, начинаешь переводить тему в какое-то другое русло, с поучительными комментариями вида "ну я тебе уже намекаю".
V>что пузырьковая сортировка — это целое семейство алгоритмов.
А теперь прочитай ещё раз мой ответ на эту тему:
V>>Не будет. Простой пузырёк протягивает флаг наличия несортированных элементов, а модифицированный вместо этого протягивает границы несортированной области (индекс начала и индекс конца) и работает в оба направления туда-сюда, сужая к центру (обычно) несортированную область.
EP>Даже с этими модификациями получается больше сравнений — дойдёт до 6, сделает swap, дойдёт до конца, а потом ещё сделает проход от 5 до 1.
EP>>>>Покажи реализацию без лишнего прохода, или хотя бы дай ссылку на код. V>>>Стандартная и есть без лишнего прохода. EP>>Код в студию, иначе наш спор не разрешится. V>В западной литературе шейкерную выделяют в отдельный вид сортировки, нас же её давали как разновидность пузырьковой.
Я же тебе говорю, возьми хоть шейкерную — у неё всё равно в этом случае сравнений будет больше чем вставками (вариант с линейным поиском обратно).
V>Более того, визуализация шейкерной сортировки на видео — ошибочна, ы-ы-ы.
Какое видео?
V>В шейкерной необходимо запоминать первое и последнее место обмена, т.е. должно происходить сужение диапазона.
Да, но только самое правое место обмена запоминается/важно при проходе направо, а левое — при проходе налево.
V>На прямом проходе обнаруживается единственный обмен 5 с 6, на обратном проходе должно быть одно сравнение 5 с 4 и сразу выход.
Нет там выхода сразу после сравнения 4 vs 5. У пузырьковой/шейкера нет break внутри цикла. Вместо пятёрки там мог быть ноль: 1 2 3 46 0 7 8 9.
Да даже если допустить что там выход после 4 vs 5 — это всё равно опровергает твой тезис о том что вставками здесь дороже, так как там столько же сравнений.
V>Код тривиальный, писать не буду. ))
Можешь скопировать откуда-нибудь, хоть псевдокод. Только не тяни, не надо растягивать это на десятки сообщений
Здравствуйте, Serginio1, Вы писали:
_>>2. Такая схема уже много лет как используется во всех остальных языках. Например у нас сайты работают именно так, только на сервере при этом отвечает на ajax запросы Питон (и без всякого asp естественно). S> А где же высокоскоростной C++?
Там, где latency в микросекундах или единиц миллисекунд измеряется, вестимо.
Пока сайты будут по нескольку секунд каждую страницу открывать, клиента и сервера можно писать хоть на руби, хоть на питоне.
S> Ну почему. Сейчас все пишется через await, Ajax ы. Это конечно не System.Threading.Tasks.Parallel но ассинхронные вычисления. S>Но мы то говаорим о вытеснении C++ более медленных платформ.
Из последнего что создаёт информационный шум — во всём мире начинают потихоньку переходить на терабитные сетки. Это нормальный процесс, рано или поздно он начался бы... Посмотрим, как это скажется на требованиях к быстрому клиенту и серверу. Пока что эти требования, мягко говоря, несерьезные, бо сетка съедает всё быстродействие.
Здравствуйте, vdimas, Вы писали:
V>Здравствуйте, Serginio1, Вы писали:
_>>>2. Такая схема уже много лет как используется во всех остальных языках. Например у нас сайты работают именно так, только на сервере при этом отвечает на ajax запросы Питон (и без всякого asp естественно). S>> А где же высокоскоростной C++?
V>Там, где latency в микросекундах или единиц миллисекунд измеряется, вестимо. V>Пока сайты будут по нескольку секунд каждую страницу открывать, клиента и сервера можно писать хоть на руби, хоть на питоне.
S>> Ну почему. Сейчас все пишется через await, Ajax ы. Это конечно не System.Threading.Tasks.Parallel но ассинхронные вычисления. S>>Но мы то говаорим о вытеснении C++ более медленных платформ.
V>Из последнего что создаёт информационный шум — во всём мире начинают потихоньку переходить на терабитные сетки. Это нормальный процесс, рано или поздно он начался бы... Посмотрим, как это скажется на требованиях к быстрому клиенту и серверу. Пока что эти требования, мягко говоря, несерьезные, бо сетка съедает всё быстродействие.
Я уже писал, что сейчас сервер передает только Json данные. А DOM уже строится на клиенте, при этом используется кэширование на клиенте. То есть скорость передачи при этом не является ограничением.
Проблема в уже в JS.
и солнце б утром не вставало, когда бы не было меня
Пока я отвечал, ты существенно изменил сообщение. Отвечу на разницу, на которую ещё не ответил.
V>>>Похоже, что в тех реализациях, что ты представляешь — пузырьковая сортировка отработает N! (факториал) раз независимо от исходных данных. )) EP>>Очень смешно. Пузырьковая сортировка квадратична в худщем случае. V>Вот как раз не смешно. Самый простой вариант пузырьковой сортировки отрабатывает фиксированное кол-во раз, независимо от содержимого массива: V>
V>for(int end = size - 1, end > 0, end--)
V> for(int i = 0; i < end; i++)
V> swap_if_needed(array[i], array[i+1]);
V>
V>Чуть меньше, чем квадратичная, не?
Квадратичная в чистом виде, потому что сумма арифметической прогрессии квадратична. Никакого факториала.
V>Код тривиальный, но длинный, открывать студию и писать не буду. ))
Да не надо писать, скопируй откуда-нибудь, или дай ссылку.
V>Вербально как-то так: V>1. движение вперед от нижней до верхней границы неотсортированной области, поиск первой пары для обмена, запоминание нижней границы отсортированного диапазона (минус одна позиция от текущей); если обмена не было — выход.
V>2. продолжаем движение вперед, обмен при необходимости, запоминание верхней границы отсортированного диапазона.
V>3. сравнение с первым элементом из отсортированной области, при необходимости продолжаем "всплытие" (в любом случае, запомненная на предыдущем шаге граница не изменяется).
V>4. движение назад аналогично, потом goto 1.
V>На каждом шаге у нас "всплывает" максимальный (или "тонет" минимальный) элемент из неотсортированной области к её краю, т.е. применяется обычный пузырёк; на границе отсортированной области алгоритм меняется — мы движемся лишь до тех пор, пока необходим обмен.
И не одонго break'а внутри цикла, да?
Попробуй примени этот алгоритм к последовательности с нулём: 1 2 3 46 0 7 8 9
И к последовательности с пятёркой: 1 2 3 46 5 7 8 9
Если нет break'а, то в обоих случаях при обратном проходе должен дойти до самого начала
Здравствуйте, PM, Вы писали:
PM>Буквы не читай, сообщения пиши. Или я что-то пропустил и языки Java/C# умеют работать без JVM/CLR
Зато C/С++ есть для JVM и .Net и шота не видно никаких чудес. Джава и шарп рвут всё на своих платформах. Как то так.
PM>Почитайте на досуге как авторы LMAX героически боролись
: высокоуровневый код C++ скомпилированный в JavaScript почти в два раза быстрее аналога на C# в своей родной среде. EP>JavaScript, в веб-браузере, Карл!
Сколько ты будешь мусолить этот булшыт ?
1 Вроде как очевидно, что здесь разные платформы. Попробуй тот же мега-с++ код скомпилировать в дотнет и открой для себя страшное — скорость сильно вряд ли будет отличаться от C#.
2 Попробуй скомпилировать C# в тот же javascript, получишь ровно тот же перформанс, что и после С++. А все почему ? Потому что js, а не потому что С++.
Вот скомпилить Шарп в натив сильно вряд ли выйдет, т.к. язык принципиально требует специальную платформу, как и js.
Здравствуйте, Ikemefula, Вы писали:
I>Вот скомпилить Шарп в натив сильно вряд ли выйдет, т.к. язык принципиально требует специальную платформу, как и js.
Причем самыми востребованными программистами остаются специалисты, пишущие на «1С» и PHP.
И что? Вывод дальше какой? Эникейщики ещё более востребованы
S>>>Но например этот отчет бухгалтер делает раз в месяц. И он может подождать даже пол часа, занимаясь другой работой. EP>>Бывают и такие варианты. EP>>А бывают и другие, например бухгалтер генерирует отчёт, потом проверяет его, исправляет ошибки, и опять запускает — и так может быть несколько раз. EP>>Или например инженер делает расчёт, ждать результата он может долго скажем день, но при этом бОльшая доступная вычислительная мощность переходит в качество — он может сделать более густую расчётную сетку, произвести большее количество нелинейных расчётов и т.д. и т.п. S> Ты меня не читаешь.
Читаю.
S>Я говорю, что ускоряю скорость отчетов в 100 раз. Все довольны, но иногда прихожу к буху и спрашиваю каким отчетом пользутесь, а они говоря, что по привычке старым. При этом это не доли секунд, а пол часа.
А ещё раз говорю, это один из вариантов. И я не оспариваю то что этот вариант реальный.
S>>> поскипано. Это все понятно. Я не стал выводить выкладки. Понятно, что факторов очень много. EP>>Много, и тормоза отнюдь не двукратные. S> Правильно, значительно меньше при правильном написании алгоритма. Все твои примеры это выбор самого плохого подбора алгоритма.
Это уже пошло отрицание реальности. Все мои примеры вообще алгоритм не меняют. Меняют уровень абстракции.
Если добавили замыкание и ФВП, и в результате чего получили многократные тормоза и отжоры памяти — это не замена алгоритма, это использование более высокоуровневых средств.
Если мы обвернули примитивную операцию в класс, для удобства, не меняя сути всего алгоритма — это использование более высокоуровневых средств.
Если вместо ручной склейки умножения массивов и операции умножения элементов мы реализуем их по отдельности, а склейку делает сам компилятор — это не замена алгоритма.
И т.д. и т.п.
EP>>А я вообще забыл упомянуть тормоза от GC, это отдельная тема. Тормоза для pointer semantics style есть даже без учёта бОльшей нагрузки на GC. EP>>И если активно использовать pointer semantics в C++ — то и там появятся точно такие же тормоза как и в Java/C#/etc: пример
— заменили плотно упакованные элементы, на структуру ссылочного вида — в результате разница по скорости 208.6x, и это без учёта работы менеджера памяти. EP>>Но в C++ default это value semantics, и там его намного легче использовать чем в языках заточенных под pointer semantics. S> Тормоза от GC зависят от задач.
Ещё раз, это пример не про сборку мусора и т.п., а чисто на случай когда используются указатели вместо value sematnics.
S>В большинстве случаев сбор мусора, это просто сдвиг указателя конца кучи на начало. S>Не все так однозначно.
А обход графа это бесплатно что-ли?
Ты видимо слышал про сдвиг указателя, но приплёл его абсолютно не к месту. Тот самый сдвиг указателя, о котором часто вспоминают, происходит при выделении памяти из первого поколения, а не при сборки мусора. При сборки происходит обход графа живых объектов, с их копированием (зависит от реализации).
S>>>Это EP>>>>>>Во-первых, это всего лишь один вариант целесообразности. Например железо может быть уже на миллионах устройств клиентов — и вместо покупки нового девайса, они пойдут к конкурентам, софт которых работает на текущем железе, пусть и стоимость его разработки была выше. S>>> Или если таких приложений будет 1-2 он уйдет к тем у кого 1000-100000. EP>>Не понял этого тезиса. S> Да в том, что нужна скорость разработки и количество специалистов которые могут решить эти задачи.
Это важно в том числе
S>Если таких специалистов оочень мало, то будут побеждать те языки где сложность входа значительно меньше.
Побеждать в чём? В задачах неприхотливых ни к скорости, ни к потреблению энергии, ни к потреблению памяти? Да, конечно будут.
S>Как ты думаешь, что проще для изучения 1С++ или 1С?
Я 1С не знаю, но предполагаю что порог вхождения ниже. А стать водителем ещё проще.
EP>>А вообще не понятно к чему вопрос про занятость, даже если он в среднем занят на доли процента, это не делает не нужным быстрое железо, и быстрый софт. EP>>Например женщина в среднем вынашивает ребёнка в течении скажем 2% от продолжительности своей жизни, размазать этот процент по всем годам никак не получится, и она не сможет родить ребёнка через день после зачатия S> Они нужны. Но у них своя ниша.
Несомненно
S>>>>>Заметь, что в браузерах победил JS. Опять же какая разница для пользователя в ожидании 0.1 или 0.2 секунды. EP>>>>ASM.JS достаточно быстрый. Я даже выше приводил ссылку. C++ скомпилированный в ASM.JS обогнал C# в своей родной среде практически в два раза EP>>>>JavaScript, в веб-браузере, Карл! S>>> В итоге все зависит от компилятора. Например TS тоже транслируется в JS и ничто не мешает транслировать в более оптимальный. Здесь проблема не языков а компиляторов которые совершенствуются. EP>>Как раз таки проблема в языках, об этом и речь. Высокоуровневый C++ быстрый отнюдь не только потому что для него оптимизаторы лучше, а во многом потому что в самом языке есть бесплатные, или практически бесплатные абстракции и высокоуровневые инструменты. S> В C# еще больше.
Ещё больше чего? Бесплатных высокоуровневых абстракций?
S>Посмотри на тот же Code First и Linq.
Это C# Linq бесплатный?
Аналог Linq-а кстати возможен и в C++, причём бесплатный — то есть строковые запросы будут формироваться автоматически на этапе компиляции Недавно как раз была подобная тема, с конкретными примерами — если интересно могу найти ссылку.
S>Я без слез не могу смотреть на код С++ которые через COM вызывают 1С работая с Idispatch.
Если кто-то постоянно пишет низкоуровневый interop, не сделав ни обёрток, или даже не сгенерировав их автоматом — то это ССЗБ в чистом виде, они есть на каждом языке.
S>>>>> Берем какую то задачу и программируем. Зная ЗП среднестатистического программиста вычисляем стоимость. Затем берем тесты и вычисляем стоимость железа для достижения одинакового результата. EP>>>>Дальше-то ты какой вывод делаешь? S>>> Вывод в том, что существование тех или иных языков или платформ вызвано не только скоростью выполнения EP>>В целом да, а в частности нет. Например сделали язык заточенный под скорость, потому что нужна скорость — вопрос, чем вызвано его существование? S> Тем, что у него есть своя ниша. А вот какова емкость этой ниши?
Да, для каждого языка есть своя ниша, отчасти они пересекаются. Ёмкости ниш разные, да.
Дальше что? Ты можешь сразу сказать к чему ты подводить?
S>>>А количество специалистов зависит от сложности выполнения той или иной задачи и зарплаты за её выполнение. И так по кругу. Рынок рулит EP>>Дальше что? Это накладывает вето на любое сравнение скорости на разных языках? S> Это ничего не наклавдывает. Эволюция говорит о том есть борьба и единство противоположностей. Нужна конкуренция и из неё рождаются новые языки и платформы. Именно по этому развивается С++,С#,Java питон и 1С
Здравствуйте, Ikemefula, Вы писали:
PM>>Буквы не читай, сообщения пиши. Или я что-то пропустил и языки Java/C# умеют работать без JVM/CLR I>Зато C/С++ есть для JVM
Здравствуйте, vdimas, Вы писали:
S>> А где же высокоскоростной C++?
V>Там, где latency в микросекундах или единиц миллисекунд измеряется, вестимо. V>Пока сайты будут по нескольку секунд каждую страницу открывать, клиента и сервера можно писать хоть на руби, хоть на питоне.
Там где latency в микросекундах и единицах миллисекунд нужен не высокоскоростной С++, а корректный код, предельно предсказуемый по издержкам и соответсвующая архитектура, фактически система реального времени. Вместо "выполним всё быстро-быстро" используется "вызов x занимает не более Y тактов".
А вот там, где обработка данных, т.е. нужна пропускная способность экстремальнее некуда — там да, без высокоскоростного С++ никак. Более того — и С++ часто не хватает, приходится или вставки ассемблера делать или генерить хитрый код или вытеснять вычисление в специализированый процессор, тот же gpu и тд.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
PM>>>Буквы не читай, сообщения пиши. Или я что-то пропустил и языки Java/C# умеют работать без JVM/CLR I>>Зато C/С++ есть для JVM
EP>Покажи нормальный компилятор C++ для JVM.
Не следил за вопросом. Качество генерации байткода у джавы и шарпа вполне нормальное. Основные проблемы с производительностью даёт сам джыт. Какой бы ты наипрекрасный байткод не подсунул, джыт всё равно его опаскудит.
: высокоуровневый код C++ скомпилированный в JavaScript почти в два раза быстрее аналога на C# в своей родной среде. EP>>JavaScript, в веб-браузере, Карл! I>Сколько ты будешь мусолить этот булшыт ?
А сколько ты ещё будешь нести свой "булшыт"?
I>1 Вроде как очевидно, что здесь разные платформы. Попробуй тот же мега-с++ код скомпилировать в дотнет и открой для себя страшное — скорость сильно вряд ли будет отличаться от C#.
Не верно. Низкоуровневый C# быстрее в разы высокоуровневого C# в пределах .NET, потому что язык такой — абстракции дорогие.
Высокоуровневый код C++ и ручной низкоуровневый аналог даёт зачастую идентичный машинный код, в этом и есть фишка.
I>2 Попробуй скомпилировать C# в тот же javascript, получишь ровно тот же перформанс, что и после С++. А все почему ? Потому что js, а не потому что С++.
Да нет же, ты пример не смотрел, сути тезиса не понял, зато "мнение имеешь" Правильно выше сказали "буквы не читай, сообщения пиши".
В C# скомпилированном в JavaScript точно также как и на .NET не будет заинлайненной лямбды, и от этого точно также будут тормоза.
Здравствуйте, gandjustas, Вы писали:
I>>Вот скомпилить Шарп в натив сильно вряд ли выйдет, т.к. язык принципиально требует специальную платформу, как и js.
G>А как же .net native?
native в данном вопросе это просто маркетинговый буллшит от микрософта. Примерно как light на сигаретах — не означает отсутствие вреда здоровью.
Здравствуйте, Serginio1, Вы писали:
EP>>Как раз таки проблема в языках, об этом и речь. Высокоуровневый C++ быстрый отнюдь не только потому что для него оптимизаторы лучше, а во многом потому что в самом языке есть бесплатные, или практически бесплатные абстракции и высокоуровневые инструменты. S> В C# еще больше. Посмотри на тот же Code First и Linq. Я без слез не могу смотреть на код С++ которые через COM вызывают 1С работая с Idispatch.
Не в первый раз наблюдаю, что при сравнении С++ с другими, более поздними языками, люди активно не использующие С++ приводят примеры кода 10-15 летней давности (MFC, COM). Причем уже в то время в Visual C++ была средства для нормальной работы с COM (ATL, #import, позже _com_ptr_t) которые позволяли писать код без многоэтажных if(SUCCEEDED()) AddRef/Release.
I’ve created a currency formatter, set the rounding algorithm, and formatted a value. What about Standard C++? A lot of developers seem to think that C# is the most popular language on the Windows platform today because it is so much better than C++. It’s not, instead it’s all about the tooling. One of the main arguments for .NET was that it avoided the reference counting hell that C++ apparently produced. Proponents of this position would like to show you the example above written in Standard C++:
But no C++ developer in his right mind would ever write code like this (and I haven’t even included error handling). Instead the C++ developer would naturally write something like this:
CurrencyFormatter currency(L"USD");
currency.ApplyRoundingForCurrency(RoundingAlgorithm::RoundDown);
String result = currency.Format(123.456);
assert(result == L"$123.45");
Недавно как раз была подобная тема, с конкретными примерами — если интересно могу найти ссылку.