Время - сортировка
Cтраница 3
Существует несколько методов сортировки, реализованных в виде программ (2.2.5), которыми располагает ВС. Критерием эффективности (2.2.6) сортировки массива Р / с помощью алгоритма AI является, например, время сортировки. Если поток поступающих на сортировку массивов имеет некоторую статистическую устойчивость в виде плотности распределения р ( Р) и для этого распределения имеется наилучший метод А сортировки, то естественно найти такой метод, используя альтернативную адаптацию. [31]
Главное в случайных событиях, к которым сводятся неупорядоченные процессы - неопределенность их исходов. Степень неопределенности исходов этих событий ( процессов) может быть различная: одна при появлении детали с положительным или отрицательным допуском во время сортировки равного количества деталей с одним и другим знаком допуска ( в данном случае необходимо определить, какому полю допуска положительному или отрицательному соответствует конкретная деталь), другая, более высокая, при установлении истинных размеров детали. [32]
Создание быстрой сортировки по принципу один процессор для каждой порции неприемлемо как с точки зрения интересов сортировки, так и с точки зрения пропускной способности системы. Допустим, что две 32-процессорные системы могут выполнить 4032 сравнений за то же время, за какое один процессор выполнит 126 сравнений. Время сортировки, требующей 4000 сравнений ( по 125 на один процессор), может быть меньше, чем у быстрой сортировки, требующей в целом 384 сравнения. [33]
Почвенный образец доводят до воздушносухого состояния и сортируют через сита с отверстиями 3, 1 и 0 25 мм. Во время сортировки снизу набора сит ставят поддонник, а сверху набор сит закрывают крышкой. [34]
 |
Укладка трубы на плазе ( плазировка трубы. [35] |
Операция указанной проверки называется плазировкой. Для удобства плазировки все трубы поверхностей нагрева, поступающие на монтаж в виде россыпи, сортируются по позициям, указанным в чертежах. Во время сортировки трубы одноименных позиций раскладываются в отдельные штабеля. [36]
Наиболее серьезным недостатком является ее очень быстрое замедление, когда число сортируемых элементов становится большим. Таким образом, зависимость времени сортировки от числа сортируемых элементов является квадратичной: увеличение вдвое требует четырехкратного увеличения времени. [37]
Время сравнения зависит от способа кодировки ключей и от доступности и временных характеристик команд сравнения для различных видов данных. Если нет команд десятичного сравнения, то может потребоваться преобразование в чисто двоичный вид. Время, необходимое для преобразования ключей, добавляется к времени сортировки. [38]
Это дерево описывает структуру разделения для двоичной быстрой сортировки, соответствующей рис. 10.2 и 10.3. Поскольку нет гарантии того, что какие-либо элементы займут свои окончательные позиции, ключи соответствуют внешним узлам дерева. Такая структура обладает следующим свойством: продвигаясь по пути от корня к конкретному ключу, принимая О за левую ветвь и I за правую ветвь, получаем значения старших разрядов этого ключа. Именно эти значения и отличают данный ключ от всех остальных во время сортировки. В условиях рассматриваемого примера это может случиться только в окрестности нижнего уровня дерева, однако возможно и на более высоких уровнях: например, если I или Хв число таких ключей не входили, то их узлы на чертеже будут заменены нулевым узлом. [39]
 |
Эмпирическое исследование вариантов быстрой сортировки. [40] |
В этой таблице представлена относительная стоимость нескольких различных вариантов быстрой сортировки на примере упорядочения первых N слов из книги Moby Dick. Непосредственное использование метода вставки для сортировки небольших подфайлов или игнорирование небольших подфайлов с последующей сортировкой того же файла методом вставки потом - суть стратегии, обеспечивающие один и тот же уровень эффективности, но в то же время экономия расходов, достигаемая за счет реализации обоих стратегий несколько ниже, чем для целочисленных ключей ( см. табл. 7.1), поскольку стоимость операции сравнения строк влечет большие издержки. Есяи во время разбиения файлов просмотр не останавливается на дублированных ключах, то время сортировки файла, у которого все ключи одинаковы, подчиняется квадратичной зависимости; низкая эффективность проявляется в этом примере в связи с тем, что существует множество слов, которые встречаются в данных довольно часто. По той же причине разделение на три части обеспечивает высокий уровень эффективности сортировки; она на 30 - 35 процентов быстрее системной сортировки. [41]
Способ увеличения сложности состоит, по-видимому, в сортировке элементов и использовании бинарного поиска для локализации знаков. Однако если определения чаще, чем все сразу, появляются в непредсказуемые моменты, то сортировку необходимо производить всякий раз при появлении определения. Время поиска для такой таблицы пропорционально логарифму длины таблицы, если можно пренебречь временем сортировки, что справедливо, когда число обращений к программе LOOKUP существенно больше, чем к INSTALL. Такой вариант поиска осуществляется быстрее, но он более сложен. [42]
Кроме того, измените программу так, чтобы проходы по массиву прекращались, если при очередном проходе не было произведено ни одной перестановки. Это означает, что элементы массива уже упорядочены. Преимущество этого изменения ( его можно реализовать с помощью индикатора) состоит в том, что время сортировки, вообще говоря, уменьшается. [43]
 |
Обменная сортировка. [44] |
Метод пользуется необоснованной славой из-за своего уменьшительно-ласкательного названия, однако по сравнению с методом вставок и методом выбора он имеет меньшую эффективность. Число шагов просмотра с обменом оказывается не более ( п - 2), и, из-за того что легкие элементы всплывают по нескольку сразу, кажется, что это сильно уменьшает затраты на сортировку. Но с другой стороны, тяжелые элементы, такие, как 9, если они находятся наверху, перемещаются вниз последовательно по одной позиции при каждом шаге, что увеличивает время сортировки. Число обменов оказывается довольно большим. [45]
Страницы: 1 2 3 4