Русский
Русский
English
Статистика
Реклама

Алгоритмы

Перевод Ускорение JPEG-кодирования с использованием нескольких потоков

14.01.2021 12:05:51 | Автор: admin
Стандарт JPEG появился в 1992 году. С тех пор JPEG-изображения оказались неразрывно связаны с цифровой фотографией, они используются практически в каждом приложении, которое работает с изображениями фотографического качества. Причина того, что стандарт JPEG был так быстро принят всем миром, того, что он стал практически универсальным способом хранения изображений, заключается в том, что в нём одновременно используется несколько подходов к сжатию изображений. Один из этих подходов основан на понимании ограничений системы зрительного восприятия информации человеком, и того, какую информацию, наиболее важную, нужно сохранить, а от какой, менее важной, можно избавиться.



Алгоритм кодирования данных JPEG


Процесс сжатия изображений с использованием метода JPEG требует выполнения нескольких шагов (ниже приведена соответствующая схема). Обычно изображение сначала преобразуется из цветового пространства RGB в цветовое пространство YCbCR. Причина необходимости этого шага заключается в том, чтобы сделать возможным субсэмплинг пикселей. Человеческий глаз более чувствителен к изменениям яркости, чем к изменениям цветности. Это позволяет произвести даунсэмплинг цветового канала, но сохранить канал яркости в полном разрешении. На этом шаге изображение может потерять 50% данных, а видимое ухудшение его качества будет минимальным. Затем изображение делится на блоки размером 8x8 пикселей (их называют MCU, Minimal Coding Unit, минимальная единица кодирования). В кодировании видео аналогом MCU являются макроблоки (Macroblock). Итак, MCU это квадратные блоки пикселей, сжатие информации о которых выполняется на основании сведений об их схожести друг с другом. Сведения о пикселях каждого MCU переводятся из пространственной области в частотную область с использованием дискретного косинусного преобразования (Discrete Cosine Transformation, DCT). Благодаря выполнению этой операции можно легко избавиться от высокочастотной информации (мелких деталей) для ещё более сильного сжатия изображения. Чем больше высокочастотных компонентов убирают тем меньше будет файл и тем ниже будет качество изображения. Для управления этим аспектом кодирования применяется опция Q (уровень сжатия), используемая программами для JPEG-кодирования.


Обработка изображения при JPEG-кодировании

Одна из многих разумных идей, включённая в стандарт, заключается в использовании схожести значения DC (яркости) между находящимися рядом друг с другом MCU. Это позволяет добиться дальнейшего сокращения размера файла изображения за счёт того, что кодируются лишь изменения значений, а не сами эти значения. На вышеприведённой схеме этот процесс представлен блоком DPCM coding. Это отличная идея, но она создаёт одну небольшую проблему. Если значение DC для каждого MCU зависит от значения для предыдущего MCU, представляющего собой разницу значений, это значит, что если в данных некоего MCU будет ошибка это повлияет на все MCU, идущие за ним.

Ситуацию ещё немного усугубляет то, что сжатые символы, кодирующие данные изображения (выше это представлено блоком Huffman coding) это коды переменной длины (Variable Length Codes, VLC). Всего один неправильный бит может повредить все данные, расположенные в месте повреждения и дальше. В те давние времена, когда был изобретён формат JPEG, это было совершенно реальной проблемой, так как изображения часто передавались по каналам, которые могли не обладать надёжными механизмами коррекции ошибок (вроде соединений, создаваемых с помощью акустических модемов). Изображения, кроме того, хранились на носителях (вроде дискет), информация, записанная на которые, легко могла быть повреждена. Знание о том, что графическая информация, хранимая в JPEG-файлах, может пострадать из-за ошибок, привело к тому, что в стандарт добавили механизм, ограничивающий масштабы повреждения изображений. В основе этого механизма лежит идея о периодическом сбросе предыдущего значения DC в 0, что приводило к тому, что значение для следующего MCU должно было вычисляться в виде его разницы с 0. Это означало, что повреждённые значения DC влияли лишь на пиксели, расположенные до следующей точки рестарта.

Реализована эта возможность с использованием рестарт-маркеров (Restart Marker). Речь идёт о 2-байтовых маркерах, расположенных между MCU с регулярным интервалом (например через каждые 100 MCU). Если данные оказываются повреждёнными несложно найти следующий рестарт-маркер (JPEG-маркеры всегда находятся на границах байтов, им предшествует значение 0xFF). После нахождения позиции следующего рестарт-маркера изображение может быть правильно декодировано начиная с этой позиции, так как известно количество MCU между такими маркерами.

Постоянное развитие масштабов использования цифровых изображений


После выпуска стандарта JPEG компьютерные сети и хранилища данных становились всё надёжнее, в них применялись системы обнаружения и коррекции ошибок (например TCP/IP). Твердотельные накопители, используемые в цифровых фотоаппаратах, были достаточно надёжными и о рестарт-маркерах на какое-то время забыли, так как они увеличивали размеры файлов не давая взамен никаких заметных преимуществ. В это время программное обеспечение создавалось, в основном, в расчёте на выполнение на одном процессоре с использованием одного потока. Тот факт, что JPEG-изображения нужно было декодировать за один проход, что было нужно из-за использования кодов переменной длины и данных об изменениях значений для MCU, не вызывал каких-либо проблем для программ, так как они, в любом случае, создавались в расчёте на однопоточный режим.

Правда, в последние годы произошли огромные изменения в компьютерах, и в том, как мы пользуемся JPEG-файлами. Практически каждое вычислительное устройство обладает несколькими CPU и работает под управлением операционной системы, поддерживающей несколько потоков (сюда входят даже телефоны). Другие изменения заключаются в том, что люди снимают, редактируют и просматривают миллиарды JPEG-фотографий на своих телефонах. Каждое новое поколение телефонов позволяет создавать фотографии всё большего и большего разрешения, хранящиеся во всё более объёмных файлах. Для любого, кто работает с огромным количеством снимков, очень важным оказывается время, необходимое для кодирования и декодирования графических файлов.


Средний размер изображений, запрашиваемых веб-страницей (по материалам HTTP Archive)

Превращение хорошей идеи в идею очень хорошую


Компьютеры, с 1970-х годов, практически непрерывно становятся всё мощнее и мощнее. Обычно это непрерывное улучшение их характеристик описывают, прибегая к закону Мура. Соответствующий термин появился много лет назад благодаря эмпирическому наблюдению Гордона Мура, в соответствии с которым число транзисторов в компьютерах удваивается каждые 18 месяцев. Этот закон, в целом, остаётся справедливым в том, что касается количества транзисторов, но рост скорости работы компьютеров упёрся в физические ограничения кремния и в проблемы, связанные с питанием микросхем и выделением ими тепла. Так как в последние годы скорость работы отдельного процессора увеличивалась не слишком сильно, внимание индустрии переключилось на применение нескольких процессоров, которые могли бы справляться с различными задачами быстрее за счёт параллельной работы над ними. В современных вычислительных окружениях ценится возможность делить задачи на части и передавать выполнение этих частей разным процессорам. Не все задачи можно так разделить, так как в некоторых случаях следующие части задач могут зависеть от результатов, полученных при обработке их предыдущих частей. Кодирование и декодирование JPEG обычно тяжело разделить на несколько задач и обрабатывать эти задачи параллельно. Дело тут в том, что следующие MCU зависят от предыдущих, и в том, что в JPEG используются коды переменной длины.

Но Благодаря использованию рестарт-маркеров VLC-данные сбрасываются у границ байтов (в позициях после маркера), сбрасываются и разницы DC-значений MCU. Это означает, что с использованием рестарт-маркеров и кодирование, и декодирование JPEG-изображений может быть разделено на несколько потоков. При кодировании изображение может быть разделено на фрагменты, каждый из которых может кодироваться отдельным процессором. Когда каждый из процессоров завершил свою задачу, то, что получилось у них на выходе, может быть склеено с использованием рестарт-маркеров. Задача декодирования может быть распределена между таким количеством процессоров, которое соответствует количеству рестарт-маркеров. Единственная дополнительная задача, которую нужно для этого решить, заключается в предварительном просмотре сжатых данных и в поиске рестарт-маркеров. Дело в том, что размеры данных, находящихся между маркерами, варьируются, и в JPEG-файлах нет каталога, содержащего сведения о позициях рестарт-маркеров.

Реальный пример


В многопоточных приложениях производительность редко находится в прямой зависимости от количества задействованных CPU. То есть разделение задачи на 12 потоков, выполняющихся на 12 процессорных ядрах, не значит, что эта задача будет выполнена в 12 раз быстрее, чем в однопоточном режиме. При работе в многопоточном режиме на систему ложится дополнительная нагрузка по управлению потоками, и память обычно представляет собой единую сущность, совместно используемую процессорами. Проведём испытание на следующем изображении.


Изображение для испытания

Мы, в Optidash, реализовали вышеописанную идею использования рестарт-маркеров ради серьёзного ускорения декодирования и кодирования изображений. Вышеприведённое изображение было обработано с помощью одного из наших тестовых инструментов на 15-дюймовом MacBook Pro 2018 года с 6-ядерным процессором Intel i7. Вот результаты этого испытания.

Количество ядер Время декодирования, мс Время кодирования, мс
1 53 264
3 25 104
6 18 61

Как видите, разделение задач кодирования и декодирования JPEG-файлов между несколькими процессорными ядрами даёт вполне ощутимые преимущества. Производительность при увеличении числа ядер, что зависит от конкретной задачи, редко меняется линейно. В данном случае то, какой выигрыш может дать использование нескольких ядер, ограничивается интенсивным использованием больших областей памяти.

Вот псевдокод, демонстрирующий то, как может быть устроен многопоточный JPEG-кодировщик:

void ThreadedWriteJPEG(assorted JPEG parameters, int numThreads) {int slice;pthread_t tinfo;// задаём счётчик, используемый для определения момента завершения работыsliceRemaining = numThreads;// Запускаем поток для каждого фрагментаfor (slice = 0; slice < numThreads; slice++) {pthread_t tinfo;// Используем структуру slice для хранения сведений о работе каждого потока// В эти сведения входят указатель на начало полосы пикселей// и количество строк пикселей, которое нужно сжать<настройка структуры slice для обеспечения работы каждого потока>pthread_create(&tinfo, NULL, JPEGBuffer, &slices[slice]);} // для каждого фрагмента// ожидаем завершения всех рабочих потоковWaitForThreads(&sliceRemaining);// объединяем фрагменты в один файл и записываем егоWriteJPEGBuffer(slices, numThreads);}

Сталкивались ли вы с задачами обработки JPEG-файлов, для решения которых вам пригодилась бы многопоточная система кодирования и декодирования таких файлов?

Подробнее..

Перспективы радарных систем на наноспутниках

13.01.2021 18:13:38 | Автор: admin

Я раньше не очень интересовался cubesat. Они казались мне чем-то неземным, сложным, далеким. Но все изменилось, когда недавно нам пришел заказ на разработку одной подсистемы для наноспутника. Я стал интересоваться, а какое же радиооборудование люди умудряются ставить на этих малышей. К своему удивлению, я увидел даже примеры создания радарных систем на cubesat. Эта техника показалась мне настолько крутой, что мы c k_const составили себе труд присмотреться к некоторым примерам спутниковой радарной обработки с синтезированной апертурой.


Мы заранее скажемся новичками в этой области. Призываю специалистов к критике и обмену информацией по теме в комментариях.


Тема радаров обзора земной поверхности имеет большое значение для народного хозяйства. Приложения этой техники простираются от картографии и геологии до транспорта и сельского хозяйства. В России особо актуально управление лесным хозяйством и предупреждение природных катастроф. У нас существует группировка спутников дистанционного зондирования Земли (ДЗЗ), правда, радарные методы на действующих спутниках представлены мало. В основном на российских спутниках ДЗЗ, как я понял, используется оптическая съемка.


Повышению интереса к теме радарных систем на маленьких космических носителях способствует снижение стоимости их выведения на орбиту. Я не знаю цен выведения на орбиту в России, подскажите, кто знает. Но цены самих платформ известны, и они не космические. На западе все более открыто, информация есть здесь, например. Эти цены сильно ниже тех миллионов, которые нужно выложить за запуск "обычного" спутника, а также за его железо. Ведь оно должно быть более надежным, так как большая цена решения увеличивает риск. Это я уже не говорю про софт, надежность которого должна быть такой, какая нам, наземным программистам, даже и не снилась.


Ввиду этих фактов, вполне понятен интерес ученых и инженеров всего мира к возможности создания радарных систем на наноспутниках. Недолго поразмыслив, мы увидим, что единственное, что можно предложить, это разделить радарную систему на приемную и передающую части и расположить их на отдельных спутниках. Конечно, создать апертуру антенны, равнозначную апертуре на "обычном" спутнике не удастся. Нужны системные ухищрения, чтобы скомпенсировать потери в энергетическом бюджете. В публикациях западных инженеров мы находим несколько подходов к компенсации. Рассмотрим подходы более подробно.


Здесь следует отметить, что ввиду большей по сравнению с радарами на воздушных носителях дальности, обычно на спутниках необходимо применять синтез апертуры, как метод увеличения разрешения. Этому способствует хорошая стабильность и предсказуемость движения спутника по орбите. Такие радары называют радарами с синтезированной апертурой (РСА) или synthetic aperture radar (SAR).


Первый и основной тезис: использование спутников, оснащенных только приемниками или только источниками сигнала. Таким образом, радар еще и становится бистатическим или мультистатическим, если приемников больше, чем один. Здесь обнаруживается одна из возможностей поправить энергетический потенциал: чем больше приемников, тем он больше. Сигнал нескольких приемников будет проинтегрирован, что даст увеличение отношения сигнал/шум в соответствующее число раз.


Следующей возможностью является использование сигналов уже существующих источников. Естественно, копия сигнала этого источника должна оказаться в одном месте с копией принятого отраженного сигнала.


Во-первых, этими источников могут быть передатчика спутниковых систем связи. Они должны иметь мощность, достаточную для обеспечения хорошего ОСШ, и полосу, достаточную для обеспечения требуемого разрешения по дальности. Есть примеры использования как геостационарных спутников связи, так и спутников на низких орбитах. Можно также использовать сигналы существующих радаров на "обычных" спутниках.


Во-вторых, можно воспользоваться сигналами наземных источников. Они имеют достаточную мощность и расстояние от них до поверхности отражения невелико. Полоса таких сигналов тоже может быть достаточной. Одной из проблем такого способа будет ограничение облучаемой таким сигналом поверхности. Если в нужной местности не найдется такого источника, то система работать не будет. Еще одной проблемой может быть наличие нескольких таких сигналов на одной территории, что приведет к усложнению алгоритмов обработки. Даже сам сбор такого сигнала может быть непростым делом, ведь наземные системы оптимизированы для облучения земной поверхности и могут излучать мало энергии в сторону спутника.


В-третьих, можно использовать специально созданный и запущенный источник на воздушном носителе. Недостатком такой системы будет необходимость обеспечения его своевременного запуска и пролета по маршруту. Это также будет приводить к дополнительным сложностям при обработке.


Сейчас я не буду вдаваться во все тонкости этих подходов. Вы можете изучить их по этой и другой литературе, которую легко найти в Сети.


Для нас основным вопросом на данном этапе была доступность математики по обработке сигнала в такой радарной системе. Мы начали с простейшего примера, как мы покажем далее, доступного для освоения каждому.


Простейшим примером с нашей точки зрения является обработка сигналов со спутниковых РСА-систем, типа ALOS, ENVISAT, Sentinel, TerraSAR-X, COSMO-SkyMed, Radarsat-2 и др., производящих съемку в маршрутном режиме. Простота с одной стороны подтверждается банальным наличием сырых данных с некоторых из этих спутников в открытом доступе, c другой стороны наличием ПО с открытым кодом (GMTSAR), которое позволяет как фокусировать сырые радиолокационные изображения, так и делать более сложные вещи, такие как создание интерференционных картин между двумя изображениями, снятыми в различные пролеты спутника. Такая мощная база безусловно может стать хорошим подспорьем в деле изучения РСА.


Далее мы покажем каким образом можно получить радиолокационное изображение интересующей местности на примере сырых данных, полученных при съемке Санкт-Петербурга со спутника ALOS PALSAR. Оговоримся, что данная статья не претендует на всеобъемлющее руководство, мы лишь пытаемся показать, с чего можно начать.


Для начала рассмотрим разрешение радиолокационного изображения, получаемого со спутника. Номинальное разрешение по наклонной дальности определяется полосой B импульса радара:


$rho_{r}=\frac{c}{2B}$


Для нашего случая B = 14 МГц, и разрешение по наклонной дальности равно около 10 м. Не менее важной характеристикой является разрешение по дальности по поверхности земли. Чтобы проще было разобраться в терминологии, обратимся к рис. 1, где представлена геометрия РСА. Вектор скорости спутника перпендикулярен плоскости рисунка, радар излучает импульсы перпендикулярно скорости, под углом к высоте спутника H, наклонная дальность. Разрешение по дальности по поверхности земли геометрически связано с разрешением по наклонной дальности:


$\rho_{gr}=\frac{c}{2Bsin\theta}$


и составляет составляет для нашего случая около 60 м. Из представленных соотношений видно, что разрешение по дальности не зависит от высоты спутника H и может быть улучшено увеличением полосы излучаемого импульса. Во многих случаях полоса импульса ограничена, так как ограничена скорости передачи данных со спутника на землю.


image


Рис.1. Геометрия РСА. Вид спереди. H высота спутника, угол обзора, наклонная дальность.


Чтобы понять разрешение по азимуту, рассмотрим рис. 2, где радар пролетает над точечной целью. В приближении прямоугольной апертуры угол


$ \theta_{a}\approx \lambda /L $


где L длина антенны в азимутальном направлении, длина волны радара. Тогда разрешение по азимуту для радара с реальной апертурой определяется


$ R_{a}=\rho tan\theta_{a}\approx \frac{\rho \lambda}{L}=\frac{\lambda H}{Lcos\theta } $


image


Рис.2. Геометрия РСА. Вид сбоку. L длина антенны, наклонная дальность.


Если точечная цель остается неподвижной во время пролета радара над ней, радар может синтезировать апертуру, величина которой 2Ra, что приводит к значительному улучшению разрешения по азимуту:


$ \rho_{a}=\frac{\rho \lambda}{2R_{a}}=\frac{L}{2} $


Как мы видим теоретическое разрешение по азимуту в маршрутном режиме РСА определяется размерами антенны в азимутальном направлении. Разрешение РСА по азимуту не зависит от расстояния между целью и радаром. Более того, чем меньше размер антенны, тем большее разрешение может быть достигнуто. Объясняется это следующим образом. Чем меньше размер реальной апертуры антенны (шире ее основной лепесток диаграммы направленности), тем больше размер синтетической апертуры (цель дольше находится в луче). Чем больше размер синтетической апертуры, тем более узкий синтетический луч может быть получен, что в конечном итоге приводит к высокому разрешению по азимуту.


Размер антенны в азимутальном направлении спутника ALOS PALSAR составляет 10 м, следовательно теоретически достижимое разрешение по азимуту в маршрутном режиме РСА составляет 5 м. На практике размер пикселя делают одинаковым по дальности и азимуту.


Перед тем как переходить непосредственно к получению изображений, кратко рассмотрим алгоритм фокусировки, который мы будет применять, а именно дальностно-допплеровский алгоритм (range-doppler algorithm, RDA). Этот алгоритм разрабатывался в 1976-1978 гг. для обработки данных со спутника SEASAT SAR, запущенного в 1978 году. Основная идея алгоритма RD: использование того факта, что сигналы дальности и азимута могут быть разделены на два одномерных сигнала при определенных условиях. Тогда фокусировка изображения являет собой две последовательных операции одномерной компрессии импульса, то есть компрессия по дальности и компрессия по азимуту.


Компрессия сигнала по дальности относительно проста и может быть реализована путем согласованной фильтрации эхо-сигнала в частотной области дальности на основе знания опорного передаваемого сигнала. Обычно в качестве передаваемого сигнала используется ЛЧМ импульс (chirp). Это позволяет снизить пиковую мощность передатчика. Этот ЛЧМ импульс отражается от участка поверхности Земли, длиной обычно около 100 км. Принятый отраженный сигнал является сверткой комплексной отражательной способности поверхности Земли и ЛЧМ сигнала. Математически ЛЧМ записывается следующим образом:


$ s(t)= exp(i\pi k t^{2}),\quad \left | t \right |< \tau_{p} $


где k скорость изменения частоты (chirp slope), длительность импульса (pulse duration). Для ALOS PALSAR:


$ k= 1.03704\cdot 10^{12} \quad s^{-2}\\ \tau_{p}=0.27 \quad \mu s $


Согласованный фильтр в данном случае это просто комплексно-сопряженный исходный ЛЧМ импульс, *s****(t).


Обработка сигнала в направлении азимута несколько сложнее. Это связано с тем, что изображение точечной цели, проходящей через синтетическую апертуру, испытывает миграцию по дальности, т. е. эхо-сигнал от одной и той же цели при различных положениях спутника по азимуту (естественно в пределах синтетической апертуры) появляется в различных ячейках дальности. Таким образом, данные по азимуту оказываются связанны с данными по дальности. Чтобы можно было производить компрессию по азимуту, необходимо вернуть отметку о цели в ячейки соответствующие одной дальности. Количественно миграция дальности во временном пространстве дальности частотном пространстве по азимуту определяется следующим выражением:


$ R_{RCMC}(f_{s})=R_{0}\left ( \frac{1}{\sqrt{1-(\lambda f_{s}/(2V))^2}} -1 \right ) $


где Ro дальность ближайшего подхода спутника к цели, fs - доплеровская частота, V - эффективная скорость. Для точной коррекции миграции дальности каждого пикселя требуется процедура интерполяции.


После того как каждая отметка о цели появляется в своей ячейке дальности, можно переходить к компрессии сигнала по азимуту. Запишем фазу эхо-сигнала:


$ C(s)=exp\left [ -i\frac{4\pi }{\lambda }R(s) \right ] $


где R(s) дальность до цели функция времени по азимуту (медленное время), поскольку цель перемещается по синтетической апертуре, пока спутник пролетает над ней. Функция R(s) аппроксимируется параболой:


$ R(s)=R_{0}+\dot{R}(s-s_{0})+\ddot{R}/2(s-s_{0})^{2} $


где точкой обозначены производные по медленному времени s. Тогда мы можем переписать фазу эхо-сигнала, как функцию дальности, а также первой и второй производных дальности по времени s.


$ C(s)=exp\left [ -i\frac{4\pi }{\lambda } \left [ R_{0}+\dot{R}(s-s_{0})+\ddot{R}/2(s-s_{0})^{2} \right ] \right ] $


Определим допплеровский центроид и скорость изменения допплеровской частоты следующим образом:


$ f_{dc}=\frac{-2\dot{R}}{\lambda } \qquad f_{R}=\frac{-2\ddot{R}}{\lambda } $


Тогда


$ C(s)=exp\left [ -i\frac{4\pi R_{0}}{\lambda } \right ] exp \left [ i2\pi \left ( f_{dc}(s-s_{0})+f_{R}(s-s_{0})^{2} \right ) \right ] $


Как мы видим это еще один ЛЧМ сигнал с параметрами fdc и fR. Согласованный фильтр в данном случае это просто комплексно-сопряженный сигнал фазовой функции, *С****(s). При фокусировке по азимуту мы проходим по всем ячейкам дальности (Ro) и для каждой колонки азимута создаем фильтр со своими параметрами (fdc и fR).


Здесь мы не ставим целью всесторонне и исчерпывающе описать дальностно-допплеровский алгоритм фокусировки РСА изображений. В поисках дополнительной информации читатель может обратиться к следующим монографиям:


\1. John C. Curlander, Robert N. McDonough Synthtic Aperture Radar: Systems and Signal Processing
\2. Jan G. Cumming, Frank H. Wong Digital Processing of Synthetic Aperture Radar Data: Algorithms and Implementation
\3. Xiaolan Qiu, Chibiao Ding, Donghui Hu BISTATIC SAR DATA PROCESSING ALGORITHMS


А мы тем временем перейдем к практической части.


Как мы уже упоминали ранее, в нашем распоряжении имеется GMTSAR программное обеспечение с открытым кодом (GNU General Public License) для цифровой обработки данных РСА. Код написан на языке C, однако требует предварительной установки GMT и NETCDF. GMT Generic Mapping Tools (Универсальные картографические инструменты, GMT) набор программ с открытыми кодами, предназначенных для обработки и отображения двумерной и трёхмерной информации, растеризации, фильтрации и других алгоритмов обработки изображения, а также отрисовки различных картографических проекций. NetCDF (Network Common Data Form) машино-независимый двоичный формат файлов, являющийся стандартом для обмена научными данными.


GMTSAR имеет 3 основных компонента: 1) препроцессор для каждого типа спутника для подготовки данных и орбитальной информации из внутреннего формата спутника в формат, пригодный для обработки; 2) InSAR процессор для фокусировки, совмещения нескольких изображений и формирования комплексной интерферограммы; 3) базирующийся на возможностях GMT постпроцессор для фильтрации интерферограмм, формирования градиентов фазы, а также отображения всех получаемых результатов.


Итак, перейдем к установке. Домашняя страница GMTSAR находится по адресу https://topex.ucsd.edu/gmtsar/. Здесь можно найти описание программы, файлы данных РСА, предоставленные в качестве примеров и много другой информации. Инструкцию по установке программы вы найдете по адресу https://github.com/gmtsar/gmtsar/wiki/GMTSAR-Wiki-Page. Продублируем ее здесь для Ubuntu 16.06 LTS/20.0:


  1. Install extra libraries. Note that depending on your OS version the actual version numbers in some of the packages below may differ):

sudo apt-get install csh subversion autoconf libtiff5-dev libhdf5-devsudo apt-get install liblapack-devsudo apt-get install gfortransudo apt-get install g++sudo apt-get install libgmt-devsudo apt-get install gmt gmt-dcw gmt-gshhg (16.0 LTS)sudo apt-get install gmt

  1. Download and install orbit files and place in suitable directory (e.g., /usr/local/orbits):

http://topex.ucsd.edu/gmtsar/tar/ORBITS.tarsudo -icd /usr/localmkdir orbitscd orbitstar -xvf ~/Downloads/ORBITS.tar # (need full path to ORBITS.tar)

  1. Download GMTSAR GITHUB suitable directory:

sudo -icd /usr/localgit clone --branch 6.0 https://github.com/gmtsar/gmtsar GMTSAR#  or#  checkout the master version for more new but not stable features. 

  1. Make and install GMTSAR (change the orbits directory if different):

cd GMTSARautoconf./configure with-orbits-dir=/usr/local/orbitsmakemake install

  1. Add the executables to your path (for csh or tcsh):

cd ~#   edit your .tcshrc file and add the following linessetenv GMTSAR /usr/local/GMTSARsetenv PATH $GMTSAR/bin:"$PATH"#  orcd ~#  edit your .bashrc file and add the following linesexport GMTSAR=/usr/local/GMTSARexport PATH=$GMTSAR/bin:"$PATH"

Инструкция рабочая, однако, может понадобится установка дополнительных библиотек. Для пользователей Windows есть возможность скачать виртуальную машину с предустановленным ПО GMTSAR: https://topex.ucsd.edu/gmtsar/downloads/


ВАЖНЙ МОМЕНТ!!! Перед использованием программы необходимо, чтобы в вашей системе дробная часть числа отделялась от целой части точкой. Это можно сделать, перейдя в меню Параметры вкладка Регион и язык и выбрав в Форматах страну United Kingdom.


Итак, надеемся установка GMTSAR не вызовет значительных трудностей. По окончании установки, если вы откроете терминал и введете команду gmt, то должны увидеть данные об установленной версии GMT. Используя команду gmtsar.csh, вы увидите список найденных скриптов из пакета GMTSAR. Обратим внимание, что все процедуры обработки данных из пакета GMTSAR организованы в виде c-shell скриптов. Скрипты объединяют вызов необходимых подпрограмм на языке Си с вызовом стандартных подпрограмм GMT, а также с манипулированием данными. Одни скрипты могут включать в себя другие, позволяя гибко выбирать необходимые процедуры.


Сегодня нам понадобятся следующие скрипты:


  • pre_proc.csh preprocess the raw SAR data for a pair of images
  • sarp.csh focus a single SAR image
  • slc2amp.csh make and amplitude image from and SLC

Как видно из описаний pre_proc.csh подготавливает данные пары изображений (нам понадобится одно изображение), sarp.csh фокусирует радиолокационное изображение, формируя Single Look Complex-изображение (SLC), slc2amp.csh делает амплитудное изображение из SLC.


Таким образом, с ПО мы разобрались, теперь нам необходимо скачать доступные сырые радиолокационные изображения. Для начала рассмотрим какие вообще данные предоставляет миссия спутника ALOS PALSAR: https://earth.esa.int/eogateway/catalog/alos-palsar-products


ALOS PALSAR products are available in following modes:


Fine Beam Single polarisation(FBS), single polarisation (HH or VV)), swath 40-70km, resolution 10m, temporal coverage from 02/05/2006 to 30/03/2011


Fine Beam Double polarisation (FBD), double polarisation (HH/HV or VV/VH), swath 40-70km, resolution 10m, temporal coverage from 02/05/2006 to 30/03/2011


Polarimetry mode (PLR), with four polarisations simultaneously: swath 30km, resolution 30m, temporal coverage from 26/08/2006 to 14/04/2011


ScanSAR Burst mode 1 (WB1), single polarisation: swath 250-350km, resolution 100m, temporal coverage from 12/06/2006 to 21/04/2011


Following processing levels are available:


RAW(level 1.0): Raw data generated by every downlink segment and every band. Divided into an equivalent size to one scene.


SLC (level 1.1): Slant range single look complex product. Not available for WB1


GDH (level 1.5): Ground range Detected, Normal resolution product


GEC (level 1.5): Geocoded product


Как мы видим миссия ALOS PALSAR вела съемку в 4 различных режимах, предоставляя на выходе 4 уровня обработки данных. Нас, конечно, интересуют в первую очередь сырые RAW (level 1.0) данные в режимах Fine Beam Single polarisation (HH or VV) и Fine Beam Double polarisation (HH/HV or VV/VH), их мы и будем искать.


Для доступа к данным необходимо перейти на сайт https://search.asf.alaska.edu/#/ и зарегистрироваться там. Интерфейс поисковика данных довольно прост и интуитивно-понятен, поэтому тезисно опишем порядок действий (см. рис. 3):


  • Выбираем ALOS PALSAR в меню Dataset
  • Рисуем на карте интересующий регион, нажав + в подменю Area of interest
  • Жмем SEARCH
  • На карте появятся области, для которых доступны радиолокационные данные (выделены синим)
  • В списке, либо кликнув мышкой на карте, выбираем регион, и видим доступные файлы для него
  • Находим файл уровня 1.0 и скачиваем его.

image


Рис.3 Поиск данных со спутника ALOS PALSAR


Теперь переходим непосредственно к обработке скачанных данных с помощью GMTSAR. Откроем терминал, распакуем скачанный zip-файл и перейдем в папку, которая находилась в архиве. Эта папка будет содержать следующие файлы:


cd folder_with_datals -l-rw-r--r-- 1 1000 1000       1848 Dec 16  2016 ALPSRP023161190.l0.workreport-rw-rw-rw- 1 1000 1000  762000120 Dec 16  2016 IMG-HH-ALPSRP023161190-H1.0__A-rw-rw-rw- 1 1000 1000   12506972 Dec 16  2016 LED-ALPSRP023161190-H1.0__A-rw-rw-rw- 1 1000 1000        720 Dec 16  2016 TRL-ALPSRP023161190-H1.0__A-rw-rw-rw- 1 1000 1000       1800 Dec 16  2016 VOL-ALPSRP023161190-H1.0__A-rw-rw-rw- 1 1000 1000       1848 Dec 16  2016 workreport

Файл IMG-HH-ALPSRP023161190-H1.0__A содержит радиолокационные данные, файл LED-ALPSRP023161190-H1.0__A орбитальную информацию, остальные файлы нам не понадобятся.


В первую очередь нам нужно подготовить данные, для этого служит скрипт pre_proc_init.csh. При запуске скрипта без аргументов, выводится мануал по использованию. Запустим pre_proc_init.csh, чтобы понять как пользоваться этим скриптом.


pre_proc_init.cshUsage: pre_proc_init.csh SAT data.in       preprocess a set of images using default Dopper centroid, rear_range and radius, number of patches       a baseline-time plot will be generated       after running this command        the user should choose an appropriate master image        the user should also decide a common Dopper centroid, rear_range and radius, number of patches to run batch processing       the data with completely different Doppler centroid or baselines can be omitted from further processing SAT can be ALOS ERS or ENVI(ENVISAT)       format of data.in is:         line 1: master_name         line 2 and below: aligned_name       example of data.in for ALOS is:         IMG-HH-ALPSRP096010650-H1.0__A         IMG-HH-ALPSRP089300650-H1.0__A         IMG-HH-ALPSRP236920650-H1.0__A       example of data.in for ERS is:         e1_05783         e1_07787         e1_10292       example of data.in for ENVISAT is:         ENV1_2_127_2925_07195         ENV1_2_127_2925_12706         ENV1_2_127_2925_13207Example: pre_proc_init.csh ENVI data.in

Итак, чтобы воспользоваться скриптом, нам необходимо в качестве первого аргумента использовать имя спутника (ALOS), в качестве второго файл, содержащий имена файлов с сырыми данными (несколько файлов нужно для построения интерферограмм, в нашем случае будет один файл IMG-HH-ALPSRP023161190-H1.0__A). Создадим файл data.in и запустим препроцесс:


ls IMG-HH-ALPSRP023161190-H1.0__A >> data.inpre_proc_init.csh ALOS data.inrunning pre_proc_init.cshpreprocess master imageledflag 1.... swapping byteswriting generic LED file: IMG-HH-ALPSRP023161190-H1.0__A.LED near_range, shift = 959139 192 .... calculating doppler for IMG-HH-ALPSRP023161190-H1.0__A.raw Working on line 2000  Working on line 4000  Working on line 6000  Working on line 8000  Working on line 10000  Working on line 12000  Working on line 14000  Working on line 16000  Working on line 18000  Working on line 20000  Working on line 22000  Working on line 24000  Working on line 26000  Working on line 28000  Working on line 30000 

В результате работы скрипта препроцесса, в нашей папке появилось несколько новых файлов, в том числе .PRM, который содержит всю необходимую информацию для фокусировки (более детальное описание PRM-файла можно найти на стр.47 мануала GMTSAR: https://topex.ucsd.edu/gmtsar/tar/GMTSAR_2ND_TEX.pdf ). Для запуска процесса фокусировки необходимо запустить скрипт sarp.csh* с именем PRM-файла, созданного на предыдущем этапе, в качестве аргумента:


sarp.csh IMG-HH-ALPSRP023161190-H1.0__A.PRMComputing range reference function.Processing patch 1Processing Elapsed Time: 0 min 0.07 secRange CompressionProcessing Elapsed Time: 0 min 13.37 secAzimuthal TransformProcessing Elapsed Time: 0 min 33.64 secRange MigrationProcessing Elapsed Time: 0 min 50.55 secAzimuthal CompressionProcessing Elapsed Time: 1 min 53.07 secWriting DataProcessing patch 2Processing Elapsed Time: 1 min 54.17 secRange CompressionProcessing Elapsed Time: 2 min 6.90 secAzimuthal TransformProcessing Elapsed Time: 2 min 26.29 secRange MigrationProcessing Elapsed Time: 2 min 43.15 secAzimuthal Compression

Как можно заметить из вывода выполнения скрипта, фокусировка происходит блоками. В нашем случае фокусировка радиолокационного изображения размером 120000x25000 пикселей длилась около 5 минут. В результате в рабочей папке появится файл IMG-HH-ALPSRP023161190-H1.0__A.SLC, из которого нам останется сформировать амплитудное изображение. Делать мы это будем выполнением следующего скрипта:


slc2amp.cshUsage: slc2amp.csh filein.PRM rng_dec fileout.grd        rng_dec is range decimation       e.g. 1 for ERS ENVISAT ALOS FBD            2 for ALOS FBS             4 for TSXExample: slc2amp.csh IMG-HH-ALPSRP055750660-H1.0__A.PRM 2 amp-ALPSRP055750660-H1.0__A.grd

В качестве первого аргумента надо указать все тот же PRM-файл, в качестве второго децимацию, (в соответствии с режимом съемки наших данных выбираем 2), третьим аргументом указываем имя выходного файлы (out.grd).


slc2amp.csh IMG-HH-ALPSRP023161190-H1.0__A.PRM 2 out.grd

Таким образом, на выходе получаем netCDF-файл out.grd, содержащий информацию об амплитудном изображении. К сожалению, готовых средств для отображения полученного изображения в GMTSAR мы не обнаружили, однако, покажем, что нами действительно получено сфокусированное радиолокационное изображение Санкт-Петербурга. Для этого выполним следующие команды:


gmt begin ampgmt grd2cpt -Cgray out.grdgmt grdimage out.grd -I+d -Bgmt end show

В первой строке мы запускаем сессию GMT с именем "amp". 2 следующие команды формируют изображение, последняя закрывает сессию GMT и открывает файл amp.pdf с полученным изображением. Рассмотрим полученное изображение (рис. 4):


image


Рис.4 Радиолокационное изображение Санкт-Петербурга


Как видно, мы получили сфокусированное радиолокационное изображение. При этом, оно зеркально по вертикали, то есть нижнюю строку мы отобразили как верхнюю, а верхнюю как нижнюю. Однако, это не меняет того факта, что фокусировка прошла успешно и кодом GMTSAR можно пользоваться.


Статья написана в соавторстве с k_const. Теперь мы немного понимаем в радарах с синтезированной апертурой, но нам явно есть еще чему поучиться. Приглашаем специалистов к дискуссии.


СПИСОК ЛИТЕРАТУР


  1. Curlander J. C. Synthtic Aperture Radar: Systems and Signal Processing. / J. C. Curlander, R. N. McDonough. Wiley, 1992. 672 p.
  2. Cumming J. G. Digital Processing of Synthetic Aperture Radar Data: Algorithms and Implementation. J. G. Cumming, F. H. Wong. Artech House, 2005. 436 p.
  3. Xiaolan Qiu Bistatic SAR Data Processing Algorithms. / Xiaolan Qiu, Chibiao Ding, Donghui Hu. Wiley, 2013. 327 p.
  4. Sandwell D. GMTSAR: An InSAR Processing System Based on Generic Mapping Tools (Second edition). / D. Sandwell, R. Mellors, X. Tong, M. Wei, P. Wessel. // UC San Diego: Scripps Institution of Oceanography. 2016. Retrieved from https://topex.ucsd.edu/gmtsar/tar/GMTSAR_2ND_TEX.pdf
Подробнее..

Практическое применение алгоритма для представления Цекендорфа

05.01.2021 20:17:13 | Автор: admin

Как то в прошлом

Я написал статью о рекурсивном алгоритме Цекендорфа : пост

Пример кода
def le_fib(limit, fib)  theoretical = fib[fib.count - 1] + fib[fib.count - 2]  return fib.last if theoretical > limit  fib << theoretical  le_fib(limit, fib)enddef main(target,result)  temporary = le_fib(target, [1,1])  result << temporary  return result if target - temporary <= 0  main(target - temporary, result)endpp main(gets.to_i,[])

Функцияle_fib- рекурсивно ищет ряд Фибоначчи с пределом, на то, что бы следующее число не было больше чем входное числоtarget. Здесь важно, что нас не интересует ряд Фибоначчи целиком, нам важно лишь его окончание.

Функцияmain- рекурсивно ищет масcив, числа которого есть числами Фибоначчи, и которые бы в сумме давали нам входное число.

Хотя по правде говоря в комментах предложили более изящное решение :

Один цикл и делов
n, F = 100, [1, 2]while F[-1] < n do  F << F[-2] + F[-1]endF.reverse.each do |f|  if f <= n    n -= f    print f    print '+' if n > 0  endend

На практике я буду применять именно второй алгоритм так как он мение перегружен лишними действиями.

Постановка задачи куда мы будем "впихивать этот алгоритм"

Есть некий набор продуктов, условно говоря :

[ Курица, томаты, лаваш, грибы ].

Эти продукты имеют ценность, как себестоимость так и ценность для конечного пользователя.
К примеру градацию можно произвести такую

[ курица > томаты > грибы > лаваш ] .

Задача состоит в том что бы генерировать такой набор продуктов, который имел бы по крайней мере 1 "Low cost", и 1 "High cost" продукт.

Вот тут то я хочу приспособить этот алгоритм (Цекендорфа).

Главная идея в том что бы создать хэш (структура данных в Ruby) где ключ это число Фиббоначи, а значение собственно имя продукта.

Задача есть, теперь перейдем к решению.

Для начала анализируем сам алгоритм

Запустим его в цикле от x до y и посчитаем количество вхождений каждого числа.

  1. [1,100][1,100][1,1000][1,1000]
  2. Как видим на малых Y вероятность того что число будет использовано в последовательности - равномерно распределенно так как верхняя граница чисел Фибоначчи постоянно растёт пропорционально к текущему числу в итерации.

    Что мы с этого получили - чем больше входное число, тем выше вероятность получения одного и того же граничнего числа последовательности Фибоначчи.

    Значит нам нужен отрезок с более равномерным распределением. Уменьшаем Y

    [1,143][1,143]
  3. Видим пик на крайних числах 1 и 89. Что собственно отвечает постановки задачи, но при этом мы не теряем случайное равномерное выпадение "Middle cost" продуктов.

    Предлагаю остановится на 3 варианте где x = 1 и y = 143.

Реализация

Программы куда будем прописывать алгоритм Цекендорфа, выглядит так :

  • Модуль-перечень продуктов (для возможной тематичности)

  • Collector, который загружает перечень продуктов и составляет Hash (где ключ -> число Фибоначчи, значение -> название продукта)

Такую струтуру я использую для возможной тематичности продуктов, достаточно просто создать новый перечень продуктов и передать в autoloader название новой тематики, что бы времено ввести новые продукты в оборот.

К слову говоря, всё это я делаю для Telegram бота , который создан по гайду описаном в другом посте.

Итак, написав небольшой парсер, на выходе получаем такой результат

Небольшой парсер
@fib = [1,2,3,5,8,13,21,34,55,89]    def collect_the_items      food_hash = Hash.new      (0..9).each do |iterator|        food_hash[@fib[iterator]] = FOOD.first[iterator]      end      puts food_hash.map{|key,value| "#{key} - #{value}"}    end

Следующим шагом, слегка изменим алгоритм представления Цекендорфа :

Алгоритм
def get_sequence(limit)    result = []  n, fib = limit, [1, 2]    while fib[-1] < n do    fib << fib[-2] + fib[-1]  end  fib.reverse.each do |f|    if f <= n      n -= f      result << f    end  end  resultend

Я собираюсь использовать готовую последовательность и пройдя по ней - просто вывести все продукты по ключам.

Код функции
def generate_food          food_array = Collector.collect_the_items          food = []          rarity = rand(1..143)          get_sequence(rarity).each do |key|            food << food_array[key]          end          foodend

Похоже всё готово к тесту, проведу 6 тестовых прогонов, результаты будут в виде ответа от телеграмм бота.
Немного украшу сообщение от бота. Поскольку это никак не отражается на задаче - я не буду описывать этот шаг.

Результаты теста

примечание :
Low cost : ?
Mid cost : ?
High cost : ?

Результат

Применения алгоритма представления Цекендорфа меня полностью удовлетворяет. Тоесть - выполняет поставленную перед ним задачу.

Один из первых комментов под статьей на которой основано это практическое приминение, как раз таки и ставил перед мной вопрос : "а действительно, где это применить можно?". Как видим, вот для таких задач данный алгоритм вполне можно использовать.

И я не говорю о том что это единственный правильный вариант составления списка продуктов для моего бота, но он действительно вполне потян и работает.

Подробнее..

О реализации ввода-вывода с именами

05.01.2021 22:19:51 | Автор: admin

Введение

Как-то на одном из компьютерных форумов участники делились соображениями, чего им не хватает в языках, так сказать, в повседневной деятельности. Один заявил, что ему очень не хватает оператора типа put data. Для тех, кто не слышал о таком, поясню, что в языке PL/1 был предусмотрен оператор вывода (или ввода) значений переменных вместе с их именами, т.е. вместе с идентификаторами.

Например, если обычный вывод put list(X,Y); давал что-нибудь вроде:

1280 1024

то оператор put data(X,Y); печатал:

X= 1280 Y= 1024

не заставляя писать для этого вывод в виде оператора:

put list(X=,X,Y=,Y);

Чаще всего это использовалось в отладочных целях, но не обязательно. Например, используя вывод в текстовый файл с помощью put data, а затем ввод этих же данных как исходных в другой программе с помощью зеркального оператора get data можно было получить удобную для чтения и редактирования форму представления исходных данных в текстовом виде.

Можно возразить, что современные оболочки систем программирования легко позволяют вывести значения (и имена) любых объектов программы в интерактивном режиме безо всяких put data и поэтому в нем больше нет необходимости.

Я тоже использую встроенный интерактивный отладчик, с помощью которого можно посмотреть любые, даже сложные (составные) данные. Однако потребность в возможностях put data не исчезла. Иногда нужен и анализ данных на распечатке, (т.е. в логе) с возможностью быстрого и удобного добавления в текст программы вывода для отладки. К тому же для работы отладочных интерактивных систем используется дополнительная информация, которая обычно в выполняемом exe-файле отсутствует. В этом же случае все имена переменных зашиты в самой программе. Таким образом, удобства, предоставляемые языком в виде оператора, подобного put data, не заменяют, а дополняют возможности отладчиков. Кстати, в стародавние времена так называемая посмертная выдача на печать после ошибки иногда включала в себя и вывод полного списка всех имен переменных вместе с их текущими значениями. Некоторым программистам так нравился такой вывод, что они специально в конце своей программы ставили деление на ноль.

Реализации ввода-вывода с именами

В исходном варианте компилятора, которым я пользуюсь и который по мере сил развиваю, оператора put data не было. И мне его тоже очень не хватало в процессе отладки. Требовалось его ввести, причем хотелось сделать все как можно проще, компактнее и не внося больших изменений в компилятор. Поэтому была принята следующая схема реализации:

1. Сначала компилятором выполняется обычный разбор очередного объекта, перечисленного в списке ввода-вывода. Но при этом все лексемы, которые выдал лексический анализатор по запросу компилятора, еще и запоминаются в специальном буфере. По окончании разбора результат (т.е. все получившиеся операции внутреннего представления программы) отбрасывается, но характеристики объекта, например, его имя в программе, размерность и т.п., становятся известны.

2. Затем разбор повторяется заново, теперь полученные операции внутреннего представления программы будут использованы для генерации кода. Однако при разборе вместо лексического анализатора подключается его эмулятор, который уже не проводит лексический анализ исходного текста, а просто достает и выдает компилятору разобранные ранее и запомненные лексемы. Кроме них эмулятор может выдать и новые, сгенерированные им самим, лексемы.

Получается, что компилятор как бы сам для себя на ходу изменяет и дописывает исходный текст программы и тут же исправленный текст обрабатывает штатным образом. В чем-то эти действия немного похожи на макроподстановку.

Для реализации put data достаточно проанализировать запомненные в буфере лексемы, найти конец разбираемого элемента (это запятая вне скобок или внешняя закрывающая скобка) и все предыдущие лексемы объединить в одну строку, которую в начале работы эмулятора и выдать с признаком текстовая константа.

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

Таким образом, например, текст:

put data(x(i+1,j-1));

внутри компилятора будет восприниматься как:

put list(x(i+1,j-1)=,x(i+1,j-1));

Разумеется, так будут обрабатываться не только объекты-переменные, но и любые выражения при выводе. Исключение составляет лишь вывод текстовых констант. Для них дополнительные лексемы, конечно же, не формируются во избежание бессмысленного вывода одного и того же текста два раза подряд со знаком равенства посередине.

Ввод-вывод не скалярных объектов

Идея исправлять исходный текст программы на лету позволила легко решить поставленную задачу. Однако полученный механизм жаль было использовать только для такой мелочи как put data, поскольку этот же подход можно было применить и для более объемной задачи ввода-вывода не скалярных объектов. Автоматический ввод-вывод всех элементов не скалярного объекта также был предусмотрен в языке и тоже отсутствовал в исходной версии компилятора, хотя на практике часто требовался.

Здесь ситуация сложнее, чем с put data для скаляра, так как для вывода массива вместо текста:

put data(x);

требовалось на лету сформировать уже что-нибудь вроде:

do i=lbound(x) to hbound(x); put data(x(i)); end;

Но и это еще не все. Например, если x двумерный массив целых (например, матрица 3х3), тот же самый оператор put data(x); уже должен осуществлять вывод по двум циклам, чтобы дать в результате что-то такое:

X(1,1)= 1 X(1,2)= 2 X(1,3)= 3 X(2,1)= 4 X(2,2)= 5 X(2,3)= 6 X(3,1)= 7 X(3,2)= 8 X(3,3)= 9

Но при этом оператор put data(x(2)); должен вывести лишь одну строку матрицы:

X(2,1)= 4 X(2,2)= 5 X(2,3)= 6

А если x это набор разнотипных элементов (в PL/1 такой набор называется структурой), то нужно еще выводить и имена отдельных полей этого набора, например:

declare

1 a,

2 a1 fixed,

2 a2 fixed,

2 b,

3 b1 fixed,

3 b2 float;

put data(a);

A.A1= 0 A.A2= 0 A.B.B1= 0 A.B.B2= 0.000000E+00

Учитывая, что в структуре могут быть подструктуры, в свою очередь включающие массивы (т.е. могут быть и структуры массивов и массивы структур), то задача автоматического вывода элементов становится довольно громоздкой:

declare

1 a(1:2),

2 a1 fixed,

2 a2 fixed,

2 b,

3 b1 (-5:3) fixed,

3 b2 float;

put data(b);

B(1).B1(-5)= 0 B(1).B1(-4)= 0 B(1).B1(-3)= 0 B(1).B1(-2)= 0 B(1).B1(-1)= 0 B(1).B1(0)= 0 B(1).B1(1)= 0 B(1).B1(2)= 0 B(1).B1(3)= 0 B(1).B2= 0.000000E+00 B(2).B1(-5)= 0 B(2).B1(-4)= 0 B(2).B1(-3)= 0 B(2).B1(-2)= 0 B(2).B1(-1)= 0 B(2).B1(0)= 0 B(2).B1(1)= 0 B(2).B1(2)= 0 B(2).B1(3)= 0 B(2).B2= 0.000000E+00

Однако в языке PL/1 есть хорошая основа для доработок в виде возможности записать оператор цикла прямо внутри оператора ввода-вывода. В свое время разработчикам языка вывод массивов казался очень важным. Поэтому они разрешили писать цикл ввода-вывода в виде:

put list((x(i) do i=lbound(x) to hbound(x)));

вместо обычного цикла:

do i=lbound(x) to hbound(x); put list(x(i)); end;

Признаком начала цикла внутри оператора ввода-вывода является открывающая скобка. Кстати, разработчики PL/1 здесь немного попали впросак, поскольку при выводе выражения, начинающегося со скобки, большинство компиляторов воспримет эту скобку за начало цикла. Программистам приходилось писать выражения в экзотическом виде, только чтобы они не начинались со скобки:

put list(1e0*(x1+x2)/2e0));

Тем не менее, это сильно упрощает доработку компилятора, поскольку для вывода всех элементов массива достаточно при разборе очередного объекта ввода-вывода поставить его в скобки, дописать индексы и написать в этих же скобках заголовок цикла. В заголовке цикла начальное и конечное значение переменной цикла это константы, которые берутся из описания не скалярного объекта. В данной версии компилятора разрешено только статическое описание границ массивов и это также сильно упрощает доработку.

Легко заметить, что вывод с именами (put data) и вывод не скалярных объектов это дополняющие друг друга возможности. Объединяет их то, что в обоих случаях разбор объекта при трансляции выполняется два раза. Сначала все лексемы при лексическом разборе объекта запоминаются, а при повторном разборе выдаются из буфера так, как если бы из исходного текста. Но при этом в нужный момент выдаются и новые лексемы. В обоих случаях вместо лексического анализатора работает его эмулятор. Когда нужны обе возможности одновременно работают оба эмулятора, один на более низком уровне выдает лексемы для индексов, названий полей структур и заголовков циклов, а второй добавляет к ним элементы с текстовыми константами-именами.

Причем эмулятор верхнего уровня, создающий текстовые константы-имена, даже не подозревает, что лексический анализатор уже заменен на эмулятор для выдачи элементов массива и имен структур. Обе доработки компилятора не мешают друг другу и действуют независимо.

При этом работа эмулятора нижнего уровня гораздо сложнее, чем в случае put data, здесь используется такой алгоритм, как конечный автомат. Т.е. эмулятор имеет несколько состояний, запоминаемых между вызовами, при разборе переходя от одного к другому и выдавая в каждом состоянии лексемы разного типа. Это позволяет сначала выдать одну или несколько лексем - открывающих скобок, затем все имена промежуточных уровней структуры и все индексы, как переменные циклов, а затем набор лексем, обозначающих заголовки циклов по каждой размерности и, наконец, лексемы - закрывающие скобки.

Естественно, что если в исходном тексте старшие индексы объекта были явно указаны, то эмулятор дописывает только недостающие младшие индексы. Поэтому, например, для трехмерного массива x(1:10,1:10,1:10) оператор вывода:

put list(x); выдаст 1000 значений

put list(x(5)); выдаст 100 значений

put list(x(5,6)); выдаст 10 значений.

А для оператора put list(x(5,6,8)); эмулятор вообще не сгенерирует дополнительных лексем-индексов и будет напечатано единственное значение.

Недостатком описанной реализации оказалось то, что при применении оператора put data к не скалярным объектам на печати вместо всех значений индексов печатались идентификаторы переменных циклов, которые подставлялись в исходный текст в момент трансляции. А поскольку для этой цели использовались служебные целые переменные ?A, ?B, ?С,?O (всего 15 штук для максимально возможной размерности массива 15) выдача выглядела странно и во многом теряла ценность:

X(?A,?B)= 1 X(?A,?B)= 2 X(?A,?B)= 3 X(?A,?B)= 4 X(?A,?B)= 5 X(?A,?B)= 6 X(?A,?B)= 7 X(?A,?B)= 8 X(?A,?B)= 9

Для исправления этого недостатка потребовалось доработать системную библиотеку. В случае оператора put data с индексами компилятор не просто формирует текстовую константу имя переменной с подставленными индексами ?A, ?B, ?С,?O, но и дописывает перед каждым индексом специальный не выводимый символ 07FH.

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

Переменные с именами при вводе

Естественно, имеется парный оператор к put data - это get data, который должен вводить значения переменных, заданные вместе с их именами. Но здесь, на мой взгляд, разработчики PL/1 переусложнили данный оператор. В соответствии со стандартом языка оператор ввода должен не просто пропускать имена, но распознавать их и записывать следующее далее значение по нужному адресу. Например, если перетасовать значения, выданные put data(x);, в другом порядке:

X(1,2)= 2 X(1,1)= 1 X(2,3)= 6 X(2,1)= 4 X(2,2)= 5 X(3,1)= 7 X(1,3)= 3 X(3,2)= 8 X(3,3)= 9

То оператор get data(x); все равно должен ввести значения в правильном порядке, распознав каждое имя и индексы перед знаком равенства. И хотя такая обработка дает дополнительные удобства, например, можно пропускать данные, которые не меняются при вводе, все-таки это слишком хлопотно и сложно для реализации. А, главное, для такой возможности нужно иметь таблицу имен переменных и их адресов в каждом exe-файле, использующем get data. Поэтому я не стал реализовывать распознавание имен при вводе, а ограничился при чтении простым пропуском всех символов до знака равенства при разборе очередного элемента. Самое важное для меня операторы put data и get data остались зеркальными и выдача данных оператором put позволяет потом безошибочно читать их оператором get с таким же списком объектов.

Заключение

Как показывает практика, большую часть времени программист тратит все-таки на отладку. Поэтому любые средства и языка, и системы программирования в целом, хоть как-то облегчающие процесс отладки, должны только приветствоваться. Одним из таких простейших средств является встроенный ввод-вывод объектов программы вместе с их именами, реализация которого, как показано выше, не требует значительных затрат в компиляторе.

Мало этого, в данном случае удалось, не затрагивая работу основных частей компилятора, добавить дополняющие друг друга возможности и автоматического формирования имен, и автоматического вывода всех элементов массива. Объем кода доработок составил менее процента от общего объема компилятора, однако они оказывают существенную помощь, особенно при отладке, экономя и время, и внимание программиста при написании операторов ввода-вывода.

Послесловие

По личному опыту знаю, что, самая распространенная реакция на подобные заметки обычно сводится к двум заявлениям:

1. Это нафиг никому не нужно.

2.Это легко повторить на любом современном языке.

Первое заявление должно было бы звучать как мне это не нужно и тогда оно было бы корректным, но тогда непонятно, зачем об этом объявлять, а не просто пройти мимо.

Второе заявление, в принципе, верно. Например, в языке Немерле, есть доступ к такому свойству переменной, как имя в тексте программы, т.е. как раз нужная база для отладочного вывода, подобного put data.

Поэтому мне была предложена несложная библиотека на Немерле, реализующая, как уверял ее автор, вывод с именами и повторяющий возможности старого PL/1:

using System.Console;using PL1.Macro;module Program{  Main() : void  {    def x = 1280;    def y = 1024;    put data(x, y);    put data(x, y, x + y, x.ToString() + "asd");    _ = ReadLine();  }}using Nemerle;using Nemerle.Compiler;using Nemerle.Compiler.Parsetree;using System.Collections.Generic;using System.Linq;namespace PL1.Macro{  public macro PutData(args)  syntax ("put", "data", args)  {    PutDataImpl.Impl(args)  }  module PutDataImpl  {    public Impl(args : PExpr) : PExpr    {      match (args)      {        | PExpr.Tuple as args =>          def code = List();          foreach (arg in args.args)          {            code.Add(<[ $(arg.ToString()) ]>);            code.Add(<[ "=" ]>);            code.Add(arg);            code.Add(<[ " " ]>);          }          code.RemoveAt(code.Count - 1);          def code = code.Aggregate((a1, a2) => <[ $a1 + $a2 ]>);          <[ System.Console.WriteLine($(code)) ]>        | _ => PExpr.Error(args.Location, "Tuple expected.")      }    }  }}

Однако на предложение доработать библиотеку, чтобы она позволяла выводить и не скалярные объекты с печатью всех индексов (и тогда действительно бы повторяла возможности PL/1), мне в ответ было предложено сделать это самому в виде домашнего задания. Оказанную честь я отклонил, под предлогом того, что вообще-то у меня все это уже давно есть и используется. Судя по всему, автор библиотеки просто сразу не сообразил, как это сделать. И почему-то вспомнилась сцена из фильма Формула любви, где Калиостро удивив всех поеданием вилки, все-таки отказался съесть при этом еще и тарелку.

Подробнее..

Модификация исполняемого кода как способ реализации массивов с изменяемым границами

09.01.2021 02:10:27 | Автор: admin

Введение

В свете все возрастающего потока англоязычных околонаучных терминов в области программирования и следуя за модой, в названии статьи можно было бы вместо некрасивого модификация исполняемого кода написать что-нибудь вроде run-time reflection. Суть от этого не меняется. Речь о реализации в компиляторе такого непростого объекта, как массив с заранее неизвестными границами. Типичный пример использования подобных объектов это операции (в математическом смысле) с матрицами разных размеров.

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

Обычно текущие значения границ пишутся в специальную структуру (паспорт массива) и затем используются в командах вычисления адресов элементов массива. Для границ-констант, известных при компиляции, паспорт в общем случае в выполняемой программе не требуется.

Из сложности реализации таких массивов следует неприятное следствие: обращение к массивам с динамическими границами выполняется существенно медленнее, чем к массивам с границами-константами. Желательно было бы соединить мощь и удобство работы с массивами с задаваемыми при исполнении кода границами с быстротой доступа к массивам с границами-константами, когда часть вычислений адресов элементов может производиться уже на этапе компиляции программы.

Далее все рассуждения приводятся на примере конкретной реализации компилятора PL/1-KT с языка PL/1 для Win64.

Подход к реализации

Самый простой подход к решению данной задачи, который первым приходит в голову заменить значения границ-констант массивов на новые нужные значения и просто перетранслировать программу. Разумеется, во многих случаях такой подход неприемлем. Но рассмотрим, чем будет отличаться выполняемый код? Например, такому обращению к элементу массива:

dcl x(100,100) float(53);dcl (i,j)      fixed(63);x(i,j)=12345e0;

соответствует такой исполняемый код x86-64:

48693DB838010020030000   imul rdi,I,80048A1C038010000000000     mov  rax,J488DBCC710FDFFFF         lea  rdi,X+0FFFFFCD8h[rdi+rax*8]BE30000000               mov  rsi,offset @00000030h48A5                     movsq

Видно, что при разных значениях границ-констант массива исполняемый код будет отличаться лишь разными значениями операндов-констант в некоторых командах. В данном случае это значение третьего операнда-константы операции IMUL и константа-смещение в операции LEA.

Следовательно, если в выполняемом модуле сохранить информацию об адресах таких команд, а также информацию, каким образом получены такие операнды-константы, то можно создать служебную подпрограмму, которая при вызове во время исполнения программы заменит все нужные операнды-константы на новые значения, соответствующие новым требуемым значениям границ массивов.

После этого, исполнение кода пойдет так, как если бы при трансляции были заданы такие новые границы-константы. Получаются массивы как бы с динамическими границами, т.е. изменяемыми при выполнении программы, но обращение к которым идет точно так же, как и к массивам со статическими границами.

Это принципиально отличается от JIT-компиляции, поскольку код создавать не требуется, а нужно лишь самым простейшим образом скорректировать части нескольких уже готовых команд.

Некоторую сложность такому подходу добавляет тот факт, что операнд-константа может быть из нескольких составляющих и только часть из них определяется именно границами массива. Поэтому служебная подпрограмма должна заменять в операнде-константе только ту часть, которая меняется при изменении значений границ.

Выделение памяти для массивов с динамическими границами

Если границы массивов, а, значит, и объем занимаемой памяти, меняются во время исполнения программы, то в общем случае такие массивы не могут размещаться в статической памяти. Конечно, там можно заранее разместить массив с заведомо наибольшими значениями границ, а затем в процессе исполнения только динамически уменьшать их, но такой подход ограничен и неудобен.

Поэтому память для массивов с динамическими границами должен явно выделять программист из кучи оператором ALLOCATE и освобождать оператором FREE. В языке PL/1 такие объекты считаются объектами с управляемой (CONTROLLED) памятью.

Следовательно, новые значения констант должны быть определены до собственно создания массива, т.е. до выполнения соответствующего оператора ALLOCATE. Поэтому и обращение к служебной подпрограмме замены констант для данного массива должно быть тоже прежде выполнения оператора ALLOCATE, так как объем выделяемой для массива памяти это также операнд-константа в одной из команд перед вызовом ALLOCATE, зависящий от размеров границ.

Обработка констант

Константы, которые вычисляются из границ-констант массива и которые, в конечном итоге, становятся частью операндов-констант исполняемого кода, формируются на этапе анализа исходного текста программы при компиляции.

Компилятор PL/1-KT переводит текст программы в промежуточную обратную польскую запись, где каждая константа это отдельная операция, имеющая единственный операнд само значение константы (4 байта). Для реализации динамических массивов вводится новая операция модифицированная константа, которая имеет не значение, а операнд-ссылку на таблицу компилятора. По ссылке располагается само значение константы, а также вся необходимая информация, позволяющая определить, как получилось данное значение, и, следовательно, позволяющая рассчитать новое значение при новых границах.

После окончания трансляции эти ссылки сохраняются и в выполняемом модуле, причем к ним добавляются адреса команд, в код которых замешивается данная константа, а также адрес служебного (создаваемого компилятором) указателя на выделенную динамическому массиву память.

Служебная подпрограмма подготовки кода имеет один параметр служебный указатель и рассматривает только те ссылки на команды, в которых используется указатель, совпадающий с ее входным параметром. Для этих ссылок определяется место в команде, где записана сама константа, формируется новая константа из новых значений границ, к ней добавляется часть исходной константы, которая не зависит от границ. Новая константа заменяет в команде старую, и подпрограмма ищет следующую ссылку для заданного массива, т.е. для заданного указателя.

Исправляемые таким образом команды текстуально могут находиться и выше и ниже вызова служебной подпрограммы. Но, разумеется, если начать выполнять еще не приведенный к правильным границам код, поведение программы станет непредсказуемым.

Объекты программы, зависящие от размеров границ массивов

Таких объектов в программе на языке PL/1 оказалось восемь:

- встроенные функции языка LBOUND/HBOUND/DIMENSION, выдающие значения нижней/верхней границы или числа элементов для заданной размерности;

- оператор ALLOCATE, неявно имеющий входным параметром число выделяемых массиву байт, зависящее от его границ;

- индекс, т.е. собственно команды вычисляющие часть адреса по очередному индексу-переменной при обращении к элементу массива;

- последний индекс, появляется только в случае режима компиляции с контролем выхода индекса за границы массива. Для данного элемента корректировать константу в команде не требуется, например, это случай одномерного массива, где вычисление адреса умножением по единственному индексу не зависит от значения границ, но где-то далее имеются команды контроля выхода индекса за границы и их-то константы и необходимо скорректировать;

- смещение массива, это последняя из команд вычисления адреса элемента массива. К этому моменту уже вычислены составляющие адреса от индексов-переменных и в этой команде для x86-64 обычно реализуется базово-индексный режим адресации, причем в команде имеется постоянное смещение, которое как раз и зависит от значений границ и должно быть скорректировано. Ненулевое смещение возникает, так как нижние границы не обязательно нулевые, некоторые индексы могут быть константами, а элемент, адрес которого вычисляется, сам может быть элементом структуры (агрегата разнотипных элементов), имеющим свое постоянное смещение - начало каждого элемента внутри этой структуры;

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

Наиболее громоздким для обработки является корректировка константы в команде элемента смещение, поскольку в константу команды-смещение входят и части от индексов-констант. Служебной подпрограмме необходимо повторить весь расчет адресной части заново, причем, если по дороге были индексы-константы, еще необходимо тут же проверить их на выход за пределы новых значений границ.

Синтаксис массивов с изменяемыми границами

В стандарте языка PL/1 изменяемые границы массивов просто задаются выражениями, например:

dcl  n      fixed(31),     x(0:n) float ctl;get list(n);allocate x;

Для описываемой реализации такая запись бессмысленна, поскольку границы будут меняться другим способом, поэтому в описании вместо переменных используется знак *, этот пример эквивалентен предыдущему:

dcl  n      fixed(31),     x(*)   float ctl;get list(n);?index(1,1)=0; ?index(1,2)=n; // устанавливаем новые границыcall ?ret(addr(x));           // меняем константы кода обращения к xallocate x;

Для изменения границ в компилятор PL/1-KT введены служебные элементы в виде встроенного глобального двумерного массива новых значений нижних и верхних границ:

dcl ?index(15,2) fixed(31) external;

Первая размерность этого массива 1:15, поскольку это максимально допустимое число размерностей массива в компиляторе PL/1-KT.

А также введена служебная подпрограмма перетрансляции, т.е. корректировки констант в командах, использующая текущие значения массива ?index:

dcl ?ret entry(ptr) external;

Служебный массив ?index и подпрограмма ?ret предопределены в компиляторе PL/1-KT. При запуске программы все значения границ в массиве ?index по умолчанию заданы единичными.

Передача новых значений границ через глобальный массив ?index, а не через входные параметры подпрограммы ?ret сделана для большей гибкости их использования. Например, в этом случае не требуется повторять задания границ для массивов одинаковых размеров, не требуется каждый раз перечислять нижние границы каждой размерности, если они всегда остаются единичными и т.п.

В случае какой-либо ошибки корректировки констант, эта подпрограмма не возвращает код ошибки, но инициирует перехватываемое исключение, поскольку далее обращение к массиву, указанному как входной параметр, даст непредсказуемые результаты.

Компилятор PL/1-KT отмечает в своей таблице признак изменяемой границы у данного массива, а сам значок * просто заменяет на некоторые некруглые значения границ. Это сделано для того, чтобы далее в процессе компиляции создавались обычные команды для массивов с границами-константами. А некруглые значения не позволяют оптимизатору применять более короткие формы команд, поскольку тогда невозможно скорректировать их другими, например, большими значениями.

Динамические границы, обозначаемые *, могут быть только старшими размерностями и следовать подряд. При этом такие границы могут быть не только у массивов однородных элементов, но и у массивов структур, т.е. агрегатов данных разных типов. Младшие размерности при этом могут оставаться константами, например:

dcl // структура-массив с изменяемыми границами1 s(*,*)       ctl, 2 x1          char(100) var, 2 y1 (-1:25)  float, // внутри могут быть и границы-константы 2 z1 (100)    fixed(31);

Ссылка на массивы с изменяемыми границами

Для передачи в подпрограммы массивов с изменяемыми границами как параметров, учитывается тот факт, что такие массивы всегда неявно используют указатели. Но поскольку это служебные указатели, создаваемые компилятором, напрямую использовать их имена нельзя. Обращение к указателю без явного использования его имени возможно в языке PL/1 в случае применения встроенной функции ADDR, например:

dcl x(100) float based(p1),   (p1,p2) ptr;p2=addr(x); //это эквивалентно p2=p1;

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

call умножение_матриц(addr(a),addr(b),addr(c),m,n,q);

и тогда описание параметров таких подпрограмм становится единообразным, не зависящим от самих массивов:

dcl умножение_матриц entry(ptr,ptr,ptr,fixed(31),fixed(31),fixed(31));

Этот прием позволяет передавать динамические массивы в подпрограммы, но не позволяет принимать их внутри подпрограмм, поскольку тогда опять нужно присваивать указатели-параметры служебным указателям с недоступными именами. Поэтому в компиляторе PL/1-KT дополнительно разрешено использовать и в левой части присваивания встроенную функцию ADDR:

dcl x(*) float ctl,    p1   ptr;addr(x)=p1; //эквивалентно оператору <служебный указатель на x>=p1;

Пример использования динамических массивов как параметров

В данном примере применена описанная выше технология корректировки констант для универсального умножения матриц задаваемого размера. Динамические массивы-матрицы создаются оператором ALLOCATE и передаются (неявно, указателями) в универсальную процедуру умножения матриц. Корректировка констант в исполняемом коде производится как для фактических параметров A1, B1,C1, так и для формальных A, B, C внутри подпрограммы. Кроме этого, формальным параметрам присваиваются фактические значения с помощью разрешения использовать функцию ADDR в левой части присваивания. Процедура УМНОЖЕНИЕ_МАТРИЦ может находиться в отдельном модуле и транслироваться автономно.

TEST:PROC MAIN;DCL (A1,B1,C1)(*,*) FLOAT CTL; // ДИНАМИЧЕСКИЕ МАТРИЦDCL (M1,N1,Q1)      FIXED(31); // ЗАДАВАЕМЕ ГРАНИЦDCL (I,J)           FIXED(31); // РАБОЧИЕ ПЕРЕМЕННЕ//---- ДЛЯ ТЕСТА ЗАДАЕМ НЕКОТОРЕ ЗНАЧЕНИЯ ГРАНИЦ ----M1=5; N1=4; Q1=3;//---- КОРРЕКТИРУЕМ КОНСТАНТ A1(M1,N1), B1(N1,Q1), C1(M1,Q1) ----?INDEX(1,2)=M1; ?INDEX(2,2)=N1;?RET(ADDR(A1));                   // ИЗМЕНЯЕМ КОМАНД ДЛЯ A1?INDEX(1,2)=N1; ?INDEX(2,2)=Q1;?RET(ADDR(B1));                   // ИЗМЕНЯЕМ КОМАНД ДЛЯ B1?INDEX(1,2)=M1;?RET(ADDR(C1));                   // ИЗМЕНЯЕМ КОМАНД ДЛЯ C1//---- СОЗДАЕМ МАТРИЦ A1(M1,N1), B1(N1,Q1) И C1(M1,Q1) ----ALLOCATE A1,B1,C1;//---- ДЛЯ ТЕСТА ЗАПОЛНЯЕМ МАТРИЦ НЕКОТОРМИ ЗНАЧЕНИЯМИ ----DO I=1 TO M1; DO J=1 TO N1; A1(I,J)=I+J; END J; END I;DO I=1 TO N1; DO J=1 TO Q1; B1(I,J)=I-J; END J; END I;//---- УМНОЖЕНИЕ МАТРИЦ A1 И B1, РЕЗУЛЬТАТ - МАТРИЦА C1 ----УМНОЖЕНИЕ_МАТРИЦ(ADDR(A1),ADDR(B1),ADDR(C1),M1,N1,Q1);//---- ВДАЕМ ПОЛУЧЕННЙ РЕЗУЛЬТАТ ----PUT SKIP DATA(C1);FREE A1,B1,C1;//========== УМНОЖЕНИЕ МАТРИЦ ЗАДАННОГО РАЗМЕРА ==========УМНОЖЕНИЕ_МАТРИЦ:PROC(P1,P2,P3,M,N,Q);//---- ВХОД A(M,N) И B(N,Q), ОТВЕТ - МАТРИЦА C(M,Q) ----DCL (P1,P2,P3)   PTR;       // УКАЗАТЕЛИ НА МАТРИЦDCL (M,N,Q)      FIXED(31); // ЗАДАННЕ ГРАНИЦDCL (A,B,C)(*,*) FLOAT CTL; // ДИНАМИЧЕСКИЕ МАТРИЦDCL (I,J,K)      FIXED(31); // РАБОЧИЕ ПЕРЕМЕННЕ//---- НОВЕ ОПЕРАТОР ПРИСВАИВАНИЯ УКАЗАТЕЛЕЙ ----ADDR(A)=P1;     // АДРЕС ДЛЯ МАССИВА AADDR(B)=P2;     // АДРЕС ДЛЯ МАССИВА BADDR(C)=P3;     // АДРЕС ДЛЯ МАССИВА C//---- КОРРЕКТИРУЕМ КОНСТАНТ МАТРИЦ A(M,N), B(N,Q), C(M,Q) ----?INDEX(1,2)=M; ?INDEX(2,2)=N;?RET(ADDR(A));                    // ИЗМЕНЯЕМ КОМАНД ДЛЯ A?INDEX(1,2)=N; ?INDEX(2,2)=Q;?RET(ADDR(B));                    // ИЗМЕНЯЕМ КОМАНД ДЛЯ B?INDEX(1,2)=M;?RET(ADDR(C));                    // ИЗМЕНЯЕМ КОМАНД ДЛЯ C//---- САМО УМНОЖЕНИЕ МАТРИЦ ----DO I=1 TO M;   DO J=1 TO Q;          C(I,J)=0;          DO K=1 TO N;                 C(I,J)+=A(I,K)*B(K,J);          END K;   END J;END I;END УМНОЖЕНИЕ_МАТРИЦ;END TEST;

Эта тестовая программа эквивалентна приведенной ниже программе с обычными границами-константами у матриц.

TEST:PROC MAIN;DCL (P1,P2,P3)      PTR;             // УКАЗАТЕЛИ НА МАТРИЦDCL A1(5,4)         FLOAT BASED(P1), // СТАТИЧЕСКАЯ МАТРИЦА А1    B1(4,3)         FLOAT BASED(P2), // СТАТИЧЕСКАЯ МАТРИЦА B1    C1(5,3)         FLOAT BASED(P3); // СТАТИЧЕСКАЯ МАТРИЦА C1DCL (M1,N1,Q1)      FIXED(31);       // ЗАДАВАЕМЕ ГРАНИЦDCL (I,J)           FIXED(31);       // РАБОЧИЕ ПЕРЕМЕННЕ//---- ДЛЯ ТЕСТА ЗАДАЕМ НЕКОТОРЕ ЗНАЧЕНИЯ ГРАНИЦ ----M1=5; N1=4; Q1=3;//---- СОЗДАЕМ МАТРИЦ A1(M1,N1), B1(N1,Q1), C1(M1,Q1) ----ALLOCATE A1,B1,C1;//---- ДЛЯ ТЕСТА ЗАПОЛНЯЕМ МАТРИЦ НЕКОТОРМИ ЗНАЧЕНИЯМИ ----DO I=1 TO M1; DO J=1 TO N1; A1(I,J)=I+J; END J; END I;DO I=1 TO N1; DO J=1 TO Q1; B1(I,J)=I-J; END J; END I;//---- УМНОЖЕНИЕ МАТРИЦ A1 И B1, РЕЗУЛЬТАТ - МАТРИЦА C1 ----УМНОЖЕНИЕ_МАТРИЦ(ADDR(A1),ADDR(B1),ADDR(C1),M1,N1,Q1);//---- ВДАЕМ ПОЛУЧЕННЙ РЕЗУЛЬТАТ ----PUT SKIP DATA(C1);FREE A1,B1,C1;//========== УМНОЖЕНИЕ МАТРИЦ ЗАДАННОГО РАЗМЕРА ==========УМНОЖЕНИЕ_МАТРИЦ:PROC(P1,P2,P3,M,N,Q);//---- ВХОД A(M,N) И B(N,Q), ОТВЕТ - МАТРИЦА C(M,Q) ----DCL (P1,P2,P3)   PTR;             // УКАЗАТЕЛИ НА МАТРИЦDCL (M,N,Q)      FIXED(31);       // ЗАДАННЕ ГРАНИЦDCL A(5,4)       FLOAT BASED(P1), // СТАТИЧЕСКИЕ МАТРИЦ    B(4,3)       FLOAT BASED(P2),    C(5,3)       FLOAT BASED(P3);DCL (I,J,K)      FIXED(31);       // РАБОЧИЕ ПЕРЕМЕННЕ//---- САМО УМНОЖЕНИЕ МАТРИЦ ----DO I=1 TO M;   DO J=1 TO Q;          C(I,J)=0;          DO K=1 TO N;                 C(I,J)+=A(I,K)*B(K,J);          END K;   END J;END I;END УМНОЖЕНИЕ_МАТРИЦ;END TEST;

Обе программы дают идентичный результат:

C1(1,1)=  2.600000E+01 C1(1,2)=  1.200000E+01 C1(1,3)= -2.000000E+00C1(2,1)=  3.200000E+01 C1(2,2)=  1.400000E+01 C1(2,3)= -4.000000E+00C1(3,1)=  3.800000E+01 C1(3,2)=  1.600000E+01 C1(3,3)= -6.000000E+00C1(4,1)=  4.400000E+01 C1(4,2)=  1.800000E+01 C1(4,3)= -8.000000E+00C1(5,1)=  5.000000E+01 C1(5,2)=  2.000000E+01 C1(5,3)= -1.000000E+01

Заключение

Массивы с динамически меняющимися границами являются мощным и гибким инструментом и допустимы в ряде языков программирования. Однако этот инструмент требует и более сложного вычисления адресов элементов, в отличие от статических границ, когда часть вычислений можно выполнить уже на этапе компиляции.

Предлагаемые способ реализации оставляет исполняемый код таким же быстрым, как для массивов с границами-константами, изменяя лишь некоторые операнды-константы в командах с помощью вызова специальной служебной подпрограммы.

Это требует времени для подготовки выполняемого кода перед созданием очередного массива. Однако после такой корректировки констант в коде программы, ее выполнение идет так, словно границы массивов были изначально заданы нужными значениями, что позволяет сократить операции вычисления адресов элементов массивов и в целом ускорить программу, поскольку обычно требуется корректировка лишь нескольких команд, которые затем будут выполняться многократно.

В чем-то похожие подходы применялись и ранее, например, в языке Visual Basic имеется операция reDim, задающая границы при исполнении программы. Однако в этих случаях динамически меняются все же данные в программе, а не операнды команд ее исполняемого кода.

Кроме этого, данный способ является вообще простой возможностью ввода динамических массивов в компилятор, где их раньше не было, так как не требуется самого трудоемкого изменения генерации выполняемого кода. Код остается прежним, лишь дополняется данными, содержащими адреса команд, требующих корректировки своего операнда-константы.

Послесловие

Обращаю внимание гг. комментаторов, что утверждение: это никому не нужно, поскольку наш компилятор создает прекрасные динамические массивы некорректно. Корректно оно в виде мне и моим коллегам по проекту это не нужно. В этом случае я рад за вас, но считаю, что радовать остальных читателей такими комментариями необязательно.

Подробнее..

Проблема логических языков программирования

09.01.2021 22:17:27 | Автор: admin
Некоторое время назад я писал про Интернациональное программирование на естественных языках, в которой попытался представить достойную цель для абстрактного язык программирования, попробовав примерить на него роль связующего звена между миром программистов с компьютерами и не программистов.

Но в результате оказалось, что это не нужно в принципе, т.к. не программистам просто не требуется учиться писать программы. А если иногда такое желание и возникает, то вполне хватает обычных формализованных языков программирования, которых уже сейчас насчитывается наверно более десяти тысяч.

И пользователи, как программисты, так и не программисты, просто хотя решать возникающие перед ними задачи. И хотя задачи бывают совершенно разные, но если способ (алгоритм) её решения известен, то выбрать язык для её решения не составит никакого труда.

За исключением одного класса задач. Задач, решение которых которых нельзя описать в виде алгоритма. Но можно указать некие критерии, которым должно удовлетворять искомое решение. Я имею ввиду логические языки программирования и Пролог, как самый яркий представитель этого класса.

Еще помню воспоминание из юности, когда удалось достать дискету с этим языком. Ух, с каким задором горели мои глаза, когда мне казалось, ну вот, еще чуть-чуть и будет создана система с базой знаний, у которой и можно будет получить заветный ответ 42 на любой вопрос.

Так почему этого так и не случилось? В чем проблема Пролога, да и любой системы / языка программирования, назначение которых анализировать факты и искать ответы на вопросы?

Эта проблема называется Комбинаторный взрыв экспоненциальная зависимость времени работы алгоритма от количества входных данных. И есть как минимум два решения этой проблемы.



Подходы к написания программ


Прежде чем переходить к частностям, следует сказать пару слов про парадигмы программирования. Обычно противопоставляют между собой два разных стиля в написании программ: императивный и декларативный.

Императивный это классический вариант написания программы, при котором программист сам задает шаги алгоритма работы для получения конечного результата. А сам текст программы состоит из последовательности команд, которые читаю, сохраняют и обрабатывают данные или вызывают другие команды.

Декларативный в этом стиле программист описывает условия задачи и правила для получения требуемого результата, но не требуется детально описывать все шаги работы алгоритма, оставляя их на усмотрения компьютера.

Именно к декларативному стилю относится язык Пролог, да и все остальные логические языки программирования. К декларативному стилю написания программ следует относить и язык структурированных запросов (SQL).

И проблема под называнием Комбинаторный взрыв сильнее всего оказывает негативное влияние как раз на подобные языки. Ведь в императивном подходе программист сам отвечает за последовательность выполняемых команд, и если он запрограммировал алгоритм полного перебора всех возможных вариантов решений, то он сам себе злобный Буратино.

Другое дело, программирование в декларативном стиле. Разработчик хоть и может указать ограничения, которые следует применять при поиске решения, но это возможно только в том случае, когда известен алгоритм решения задачи. Но если алгоритм решения известен, то проще использовать императивный стиль, как раз и реализуя этот алгоритм!

Поэтому основное применения языков программирования в декларативном стиле отказаться от необходимости описания четкого алгоритма поиска решения, отдав это компьютеру на откуп. Для которого самое простое решение в лоб полный перебор возможных вариантов.

Именно в этом случае и начинается экспоненциальный рост времени выполнения алгоритма. И начиная с определенного порога, время ожидания ответа становится неприемлемым для реального использования. Это и означает Комбинаторный взрыв, резкий (взрывной) рост времени выполнения алгоритма при увеличении размера входных данных.

Проблема поиска решений


В языке Пролог эта проблема решалась за счет использования механизма отката и отсечений. Иногда еще уточняли про красное и зеленое отсечение решений. Но в любом случае, это были алгоритмические механизмы для ограничения количества размера дерева возможных решений, а необходимость их применения все равно остается на программисте.

Но чтобы их правильно реализовывать, нужно знать алгоритм решения, что опять возвращает нас к утверждению о том, что если известен алгоритм, то и программировать его удобнее в императивном стиле.

А если полный алгоритм решения задачи не известен (или не подходит, например из-за большого времени для его работы), то в результате остается либо увеличивать производительность системы, чтобы сократить время выполнения алгоритма, либо искать другое решение, в том числе, сокращая вычислительную сложность поиска решений, например, исключая заведомо не подходящие данные, чтобы уменьшить возможные комбинации их перебора.

Масштабирование производительности


Увеличение производительности тоже бывает разным и работает не во всех случаях. Вертикальное масштабирование производительности одного узла вычислительной среды имеет свой естественный предел. И даже многократное увеличение скорости работы компьютера может лишь отдалить порог терпения пользователя при ожидании получения результата, но не в состоянии принципиально решить саму проблему.

Другое дело горизонтальное масштабирование, при котором выполнение алгоритма запускается на отдельных узлах, которые параллельно решают одну и ту же задачу. Такой способ масштабирования позволяет уже значительно сократить время получения итогового результата для сложных вычислительных задач. И хотя это способ является решением в лоб, но успехи в области data science доказывают успешность такого подхода.

Конечно, у горизонтального масштабирования тоже есть подводные камни. В первую очередь, сам алгоритм должен допускать возможность параллельного выполнения независимо от других узлов. Так же требуется автоматизация управления заданиями, самими вычислительными узлами, да и всей системой в целом.

Тут частично может помочь парадигма функционального программирования, которая ограничивает результат вычисления функций только входными параметрами и результатом выполнения других функций, но сам результат не зависит от состояния системы или иных внешних данных.

Поиск обобщенного решения


Вторым способом решения решения проблемы комбинаторного взрыва является уменьшение вычислительной сложности решения. Тут имеется ввиду не выбор другого алгоритма или решение задачи в символьном виде. Если такое возможно, то все опять сразу сведется к императивному стилю программированию.

Я имею ввиду возможность поиска самого алгоритма решения. Точнее не совсем алгоритма, а возможность применения к входным данным различные методы отбора, чтобы исключить необходимость их полного перебора. По сути, это сводится к применению различных методов и механизмов обработки входных данных с учетом различных закономерностей.

Это возможно как алгоритмическими методами (откат и отсечение в Прологе), так и с применением машинного обучения, которое очень хорошо справляется с поиском различных закономерностей.

Естественно, такой способ подходит не для всех классов задач. Он не подходит для выявления ВСЕХ возможных решений. Но там где это не требуется, подобные способы уменьшения вычислительной сложности имею право на существование.

Например, не требуется искать все возможные лекарства от конкретной болезни, достаточно одного, с учетом определенных ограничений, которое гарантированно подействует.

К тому же, даже при нахождении частных решений, всегда существует шанс, что с их помощью получится увидеть не очевидные на первый взгляд закономерности, которые помогу показать новые пути алгоритмического уменьшения вычислительной сложности основной задачи.

Область не решаемых задач


Как вы считает, а реально ли создать язык логического программирования, который бы сам умел автоматизировать поиск решений для задач подобных классов? Или хотя бы имел в своем арсенале встроенные механизмы для автоматизации подобной деятельности?
Подробнее..

Как мы дом смоделировали

14.01.2021 12:05:51 | Автор: admin

Несколько лет назад я задумался, что моя работа стала ремеслом. Для того, чтобы разнообразить серые будни повысить свою стоимость как специалиста я поступил в магистратуру и сразу стал вопрос ребром - как после 15 лет после окончания первого ВТУЗа по написать ВКР, за которую не было бы стыдно?

Введение

Так получилось, что практически все 15 лет с того момента, как стал инженером, я занимался обслуживанием теплосчётчиков, стоящих в подвалах многоквартирных жилых домов (МКД). Данных накопилось достаточно, чтобы их смело назвать big data.

Не буду расписывать подробно физику процесса теплопотерь зданий и сооружений, только напишу некоторые допущения, на которые пришлось пойти:

  1. Температура внутри дома. Большая инженерная проблема. Где измерять правильно? сколько точек в каких местах? Я решил ввести "средний градус по больнице" и взял это как 24 градуса.

  2. Температура на улице. Данные с Росгидромета получить можно только за деньги. Именно ей оперируют энергоснабжающие организации, когда ведут все свои расчёты. У нас в городе оказалось, что есть лаборатория оптической погоды, которая измеряет так же, но для науки данные даёт бесплатно. Написали письмо с научруком - получили данные.

  3. Частота измерений. Тут думать не пришлось, решили что суточный архив теплосчётчика - будет достаточно. Жилой дом - достаточно стационарная штука, медленно греется, медленно остывает.

  4. Данные должны быть очищены. Бывает так, что теплосчётчик "не работает". Иногда это связано с его неисправностью, иногда - с режимами наладки. Для моделирования лучше использовать валидные данные - например, когда он допущен к коммерческому расчёту.

  5. Данные ограничены периодом с начала декабря 2013 по 27 марта 2017 года. As is.

  6. Обработка данных в Statistica. Такую задачу мне поставил научрук, академическую лицензию я приобрёл.

Немного теории

Из мировой практики [1] выделим два подходящих для поставленной задачи метода измерения:

Анализ показаний приборов учета теплопотребления МКД. Основывается на долгосрочных измерениях энергопотребления всего здания в целом с помощью приборов учета.

Расчетно-экспериментальный метод на базе компьютерного моделирования. Основывается на проведении компьютерного моделирования энергопотребления, чаще всего здания в целом.

Мы оба метода объединили: вывели на основании показаний теплосчётчика удельную характеристику теплопотребления дома и создали простую математическую модель.

Потребление тепла МКД зависит от наружной температуры, больше перепад больше потребление. Так же, очевидно, потребление зависит от величины дома, энергоснабжающая организация в своих расчётах использует суммарную жилую площадь, мы привели полученные величины к жилой площади дома. Используя [2] уравнение теплового баланса, вывели формулу 1 коэффициента теплоотдачи [3]

G=Q/(t*(Tвн-Tнар)*S)

где G коэффициент теплоотдачи, Вт/м2*С;

Q количество тепла за сутки из данных, ГКал;

Твн средняя температура в жилых помещениях МКД, принятая за плюс 24С;

Тнар среднесуточная температура внешней среды за учитываемые сутки, С;

вннар) тепловой напор, С;

S жилая площадь, м2;

t количество часов в сутках, 24 часа.

Очевидно, что коэффициент теплоотдачи является функцией от теплового напора, формула 2 :

G=f(Tвн-Tнар )

Так как вид функции неизвестен, мы можем её попробовать найти её аналитическим путём.

Разработка методики расчётов

По полноте данных, 830 суточных записей - максимальное количество данных за вышеозначенный период был выбран дом : двухподъездный четырёхэтажный дом 1965 года постройки. Материал стен силикатный кирпич, кровля скатная, фасад утеплён минераловатной плитой и закрыт сайдингом.

На рисунке ниже изображена гистограмма вычисленного коэффициента теплоотдачи согласно формуле 1 с наложением среднесуточных температур на ось времени. Нужно отметить, что пиковые значения коэффициента приходятся на даты, когда температура наружного воздуха выше 0С.

Пропуск данных в отопительном сезоне 2015-2016 гг. объясняется неисправностью узла учёта, то есть данные за этот период удалены во время очистки как некорректные.

По формуле 2 построим облако точек [4] наблюдений используя программу Statistica, диаграмма рассеяния изображена на рисунке ниже.

Так как наблюдения на диаграмме рассеяния приведены за разные годы, очевидно, что распределение подчиняется некоторой зависимости. Программа Statistica позволяет на основании данных создать аппроксимирующие уравнения с разными степенями подгонки. Регрессионная граница - предсказанный интервал вокруг подогнанной (регрессионной) линии. Можно ввести значение вероятности (Уровень) того, что "истинная" подогнанная линия (для совокупности) попадет между границами. Стандартная ошибка для подогнанной линии (которая отражает прогнозируемые значения при данной линейной или полиномиальной подгонке) вычисляется на основе модели полиномиальной регрессии (предполагается, что данные и их полиномиальные преобразования распределены нормально).

Проверим распределение переменной G на нормальность:

А дальше программа аппроксимировала. Наиболее удачным вариантом мы сочли полином третьей степени, так как в предсказанный интервал попадает наибольшее количество точек:

Промежуточный итог

Само полученное уравнение регрессии является математической моделью теплопотребления выбранного МКД.

Видно, что наиболее "дорогими" с точки зрения энергозатрат являются моменты, когда наружняя температура воздуха очень близка к температуре внутри дома.

По большей части статья содержит материалы моей магистерской и не может претендовать на абсалютную истину. Это скорей попытка глянуть сверху на результаты напряженной работы.

Буду благодарен за критику.

Ссылки на источники

1. Наумов, А. Л. Определение класса энергетической эффективности эксплуатируемых жилых многоквартирных домов / А. Л. Наумов, Д. В. Капко // Энергосбережение. 2015. 8. С. 2430.

2. Mukashev A., Dynamic method of the heating devices efficiency measurement // Mukashev A., Pugovkin A., Kuprekov S., Petrova N.,Abramchuk S, International Scientific Conference Environmental and Climate Technologies, CONECT2017,Riga.

3. П.А. Зорин Контроль энергоэффективности теплоснабжения зданий типовой застройки / П.А. Зорин, С.В. Купреков, А.В. Пуговкин, О.В. Стукач, сборник материалов XIV Международной научно-практической конференции Электронные методы и системы управления, Томск: Томск. гос. ун-т систем упр. и радиоэлектроники, 2018, том 2, С.302-305.

4. О.В. Стукач Программный комплекс Statistica в решении задач управления качеством: Учебное пособие; Национальный исследовательский Томский политехнический университет. Томск: Изд-во Томского политехнического университета, 2011. 163 с.

Подробнее..

Перевод числа в строку с помощью FPU

17.01.2021 06:18:51 | Автор: admin

Введение

Часто требуемое для вывода результатов расчетов преобразование числа с плавающей точкой из формата IEEE-754 в текстовую строку в научной нотации (т.е. с показателем степени E) не является совсем уж тривиальной задачей. В силу обстоятельств автору пришлось самостоятельно изобретать велосипед такого преобразования. Причем хотелось сделать это максимально эффективно, в полной мере используя аппаратные возможности обработки чисел.

Как ни странно, в литературе мне не попалось ни одного готового примера на эту тему. Поэтому описываемое ниже собственное решение призвано восполнить этот пробел в виде представленной ассемблерной процедуры, которая входит в системную библиотеку сопровождаемого транслятора в течение многих лет и, таким образом, надежно проверена на практике.

Постановка задачи

Формализуем задачу. Необходимо перевести восьмибайтовое число из формата IEEE-754 в текстовую строку, где указан знак числа, мантисса заданной длины и десятичный порядок с признаком E и своим знаком.

Так, если задано число 1234.567890, то строка с мантиссой, например, в 16 знаков должна выглядеть как 1.23456788999999E+003. Вместо плюса у мантиссы нужно писать пробел, а сама мантисса должна быть не меньше единицы. Кстати, данный пример иллюстрирует дискретность и приближенность представления чисел в формате IEEE-754: приведенное исходное число не может быть точно представлено как 1.23456789000000E+003, что, может быть, интуитивно ожидалось.

Использование команд FPU для преобразования

На первый взгляд, решение выглядит простым. В устройстве FPU (Floating Point Unit) процессора даже имеются команды, явно предназначенные и для перевода чисел из формата IEEE-754 в текст. Это, во-первых, команда EXTRACT разделения числа на мантиссу и порядок, а во-вторых, команда FBSTP выдающая мантиссу сразу в виде двоично-десятичного значения. Однако при ближайшем рассмотрении эти команды не дают нужного результата.

Например, если применить команду FBSTP к указанному выше числу, то получится 10 байт со значением 35 12 00 00 00 00 00 00 00 00, поскольку нецелочисленные значения сначала округляются согласно полю RC управляющего слова FPU. Это двухбитовое поле RC может принимать 4 значения, но среди них нет режима отключить округление. Поэтому часть мантиссы просто теряется, единственное чего можно добиться режимами округления это еще получить значение 34 12 при округлении к меньшему.

Да и порядок числа, так легко выделяемый командой EXTRACT, является все же степенью двойки, а не десятки, как требуется в данном случае для вывода.

Итак, при использовании возможностей FPU придется решать две задачи.

Во-первых, умножением (или делением) исходного числа на десять нужно перегнать всю мантиссу в целочисленную часть числа, тогда команда FBSTP выдаст, наконец, в двоично-десятичном виде все цифры мантиссы.

Во-вторых, нужно определить такой десятичный порядок (опять-таки умножением или делением на десять), при котором результат попадет в диапазон между 1 и 10. Это нужно для представления числа в виде мантиссы с одной цифрой перед точкой и найденным порядком. Увы, совместить эти две задачи в едином цикле умножения/деления невозможно.

Причем есть и подводный камень в виде значения числа, максимально приближенного к единице, но не равного единице. Циклом деления или умножения легко можно ошибиться в показателе степени и вместо требуемого в данном случае 9.999E-001 получить неправильное значение типа 9.999E+000. К сожалению, при всем богатстве команд FPU обойтись без циклов деления и умножения на десять не удается.

Алгоритм преобразования

При формировании мантиссы для числа типа double умножение или деление на 10 продолжаются до тех пор, пока двоичный порядок числа не достигнет (или не станет больше/меньше) 53, поскольку под мантиссу выделено именно 53 двоичных разряда.

При формировании десятичного порядка для числа типа double умножение или деление на 10 продолжаются до тех пор, пока двоичный порядок разницы числа и 1 не достигнет (или не станет больше/меньше) -53, что означает максимальное приближение к 1. При этом необходимо еще отслеживать частный случай ближайшего к 1 значения из одних девяток, поскольку цикл умножения или деления в этом случае дает одну лишнюю или одну недостающую степень.

Пример реализации преобразования

Далее приведена ассемблерная подпрограмма преобразования числа в текст именно так, как она записана в системной библиотеке. Хотя при этом появляются дополнительные детали, связанные с особенностями использования в конкретном трансляторе, я считаю правильнее ничего не выбрасывать и не превращать реализацию в короткий, но искусственный и не работающий во всех случаях пример.

Пара комментариев к тексту. Подпрограмма написана на языке ассемблера RASM, который имеет некоторые особенности.

В частности здесь используются временные метки в виде символа @. Алгоритм их реализации следующий: транслятор имеет внутренний счетчик меток. Когда метка @ встречается в команде перехода, к ней автоматически дописывается значение этого счетчика (т.е. реально создаются метки @0000, @0001 и т.д.). Когда встречается символ @ с двоеточием, к нему также автоматически приписывается значение счетчика и после этого счетчик увеличивается на 1.

Таким образом, получаются метки, на которые можно передавать управление только вперед и использовать многократно, не придумывая для каждой следующей метки новое имя. Поскольку в ассемблере метки часто используются лишь однократно для обхода группы команд, такой прием упрощает написание и анализ программы.

Кроме этого, для команд FPU в RASM не анализируется размер операнда, он имеется прямо в названиях команд в виде значений 16, 32, 64 или 80.

Но вернемся к задаче. Подпрограмме по адресу в EBX передается исходное восьмибайтовое число в формате IEEE-754 и требуемая длина текстовой строки-результата в AL.

В результате работы число записывается в стек в виде текста в научной нотации и в AL сохраняется длина этой строки. Другие регистры не сохраняются.

С целью разгрузить конвейеры процессора некоторые команды рассыпаны по тексту и не образуют непрерывных логических цепочек, что несколько затрудняет чтение текста. Но таких мест немного. Программа реентерабельна и может быть использована в параллельных вычислениях. При начале работы программы управляющее слово FPU CW=0360.

  1. Сначала в стеке выделяется место для ответа и заполняется нулевым шаблоном, т.е. значением 0.000 E+000.

  2. Затем проверяется знак числа и в зависимости от него формируется мантисса умножением или делением числа на десять.

  3. Командой FBSTP мантисса переписывается в память из FPU в двоично-десятичном виде и ее часть (заданной длины) переносится в ответ.

  4. После этого исходное число опять-таки умножением или делением на десять как можно ближе подгоняется к 1, что позволяет вычислить требуемый десятичный порядок, который и записывается на заранее подготовленное в ответе место.

      CSEGPUBLIC ?QFCMW:;---- ПОДГОТОВКА МЕСТА В СТЕКЕ ----      MOVZX     ECX,AL          ;ЗАДАННАЯ ДЛИНА СТРОКИ      POP       EAX             ;ДОСТАЛИ АДРЕС ВОЗВРАТА      SUB       ESP,ECX         ;ВДЕЛИЛИ МЕСТО В СТЕКЕ      MOV       EDI,ESP         ;ОНО ЖЕ НАЧАЛО СТРОКИ-РЕЗУЛЬТАТА      MOV       ESI,ESP         ;ЗАПОМНИЛИ НАЧАЛО      PUSH      EAX             ;АДРЕС ВОЗВРАТА ВЕРНУЛИ НА МЕСТО      PUSH      ECX             ;ЗАПОМНИЛИ ЗАДАННУЮ ДЛИНУ ОТВЕТА;---- СНАЧАЛА ЗАПОЛНЕНИЕ СТРОКИ-РЕЗУЛЬТАТА НУЛЕВМ ШАБЛОНОМ ----      MOV       EAX,'0.0 '      ;ЗНАК И ПЕРВОЕ ЧИСЛО С ТОЧКОЙ      STOSD      DEC       EDI             ;ОСТАВЛЯЕМ ПЕРВЕ ТРИ СИМВОЛА ШАБЛОНА      SUB       CL,8            ;ВЧЛИ СЛУЖЕБНЕ ЗНАКИ И ПОРЯДОК      MOV       AL,'0'      JBE       @               ;ОШИБКА, НЕТ МЕСТА ПОД МАНТИССУ      REP       STOSB           ;ЗАПОЛНИЛИ МАНТИССУ НУЛЯМИ@:    MOV       EAX,'00+E'      ;ПОКА ДВА НУЛЯ ПОРЯДКА      STOSD                     ;ЗАПИСАЛИ НУЛЕВОЙ ПОРЯДОК      LEA       EBP,[EDI]-2     ;ЗАПОМНИЛИ АДРЕС ПОРЯДКА      FLD64     [EBX]           ;ЗАГРУЗИЛИ ЗАДАННОЕ ЧИСЛО      MOV       B PTR [EDI],'0' ;ПОКА ТРЕТИЙ НУЛЬ ПОРЯДКА;---- ПРОВЕРКА ЗАДАННОГО ЧИСЛА НА ПЛЮС/МИНУС/НОЛЬ ----      FTST                      ;СРАВНИЛИ С НУЛЕМ      FNSTSW    AX      SAHF      JNZ       @               ;ЗАДАННОЕ ЧИСЛО НЕ НОЛЬ;---- СРАЗУ ВХОД С ЧИСТМ НУЛЕМ ----      POP       EAX             ;ВХОД С ЗАДАННОЙ ДЛИНОЙ И НУЛЕМ      FSTP      ST              ;ОЧИСТИЛИ FPU ОТ ИСХОДНОГО ЧИСЛА      RET;---- ОБРАБОТКА ЗНАКА ЗАДАННОГО ЧИСЛА ----@:    JNB       @               ;ЕСЛИ ЧИСЛО ПОЛОЖИТЕЛЬНО      MOV       B PTR [ESI],'-' ;ОТМЕТИЛИ ЗНАК ОТРИЦАТЕЛЬНОГО      FABS                      ;УБРАЛИ ЗНАК В САМОМ ЧИСЛЕ@:    MOV       EDX,OFFSET ДЕСЯТЬ ;ДЕСЯТИЧНАЯ СИСТЕМА;---- ПРОВЕРКА ВЕЛИЧИН ПОРЯДКА ИСХОДНОГО ЧИСЛА ----      FLD       ST              ;РАЗМНОЖИЛИ ПОЛОЖИТЕЛЬНОЕ ЧИСЛО      POP       ECX             ;ОПЯТЬ ДОСТАЛИ ДЛИНУ СТРОКИ      FXTRACT                   ;РАЗДЕЛИЛИ МАНТИССУ И ПОРЯДОК      PUSH      ECX             ;ОПЯТЬ СОХРАНИЛИ ДЛИНУ СТРОКИ      FSTP      ST              ;ВКИНУЛИ МАНТИССУ      SUB       ESP,11          ;ВДЕЛИЛИ МЕСТО ПОД МАНТИССУ КАК BCD      FIST32P   [ESP]           ;ЗАПИСАЛИ ПОРЯДОК      CMP       D PTR [ESP],53  ;ОН УЖЕ 53 РАЗРЯДА ?      JE        M0003           ;ТОГДА МАНТИССА УЖЕ ГОТОВА      JL        M0002           ;ИНАЧЕ ЧИСЛО ОЧЕНЬ МАЛО;---- УМЕНЬШЕНИЕ ПОРЯДКА ЧИСЛА ОТ ОЧЕНЬ БОЛЬШОГО ----M0001:FLD       ST              ;РАЗМНОЖИЛИ ЧИСЛО      FXTRACT                   ;РАЗДЕЛИЛИ МАНТИССУ И ПОРЯДОК      FSTP      ST              ;ВКИНУЛИ МАНТИССУ      FIST32P   [ESP]           ;ДОСТАЛИ ПОРЯДОК      CMP       D PTR [ESP],53  ;УЖЕ 53 РАЗРЯДА ?      JLE       M0003           ;ТОГДА МАНТИССА УЖЕ ГОТОВА      FIDIV16   [EDX]           ;РАЗДЕЛИЛИ ЧИСЛО НА ДЕСЯТЬ      JMPS      M0001           ;ПРОВЕРЯЕМ НОВЙ ПОРЯДОК;---- УВЕЛИЧЕНИЕ ПОРЯДКА ЧИСЛА ОТ ОЧЕНЬ МАЛОГО ----M0002:FLD       ST              ;РАЗМНОЖИЛИ ЧИСЛО      FXTRACT                   ;РАЗДЕЛИЛИ МАНТИССУ И ПОРЯДОК      FSTP      ST              ;ВКИНУЛИ МАНТИССУ      FIST32P   [ESP]           ;ДОСТАЛИ ПОРЯДОК      CMP       D PTR [ESP],53  ;УЖЕ 53 РАЗРЯДА ?      JGE       M0003           ;ТОГДА МАНТИССА УЖЕ ГОТОВА      FIMUL16   [EDX]           ;УМНОЖИЛИ ЧИСЛО НА 10      JMPS      M0002           ;ПРОВЕРЯЕМ НОВЙ ПОРЯДОК;---- ВДАЧА МАНТИСС В ДВОИЧНО-ДЕСЯТИЧНОМ ВИДЕ ----M0003:FBSTP     [ESP]+1         ;ЗАПОМНИЛИ МАНТИССУ КАК BCD-ФОРМАТ;---- ФОРМИРОВАНИЕ ТЕКСТА ИЗ BCD-МАНТИСС ----      LEA       EDI,[ESI]+1     ;АДРЕС ОТВЕТА ПОСЛЕ ЗНАКА      FLD1                      ;ЗАГРУЗИЛИ КОНСТАНТУ 1E0      SUB       CL,7            ;ЗАДАННАЯ ДЛИНА МАНТИСС В ОТВЕТЕ      FLD64     [EBX]           ;ОПЯТЬ ЗАГРУЗИЛИ ИСХОДНОЕ ЧИСЛО      LEA       ESI,[ESP]+10    ;АДРЕС ПЕРВХ ЦИФР МАНТИСС      STD      MOV       DH,0            ;ПОКА НУЛИ НЕ ПИШЕМ      FABS                      ;ЗНАК ИСХОДНОГО ЧИСЛА БОЛЬШЕ НЕ НУЖЕН      MOV       AH,0            ;НАЧИНАЕМ С ЧЕТНОЙ ТЕТРАД      FCOM                      ;ЗАРАНЕЕ СРАВНИВАЕМ ЧИСЛО С 1E0      MOV       BL,1            ;ПОКА ОНО МОЖЕТ БТЬ ВБЛИЗИ +1/-1;---- ЦИКЛ ПЕРЕПИСИ ПО ВСЕМ ТЕТРАДАМ BCD-МАНТИСС ----M0004:XOR       AH,1            ;ОЧЕРЕДНАЯ ТЕТРАДА      JZ        @               ;ЕСЛИ НЕЧЕТНАЯ ТЕТРАДА      LODSB                     ;ДОСТАЛИ БАЙТ МАНТИСС      CMP       ESI,ESP         ;ЗА ПРЕДЕЛАМИ МАНТИСС ?      MOV       DL,AL           ;ДВЕ ТЕТРАД МАНТИСС      JB        M0007           ;ЗАКОНЧИЛИ ВВОД;---- ЧЕТНАЯ ТЕТРАДА ----      SHR       AL,4            ;ЧЕТНАЯ ТЕТРАДА BCD      JMPS      M0005;---- НЕЧЕТНАЯ ТЕТРАДА ----@:    MOV       AL,DL      AND       AL,0FH          ;НЕЧЕТНАЯ ТЕТРАДА BCD;---- ПРОПУСК ЛИДИРУЮЩИХ НУЛЕЙ МАНТИСС ----M0005:OR        DH,AL           ;ЕЩЕ ИДУТ НУЛИ МАНТИСС ?      JNZ       @               ;УЖЕ ИДУТ ЦИФР МАНТИСС      INC       ECX             ;НЕ УЧИТВАЕМ ЭТОТ НОЛЬ В МАНТИССЕ      JMPS      M0006           ;ПРОПУСКАЕМ НЕЗНАЧАЩИЙ НОЛЬ;---- ПРОВЕРКА НА ВСЕ ДЕВЯТКИ (Т.Е. НА ЧИСЛО ВБЛИЗИ +1/-1) ----@:    CMP       AL,9            ;ИДУТ СПЛОШНЕ ДЕВЯТКИ ?      JZ        @               ;ДА, ПРОДОЛЖАЮТСЯ ДЕВЯТКИ      MOV       BL,0            ;УЖЕ НЕ ВБЛИЗИ +1/-1 (НЕ ДЕВЯТКА);---- ПРОПУСК ТОЧКИ, ЗАРАНЕЕ ЗАПИСАННОЙ В ОТВЕТ ----@:    CMP       B PTR [EDI],'.' ;ЗДЕСЬ В ШАБЛОНЕ ТОЧКА ?      JNZ       @      INC       EDI             ;ПРОПУСКАЕМ ТОЧКУ;---- ЗАПИСЬ ОЧЕРЕДНОЙ ЦИФР МАНТИСС КАК ТЕКСТА ----@:    ADD       [EDI],AL        ;ПИШЕМ ОЧЕРЕДНУЮ ЦИФРУ В ОТВЕТ      INC       EDI             ;СЛЕДУЮЩИЙ АДРЕСM0006:LOOP     M0004            ;ЗА СЛЕДУЮЩЕЙ ТЕТРАДОЙM0007:CLD;---- ФОРМИРОВАНИЕ ВЕЛИЧИН ПОРЯДКА ----      MOV       ESI,OFFSET ДЕСЯТЬ      FNSTSW    AX      XOR       EDX,EDX         ;ПОКА ПОРЯДОК НОЛЬ      SAHF      JZ        M0011           ;ЧИСЛО СТРОГО РАВНО 1 - ПОРЯДОК НОЛЬ      JA        M0009           ;ЧИСЛО БОЛЬШЕ 1 - ПОРЯДОК ПОЛОЖИТЕЛЕН      MOV       B PTR [EBP]-1,'-' ;ОТМЕТИЛИ ОТРИЦАТЕЛЬНЙ ПОРЯДОК;---- УВЕЛИЧЕНИЕ ПОРЯДКА ДО ЧИСЛА БОЛЬШЕ 1 ----M0008:FIMUL16   [ESI]           ;УВЕЛИЧИЛИ ЧИСЛО В 10 РАЗ      INC       EDX             ;УВЕЛИЧИЛИ ПОРЯДОК      FCOM                      ;СРАВНИВАЕМ С 1      FNSTSW    AX              ;ЗАПОМНИЛИ РЕЗУЛЬТАТ СРАВНЕНИЯ      SAHF      JZ        M0011           ;СТРОГО РАВНО 1 - НАШЛИ ПОРЯДОК      FLD       ST              ;РАЗМНОЖИЛИ ЧИСЛО      FSUB      ST,ST2          ;РАЗНИЦА С 1      FXTRACT                   ;ДОСТАЛИ МАНТИССУ И ПОРЯДОК      FSTP      ST              ;ВБРОСИЛИ МАНТИССУ      FIST32P   [ESP]           ;ПОРЯДОК РАЗНИЦ      CMP       D PTR [ESP],-53 ;УЖЕ ВПЛОТНУЮ К 1 ?      JLE       M0010           ;ДА, ВПЛОТНУЮ, БЛИЖЕ НЕ БУДЕТ      SAHF                      ;ОПЯТЬ ДОСТАЛИ ФЛАГИ СРАВНЕНИЯ С 1      JA        M0011           ;УЖЕ БОЛЬШЕ - НАШЛИ ПОРЯДОК      JMPS      M0008           ;ПРОДОЛЖАЕМ УМНОЖАТЬ НА 10;---- УМЕНЬШЕНИЕ ПОРЯДКА ДО ЧИСЛА МЕНЬШЕ 1 ----M0009:FIDIV16   [ESI]           ;УМЕНЬШИЛИ ЧИСЛО В 10 РАЗ      INC       EDX             ;УМЕНЬШИЛИ ПОРЯДОК      FCOM                      ;СРАВНИВАЕМ С 1      FNSTSW    AX              ;ЗАПОМНИЛИ РЕЗУЛЬТАТ СРАВНЕНИЯ      SAHF      JZ        M0011           ;СТРОГО РАВНО 1 - НАШЛИ ПОРЯДОК      FLD       ST              ;РАЗМНОЖИЛИ ЧИСЛО      FSUB      ST,ST2          ;РАЗНИЦА С 1      FXTRACT                   ;ДОСТАЛИ МАНТИССУ И ПОРЯДОК      FSTP      ST              ;ВБРОСИЛИ МАНТИССУ      FIST32P   [ESP]           ;ПОРЯДОК РАЗНИЦ      CMP       D PTR [ESP],-53 ;УЖЕ ВПЛОТНУЮ К 1 ?      JG        @               ;ЕЩЕ НЕ ВПЛОТНУЮM0010:INC       EBX             ;ПРИЗНАК НАХОЖДЕНИЯ ВБЛИЗИ 1      JMPS      M0011           ;ПЕРЕСТАЕМ ИСКАТЬ ПОРЯДОК@:    SAHF                      ;ОПЯТЬ ЗАГРУЗИЛИ ФЛАГИ СРАВНЕНИЯ С 1      JNB       M0009           ;ПРОДОЛЖАЕМ ДЕЛИТЬ НА 10      DEC       EDX             ;ЧИСЛО В ОТВЕТЕ ДОЛЖНО БТЬ БОЛЬШЕ 1M0011:ADD       ESP,11          ;ОСВОБОДИЛИ СТЕК ОТ BCD-МАНТИСС;---- КОРРЕКТИРОВКА ПОРЯДКА ВБЛИЗИ +/-1 ----      CMP       BL,2            ;БЛИ ВСЕ ДЕВЯТКИ И ПОЧТИ 1 ?      XCHG      EAX,EDX         ;ДОСТАЛИ ЗНАЧЕНИЕ ПОРЯДКА      JNZ       @               ;НЕТ, ЧИСЛО НЕ ВБЛИЗИ 1      DEC       EAX             ;ВБЛИЗИ 1 СВЕРХУ, ДЕЛАЕМ 0.999...E+000      CMP       B PTR [EBP]-1,'-' ;ЧИСЛО МЕНЬШЕ 1E0 ?      JNZ       @               ;НЕТ, БОЛЬШЕ      INC       EAX             ;ВЕРНУЛИ ПОРЯДОК      INC       EAX             ;ВБЛИЗИ 1 СНИЗУ,  ДЕЛАЕМ 9.999...E-001;---- ЗАПИСЬ СТАРШЕЙ ЦИФР ПОРЯДКА ----@:    PUSH      100      XOR       EDX,EDX      POP       EBX             ;ДЕЛИМ НА КОНСТАНТУ 100      FSTP      ST              ;ОЧИЩАЕМ FPU ОТ ПОИСКА ПОРЯДКА      DIV       EBX             ;ПОЛУЧАЕМ ЧАСТНОЕ - ПЕРВУЮ ЦИФРУ      ADD       [EBP],AL        ;СТАРШАЯ ЦИФРА ПОРЯДКА;---- ЗАПИСЬ ДВУХ МЛАДШИХ ЦИФР ПОРЯДКА ----      MOV       BL,10           ;ДЕЛИМ НА КОНСТАНТУ 10      XCHG      EAX,EDX         ;ОСТАТОК ОТ ДЕЛЕНИЯ НА 100      DIV       BL              ;ЧАСТНОЕ И ОСТАТОК - ДВЕ ЦИФР ПОРЯДКА      FSTP      ST              ;ВБРОСИЛИ КОНСТАНТУ 1 ИЗ FPU      ADD       [EBP]+1,AX      ;ДВЕ ОСТАЛЬНЕ ЦИФР ПОРЯДКА;---- ВХОД С ОТВЕТОМ В СТЕКЕ И ДЛИНОЙ СТРОКИ В AL ----      POP       EAX             ;ДЛИНА СТРОКИ ОТВЕТА В СТЕКЕ      RET      DSEGДЕСЯТЬ DW 10                    ;БАЗА ДЛЯ ПЕРЕВОДА В ДЕСЯТИЧНУЮ СИСТЕМУ

Заключение

Использование команд FPU сделало данную реализацию довольно компактной (326 байт команд) и удовлетворительной по скорости. Например, на компьютере с процессором Intel Core Solo 1.33 GHz сто миллионов преобразований числа 1234.567890 в текст заняли 89 секунд.

Таким образом, скорость работы данной подпрограммы составила 845 преобразований в секунду на каждый мегагерц тактовой частоты процессора. При этом полный отказ от использования команд FPU вряд ли позволит увеличить скорость требуемого преобразования.

Однако эффективность преобразования числа в текст могла бы быть повышена, если бы разработчики FPU предусмотрели режим без округления для команды FBSTP. Это позволило бы при применении этой команды для перевода мантиссы в текст избежать циклов умножения и деления на десять лишь только для получения всех значащих цифр.

Подробнее..

Linked List Когда нужно писать свой Copy-on-write в iOS?

01.01.2021 18:11:05 | Автор: admin

Я всегда думал: "А зачем нужно писать свой copy-on-write? Ведь круто, когда есть структуры и они такие быстрые, что всё делают за тебя."

Но все это не нужно, пока не начинаешь писать свои типы и не подсаживаешься на LinkedList'ы.

Что такое этот связанный список и какие у него преимущества?

Связанный список имеет несколько теоретических преимуществ по сравнению с вариантами непрерывного хранения, такими как Array:

  • Связанные списки имеют временную сложность O (1) для вставки первых элементов. Массивы же имеют временную сложность O (n).

  • Соответствие протоколам сбора Swift, таким как Sequence и Collection, предлагает множество полезных методов для довольно небольшого количества требований.

Связанный список (Linked List) - это последовательность элементов данных, в которой каждый элемент называется узлом (Node).

Есть два основных типа связанных списков:

Односвязные списки - это связанные списки, в которых каждый узел имеет ссылку только на следующий узел.

Двусвязные списки - это связанные списки, в которых каждый узел имеет ссылку на предыдущий и следующий узел.

Вам нужно отслеживать, где список начинается и где заканчивается. Обычно это делается с помощью указателей, называемых head и tail.

Вот так это всё выглядит:

public class Node<Value> {  public var value: Value  public var next: Node?      public init(value: Value, next: Node? = nil) {    self.value = value    self.next = next  }}public struct LinkedList<Value> {  public var head: Node<Value>?  public var tail: Node<Value>?    public init() {}  public var isEmpty: Bool { head == nil }}

Вау, прикольная структура данных! Она знает и предыдущий, и следующий элемент. Также в списке мы быстро можем добавить. Но есть проблема.

Так как наша Node'a является классом, а значит и reference type. Это значит, что для многих узлов у нас есть общая ячейка памяти и куча ссылок на них. Они могут расти и с большими размера за ними сложно наблюдать.

Как решить эту проблему? Поскольку LinkedList является структурой и поэтому должен использовать семантику значений. Внедрение своего COW решит эту проблему.

Сделать value type значений с помощью COW довольно просто. Прежде чем изменять содержимое связанного списка, вы хотим создать копию базового хранилища и обновить все ссылки (начальные и конечные) на новую копию.

private mutating func copyNodes() {  guard var oldNode = head else {      return  }  head = Node(value: oldNode.value)  var newNode = head    while let nextOldNode = oldNode.next {    newNode!.next = Node(value: nextOldNode.value)    newNode = newNode!.next    oldNode = nextOldNode  }  tail = newNode}

Этот метод заменит существующие узлы связанного списка вновь выделенными узлами с тем же значением. Здесь всё очень круто, кроме введения накладных расходов O (n) на каждый вызов изменения

Оптимизируем COW

Накладные расходы O (n) при каждом вызове изменения недопустимы.

Есть два пути, которые помогают решить эту проблему. Первый - избегать копирования, когда у узлов только один владелец.

isKnownUniquelyReferenced

В стандартной библиотеке Swift существует функция isKnownUniquelyReferenced. Эта функция может использоваться, чтобы определить, имеет ли объект ровно одну ссылку на него.

И если добавить в начало функции copyNodes() код, то копировать дальше не надо:

private mutating func copyNodes(returningCopyOf node:Node<Value>?) -> Node<Value>? {  guard !isKnownUniquelyReferenced(&head) else {return nil  }  guard var oldNode = head else {return nil}  head = Node(value: oldNode.value)  var newNode = head  var nodeCopy: Node<Value>?  while let nextOldNode = oldNode.next {    if oldNode === node {      nodeCopy = newNode    }    newNode!.next = Node(value: nextOldNode.value)    newNode = newNode!.next    oldNode = nextOldNode}  return nodeCopy}

Этот метод имеет много общего с предыдущей реализацией. Основное отличие состоит в том, что он вернет вновь скопированный узел на основе переданного параметра.

Таким образом Copy-on-write не является чем-то далеким и подкапотным. А вполне управляемым и понятным.

Подробнее..
Категории: Алгоритмы , Swift , Linkedlist

Кодирование для чайников, ч.1

01.01.2021 18:11:05 | Автор: admin

Не являясь специалистом в обозначенной области я, тем не менее, прочитал много специализированной литературы для знакомства с предметом и прорываясь через тернии к звёздам набил, на начальных этапах, немало шишек. При всём изобилии информации мне не удалось найти простые статьи о кодировании как таковом, вне рамок специальной литературы (так сказать без формул и с картинками).

Статья, в первой части, является ликбезом по кодированию как таковому с примерами манипуляций с битовыми кодами, а во второй я бы хотел затронуть простейшие способы кодирования изображений.

0. Начало

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

Чего мне не хватало в 70-80-е, так это в школе, пусть не на информатике, а, например, на уроках математики - базовой информации по кодированию. Дело в том, что кодированием информации каждый из нас занимается ежесекундно, постоянно и в целом - не концентрируясь на самом кодировании. То есть в быту мы это делаем постоянно. Так как это происходит?

Мимика, жесты, речь, сигналы разного уровня - табличка с надписью, знак на дороге, светофоры, и для современного мира - штрих- и бар-коды, URL, хэш-тэги.

Давайте рассмотрим некоторые более подробно.

1.1 Речь, мимика, жесты

Удивительно, но всё это - коды. С помощью них мы передаём информацию о своих действиях, ощущениях, эмоциях. Самое важное, чтобы коды были понятны всем. Например, родившись в густых лесах у Амазонки и не видя современного городского человека, можно столкнуться с проблемой непонимания кода - улыбка, как демонстрация зубов, будет воспринята как угроза, а не как выражение радости.

Следуя определению, что же происходит когда мы говорим? Мысль - как форма, удобная для непосредственного использования, преобразуется в речь - форму удобную для передачи. И, смотрите, так как у звука есть ограничение как на скорость, так и на дальность передачи, то, например, жест, в какой-то ситуации, может быть выбран для передачи той же информации, но на большее расстояние. Но мы всё еще будем ограничены дальностью остроты нашего зрения и тогда человек начинает придумывать другие способы передачи и преобразования информации, например огонь или дым.

1.2 Чередующиеся сигналы

Индеец пингуетИндеец пингует

В примитивном виде кодирование чередующимися сигналами используется человечеством очень давно. В предыдущем разделе мы сказали про дым и огонь. Если между наблюдателем и источником огня ставить и убирать препятствие, то наблюдателю будет казаться, что он видит чередующиеся сигналы "включено/выключено". Меняя частоту таких включений мы можем выработать последовательность кодов, которая будет однозначно трактоваться принимающей стороной.

Наряду с сигнальными флажками на морских и речных судах, при появлении радио начали использовать код Морзе. И при всей кажущейся бинарности (представление кода двумя значениями), так как используются сигналы точка и тире, на самом деле это тернаный код, так как для разделения отдельных кодов-символов требуется пауза в передаче кода. То есть код Морзе кроме "точка-тире", что нам даёт букву "A" может звучать и так - "точка-пауза-тире" и тогда это уже две буквы "ET".

1.3 Контекст

Когда мы пользуемся компьютером, мы понимаем, что информация бывает разной - звук, видео, текст. Но в чем основные различия? И до того, как начать информацию кодировать, чтобы, например, передавать её по каналам связи, нужно понять, что из себя представляет информация в каждом конкретном случае, то есть обратить внимание на содержание. Звук - череда дискретных значений о звуковом сигнале, видео - череда кадров изображений, текст - череда символов текста. Если мы не будем учитывать контекст, а, например, будем использовать азбуку Морзе для передачи всех трёх видов информации, то если для текста такой способ может оказаться приемлемым, то для звука и видео время, затраченное на передачу например 1 секунды информации, может оказаться слишком долгим - час или даже пара недель.

2. Кодирование текста

От общего описания кодирования перейдём к практической части. Из условностей вы за константу примем то, что будем кодировать данные для персонального компьютера где за единицу информации приняты - бит и байт. Бит, как атом информации, а байт - как условный блок размером в 8 бит.

Текст в компьютере является частью 256 символов, для каждого отводится один байт и в качестве кода могут быть использованы значения от 0 до 255. Так как данные в ПК представлены в двоичной системе счисления, то один байт в значении ноль равен записи 00000000, а 255 как 11111111. Чтение такого представления числа происходит справа налево, то есть один будет записано как 00000001.

Итак, символов английского алфавита 26 для верхнего и 26 для нижнего регистра, 10 цифр. Так же есть знаки препинания и другие символы, но для экспериментов мы будем использовать только прописные буквы (верхний регистр) и пробел.

Тестовая фраза "ЕХАЛ ГРЕКА ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕЧКЕ РАК СУНУЛ ГРЕКА РУКУ В РЕКУ РАК ЗА РУКУ ГРЕКУ ЦАП".

2.1 Блочное кодирование

Информация в ПК уже представлена в виде блоков по 8 бит, но мы, зная контекст, попробуем представить её в виде блоков меньшего размера. Для этого нам нужно собрать информацию о представленных символах и, на будущее, сразу подсчитаем частоту использования каждого символа:

Символ

Количество

ПРОБЕЛ

18

Р

12

К

11

Е

11

У

9

А

8

Г

4

В

3

Ч

2

Л

2

И

2

З

2

Д

1

Х

1

С

1

Т

1

Ц

1

Н

1

П

1

Всего нами использовано 19 символов (включая пробел). Для хранения в памяти ПК будет затрачено 18+12+11+11+9+8+4+3+2+2+2+2+1+1+1+1+1+1+1=91 байт (91*8=728 бит).

Эти значения мы берём как константы и пробуем изменить подход к хранению блоков. Для этого мы замечаем, что из 256 кодов для символов мы используем только 19. Чтобы узнать - сколько нужно бит для хранения 19 значений мы должны посчитать LOG2(19)=4.25, так как дробное значение бита мы использовать не можем, то мы должны округлить до 5, что нам даёт максимально 32 разных значения (если бы мы захотели использовать 4 бита, то это дало бы лишь 16 значений и мы не смогли бы закодировать всю строку).

Нетрудно посчитать, что у нас получится 91*5=455 бит, то есть зная контекст и изменив способ хранения мы смогли уменьшить использование памяти ПК на 37.5%.

К сожалению такое представление информации не позволит его однозначно декодировать без хранения информации о символах и новых кодах, а добавление нового словаря увеличит размер данных. Поэтому подобные способы кодирования проявляют себя на бОльших объемах данных.

Кроме того, для хранения 19 значений мы использовали количество бит для 32 значений, это снижает эффективность кодирования.

2.2 Коды переменной длины

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

Символ

Количество

Переменный код, бит

ПРОБЕЛ

18

0

Р

12

1

К

11

00

Е

11

01

У

9

10

А

8

11

Г

4

000

В

3

001

Ч

2

010

Л

2

011

И

2

100

З

2

101

Д

1

110

Х

1

111

С

1

0000

Т

1

0001

Ц

1

0010

Н

1

0011

П

1

0100

Для подсчёта длины закодированного сообщения мы должны сложить все произведения количества символов на длины кодов в битах и тогда получим 179 бит.

Но такой способ, хоть и позволил прилично сэкономить память, но не будет работать, потому что невозможно его раскодировать. Мы не сможем определить в такой ситуации что означает код "111", это может быть "РРР", "РА", "АР" или "Х".

2.3 Префиксные блочные коды

Для решения проблемы предыдущего примера нам нужно использовать префиксные коды - это такой код, который при чтении можно однозначно раскодировать в нужный символ, так как он есть только у него. Помните ранее мы говорили про азбуку Морзе и там префиксом была пауза. Вот и сейчас нам нужно ввести в обращение какой-то код, который будет определять начало и/или конец конкретного значения кода.

Составим третью таблицу всё для той же строки:

Символ

Количество

Префиксный код с переменными блоками, бит

ПРОБЕЛ

18

0000

Р

12

0001

К

11

0010

Е

11

0011

У

9

0100

А

8

0101

Г

4

0110

В

3

0111

Ч

2

10001

Л

2

10010

И

2

10011

З

2

10100

Д

1

10101

Х

1

10110

С

1

10111

Т

1

11000

Ц

1

11001

Н

1

11010

П

1

11011

Особенность новых кодов в том, что первый бит мы используем для указания размера следующего за ним блока, где 0 - бок три бита, 1 - блок четыре бита. Нетрудно посчитать, что такой подход закодирует нашу строку в 379 бит. Ранее при блочном кодировании у нас получился результат в 455 бит.

Можно развить этот подход и префикс увеличить до 2 бит, что позволит нам создать 4 группы блоков:

Символ

Количество

Префиксный код с переменными блоками, бит

ПРОБЕЛ

18

000

Р

12

001

К

11

0100

Е

11

0101

У

9

0110

А

8

0111

Г

4

10000

В

3

10001

Ч

2

10010

Л

2

10011

И

2

10100

З

2

10101

Д

1

10110

Х

1

10111

С

1

11000

Т

1

11001

Ц

1

11010

Н

1

11011

П

1

11100

Где 00 - блок в 1 бит, 01 - 2 бита, 10 и 11 - 3 бита. Подсчитываем размер строки - 356 бит.

В итоге за три модификации одного способа мы регулярно уменьшаем размер строки, от 455 до 379, а затем до 356 бит.

2.4 Код Хаффмана

Один из популярнейших способов построения префиксных кодов. При соблюдении определенных условий позволяет получить оптимальный код для любых данных, хотя и допускает вольные модификации создания кодов.

Такой код гарантирует, что для каждого символа есть только одна уникальная последовательность значений битов. При этом частым символам будут назначены короткие коды.

Символ

Количество

Код

ПРОБЕЛ

18

00

Р

12

101

К

11

100

Е

11

011

У

9

010

А

8

1111

Г

4

11011

В

3

11001

Ч

2

111011

Л

2

111010

И

2

111001

З

2

111000

Д

1

1101011

Х

1

1101010

С

1

1101001

Т

1

1101000

Ц

1

1100011

Н

1

1100010

П

1

110000

Считаем результат - 328 бит.

Заметьте, хоть мы и стали использовать коды в 6 и 7 бит, но их слишком мало, чтобы повлиять на исход.

2.5.1 Строки и подстроки

До сих пор мы кодировали данные, рассматривая их как совокупность отдельных символов. Сейчас мы попробуем кодировать целыми словами.

Напомню нашу строку: "ЕХАЛ ГРЕКА ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕЧКЕ РАК СУНУЛ ГРЕКА РУКУ В РЕКУ РАК ЗА РУКУ ГРЕКУ ЦАП".

Составим таблицу повторов слов:

Слово

Количество

ПРОБЕЛ

18

ГРЕКА

3

В

2

РАК

2

РЕКУ

2

РУКУ

2

ВИДИТ

1

ГРЕКУ

1

ЕХАЛ

1

ЗА

1

РЕЧКЕ

1

СУНУЛ

1

ЦАП

1

ЧЕРЕЗ

1

Для кодирования нам нужно придумать концепцию, например - мы создаём словарь и каждому слову присваиваем индекс, пробелы игнорируем и не кодируем, но считаем, что каждое слово разделяется именно символом пробела.

Сначала формируем словарь:

Слово

Количество

Индекс

ГРЕКА

3

0

В

2

1

РАК

2

2

РЕКУ

2

3

РУКУ

2

4

ВИДИТ

1

5

ГРЕКУ

1

6

ЕХАЛ

1

7

ЗА

1

8

РЕЧКЕ

1

9

СУНУЛ

1

10

ЦАП

1

11

ЧЕРЕЗ

1

12

Таким образом наша строка кодируется в последовательность:

7, 0, 12, 3, 5, 0, 1, 9, 2, 10, 0, 4, 1, 3, 2, 8, 4, 6, 11

Это подготовительный этап, а вот то, как именно нам кодировать словарь и данные уже после подготовительного кодирования - процесс творческий. Мы пока останемся в рамках уже известных нам способов и начнём с блочного кодирования.

Индексы записываем в виде блоков по 4 бита (так можно представить индексы от 0 до 15), таких цепочек у нас будет две, одна для закодированного сообщения, а вторая для соответствия индексу и слову. Сами слова будем кодировать кодами Хаффмана, только нам еще придется задать разделитесь записей в словаре, можно, например, указывать длину слова блоком, самое длинное слово у нас в 5 символов, для этого хватит 3 бита, но так же мы можем использовать код пробела, который состоит из двух бит - так и поступим. В итоге мы получаем схему хранения словаря:

Индекс / биты

Слово / биты

Конец слова / биты

0 / 4

ГРЕКА / 18

ПРОБЕЛ / 2

1 / 4

В / 5

ПРОБЕЛ / 2

2 / 4

РАК / 10

ПРОБЕЛ / 2

3 / 4

РЕКУ / 12

ПРОБЕЛ / 2

4 / 4

РУКУ / 12

ПРОБЕЛ / 2

5 / 4

ВИДИТ / 31

ПРОБЕЛ / 2

6 / 4

ГРЕКУ / 17

ПРОБЕЛ / 2

7 / 4

ЕХАЛ / 20

ПРОБЕЛ / 2

8 / 4

ЗА / 10

ПРОБЕЛ / 2

9 / 4

РЕЧКЕ / 18

ПРОБЕЛ / 2

10 / 4

СУНУЛ / 26

ПРОБЕЛ / 2

11 / 4

ЦАП / 17

ПРОБЕЛ / 2

12 / 4

ЧЕРЕЗ / 21

ПРОБЕЛ / 2

7

0

12

3

5

0

1

9

2

10

0

4

1

3

2

8

4

6

11

и само сообщение по 4 бита на код.

Считаем всё вместе и получаем 371 бит. При этом само сообщение у нас было закодировано в 19*4=76 бит. Но нам всё еще требуется сохранять соответствие кода Хаффмана и символа, как и во всех предыдущих случаях.

Послесловие

Надеюсь статья позволит составить общее впечатление о кодировании и покажет, что это не только военный-шифровальщик или сложный алгоритм для математических гениев.

Периодически сталкиваюсь с тем, как студенты пытаются решить задачи кодирования и просто не могут абстрагироваться, подойти творчески к этому процессу. А ведь кодирование, это как причёска или модные штаны, которые таким образом показывают наш социальный код.

Подробнее..

Это непростое условное выполнение

02.01.2021 18:15:24 | Автор: admin
Некоторое время назад я рассказывал о программном комплексе для выявления скрытого параллелизма в произвольном алгоритме и технологиях его, параллелизма, рационального использовании (http://personeltest.ru/aways/habr.com/ru/post/530078/). Одним из компонентов этого комплекса является т.н. универсальный вычислитель, выполненный в соответствии с архитектурой Data-Flow (далее DF, потоковый вычислитель, описание здесь habr.com/ru/post/534722).
Подробнее..

Задача о m максимумах

02.01.2021 20:04:09 | Автор: admin

Старая-старая школьно-студенческая задача... Дан массив целых чисел. Требуется найти m его максимальных (или минимальных) элементов. Когда я задаю эту задачу учащимся, то почти в каждой группе находятся "умельцы", решающие ее с помощью сортировки. В самом деле, это ведь так просто: сортируем массив по убыванию (вручную или подходящей библиотечной функцией) и просто берем m первых элементов. Такое решение всегда казалось мне алгоритмическим варварством - найти m максимумов достаточно просто за один проход массива; сортировка существенно сложнее. И однажды я решил исследовать сей вопрос вычислительными экспериментами. Результаты этих экспериментов я и предлагаю вашему вниманию. Не исключено, что кому-то результаты помогут и в практической работе. Намекну - интуиция меня в целом не подвела.

Spoiler

Без сортировки задача может быть решена, например, так. Создаем рабочий массив длины m и заполняем его начальными значениями. В общем случае можно в качестве такого значения выбрать минимальное значение int/integer для соответствующей среды программирования. А если известна нижняя граница значений исходного массива, то можно взять любое число, меньшее этой границы.

Итак рабочий массив заполнен одинаковыми значениями. Теперь берем элемент за элементом исходного массива и вставляем его в нужное место рабочего массива. При этом длину рабочего массива сохраняем равной m (после вставки последний элемент пропадает). Если очередной элемент меньше последнего значения рабочего массива, то он просто пропускается. Этот процесс имеет вычислительную сложность O(nm). Тогда как сортировка в лучшем случае описывается асимптотикой O(n*og(n)). Асимптотики показывают, как ведет себя функция (в данном случае - время сортировки) при стремлении параметров к бесконечности. Можно сказать, что время описанного алгоритма при стремлении n к бесконечности задается формулой t1=k1*O(n), а время сортировки t2=k2*O(n*log(n)). Здесь k1 и k2 - некие константы, зависящие от процессора, языка программирования, операционной системы и других факторов.

Я построил три системы тестов (для Питона, Java и VBA). Все тесты устроены по сути одинаково: строились массивы возрастающих размеров, заполнялись случайными числами задаваемого диапазона, сортировались с фиксацией времени и прогонялись через описанный выше алгоритм тоже с фиксацией времени. Каждый тест повторялся 10 раз и время усреднялось. В Питоне и Java использовалась встроенная сортировка, в VBA - реализация QuickSort.

Питон

Ниже показан код питоновских тестов.

import timefrom random import randint    def max_n_1(arr,n):    return sorted(arr,reverse=True)[0:n]    def max_n_2(arr,n):    res=[-1 for _ in range(n)]    for x in arr:        if x > res[n-1]:            i=n-1            j=i-1            while(j>=0 and res[j]<x):                res[i]=res[j]                i=i-1                j=j-1            res[i]=x    return res      def start():    k=10    n=10000    print("k=",k)    while(n<=500000):        print("n=",n,end=' ')        t1=0.0        for i in range(10):            arr=[randint(1,2000) for _ in range(n)]            start_time = time.time()            z1=max_n_1(arr,k)            fin_time = time.time()            t1=t1+(fin_time-start_time)        print(t1/10.0,end=' ')            t2=0.0        for i in range(10):             arr=[randint(1,2000) for _ in range(n)]            start_time = time.time()            z2=max_n_2(arr,k)            fin_time = time.time()            t2=t2+(fin_time-start_time)        print(t2/10.0)            n+=10000        start()

Размеры массива менялись от 10 до 500 тыс. элементов с шагом 10 тыс. Было выполнено два прогона: определение пяти и десяти максимумов. Результат для 10 максимумов показан ниже.

Время здесь приведено в миллисекундах. Что видим? Сортировка отстает (на краю интервала - вдвое). Для пяти максимумов картина аналогична. И надо заметить, что хотя питоновская сортировка очень эффективна, простой алгоритм оказывается быстрее. Заметны резкие провалы в производительности (зубцы на графиках). Они, вероятно, объясняются влиянием внутренних процессов (типа сборки мусора). Это же замечание относится и к другим графикам.

Java

Код тестов выглядел так:

import java.util.*;class Start{   public static void main(String [] args)   {       Random random = new Random();    Scanner inp = new Scanner(System.in);    long startTime,endTime,tot1,tot2;    int i,a,b,n,m,x,ii,jj,u;    a=1;    b=3000; // диапазон случайных чисел [a,b]    m=10;        System.out.println(a+" "+b+" "+m);    for (n=50000; n<=5000000; n+=50000)    {    int arr[] = new int[n];      int ma[]  = new int[m];      tot1=0;      for (u=0; u<10; u++)      {              for (i=0; i<n; i++)      {     arr[i]=a+random.nextInt(b-a+1);      }        startTime = System.currentTimeMillis();        Arrays.sort(arr);        endTime = System.currentTimeMillis();        tot1=tot1+(endTime-startTime);      }      tot2=0;      for (u=0; u<10; u++)      {              for (i=0; i<n; i++)      {      arr[i]=a+random.nextInt(b-a+1);      }           startTime = System.currentTimeMillis();      for (i=0; i<m; i++) ma[i]=-999999;      for (i=0; i<n; i++)      {            x=arr[i];                    if (x >= ma[m-1])            {              ii=m-1;              jj=ii-1;              while(jj>=0 && ma[jj]<x)              {                ma[ii]=ma[jj];                ii--;                jj--;              }                ma[ii]=x;            }          }          endTime = System.currentTimeMillis();          tot2=tot2+(endTime-startTime);        }      System.out.println(n+" "+tot1+" "+tot2);   }  } }

Здесь размер массива тоже менялся от 10 тыс. до 500 тыс. элементов. Время - в миллисекундах. Результат оказался весьма похожим на питоновский (только сортировка Javа, увы, медленнее).

VBA

В этом языке нет универсальной встроенной сортировки (можно, правда, сортировать ячейки листа, но в этом случае будут велики накладные расходы, связанные с загрузкой и выгрузкой данных). Поэтому пришлось реализовать QuickSort вручную. Все это выглядит так:

Private Declare Function GetTickCount Lib "kernel32" () As Long'::: Собственно сортировкаSub QSort(A() As Long, Optional b As Long = 1, Optional e As Long = 0)    If b > e Then Exit Sub    i& = b    j& = e    w& = A((i& + j&) / 2)    Do While (True)      Do While (A(i&) < w&)         i& = i& + 1      Loop      Do While (A(j&) > w&)         j& = j& - 1      Loop      If i& <= j& Then         Tmp& = A(i&)         A(i&) = A(j&)         A(j&) = Tmp&         i& = i& + 1         j& = j& - 1      End If      If i& > j& Then Exit Do    Loop        If j& > b Then QSort A, b, j&    If i& < e Then QSort A, i&, eEnd Sub'::: Проверка успешности сортировки Function check(X() As Long) As Boolean     n& = UBound(X)     For i& = 1 To n& - 1         If X(i& + 1) < X(i&) Then            Debug.Print "Err! i=" + CStr(i&)            check = False            Exit Function         End If     Next i&     check = TrueEnd Function'::: Вставка в упорядоченный массивSub ins_in_arr(X As Long, A() As Long, n As Integer)    If X < A(n) Then Exit Sub    For i% = 1 To n        If X > A(i%) Then           For j% = n To i% + 1 Step -1               A(j%) = A(j% - 1)           Next j%           A(i%) = X           Exit Sub        End If    Next i%End Sub'::: Собственно тестSub test()Const sz = 500Dim X() As LongDim Ma(1 To sz) As Long    Randomize    ooo& = 1    For n& = 10000 To 500000 Step 10000                t1# = 0        For nc% = 1 To 10                                ReDim X(1 To n&) As Long            For i& = 1 To n&                X(i&) = Rnd() * 5000            Next i&            s1& = GetTickCount            For i& = 1 To sz                Ma(i&) = -2147483647            Next i&            For i& = 1 To n&                ins_in_arr X(i&), Ma, 10            Next i&            s2& = GetTickCount            t1# = t1# + s2& - s1&                Next nc%                        Cells(ooo&, 1).Value = n&        Cells(ooo&, 2).Value = t1# / 10                        t2# = 0                For nc% = 1 To 10                    ReDim X(1 To n&) As Long            For i& = 1 To n&                X(i&) = Rnd() * 5000            Next i&            s1& = GetTickCount            QSort X, 1, n&            s2& = GetTickCount            If Not check(X) Then               MsgBox "Ошибка при сортировке!"               Exit Sub            End If            t2# = t2# + s2& - s1&        Next nc%        Cells(ooo&, 3).Value = t2# / 10        ooo& = ooo& + 1            Next n&End Sub

На каждом витке цикла корректность сортировки проверяется. Время проверки, естественно, не включается в общий хронометраж. Набор исходных данных тот же - от 10 до 500 тыс. целых чисел. Получает, в общем, похожая картина:

Представляет некоторый интерес изучить зависимость времени от количества искомых максимумов (при фиксированном размере массива). Здесь, очевидно, сортировка будет тем выгоднее, чем больше максимумов требуется найти. А вставка в упорядоченный массив будет тем медленнее, чем массив больше.

Самым невыгодным случаем будет являться, как ни странно, входной массив, уже упорядоченный по возрастанию. В этом случае количество сравнений при вставке достигнет максимума и будет равно n*m. Массив, упорядоченный по убыванию, напротив, весьма выгоден. Число сравнений здесь будет ~ m+n.

Описанный в самом начале статьи алгоритм, можно ускорить, если вместо простого упорядоченного массива использовать древовидную или пирамидальную структуру. Именно так и реализована в Питоне в модуле heapq функция nsmallest.

Для небольших массивов (несколько тысяч элементов и менее) разница в подходах представляется несущественной. И если нужно быстро написать код, то сортировка - вполне приемлемое решение. Для больших массивов выгоднее от сортировки отказаться.

Вот и все, что я хотел рассказать об этой задаче. Спасибо, что дочитали до конца. С наступившим 2021-м годом!

Подробнее..

Нейротипология и нейромаркетинг будущего

04.01.2021 16:19:24 | Автор: admin

Недавно я пересматривал Назад в Будущее, культовую трилогию о том, как парень со своим гениальным дедом путешествует в будущее, прошлое и обратно. Интересно видеть, как почти 30 лет назад люди видели будущее- ховерборды вместо скейтов, летающие автомобили, романтика!

Сейчас становятся популярны идеи о том, что в будущем будет много киборгов, спасибо киберпанк 2077-идея о том, что не хватит наших мощностей для бега, зрения и конечно же мозга. Мы будем менять свои биологические глаза на какие-то кибер визоры с рентгеном, виденьем в темноте и инфракрасным зрением. Датчики на руках будут измерять температуру напитков и мы забудем о былой трудности, связанной с дорогостоящими медикаментами- имплантанты будут почти у всех и в прямом доступе.

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

Я хочу рассказать вам о том, что происходит уже сейчас и на что Точно лучше не закрывать свои глаза, отбрасывая это как бредни.

Вы знаете историю о том, как остров Манхеттен , исторический центр Нью-Йорка был куплен за 24 доллара у местных абориген капиталистами-американцами (привет дядя Сем). Это метафора моего сообщения. Но это пост не о том, какие американцы козлы или молодцы.

Иерархия- одно из свойств любой человеческой общины, даже наиболее демократичные коллективы людей все равно бессознательно распределяются по иерархии, так устроен наш мозг, а точнее лобная доля- мы ищем лидера или становимся им.

Хотелось бы привести пример про то, что самка выбирает наиболее лидирующую особь самца- но и это тоже несколько утопический бред. Например, некоторые самки кузнечиков выбирают не тех, кто победил в брачной битве самцов, а тех, кто наоборот- избегал конфликта. Запомните, не все самки выбирают победителей- это биология. Иногда побеждает не высовывающийся.

У наших абориген всего за несколько долларов выкупили площадь земли, на которой жили их предки, которая нынче оценивается в сотни миллиардов долларов.

Уже тогда эти ушлые парни успели на этом разжиться так, что озолотили не одно поколение своих потомков.

Кто-то скажет- "в этой истории победили нехорошие люди!", да, в глубине души я с вами согласен. Однако эта история иллюстрирует нам, что нынче происходит в мире.

Жители стран СНГ последние десятилетия наблюдают, как после краха плановой экономики на территорию наших стран начала приходить рыночная экономика.

Словно пулемет против рогатки- начали загибаться рынки, которые привыкли жить десятилетиями в стабильности.

Плановая экономика создавала некоторый покой, ты знаешь что получишь, если просто будешь работать. Раз в пять лет на собрании решалось, что страна будет покупать и продавать следующие пять лет.

И тут- бам! На нашу территорию пришли ОНИ! Те самые голодные до новых рынков ребята, те самые, чей дух заколен годами конкуренции и охоты, поджарые, быстрые и гибкие, знают наперед, чем купить клиента!

Где вместо блеклой обложки "газировка" написано ярким цветом "кола кола!" и слоган, теглайн, о котором не было слышно ровным счетом ничего. Привет, Пелевин.

Мы видим, как последние 20 лет происходит постепенный захват всех рынков, где мы не были достаточно компетентны.

К чему я это пишу- в зависимости от вашей картины мира вы можете ждать морали и справедливости, или думать, что все как должно быть. Вы можете думать, что у Бога все схвачено и "Русь поднимется с колен!", однако все всегда складывается по одному правилу- побеждает компетентнейший.

Иногда компетенция это сила+сноровка, иногда это знание закона и правил рынка. Иногда, как в случае с моим рассказом про крах плановой экономики- компетентность это уметь реагировать на потребительский спрос и управлять им.

Иногда компетентность- это 30 лет вести битву за самые живые умы в мире, выманивая их из других стран заманчивыми предложениями об идеальных условиях.

Теперь мы подходим к основной теме моего сообщения.

В мире сейчас происходят удивительные процессы- процесс отупления масс и избирательного и точечного выстреливания талантов. Процент реально умных детей невысок, но они совсем не такие, как мы привыкли думать про умного человека.

Менделеев сказал "знания без нравственности-меч в руках сумасшедшего".

Так вот, готовься, мир. Они идут. Школьники-фрилансеры, которые обеспечивают своих родителей за счет серверов по майнкрафту. Студенты универов, которые теряют интерес к учебе из-за быстрых денег в ютубе и стримах. Реперы которые пердят в микрофон на всю страну.

Корочка нужна была раньше, сейчас нужна компетентность.

Что же будет с обществом людей?

Я не буду кричать ИЛИТА правит миром! Нет. Это не мое дело , я уже сказал вам- я верю в силу компетентности.

Если ты купил у туземца остров за всего ничего, может ты знаешь что-то, чего не знает он?

В моем представлении миром будущего правят корпорации. Да не просто правят. Господствуют.

Самое ближайшее сравнение- матрица, где люди плавают в розовой жиже.

Вместо жижи- мастерское знание вашего мозга.

Мы видим как ютуб или соц сети угадывают ваши предпочтения. И это ТОЛЬКО начало.

Розовые комнатки- ваши аккаунты в Тик-ТокеРозовые комнатки- ваши аккаунты в Тик-Токе

Если вы что-то знаете о том, как устроен наш мозг, вы понимаете, что причина нашего подсаживания на какие-то либо продукты- это дофамин, гормон удовольствия.

Если пищевые корпорации зная это- добавляют в свои продукты сахар(кто в танке- смотрим одноименный фильм), то что же делают другие компании?

Нас же не могут кормить сахаром за лайки? Или за выложенный пост?

Или могут?

Немножко о том, как наш мозг вырабатывает дофамин. Дофамин вырабатывается в железе- это такая фабрика по производству гормонов. Сигнал в железу попадает от гипофиз- это как в мультфильме "головоломка"-распределительный центр сигналов по разным заводам. А перед попаданием в гипофиз ( который как в "головоломке") сигнал попадает в гипоталамус.

Такая вот цепочка получается- гипоталамус-гипофиз- железа.

И только после всего этого цикла включается наше осознание процессов. Этими экспериментами плотно занимался бенджамин Либет в прошлом столетии, шли споры про наличие или отсутствие свободной воли у человека. Мы не будем туда вникать, просто знайте- в процессе получения любой информации вы какое-то количество мгновений не управляете собой- потому что ваши нейросигналы бегают быстрее, чем вы их осознаете.

Мы постоянно осознаем себя "пост фактум", и я иногда задержка составляет не мгновения, а часы и даже месяца.

Так вот - о чем весь рассказ

Почему алгоритмы тик тока и инстаграмма выдают вам контент, на который вы уделили внимание? Они предполагают, что этот контент вырабатывает у вас дофамин.

И дают его больше, чтобы вы больше уделяли время их продукту.

Как вы думаете, что выдавал бы вам тик ток, если бы сразу знал от чего у вас вырабатывается дофамин? Он сразу бы делал это! Если бы это был белый шум или цветная радуга под звуки дельфинов.

Теперь представим, что гипоталамус это распределительная коробка, которая НЕ УНИКАЛЬНА для каждого человека, что есть эволюционно так сложилось, что наша личность - это продукт неокортекса, коры головного мозга. А гипоталамус- это нечто, данное нам с рождения. Это то, что остается практически неизменным с 9 месяцев и даже после обширного инсульта в 93.

То есть - есть некоторые типы гипоталамусов, которым характерны одинаковые реакции на одни и те же раздражители.

Назовем это типологией гипоталамусов.

Что есть типы людей, гипоталамусы которых одинаково реагируют на одни и те же информационные импульсы, а значит можно заранее предопределить, на что у них выработается дофамин.

Да, наверняка вы знаете множество псевдонаучных типологий, даже широко известных, как MBTI, соционика, гороскоп, дизайн человека.

Однако ни одна из них не встанет в один ряд с той, которая позволяет создавать наркоманию из своего контента.

И нас с вами это ждет.

Возможно уже сегодня, какой-нибудь Булат из Казани, никому неизвестный парень - случайно вывел такую типологию.

Возможно уже сегодня кто-то из вас захочет узнать подробнее про этого парня и предложит ему стать партнерами, разработать вместе нейросеть, чтобы по хвостам в соц сетях выстраивать гипотезу о том, к какому типу гипоталамуса относится тот или иной подписчик вашего бизнес аккаунта.

Возможно завтра это будет использоваться повсеместно. Наверное вам лучше уже сейчас, заранее узнать, как работает ваш гипоталамус на практике- просто чтобы защититься.

Если эта статья зайдет- буду писать еще, как это работает в деталях. Ваши комментарии и лайки подстегивают писать еще!

Подробнее..

Видео курсов Computer Science клуба

05.01.2021 18:18:32 | Автор: admin

Computer Science клуб это открытые лекции по компьютерным наукам в Санкт-Петербургском отделении Математического института РАН. Филиалы CS клуба действуют в Новосибирске и Казани. В связи с эпидемией все лекции осеннего семестра проходили онлайн и были доступны всем желающим вне зависимости от их местонахождения. Видеозаписи этих курсов выложены на сайт клуба и в канал на ютубе.

В осеннем семестре читались следующие курсы:

Кроме курсов, состоящих из нескольких лекций, в клубе проходят доклады Computer Science семинара - это открытые лекции от действующих учёных, популярно рассказывающие о какой-то теме. В этом семестре у нас были следующие доклады:

Также на базе Computer Science клуба проходили семинаре по курсу "Алгоритмы: продвинутые главы" от Константина Макарычева. Константин записал видеолекции на русском для курса, который он читает в Northwestern University в США. На семинарах были очень подробные и интересные обсуждения. Семинары вели Александр Шень (LIRMM, Монпелье) и Илья Разенштейн (Microsoft Research). В качестве приглашённого лектора выступал Григорий Ярославцев (Indiana University).

Более того, на сайте вы можете найти материалы и видеозаписи большинства курсов, которые когда-либо читались в клубе. Список курсов.

Следующий семестр также будет проходить в режиме онлайн. Подписывайтесь на наши новости в соцсетях, чтобы ничего не пропустить. Ссылки вы найдёте в "подвале" на сайте клуба.

Подробнее..

Перевод В поисках искусственного здравого смысла

05.01.2021 20:17:13 | Автор: admin
19 июля 2020 года была опубликована запись в блоге под названием Чувствуете себя непродуктивным? Может, стоит перестать задумываться. В этой статье о самосовершенствовании в 1000 слов объясняется, что чрезмерное обдумывание враг творчества, и даётся совет быть внимательнее:

Чтобы что-то сделать, возможно, нам нужно меньше думать. Это кажется нелогичным, но я считаю, что иногда наши мысли могут мешать творческому процессу. Иногда мы можем работать лучше, когда отключаемся от внешнего мира, сосредотачиваясь на том, что перед нами.

Пост был написан GPT-3, огромной нейронной сетью Open AI с 175 миллиардами параметров, обученной почти полутриллиону слов. Студент Калифорнийского университета в Беркли Лиам Порр просто написал заголовок и позволил алгоритму написать текст. Забавный эксперимент, чтобы посмотреть, сможет ли ИИ обмануть людей. Действительно, GPT-3 ударил по нервам: этот пост достиг первого места на Hacker News.

Итак, с сегодняшним ИИ есть парадокс. Хотя некоторые из работ GPT-3, возможно, удовлетворяют критерию теста Тьюринга, убеждая людей в том, что с ними общается человек, но он явно терпит неудачу на простейших заданиях. Исследователь искусственного интеллекта Гэри Маркус попросил GPT-2, предшественника GPT-3, закончить такое предложение:

Что происходит, когда вы складываете растопку и поленья в камин, а затем бросаете несколько спичек? Обычно начнётся

Огонь вот что немедленно закричит любой ребёнок. Но ответ GPT-2: Ick

Эксперимент не удался. Дело закрыто?





Тёмная материя естественного языка


Человеческое общение это процесс оптимизации. Оратор сводит к минимуму количество высказываний, необходимых для передачи своей мысли слушателю. Всё, что упускается из виду, у нас называется здравым смыслом. И, поскольку слушателю доступен тот же здравый смысл, что и говорящему, он может придать высказыванию значение.

Таким образом, по определению здравый смысл никогда не записывается. Как указал учёный NLU Валид Саба, мы не говорим:

Чарльз, который является живым молодым взрослым человеком и учился в аспирантуре, бросил аспирантуру, чтобы присоединиться к компании разработчику программного обеспечения, которой был нужен новый сотрудник.

Мы говорим проще:

Чарльз бросил аспирантуру, чтобы работать в компании разработчике программного обеспечения

и предполагаем, что наш собеседник уже знает:

  • Вы должны быть живы, чтобы учиться в школе или присоединиться к компании.
  • Вы должны быть в аспирантуре, чтобы бросить её.
  • У компании должна быть открытая вакансия, чтобы закрыть её.

И так далее. Все человеческие высказывания подобны этому, они наполнены невидимыми правилами здравого смысла, о которых мы никогда прямо не заявляем. Таким образом, здравый смысл можно сравнить с тёмной материей в физике: она невидима, но составляет основную массу.
Итак, как же тогда можно научить машины искусственному здравому смыслу? Как они могут понять, что мы бросаем спичку, потому что хотим разжечь огонь?

Искусственный здравый смысл: метод грубой силы


Есть причина полагать, что мы можем использовать метод грубой силы в искусственном здравом смысле, и эта причина наклон кривой на следующем графике:


Производительность GPT-3 на SuperGLUE

Этот график из работы о GPT-3 Языковые модели FSL показывает производительность модели на SuperGLUE в зависимости от количества параметров модели, причём полная модель GPT-3 это крайняя точка справа. SuperGLUE содержит довольно сложные семантические задачи, такие как схемы Винограда:

Трофей не помещается в коричневый чемодан, потому что он слишком мал.
Что слишком мало?
Ответ: чемодан.

Примечательно, что при 175 миллиардах параметров кривая всё ещё растёт: точка максимума ещё не достигнута. Итак, одна из гипотез состоит в том, что мы должны иметь возможность строить еще более крупные модели с триллионами или более параметров и в конечном счёте появится искусственный здравый смысл. Назовём это предположение гипотезой грубой силы.

Однако это всего лишь гипотеза, и мы не знаем, правдивая она на самом деле или нет. Контраргумент здесь: машина просто не может учиться на том, что не прописывается явно.

Бесконечные правила


Если мы хотим научить машины здравому смыслу, почему бы просто не записать его весь в виде правил, а затем передать эти правила машине? Это именно то, что Дуглас Ленат намеревался сделать в 1980-х годах. Он нанял учёных-компьютерщиков и философов для создания базы знаний здравого смысла, известной сегодня как Cyc. На сегодня Cyc содержит 15 миллионов правил, таких как:

1. У летучей мыши есть крылья.
2. Поскольку у неё есть крылья, летучая мышь может летать.
3. Поскольку летучая мышь может летать, она может путешествовать с места на место.

Проблема с жёстко запрограммированной системой, такой как Cyc, заключается в том, что правила бесконечны: для каждого правила есть исключение, исключение из исключения и так далее. Поскольку у летучей мыши есть крылья, она может летать, если только она не сломала крыло. Из-за этого бесконечного цикла набор правил становится всё более сложным, из-за чего людям всё труднее поддерживать память машины, а машинам сохранять её.

Поэтому неудивительно, что, несмотря на десятилетия усилий, Cyc по-прежнему не работает и может никогда не заработать. Профессор Вашингтонского университета Педро Домингос называет Cyc крупнейшим провалом в истории искусственного интеллекта. Орен Эциони, генеральный директор Института искусственного интеллекта Аллена, ещё один критик, заметил в интервью Wired: Если бы это работало, люди бы знали, что это работает.

Подведём итоги. Для настоящего ИИ нам нужно создать искусственный здравый смысл. Но есть убедительные аргументы против гипотезы грубой силы. С другой стороны, есть веские аргументы против жёстко запрограммированных правил. Что, если бы мы объединили лучшее в этих подходах?

Гибридный подход


Знакомьтесь с COMET, моделью на основе трансформера, разработанной профессором Вашингтонского университета Йеджин Чой и её сотрудниками. Суть модели состоит в том, что она обучается на семенной базе знаний здравого смысла, а затем расширяет эту базу, генерируя новые правила на основе каждого нового высказывания. Таким образом, COMET это способ загрузить искусственный здравый смысл. В своей статье исследователи пишут, что COMET часто дает новые соответствующие здравому смыслу знания, которые специалисты по оценке считают корректными.
В качестве теста я набрал текст: Гэри складывает растопку и поленья в камин, а затем бросает несколько спичек в COMET API, а вот часть графа вывода:


Часть выведенного COMET графа здравого смысла

COMET правильно делает вывод, что Гэри *хотел* разжечь огонь. Система также указывает, что в результате Гэри становится тепло. На мой взгляд, это звучит намного лучше, чем ответ GPT-3 на тот же запрос.

Итак, является ли COMET решением проблемы искусственного здравого смысла? Это ещё предстоит узнать. Если, скажем, COMET добьётся производительности человеческого уровня на SuperGLUE, это, несомненно, станет прорывом в области.

С другой стороны, критики могут возразить, что здравый смысл нельзя измерить с помощью искусственных эталонных наборов данных. Есть риск того, что после создания такого набора эталонных данных исследователи в какой-то момент начнут переобучать модель, что сделает результат эталонного теста бессмысленным. Одно из направлений мысли протестировать ИИ с помощью тех же тестов интеллекта, что и людей. Например, исследователи Стеллан Олссон и сотрудники из Университета Иллинойса в Чикаго предлагают проверить искусственный здравый смысл с помощью тестов IQ маленьких детей.

Не позволяйте сегодняшнему ИИ обмануть вас


Наконец, не позволяйте сегодняшнему ИИ обмануть вас. Оглядываясь на статью GPT-3, я понимаю, что многие из её высказываний поверхностные и обобщённые, как, например, в печенье с предсказаниями:

Важно сохранять непредвзятость и пробовать новое.

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

image



Подробнее..

Нейросети в большом городе. Разбираемся, как они помогают идентифицировать людей, и запускаем собственную нейросеть

08.01.2021 16:23:02 | Автор: admin
Алгоритмы по детекции лиц плотно вошли в нашу жизнь, хотя и не все это замечают. Началось всё в 2015 году со сферы развлечений. Стартап Looksery, занимающийся разработкой AR-фильтров, был куплен Snapchat. Приложение распознавало лицо человека на фотографии и накладывало на него весёлые рожицы. Чуть позже, в начале 2016 года, Facebook купил белорусский стартап MSQRD и запустил маски в Facebook Stories. Но это можно считать только обкаткой таких технологий.

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




Прежде чем продолжить, чтобы не запутаться, дадим определения некоторым терминам.

Детекция обнаружение какого-либо класса объектов, например лица.

Идентификация обнаружение определённого объекта, например лица Васи Пупкина.

Дальнейшее развитие нейронных сетей подняло точность идентификации, достаточную для решения таких задач, как защита и безопасность. В 2017 году Apple представила FaceID сканер, позволяющий разблокировать телефон по лицу владельца. Появился новый способ оплаты покупок по биометрии. Летом 2020 года сеть московских кафе Prime начала тестировать систему оплаты по лицу клиента. Вместо использования пропусков для турникетов начинают идентифицировать человека через видеокамеру.

Обращая внимание на количество камер, установленных в крупных городах, можно осознать, что тема важна и актуальна. Правительства крупнейших стран заинтересованы в автоматизации и вкладывают огромные средства в реализацию подобных проектов.

Распознавание с помощью алгоритмов


В 2001 году Пол Виола и Майкл Джонс предложили метод детекции объектов, который широко использовался для определения лиц. В 2005 году Навнит Далал и Билл Триггс показали свои гистограммы направленных градиентов (Histogram of Oriented Gradients, HOG), с помощью которых также можно было детектировать лица.

К сожалению, качество данных подходов оставляло желать лучшего. Был высок уровень срабатывания ошибок первого и второго рода.

Ошибка первого рода отказ от правильной гипотезы, когда лицо в кадре не детектируется.
Ошибка второго рода принятие неправильной гипотезы, когда детектируется то, что к лицу не относится.

Алгоритмы плохо работали при слабом освещении, наклоне или повороте головы. Разницы по точности между этими двумя методами особо не наблюдалось.

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

  • Плохой уровень освещённости (света от монитора в тёмной комнате достаточно для распознавания);
  • Голова наклонена или слегка повёрнута в сторону;
  • Лицо не полностью попадает в кадр или частично прикрыто ладонью;
  • Борода, очки не проблема.

Так что те, кто до сих пор использует решения на основе старых алгоритмов, бросайте это дело! Давно существуют решения, требующие такой же вычислительной мощности, но при этом дающие точность, близкую к 100 %.

Распознавание лиц в городах


По состоянию на 2019 год, количество камер с системой распознавания лиц, установленных в крупных городах:

  • Пекин 470 тыс.;
  • Великобритания 420 000 тыс.;
  • Вашингтон 30 000 тыс.;

В Москве на данный момент установлено около 193 тыс. HD-камер. Расположение камер можно посмотреть на сайте data.mos.ru.

Также система распознавания лиц запущена в московском метро. Камеры установлены в вагонах и у турникетов. В 2021 году будет добавлена функция оплаты проезда через идентификацию лица. При прохождении человека через турникет оплата будет списываться автоматически. Для этого всего лишь нужно связать банковскую карту с биометрическими данными.

Цели развёртывания систем распознавания


Теоретически эти меры должны будут сократить преступность, распознавая нарушителей за доли секунды. Система слежения позволит выявить самые опасные места в городе и вычислить нелегальных мигрантов. По данным МВД, за два года тестовой работы системы распознавания лиц нашли около 100 человек, находящихся в федеральном розыске, после чего в конце 2019 года к системе решили подключить все городские камеры.

Эффективность новой системы слежения заключается в том, что если раньше все материалы сохранялись в отдельный видеоархив и сотрудниками полиции необходимо было прогонять каждое видео через специальную программу, то теперь распознавание лиц происходит одновременно с нескольких тысяч камер в режиме реального времени.

К сожалению, ни одна система не идеальна иногда происходит утечка данных. В сети за скромную плату такая информация продаётся всем желающим. Чаще всего такие данные покупают частные детективы или коллекторы.

Как обрабатываются такие данные


Ряд компаний на протяжении более 40 лет активно разрабатывает системы распознавания человеческих лиц. В их числе даже знаменитый производитель оружия Smith & Wesson со своей системой ASID Automated Suspect Identification System. А полиция Лондона сейчас тестирует похожую систему в сотрудничестве с японской компанией NEC. Но лидером в данной области можно смело назвать российскую компанию NtechLab. В 2015 году алгоритм распознавания лиц от NtechLab был признан лучшим на организованном Вашингтонским университетом международном конкурсе The MegaFace Benchmark. В мае 2016 NtechLab в числе трёх российских компаний была допущена к официальному тестированию технологий биометрии, проводимому NIST. Сам факт допуска к испытаниям дал компании право участвовать в гостендерах США и ряда других стран.


Широкой аудитории алгоритм был представлен в виде сервиса FindFace, который искал людей во Вконтакте по фотографии. После своего запуска сервис наделал много шума в соцсетях, а также спровоцировал несколько скандалов с деаноном. По всей видимости, сервис был маркетинговым приёмом, призванным показать возможности платформы потенциальным приобретателям технологии. Вскоре после этого разработчики закрыли сервис, и компания начала оказывать услуги государству и различным отраслям бизнеса. В частности стало известно, что мэрия Москвы заплатила NtechLab не менее $3,2 млн за использование её технологии распознавания лиц в городской системе видеонаблюдения.

Собственная система слежения в домашних условиях на основе нейронных сетей


MTCNN нейронная сеть для детекции лиц


MTCNN это каскад свёрточных нейронных сетей. В модели используются 3 сети: P-Net, R-Net и O-net. Каждая последующая нейронная сеть увеличивает точность предсказания.



Первая P-Net на выходе выдаёт координаты ограничивающих прямоугольников предполагаемых лиц. Далее R-net отсекает менее вероятные области лиц и добавляет уровень достоверности к тем, которые остались. В третьей сети мы снова избавляемся от прямоугольников с более низким уровнем достоверности и добавляем координаты 5 лицевых ориентиров.


Результат работы mtcnn

Для тех, кто хочет поэкспериментировать, нейронная сеть упакована в Python-библиотеку с одноимённым названием MTCNN. Для запуска достаточно создать объект MTCNN и вызвать метод detect_face.

Детектор возвращает словарь с тремя ключами: координаты прямоугольника, ключевые точки и уровень достоверности. Пример кода с гитхаба проекта ниже:

import cv2from mtcnn import MTCNN detector = MTCNN()image = cv2.cvtColor(cv2.imread("ivan.jpg"), cv2.COLOR_BGR2RGB)result = detector.detect_faces(image)bounding_box = result[0]['box']keypoints = result[0]['keypoints']cv2.rectangle(image,          (bounding_box[0], bounding_box[1]),          (bounding_box[0]+bounding_box[2], bounding_box[1] + bounding_box[3]),          (0,155,255), 2)cv2.circle(image,(keypoints['left_eye']), 2, (0,155,255), 2)cv2.circle(image,(keypoints['right_eye']), 2, (0,155,255), 2)cv2.circle(image,(keypoints['nose']), 2, (0,155,255), 2)cv2.circle(image,(keypoints['mouth_left']), 2, (0,155,255), 2)cv2.circle(image,(keypoints['mouth_right']), 2, (0,155,255), 2)cv2.imwrite("ivan_drawn.jpg", cv2.cvtColor(image, cv2.COLOR_RGB2BGR))print(result)

У меня были проблемы с зависимостями пакетов. Если у вас появляются ошибки, скопируйте в файл requirements.txt следующие пакеты:

opencv-python==4.2tensorflow==1.12.3keras==2.2.4numpy == 1.16protobuf==3.6.0mtcnn

Если tensorflow не устанавливается тогда обновите setuptools командой:

pip install setuptools --upgrade --ignore-installed

FaceNet


Сиамская нейронная сеть, идентифицирующая лица. Слово сиамская означает, что она состоит из двух идентичных нейронных сетей с одинаковыми весами. Во время обучения FaceNet извлекает черты лица и преобразует их в евклидово пространство, где расстояния между точками вектора напрямую соответствуют мере сходства лиц. Сравнивая два изображения с двух сетей во время обучения, коэффициенты меняются так, чтобы увеличить евклидово расстояние, если изображены разные люди, и минимизировать его, когда изображён один и тот же человек.

После обучения нейронная сеть способна производить идентификацию, сверяя текущее лицо с лицами, которые хранятся в базе данных.

Для того чтобы провести идентификацию, сначала нужно провести детекцию, воспользовавшись любым из методов по определению лиц. После получения изображения лица, в котором глаза и губы находятся примерно на одном и том же месте изображения, мы передаём картинку в FaceNet, предварительно преобразовав к разрешению 96x96 пикселей.

Далее изображение преобразуется в евклидово пространство и сравнивается с данными из базы лиц. Если расстояние меньше заданного порогового значения, сеть просигнализирует о совпадении.


Принцип работы faceNet

Тот, кто хочет протестировать модель, может заглянуть на данный репозиторий. Веса для предобученной нейронной сети можно скачать с google-диска.

Это стандартные реализации алгоритмов обнаружения. На уровне систем безопасности используется более тонкая и сложная настройка. Разумеется, это коммерческая тайна.

Слабые места подобных систем


Параллельно с развитием систем слежения разрабатываются методы деанонимизации. Для защиты от слежки используют очки со светодиодами, специальные пиктограммы, не характерные для человеческого лица, или обыкновенные маски.


На точность распознавания в условиях городской среды влияют такие факторы, как погодные условия, место размещения камеры, направление объектива, уровень освещённости, частичное закрывание лица шарфом или медицинской маской.


Известны случаи, когда алгоритм ошибается и принимает добропорядочного человека за нарушителя, который находится в розыске. Полиция задерживает человека до тех пор, пока не будет уверена в том, что алгоритм ошибся.

Перспективы развития систем видеонаблюдения


В настоящее время разрабатываются системы, определяющие конкретные позы человека, например для детекции драки. Учатся идентифицировать людей по походке (она у каждого человека индивидуальна) и создают биобанк для хранения таких биометрических данных.

В ближайшем будущем, системы видеонаблюдения получат значительномое расширение сферы применения и это не обязательно безопасность. Например одно из наиболее перспективных направлений это розничная торговля.

image



Подробнее..

Идеальное хэширование

11.01.2021 16:10:01 | Автор: admin

Какова сложность поиска элемента по ключу?

Это зависит от того, какую структуру данных использовать.

В односвязном списке - линейная сложность.

В отсортированном массиве или в двоичном дереве поиска - логарифмическая сложность.

В хэш-таблице - сложность константная. Но это в лучшем случае. А в худшем стремится к линейной

А можно ли создать идеальную хэш-таблицу, чтобы сложность поиска элемента даже в худшем случае оставалась константной?

В общем случае - нет. Но если список всех ключей установлен заранее и не изменяется, а хэш-коды у всех ключей различны, то можно построить идеальную хэш-таблицу без коллизий, где поиск любого элемента происходит за несколько тривиальных операций, причём, количество этих операций не зависит от размера хэш-таблицы.

Идеально! Поговорим о том, как это сделать.
Кстати, на курсе "Алгоритмы и структуры данных" на платформе OTUS у нас есть отдельный модуль, посвящённый вопросам создания хэш-таблиц.


Представьте англо-русский словарь. Английские слова являются ключами, а перевод - значениями. Время поиска любого слова в таком словаре может происходит за константное время, как если бы мы обращались к элементу массива по индексу!

Взял, такой, хэш-код слова dog, вычислил хэш-функцию, поколдовал ещё немножко, и, вуаля, в руках уже собака на поводке указателе!

Как такое возможно?

Предположим, в словаре 10.000 слов-ключей. Для их хранения мы открываем хэш-таблицу на 10.000 элементов. Возможно ли создать волшебную хэш-функцию-биекцию, которая каждый ключ отображала бы на индекс массива, где он должен лежать? Наверное, это возможно, если создать небольшую нейронную сеть и обучить её.

Если же ограничиваться простейшей хэш-функцией вида (A * k + B) % N, с возможностью подбора лишь двух коэффициентов A и В, то создать волшебную биекцию вряд ли удастся - коллизий не избежать. В этой формуле k - уникальный хэшкод (ulong) уникального ключа, N - количество ключей.

Идея идеального хэширования заключается в двухэтапном хэшировании.

На первом этапе находим квартиру, а на втором этапе - комнату, где располагается искомое значение.

Это напоминает метод разрешения коллизий методом цепочек. Но если в методе цепочек в каждой квартире расположен односвязный список комнат, то в идеальном хэшировании мы в каждой квартире создадим отдельную хэш-таблицу с матрицей комнат. Это будут квадрокомнатные квартиры, но обо всём по порядку.

Первый этап

Минимизация количества комнат в квартирах.

Поскольку список всех ключей известен заранее, то можно подобрать такие коэффициенты, чтобы максимальное количество комнат (коллизий) в одной квартире было минимальным. Достаточно несколько десятков попыток, чтобы минимизировать максимальное количество коллизий.

Например, за 100 итераций подбора коэффициентов для словаря из 10.000 ключей максимальное количество коллизий для одного элемента не превышает 10.

Итак, на первом этапе мы подбираем глобальные коэффициенты А и В для хэш-функции вида (A * k + B) % N. Эта функция вычисляет номер квартиры, в которой находится значение для заданного ключа. При этом минимизируется максимальное количество комнат (коллизий) в каждой квартире.

Второй этап

Для размещения K элементов в одной квартире мы резервируем K комнат. Такая квадрокомнатная квартира позволит без особого труда подобрать коэффициенты A и B для размещения K элементов без единой коллизии, потому что значения всех ключей известно заранее (напомним, что хэш-коды всех ключей различны). Коэффициенты подбираются для каждой квартиры отдельно и хранятся в каждом элементе первой хэш-таблицы, вместе с количеством комнат.

Вот и всё!

Для поиска любого элемента в идеальной хэш-таблице необходимо выполнить следующие действия:

  1. Найти номер квартиры i по хэш-коду ключа k: (A * k + B) % N.

  2. Взять коэффициенты для вычисления номера комнаты: Ai, Bi, K.

  3. Найти номер комнаты по формуле: (Ai * k + Bi) % K

  4. Вернуть значение из найденной комнаты.

В любом случае (как в лучшем, так и худшем) на поиск элемента потребуется константное количество действий, которое не зависит от общего количества элементов.

Расход памяти

Может показаться, что наличие квадрокомнатных квартир потребует слишком много памяти для хранения нашей идеальной хэш-таблицы. Продемонстрируем, что затраты по памяти не превышают линейную сложность (троекратный расход).

Возьмём, для примера, хэш-таблицу из N = 10 элементов. В каждом элементе может быть от 0 до 10 коллизий. Вычислим вероятность коллизий, умножим на затраты по памяти и найдём математическое ожидание объёма памяти для размещения одного элемента.

Итого: для хранения квартир нужно N ячеек памяти, для хранения комнат - примерно 1.9 * N. Суммарный расход памяти: 2.9 * N = О(N) - линейный.

Заключение

Если вы уже закончили работу над крупным проектом, все настройки которого хранятся в хэш-таблице, то вы можете выписать список всех-всех-всех параметров (ключей) и создать идеальную хэш-таблицу для их хранения, чтобы увеличить скорость доступа к этим элементам.


А теперь небольшой бонус. 15 января я проведу Demo Day курса "Алгоритмы и структуры данных" на платформе OTUS, приглашаю всех желающих узнать подробно о курсе и задать вопросы лично.

Также хочу посоветовать еще несколько статей из своего блога, которые уже успели получить хороший отклик у читателей:

Подробнее..

Алгоритм обучения нейронных сетей с помощью нового вида чисел

13.01.2021 14:06:06 | Автор: admin

Приветствую читатель. Когда я был ребёнком и учился в школе, моим любимым предметом была математика, любимым предметом она была из-за того, что я очень люблю решать задачи, в какой-то момент своей жизни я начал составлять сам для себя заведомо нерешаемые задачи и пытался их решить, по полной напрягая свой разум в продумывании подхода для решения нерешаемой задачи, иногда оказывалось, что нерешаемая задача только казалась таковой из-за упущения некоторых неочевидных моментов. Любовь к решению задач сильно повлияла на меня, из-за чего я у себя в голове постоянно решаю какие-либо задачи, не только математические, но и из других сфер. За жизнь у меня накопилось множество идей (решений), от 3d принтера печатающего сталью до способа решения проблемы утилизации радиоактивных отходов атомных электростанций. Наверняка многие идеи на самом деле не реализуемы, по тем или иным причинам, а некоторые наверняка были придуманы до меня, а я просто о них не знал (так уже бывало). В прошлой моей статье я упомянул (сам не знаю зачем) о том, что я придумал новый вид чисел с помощью которых можно обучать нейронные сети. Я хотел открыть сервис по обучению нейронных сетей с помощью этих чисел, но с учётом пандемии и моего плохого состояния здоровья, я подумал, что вдруг я реально первый кто додумался до этих чисел и будет крайне плохо если я умру и знания о этих числах уйдут со мной. Поэтому я и решил написать эту статью, в которой расскажу подробно о этих числах и как их использовать для обучения нейронных сетей. Сразу скажу, что я не прорабатывал все необходимые формулы для работы с такими числами, так как был занят своим языком программирования, это лишь идея, а не готовая реализация.

Для того, что бы полностью понять о чём пойдёт речь в статье, нужно иметь знание о строении простых feedforward нейронных сетей.

Предположим нужно обучить feedforward нейронную сеть имея некую обучающую выборку, в которой есть примеры того, что подаётся на вход нейронной сети и что ожидается получить на выходе. Для такого случая можно написать функцию, назовём её fitness (как в генетическом алгоритме), на вход такой функции даётся нейронная сеть и обучающая выборка, а функция возвращает число от 0 до 1, число соответствует тому, на сколько данная нейронная сеть обучена данной выборкой, где 0 - максимально не обучена, 1 - идеально обучена. Используя такую fitness функцию, нейронную сеть можно представить как математическую функцию у которой аргументы - это веса нейронной сети, а результатом является результат fitness функции применяемой к нейронной сети с данными весами и обучающей выборкой. Я начал размышлять "как найти максимум такой функции?". В свой голове я представил 3х мерный график функции с 2 аргументами и подумал, что если добавить условие что каждый вес будет ограничен каким либо конечным диапазоном возможных значений, то можно разделить этот график на две части, в одной части графика первый аргумент имеет одни значения из своего возможного диапазона, а вторая часть графика имеет все оставшиеся значения аргумента, затем проанализировать в какой части максимум больше, взять эту часть и делить её таким же образом, но уже опираясь на другой аргумент, после чего полученную в результате второго деления часть, снова нужно разделить на две части опираясь на первый аргумент. Такое деление на части нужно производить до тех пор, пока значения результата функции на полученном от делении участке, будут иметь слишком большие колебания. Любые аргументы из полученной части графика и являются подходящими весами. Для лучшего понимания, поясню вышесказанное на примере.

График функции y = sin xГрафик функции y = sin x

Предположим есть функция y(x) = sin x, x принадлежит множеству [-4, 4], нужно найти максимум, или значение очень близкое к максимуму, данной функции на данном участке. Разделим график на 2 части, в одной части x принадлежит множеству [-4, 0], во второй части x принадлежит множеству [0, 4], как видно на графике максимум находится во второй части, затем делим вторую часть на две части [0, 2] и [2, 4]. В какой-то момент в результате деления получится часть, в которых минимальное и максимальное значение функции очень близко к 1, например [pi * 999999 / 2000000, pi / 2], из этой части любой x будет приемлемым решением. Теперь о том как вышесказанное реализовать на практике. Однажды я сидел и смотрел в интернете научно-популярное видео, касалось оно космоса и в нём вскользь мелькнула информация о суперпозиции, в этот момент я подумал о числах которые не занимают определённую позицию, а находятся во многих местах одновременно. Например представить множество [0, 1], не как множество, а как число одновременно имеющее значение всех чисел из множества. Назовём такие числа "суперпозиционными". Результатом применения любой унарной операции к суперпозиционному числу, это суперпозиционное число, которое охватывает множество чисел, которые могут быть получены в результате применения унарной операции к любому числу из множества, которое охватывает исходное суперпозиционное число. Например: sin([-pi, pi]) = [-1, 1]. Результатом применения любой бинарной операции над суперпозиционными числами, это суперпозиционное число, которое охватывает множество чисел, которые могут быть получены в результате применения бинарной операции к двум любым числам из множеств, которые охватывают исходные суперпозиционные числа. Например: [-3, 6] - [-12, 7] = [-10, 18]. Вещественные числа так же можно представить в виде суперпозиционных как множество с одним числом, например [3, 3]. Что дают такие числа? Если есть некая функция с одним или несколькими неизвестными аргументами, но при этом значения этих аргументов ограничены каким либо конечным множество возможных значений, то подставив в качестве таких аргументов суперпозиционные числа, охватывающие собой множества возможных аргументов, можно узнать диапазон возможных значений функции. Вот как я придумал обучать простые feedforward нейронные сети:

  • создать нейронную сеть в которой все веса - суперпозиционные числа с множеством, которое ограниченно минимальным и максимальным значением веса

  • создать fintess функцию которая принимает указную нейронную сеть и обучающую выборку

  • уменьшить размер множества из суперпозиционного числа в одном весе в 2 раза, охватив либо половину множества с меньшими числами, либо с большими числами. Выбирается та половина, заменив на которую fitness функция даст большее значение. Если для обоих половин fitness функция выдаёт одинаковое значение, то выбирается случайная половина

  • выше указанные действия повторяются для каждого веса

  • выше указанные действия повторяются до тех пор, пока границы всех множеств суперпозиционных чисел в весах отличаются на определённое значение

  • заменить каждый вес на любое вещественное число из множества охватываемого суперпозиционным числом из соответствующего веса

Выше указанный алгоритм уже сейчас можно реализовать и опробовать на сколько он эффективен. Мне очень хотелось бы это сделать, но категорически не хватает времени. После того как я придумал данный алгоритм, я периодически о нём думал и понял, что у него есть очень весомая проблема - когда fitness функция будет производить анализ того на сколько нейронная сеть подходит для выборки, естественно что в процессе анализа, функция в том числе будет смотреть на сколько нейронная сеть подходит для каждого отдельного примера и может так получиться, что для каждого отдельного примера лучшие веса находятся в одном диапазоне значений, но самые подходящие веса для всей выборки в целом - в другом диапазоне. Для решения этой проблемы, мною был придуман ещё один вид чисел, а также новый алгоритм обучения который, как мне кажется, должен значительно увеличить вероятность выбора правильного множества чисел.

Хотя как идея, суперпозиционные числа олицетворяют собой числа которые находятся одновременно в нескольких местах, по факту вышеуказанные алгоритм использует такие числа как олицетворение вещественного числа находящегося в неком промежутке, а в результате получаем промежуток в котором может быть результат действий производимого над числами. Одна из проблем такого подхода в том, что совершенно не учитываются вероятность получения каких либо значений в диапазоне чисел. Например: если есть некое число принадлежащее множеству [1, 2] и есть второе число принадлежащее множеству [4, 5], то если сложить два этих числа, получится число принадлежащее множеству [5, 7], но число 5 можно получить только если сложить 1 и 4, а для числа 6 существует бесконечное количество пар чисел, поэтому вероятность получения числа 6 выше, чем вероятность получения числа 5. Поэтому мною были придуман новый вид чисел, с помощью которых можно учитывать вероятности. Разумеется если взять некое бесконечное множество и некое неизвестное число гарантированно принадлежащее данному множеству, то вероятность того что это число будет равным некому заранее известному числу из этого множества, стремится к 0, поскольку множество бесконечно. Но вот что я придумал сделать, предположим есть множество [a, b] и есть некое случайное число x принадлежащее множеству, предположим что если разделить множество на n равных частей, то x имеет некую вероятность принадлежать одной из частей, для каждой части вероятность может быть различной. Предположим что есть функция f получающая номер части и возвращающая вероятность (от 0 до 1) того, принадлежит ли этой части число x. На основе функции f можно создать функцию f1, f1(x) = f(x) * n. При стремлении n к бесконечности, функция f1 возвращает значение, с помощью которого можно оценить вероятность того, что x находится в окрестностях некого числа. Если f1 возвращает значение 0, то считается, что вероятность существует, но она минимально возможная, а чем выше число, тем выше вероятность. Для создания нового вида чисел, я взял суперпозиционные числа и добавил к ним функцию f1. Характеристику числа, которую описывает функция f1 я изначально назвал концентрацией, но уже после того как я всё придумал, мне в подписки на youtube пришло два видео (первое, второе), в которых рассказывается о вероятности вероятностей и там такую характеристику называли плотностью, поэтому и я тоже буду называть её плотностью, а сами числа - плотностными. Для удобства в дальнейшем областью определения (какому множеству принадлежит x) функции в плотностных числах, будет множество [0, 1], а для получения плотности в конкретной точке, значение получаемое из функции, будет масштабироваться.

С помощью таких плотностных чисел у fitness функции куда больше данных, для более качественной оценки весов нейронной сети. Выше я уже писал, что для уменьшения проблемы вызванной суперпозиционными числами, я придумал не только новый вид чисел, но и новый алгоритм обучения. Думая о том как решить проблему вызванную суперпозиционными числами, я понял что эта проблема очень сильно усугубляется тем, что все веса являются суперпозиционными числами и если в один момент во время обучения суперпозиционным числом будет только один вес, то это должно колоссально снизить проблему, а если заменить суперпозиционное число на плотностное, проблема должна ещё больше снизиться. И так, теперь только один вес является плотностным числом, а какими значениями заполнить все остальные числа? Случайными? Не очень мне такой подход нравиться и я решил, что можно в начале обучить нейронную сеть способом используемым с суперпозиционными числами, но вместо суперпозиционных чисел, использовать плотностные, а затем уже использовать новый подход. В результате финальный вариант алгоритма получился следующим:

  • создать нейронную сеть в которой все веса - плотностные числа с множеством, которое ограниченно минимальным и максимальным значением веса и с функцией y(x) = 1

  • создать fintess функцию которая принимает указную нейронную сеть и обучающую выборку

  • уменьшить размер множества из плотностного числа в одном весе в 2 раза, охватив либо половину множества с меньшими числами, либо с большими числами. Выбирается та половина, заменив на которую fitness функция даст большее значение. Если для обоих половин fitness функция выдаёт одинаковое значение, то выбирается случайная половина

  • выше указанные действия повторяются для каждого веса

  • выше указанные действия повторяются до тех пор, пока границы всех множеств плотностных чисел в весах отличаются на определённое значение

  • заменить каждый вес на любое вещественное число из множества охватываемого плотностным числом из соответствующего веса

  • заменить один вес на плотностное число, охватывающее множество ограниченное минимальным и максимальным значением веса

  • уменьшить размер множества из плотностного числа в одном весе в 2 раза, охватив либо половину множества с меньшими числами, либо с большими числами. Выбирается та половина, заменив на которую fitness функция даст большее значение. Если для обоих половин fitness функция выдаёт одинаковое значение, то выбирается случайная половина

  • выше указанное действие повторять до тех пор, пока границы множества плотностного числа в весе отличаются на определённое значение

  • заменить вес на любое вещественное число из множества охватываемого плотностным числом из веса

  • повторить 4 последних действия над каждым весом

  • если в результате последних 5-ти действий нейронная сеть стала более обученной, то повторить эти 5 действий ещё раз

Хотя и в суперпозиционных числах, и в плотностных числах может быть сколь угодно много отрезков возможных чисел (например: суперпозиционное число состоящее из 3 отрезков ([0, 1], [20, 40], [100, 101]) ), поскольку я эти числа использую только в контексте обучения нейронных сетей, то всё что я говорю ниже, относиться к плотностным числам которые состоят из 1 отрезка ограниченного 2-мя вещественными числами. В начале этой статьи я писал о том, что я не проработал все необходимые формулы и вот о каких формулах идёт речь. Если взять два плотностных числа [1, 2, y(x) = 1], [4, 5, y(x) = 1], то при сложении этих чисел получается число [5, 7, y(x) = 1 - |0.5 - x| * 2]. Откуда взялась функция y(x) = 1 - |0.5 - x| * 2? Я её вывел вручную и возможно она не верна, но даже если я не прав с формулой, то в любом случае при сложении двух плотностных чисел, в результирующем числе будет функция которая использует функции из слагаемых. Если в качестве функции активации нейронов использовать функцию y(x) = x, то даже в таком случае для обучения моим алгоритмом, нужно знать как складывать и перемножать 2 плотностных числа. С учётом того, что в результате сложения или перемножения двух плотностных чисел, формулы из 2-х исходных чисел будут храниться и в результирующем числе, то при увеличении количества нейронов и слоёв в сети, количество времени и памяти для обучения растёт экспоненциально. Однако есть одно но, для того чтобы узнать какая функция будет в результате сложения, необходимо знать только функции из слагаемых, т.е. в выражении [a1, b1, y1(x) = f1(x)] + [a2, b2, y2(x) = f2(x)] = [a3, b3, y3(x) = f3(x)], f3 не зависит от a1, b1, a2, b2, а зависит только от f1 и f2, если этим свойством обладает и произведение, то есть несколько оптимизаций с помощью которых можно значительно сократить скорость роста потребления памяти и времени во время обучения. Поскольку статья получилась и так не маленькой, а так же поскольку формулы для сложения и произведения пока не известны, рассказ об оптимизациях отложу на потом.

P. S. Достаточно быстро я остановил разработку компилятора для моего языка, о котором была моя прошлая статья. Кратко о том по чему я это сделал - https://cine-lang.blogspot.com/2020/02/blog-post.html. После прекращения разработки, я начал разработку нового языка, у которого отсутствуют недостатки предыдущего. На момент написания статьи я реализовал новый язык, компилятор и стандартную библиотеку на 80%. Мне очень хочется закончить новый вариант своего языка программирования, а так же реализовать хотя бы, несколько из своих идей (когда закончу ЯП, хочу попробовать реализовать свой алгоритм сжатия изображений, аудио и видео). Но в последнее время жизнь складывается не очень (как в прочем и у многих), из-за совокупности нескольких факторов (включая пандемию), я потерял работу и если осенью я хотя бы грибами питался, то сейчас иногда приходиться и ролтоны есть. Из за того, что в данный момент я много времени трачу на поиск работы (подработок) и иногда еды, а так же из-за психологического давления того факта, что у меня нет средств к существованию, разработка языка продвигается медленно. Если я бы смог фокусироваться на разработке, то компилятор и стандартную библиотеку я закончил бы, скорее всего к концу февраля. Поскольку моя обычная зарплата не превышает 200 долларов США в месяц, даже незначительная финансовая помощь поможет мне значительно. По этому, прошу помощи у всех не равнодушных (на хабре есть кнопка "Задонатить"). Благодарю всех откликнувшихся.

Подробнее..

Алгоритм Kosaraju по полкам

14.01.2021 12:05:51 | Автор: admin

На самом деле, уже есть статья на Хабре по этому алгоритму, но она не освещает доказательство корректности и некоторых шагов алгоритма. Я решил создать более справочную версию той статьи с полным разбором.

Этот пост будет полезен студентам, изучающим дисциплину "Алгоритмы и Теория графов", а также тем, кто хочет улучшить/освежить свои знания об алгоритмах на графах.

Для того, чтобы понять алгоритм Косарайю необходимо владеть некоторыми понятиями теории графов

Основные понятия

сильно связные вершины u, vсильно связные вершины u, v

Вершины u, v называются сильно связными, если в графе G существует путь (необязательно прямой) uv И vu (Обозначим сильно связные вершины uv)

Компоненты сильной связностиКомпоненты сильной связности

Компоненты сильной связности - максимальные по включению сильно связные подграфы.

Инвертирование графа -- смена направления всех рёбер в графе на противоположные (двунаправленное ребро остаётся самим собой)

Инвертирование графа - процесс поворота рёбер в обратную сторону (двунаправленное ребро останется самим собой)

Можно привести несколько достаточно очевидных лемм:

1. Компонента сильной связности -- это множество вершин, входящих в множество циклов,
имеющих хотя бы одну общую вершину

связаны циклы 1 и 2, 2 и 3связаны циклы 1 и 2, 2 и 3

2. Инвертирование рёбер цикла не влияет на его цикличность

3. Если истинно u v И v w, то истинно u v w

4. Отдельная вершина представляет собой одну компоненту сильной связности

Алгоритм непосредственно

Алгоритм предназначен для поиска компонент сильной связности в ориентированном графе и состоит из трёх шагов:

  1. Выполнить поиск в глубину (DFS), пока не будут помечены все вершины. Вершина считается помеченной, когда ей присвоен индекс в порядке завершения рекурсивных шагов тактов DFS (время выхода).

    Назовём одним тактом DFS поиск очередного дерева путей

  2. Инвертировать исходный граф

  3. Выполнить DFS в порядке убывания пометок вершин.

Полученные деревья каждого такта DFS последнего шага являются компонентами сильной связности

Небольшое, но важное уточнение: время выхода следует считать следующим образом: изначально счётчик времени нулевой, а увеличивается он в двух случаях:

  1. Начало нового такта DFS

  2. Прохождение по ребру (при том, не важно, рекурсивный проход или нет)

Прежде чем доказывать алгоритм, предлагаю разобрать пример работы алгоритма

Пример работы алгоритма Косарайю пошагово

Дан следующий граф:

Шаг 1:
Непомеченные вершины имеют метку '?'
Справа от исходного графа находится дерево DFS (если была возможность выбрать из 2 рёбер, я выбирал пойти в вершину с меньшим индексом; можете проверить сами, как работает алгоритм, если выбирать бОльший индекс)

Из иллюстрации видно, как работает рекурсия алгоритма поиска в глубину - возвращаясь из вершины (из которой больше нет путей в непомеченные вершины) время увеличивается на 1

Из этого шага прослеживается, что вершина начала такта (корень) имеет самую большую (в такте) метку -- это объясняется рекурсивностью алгоритма DFS -- алгоритм заходит в одну вершину и выходит из неё же. Этот факт понадобится при доказательстве

Шаг 2:
Инвертируем рёбра

Шаг 3:
Так как теперь нам интересен лишь лес тактов DFS, то нет смысла считать время выхода из вершин, поэтому я не показал рекурсивных переходов

Справа от инвертированного графа
показан лес тактов DFS

После завершения алгоритма имеем 3 компоненты сильной связности

Доказательство корректности алгоритма

Немного уточним, что требуется доказать:


Вершины u и v сильно связны после выполнения алгоритма они принадлежат одному дереву такта DFS

Доказательство:

Если вершины u и v были сильно связны в графе G, то на третьем этапе будет найден путь из одной вершины в другую (по лемме 2), это означает, что по окончании алгоритма обе вершины лежат в одном дереве.

Вершины u и v лежат в одном и том же дереве поиска в глубину на третьем шаге алгоритма. Значит, они обе достижимы из корня r этого дерева.

Вершина r была рассмотрена на 3 шаге раньше всех, значит время выхода из неё на 1 шаге больше, чем время выхода из вершин u и v. Из этого мы получаем 2 случая:

  1. Обе эти вершины были достижимы из r в исходном графе. Это означает сильную связность вершин u и r и сильную связность вершин v и r (по лемме 2). Складывая пути мы получаем связность вершин u и v (по лемме 3)

  2. Хотя бы одна вершина не достижима из r в исходном графе, например v. Значит и r была не достижима из v в исходном графе, так как время выхода r больше (если бы она была достижима, то время выхода v было бы больше, чем у r, просмотрите ещё раз первый шаг примера). Значит между этими вершинами нет пути (ни в исходном, ни в инвертированном графах), но последнего быть не может, потому что по условию v достижима из r на 3 шаге (в инвертированном графе)

Значит, из случая 1 и не существования случая 2 получаем, что вершины u и v сильно связны в обоих графах

Сложность алгоритма

Поиск в глубину в исходном графе выполняется за O(V+E)

Для того, чтобы инвертировать все ребра в графе, представленном в виде списка смежности потребуется O(V+E) действий. Для матричного представления графа не нужно выполнять никакие действия для его инвертирования (индексы столбцов будут использоваться в качестве индексов строк и наоборот)

Количество рёбер в инвертированном равно количеству рёбер в изначальном графе, поэтому поиск в глубину будет работать за O(V+E)

В итоге получаем, что сложность алгоритма O(V+E)

Итог

Алгоритм Косарайю ищет компоненты сильной связности, причём делает он это за O(V+E) времени.

Где применять алгоритм, полностью зависит от Вашего воображения составлять графы.

Например: проецирование транспортной сети на граф. Алгоритм поможет проверить новоиспечённую транспортную сеть на достижимость каждой вершины из каждой вершины (чтобы убедиться, что есть путь из окраины в центр и обратно).

Можно тестировать алгоритмом систему воздуховода в зданиях; течение тока в полупроводниковых приборах

Можно мыслить шире: проецируем кровеносную систему живого существа, которое Вам поручили создать в рамках проекта генной инженерии, где-нибудь в 2077 году). Алгоритм поможет узнать, доходит ли кровь от сердца до органов и обратно.

Подробнее..

Тестирование псевдослучайной последовательностью

14.01.2021 20:16:39 | Автор: admin

Как конечные пользователи канала связи мы должны были принять участие в испытаниях доработанной системы связи. Собственно говоря, наше участие было простое принести ноутбук и блок сопряжения, подключить к системе и непрерывно выдавать из компьютера любые информационные кадры как некоторую полезную нагрузку.

Разработчики должны были гонять систему в разных режимах, а затем телеметристы выдать нам принятый массив данных. После этого мы должны были проверить контрольные суммы (пардон, циклически избыточный код) каждого кадра и, если найдем ошибки, внести их число в протокол испытаний.

Поэтому надо было подготовить простую программу (в смысле ПО) для испытаний. И встал вопрос, что выдавать в качестве информации? Решили все-таки не тривиальную решетку AA55, а псевдослучайную последовательность с помощью примитивного полинома Галуа.

Алгоритм там действительно очень простой:

;---- ВДАЧА ПСЕВДОСЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ----ПСП:  MOV       EBX,ЗНАЧЕНИЕ   ;ПЕРВОНАЧАЛЬНО ВСЕ ЕДИНИЦ      MOV       CX,ДЛИНА_ПСП   ;НОМЕРА ОТВОДОВ ОБРАТНОЙ СВЯЗИ;---- ВСТАВЛЯЕМ ПОЗИЦИЮ ОТВОДА ОБРАТНОЙ СВЯЗИ ----M1:   MOV       EAX,1      XCHG      CH,CL      SHL       EAX,CL      XCHG      CH,CL;---- ОБРАБАТВАЕМ ОЧЕРЕДНОЙ БИТ ----      ROR       EBX,1      JNB       M2;---- ОЧЕРЕДНОЙ БИТ - ЕДИНИЦА ----      AND       EAX,EBX ;ВДЕЛЯЕМ СИГНАЛ ОБРАТНОЙ СВЯЗИ      MOV       EAX,1      JNZ       @      SHL       EAX,CL      OR        EBX,EAX ;ЕСЛИ ОБРАТНАЯ СВЯЗЬ=0, ДОПИСВАЕМ 1      JMPS      M4@:    SHL       EAX,CL      NOT       EAX      AND       EBX,EAX ;ЕСЛИ ОБРАТНАЯ СВЯЗЬ=1, ДОПИСВАЕМ 0      JMPS      M4;---- ОЧЕРЕДНОЙ БИТ - НОЛЬ ----M2:   AND       EAX,EBX ;ВДЕЛЯЕМ СИГНАЛ ОБРАТНОЙ СВЯЗИ      MOV       EAX,1      JZ        @      SHL       EAX,CL      OR        EBX,EAX ;ЕСЛИ ОБРАТНАЯ СВЯЗЬ=1, ДОПИСВАЕМ 1      JMPS      M3@:    SHL       EAX,CL      NOT       EAX      AND       EBX,EAX ;ЕСЛИ ОБРАТНАЯ СВЯЗЬ=0, ДОПИСВАЕМ 0;---- ВДАЧА НУЛЯ ----M3:  CLC     RCR       БАЙТ,1     JMPS      @;---- ВДАЧА ЕДИНИЦ ----M4:  STC     RCR       БАЙТ,1;---- ВДАЧА ОЧЕРЕДНОГО БАЙТА ПСП ----@:   DEC       БИТ    ;БАЙТ ЕЩЕ НЕ КОНЧИЛСЯ ?     JNZ       M1     MOV       БИТ,8  ;ОПЯТЬ 8 БИТ     MOV       ЗНАЧЕНИЕ,EBX ;ДЛЯ ПРОДОЛЖЕНИЯ ПСП     MOV       AL,БАЙТ ;ВДАЛИ ОЧЕРЕДНОЙ БАЙТ ПСП     RET

Эта подпрограмма выдает все возможные комбинации нулей и единиц (кроме комбинации из одних нулей) заданной длины в псевдослучайном порядке. В нашем случае для длины 32 бит получается полмиллиарда псевдослучайных байт до повторения данной последовательности заново. Очень просто и красиво.

Поскольку испытания были долгие, их разбили на 2 дня. В первый день мы подключили ноутбук и ушли, так как во время собственно испытаний нам делать нечего. Вечером обработали принятые данные, все в порядке.

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

Что за черт? Да тут всего один кабель в систему уходит. Перезапустили программу. Опять доклад: сигнал исчез. Полчаса, час пытаемся что-то исправить, хотя попытки большей частью сводятся к хождению вокруг стола с компьютером и пожиманию плечами.

Все повторяется: при включении компьютера аппаратная заявляет, что видит несущую (а это что? Нет у нас никакой несущей!), затем запускаем собственно программу и сигнал опять пропадает. Вдруг через час в переговоры с аппаратной вмешивается телеметрист: да нет никакого пропадания сигнала! Я все нормально принимаю, как и вчера.

Фу-ты, ну-ты. Вчера же действительно все было нормально!

Начинаем разбираться.

Оказывается, вчера в аппаратной дежурил молодой специалист. Его спросили, есть сигнал полезной нагрузки? Он глянул на осциллограф а там бежит наша шумоподобная псевдослучайная последовательность. Он же не знает, как должен выглядеть сигнал, поэтому спокойно докладывает: да, есть.

А сегодня дежурит опытный человек, много раз проводивший испытания. Но вот таких сигналов полезной нагрузки ему, похоже, никогда не давали. Включаем компьютер он докладывает, что видит несущую (это на самом деле выдача одних нулей). А когда программа начинает выдавать псевдослучайную последовательность, он вместо доклада вижу шумоподобный сигнал сразу делает ложный вывод: сигнал исчез, белый шум.

Таким образом, получилось не только тестирование канала связи псевдослучайной последовательностью, но и случайное тестирование самой псевдослучайной последовательности, убедительно подтвердившее ее случайность, ведь вполне опытный человек не смог отличить ее от белого шума.

Это заставило задуматься о математике вообще и о необычных людях, двигавших ее (а, заодно, и развитие всей науки) вперед. Мы использовали полином Галуа. Всего 20 лет жизни Эвариста Галуа и 4 года его занятие математикой оставили такое наследие, которым мы, не задумываясь, пользуемся до сих пор.

Конечно, работы Галуа появились не на пустом месте. Можно сказать, что он принял знамя из рук Нильса Абеля, тоже обидно рано ушедшего из жизни. И после нелепой смерти Галуа, на дуэли, да еще при мутных обстоятельствах, развитие математики, конечно, не остановилось. Например, уже через двадцать лет появились полиномы Чебышева, которыми мы пользуемся каждый раз, когда с помощью FPU считаем триногометрические функции.

Но все-таки личность математика тоже играет важную роль. Еще в античности философы, а заодно и математики, рассказывали друг другу шутку-софизм про Ахиллеса и черепаху. При этом они находились в шаге от великого математического открытия: сумма бесконечного числового ряда может быть конечной. Но тогда рядом не оказалось мальчишки со свежим взглядом, вроде Галуа, который бы вместо идиотского вывода Ахиллес никогда не догонит черепаху, сделал бы шаг в правильном направлении: Ахиллес никогда не догонит черепаху за заданное время, за первую секунду, но за вторую уже перегонит - значит, несмотря на бесконечное деление времени на части, сумма этих бесконечных частей конечна! Такого математика тогда не нашлось и ряды (которые мы не совсем правомерно называем рядами Тейлора) отодвинулись на тысячи лет.

Если бы Галуа не погиб в юном возрасте, сколько бы еще открытий мог бы сделать. А если бы он с Чарльзом Бэббиджем бы встретился, ну или бы с Адой Лавлейс, возможно, жили бы мы сейчас совсем в другом компьютерном мире

Подробнее..

Категории

Последние комментарии

© 2006-2021, personeltest.ru