Мощности компьютеров растут, но под них выпускаются все более объемистые компьютерные игры. Растет и также беззастенчиво пожирает ресурсы WINDOWS, 10-я его версия занимает почти 40 гигабайт. Далее фильмы, свои фотографии... А сколько данных на предприятиях! В общем, сколько бы места ни предоставили людям, они умудряются быстро забить всё под завязку.
Большие объемы - это и малая скорость переноса и обработки информации. А время - это деньги! Гигабайтные системы можно переписывать часами, соответственно возрастает вероятность сбоев оборудования и порчи данных в самый неподходящий момент. В больших файлах также удобнее прятаться вирусам.
Поэтому в наше время по-прежнему актуальна задача компактного хранения информации, а не только тогда, когда при малых мощностях надо было ужиматься до предела и выворачиваться наизнанку.
Очень важно, чтобы программы и операционные системы, которыми пользуются миллионы, а может быть, и миллиарды граждан, - не тратили место и время этих граждан только потому, что программные средства сделаны топорно. Увы, в основном беззастенчиво тратят ресурсы, потому что вылизывать продукцию - себе дороже выйдет. По моим оценкам WINDOWS избыточен в 10 тысяч раз, а местами до миллиона. Вот он и пыжится над каждой мелкой картинкой, а особенно задумчив при загрузке. Над чем думать-то, если еще ничего не спросили?! На самом деле все это может делаться мгновенно. Покупатели, не разбирающиеся в программировании, все равно заплатят, поскольку у них практически нет выбора.
Тем не менее, есть стандартные программные средства, которые ужимают данные не вникая в их суть. Текстовую информацию обычно удается сжать в три раза, и она примет вид абракадабры. Разумеется, для прочтения она обратно разворачивается. Графическую информацию и производственные данные удается сжать в 10, иногда в 100 раз.
А вот собственно исполняемые программы (загрузочные модули), сделанные качественно, почти не сжимаются. Ну, в крайнем случае процентов на 10. Зато некачественные программы сжимаются в сотни раз, что является ярким признаком топорности.
Намного можно повысить степень сжатия информации, если знать ее структуру и назначение. Приведу пример из своей практики. С развитием интереса к простым числам возникла проблема хранения большого их количества. В пределах одного триллиона содержится простых чисел более 37 миллиардов. Если, как в книге, хранить каждое число в виде 12 цифр плюс запятая в качестве разделителя, то всё это займет 450 миллиардов знаков, или 450 тысяч увесистых книг, что потянет не каждая библиотека и не каждый компьютер.
Числа можно хранить в двоичном коде, тогда каждое из них до триллиона займет 6 байтов, что сократит количество книг вдвое. Правда, тогда их сможет читать только компьютер.
Еще втрое можно сжать стандартными методами. Но это все равно плохо, поскольку перенос с места на место, разархивирование и просто чтение могут длиться часами. Поэтому когда 20 лет назад при более скромной технике я сообщил, что сделал хранилище простых чисел до триллиона, то первым делом специалисты поинтересовались, где я раздобыл нужное оборудование, и какие помещения оно занимает.
А занимает оно всего-то микроскопические 20 килобайт, т.е. как 10 страниц обычного текста или сотая часть фотографии далеко не высшего качества. Секрет заключается в том, что хранятся лишь некоторые ключевые сведения, а остальные быстренько досчитываются для того промежутка, который пожелал увидеть пользователь. Причем программа, досчитывающая и выдающая числа, уместилась в тех же 20 килобайтах.
Таким образом, квалифицированное использование структуры информации позволило сжать 450 миллиардов знаков до 20 тысяч, т.е. в десятки миллионов раз. При такой степени сжатия хранилище даже в 1000 раз большее (для простых чисел до квадриллиона) все еще останется небольшим и сравнимым с объемом одного хорошего фотоснимка.
Из других задач мне также удалось сделать транслятор языка в миллион раз меньше, чем Си. Причем это не игрушка, а рабочий инструмент, который позволил выпустить сотни мощных производственных систем, также в миллионы раз более компактных и в десятки тысяч раз более шустрых, чем у конкурентов, а также не требующих обслуживания от производителя. (Для сравнения: сейчас у производителей модно ежемесячно драть деньги за обслуживание.) За десятки лет уже компьютеры и операционные системы не раз поменялись, сменилось не одно поколение работников, кое-где и хозяева, а программы, разработанные четверть века назад, все пашут с по-прежнему непревзойденной никем скоростью.
Понятно, что не стоит ждать высоких технических показателей от ширпотреба, сляпанного на скорую руку большими коллективами, в которых никто ни за что не отвечает. Но не раз мне доводилось соревноваться с асами программирования, которые, по крайней мере, отдельные расчеты умеют доводить до высшего мирового уровня. Правда, у асов обычно туго с математикой, и это сильно сказывается. Я же достигал лучших показателей за счет математических методов, используя лишь малую часть ресурсов ЭВМ. Впрочем, не скажу, что в инженерных, бухгалтерских и вообще в производственных расчетах нужна особо мудреная математика. Достаточно рядовой, но профессиональной подготовки.
Приведу один наглядный пример.
В журнале "Мир ПК" за 1997 г., номер 5, инженер-программист Виталий Ланской опубликовал программу рисования фрактала Мандельбротта объемом 97 байтов (как пара строк книжного текста) и, крайне гордый своим достижением, кинул клич, мол, пусть кто-нибудь попробует сделать программу лучше, т.е. еще короче.
Надо сказать, что объемистые программы, конечно, существовали, но чтобы выдавить из них воду и довести результат до 97 байтов, - для этого надо быть классным специалистом. Поэтому Ланской счел нужным упомянуть даже о своих первоначальных вариантах в 430 и 370 байтов, которым подивились его друзья.
Некоторые мои коллеги были в курсе и пытались оптимизировать код. Кто-то даже выдавил один-два байта, но не счел свое достижение настолько эпохальным, чтобы раззванивать о нем на весь свет. Ясно, что в миллионы раз не уменьшить программу, которую уже тщательно оптимизировали. А то из 97 байтов получился бы ноль. Так что улучшение на один-два байта - это существенное достижение.
В 10-м номере журнала за тот же год подвели итоги. Поступило два решения:
Один умелец Михаил Орехов, тоже инженер-программист, поднатужившись, выдавил 5 байтов и у него осталось 92, в основном повторяющих решение Ланского. Он также с гордостью подробно описал все этапы и муки своего творчества.
Я же избрал другой подход, о котором без знания математики догадаться было трудно, и в который вообще сложно поверить, не увидев результата. В нем для явно вещественной (а не целочисленной) задачи не используются вещественные числа (так называемый сопроцессор), что даже асы расценивали как совершенно пустое дело в смысле оптимальности и вообще в плане реализации, но промахнулись. Моя версия на меньших ресурсах ПК (без использования сопроцессора) оказалась не только гораздо короче, но еще и в 7 (семь!) раз быстрее.
Вот так небольшой ловкостью рук (точнее, с нужными знаниями) можно повысить скорость на порядок, когда она уже железно считалась неулучшаемой. Не удивительно, что ее можно повысить в миллионы раз там, где никто не боролся за качество. А значит, львиная доля оборудования и времени обычно тратятся впустую, и денежки просто вылетают в трубу.
В журнале без лишних слов я выдал программу в 63 байта:
Вот фрактал Мандельбротта, нарисованный моей программой:
Для отчетности привожу коды версии, в которой мне позже удалось выкинуть еще 1 байт:
176, 19, 205, 16, 104, 0, 160, 31, 190, 128, 0, 191, 191, 254, 78, 71, 116, 249, 177, 46, 139, 234, 3, 232, 43, 208, 15, 175, 234, 114, 17, 3, 208, 247, 234, 193, 248, 5, 193, 253, 6, 19, 198, 141, 83, 127, 226, 228, 134, 15, 247, 233, 67, 117, 216, 205, 22, 213, 232, 205, 16, 195. (Всего 62 байта.)
В той же статье "Не только спортивный интерес" я рассказал о своем языке программирования с объемом транслятора в 5 килобайт, а также в свою очередь предложил всем посоревноваться на другой задачке: программке рисования линии. В моем варианте было 92 байта:
Впоследствии журнал не сообщал о достижениях умельцев, по-видимому, из-за отсутствия таковых, либо из-за слишком незначительных успехов. Но позже еще один самородок Уленгов в письме прислал мне вариант на 90 байтов, сумев-таки выжать из моей версии пару байтов. Уже более двух десятков лет программка рисования линии с поправкой коллеги успешно пашет во множестве моих программ.
Авторская публикация. Свидетельство о публикации в СМИ № J108-49624.
Обсуждения Компактное хранение информации
N - исходное целое неотрицательное число,
r - количество двоичных разрядов (четное число),
Q - для результата, R1,R2 - рабочие.
1. Полагаем Q=R2=0, k=r.
2. Уменьшаем k на 2. Если стало k<0, то конец.
Вычисляем R1=R2+Q и заносим 1 в k-й бит числа R1.
Делим Q на 2 (т.е. сдвиг всех битов вправо на одну позицию).
Если N>=R1, то заносим 1 в k-й бит числа Q и пишем R1 в R2.
Переход на пункт 2. Конец алгоритма.
В машинных кодах эта подпрограммка занимает 77 байтов на 32-разрядном процессоре и 73 на 16-разрядном, хотя это, вероятнее всего, не предел. Из 1000-разрядного числа корень извлекается за тысячную долю секунды.
Вообще, на ЭВМ чаще запаяно извлечение корня методом последовательных приближений, который основан на формуле Герона, известной с глубокой древности. По достигнутому приближению x следующим берется (a/x+x)/2, где a - исходное число, из которого надо извлечь квадратный корень. Однако, с ростом разрядности сильно замедляется деление. Кроме того, ранее и сейчас есть спрос на специальные вычислители (например, на летательных аппаратах) с предельно простыми алгоритмами.
Здесь представлен такой алгоритм. Хотя в литературе я его не нашел, но трудно рассчитывать на первенство, поскольку обычно всё простое давно найдено. Тем не менее, примеры из статьи и из истории науки показывают, что часто простые вещи не находили лишь потому, что не искали и считали поиск безнадежным.
Плохо, что Вы один.
Увеличение объема оперативной памяти позволяет исключить загрузку временных файлов на жесткий диск, а, следовательно, и скорость работы ПК будет большей. Иногда создаётся впечатление, что ваш комп завис. Так, для 32-битной Windows объем более 4 Гб будет бесполезен, так как система не «увидит» больше положенной емкости, разве что вы ее переустановите. Оперативная память должна обладать высокой емкостью, если компьютер используется для ведения современных игр или профессионального редактирования аудио или видео файлов. Установив в таком случае карту оперативной памяти на 8 или даже 16 Гб, тогда необходимость в модернизации ПК точно отпадет на несколько лет. Больший объем оперативной памяти может понадобиться разве только для работы с серверами, но я не профи в этом вопросе Увы и дать чёткие рекомендации не могу.
Изображения бегающих долларов несколько смазаны именно потому, что они бегают. Наделал также ряд движущихся калейдоскопов объемом порядка 100 байт. Картинки приведены в комментариях, но фото не отражают движения. Сейчас, конечно, никого не удивишь простенькими картинками 90-х годов. Но не только на них рекордные достижения программирования так и остались непревзойденными.