Co oznacza „mapa”?

Termin ten spotkałem wiele razy w różnych materiałach edukacyjnych CS:

L2 CS162 (UC Berkeley):

We / wy mapowane na pamięć
L4 CS162 (UC Berkeley):

Pliki mapowane w pamięci
L24 CS61 (UC Berkeley):

„We / wy mapowane na pamięć”: Rejestry sterowania / danych mapowane na przestrzeń adresową procesora
Nawet po „mapowaniu” google otrzymałem artykuł Map_ (funkcja wyższego rzędu) , ale nie było to dla mnie jasne.
Co więcej, starałem się zrozumieć znaczenie w kontekście bitmap, czytając artykuł w Wikipedii :

Tablica bitów jest odwzorowaniem z pewnej domeny (prawie zawsze zakresu liczb całkowitych) na wartości w zbiorze {0, 1}

Nie jestem pewien, ale w powyższym kontekście brzmi dla mnie o konwersji danych.
Później po przeczytaniu książki CS znalazłem tylko ten akapit, ale nie wyjaśnił mi on znaczenia „mapowania”:

Mapowanie pamięci Linux (wraz z innymi formami Uniksa) inicjuje zawartość wirtualnego obszaru pamięci, kojarząc go z obiektem na dysku, proces znany jako mapowanie pamięci.
Otrzymałem również MapReduce jako wynik wyszukiwania: gdzie mapa jest wyjaśniona jako „idiom w obliczeniach równoległych, w którym prostą operację stosuje się do wszystkich elementów sekwencji, potencjalnie równolegle”.

Nadal jestem zdezorientowany tym terminem. Czy ktoś może wyjaśnić, co oznacza „mapa” w kontekście, o którym wspomniałem?

data-structures operating-systems memory-management Kais
źródło

Odpowiedzi:

Istnieją więc dwa różne zastosowania słowa „mapa”, które tutaj rozpakuję.

$f$ $x$ $2x$ $\forall x \ldotp f(x) = 2x$

To użycie obejmuje „IO zamapowane w pamięci”: istnieje (konceptualna) funkcja kojarząca każdy kawałek pamięci z określoną akcją IO. Tak naprawdę nikt nigdy nie wypisuje tej funkcji, ale ona rzeczywiście istnieje: dla każdego kawałka zmapowanej pamięci wiąże się z nią jakieś IO. Może część dysku, może rejestr sprzętu na urządzeniu peryferyjnym itp.

Podobnie, tablice bitów (i ogólnie tablice) należą do tego: każdy indeks ma z nim powiązany jeden element (w danym momencie), więc tablica jest faktycznie kodowaniem funkcji w domenie skończonej.
W programowaniu funkcjonalnym i pochodnych (takich jak MapReduce) mapa odnosi się do zastosowania transformacji w strukturze.

Oryginał mappochodzi z Lispa, w którym odwoływał się do funkcji, która wzięła inną funkcję i listę, i zwrócił wynik zastosowania funkcji do każdego elementu tej listy.

Ale to zjawisko jest dość ogólne. W Haskell struktura danych, która dopuszcza taką operację, nazywa się funktorem , a operacja nazywa się fmap (ze względów historycznych, aby uniknąć konfliktów z mapą listy).

Wszystkie one są powiązane poprzez koncepcję Functora z teorii kategorii, która jest abstrakcją struktur dopuszczających operację „mapy”.

jmite
źródło

(Literówka w Functornazwie linku - za mało, by sugerować edycję).

Mat.

Bardzo jasne i doskonałe wyjaśnienie. Nie rozumiałem jednak, co oznacza „funkcja skończona”.

Kais

@Kais „funkcja skończona” jest najczęściej używana dla funkcji, dla której żaden element nie jest odwzorowany na nieskończoność. Wydaje mi się, że jmite chciał podkreślić, że tablice są w zasadzie funkcjami odwzorowującymi zestaw (prawidłowych) indeksów na zawarte wartości.

Michael Hoff,

Te dwa zastosowania są tak naprawdę tylko aspektami tego samego. mapZwraca wynik w której każdy element jest powiązany z odpowiednim elementem na wejściu. Różnica polega na tym, że pierwsze użycie opisuje istniejącą relację, a drugie odnosi się do operacji, która tworzy relację.

Barmar

Literówka

Barmar

W dalszej części będę mniej niż dokładny na wiele sposobów, poświęcając techniczną dokładność, aby zapewnić podstawowe zrozumienie. Oczywiste jest, że zapoznałeś się z wieloma źródłami technicznymi, a sama techniczność materiału utrudnia zrozumienie, co jest dość podstawową i prostą koncepcją.

Mówiąc najprościej, najczęstszym zastosowaniem mapy słów jest opisanie związku między rzeczami w dwóch różnych zestawach. Może to być funkcja matematyczna lub inny rodzaj reprezentacji i mechanizmu. Najczęstszą, która przychodzi mi na myśl, jest mapa ulic.

Mapa ulic jest obrazem konkretnego terenu lub obszaru w prawdziwym świecie, w którym linie, rysunki i słowa zapisane na mapie odpowiadają rzeczywistym ulicom i budynkom. Istnieje relacja jeden do jednego między reprezentacją terenu przedstawioną na mapie ulic a rzeczywistym terenem.

Patrząc dalej, możemy również zobaczyć, że mapa ulic reprezentuje rzeczywisty teren. Rzeczywisty teren ma obiekty i szczegóły oraz dynamiczne procesy, których mapa ulic nie przedstawia. Mapa ulic jest abstrakcyjnym przedstawieniem rzeczywistego terenu, a to, co jest przedstawione na mapie ulic, jest tylko tym, co jest potrzebne do spełnienia jej celu, aby zapewnić pomoc nawigacyjną na prawdziwym terenie.

Wiele przykładów w pytaniu dotyczy utworzenia reprezentacji z mechanizmami pomocniczymi, aby osoba mogła korzystać z reprezentacji, a mechanizm tłumaczy działania tej osoby na to, co jest potrzebne do podstawowej funkcjonalności, która jest ukryta przez fasadę reprezentacji.

Plik we / wy mapowany w pamięci pozwala programistom myśleć o pliku jako dużym obszarze pamięci, aby użyć reprezentacji pamięci rzeczywistego pliku. Programista nie uważa pliku za plik, ale zamiast tego myśli o nim jako o dużym obszarze pamięci. Funkcja We / Wy pliku odwzorowanego na pamięć zapewnia, że gdy programista odwołuje się do określonego przesunięcia pamięci, uzyskuje się dostęp do odpowiednich danych w pliku.

Urządzenie we / wy mapowane na pamięć pozwala uprościć interfejs programowania urządzenia poprzez zapis do adresów pamięci lub odczyt z adresów pamięci. Te operacje zapisu i odczytu są tłumaczone przez podstawową funkcjonalność urządzenia we / wy mapowanego na pamięć na konkretne działania specyficzne dla urządzenia potrzebne do przeprowadzenia żądanej usługi lub akcji.

Mapa bitowa to zestaw bitów, które zapewniają zgodność jeden do jednego z wartościami innego zestawu. Na przykład CreateFile()funkcja Win32 API ma kilka argumentów mapy bitowej, które są używane do wskazywania różnego rodzaju atrybutów pliku. Określone bity w mapie bitowej odpowiadają konkretnemu zachowaniu pliku, np. „Otwórz jako tylko do odczytu” lub „Zawsze twórz nowy pusty plik”. Zapewnione są specjalne stałe, które są łączone za pomocą binarnych operacji bitowych w celu określenia rzeczywistych argumentów. Zobacz funkcję CreateFile i przykładowy kod źródłowy przy otwieraniu pliku do odczytu lub zapisu .

Richard Chambers
źródło

Świetne wyjaśnienie. Jednak jeśli chodzi o Memory mapped file I/O, czy jest to alternatywa dla standardowych plików we / wy (fopen, fgetc ..)? czy przewaga wydajności wynika z faktu, że dostęp do pamięci RAM jest szybszy w porównaniu do dysków?

Kais

@Kais Memory Mapped File I / O (MMF) jest alternatywą dla standardowych wywołań API plików. Korzystanie z MMF może, ale nie musi, być zaletą wydajności. To naprawdę zależy od tego, jak dobrze mechanika MMF pasuje do sposobu korzystania z zawartości pliku, a także od wielkości pliku. MMF I / O stronicuje obszary pliku do pamięci w dużych blokach. Możesz zrobić coś podobnego z interfejsem API plików i zrobić znaczącą różnicę w wydajności. W przypadku standardowych interfejsów API we / wy do plików często dochodzi do kopiowania między buforami pamięci z przestrzeni jądra do przestrzeni użytkownika, która jest często omijana przez MMF.

Richard Chambers

@ Kais nie jestem pewien, o co pytasz. Kopiowanie danych z jednej lokalizacji pamięci do drugiej wymaga czasu i cykli procesora, więc zmniejszenie kopiowania danych poprawia wydajność podczas uzyskiwania dostępu do danych. Plik I / O jest ogólnego przeznaczenia i wewnętrznie wykonuje własne buforowanie i stronicowanie zawartości pliku, jednak zwykle rozmiar buforów pamięci jest mniejszy niż w przypadku I / O pliku mapowanego do pamięci. Interfejs API pliku ma tendencję do faworyzowania we / wy małych porcji, a nie dużych bloków. Dostęp sekwencyjny jest zwykle preferowany, gdy spojrzy się na stos plików I jądra i jądro.

Richard Chambers

@Kais, więc jeśli możesz podpowiedzieć do interfejsu API we / wy pliku, możesz poprawić wydajność aplikacji korzystającej z interfejsu API we / wy pliku, gdy we / wy pliku jest wąskim gardłem w wydajności. Korzystanie z operacji we / wy pliku odwzorowanego w pamięć może również pomóc, zwłaszcza w przypadku sekwencyjnego dostępu i operacji, które mieszczą się w jednym rozmiarze strony MMF. Zobacz materiały i linki pod tym adresem URL na temat niskiego poziomu We / Wy z GNU C gnu.org/software/libc/manual/html_node/…, który opisuje niektóre mechanizmy niższego poziomu GNU.

Richard Chambers

@Kais Zauważyłem znaczną poprawę wydajności dzięki API standardowej biblioteki plików C, używając tej setbuf()funkcji do ustawienia dużego bufora we / wy pliku. Wszystko, co możesz zrobić, aby ograniczyć dostęp do urządzenia pamięci masowej, zwykle stanowi bonus. W przypadku napędów dyskowych zmniejszenie liczby wyszukiwań może mieć dużą różnicę, jednak istnieje wiele czynników, na które niewiele można poradzić, na przykład sposób organizacji danych na talerzach, prędkość obrotowa talerzy, prędkość ruchu głowy, buforowanie dane, jak dobrze trafienia w pamięci podręcznej zmniejszają przechodzenie na dysk elektromechaniczny itp.

Richard Chambers

Mapowanie to po prostu proces kojarzenia jednej jednostki danych z inną jednostką danych. Celem mapowania jest umożliwienie uproszczonego dostępu do mapowanych danych. Na przykład w klasycznych systemach kompatybilnych z IBM adres pamięci 0xB8000 został zmapowany na pamięć wideo karty graficznej. Zapis do tej pamięci zaktualizowałby zawartość ekranu, a odczytanie z niej spowodowałoby odzyskanie zawartości ekranu. Mapowanie plików, mapowanie urządzeń, a nawet mapowanie struktury danych (zwykle nazywane Mapą, HashMapą lub Słownikiem), wszystkie sposoby kojarzenia jednej jednostki danych z inną jednostką danych.

Mapowanie ma dwie podstawowe zalety. Po pierwsze, mapowanie zmniejsza złożoność dostępu do powiązanego urządzenia lub pliku. Na przykład mapowanie plików i mapowanie urządzeń pozwala traktować te urządzenia tak, jakby były zwykłą pamięcią. Zamiast uczyć się różnych portów I / O, poleceń danych itd., Otrzymujesz jeden prosty interfejs, który jest tak naturalny i oczywisty jak zapis do pamięci RAM.

Drugą korzyścią jest to, że może zmniejszyć wymagania dotyczące pamięci. Na przykład, a Map<Integer, SomeDataType>może wytworzyć „rzadką tablicę”, która jest użyteczna tam, gdzie potrzebna jest tablica, która zawiera głównie nieprawidłowe / nieużywane dane, i można uzyskać do niej dostęp w czasie prawie liniowym. Może to być znacznie bardziej wydajne niż lista połączona (gdzie dostęp do n-tego elementu zajmuje O ( n ) ).

Mapowanie jest przede wszystkim używane jako abstrakcja, aby ukryć skomplikowane algorytmy / funkcje przed deweloperem, aby mogli skupić się na zadaniu wdrożenia programu. Należy pamiętać, że mapowanie nie zawsze jest tak wydajne pod względem czasu przetwarzania, jak bezpośredni dostęp do urządzenia lub pliku, ale zawsze jest mniej skomplikowane niż to (np. Mapowanie zmniejsza ilość specjalistycznego kodu, który programista musi napisać, aby uzyskać dostęp do danych ).

phyrfox
źródło

Dziękuję za wyjaśnienie. Jednak nie rozumiałem, co oznacza „rzadka tablica” i jak jest bardziej wydajna.

Kais

@Kais Rzadka tablica to lista składająca się głównie z zerowych wartości. Zamiast zapisywać wszystkie wartości w pamięci, rzadka tablica przechowuje tylko niezerowe wartości w pamięci. Dzięki temu jest bardziej wydajne niż zwykłe przydzielanie całej pamięci na raz. Rzadkie tablice powinny zazwyczaj być w około 75% puste, aby zaoszczędzić miejsce. Pamięć wirtualna często działa również w ten sposób, gdy system operacyjny przechowuje tylko „brudne” strony pamięci, a także systemy plików, które pozwalają przechowywać tylko sektory o wartościach niezerowych.

phyrfox