Memory Allocator

11

Anda sedang mendesain bahasa pemrograman esoterik baru dan satu fitur yang Anda putuskan untuk ditambahkan adalah pengalokasi memori dinamis. Bahasa Anda menentukan ruang alamat virtual khusus khusus untuk ruang program pengguna. Ini terpisah dari ruang alamat yang digunakan oleh pengalokasi memori untuk kondisi internal apa pun.

Untuk membantu mengurangi biaya distribusi implementasi Anda, ukuran kode harus sekecil mungkin.

Antarmuka

Anda harus menyediakan tiga fungsi: inisialisasi, mengalokasikan, dan membatalkan alokasi.

Inisialisasi

Fungsi ini mengambil parameter integer positif tunggal N. Ini berarti program pengguna memiliki Nbyte di ruang alamatnya dari mana ada N-1byte untuk mengalokasikan memori. Alamat 0dicadangkan untuk "null".

Dijamin bahwa fungsi ini akan dipanggil tepat satu kali sebelum mengalokasikan / membatalkan alokasi panggilan.

Perhatikan bahwa fungsi ini tidak perlu mengalokasikan memori fisik apa pun untuk ruang alamat virtual program pengguna; Anda pada dasarnya menciptakan "tampilan dan nuansa" dari pengalokasi memori kosong.

Alokasikan

Fungsi pengalokasian harus menerima permintaan jumlah byte memori yang akan dialokasikan. Masukan dijamin positif.

Fungsi Anda harus mengembalikan alamat integer ke awal blok yang dialokasikan, atau 0untuk menunjukkan bahwa tidak ada blok yang berdekatan dari ukuran yang diminta tersedia. Jika blok yang berdekatan dari ukuran yang tersedia tersedia di mana saja di ruang alamat Anda harus mengalokasikan!

Anda harus memastikan bahwa tidak ada dua blok yang dialokasikan tumpang tindih.

Deallocate

Fungsi deallocate harus mengambil alamat awal blok yang dialokasikan, dan secara opsional juga dapat mengambil ukuran blok yang diberikan.

Memori yang telah dibatalkan alokasi tersedia lagi untuk alokasi. Diasumsikan bahwa alamat input adalah alamat yang valid.

Contoh implementasi Python

Perhatikan bahwa Anda dapat memilih metode apa pun untuk melacak keadaan internal; dalam contoh ini instance kelas melacaknya.

class myallocator:
    def __init__(self, N):
        # address 0 is special, it's always reserved for null
        # address N is technically outside the address space, so use that as a
        # marker
        self.addrs = [0, N]
        self.sizes = [1, 0]

    def allocate(self, size):
        for i,a1,s1,a2 in zip(range(len(self.addrs)),
                                 self.addrs[:-1], self.sizes[:-1],
                                 self.addrs[1:]):
            if(a2 - (a1+s1) >= size):
                # enough available space, take it
                self.addrs.insert(i+1, a1+s1)
                self.sizes.insert(i+1, size)
                return a1+s1
        # no contiguous spaces large enough to take our block
        return 0

    def deallocate(self, addr, size=0):
        # your implementation has the option of taking in a size parameter
        # in this implementation it's not used
        i = self.addrs.index(addr)
        del self.addrs[i]
        del self.sizes[i]

Mencetak gol

Ini adalah kode golf; kode terpendek dalam byte menang. Anda tidak perlu khawatir kehabisan memori untuk kondisi internal apa pun yang diperlukan oleh pengalokasi Anda.

Lubang loop standar berlaku.

Papan peringkat

Tampilkan cuplikan kode

code-golf helloworld922
sumber
3
Saya ragu daftar Python mengambil tepat satu byte per elemen. Apakah "memori yang dialokasikan" harus dalam byte, atau dapatkah itu hanya "tipe array / daftar generik bahasa Anda"?
Gagang Pintu
4
Tidak diperlukan alokasi aktual (kecuali untuk apa pun yang Anda inginkan untuk pelacakan keadaan internal, yang berada pada ruang alamat virtualnya sendiri); Anda hanya mengembalikan bilangan bulat ke beberapa ruang alamat virtual terbatas abstrak.
helloworld922
To help reduce the cost of distributing your implementation the size of the code must be as small as possibleatau mungkinkah efisien (kecil dan efisien tidak sama) mungkin? : D
The Coder
Huh, desain bahasa ?
Akangka
Sementara tantangan ini dimotivasi dengan latar belakang desain bahasa, mendesain bahasa sebenarnya bukan bagian dari tugas (melainkan mengimplementasikan bagian dari satu), jadi saya telah menghapus tag.
Martin Ender

Jawaban:

4

Ruby, 80

i,a,d=->n{$m=?o*n},->n{$m.sub!(/\B#{?o*n}/,?f*n);"#$`".size},->n,s{$m[n,s]=?o*s}

Seperti jawaban MegaTom, tetapi gunakan string daripada array untuk menyimpan status. Karakter "o" menunjukkan sel terbuka, sedangkan "f" menunjukkan sel terisi. Ini memungkinkan kita menggunakan fungsi manipulasi string Ruby yang relatif singkat:

?o*n menginisialisasi string n "o" s.

/\B#{?o*n}/adalah ekspresi reguler yang cocok dengan "o" berturut-turut yang tidak termasuk karakter pertama. sub!mengganti kecocokan pertama dengan n "f" s.

"#$`" memberikan string ke kiri pertandingan, atau string kosong jika tidak ada pertandingan, sehingga ukurannya adalah indeks yang dialokasikan atau 0.

Deallocate hanya mengatur bagian yang ditunjuk dari string kembali ke "o".

histokrat
sumber
4

JavaScript (ES6), 88

Menggunakan variabel global _( array yang sangat jarang) untuk melacak.

Sekarang bagaimana saya bisa mengujinya?

I=n=>(_=[1],_[n]=0)
A=n=>_.some((x,i)=>i-p<n?(p=i+x,0):_[p]=n,p=1)?p:0
D=p=>delete _[p]
edc65
sumber
3

Ruby, 135

Memiliki susunan global melacak apakah setiap sel dialokasikan atau tidak.

i=->n{$a=[!0]*n;$a[0]=0}
a=->n{s=$a.each_cons(n).to_a.index{|a|a.none?};n.times{|i|$a[s+i]=0}if s;s||0}
d=->s,n{n.times{|i|$a[s+i]=!0}}
MegaTom
sumber
1

Mathematica, 152

i=(n=#;l={{0,1},{#,#}};)&
a=If[#=={},0,l=l~Join~#;#[[1,1]]]&@Cases[l,{Except@n,e_}:>{e,e+#}/;Count[l,{a_,_}/;e<=a<e+#]<1,1,1]&
d=(l=l~DeleteCases~{#,_};)&

nmenyimpan ukuran total, lmenyimpan keadaan internal. Pengalokasi akan mencoba mengalokasikan tepat di belakang bagian lain dari memori yang dialokasikan.

njpipeorgan
sumber