Дополнительное пространство - память
Cтраница 1
Дополнительное пространство памяти для вспомогательного массива не представляют собой сколь-нибудь серьезной проблемы в условиях многочисленных приложений поразрядной сортировки применительно к длинным ключам или записям, поскольку для этих типов данных успешно применяется сортировка по указателю. [1]
Дополнительное пространство памяти JUUE немом о ГУ тельного надеина не представляют собой с коль-мм будь серьезной проблемы в условиях многоч меленных tip ил ожени и поразрядной сорт) фо & кн прнменнт аьно к шгпнпым ключам или запнся. [2]
Непрямая сортировка требует дополнительного пространства памяти для размещения массива индексов или массива указателей и дополнительного времени для выполнения операций непрямого сравнения. Во многих приложениях эти затраты являются вполне оправданной ценой за гибкость и возможность вообще не затрагивать записи. В случае файлов, состоящих из больших записей, мы практически всегда будем пользоваться непрямой сортировкой, а во многих приложениях часто происходит так, что вообще нет необходимости перемещать данные. В рамках этой книги обычно применяется прямой доступ к данным. Однако в некоторых приложениях все-таки придется воспользоваться массивами индексов и указателей во избежание перемещения данных; именно в силу этих причин мы и остановились здесь на этой теме. [3]
Реализовать абстрактное обменное слияние, использующее дополнительное пространство памяти, размер которого пропорционален размеру меньшего из файлов, подвергаемых слиянию. Ваш метод должен наполовину уменьшать потребность в пространстве сортировки слиянием. [4]
Для практической реализации в любом случае требуется дополнительное пространство памяти, так почему бы не рассмотреть возможность реализации сортировки слиянием, ориентированной на связные списки. [5]
Разработайте реализацию слияния, которое уменьшает потребность в дополнительном пространстве памяти до max ( M, N / M), воспользовавшись следующей идеей. Затем, ( /) рассматривая эти блоки как записи, первые ключи которых суть сортировочные ключи, отсортировать их, используя для этой цели сортировку выбором, и ( if) выполнить проход по массиву, выполняя слияние первого блока со вторым, затем второго блока с третьим и так далее. [6]
Для некоторых размеров файлов, рдээийжьк имеет смысл использовать дополнительное пространство памяти, которое в других случаях Будет отведено под вспомогательный массн &1 чтобы попытаться обойтись всего лишь одним проходом дла подсчета индексных ключей, выполняя переупорядочение бс: э использования дополнительной ламнтн. Например, сортировка I мнят иона 32-разрядных ключей, принимающий случайные значения, может бить кущсстБ - лена за олин проход сортировки методом подсчета индексных ключей на 20 старших разряда и последующей сортировкой методом вставки. Чтобы выполнить эту процедуру, потребуется пространство памяти только для счетчикои ( I миллион) - значительно меньше, чем нужно ллч рдзмещснин яспомогательного массива. [7]
Для некоторых размеров файлов, возможно, имеет смысл использовать дополнительное пространство памяти, которое в других случаях будет отведено под вспомогательный массив, чтобы попытаться обойтись всего лишь одним проходом для подсчета индексных ключей, выполняя переупорядочение без использования дополнительной памяти. Например, сортировка 1 миллиона 32-разрядных ключей, принимающих случайные значения, может быть осуществлена за один проход сортировки методом подсчета индексных ключей на 20 старших разрядах и последующей сортировкой методом вставки. Чтобы выполнить эту процедуру, потребуется пространство памяти только для счетчиков ( 1 миллион) - значительно меньше, чем нужно для размещения вспомогательного массива. [9]
Статистика, полученная с помощью специальных экспериментов, показывает, что результаты улучшаются также при выделении дополнительного пространства памяти для таблицы хеширования. При этом чем меньше степень заполненности таблицы, тем менее вероятны случаи переполнения. [10]
Найти эффективный метод, который ( /) переупорядочивает записи - файла таким образом, что те их них, ключи которых начинаются с бита 0, идут раньше тех записей, ключи которых начинаются с бита 1, ( / /) использует дополнительное пространство памяти, пропорциональное квадратному корню из числа записей ( или меньше того) и ( / / /) является устойчивым. [12]
Эффективное объединение двух очередей по приоритетам, по-видимому, потребует более сложной структуры данных, которая будет подробно рассматриваться в разделе 9.7. С другой стороны, представленный здесь простой метод, в основу которого положен пирамидальный порядок, вполне достаточен для большинства различных приложений. Он использует минимальное дополнительное пространство памяти и обеспечивает высокую эффективность выполнения операций за исключением тех случаев, когда часто и на больших объемах данных выполняются операции объединить. [13]
Как будет показано в разделе 8.7, сортировка слиянием также эффективна, если сортируемый файл организован как связный список. В этом случае указанное свойство сохраняется, однако для связей расходуется дополнительное пространство памяти. В случае массивов, как отмечалось в разделе 8.2, можно выполнять обменное слияние ( обсуждение этой темы будет продолжено в разделе 8.4), однако эта стратегия вряд ли оправдывается на практике. [14]
Реализация поразрядной сортировки LSD, представленная в разделе 10.5, выполняет bytesword проходов по файлу. Увеличивая R, мы получаем эффективный метод сортировки для достаточно больших 7V при наличии дополнительного пространства памяти для размещения R счетчиков. Как отмечалось при доказательстве леммы 10.5, целесообразно выбирать R таким, чтобы значение InR ( число разрядов в байте) было примерно равно одной четвертой от размера слова, так чтобы поразрядная сортировка представляла собой четыре прохода сортировки методом подсчета индексных ключей. Проверяется каждый бит каждого ключа. Этот пример является прямой аналогией организационной архитектуры многих компьютеров: в одной из типичных организаций используется 32-разрядное слово, которое, в свою очередь, состоит из 8-разрядных байтов. Мы извлекаем из слов байты, а не биты, и этот подход позволяет достичь довольно высокой эффективности на многих типах компьютеров. Теперь каждый проход процедуры подсчета индексных ключей линеен, а поскольку их всего лишь четыре, то и вся сортировка линейна - вряд ли можно надеяться на что-либо лучшее, когда речь идет о сортировке. [15]
Страницы: 1 2