Последний вариант программы Эппеля решал задачу меньше чем за день, то есть в 400 раз быстрее, чем первый. С тех пор его методы использовались многими физиками. В нашем кратком пересказе его статьи будут пропущены многие важные детали, за которыми вам следует обратиться к упоминавшейся книге Пфалз- нера и Гиббона. Самое главное, что огромное увеличение производительности было достигнуто благодаря многоуровневому подходу.
Алгоритмы и структуры данных
Прежде всего Эппель занялся поисками подходящего алгоритма. Ему удалось уменьшить затраты на выполнение одного шага по времени с 0(п2) до 0(n\ogn)[ благодаря выбору правильного представления объектов на бинарном дереве, где объекты верхнего уровня представляли собой кластеры физических объектов. Сила, действующая на конкретный объект, может вычисляться как сумма сил,
' Запись 0{п2) можно понимать как «пропорционально п2 ». Выражения типа 15/;2+ 100/7 и п21 2-10 могут быть отнесены к этму классу. Формально запись /(я) = 0(g(/i)) означает, что существуют такие значения констант с и я0, для которых f(n)<cg(n) при любом п>па Точное определение можно паи гн в учебниках по теории алгоритмов и дискрет пои математике, а в разделе 8.5 (см. главу 8) иллюстрируется важность этого понятия в процессе разработ ки алгоритмов действующих на него со стороны больших кластеров. Эппель показывает, что это приближение не вносит погрешностей в модель. Дерево состоит из log2 п уровней, а получающийся алгоритм с временем выполнения 0(п ]og2 п) близок по духу алгоритму «разделяй и властвуй» из раздела 8.3. Правильный выбор структуры данных уменьшил время выполнения исходной программы примерно в 12 раз.
Опубликовал vovan666
April 16 2013 23:59:13 ·
0 Комментариев ·
3987 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
