¿Qué significa "mapa"?

10

He encontrado el término muchas veces, en varios materiales educativos de CS:

  1. L2 CS162 (UC Berkeley):

    E / S mapeadas en memoria

  2. L4 CS162 (UC Berkeley):

    Archivos mapeados de memoria

  3. L24 CS61 (UC Berkeley):

    "E / S asignadas a memoria": registros de control / datos del dispositivo asignados al espacio de direcciones de la CPU

  4. Incluso, después de buscar en Google "mapeo", recibí el artículo Map_ (función de orden superior) , pero no estaba muy claro para mí.
  5. Aún más, traté de entender el significado en el contexto de bitmapal leer el artículo de Wikipedia :

    Una matriz de bits es una asignación de algún dominio (casi siempre un rango de enteros) a valores en el conjunto {0, 1}

    No estoy seguro, pero en el contexto anterior me parece acerca de la conversión de datos.

  6. Más tarde, después de leer un libro de CS, encontré solo este párrafo, pero no explicaba el significado de "mapeo" para mí:

    Mapeo de memoria Linux (junto con otras formas de Unix) inicializa el contenido de un área de memoria virtual al asociarlo con un objeto en el disco, un proceso conocido como mapeo de memoria.

  7. También obtuve MapReduce como resultado de búsqueda: donde el mapa se explica como "un modismo en la computación paralela donde se aplica una operación simple a todos los elementos de una secuencia, potencialmente en paralelo".

Todavía estoy confundido sobre el término. ¿Alguien puede explicar qué significa "mapa" en los contextos que mencioné?

Kais
fuente

Respuestas:

14

Entonces, hay dos usos distintos de la palabra "mapa", que descomprimiré aquí.

  1. FX2XX.F(X)=2X

    Este uso incluye "IO mapeado en memoria": hay una función (conceptual) que asocia cada pieza de memoria con una acción de IO particular. En realidad, nadie escribe la función, pero de hecho está ahí: por cada pieza de memoria asignada, hay algunas IO asociadas a ella. Tal vez una parte de un disco, tal vez un registro de hardware en un periférico, etc.

    Del mismo modo, las matrices de bits (y las matrices en general) entran en esto: cada índice tiene un único elemento asociado (en cualquier momento), por lo que una matriz es efectivamente una codificación de una función de dominio finito.

  2. En la programación funcional y derivados (como MapReduce), el mapa se refiere a la aplicación de una transformación a través de una estructura.

    El original mapproviene de Lisp, donde se refiere a la función que tomó otra función y una lista, y devolvió el resultado de aplicar la función a cada elemento de esa lista.

    Pero, este fenómeno es bastante general. En Haskell, una estructura de datos que admite dicha operación se llama functor , y la operación se llama fmap (por razones históricas, para evitar conflictos con el mapa de lista).

    Todos estos están relacionados a través del concepto de un Functor de la teoría de categorías, que es una abstracción de estructuras que admiten una operación de "mapa".

jmite
fuente
44
(Error tipográfico en el Functornombre del enlace, demasiado pequeño para sugerir una edición.)
Mat
Muy clara y excelente explicación. Sin embargo, no entendí qué significa 'función finita'.
Kais
1
La 'función finita' de @Kais se usa más comúnmente para una función para la cual ningún elemento está asignado al infinito. Supongo que jmite quería resaltar que las matrices son básicamente funciones que asignan el conjunto de índices (válidos) a los valores contenidos.
Michael Hoff
2
Los dos usos son realmente aspectos de la misma cosa. La mapfunción devuelve un resultado donde cada elemento está asociado con el elemento correspondiente de la entrada. La distinción es que el primer uso describe una relación existente, mientras que el segundo se refiere a una operación que crea la relación.
Barmar
1
Error tipográfico
Barmar
8

En lo que sigue voy a ser menos que exacto de varias maneras, sacrificando la precisión técnica para proporcionar una comprensión básica. Es obvio que ha leído una serie de fuentes técnicas y que la misma tecnicidad del material le dificulta comprender qué es un concepto bastante básico y simple.

En términos simples, el uso más común de la palabra mapa es describir una relación entre las cosas en dos conjuntos diferentes. Esta puede ser una función matemática o puede ser algún otro tipo de representación y mecanismo. Lo más común que viene a la mente de inmediato es el mapa de calles.

Un mapa de calles es una imagen de un terreno o área particular en el mundo real en el que las líneas y dibujos y palabras escritas en el mapa corresponden a calles y edificios físicos reales. Existe una relación uno a uno entre la representación del terreno que se muestra en el mapa de calles y el terreno real.

Mirando más allá, también podemos ver que un mapa de calles es una representación del terreno real. El terreno real tiene objetos y detalles y procesos dinámicos que el mapa de calles no representa. El mapa de calles es una representación abstracta del terreno real y lo que se representa en el mapa de calles es solo lo que se necesita para cumplir su propósito, para proporcionar una ayuda de navegación para el terreno real.

Varios de los ejemplos en la pregunta implican crear una representación con mecanismos de apoyo para que una persona pueda usar la representación y el mecanismo traduzca las acciones de la persona en lo que se necesita para la funcionalidad subyacente que está oculta por la fachada de la representación.

La E / S de archivo mapeada en memoria permite a un programador pensar en un archivo como un área grande de memoria, para usar una representación de memoria de un archivo real. El programador no piensa en el archivo como un archivo, sino que lo considera como un área grande de memoria. La funcionalidad de E / S del archivo mapeado en memoria se asegura de que cuando el programador haga referencia a un desplazamiento de memoria particular, se acceda a los datos correspondientes en el archivo.

La E / S del dispositivo mapeado en memoria permite simplificar la interfaz de programación de un dispositivo escribiendo en direcciones de memoria o leyendo desde direcciones de memoria. Estas funciones de escritura y lectura se traducen mediante la funcionalidad de E / S del dispositivo mapeado en la memoria subyacente en las acciones específicas del dispositivo real necesarias para llevar a cabo el servicio o acción solicitada.

Un mapa de bits es un conjunto de bits que proporciona una correspondencia uno a uno con los valores de algún otro conjunto. Por ejemplo, la CreateFile()función de la API Win32 tiene varios argumentos de mapa de bits que se utilizan para indicar diferentes tipos de atributos de archivo. Los bits específicos en un mapa de bits corresponden a un comportamiento de archivo específico como "Abrir como solo lectura" o "Crear siempre un nuevo archivo vacío". Se proporcionan constantes especiales que se combinan mediante operaciones de bits binarios para especificar los argumentos reales. Consulte la función CreateFile y el código fuente de ejemplo en Abrir un archivo para leer o escribir .

Richard Chambers
fuente
Gran explicación Sin embargo, en relación con el Memory mapped file I/O, ¿es una alternativa a la E / S de archivos estándar (fopen, fgetc ..)? ¿Cuál es la ventaja de rendimiento debido a la naturaleza del acceso RAM más rápido en comparación con los discos?
Kais
1
@Kais Memory Mapped File I / O (MMF) es una alternativa al uso de llamadas estándar de API de archivos. Puede haber o no una ventaja de rendimiento al usar MMF. Realmente depende de qué tan bien la mecánica de MMF se ajuste a la forma en que está utilizando el contenido del archivo, así como de qué tan grande sea el archivo. MMF I / O pagina áreas del archivo en la memoria en bloques grandes. Puede hacer algo similar con la API de archivo y hacer una diferencia de rendimiento significativa. Con la E / S API estándar de archivos, suele haber una gran cantidad de copias entre las memorias intermedias de memoria desde el espacio del núcleo al espacio del usuario que a menudo se omite con MMF.
Richard Chambers el
1
@Ka no está seguro de lo que está preguntando. Copiar datos de una ubicación de memoria a otra lleva tiempo y ciclos de CPU, por lo que reducir la copia de datos mejora el rendimiento al acceder a los datos. La E / S de archivo es de uso general e internamente realiza su propio almacenamiento en caché y paginación del contenido del archivo, sin embargo, por lo general, el tamaño de los búferes de memoria es menor que el que se usa con la E / S de archivo mapeado en memoria. La API de archivo tiende a estar orientada a favorecer la E / S de fragmentos pequeños en lugar de bloques grandes. El acceso secuencial tiende a favorecerse con una mirada hacia adelante dentro de la pila y el núcleo de E / S de archivo.
Richard Chambers
1
@Kais, de modo que si puede proporcionar una pista sobre la API de E / S de archivo, puede mejorar el rendimiento de su aplicación que utiliza la API de E / S de archivo cuando la E / S de archivo es un cuello de botella de rendimiento. Y el uso de E / S de archivos mapeados en memoria también puede ayudar especialmente con el acceso secuencial y las operaciones que se encuentran dentro de un solo tamaño de página MMF. Consulte el material y los enlaces en esta URL sobre E / S de bajo nivel con GNU C gnu.org/software/libc/manual/html_node/… que describe algunas de las mecánicas de nivel inferior de GNU.
Richard Chambers
1
@Kais He visto mejoras significativas en el rendimiento con la API de archivos de la Biblioteca estándar de C al usar la setbuf()función para establecer un búfer de E / S de archivos grandes. Cualquier cosa que pueda hacer para reducir el acceso al dispositivo de almacenamiento tiende a ser una ventaja. Para las unidades de disco, reducir el número de búsquedas puede marcar una gran diferencia, sin embargo, hay una serie de influencias sobre las que no se puede hacer mucho, como la forma en que se organizan los datos en los discos de disco, la velocidad de rotación de los platos, la velocidad de movimiento de la cabeza, el almacenamiento en caché de datos, qué tan bien los golpes de caché reducen el acceso al disco electromecánico, etc.
Richard Chambers
1

El mapeo es simplemente el proceso de asociar una unidad de datos con otra unidad de datos. La intención del mapeo es permitir un acceso simplificado a los datos mapeados. Por ejemplo, en los sistemas clásicos compatibles con IBM, la dirección de memoria 0xB8000 se asignó a la memoria de video de la tarjeta de video. Escribir en esta memoria actualizaría el contenido de la pantalla, y leer desde ella recuperaría el contenido de la pantalla. El mapeo de archivos, el mapeo de dispositivos e incluso el mapeo de estructura de datos (típicamente llamado Mapa, HashMap o Diccionario), son todas formas de asociar una unidad de datos con otra unidad de datos.

El mapeo tiene dos beneficios principales. El primero es que el mapeo reduce la complejidad de acceder al dispositivo o archivo asociado. Por ejemplo, la asignación de archivos y la asignación de dispositivos le permiten tratar esos dispositivos como si fueran solo memoria simple. En lugar de aprender varios puertos de E / S, comandos de datos, etc., obtienes una interfaz simple que es tan natural y obvia como escribir en la RAM.

El segundo beneficio es que puede reducir los requisitos de memoria. Por ejemplo, a Map<Integer, SomeDataType>puede producir una "matriz dispersa", que es útil cuando desea una matriz que contendrá principalmente datos no válidos / no utilizados, y se puede acceder en un tiempo casi lineal. Esto puede ser mucho más eficiente que una lista vinculada (donde toma O ( n ) tiempo acceder a la n elemento -ésima).

El mapeo se utiliza principalmente como una abstracción para ocultar algoritmos / funciones complicadas del desarrollador para que puedan centrarse en la tarea de implementar el programa. Tenga en cuenta que el mapeo no siempre es tan eficiente, en términos de tiempo de procesamiento, como acceder directamente al dispositivo o archivo, pero siempre es menos complicado que hacerlo (por ejemplo, el mapeo reduce la cantidad de código especializado que el desarrollador debe escribir para acceder a los datos )

phyrfox
fuente
Gracias por la explicación. Sin embargo, no entendí qué significa "matriz dispersa" y cómo es más eficiente.
Kais
@Kais Una matriz dispersa es una lista que consta principalmente de valores cero. En lugar de almacenar todos los valores en la memoria, una matriz dispersa solo almacena los valores distintos de cero en la memoria. Al hacer esto, es más eficiente que simplemente asignar toda la memoria a la vez. Las matrices dispersas generalmente deben estar aproximadamente un 75% vacías para ahorrar espacio. La memoria virtual a menudo también funciona de esta manera, donde el sistema operativo solo almacena páginas "sucias" de memoria, así como sistemas de archivos que le permiten almacenar solo sectores de valores distintos de cero.
phyrfox