Русская Википедия:Целочисленная сортировка

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Плохой перевод Шаблон:Викифицировать Целочисленная сортировка — задача сортировки некоторого набора значений при помощи целочисленных ключей. Алгоритмы целочисленной сортировки можно применять и для задач, в которых ключами являются числа с плавающей запятой или текстовые строкиШаблон:Sfn. Возможность выполнения целочисленных арифметических операций над ключами позволяет алгоритмам целочисленной сортировки быть во многих случаях быстрее, чем аналогичные алгоритмы сортировки с использованием сравнений, в зависимости от допустимых в модели вычислений операций и величины чисел-ключей.

Обычные алгоритмы целочисленной сортировки: корзинная сортировка, поразрядная сортировка, сортировка подсчётом широко распространены и эффективныШаблон:SfnШаблон:Sfn. Дальнейшие исследования алгоритмов целочисленной сортировки были направлены на теоретические улучшения худшего случая, а алгоритмы, которые были получены, не считаются эффективными для современных 64-битных компьютеров, хотя эксперименты показали, что некоторые из этих методов могут быть лучше поразрядной сортировки данных со 128 и более битами на ключШаблон:Sfn. Кроме того, для больших наборов данных почти произвольный характер доступа к памяти алгоритмов целочисленной сортировки является ограничением, особенно в сравнении с другими алгоритмами сортировок, которые были разработаны с учётом иерархичной структуры памяти.

Целочисленная сортировка используется в одном из шести эталонных тестов в наборе DARPA High Productivity Computing Systems Discrete Mathematics и в одном из одиннадцати критериев NAS Parallel Benchmarks suite[1].

Модели вычислений

Временны́е ограничения алгоритмов целочисленной сортировки обычно зависят от трех параметров: <math>n</math> — количество значений данных, которые должны быть отсортированы, <math>K</math> — порядок величины максимально возможного ключа и <math>W</math> — число бит в машинном слове компьютера, на котором алгоритм будет выполняться. Как правило, полагается, что <math>W \geqslant \log_2 \max(n, K)</math>, то есть, машинные слова достаточно большие, чтобы представлять как индекс в последовательности входных данных, так и ключШаблон:Sfn.

Алгоритмы целочисленной сортировки, как правило, разрабатываются для работы либо для Шаблон:Нп3, либо для машины с произвольным доступом к памяти. Основное различие этих моделей заключается в том, что машины с произвольным доступом позволяют использовать произвольное значение в регистре в качестве адреса памяти в операциях чтения и записи с единичной временно́й стоимостью, а сложные манипуляции с данными организовать с помощью таблицы поиска. Модель машины указателей позволяет доступ к памяти только через указатели, которыми нельзя манипулировать путём арифметических операций. В обеих моделях побитовые операции могут быть выполнены, как правило, за один квант времени. Различные алгоритмы целочисленной сортировки делают разные предположения о том, можно ли выполнять целочисленное умножение за один квант времениШаблон:SfnШаблон:Sfn. Могут рассматриваться и более специализированные модели вычислений, такие как параллельные машины с произвольным доступомШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.

В 1999 году показано, что в некоторых случаях умножение или табличный поиск, необходимый для некоторых алгоритмов целочисленной сортировки, можно заменить на специализированные операции, которые могут быть легко реализованы аппаратными средствами, но обычно недоступны на компьютерах общего назначенияШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ DARPA HPCS Discrete Mathematics Benchmarks Шаблон:Wayback, Duncan A. Buell, University of South Carolina, retrieved 2011-04-20.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Целочисленная_сортировка&oldid=11279809