эффективность / алгоритмы против системных спецификаций

Question

Мы все говорим об эффективности алгоритмов, и в основном это зависит от размера ввода.

Как насчет системных спецификаций текущего компьютера, на котором работает алгоритм? Имеет ли какое-либо значение запуск другого алгоритма сортировки в Core 2 Duo 2,6 ГГц, 4 ГБ RAM-компьютере или в P-2, 256 МБ RAM-компьютере?

Я уверен, что должна быть разница в производительности. Но я хочу знать, какова реальная связь между алгоритмами и спецификациями системы ...

Answer 1

Повышение производительности оборудования даст вам постоянное C-кратное время работы вашего алгоритма. Это означает, что если у вас есть компьютер A, который в 2 раза медленнее, чем компьютер B. Чем ваш алгоритм будет работать в два раза быстрее на компьютере B. Тем не менее, в два раза быстрее, хотя на самом деле вряд ли имеет значение, если рассматривать большие входные значения для алгоритма.

В большой записи O , то есть у вас будет что-то вроде O (n) по сравнению с C O (n) = O (c n) = O (n) , Сложность алгоритма и общее время выполнения для больших значений будут примерно одинаковыми как на компьютере A, так и на компьютере B.

Если вы проанализируете время выполнения алгоритма, используя что-то вроде большой O-нотации, то у вас будет гораздо лучшее представление о том, как алгоритм действительно работает. Производительность компьютера не даст вам никакого преимущества, если вы сравниваете алгоритм O (logn) по сравнению с O (n ^ 2).

Взгляните на некоторые значения данных для n:

Я предполагаю, что для медленного компьютера - 1 секунда на операцию, а для быстрого компьютера - 2 операции в секунду. Я сравню лучший алгоритм с медленным компьютером с худшим алгоритмом с быстрым компьютером.

для n = 10:

Алгоритм 1: O (logn): 4 операции Медленный компьютер: 4 секунды

Алгоритм 2: O (n ^ 2): 100 операций Быстрый компьютер: 50 секунд

для n = 100:

Алгоритм 1: O (logn): 7 операций Медленный компьютер: 7 секунд

Алгоритм 2: O (n ^ 2): 10000 Операции Быстрый компьютер: 1,4 часа

большая разница

для n = 1000:

Алгоритм 1: O (logn): 10 операций Медленный компьютер: 10 секунд

Алгоритм 2: O (n ^ 2): 1 000 000 Операции Быстрый компьютер: 5,8 дней

Огромная разница

---

С увеличением n разница становится все больше и больше.

Теперь, если вы попытались запустить каждый из этих алгоритмов на более быстром / медленном компьютере для большого размера ввода. Это не имеет значения. Руки вниз O (logn) будет быстрее.

Answer 2

Мне не нравятся ответы Брайана Бонди и Чими ...

Возможно, это из-за того, что я начал в другую эпоху, когда 32 КБ считалось большим объемом памяти, а на большинстве "персональных компьютеров" было 8 КБ, и что теперь я работаю в научных вычислениях, где самые большие наборы данных обрабатываются в некоторых из крупнейших систем в мире с тысячами узлов обработки и, казалось бы, невероятные объемы хранения. Поэтому я не упускаю из виду некоторые другие элементы вопроса.

Размер набора данных имеет фантастическое значение. Большинство всех ответов на этот вопрос до сих пор игнорируют это и работают для очень небольших чисел N. Все остальные, кто ответил, предположили, что «все это умещается в памяти» или что-то подобное.

Для больших наборов данных в игру вступают другие факторы, и «большой» зависит от того, какие ресурсы вы должны использовать для решения своей проблемы. Современные системы имеют возможность автономного хранения (например, DVD-дисков), сетевого хранения (например, nfs), оперативного хранения (например, последовательного ATA) и двухуровневого хранения памяти, основной памяти системы и кэш-памяти на кристалле. Какое значение имеют заемные средства и чем больше набор данных, тем больше они имеют значение. Вам может понадобиться, а может и нет, спроектировать доступ к ним в своем «алгоритме», но если вы это сделаете, это действительно имеет значение!

По мере того, как вы увеличиваете масштаб за какой-то конкретный момент - предел одного ЦП и его локальной памяти примерно равен - эти другие факторы становятся все более значительным фактором в накладных расходах рабочей нагрузки. Когда я был Digital, мы сделали одну из первых реальных коммерческих работ на многопроцессорных системах, и я помню, как проводил тест, который показал, что использование одного CPU в качестве одного «блока» возможностей рабочей нагрузки CPU, второго CPU (в тесно связанная система) даст вам в общей сложности около 1,8. То есть второй процессор прибавил около 0,8. В трех случаях увеличение упало примерно до 0,6, а в четырех оно упало намного больше, примерно до 0,2, что в сумме составило около 2,6 для четырехпроцессорного устройства, хотя у нас были некоторые проблемы с сохранением хороших чисел в четырех процессорах из-за других эффектов. (усилия по измерению стали большой долей дополнительного ресурса). ... Суть в том, что многопроцессорные системы не обязательно были такими, какими они были взломаны - в четыре раза ЦП НЕ дает вам в четыре раза больше вычислительной мощности, хотя теоретически вы получаете в четыре раза больше флопов. ... Мы повторили работу над чипом Alpha, первым в истории многоядерным процессором, и результаты оказались довольно хорошими. Конечно, могли бы быть оптимизации, чтобы улучшить долю каждого дополнительного процессора, и, конечно, с тех пор было проделано много работы, чтобы более разумно разделить вычислительные потоки, но вы никогда не достигнете 100% от каждого нового. Частично потому, что все они замедляют некоторые (дополнительные издержки) для координации.

Небольшое междометие - у нас была поговорка об этой работе: "Верни все важные вещи в компилятор!" RISC, понял? Это произошло потому, что сам компилятор должен был организовать рабочую нагрузку, чтобы конкурирующие потоки не наступали друг на друга!

В конечном итоге выполнение обработки действительно массивного перехвата данных требует действительно разумной стратегии перемещения данных из удаленного хранилища данных в локальную память и из нее. И разделение труда в алгоритме абсолютно необходимо. В работе, которую я выполнял с Роберто Мечосо в Калифорнийском университете в Лос-Анджелесе, занимался моделированием глобальной циркуляции, у них был проект брокера данных, который иллюстрирует попытки людей сделать большую работу. Честно говоря, результат был не так хорош, как мог бы, но идеи дизайна, которые в него вошли, заслуживают изучения. ... Предполагая, что вы рассматриваете эту часть своего "алгоритма" - а не только часть, где все сводится к минимуму, управление алгоритмами ресурсами является одним из наиболее важных аспектов разумного, если не оптимального использования ресурсов при выполнении существенных вычислений.

... Надеюсь, это поможет ответить на ваш вопрос.

Answer 3

Одна вещь, не затронутая до сих пор, состоит в том, что алгоритмы часто описываются в терминах скорости, например O (n), O (n log (n)) и т. Д. ... но они также имеют характеристики с точки зрения использования ресурсов, где улучшенная скорость, скажем, O (n) по сравнению с O (n log (n)), составляет стоимость гораздо большего использования памяти. В современных компьютерах по мере истощения ресурсов их обычно заменяют более медленными, например, более крупными. замена памяти на диск, где медленный ресурс на несколько порядков медленнее. Таким образом, когда мы строим график производительности нашего алгоритма в зависимости от времени и ожидаем, что прямая линия, n log n кривая и т. Д., Мы часто видим всплески для больших значений n, когда память перегружается. В этом случае разница между 1 ГБ и 2 ГБ ОЗУ может быть огромной, поэтому с практической точки зрения ответ на ваш вопрос - да, Спецификация системы очень важна , а выбор алгоритмов требует знаний спецификации системы и размера входных данных .

Например, я разрабатываю программное обеспечение для моделирования и анализа поверхностей, и я знаю, что мои программы хорошо работают на 32-битной системе XP для моделей TIN с 4 миллионами точек. Разница в производительности между 3,5 и 4 миллионами очков незначительна. При 4,5 млн. Баллов снижение производительности настолько серьезное, что программное обеспечение не работает.

Answer 4

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

Но когда вы выполняете анализ алгоритмов, вы часто игнорируете постоянные факторы, подобные этому, и это единственное, что делает нотация big-O. Так что пузырьковая сортировка - это O (n ^ 2), а быстрая сортировка - это O (nlogn) (в среднем случае), и это не имеет значения, независимо от того, насколько быстро ваше оборудование.

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

Если вы хотите начать такое сравнение, вам нужно сделать две вещи вместе: определить алгоритмическую сложность, включая постоянные факторы, и разработать скоростную модель (например, сколько итераций конкретного цикла он может выполнить в секунду) для фактическое оборудование, на котором вы работаете. Одна из интересных вещей в Искусстве компьютерного программирования Кнута, по сравнению с другими книгами по алгоритмам, заключается в том, что он делает оба, так что для каждого проверяемого алгоритма он вычисляет, сколько единиц времени выполнения потребуется для заданного размера ввода на его (мифическом) компьютере MIX. Затем вы могли бы скорректировать вычисления для более быстрого или медленного оборудования - то, с чем нотация big-O не помогает.

Answer 5

Но я хочу знать, что является настоящим связь между алгоритмами и технические характеристики системы ...

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

• Лучшая система (= быстрее ЦП, больше ОЗУ) работает быстрее, а худшая (= медленнее ЦП, меньше ОЗУ) работает медленнее. Тот же алгоритм (независимо от того, хорош он или плох), скорее всего, будет работать быстрее в лучшей системе и медленнее в худшей.

• Более быстрый алгоритм работает быстрее, чем более медленный. Он будет работать быстрее в более медленной системе и быстрее в более быстрой системе.

Так в чем же конкретно заключался ваш вопрос? Является ли ваш вопрос «Нужен ли нам быстрый алгоритм, если система уже такая быстрая? Да, может быть. Но в этом случае я бы задал два вопроса:

1. Зачем выбирать медленный алгоритм только потому, что система быстрая? Таким образом, ваш код будет работать только на приличной скорости в очень быстрой системе. Если вы выберете быстрый алгоритм, ваш код может даже работать на приличной скорости в гораздо худшей системе.

2. Зачем пытаться намеренно достичь худшей производительности? Даже если плохой алгоритм может быть запущен в течение пяти секунд, что вы считаете достаточно быстрым на быстрой машине, хороший алгоритм может работать за 100 миллисекунд. Так почему же заставить вашу программу выполнить задачу за 5 секунд, она может выполнить точно такую ​​же задачу за 100 миллисекунд?

На самом деле, это номер пункта (2), который действительно часто доставляет мне неприятности. Очень часто люди говорят: «Эй, не переусердствуйте, это не будет иметь большого значения. Этот код - такая маленькая система в такой большой системе». Да, если вы просто посмотрите на этот код изолированным, это правда. Но есть поговорка: «Много микла делает гадость». Конечно, вы должны оптимизировать наиболее ресурсоемкие части в первую очередь. Однако, если система состоит из 100 модулей, и каждый из них использует только один процент процессорного времени, оптимизация одного из них для увеличения его в два раза приведет к общему увеличению времени обработки на 0,5%, почти ничего; Вот почему большинство людей воздерживаются от этого. Но люди упускают из виду то, что оптимизация всех этих процессов в два раза быстрее приведет к увеличению времени обработки на 50% (или, следовательно, приложение будет работать в два раза быстрее в целом).

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

Answer 6

Да. Помните, что с начала 80-х мы подскочили на 4 порядка. (1 МГц, 10 МГц, 100 МГц, 1000 МГц). Но это только разница между n = 10 и n = 10000 с точки зрения размеров набора данных. Я могу купить терабайтный жесткий диск ... больше 6-7? порядков, чем мой старый 20-мегабайтный диск.

Там гораздо больше данных, плавающих вокруг, чем вычислительная мощность. Так что, хотя вы можете быть озадачены тем, насколько полезен big-O при n = 50, n = 500 видов размеров ... когда n = 1000,00, вы хотите минимизировать n настолько, насколько сможете. Что-нибудь сверхлинейное просто грубо для вашей вычислительной мощности ... неполиномиальное еще хуже. Это распространяется от верхней части системы до нижней части. Таким образом, эффективность важна, как только вы справляетесь с реальными размерами наборов данных.

Позвольте привести пример.

Я занимался проектированием базы данных для младших классов. К концу у меня было, может быть, 5 таблиц с 20-40 заранее определенными категориями. Добавлены строки, 10, 20 строк. Ничего страшного. Я был одержимым Я сделал это на PHP, а не на Perl. Я был все это и мешок с 'чипсами .

Перейдите сейчас, через несколько лет. Я занимаюсь хобби проектом по изучению фондового рынка. Я собираю данные с финансового сайта каждый день - 6100 акций, около 10 столбцов на каждом складе. Тридцать тысяч + строк в неделю. Мой первоначальный дизайн был «нормализован», со статическими данными и динамическими данными в разных таблицах. Когда я поиграл со своими запросами, узнав о вещах, если бы я сделал плохое объединение, я буквально сломал бы свой сервер и сделал бы его недоступным. Так что я денормализовал. Мой следующий этап - пометка и начало фактического майнинга. Я не планирую делать серьезные прогнозы до Рождества; примерно 11x30K = 330K строк для добычи и анализа. Эффективность алгоритма будет иметь значение , если я хочу, чтобы мои данные обрабатывались своевременно. Не имеет значения, если бы мой процессор был в 10 раз быстрее ... если бы я использовал алгоритм N ^ 2, он был бы выполнен только в 2 раза быстрее. : -)

Answer 7

Имеет ли какое-либо значение запуск другого алгоритма сортировки в Core 2 Duo 2,6 ГГц, 4 ГБ RAM-компьютере или в P-2, 256 МБ RAM-компьютере?

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

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

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

Answer 8

Помните об особенностях языка, на котором вы реализуете свой алгоритм.

Например, в мире Java, как показано в этой статье , более быстрый компьютер не всегда означает более быстрое выполнение:

Та же Java-программа на компьютере с одним процессором может работать намного быстрее, чем на многопроцессорной / многоядерной машине !!

Answer 9

По вашему вопросу вы хотите спросить, почему эффективность алгоритма описывается только с точки зрения размера ввода?

Алгоритмы обычно описываются с использованием Big O Notation . Эти обозначения описывают асимптотическое поведение алгоритма; он описывает поведение, когда входные данные очень очень большие.

Так, например, у нас есть два алгоритма сортировки.

1. Algo # 1 с O (n)
2. Алго № 2 с O (n ^ 2)

А давайте возьмем два ПК:

1. ПК1
2. ПК2 в 100 раз быстрее, чем ПК1

И у нас есть две установки:

1. ПК1 под управлением Algo # 1
2. ПК2 под управлением Algo # 2

Когда n очень очень велико (например, миллиарды?), ПК1 все равно побьет ПК1:)

Answer 10

Конечно, да. При высокой загрузке ЦП время выполнения уменьшится.
Аналогично с более высокой памятью, время, необходимое для обмена данными (если применимо), определенно уменьшится.