Effizientes veränderbares Byte-Array in nativem Lua

Ich versuche, eine effiziente Implementierung eines LZ77-Decoders in nativem Lua zu machen (d. H. Keine C-Bibliothek und keine Abhängigkeiten von Nichtkern-Lua-Bibliotheken) - siehe liblzg.Effizientes veränderbares Byte-Array in nativem Lua

Zum Laden und Analysieren der Binärdatei funktioniert eine Lua-Zeichenfolge perfekt und mit guter Leistung (z. B. mit der s: byte (k) -Methode). Zum Erzeugen der decodierten Ausgabedaten sind Zeichenfolgen jedoch nicht sehr optimal, da sie unveränderlich sind und die Verkettung von Zeichenfolgen viel Zeit in Anspruch nimmt, wenn die Ausgabe groß wird.

Der Decoder muss in der Lage:

Append einen Byte an den Ausgang zu einem Zeitpunkt (bis zu Millionen mal)
Read (mehr oder weniger Zufallszugriff) von dem Ausgangspuffer

Was sind die besten Optionen? Die Größe der Ausgabedaten ist vorher bekannt, daher kann sie vorab zugewiesen werden.

Quelle

2010-11-24 marcus256

Aus Neugier, warum nicht können Sie die C-Bibliothek verwenden? Ist das eine Lernübung oder wird es in einer Sandbox-Lua-Umgebung benötigt? –

Es ist eher eine lehrreiche Übung (ich möchte die Leistung sehen und wie sich die Techniken zwischen einer kompilierten Sprache und einer verwalteten Skriptumgebung unterscheiden). Außerdem stelle ich mir vor, dass eine reine Lua-Implementierung die Bereitstellung viel einfacher macht. – marcus256

Perfekte Frage. Übrigens bin ich nicht der Einzige, der die gleiche Idee hatte – Hydro

Klingt wie ein perfekter Job für table.concat Ihren Ausgang ist nur eine Tabelle von Bytes.

Wenn Sie kopieren müssen, tun Sie es so, wie Sie es normalerweise für eine Tabelle tun würden. zB:

for i=#output-5,9 do output[#output+1]=output[i] end

Wenn Sie schließlich mit dem Ausgangsstrom fertig sind, wandeln es in einen String mit str=table.concat(output)

Quelle

2010-11-24 18:52:55 daurnimator

Was ist der Leistungsnachteil einer großen Tabelle? Ich nehme an, es ist tatsächlich eine Tabelle von Zahlen (d. H. Verdoppelt), so dass nur der Wert 8: 1 groß wäre, und dann gibt es den Tabellenindex-Overhead. - Ich werde es testen. Würde ich auch etwas von der Vorabzuweisung der Ausgabetabelle erhalten (da die Größe bekannt ist)? – marcus256

Aus Neugier: Wie effizient ist table.concat? Sagen wir, ich habe 1.000.000 Tabellenelemente - wäre eine rekursive Verkettung sinnvoll (1 + 1, 1 + 1, 1 + 1, ...)?100 + 100, 100 + 100, usw.), damit du nicht 999,997 + 1, 999,998 + 1 usw. machst? – marcus256

FUNKTIONIERT! (Geschwindigkeit: 3 MB/s, im Vergleich zu 300 MB/s für die C - Version, OK) Ich habe auch eine Geschwindigkeitssteigerung durch Verfolgung der Ausgabelänge in einer separaten Variablen, anstatt #output zu machen (was eine kostspielige Operation für Tabellen). Ich bin mir zwar nicht sicher über den Speicherverbrauch, aber ich betrachte es als: Problem gelöst. – marcus256

Vermeiden Sie die Verkettung von Strings: Speichern Sie die Ausgabestrings in einer Tabelle und schreiben Sie am Schluss alle Strings darin. Wenn Sie befürchten, dass der Tisch zu groß wird, spülen Sie ihn regelmäßig aus. Siehe http://www.lua.org/pil/11.6.html

Quelle

2010-11-24 10:58:37 lhf

Heh, du hast mich dazu geschlagen. Upvoted Sie stattdessen. – Zecc

Leider löst dies nicht das Problem des wahlfreien Zugriffs auf den Puffer. Eine Operation, die unterstützt werden muss, ist (zum Beispiel): "wähle 9 Bytes beginnend 5 Bytes zurück im Ausgabepuffer und füge sie an den Ausgabepuffer an" (ja, die Kopie kann sich selbst überlappen!). – marcus256

@ marcus256 Der Ansatz, den @lhf vorschlägt, würde in diesem Fall immer noch funktionieren. Sie müssen nur einige Funktionen korrigieren, um diese Operationen auf einer Tabelle von Strings zu abstrahieren. Vielleicht sollten Sie die Tabelle jedes Mal, wenn ein überlappendes Lesen/Schreiben erforderlich ist, auf eine einzelne Zeichenkette "spülen", oder bringt das Ihre Leistung wieder zum Erliegen? –

Effizientes veränderbares Byte-Array in nativem Lua

Antwort

Verwandte Themen