Was bedeutet "Karte"?

10

Ich bin dem Begriff in verschiedenen CS-Lehrmaterialien oft begegnet:

  1. L2 CS162 (UC Berkeley):

    Speicherzugeordnete E / A.

  2. L4 CS162 (UC Berkeley):

    Speicherzugeordnete Dateien

  3. L24 CS61 (UC Berkeley):

    "Speicherzugeordnete E / A": Gerätesteuerung / Datenregister, die dem CPU-Adressraum zugeordnet sind

  4. Selbst nachdem ich "Mapping" gegoogelt hatte , bekam ich den Artikel Map_ (Funktion höherer Ordnung) , aber es war mir nicht sehr klar.
  5. Noch mehr, versuchte die Bedeutung im Kontext von bitmapdurch das Lesen des Wikipedia-Artikels zu verstehen :

    Ein Bit-Array ist eine Zuordnung von einer Domäne (fast immer ein Bereich von Ganzzahlen) zu Werten in der Menge {0, 1}

    Ich bin mir nicht sicher, aber im obigen Kontext klingt es für mich nach Datenkonvertierung.

  6. Später, nachdem ich ein CS-Buch gelesen hatte, fand ich nur diesen Absatz, aber er erklärte mir nicht die Bedeutung von "Mapping":

    Speicherzuordnung Linux (zusammen mit anderen Unix-Formen) initialisiert den Inhalt eines virtuellen Speicherbereichs, indem es einem Objekt auf der Festplatte zugeordnet wird. Dieser Vorgang wird als Speicherzuordnung bezeichnet.

  7. Ich habe auch MapReduce als Suchergebnis erhalten: wobei map als "eine Redewendung im parallelen Rechnen erklärt wird, bei der eine einfache Operation auf alle Elemente einer Sequenz angewendet wird, möglicherweise parallel".

Ich bin immer noch verwirrt über den Begriff. Kann jemand erklären, was "Karte" in den von mir erwähnten Kontexten bedeutet?

Kais
quelle

Antworten:

14

Es gibt also zwei verschiedene Verwendungen des Wortes "Karte", die ich hier auspacken werde.

  1. fx2xx.f(x)=2x

    Diese Verwendung umfasst "speicherabgebildete E / A": Es gibt eine (konzeptionelle) Funktion, die jedes Speicherelement einer bestimmten E / A-Aktion zuordnet. Eigentlich schreibt niemand die Funktion aus, aber sie ist tatsächlich vorhanden: Für jedes zugeordnete Speicherelement sind E / A-Vorgänge zugeordnet. Möglicherweise ein Teil einer Festplatte, möglicherweise ein Hardwareregister an einem Peripheriegerät usw.

    Ebenso fallen Bit-Arrays (und Arrays im Allgemeinen) in diese Kategorie: Jedem Index ist (zu einem bestimmten Zeitpunkt) ein einzelnes Element zugeordnet, sodass ein Array effektiv eine Codierung einer Finite-Domain-Funktion ist.

  2. In der funktionalen Programmierung und bei Ableitungen (wie MapReduce) bezieht sich map auf das Anwenden einer Transformation auf eine Struktur.

    Das Original mapstammt von Lisp, wo es auf die Funktion verwies, die eine andere Funktion und eine Liste übernahm, und das Ergebnis der Anwendung der Funktion auf jedes Element dieser Liste zurückgab.

    Dieses Phänomen ist jedoch recht allgemein. In Haskell wird eine Datenstruktur, die eine solche Operation zulässt, als Funktor bezeichnet , und die Operation wird als fmap bezeichnet (aus historischen Gründen, um Konflikte mit der Listenzuordnung zu vermeiden).

    All dies hängt mit dem Konzept eines Funktors aus der Kategorietheorie zusammen, bei dem es sich um eine Abstraktion von Strukturen handelt, die eine "Karten" -Operation zulassen .

jmite
quelle
4
(Tippfehler im Linknamen Functor- zu wenig, um eine Änderung vorzuschlagen.)
Mat
Sehr klare und ausgezeichnete Erklärung. Ich habe jedoch nicht verstanden, was "endliche Funktion" bedeutet.
Kais
1
@Kais 'endliche Funktion' wird am häufigsten für eine Funktion verwendet, für die kein Element auf unendlich abgebildet ist. Ich denke, jmite wollte hervorheben, dass Arrays im Grunde Funktionen sind, die die Menge der (gültigen) Indizes den enthaltenen Werten zuordnen.
Michael Hoff
2
Die beiden Verwendungen sind wirklich nur Aspekte derselben Sache. Die mapFunktion gibt ein Ergebnis zurück, bei dem jedes Element dem entsprechenden Element der Eingabe zugeordnet ist. Der Unterschied besteht darin, dass die erste Verwendung eine vorhandene Beziehung beschreibt, während sich die zweite auf eine Operation bezieht, die die Beziehung erstellt.
Barmar
1
Tippfehler
Barmar
8

Im Folgenden werde ich in vielerlei Hinsicht weniger genau sein und die technische Genauigkeit opfern, um ein grundlegendes Verständnis zu vermitteln. Es ist offensichtlich, dass Sie eine Reihe technischer Quellen gelesen haben und die technische Qualität des Materials es Ihnen schwer macht, ein ziemlich einfaches und einfaches Konzept zu verstehen.

In einfachen Worten ist die häufigste Verwendung der Wortkarte die Beschreibung einer Beziehung zwischen den Dingen in zwei verschiedenen Mengen. Dies kann eine mathematische Funktion oder eine andere Art der Darstellung und des Mechanismus sein. Am häufigsten fällt mir sofort die Straßenkarte ein.

Eine Straßenkarte ist ein Bild eines bestimmten Geländes oder Gebiets in der realen Welt, in dem die auf der Karte geschriebenen Linien, Zeichnungen und Wörter den tatsächlichen physischen Straßen und Gebäuden entsprechen. Es gibt eine Eins-zu-Eins-Beziehung zwischen der Darstellung des in der Straßenkarte abgebildeten Geländes und dem tatsächlichen Gelände.

Wenn wir weiter schauen, können wir auch sehen, dass eine Straßenkarte eine Darstellung des tatsächlichen Geländes ist. Das tatsächliche Gelände enthält Objekte und Details sowie dynamische Prozesse, die auf der Straßenkarte nicht dargestellt sind. Die Straßenkarte ist eine abstrakte Darstellung des tatsächlichen Geländes, und was in der Straßenkarte dargestellt ist, ist nur das, was benötigt wird, um ihren Zweck zu erfüllen und eine Navigationshilfe für das reale Gelände bereitzustellen.

Einige der Beispiele in der Frage umfassen das Erstellen einer Darstellung mit unterstützenden Mechanismen, damit eine Person die Darstellung verwenden kann, und der Mechanismus übersetzt die Aktionen der Person in das, was für die zugrunde liegende Funktionalität erforderlich ist, die von der Fassade der Darstellung verborgen wird.

Mit der Speicherzuordnungs-Datei-E / A kann ein Programmierer eine Datei als großen Speicherbereich betrachten und eine Speicherdarstellung einer realen Datei verwenden. Der Programmierer betrachtet die Datei nicht als Datei, sondern als großen Speicherbereich. Die Speicherzuordnungs-Datei-E / A-Funktionalität stellt sicher, dass auf die entsprechenden Daten in der Datei zugegriffen wird, wenn der Programmierer auf einen bestimmten Speicheroffset verweist.

Durch speicherabgebildete Geräte-E / A kann eine Geräteprogrammierschnittstelle vereinfacht werden, indem in Speicheradressen geschrieben oder aus Speicheradressen gelesen wird. Diese Schreib- und Leseaktionen werden von der zugrunde liegenden speicherabgebildeten Geräte-E / A-Funktionalität in die tatsächlichen gerätespezifischen Aktionen übersetzt, die zur Ausführung des angeforderten Dienstes oder der angeforderten Aktion erforderlich sind.

Eine Bitmap ist eine Menge von Bits, die eine Eins-zu-Eins-Entsprechung zu den Werten einer anderen Menge liefern. Beispielsweise verfügt die CreateFile()Funktion der Win32-API über mehrere Bitmap-Argumente, mit denen verschiedene Arten von Dateiattributen angegeben werden. Bestimmte Bits in einer Bitmap entsprechen einem bestimmten Dateiverhalten, z. B. "Als schreibgeschützt öffnen" oder "Immer neue leere Datei erstellen". Es werden spezielle Konstanten bereitgestellt, die mithilfe von Binärbitoperationen kombiniert werden, um die tatsächlichen Argumente anzugeben. Siehe CreateFile-Funktion und den Beispielquellcode unter Öffnen einer Datei zum Lesen oder Schreiben .

Richard Chambers
quelle
Tolle Erklärung. Doch in Bezug auf die Memory mapped file I/Oist es eine Alternative zur Standard - Datei i / o (fopen, fgetc ..)? Ist der Leistungsvorteil aufgrund der Art des Arbeitsspeichers schneller als bei Festplatten?
Kais
1
@Kais Memory Mapped File I / O (MMF) ist eine Alternative zur Verwendung von Standard-Datei-API-Aufrufen. Die Verwendung von MMF kann einen Leistungsvorteil haben oder auch nicht. Es hängt wirklich davon ab, wie gut die Mechanik von MMF zu der Art und Weise passt, wie Sie den Dateiinhalt verwenden, und wie groß die Datei ist. MMF-E / A-Seitenbereiche der Datei werden in großen Blöcken gespeichert. Mit der Datei-API können Sie etwas Ähnliches tun und einen signifikanten Leistungsunterschied erzielen. Bei Standard-Datei-API-E / A wird häufig zwischen Speicherpuffern vom Kernel-Speicherplatz in den Benutzerbereich kopiert, der häufig mit MMF umgangen wird.
Richard Chambers
1
@ Kais nicht sicher, was Sie fragen. Das Kopieren von Daten von einem Speicherort zu einem anderen erfordert Zeit und CPU-Zyklen. Wenn Sie also das Kopieren von Daten reduzieren, wird die Leistung beim Zugriff auf Daten verbessert. Die Datei-E / A ist universell einsetzbar und führt intern ein eigenes Caching und Paging von Dateiinhalten durch. In der Regel ist die Größe der Speicherpuffer jedoch kleiner als bei Speicherzuordnungs-Datei-E / A. Die Datei-API tendiert dazu, die E / A kleinerer Blöcke anstelle großer Blöcke zu bevorzugen. Sequentieller Zugriff wird in der Regel mit Blick nach vorne innerhalb des Datei-E / A-Stapels und des Kernels bevorzugt.
Richard Chambers
1
@Kais Wenn Sie also einen Hinweis auf die Datei-E / A-API geben können, können Sie die Leistung Ihrer Anwendung verbessern, die die Datei-E / A-API verwendet, wenn die Datei-E / A einen Leistungsengpass darstellt. Die Verwendung von Memory Mapped File I / O kann auch hilfreich sein, insbesondere bei meist sequentiellem Zugriff und Vorgängen, die innerhalb einer einzelnen MMF-Seitengröße liegen. Lesen Sie das Material und die Links unter dieser URL zu Low-Level-E / A mit GNU C gnu.org/software/libc/manual/html_node/…, in denen einige der GNU-Mechaniken auf niedrigerer Ebene beschrieben werden.
Richard Chambers
1
@Kais Ich habe mit der Datei-API der C Standard Library signifikante Leistungsverbesserungen festgestellt, indem ich die setbuf()Funktion zum Festlegen eines E / A-Puffers für große Dateien verwendet habe. Alles, was Sie tun können, um den Zugriff auf das Speichergerät zu reduzieren, ist in der Regel ein Bonus. Bei Festplattenlaufwerken kann die Reduzierung der Anzahl der Suchvorgänge einen großen Unterschied bewirken. Es gibt jedoch eine Reihe von Einflüssen, gegen die Sie nicht viel tun können, z. B. die Organisation der Daten auf Festplattenplatten, die Rotationsgeschwindigkeit der Platten, die Geschwindigkeit der Kopfbewegung und das Caching von Daten, wie gut Cache-Treffer reduzieren, gehen auf die elektromechanische Platte usw.
Richard Chambers
1

Bei der Zuordnung wird einfach eine Dateneinheit einer anderen Dateneinheit zugeordnet. Die Zuordnung soll einen vereinfachten Zugriff auf die zugeordneten Daten ermöglichen. In klassischen IBM-kompatiblen Systemen wurde beispielsweise die Speicheradresse 0xB8000 dem Videospeicher der Grafikkarte zugeordnet. Durch Schreiben in diesen Speicher wird der Inhalt des Bildschirms aktualisiert, und durch Lesen wird der Inhalt des Bildschirms abgerufen. Dateizuordnung, Gerätezuordnung und sogar Datenstrukturzuordnung (normalerweise als Map, HashMap oder Dictionary bezeichnet) sind alle Möglichkeiten, eine Dateneinheit einer anderen Dateneinheit zuzuordnen.

Mapping hat zwei Hauptvorteile. Das erste ist, dass die Zuordnung die Komplexität des Zugriffs auf das zugehörige Gerät oder die zugeordnete Datei verringert. Mit der Dateizuordnung und Gerätezuordnung können Sie diese Geräte beispielsweise so behandeln, als wären sie nur einfacher Speicher. Anstatt verschiedene E / A-Ports, Datenbefehle usw. zu lernen, erhalten Sie eine einfache Schnittstelle, die genauso natürlich und offensichtlich ist wie das Schreiben in den Arbeitsspeicher.

Der zweite Vorteil besteht darin, dass der Speicherbedarf reduziert werden kann. Beispielsweise Map<Integer, SomeDataType>kann a ein "spärliches Array" erzeugen, was nützlich ist, wenn Sie ein Array möchten, das hauptsächlich ungültige / nicht verwendete Daten enthält und auf das in nahezu linearer Zeit zugegriffen werden kann. Dies kann weitaus effizienter sein als eine verknüpfte Liste (bei der der Zugriff auf das n- te Element 0 ( n ) dauert ).

Mapping wird hauptsächlich als Abstraktion verwendet, um komplizierte Algorithmen / Funktionen vor dem Entwickler zu verbergen, damit er sich auf die Aufgabe der Implementierung des Programms konzentrieren kann. Beachten Sie, dass die Zuordnung in Bezug auf die Verarbeitungszeit möglicherweise nicht immer so effizient ist wie der direkte Zugriff auf das Gerät oder die Datei, jedoch immer weniger kompliziert ist (z. B. reduziert die Zuordnung die Menge an spezialisiertem Code, den der Entwickler schreiben muss, um auf die Daten zuzugreifen ).

Phyrfox
quelle
Danke für die Erklärung. Ich habe jedoch nicht verstanden, was "spärliches Array" bedeutet und wie es effizienter ist.
Kais
@Kais Ein Sparse-Array ist eine Liste, die hauptsächlich aus Nullwerten besteht. Anstatt alle Werte im Speicher zu speichern, speichert ein Array mit geringer Dichte nur die Werte ungleich Null im Speicher. Auf diese Weise ist es effizienter, als einfach den gesamten Speicher auf einmal zuzuweisen. Sparse Arrays sollten normalerweise zu 75% leer sein, um Platz zu sparen. Der virtuelle Speicher funktioniert häufig auch so, wenn das Betriebssystem nur "schmutzige" Speicherseiten sowie Dateisysteme speichert, in denen Sie nur Sektoren mit Werten ungleich Null speichern können.
Phyrfox