[C++] Тренировочные задачи. Оптимизация скорости.
1. Секунды зависят от производительности конкретного компьютера, так что сравнивать надо на одной машине.
2. Язык не так принципиален, как то, как ты им пользуешься.
В частности:
- решето Эратосфена вовсе не так эффективно для генерации простых чисел. Проще тупо делить очередное число N на все найденные ранее простые, меньшие sqrt(N)
- Тебе не нужны ВСЕ простые до Max, а нужно только столько, чтобы их сумма была меньше Max.
Используя эти два соображения, я написал код на C#, который решает твою задачу для 10 миллиардов за 0.1 секунды, для 100 миллиардов - за 0.45 секунды, а для триллиона - за 2.06 секунд. При этом я ничего не оптимизировал, писал самым примитивным способом.
Код: http://pastebin.com/AaCiF3rR
2. Язык не так принципиален, как то, как ты им пользуешься.
В частности:
- решето Эратосфена вовсе не так эффективно для генерации простых чисел. Проще тупо делить очередное число N на все найденные ранее простые, меньшие sqrt(N)
- Тебе не нужны ВСЕ простые до Max, а нужно только столько, чтобы их сумма была меньше Max.
Используя эти два соображения, я написал код на C#, который решает твою задачу для 10 миллиардов за 0.1 секунды, для 100 миллиардов - за 0.45 секунды, а для триллиона - за 2.06 секунд. При этом я ничего не оптимизировал, писал самым примитивным способом.
Код: http://pastebin.com/AaCiF3rR
Блин. Написал целую простыню тебе, и случайно закрыл окно.
Вкратце: язык С++ - не волшебная пилюля. Правильный выбор алгоритма ускорит решение в 1000 раз, правильная организация этого алгоритма на твоем любимом языке может дать еще 2-кратное ускорение, а смена языка на С++ ускорит максимум на 10%.
Кроме того, учти, что производительность в наше время редко упирается чисто в процессор. Узким местом часто является что-то другое: обращения к памяти, внешним устройствам, синхронизация, локализация данных.
Если тебе все-таки хочется математики и хардкора, вот тебе более интересная задачка, в которой понятно, где копать, но в то же время копать можно очень долго:
Дан vector<double> X достаточно большого размера. Скажем, миллиард.
Надо посчитать vector<double> Y такой, что каждый элемент Yi = 1/(1+e^(-Xi)).
В качестве точки отсчета можно взять "наивный" алгоритм:
Тут много чего можно улучшить. Можно память выделить на Y сразу и обойтись без push. Можно распараллелить на все доступные ядра процессора, причем разными способами. Можно, наконец, ускорить вычисление экспоненты - это самая интересная часть
Для пущего интереса давай допустим приближенное вычисление exp(), но так, чтобы первые 13 десятичных знаков Yi были точные.
Вкратце: язык С++ - не волшебная пилюля. Правильный выбор алгоритма ускорит решение в 1000 раз, правильная организация этого алгоритма на твоем любимом языке может дать еще 2-кратное ускорение, а смена языка на С++ ускорит максимум на 10%.
Кроме того, учти, что производительность в наше время редко упирается чисто в процессор. Узким местом часто является что-то другое: обращения к памяти, внешним устройствам, синхронизация, локализация данных.
Если тебе все-таки хочется математики и хардкора, вот тебе более интересная задачка, в которой понятно, где копать, но в то же время копать можно очень долго:
Дан vector<double> X достаточно большого размера. Скажем, миллиард.
Надо посчитать vector<double> Y такой, что каждый элемент Yi = 1/(1+e^(-Xi)).
В качестве точки отсчета можно взять "наивный" алгоритм:
for(int i=0; i<X.size(); i++)
{
Y.push(1/(1+exp(X[i])));
}
Тут много чего можно улучшить. Можно память выделить на Y сразу и обойтись без push. Можно распараллелить на все доступные ядра процессора, причем разными способами. Можно, наконец, ускорить вычисление экспоненты - это самая интересная часть
Для пущего интереса давай допустим приближенное вычисление exp(), но так, чтобы первые 13 десятичных знаков Yi были точные.
смена языка на С++ ускорит максимум на 10%уверен, что максимум гораздо больше
Вкратце: язык С++ - не волшебная пилюля.Волшебная, когда тебе внезапно надо не сферические задачки олимпиадников решать, а реальные практические.
Вот тут-то и появляются тонкости эффективной работы с памятью, сетью, диском.
Понятно дело, что на твоём сишарпе числа перемножать не сильно медленнее будет.
тонкости эффективной работы с памятью, сетью, диском.Шо вы таки имеете ввиду?
тонкости эффективной работы с памятью, сетью, диском.например переписать функцию sendfile, чтобы нормально отдавать 20-30Гбит/с с дисков в сеть в рандомном чтении.
----------------------------------------------------------------------------
Шо вы таки имеете ввиду?
Полагаю, речь идет скорее о С, чем о С++. Нет?
Тебе не нужны ВСЕ простые до Max, а нужно только столько, чтобы их сумма была меньше MaxЭто ключевой момент. На этом месте я тоже поначалу попался. Собственно по причине этого предположения твой алгоритм работает существенно быстрее — ничего удивительного, размер данных маленький.
Можешь доказать, что этого достаточно?
решето Эратосфена вовсе не так эффективно для генерации простых чисел. Проще тупо делить очередное число N на все найденные ранее простые, меньшие sqrt(N)
Это не так. Решето Эратосфера работает как минимум в 10 раз быстрее. Поначалу я написал, как ты предлагаешь, но не смог дождаться ответа для 50 миллионов, быстрее было переписать алгоритм.
Секунды зависят от производительности конкретного компьютера, так что сравнивать надо на одной машине.
Если интересно, процессор 2,5 GHz Intel Core i5, память 1333 MHz DDR3, операционная система OS X, пишу и компилирую C++-код в Xcode.
Тебе не нужны ВСЕ простые до Max, а нужно только столько, чтобы их сумма была меньше MaxНе совсем контрпример, но наводит на размышления.
-----------------------------------------------------------------------------
Это ключевой момент. На этом месте я тоже поначалу попался. Собственно по причине этого предположения твой алгоритм работает существенно быстрее — ничего удивительного, размер данных маленький.
Можешь доказать, что этого достаточно?
Сумма первых девяти простых чисел равна ста: 100 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23. В твоем алгоритме, как я понял, берутся только эти девять чисел для поиска самого длинного простого числа, меньшего 100.
Ответ получается верным, ибо самое длинное простое число 41 = 2 + 3 + 5 + 7 + 11 + 13, имеющее длину 6, составляется из первых девяти простых чисел. Но твой алгоритм пропускает другие простые числа, которые меньше ста и имеют не единичную длину. Например, число 73 = 23 + 29 + 31 или 97 = 29 + 31 + 37.
Почему не может оказаться так, что твой алгоритм для других значений max пропустит простые числа, имеющие максимальную длину, и даст неправильный ответ? Это большой вопрос.
Сумма первых девяти простых чисел равна ста: 100 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23. В твоем алгоритме, как я понял, берутся только эти девять чисел для поиска самого длинного простого числа, меньшего 100.Ты прав, формально это не доказывается, и мой алгоритм неправильный. На практике же максимальная найденная длина настолько близка к максимальной возможной, что этот недостаток легко устраним.
Вот смотри, для 100 миллиардов я сначала нашел 125494 простых чисел. Потом я обнаружил, что максимальная длина - 125479. Значит, мне нужно найти еще несколько простых чисел так, чтобы сумма 125479 последних была бы больше 100 миллиардов. В данном случае мне нужно найти еще 0 простых, т.к. этот инвариант уже выполняется.
После этого повторяем поиск, и находим результат уже математически точно.
Кстати, попробовал разные значения Max (10, 100, 1000 миллиардов), и ни разу не оказалось, что сумма maxLen последних найденных простых меньше, чем Max. То есть даже без модификации алгоритм давал правильный ответ, и добавленный мною код не выполняется ни разу (хотя и приводит к математической правильности алгоритма).
Это не так. Решето Эратосфера работает как минимум в 10 раз быстрее.Возможно, ты и прав, и просто у меня данных было меньше. Википедия с тобой согласна, что решета работают быстрее индивидуальных тестов.
Но решето Эратосфера
а) может быть написано быстрее, чем это сделал ты.
б) не является самым быстрым решетом, есть алгоритмы быстрее него. http://en.wikipedia.org/wiki/Generating_primes
В конце концов, генерировать простые числа можно и за пределами твоего алгоритма (или тупо скачать первый миллион с http://primes.utm.edu/lists/small/millions )
Волшебная, когда тебе внезапно надо не сферические задачки олимпиадников решать, а реальные практические.Ты, возможно, считаешь, что я сижу в башне из слоновой кости? Вообще-то моя нынешняя команда пишет реальные практические алгоритмы машинного обучения, в которых полностью используются тонкости эффективной работы с паматью и внешними устройствами, и делает это на C# вполне успешно.
Вот тут-то и появляются тонкости эффективной работы с памятью, сетью, диском.
Под "вполне успешно" понимается "быстрее аналогов на порядки".
И в нашей команде есть люди значительно круче меня. Я готов даже рискнуть и предположить, что они круче и тебя. Так вот, эти люди осознанно выбрали C# для реализации высокопроизводительных вычислений.
P.S. На самом деле, кое-где мы были вынуждены вставлять нативный код на C++, потому что C# / JIT компилятор не умеют генерировать SSE инструкции, и MKL тоже на C# нет
"быстрее аналогов на порядки"вероятно, потому что схожего скилла команды, пишущей аналоги на C/С++, просто не нашлось?
Наверно. В общем, я чувствую, куда клонится этот тред, так что сразу каюсь:
я очень уважаю C++! Несомненно, C++ производительнее нашего C#. Кроме того, С++ предоставляет намного больше возможностей выстрелить себе в ногу, поэтому я чертовски уважаю программистов на C++, которые ухитряются этого избегать.
Сам я на С++ писал мало, поэтому, если начну, то не миновать мне простреленных ног.
Ну да, и я беру назад свои слова про 10% производительности. Это была не экспертная оценка, а догадка, и раз местные зубры считают, что она неверна, у меня нет причин за нее держаться. Пусть будет 100%, и не между любым языком и С++, а между C# и C++. Там, где разница в 2 раза принципиальна, придется писать на плюсах. А может, и на чем-нибудь похуже.
я очень уважаю C++! Несомненно, C++ производительнее нашего C#. Кроме того, С++ предоставляет намного больше возможностей выстрелить себе в ногу, поэтому я чертовски уважаю программистов на C++, которые ухитряются этого избегать.
Сам я на С++ писал мало, поэтому, если начну, то не миновать мне простреленных ног.
Ну да, и я беру назад свои слова про 10% производительности. Это была не экспертная оценка, а догадка, и раз местные зубры считают, что она неверна, у меня нет причин за нее держаться. Пусть будет 100%, и не между любым языком и С++, а между C# и C++. Там, где разница в 2 раза принципиальна, придется писать на плюсах. А может, и на чем-нибудь похуже.
Вот смотри, для 100 миллиардов я сначала нашел 125494 простых чисел. Потом я обнаружил, что максимальная длина - 125479. Значит, мне нужно найти еще несколько простых чисел так, чтобы сумма 125479 последних была бы больше 100 миллиардов.Да, я понял идею.
Такой подход будет работать хорошо, если верна гипотеза о том, что максимальная длина простых чисел, не превосходящих N, близка к максимальной длине натуральных чисел от 1 до N (расширяем понятие длины на все натуральные числа, полагая длину равной нулю для тех из них, которые не представляются суммой последовательных простых чисел).
Главное, что этот подход в худшем случае будет работать как твой, с поиском вообще всех простых
с поиском вообще всех простыхПравда этот поиск будет происходит твоим способом (поочередным присоединением простых чисел к их исходному списку), который работает медленнее (более чем в 20 раз), а не решетом Эратосфена. Решето Эратосфена в этом случае применить нельзя?
Напрямую нельзя. Вообще, лучше оперировать асимптотическими оценками, чем "в 20 раз", когда сравниваешь алгоритмы.
Можно, наконец, ускорить вычисление экспоненты - это самая интересная часть
Или сам сигмоид ускорить, он же хорошо полиномами приближается.
Проникся С++-ом, когда понял, что этот язык был создан для написания максимально быстрых программ. Отсюда вся его сложность.из общефилософских соображений понятно, что сложность синтаксиса языка программирования отрицательно сказывается на скорости работы написанных на нем программ.
у ассемблера самый простой синтаксис и он же самый быстрый, т.к. нет накладных расходов на обслуживание высокоуровневых абстраций языка.
сложный синтаксис языка нужен для того, чтобы на нем было удобнее составлять программы, пользуясь синтаксическими конструкциями лучше приспособленными под человеческий способ мышления. программы от этого становятся лаконичнее и понятнее.
из общефилософских соображений понятно, что сложность синтаксиса языка программирования отрицательно сказывается на скорости работы написанных на нем программ.Да нифига такого. Возьми простенький лисп. Сложность синтаксиса очень низка, за 50 строк пишется интерпретатор, а скорости нет и в помине.
из общефилософских соображений понятно, что сложность синтаксиса языка программирования отрицательно сказывается на скорости работы написанных на нем программ.А из практического опыта - ровно наоборот.
сложность синтаксиса языка программирования отрицательно сказывается на скорости работы написанных на нем программфакторов много, если есть зависимость то она совсем не монотонная
как только в языке появляется подмножество с полным и быстрыми функционалом, например
char *main = "...";
остальное можно уже игнорировать
у ассемблера самый простой синтаксис и он же самый быстрый, т.к. нет накладных расходов на обслуживание высокоуровневых абстраций языка.Расходы на высокоуровневые абстракции зачастую на этапе компиляции.
А что касается простого ассемблера, С++ с максимальной оптимизацией сгенерирует код быстрее, чем тот, что ты напишешь в 90%. А вот если пытаться самостоятельно выжимать максимальную скорость, то программирование на асме станет совсем нетривиальным.
Она может отрицательно сказываться только на скорости компиляции, но никак не на скорости работы
А из практического опыта - ровно наоборот.
Она может отрицательно сказываться только на скорости компиляции, но никак не на скорости работыСравните время на сложение элементов массива целых чисел:
- низкий уровень абстрации: массив чисел типа int, обращение к элементам по индексу
- высокий уровень абстрации: std::vector<int>, обращение к элементам через итератор
факторов много, если есть зависимость то она совсем не монотоннаяя собственно пытался намекнуть автору, что сложность с++ не связана с его производительностью
сложность с++ не связана с его производительностьюC++ дает программисту намного более полный контроль над системой, чем та же Java (или Ruby или Haskell), но при этом не теряет в уровне своей абстракции. За это мы расплачиваемся сложностью языка.
Понятно, что программы на C или ассемблере не менее производительны, чем на С++, но уровень абстракции, даваемый этими языками, несравнимо ниже.
Сравните время на сложение элементов массива целых чисел:
- низкий уровень абстрации: массив чисел типа int, обращение к элементам по индексу
- высокий уровень абстрации: std::vector<int>, обращение к элементам через итератор
В пределах погрешности измерений. Какой разницы ты ожидаешь и почему?
gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2
clang version 3.5.0 (209993)
Я часто вижу наоборот, когда из-за отсутствия или неудобства абстракций языка люди пишут существенно менее эффективный код. Например, очень мало кто заморачивается с реализацией хеш-таблиц в C, и хреначат какой-нибудь N^2 - типа здесь данных мало, и так сойдет. Сегодня мало, завтра много.
Когда будешь компилировать под релиз, для этих вариантов скорее всего скомпилируется одинаковый код, т.к. внутри вектора тот же самый массив, а в релизе итератор для вектора - простой указатель.
Да, и надо сравнивать либо в обоих случаях обращение по индексу, либо в обоих случаях перебор через итератор/указатель
Да, и надо сравнивать либо в обоих случаях обращение по индексу, либо в обоих случаях перебор через итератор/указатель
Забавный момент, если итерируем по массиву с помощью целочисленного индекса, а не по указателю - получается медленнее, чем по вектору с итератором. Ну это если оптимизации нет, разумеется.
Я часто вижу наоборот, когда из-за отсутствия или неудобства абстракций языка люди пишут существенно менее эффективный код. Например, очень мало кто заморачивается с реализацией хеш-таблиц в C, и хреначат какой-нибудь N^2 - типа здесь данных мало, и так сойдет. Сегодня мало, завтра много.Если припрет, напишут. Мне вон приходилось реализовывать и инструментировать для временных структур вектор и хэш на внутреннем представлении компилятора( а это значительно сложнее, чем на асме). А для переменных размеров данных еще и седловые точки высчитывать в рантайме и применять разные реализации.
C++ дает программисту намного более полный контроль над системой, чем та же Java (или Ruby или Haskell), но при этом не теряет в уровне своей абстракции. За это мы расплачиваемся сложностью языка.с такой формулировкой я согласен )
с такой формулировкой я согласен )а зря. По уровню абстракций он всё-таки уступает хаскелю. И никакая сложность программирования этого не выправит.
В пределах погрешности измерений. Какой разницы ты ожидаешь и почему?c выключенной (по умолчанию) оптимизацией реализация на c++ в 5 раз медленнее
с -O1 c++ проигрывает 10% по времени
с -O2 нет разницы
gcc (Debian 4.7.2-5) 4.7.2
Пример получился не показательным - оптимизация спасла ситуацию.
Однако для сложных сценариев видимо не спасает.
Иначе почему же бедные авторы linux, apache, nginx, python и пр. возятся на низком уровне абстрации, если есть такие прекрасные инструменты как boost?
Хз, по-моему в большинстве случаев компилятор сгенерирует один код для низкоуповнего и высокоуровнего кода, если этот высокоуровневый код грамотно написать. Правда некоторые оптимизации комппилятор не догадается сделать при подстановке шаблонов например.
Инерция мышления. Раньше и C++ был корявее, и компиляторы тупее.
Зачем вообще говорить о неоптимизированном коде? -O0 это какая-то произвольная точка между исходным кодом и production binary, ее производительность не имеет никакой ценности и разные языки там могут тормозить по разному просто потому что так получилось.
Зачем вообще говорить о неоптимизированном коде? -O0 это какая-то произвольная точка между исходным кодом и production binary, ее производительность не имеет никакой ценности и разные языки там могут тормозить по разному просто потому что так получилось.
Раньше и C++ был корявее, и компиляторы тупее.Стандарт обновляется, компиляторы отстают. Врядли свежие фичи языка также хорошо оптимизируются как существующие. Заметь что с -O1 оптимизацией с++ реализация все еще отстает от с-шной.
Зачем вообще говорить о неоптимизированном коде? -O0 это какая-то произвольная точка-O0 это не произвольная точка, а "дословное" переложение высокоуровневых конструкций на ассемблер, отправная точка для оптимизации. Из результатов теста видно, что "дословном изложении" более абстрактные конструкции требуют больше ресурсов.
Да там почти все - синтаксический сахар. Компиляторы догоняют.
-O1 еще более произвольный чем -O0. Уровень "дословности" тоже может быть разный - например, clang на -O0 генерит огромное количество очевидно лишних инструкций, а gcc выглядит слегка более осмысленно.
-O1 еще более произвольный чем -O0. Уровень "дословности" тоже может быть разный - например, clang на -O0 генерит огромное количество очевидно лишних инструкций, а gcc выглядит слегка более осмысленно.
Иначе почему же бедные авторы linux, apache, nginx, python и пр. возятся на низком уровне абстрации, если есть такие прекрасные инструменты как boost?Некоторые ненавидят C++, другие предпочитают подольше пописать, но потом побыстрее скомпилироваться,
третьи считают, что чем более высокоуровневый у тебя инструмент, тем больше он тебя ограничивает. Продолжать?
Оставить комментарий
nikola1956
Проникся С++-ом, когда понял, что этот язык был создан для написания максимально быстрых программ. Отсюда вся его сложность. Поэтому кажется интересным "помучить" С++ с целью решения несложных задач, которые требуют, однако, значительных затрат ресурсов системы и времени, а значит именно С++ становится лучшим инструментом для их решения.Первая задачка.
Назовем длиной простого числа наибольшее возможное количество слагаемых в сумме последовательных простых чисел, которая его представляет. Например, длина числа 23 = 5 + 7 + 11 равна трем. Требуется найти простое число максимальной длины, которое не превосходит одного миллиарда.
У меня получилось найти ответ за 101 секунду (максимальная длина равна 13935, достигается, например, на простом числе 999715711). А для верхней границы в десять миллиардов потребовалось 1119 секунд, максимальная длина оказалась равной 41708, достигается на простом числе 9999419621. Можно ли это вычислить существенно быстрее?
Свой вариант решения привожу невидимым текстом: