К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 47
Текст из файла (страница 47)
Все равно он будет обрабатывать данные на пару порядков быстрее. Впрочем, ведь далеко не всегда сортируемые данные используют весь диапазон значений сзг: от — 2 147 483 648 до 2 147 483 647. А раз так, то потребности в памяти можно существенно сократить! Действительно, количе- СТВО трЕбуЕМОй ПаМятИ СОСтаВЛяЕт: С е = Х ЧХЬ* ст! Ш1, ГдЕ я ЧХЬ— КОЛИЧЕСТВО дОПуСтИМЫХ ЗНаЧЕНИй, а ьсе ассы! — раЗМЕр ЯЧЕЕК, ХраНящИХ "зарубки" (они же — дубли). В частности, для сортировки данных диапазона гзв Глава г [О; ! 000 000) потребуется не более 4 Мбайт памяти. Это весьма незначи- тельная величина! Сортировка вещественных типов данных До сих пор мы говорили лишь о сортировке целочисленных типов данных, между тем программистам приходится обрабатывать и строки, и числа с плаваюшей запятой, и...
Первоначально предложенный мной алгоритм действительно поддерживал работу лишь с целыми числами, но после публикации статьи "Немного о линейной сортировке" (ее и сейчас можно найти в Интернете) им заинтересовались остальные программисты, среди которых были и те, кто приспособил линейную сортировку под свои нужды. В частности, линейную сортировку вешественных чисел первым (насколько мне известно) реализовал Дмитрий Коробицын, письмо которого приводится ниже: — — - — — - Ог)я)па! Меззаяе — — — — - —-- ггопп "Дмитрий Коробицын" <дч)г©пгкгц> То: "Крис Касперски" <)г)гйзепоша)!.гп> бепп ггЫау, )цпе 22, 200! 2:27 АМ ЗпЬ)есп Ке: О линейной сортировке ДК> Сегодня хочу написать про сортировку чисел г)оак ДК> Вы пишете: КК» Один только нюанс — как отсортировать числа по возрастанию? Формат КК» йоаг и г)ооЫе не сложен, но попробуй-ка вывести все числа в порядке КК» возрастания! Да, действительно для сортировки чисел г)оа! придется построить функцию 1олд аое г ~г1ое1 ю, такую, чтобы для любых х и у, если х < у, то Г(х) < Г(у).
Не вызывает сомнения, что такую функцию построить можно, но весь вопрос в том, насколько она сложна и сколько шагов потребуется от компьютера для ее реализации? Сразу оговоримся, что трудоемкость этой функции от размера массива чисел не зависит, следовательно, это константа, и на трудоемкость всего алгоритма она повлиять не сможет. Он так и останется линейным. Чтобы сильно не злоупотреблять вашим вниманием, забегая вперед, хочу сразу сказать„что эта функция очень простая.
Проше не бывает. Это "функция правды", как вы назвали ее в одной из своих статей, а Оперативная память гЗ7 Следовательно, в памяти это будет выглядеть так: старшие два бита равны О, остальные 1. У второго числа показатель степени двойки равен 1, а значение мантиссы равно О. Смещенный порядок = 128 = 1000 0000. В памяти все биты кроме второго равны О. Г1оат Лелае число Шестнаднат. ОхЗГ ГГ ГГ ГГ 1073741823 1.99999988079071044921875 Ох40 00 00 00 1073741824 2.0 Еще несколько чисел: Лелое число Г1оал 0.100000001490116119 0.200000002980232239 0.300000011920928955 0.400000005960464478 шестнаддат.
ОхЗО СС СС СО 1036831949 Охэв 4С СС СО 1045220557 Ох38 99 99 9Л 1050253722 ОхЗВ СС СС СО 1053609165 именно 1(х) = х„ т. е. преобразовывать ничего не нужно. Нужно просто компилятору указать, что в этих ячейках лежит не число 61 1, а функция 1олд 1лл. Доказательство: Р!оаг устроен следуюшим образом: 32 бита в памяти, самый старший бит это знак, то же и у 4-байтового целого числа.
После бита знака следуюшие 8 битов "смещенный порядок" — показатель степени двойки. Для положительных чисел йоаг, чем больше порядок, тем больше число, но, с другой стороны, для положительного длинного целого, чем большее число записано в старших битах, тем число больше. Оставшиеся 23 разряда — это значащая часть числа, мантисса. Значение положительного числа йоа1 получается следующим образом: Значение = (1+ мантисса*2"( — 23)) * 2"(смещенный порядок — 127).
Здесь следует пояснить, что если мантисса равна нулю, то значение числа йоа1 совпадает со степенью двойки. Если все биты мантиссы установлены в 1 (самая большая мантисса = Ох7РРРРР = 2 23 — 1), то получаем 1 + + Ох7РРРРР42" (-23) = 1,99999988079071044921875. Получаем, что для положительных йоа1 при одинаковом значении "смешенного порядка" чем больше мантисса, тем больше число, но лля длинного целого та же ситуация, при одинаковых старших битах, чем большее значение записано в младших битах, тем больше число.
Рассмотрим еще ситуацию, когда при увеличении числа меняется "смегценный порядок". Возьмем для примера числа 1,99999988079071044921875 и 2,0, оба этих числа положительные, значит старший бит равен нулю. У первого показатель степени двойки равен О, значит "смещенный порядок" = 127 = 0111 1111. Мантисса состоит вся из 1.
Глава 2 гвв ОхЗГ 00 ОО 00 1056964608 0.5 ОхЗГ 19 99 9А 1058642330 0.60000002384185791 ОхЗГ 33 ЗЗ 33 1060320051 0.699999988079071045 ОхЗГ 4С СС СО 1061997773 0.800000011920928955 ОВЗГ 66 66 66 1063675494 0.89999997615814209 ОхЗГ 80 00 ОО 1065353216 1.0 Ох40 ОО 00 ОО 1073741824 2.0 Ох40 40 00 00 1077936128 3.0 Ох40 80 00 00 1082130432 4.0 Ох40 АО ОО ОО 1084227584 5.0 Ох40 СО 00 00 1086324736 6.0 Ох40 ЕО 00 00 1088421888 7.0 Ох41 ОО 00 00 1090519040 8.0 Ох41 10 ОО 00 1091567616 9.0 Ох41 20 00 ОО 1092616192 10.0 Из приведенной записи видно, что при возрастании числа боаб возрастает и соответствуюшее ему целое число. Заметим, что целое число ноль соответствует нулю с плаваюшей точкой. Таким образом, для неотрицательных чисел никакого преобразования не требуется.
Как же быть с отрипательными числами? Отрицательные целые числа хранятся в дополнительном формате, т. е. целому числу минус один соответствует Охгг гг ГР гг, а это самое большое по модулю отрицательное число (в действительности компьютер считает, что зто "не число").
Числу минус десять миллионов соответствует боаб, примерно равный — 341038. Беотналаат. делое ххоло т1оаб -3.07599454344890991е38 ОхГГ 67 69 80 -10000000 ОхГА ОА 1Г 00 -100000000 -1.792М430293879854е35 ОхС4 65 Зб 00 -1000000000 -916.84375 ОхСО 00 ОО 00 -1073741824 -2.0 ОхВГ ВО ОО 00 -1082130432 -1.0 ОхВГ ОО 00 00 -1090519040 -0.5 ОХАВ 97 01 00 -1500000000 -1.05343793584122825е-15 Ох88 СА ВС 00 -2000000000 -1.21828234519221877е-33 Из приведенной записи видно, что чем больше по модулю отрицательное целое число, тем меньше по модулю число йоап Неужели придется проверять знак у числа, и если оно отрицательное, то делать преобразование? На самом деле нехитрым программистским приемом избавляемся от всяких преобразований. Сначала прейдем от целых чисел со знаком к целым чис- 939 Оперативная память лам без знака.
При этом преобразования не потребуются, просто область памяти вместо функции 1опд гпг Надо Онрсдсднтв Как ппягдпеб 1оп Ь (Заметим, что на сортировку положительных чисел это никак не повлияет.) Далее заметим, что самому большому по модулю отрицательному числу йоа( вместо — 1 теперь будет соответствовать ОхГГ ГГ ГГ Гà — это (211) — 1. Таким образом, самое большое целое число без знака будет соответствовать самому большому по модулю отрицательному числу.
Но если теперь у нас все целые числа не имеют знака, то как же отделить положительные боа[ от отрицательных? Потребуются преобразования? Нет! Пример программы напишем в виде функции, которой на вход передается неотсортированный массив йоа[ и его размер — п. После работы функции массив должен быть отсортирован по возрастанию.
ча1С Вост(11оат *ц, цпя1дпеа 1опд Н) цпя1дпеб 1опд *а,*гпт ц, с, и, Ргерагенеи(яа)( // преобразуем указатель. Предполагая, что ягзеот(11огт) = яггеог(1опд) гпт ц-(опя1дпеа 1опд *)ц) О сортировка бог (с=с( с < и( с-н-) а[1пт ц[с])чь( // Формируем отсортированный массив К=О; // сначала отрицательные числа, начиная с самых белесых по модулю Рог(с=охгггггггю с > Охтггггггг) с †) гог(п О( и < а[с)) пи-)1пг ц(кет)=с) // теперь положительные числа, начиная с (11оаг) нуля.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
