Speicherzuordnung

11

Sie entwerfen eine neue esoterische Programmiersprache und eine Funktion, die Sie hinzufügen möchten, ist ein dynamischer Speicherzuweiser. Ihre Sprache gibt einen speziellen dedizierten virtuellen Adressraum für den Programmraum des Benutzers an. Dies ist getrennt von dem Adressraum, der vom Speicherzuweiser für einen internen Status verwendet wird.

Um die Kosten für die Verteilung Ihrer Implementierung zu senken, muss der Code so klein wie möglich sein.

Schnittstelle

Sie müssen drei Funktionen bereitstellen: Initialisierung, Zuweisung und Freigabe.

Initialisierung

Diese Funktion verwendet einen einzelnen positiven ganzzahligen Parameter N. Dies bedeutet, dass das Programm eines Benutzers NBytes in seinem Adressraum hat, aus denen N-1Bytes zum Zuweisen von Speicher vorhanden sind . Die Adresse 0ist für "null" reserviert.

Es ist garantiert, dass diese Funktion genau einmal aufgerufen wird, bevor Allokations- / Freigabeaufrufe ausgeführt werden.

Beachten Sie, dass diese Funktion keinen physischen Speicher für den virtuellen Adressraum des Benutzerprogramms zuweisen muss. Sie erstellen im Grunde das "Look and Feel" eines hohlen Speicherzuweisers.

Zuweisen

Die Zuweisungsfunktion muss eine Anforderung der Anzahl der zuzuweisenden Speicherbytes entgegennehmen. Die Eingabe ist garantiert positiv.

Ihre Funktion muss eine ganzzahlige Adresse an den Anfang des zugewiesenen Blocks zurückgeben oder 0angeben, dass kein zusammenhängender Block der angeforderten Größe verfügbar ist. Wenn ein zusammenhängender Block der verfügbaren Größe irgendwo im Adressraum verfügbar ist, müssen Sie ihn zuweisen!

Sie müssen sicherstellen, dass sich keine zwei zugewiesenen Blöcke überlappen.

Freigeben

Die Freigabefunktion muss eine Adresse für den Start eines zugewiesenen Blocks annehmen und kann optional auch die Größe des angegebenen Blocks annehmen.

Der freigegebene Speicher steht wieder zur Zuweisung zur Verfügung. Es wird angenommen, dass die Eingabeadresse eine gültige Adresse ist.

Beispiel für eine Python-Implementierung

Beachten Sie, dass Sie eine beliebige Methode wählen können, um den internen Status zu verfolgen. In diesem Beispiel verfolgt die Klasseninstanz dies.

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]

Wertung

Das ist Code Golf; Der kürzeste Code in Bytes gewinnt. Sie müssen sich keine Sorgen machen, dass Ihnen der Speicher für einen von Ihrem Allokator benötigten internen Status ausgeht.

Es gelten Standardschlupflöcher.

Bestenliste

Code-Snippet anzeigen

code-golf helloworld922
quelle
3
Ich bezweifle, dass Python-Listen genau ein Byte pro Element belegen. Muss der "zugewiesene Speicher" in Bytes angegeben werden, oder kann es sich nur um den "generischen Array- / Listentyp Ihrer Sprache" handeln?
Türknauf
4
Es ist keine tatsächliche Zuordnung erforderlich (außer für die interne Statusverfolgung, die sich in einem eigenen virtuellen Adressraum befindet). Sie geben nur Ganzzahlen an einen abstrakten endlichen virtuellen Adressraum zurück.
helloworld922
To help reduce the cost of distributing your implementation the size of the code must be as small as possibleoder könnte es so effizient wie möglich sein (klein und effizient sind nicht dasselbe)? : D
The Coder
Huh, Sprachdesign ?
Akangka
Während diese Herausforderung mit einem Hintergrund für das Sprachdesign motiviert ist, ist das Entwerfen einer Sprache nicht Teil der Aufgabe (sondern das Implementieren von Teilen einer Sprache), daher habe ich das Tag entfernt.
Martin Ender

Antworten:

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}

Wie die Antwort von MegaTom, verwendet jedoch eine Zeichenfolge anstelle eines Arrays zum Speichern des Status. Das Zeichen "o" bezeichnet eine offene Zelle, während ein "f" eine gefüllte Zelle bezeichnet. Auf diese Weise können wir Rubys relativ knappe Funktionen zur Manipulation von Saiten verwenden:

?o*n Initialisiert eine Zeichenfolge von n "o".

/\B#{?o*n}/ist ein regulärer Ausdruck, der mit n aufeinanderfolgenden "o" übereinstimmt und das erste Zeichen nicht enthält. sub!ersetzt die erste Übereinstimmung durch n "f".

"#$`" Gibt die Zeichenfolge links von der Übereinstimmung oder eine leere Zeichenfolge an, wenn keine Übereinstimmung vorhanden war. Die Größe ist also entweder der zugewiesene Index oder 0.

Deallocate setzt nur den angegebenen Abschnitt der Zeichenfolge auf "o" zurück.

Histokrat
quelle
4

JavaScript (ES6), 88

Verwenden einer globalen Variablen _(eines sehr spärlichen Arrays), um den Überblick zu behalten.

Wie könnte ich es jetzt testen?

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
quelle
3

Ruby, 135

Hat ein globales Array, um zu verfolgen, ob jede Zelle zugeordnet ist oder nicht.

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
quelle
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~{#,_};)&

nSpeichern Sie die Gesamtgröße, lspeichert den internen Status. Der Allokator versucht, direkt hinter einem anderen Abschnitt des zugewiesenen Speichers zuzuweisen.

njpipeorgan
quelle