Что означает «карта»?

Я много раз встречал этот термин в различных учебных материалах по КС:

L2 CS162 (Калифорнийский университет в Беркли):

Отображение в памяти ввода-вывода
L4 CS162 (Калифорнийский университет в Беркли):

Файлы с отображенной памятью
L24 CS61 (UC Berkeley):

«Операции ввода-вывода с отображением в памяти»: регистры управления / данных устройства отображаются в адресное пространство ЦП.
Даже после поиска в Google «картографирования» я получил статью Map_ (высшего порядка) , но она мне не очень понятна.
Более того, попытался понять значение в контексте bitmap, прочитав статью в Википедии :

Битовый массив - это отображение некоторого домена (почти всегда диапазона целых чисел) на значения в наборе {0, 1}

Я не уверен, но в контексте выше это звучит для меня о преобразовании данных.
Позже, прочитав книгу CS, я нашел только этот абзац, но он не объяснил для меня значение «картирования»:

Отображение памяти Linux (наряду с другими формами Unix) инициализирует содержимое области виртуальной памяти, связывая его с объектом на диске, процессом, известным как отображение памяти.
Я получил также MapReduce как результат поиска: где map объясняется как «идиома в параллельных вычислениях, где простая операция применяется ко всем элементам последовательности, возможно, параллельно».

Я все еще не понимаю этот термин. Кто-нибудь может объяснить, что означает «карта» в контексте, о котором я говорил?

data-structures operating-systems memory-management Kais
источник

Ответы:

Итак, есть два разных использования слова «карта», которые я здесь распакую.

Первый очень общий, где map означает «связать», в частности, посредством функции. Если мы говорим « отображает каждый на », то мы говорим . $f$ $x$ $2x$ $\forall x \ldotp f(x) = 2x$

Это использование включает в себя «IO с отображением памяти»: существует (концептуальная) функция, связывающая каждый фрагмент памяти с определенным действием IO. Никто на самом деле никогда не записывает эту функцию, но она действительно есть: для каждого фрагмента отображенной памяти есть некоторый ввод-вывод, связанный с ней. Может быть, часть диска, может быть аппаратный регистр на периферии и т. Д.

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

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

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

Все они связаны через концепцию Функтора из теории категорий, которая представляет собой абстракцию структур, допускающих операцию «карты».

jmite
источник

(Опечатка в Functorназвании ссылки - слишком мало, чтобы предложить редактирование.)

Mat

Очень четкое и отличное объяснение. Однако я не понял, что означает «конечная функция».

Кайс

@Kais «конечная функция» чаще всего используется для функции, для которой ни один элемент не отображается в бесконечность. Я предполагаю, что jmite хотел подчеркнуть, что массивы - это в основном функции, отображающие набор (допустимых) индексов в содержащиеся значения.

Майкл Хофф

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

Бармар

Опечатка

Бармар

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

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

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

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

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

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

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

Битовая карта - это набор битов, которые обеспечивают однозначное соответствие значениям некоторого другого набора. Например, CreateFile()функция Win32 API имеет несколько аргументов битовой карты, которые используются для указания различных типов атрибутов файла. Конкретные биты в битовой карте соответствуют определенному поведению файла, например «Открыть только для чтения» или «Всегда создавать новый пустой файл». Предоставляются специальные константы, которые объединяются с использованием двоичных битовых операций для указания фактических аргументов. См. Функцию CreateFile и пример исходного кода в разделе « Открытие файла для чтения или записи» .

Ричард Чемберс
источник

Отличное объяснение. Однако относительно того Memory mapped file I/O, является ли это альтернативой стандартному файловому вводу / выводу (fopen, fgetc ..)? такое преимущество в производительности из-за характера оперативной памяти быстрее доступа по сравнению с дисками?

Кайс

@ Kais Memory Mapped File I / O (MMF) - альтернатива использованию стандартных вызовов API файлов. Использование MMF может иметь или не иметь преимущества в производительности. Это действительно зависит от того, насколько хорошо механика MMF соответствует тому, как вы используете содержимое файла, а также от размера файла. MMF вводит / выводит области файла в память большими блоками. Вы можете сделать что-то подобное с файловым API и существенно повысить производительность. При стандартном файловом API ввода / вывода, как правило, происходит много копирования между буферами памяти из пространства ядра в пространство пользователя, которое часто обходится без MMF.

Ричард Чамберс

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

Ричард Чамберс

@Kais, поэтому, если вы можете дать подсказку API-интерфейсу файлового ввода-вывода, вы можете улучшить производительность своего приложения, использующего API-интерфейс файлового ввода-вывода, когда файловый ввод-вывод является узким местом в производительности. Кроме того, использование операций ввода-вывода с отображением в память также может помочь, в основном, при последовательном доступе и операциях, размер которых не превышает одного размера страницы MMF. См. Материал и ссылки по этому URL о низкоуровневом вводе-выводе с помощью GNU C gnu.org/software/libc/manual/html_node/…, в которой описываются некоторые механизмы GNU более низкого уровня.

Ричард Чемберс

@Kais Я наблюдал значительные улучшения производительности с помощью API-интерфейса файлов стандартной библиотеки C, используя setbuf()функцию для установки большого буфера ввода-вывода файлов. Все, что вы можете сделать, чтобы ограничить доступ к устройству хранения, как правило, является бонусом. Для накопителей на дисках уменьшение количества обращений может иметь большое значение, однако есть ряд факторов, которые вы не можете сделать с этим, например, как данные организованы на дисковых дисках, скорость вращения пластин, скорость перемещения головки, кэширование данные, насколько хорошо попадания в кэш уменьшают попадание на электромеханический диск и т. д.

Ричард Чамберс

Картирование - это просто процесс связывания одной единицы данных с другой единицей данных. Назначение сопоставления - предоставить упрощенный доступ к сопоставленным данным. Например, в классических IBM-совместимых системах адрес памяти 0xB8000 был сопоставлен с видеопамятью видеокарты. Запись в эту память будет обновлять содержимое экрана, а чтение с него будет извлекать содержимое экрана. Сопоставление файлов, сопоставление устройств и даже сопоставление структуры данных (обычно называемые Map, HashMap или Dictionary) - все это способы связать одну единицу данных с другой единицей данных.

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

Второе преимущество заключается в том, что это может снизить требования к памяти. Например, a Map<Integer, SomeDataType>может создать «разреженный массив», который полезен, когда вам нужен массив, который будет в основном содержать недействительные / неиспользуемые данные и доступ к которому можно получить в почти линейное время. Это может быть гораздо более эффективно, чем связанный список (где для доступа к n- му элементу требуется время O ( n ) ).

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

phyrfox
источник

Спасибо за объяснение. Однако я не понял, что означает «разреженный массив» и как он эффективнее.

Кайс

@Kais Разреженный массив - это список, который состоит в основном из нулевых значений. Вместо того, чтобы хранить все значения в памяти, разреженный массив хранит только ненулевые значения в памяти. Делая это, это более эффективно, чем просто выделять всю память одновременно. Разреженные массивы обычно должны быть примерно на 75% пустыми для экономии места. Виртуальная память также часто работает таким образом, когда ОС хранит только «грязные» страницы памяти, а также файловые системы, которые позволяют хранить только сектора с ненулевыми значениями.

phyrfox