Математические алгоритмы

Question

Я пытаюсь понять концепцию Алгоритмов и в основном как повысить производительность компьютерной программы.

Так предположим, что я должен написать программу, которая генерирует список чисел,

1. начинается с номером 1.

2. Добавляет к нему 3.

3. Сохраняет результат (1 + 3 = 4) в списке.

4. Добавляет 5 к новому номеру.

5. Хранит результат (4 + 5 = 9) в списке.

6. Сохраняет в качестве альтернативы добавление 3 и 5 к последнему номеру в списке.

Теперь это очень простая программа и позволяет сказать, что программа должна остановиться, когда число больше, чем 10,00,000, и позволяет предположить простую программу, чтобы сделать это занимает 10 секунд, чтобы сформировать список.

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

ПРИМЕЧАНИЕ - Я пытаюсь понять концепцию здесь с примером, упомянутые выше случаи являются случайными, а не фактическими. Было бы здорово, если бы кто-то мог помочь мне понять концепцию с помощью «простого» примера, если они не хотят использовать приведенный выше пример.

Answer 1

Что вы указали выше (список шагов для составления списка) является алгоритмом.

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

int n = N/2; 
int m = N-n; 
return 1 + n * 3 + m * 5; 

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

Answer 2

Ну, в примере, который вы дали, вы не можете быть намного быстрее. Вы должны вывести весь список, и алгоритм, который вы описали, делает это эффективно.

Позволяет немного изменить проблему: вы просто выводите первую терру, чем 1000000. Это можно решить умнее, чем генерировать весь список.

Answer 3

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

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

Вы хотели бы использовать их, потому что

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

Что касается номера 1 al поэтому есть некоторые математические расчеты, так как для измерения эффективности алгоритма вы должны сделать некоторые вещи, которые лучше объясняются. here

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

Answer 4

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

Вышеупомянутые шаги в вашем вопросе указывают, что список должен быть построен, но что тогда? Если бы вы просто отбросили результаты (вы могли бы легко написать такую ​​программу или функцию), хороший оптимизатор (человек или машина) мог бы заменить нулевую или пустую программу или функцию на основании того, что результат никогда не используется. (Серьезно: это общая проблема в тестах, алгоритм вычисляет некоторый результат для измерения производительности сгенерированного кода, но этот результат не используется, поэтому компилятор удаляет потенциально целые циклы, выделения памяти, возможно целые функции!)

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

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

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

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

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

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

В частности, этот дополнительный контекст принимает форму явного оператора return (или какого-либо другого внешне видимого побочного эффекта, такого как изменение глобальной переменной).

И, кроме того, некоторые из этого дополнительного контекста могут принимать форму другого алгоритма, который включает, вызывая или составляя (с исходным алгоритмом, представляющим интерес); следовательно, процесс оптимизации рекурсивный и дает лучшие результаты, тем больше (человек или машина) может «видеть».