Apa yang dimaksud dengan "peta"?

10

Saya telah menemukan istilah ini berkali-kali, dalam berbagai materi pendidikan CS:

  1. L2 CS162 (UC Berkeley):

    I / O yang dipetakan dengan memori

  2. L4 CS162 (UC Berkeley):

    Memori memetakan file

  3. L24 CS61 (UC Berkeley):

    "Memori yang dipetakan I / O": Kontrol perangkat / register data dipetakan ke ruang alamat CPU

  4. Bahkan, setelah googling "pemetaan", saya mendapatkan artikel Map_ (fungsi-urutan lebih tinggi) , tetapi tidak terlalu jelas bagi saya.
  5. Terlebih lagi, cobalah memahami maknanya dalam konteks bitmapdengan membaca artikel Wikipedia :

    Array bit adalah pemetaan dari beberapa domain (hampir selalu rentang bilangan bulat) ke nilai dalam set {0, 1}

    Saya tidak yakin, tetapi dalam konteks di atas, ini terdengar bagi saya tentang konversi data.

  6. Kemudian setelah membaca buku CS, saya hanya menemukan paragraf ini tetapi tidak menjelaskan arti "pemetaan" bagi saya:

    Memory Mapping Linux (bersama dengan bentuk Unix lainnya) menginisialisasi konten area memori virtual dengan mengaitkannya dengan objek pada disk, proses yang dikenal sebagai pemetaan memori.

  7. Saya mendapat MapReduce sebagai hasil pencarian: di mana peta dijelaskan sebagai "idiom dalam komputasi paralel di mana operasi sederhana diterapkan ke semua elemen dari suatu urutan, berpotensi paralel".

Saya masih bingung dengan istilah itu. Adakah yang bisa menjelaskan apa arti "peta" dalam konteks yang saya sebutkan?

Kais
sumber

Jawaban:

14

Jadi, ada dua penggunaan kata "peta" yang berbeda, yang akan saya buka di sini.

  1. Yang pertama sangat umum, di mana peta berarti "untuk bergaul," terutama melalui suatu fungsi. Jika kita mengatakan " memetakan setiap menjadi ", maka kita mengatakan .x 2 x x . f ( x ) = 2 xfx2xx.f(x)=2x

    Penggunaan ini termasuk "memori yang dipetakan IO:" ada fungsi (konseptual) yang menghubungkan setiap bagian memori dengan tindakan IO tertentu. Tidak ada yang benar-benar pernah menulis fungsi, tetapi memang ada: untuk setiap bagian dari memori yang dipetakan, ada beberapa IO yang terkait dengannya. Mungkin bagian dari disk, mungkin register perangkat keras pada periferal, dll.

    Demikian juga, bit array (dan array secara umum) termasuk dalam hal ini: setiap indeks memiliki elemen tunggal yang terkait dengannya (pada waktu tertentu), sehingga sebuah array secara efektif merupakan pengkodean fungsi domain-terbatas.

  2. Dalam pemrograman fungsional dan turunannya (seperti MapReduce), peta mengacu pada penerapan transformasi melintasi struktur.

    Sumber asli mapberasal dari Lisp, di mana ia merujuk ke fungsi yang mengambil fungsi lain dan daftar, dan mengembalikan hasil penerapan fungsi ke setiap elemen daftar itu.

    Tapi, fenomena ini cukup umum. Di Haskell, struktur data yang mengakui operasi seperti itu disebut functor , dan operasi itu disebut fmap (karena alasan historis, untuk menghindari konflik dengan daftar peta).

    Ini semua terkait melalui konsep Functor dari teori kategori, yang merupakan abstraksi struktur yang mengakui operasi "peta".

Ya ampun
sumber
4
(Mengetik dalam Functornama tautan - terlalu sedikit untuk menyarankan suntingan.)
Mat
Penjelasan yang sangat jelas dan bagus. Namun saya tidak mengerti apa yang dimaksud dengan 'fungsi terbatas'.
Kais
1
@Kais 'fungsi terbatas' paling umum digunakan untuk fungsi yang tidak ada elemen yang dipetakan hingga tak terbatas. Saya kira jmite ingin menyoroti bahwa array pada dasarnya adalah fungsi memetakan set indeks (valid) dengan nilai yang terkandung.
Michael Hoff
2
Kedua kegunaan ini benar-benar hanya aspek dari hal yang sama. The mapfungsi mengembalikan hasil di mana setiap elemen dikaitkan dengan sesuai unsur input. Perbedaannya adalah bahwa penggunaan pertama menggambarkan hubungan yang ada, sedangkan yang kedua merujuk pada operasi yang menciptakan hubungan.
Barmar
1
Typo: Fucntor
Barmar
8

Berikut ini saya akan kurang akurat dalam beberapa cara, mengorbankan akurasi teknis untuk memberikan pemahaman dasar. Jelas bahwa Anda telah membaca sejumlah sumber teknis dan sangat teknisnya bahan tersebut membuat Anda sulit untuk memahami apa itu konsep yang cukup mendasar dan sederhana.

Secara sederhana penggunaan kata peta yang paling umum adalah untuk menggambarkan hubungan antara hal-hal dalam dua set yang berbeda. Ini mungkin fungsi matematika atau mungkin semacam representasi dan mekanisme lain. Yang paling umum yang langsung terlintas dalam pikiran adalah peta jalan.

Peta jalan adalah gambar medan atau area tertentu di dunia nyata di mana garis-garis dan gambar serta kata-kata yang tertulis di peta sesuai dengan jalan dan bangunan fisik aktual. Ada hubungan satu ke satu antara representasi medan yang digambarkan dalam peta jalan dan medan yang sebenarnya.

Melihat lebih jauh kita juga dapat melihat bahwa peta jalan adalah representasi dari medan yang sebenarnya. Medan sebenarnya memiliki objek dan detail serta proses dinamis yang tidak digambarkan oleh peta jalan. Peta jalan adalah representasi abstrak dari medan yang sebenarnya dan apa yang digambarkan dalam peta jalan hanya apa yang diperlukan untuk memenuhi tujuannya, untuk menyediakan bantuan navigasi untuk medan yang sebenarnya.

Sejumlah contoh dalam pertanyaan melibatkan pembuatan representasi dengan mekanisme pendukung sehingga seseorang dapat menggunakan representasi dan mekanisme menerjemahkan tindakan seseorang ke dalam apa yang diperlukan untuk fungsi dasar yang tersembunyi oleh fasad representasi.

Memori yang dipetakan file I / O memungkinkan seorang programmer untuk memikirkan file sebagai area memori yang besar, untuk menggunakan representasi memori dari file nyata. Programmer tidak menganggap file sebagai file tetapi sebaliknya menganggapnya sebagai area memori yang besar. Fungsionalitas file I / O file yang dipetakan berhati-hati untuk memastikan bahwa ketika programmer referensi memori tertentu mengimbangi bahwa data yang sesuai dalam file tersebut diakses.

Perangkat yang dipetakan dengan memori I / O memungkinkan antarmuka pemrograman perangkat disederhanakan dengan menulis ke alamat memori atau membaca dari alamat memori. Tindakan menulis dan membaca ini diterjemahkan oleh fungsi I / O yang dipetakan di memori bawah ke dalam tindakan spesifik perangkat yang sebenarnya diperlukan untuk melakukan layanan atau tindakan yang diminta.

Peta bit adalah sekumpulan bit yang menyediakan korespondensi satu ke satu dengan nilai dari beberapa set lainnya. Misalnya CreateFile()fungsi Win32 API memiliki beberapa argumen peta bit yang digunakan untuk menunjukkan berbagai jenis atribut file. Bit spesifik dalam peta bit berhubungan dengan perilaku file tertentu seperti "Buka hanya Baca" atau "Selalu Buat File Kosong Baru". Konstanta khusus disediakan yang digabungkan menggunakan operasi bit biner untuk menentukan argumen yang sebenarnya. Lihat fungsi CreateFile dan contoh kode sumber di Membuka File untuk Membaca atau Menulis .

Richard Chambers
sumber
Penjelasan yang bagus. Namun mengenai Memory mapped file I/O, apakah itu alternatif untuk file standar i / o (fopen, fgetc ..)? Apakah keunggulan kinerja karena sifat akses RAM yang lebih cepat dibandingkan dengan Disk?
Kais
1
@Kais Memory Mapped File I / O (MMF) adalah alternatif untuk menggunakan panggilan API file standar. Mungkin ada atau mungkin tidak ada keuntungan kinerja untuk menggunakan MMF. Itu benar-benar tergantung pada seberapa baik mekanisme MMF cocok dengan cara Anda menggunakan konten file serta seberapa besar file tersebut. MMF I / O halaman area file ke memori dalam blok besar. Anda dapat melakukan sesuatu yang mirip dengan file API dan membuat perbedaan kinerja yang signifikan. Dengan file standar API I / O cenderung ada banyak penyalinan antara buffer memori dari ruang kernel ke ruang pengguna yang sering dilewati dengan MMF.
Richard Chambers
1
@Kais tidak yakin dengan apa yang Anda minta. Menyalin data dari satu lokasi memori ke lokasi lain membutuhkan waktu dan siklus CPU sehingga mengurangi penyalinan data meningkatkan kinerja saat mengakses data. File I / O adalah tujuan umum dan secara internal melakukan caching dan paging konten file sendiri tetapi biasanya ukuran buffer memori lebih kecil dari apa yang digunakan dengan Memory Iapped O / O File. API file cenderung berorientasi ke arah I / O yang mendukung potongan kecil daripada blok besar. Akses berurutan cenderung disukai dengan melihat ke depan di dalam file I / O stack dan kernel.
Richard Chambers
1
@Kais jadi jika Anda dapat memberikan petunjuk untuk file I / O API maka Anda dapat meningkatkan kinerja aplikasi Anda yang menggunakan file I / O API ketika file I / O adalah hambatan kinerja. Dan menggunakan Memory Mapped File I / O juga dapat membantu terutama dengan sebagian besar akses berurutan dan operasi yang berada dalam ukuran halaman MMF tunggal. Lihat bahan dan tautan di URL ini tentang I / O tingkat rendah dengan GNU C gnu.org/software/libc/manual/html_node/… yang menjelaskan beberapa mekanisme tingkat rendah GNU.
Richard Chambers
1
@Kais Saya telah melihat peningkatan kinerja yang signifikan dengan file API C Library Standard dengan menggunakan setbuf()fungsi untuk mengatur file I / O buffer yang besar. Apa pun yang dapat Anda lakukan untuk mengurangi mengakses perangkat penyimpanan cenderung menjadi bonus. Untuk disk drive, mengurangi jumlah pencarian dapat membuat perbedaan besar, namun ada sejumlah pengaruh yang tidak dapat Anda lakukan seperti bagaimana data disusun pada piringan disk, kecepatan rotasi piringan, kecepatan gerakan kepala, cache dari data, seberapa baik hit cache mengurangi ke disk elektro-mekanis, dll.
Richard Chambers
1

Pemetaan hanyalah proses mengaitkan satu unit data dengan unit data lainnya. Maksud pemetaan adalah untuk memungkinkan akses yang disederhanakan ke data yang dipetakan. Misalnya, dalam sistem yang kompatibel dengan IBM klasik, alamat memori 0xB8000 dipetakan ke memori video dari kartu video. Menulis ke memori ini akan memperbarui konten layar, dan membaca darinya akan mengambil konten layar. Pemetaan file, pemetaan perangkat, dan bahkan pemetaan struktur data (biasanya disebut Peta, HashMap, atau Kamus), adalah semua cara mengaitkan satu unit data dengan unit data lainnya.

Pemetaan memiliki dua manfaat utama. Yang pertama adalah pemetaan mengurangi kompleksitas mengakses perangkat atau file terkait. Misalnya, pemetaan file dan pemetaan perangkat memungkinkan Anda untuk memperlakukan perangkat tersebut seolah-olah itu hanya memori biasa. Alih-alih mempelajari berbagai port I / O, perintah data, dan sebagainya, Anda mendapatkan satu antarmuka sederhana yang sama alami dan sejelas menulis ke RAM.

Manfaat kedua adalah dapat mengurangi kebutuhan memori. Sebagai contoh, a Map<Integer, SomeDataType>dapat menghasilkan "array jarang", yang berguna jika Anda menginginkan array yang sebagian besar akan berisi data yang tidak valid / tidak digunakan, dan dapat diakses dalam waktu dekat-linear. Ini bisa jauh lebih efisien daripada daftar yang ditautkan (yang membutuhkan O ( n ) waktu untuk mengakses elemen ke- n ).

Pemetaan terutama digunakan sebagai abstraksi untuk menyembunyikan algoritme / fungsi rumit dari pengembang sehingga mereka dapat fokus pada tugas mengimplementasikan program. Perhatikan bahwa pemetaan mungkin tidak selalu efisien, dalam hal waktu pemrosesan, seperti mengakses perangkat atau file secara langsung, tetapi selalu lebih mudah daripada melakukan hal itu (misalnya pemetaan mengurangi jumlah kode khusus yang harus ditulis pengembang untuk mengakses data ).

phyrfox
sumber
Terima kasih untuk penjelasannya. Namun saya tidak mengerti apa arti "jarang array", dan bagaimana itu lebih efisien.
Kais
@ Kais Larik jarang adalah daftar yang sebagian besar terdiri dari nilai nol. Alih-alih menyimpan semua nilai dalam memori, array jarang hanya menyimpan nilai-nilai yang tidak nol dalam memori. Dengan melakukan ini, ini lebih efisien daripada hanya mengalokasikan semua memori sekaligus. Array jarang biasanya sekitar 75% kosong agar menghemat ruang. Memori virtual sering bekerja dengan cara ini juga, di mana OS hanya menyimpan halaman "kotor" memori, serta sistem file yang memungkinkan Anda untuk hanya menyimpan sektor-sektor nilai-nilai non-nol.
phyrfox