Category Archives: Tutorials

Here comes the sun lalala

Lokale Vibe-Codierung: LM Studio, VS Code und Weiter

Wenn Sie den Wunsch hatten, neuronale Netze zum Schreiben von Code zu verwenden (sog. Vibe-Codierung), und über einen recht leistungsstarken Computer verfügen, beispielsweise mit einer Nvidia RTX-Grafikkarte, können Sie die gesamte Umgebung völlig kostenlos auf Ihrem Computer bereitstellen. Dadurch werden Probleme mit kostenpflichtigen Abonnements gelöst und Sie können sicher mit Projekten unter NDA arbeiten, da Ihr Code nirgendwohin gesendet wird. In diesem Beitrag beschreibe ich, wie man ein lokales Bundle aus LM Studio, VS Code und der Continue-Erweiterung zusammenstellt.

Tools für die lokale Vibe-Codierung

Für komfortables Arbeiten benötigen wir drei Hauptkomponenten:
– LM Studio: eine praktische Anwendung zum Herunterladen und Ausführen lokaler LLMs. Es übernimmt die gesamte Komplexität der Arbeit mit GGUF-Modellen und stellt einen lokalen Server bereit, der mit der OpenAI-API kompatibel ist.
– VS Code: ein beliebter und bekannter Code-Editor.
– Continue: Erweiterung für VS Code, die neuronale Netze direkt in die Arbeitsumgebung integriert. Ermöglicht das Chatten, das Hervorheben von Code für die Umgestaltung und unterstützt die automatische Vervollständigung.

Hardwareanforderungen

Lokale Sprachmodelle sind speicherintensiv:
– Grafikkarte (GPU): Nvidia mit 8 GB VRAM oder höher (für komfortables Arbeiten mit Modellen mit 7–8 Milliarden Parametern). Schwerere Modelle benötigen 16 GB VRAM.
– Speicherplatz: ca. 500 GB zum Speichern verschiedener heruntergeladener Modelle.

Link konfigurieren

Der Einrichtungsprozess ist recht einfach und erfordert keine komplexen Manipulationen im Terminal:
1. Laden Sie LM Studio herunter und installieren Sie es. Verwenden Sie die integrierte Suche, um ein leichtes Modell wie Qwen Coder oder gemma3:12b zu finden.
2. Gehen Sie in LM Studio zur Registerkarte Lokaler Server und klicken Sie auf Server starten. Standardmäßig startet es unter „http://localhost:1234/v1“.
3. Öffnen Sie VS Code und installieren Sie die Erweiterung Continue aus dem Plugin-Store.
4. Öffnen Sie die Continue-Konfigurationsdatei und fügen Sie ein neues Modell hinzu. Geben Sie dabei den „openai“-Anbieter und die Adresse Ihres lokalen Servers aus LM Studio an.

Anschließend können Sie direkt in der Seitenleiste „Weiter“ mit Ihrem lokalen LLM kommunizieren, Fragen zu Ihrem Code stellen und neue Komponenten generieren.

Warum funktioniert das?

Wie ich bereits geschrieben habe, schneiden LLMs mit flacher Struktur und WET-Code (Write Everything Twice) besser ab. Lokale Parametermodelle sind möglicherweise Giganten wie GPT-4 unterlegen, wenn es um den Entwurf komplexer Architekturen geht, aber sie sind mehr als in der Lage, Boilerplate-Code zu generieren, einfache Funktionen umzugestalten und schnelle Prototypen zu erstellen.

Darüber hinaus verlässt Ihr Code bei der lokalen Vibe-Codierung nie die Maschine. Damit ist diese Kombination ideal für die Unternehmensentwicklung und die Arbeit mit sensiblen Daten.

Ausgabe

Lokale neuronale Netze sind nicht in der Lage, einen Programmierer vollständig zu ersetzen oder ein komplexes System zu entwerfen. Die Kombination aus LM Studio + VS Code + Continue sorgt jedoch für Unabhängigkeit von Cloud-Diensten und wahrt die Privatsphäre. Dies ist ein voll funktionsfähiges Hilfsmittel für Routineaufgaben, wenn Sie bereit sind, die Einschränkungen kleiner Modelle in Kauf zu nehmen und die Projektarchitektur selbstständig zu steuern.

Links

https://code.visualstudio.com/
https://lmstudio.ai/
https://continue.dev/

Quellen

https://youtu.be/IqqCwhG46jY
https://www.youtube.com/watch?v=7AImkA96mE8

Ausführen von macOS in Docker

Es ist möglich, macOS in Docker auszuführen, trotz der Einwände von Leuten, die sagen, dass dies unmöglich sei, und angeblich verfügt macOS über Schutzsysteme, die dem widerstehen können.

Einige der klassischen Möglichkeiten, macOS auf PC-Rechnern auszuführen, waren in der Vergangenheit:
*Hackintosh
* Virtualisierung, zum Beispiel mit VMWare

Hackintosh setzt das Vorhandensein von Hardware voraus, die dem Original-Mac ähnelt oder diesem sehr nahe kommt. Die Virtualisierung stellt bestimmte Anforderungen an die Hardware, jedoch im Allgemeinen nicht so streng wie im Fall von Hackintosh. Allerdings kommt es bei der Virtualisierung zu Performance-Problemen, da macOS nicht für das Arbeiten in einer virtuellen Umgebung optimiert ist.

Seit kurzem ist es möglich, macOS in Docker auszuführen. Möglich wird dies durch das Docker-OSX-Projekt, das vorgefertigte macOS-Images zur Ausführung auf Docker bereitstellt. Es ist erwähnenswert, dass Docker-OSX kein offizielles Apple-Projekt ist und von diesem nicht unterstützt wird. Sie können jedoch macOS auf Docker ausführen und es zum Entwickeln und Testen von Anwendungen verwenden.

Eines der ersten Projekte, das macOS in Docker ausführt:
https://github.com/sickcodes/Docker-OSX

Allerdings konnte ich es nie vollständig starten; Nach dem Laden in Recovery OS fielen meine Tastatur und meine Maus einfach ab und ich konnte die Installation nicht fortsetzen. Gleichzeitig funktioniert im ersten Bootmenü die Tastatur. Vielleicht liegt es daran, dass dieses Projekt nicht mehr so ​​aktiv unterstützt wird und es bei der Ausführung unter Windows 11 + WSL2 + Ubuntu einige spezifische Probleme gibt.

Eines der derzeit aktivsten Projekte:
https://github.com/dockur/macos

Ermöglicht die Ausführung von macOS in Docker, die Schnittstelle funktioniert über den Browser per VNC(?)-Weiterleitung. Nach dem Start ist macOS unter http://localhost:5900 verfügbar

Ich habe es geschafft, dieses Projekt auszuführen und macOS Big Sur (Minute 2020) unter Windows 11 + WSL2 + Ubuntu zu installieren, aber nur durch Ändern der Compose-Datei, nämlich:

environment:
    VERSION: "11"
    RAM_SIZE: "8G"
    CPU_CORES: "4"

VERSION: „11“ ist die Version von macOS, in diesem Fall Big Sur
RAM_SIZE: „8G“ ist die für macOS zugewiesene RAM-Größe
CPU_CORES: „4“ ist die Anzahl der CPU-Kerne, die macOS zugewiesen sind

Derzeit ist auch die Ausführung von macOS Tahoe (16) möglich, allerdings gibt es eine Reihe von Problemen, die die Projektentwickler beherzt zu lösen versuchen.

Diese originelle Art, macOS zu starten, ermöglicht es Ihnen, es auf Ihrer Nicht-Mac-Hardware auszuprobieren und sich, nachdem Sie genug gelitten haben, einen Mac zu kaufen. Es kann jedoch zum Testen von Software auf älteren Systemen und für die allgemeine Entwicklung nützlich sein.

Swift in WSL2 (Linux) erstellen

Das Swift-Ökosystem entwickelt sich aktiv außerhalb der Apple-Plattformen, und heute ist es recht komfortabel, darin unter Windows mit dem Windows-Subsystem für Linux (WSL2) zu schreiben. Es ist zu bedenken, dass für Assemblys unter Linux/WSL eine schlanke Version von Swift verfügbar ist – ohne proprietäre Apple-Frameworks (wie SwiftUI, UIKit, AppKit, CoreData, CoreML, ARKit, SpriteKit und andere iOS/macOS-spezifische Bibliotheken), aber für Konsolen-Dienstprogramme und das Backend ist dies mehr als ausreichend. In diesem Beitrag werden wir den Prozess der Vorbereitung der Umgebung und der Erstellung des Swift-Compilers aus dem Quellcode in WSL2 Schritt für Schritt durchgehen (am Beispiel von Ubuntu/Debian).

Wir aktualisieren die Liste der Pakete und das System selbst:

sudo apt update && sudo apt upgrade -y

Installieren Sie die erforderlichen Abhängigkeiten für den Build:

sudo apt install -y \
  git cmake ninja-build clang python3 python3-pip \
  libicu-dev libxml2-dev libcurl4-openssl-dev \
  libedit-dev libsqlite3-dev swig libncurses5-dev \
  pkg-config tzdata rsync

Installieren Sie den Compiler und Linker (LLVM und LLD):

sudo apt install -y llvm lld

Klonen Sie das Swift-Repository mit allen Abhängigkeiten:

git clone https://github.com/apple/swift.git
cd swift
utils/update-checkout --clone

Installieren Sie „swiftly“ und fertiges Swift mit Swiftc

curl -O https://download.swift.org/swiftly/linux/swiftly-$(uname -m).tar.gz && \
tar zxf swiftly-$(uname -m).tar.gz && \
./swiftly init --quiet-shell-followup && \
. "${SWIFTLY_HOME_DIR:-$HOME/.local/share/swiftly}/env.sh" && \
hash -r

Beginnen wir mit dem Build (dies wird lange dauern):

utils/build-script \
  --release-debuginfo \
  --swift-darwin-supported-archs="x86_64" \
  --llvm-targets-to-build="X86" \
  --skip-build-benchmarks \
  --skip-test-cmark \
  --skip-test-swift \
  --skip-ios \
  --skip-tvos \
  --skip-watchos \
  --skip-build-libdispatch=false \
  --skip-build-cmark=false \
  --skip-build-foundation \
  --skip-build-lldb \
  --skip-build-xctest \
  --skip-test-swift

Nachdem der Build abgeschlossen ist, fügen Sie den Pfad zum Compiler zu PATH hinzu (geben Sie Ihren Pfad zum Build-Ordner an):

export PATH=/root/Sources/3rdparty/build/Ninja-RelWithDebInfoAssert/swift-linux-x86_64/bin/swiftc:$PATH

Wir überprüfen, ob die installierte Version von Swift funktioniert:

swift --version

Erstellen Sie eine Testdatei und führen Sie sie aus:

echo "print(\"Hello, World!\")" > hello.swift
swift hello.swift

Sie können die Binärdatei auch kompilieren und ausführen:

swiftc hello.swift
./hello

Quellen

Musterinterpreter in der Praxis

Im letzten Artikel haben wir uns mit der Theorie des Interpreter-Musters befasst, gelernt, was ein AST-Baum ist und wie man terminale und nicht-terminale Ausdrücke abstrahiert. Lassen Sie uns dieses Mal von der Theorie Abstand nehmen und sehen, wie dieses Muster in ernsthaften kommerziellen Projekten angewendet wird, die wir alle täglich verwenden!

Spoiler: Möglicherweise verwenden Sie gerade das Interpreter-Muster, indem Sie einfach diesen Text in Ihrem Browser lesen!

Eines der auffälligsten und vielleicht wichtigsten Beispiele für die Verwendung dieses Musters in der Branche ist JavaScript. Die ursprünglich „auf dem Knie“ entstandene Sprache funktioniert heute dank des Interpretationskonzepts auf Milliarden von Geräten.

10 Tage, die das Internet verändert haben

Die Geschichte von JavaScript ist voller Legenden. Im Jahr 1995 erhielt Brendan Eich während seiner Arbeit bei Netscape Communications die Aufgabe, eine einfache Skriptsprache zu entwickeln, die direkt in einem Browser (Netscape Navigator) ausgeführt werden konnte, um Webseiten interaktiv zu gestalten. Das Management wollte etwas mit einer Syntax, die dem damals sehr beliebten Java ähnelte, aber nicht für professionelle Ingenieure, sondern für Webdesigner gedacht war.

Eich hatte nur 10 Tage Zeit, um den ersten Prototyp der Sprache zu schreiben, die damals Mocha hieß (damals LiveScript und aus Marketinggründen erst JavaScript). Der Ansturm kam nicht von ungefähr: Microsoft war ihm dicht auf den Fersen und bereitete gleichzeitig aktiv seine eigene Skriptsprache VBScript für die Einbettung in den Internet Explorer-Browser vor. Netscape musste dringend seine Antwort veröffentlichen, um im drohenden Browserkrieg nicht zu verlieren.

Es war einfach keine Zeit, einen komplexen Compiler in Maschinencode zu schreiben. Die offensichtlichste und schnellste Lösung für Eich war die Architektur des klassischen Interpreter.

Der erste Interpreter (SpiderMonkey) funktionierte folgendermaßen:

  1. Der Textquellcode des Skripts wurde von der Seite gelesen.
  2. Der lexikalische Analysator hat den Text in Token zerlegt.
  3. Der Parser hat einen Abstract Syntax Tree (AST) erstellt. In Bezug auf das Interpreter-Muster bestand dieser Baum aus terminalen Ausdrücken (Zeichenfolgen, Zahlen wie 42) und nicht-terminalen Ausdrücken (Funktionsaufrufe, Anweisungen wie If, ​​​​While).
  4. Dann „durchlief“ die virtuelle Maschine diesen Baum Schritt für Schritt und führte die darin eingebetteten Anweisungen an jedem Knoten aus (wobei sie eine Methode ähnlich Interpret() aufrief).

Kontext und Objekte

Erinnern Sie sich an das Context-Objekt, das wir in der klassischen Implementierung an die Methode Interpret(Context context) übergeben mussten? Der Interpreter benötigt es, um den aktuellen Speicherzustand zu speichern.

Im Fall von JavaScript wird die Rolle dieses Kontexts auf der obersten Ebene von einem globalen Objekt (z. B. einem Fenster in einem Browser) übernommen. Wenn Ihr AST-Knoten versucht, beispielsweise über document.write(“Hello”) Text auf den Bildschirm zu schreiben, greift der Interpreter auf seinen Kontext (das Dokumentobjekt) zu und ruft die gewünschte interne Browser-API auf.

Dank des Interpreters kann JavaScript so einfach mit dem DOM (Document Object Model) interagieren – das sind alles nur Objekte in einem Kontext, auf die über Baumknoten zugegriffen wird.

Entwicklung des Interpreters: JIT-Kompilierung

Historisch gesehen ist JS in Browsern lange Zeit ein „reiner“ Interpreter geblieben. Und das hatte einen großen Nachteil: langsame Geschwindigkeit. Das Parsen des Baums und das langsame Durchlaufen jedes Knotens bei jeder Ausführung des Skripts verlangsamte komplexe Webanwendungen.

Mit der Einführung der V8-Engine von Google (integriert in Chrome) im Jahr 2008 kam es zu einer Revolution. Ingenieure erkannten, dass ein Dolmetscher für das moderne Web nicht ausreicht. Die Engine ist komplexer geworden: Sie erstellt immer noch den AST-Baum, verwendet aber jetzt die JIT-Kompilierung (Just-In-Time).

Moderne JS-Engines (V8, SpiderMonkey) funktionieren wie eine komplexe Pipeline:

  1. Der schnelle und einfache Basisinterpreter beginnt sofort mit der Ausführung Ihres JS-Codes, ohne überhaupt auf die Kompilierung warten zu müssen (das klassische Muster funktioniert hier immer noch).
  2. Parallel dazu überwacht die Engine „heiße“ Codeabschnitte (Schleifen oder Funktionen, die tausende Male aufgerufen werden).
  3. Diese Abschnitte werden vom JIT-Compiler unter Umgehung des langsamen Interpreters direkt in optimierten Maschinencode kompiliert.

Es war diese Kombination aus dem sofortigen Start des Interpreters und der Rechenleistung der Kompilierung, die es JavaScript ermöglichte, die Welt zu erobern und zur Sprache von Servern (Node.js) und mobilen Anwendungen (React Native) zu werden.

Dolmetscher in der Spielebranche

Trotz der Dominanz von C++ im Heavy Computing ist das Interpreter-Muster ein Industriestandard in der Spieleentwicklung zum Erstellen von Spiellogik. Wofür? Damit Spieleentwickler Spiele erstellen können, ohne das Risiko einzugehen, die Engine „abzuwerfen“ oder sie ständig neu kompilieren zu müssen.

Ein hervorragendes historisches Beispiel ist UnrealScript – die Sprache, in der die Logik der Spiele Unreal Tournament und Gears of War in den Unreal Engines 1, 2 und 3 geschrieben wurde. Der Text wurde in einen kompakten abstrakten Maschinenbytecode kompiliert, der dann Schritt für Schritt von der virtuellen Maschine der Engine (interpretiert) wurde.

Visuelle Diagrammskripte (Blueprints)

Heute wurde Text durch visuelle Programmierung ersetzt – das Blueprints-System in Unreal Engine 4 und 5.

Wenn Sie jemals einen Blueprint in Unreal Engine geöffnet haben, haben Sie viele Knoten gesehen, die durch Kabel verbunden sind. Architektonisch gesehen ist das gesamte Blueprints-Diagramm ein riesiger abstrakter Syntaxbaum (AST), der auf dem Bildschirm gezeichnet wird:

  1. Terminalausdrücke: Konstante Knoten. Zum Beispiel ein Knoten, der einfach die Zahl 42 oder einen String speichert. Sie geben bei der Interpretation einen bestimmten Wert zurück.
  2. Nicht-terminale Ausdrücke: Rechenknoten (Hinzufügen) oder Flusskontrollknoten (Zweig). Sie verfügen über Argumenteingänge, die der Interpreter zunächst rekursiv auswertet, bevor er das Ergebnis als Ausgabepin erzeugt.

Und die Rolle des Kontexts spielt hier die Erinnerung an eine Instanz eines bestimmten Spielobjekts (Akteur). Die Interpretermaschine „geht“ sicher durch dieses Diagramm, fordert Daten an und führt Übergänge durch.

Wo wird der Interpreter sonst noch verwendet?

Das Interpretermuster kann in fast jedem komplexen System gefunden werden, in dem dynamische Anweisungen ausgeführt werden müssen. Hier sind nur einige Beispiele aus kommerzieller Software:

  • Interpretierte Programmiersprachen (Python, Ruby, PHP). Ihre gesamte Laufzeit basiert auf dem klassischen Muster. Beispielsweise analysiert die CPython-Referenzimplementierung Ihr .py-Skript zunächst in ein AST, kompiliert es in Bytecode und dann interpretiert eine riesige virtuelle Maschine (Rechenschleife) diesen Bytecode Schritt für Schritt.
  • Java Virtual Machine (JVM). Zunächst wird Java-Code nicht in Maschinenanweisungen, sondern in Bytecode kompiliert. Wenn Sie die Anwendung ausführen, fungiert die JVM als Interpreter (allerdings mit aggressiver JIT-Kompilierung, genau wie in V8).
  • Datenbanken und SQL Wenn Sie eine SQL-Abfrage (SELECT * FROM user) in PostgreSQL oder MySQL ausgeben, fungiert die Datenbank-Engine als Interpreter. Es führt eine lexikalische Analyse durch, erstellt einen AST-Abfragebaum, generiert einen Ausführungsplan und „interpretiert“ diesen Plan dann buchstäblich, indem es über die Zeilen der Tabellen iteriert.
  • Reguläre Ausdrücke (RegEx). Jede Engine für reguläre Ausdrücke analysiert intern ein Zeichenfolgenmuster (z. B. ^\d{3}-\d{2}$) in ein Zustandsdiagramm (NFA/DFA-Automaten), das der interne Interpreter dann durchläuft und jedes Eingabezeichen mit den Eckpunkten dieses Diagramms abgleicht.
  • Unity Shader Graph / Unreal Material Editor – visuelle Knoten in modularen Shader-Code (GLSL/HLSL) interpretieren.
  • Blender Geometry Nodes – interpretieren mathematische und geometrische Operationen, um prozedural 3D-Modelle in Echtzeit zu generieren.

Gesamt

Das Interpreter-Muster geht längst über den Rahmen des „Schreibens eines eigenen Taschenrechners“ hinaus. Dies ist der leistungsstärkste Industriestandard. Von JavaScript-Engines, die täglich Gigabytes an Code hinter den Kulissen von Browsern ausführen, bis hin zu Spieledesignern, die es Ihnen ermöglichen, komplexe Logik ohne Kenntnisse von C++ zu erstellen, bleiben Interpreter eines der wichtigsten Architekturkonzepte in der modernen IT-Entwicklung.

Blockierungen in der Praxis ohne Formalin blockieren

Das Blockdiagramm ist ein visuelles Werkzeug, das dazu beiträgt, einen komplexen Algorithmus in eine verständliche und strukturierte Folge von Aktionen zu verwandeln. Von der Programmierung bis zum Geschäftsprozessmanagement dienen sie als universelle Sprache für die Visualisierung, Analyse und Optimierung der komplexesten Systeme.

Stellen Sie sich eine Karte vor, auf der anstelle von Straßen Logik und anstelle von Städten – Aktionen ist. Dies ist ein Blockdiagramm-ein unverzichtbares Werkzeug für die Navigation in den verwirrendsten Prozessen.

Beispiel 1: vereinfachtes Spielstartschema
Um das Arbeitsprinzip zu verstehen, präsentieren wir ein einfaches Spielstartschema.

Dieses Schema zeigt das perfekte Skript, wenn alles ohne Fehler passiert. Aber im wirklichen Leben ist alles viel komplizierter.

Beispiel 2: Erweitertes Schema zum Starten des Spiels mit Datenladen
Moderne Spiele erfordern häufig eine Internetverbindung, um Benutzerdaten, Speichern oder Einstellungen herunterzuladen. Fügen wir diese Schritte zu unserem Schema hinzu.

Dieses Schema ist bereits realistischer, aber was wird passieren, wenn etwas schief geht?

Wie war es: Ein Spiel, das mit dem Verlust des Internets “brach”

“brach”

Zu Beginn des Projekts konnten Entwickler nicht alle möglichen Szenarien berücksichtigen. Zum Beispiel konzentrierten sie sich auf die Hauptlogik des Spiels und überlegten nicht, was passieren würde, wenn der Spieler eine Internetverbindung hat.

In einer solchen Situation würde das Blockdiagramm ihres Codes so aussehen:

In diesem Fall hat das Spiel in der Phase des Wartens auf Daten, die sie aufgrund des Fehlens einer Verbindung nicht erhielt, anstatt einen Fehler oder korrekt zu schließen. Dies führte zum “schwarzen Bildschirm” und zum Einfrieren der Anwendung.

Wie es wurde: Korrektur bei Benutzerbeschwerden

Nach zahlreichen Beschwerden der Benutzer über das Schwebewesen erkannte das Entwicklerteam, dass wir den Fehler korrigieren mussten. Sie nahmen Änderungen am Code vor, indem sie eine Fehlerverarbeitungseinheit hinzufügen, mit der die Anwendung auf den mangelnden Verbindungsmangel korrekt reagiert.

So sieht das korrigierte Blockdiagramm aus, in dem beide Szenarien berücksichtigt werden:

Dank dieses Ansatzes informiert das Spiel jetzt den Benutzer über das Problem und kann in einigen Fällen sogar in den Offline -Modus gehen, sodass Sie das Spiel fortsetzen können. Dies ist ein gutes Beispiel dafür, warum Blockdiagramme so wichtig sind.

Unsicheres Verhalten

Das Hängen und Fehler sind nur ein Beispiel für unvorhersehbare Verhalten des Programms. Bei der Programmierung gibt es ein Konzept von unsicherem Verhalten (undefiniertes Verhalten) – Dies ist eine Situation, in der der Standard der Sprache nicht beschreibt, wie sich das Programm in einem bestimmten Fall verhalten sollte.

Dies kann zu allem führen: vom zufälligen „Müll“ beim Rückzug zum Versagen des Programms oder sogar der schwerwiegenden Sicherheitsanfälligkeit. Unbestimmte Verhalten tritt häufig bei der Arbeit mit dem Gedächtnis auf, zum Beispiel mit Zeilen in der Sprache von C.

Ein Beispiel aus der Sprache c:

Stellen Sie sich vor, der Entwickler hat die Linie in den Puffer kopiert, aber vergessen, das Ende des Null -Symbols (\ 0`) zu addieren, das das Ende der Linie markiert.

So sieht der Code aus:

#include 

int main() {
char buffer[5];
char* my_string = "hello";

memcpy(buffer, my_string, 5);

printf("%s\n", buffer);
return 0;
}

Erwartete Ergebnis: “Hallo”
Das wirkliche Ergebnis ist unvorhersehbar.

Warum passiert das? Die Funktion “printf`) mit dem Spezifizierer%S` erwartet, dass die Linie mit einem Nullsymbol endet. Wenn er nicht ist, wird sie die Erinnerung außerhalb des hervorgehobenen Puffers weiter lesen.

Hier ist das Blockdiagramm dieses Prozesses mit zwei möglichen Ergebnissen:

Dies ist ein klares Beispiel dafür, warum die Blockdiagramme so wichtig sind: Sie lassen den Entwickler nicht nur über die ideale Ausführungsweise nachdenken, sondern auch über alle möglichen Fehler, einschließlich solcher Probleme mit niedrigem Niveau, was das Endprodukt viel stabiler und zuverlässiger macht.

Pixel perfekt: Mythos oder Realität in der Ära der Deklarativität?

In der Welt der Schnittstellenentwicklung gibt es ein gemeinsames Konzept – “Pixel perfekt in der Lodge” . Es impliziert die genaueste Reproduktion der Konstruktionsmaschine auf das kleinste Pixel. Lange Zeit war es ein Goldstandard, insbesondere in der Ära eines klassischen Webdesigns. Mit der Ankunft der deklarativen Meile und dem schnellen Wachstum der Vielfalt der Geräte wird das Prinzip von “Pixel Perfect” jedoch zunehmend kurzlebiger. Versuchen wir herauszufinden, warum.

Imperial Wysiwyg vs. Deklarativer Code: Was ist der Unterschied?

Traditionell wurden viele Schnittstellen, insbesondere der Desktop, mit imperativen Ansätzen oder wysiwyg (was Sie sehen, was Sie erhalten) von Herausgebern erstellt. In solchen Tools manipuliert der Designer oder Entwickler direkt mit Elementen und platziert sie auf Leinwand mit Genauigkeit zum Pixel. Es ähnelt der Arbeit mit einem Grafikeditor – Sie sehen, wie Ihr Element aussieht, und Sie können es definitiv positionieren. In diesem Fall war die Leistung von “Pixel Perfect” ein sehr reales Ziel.

Die moderne Entwicklung basiert jedoch zunehmend auf deklarativen Meilen . Dies bedeutet, dass Sie dem Computer nicht sagen, dass er “diese Schaltfläche hier einstellen”, sondern beschreiben, was Sie bekommen möchten. Anstatt die spezifischen Koordinaten des Elements anzuzeigen, beschreiben Sie beispielsweise seine Eigenschaften: “Diese Schaltfläche sollte rot sein, 16px -Eindringlinge von allen Seiten haben und in der Mitte des Behälters stehen.” Freiimvorki wie React, Vue, Swiftui oder Jetpack komponieren nur dieses Prinzip.

Warum “Pixel Perfect” für viele Geräte nicht mit einer deklarativen Meile funktioniert

Stellen Sie sich vor, Sie erstellen eine Anwendung, die auf dem iPhone 15 Pro Max, Samsung Galaxy Fold, iPad Pro und einer 4K -Auflösung gleich gut aussehen soll. Jedes dieser Geräte hat eine unterschiedliche Bildschirmauflösung, Pixeldichte, Parteien und physische Größen.

Wenn Sie den deklarativen Ansatz verwenden, entscheidet das System selbst unter Berücksichtigung aller Parameter, wie Sie Ihre beschriebene Schnittstelle auf einem bestimmten Gerät anzeigen. Sie setzen die Regeln und Abhängigkeiten, nicht die harten Koordinaten.

* Anpassungsfähigkeit und Reaktionsfähigkeit: Das Hauptziel der deklarativen Meilen ist es, adaptive und reaktionsschnelle Schnittstellen zu erstellen. Dies bedeutet, dass sich Ihre Schnittstelle automatisch an die Größe und Ausrichtung des Bildschirms anpassen sollte, ohne die Lesbarkeit zu brechen und aufrechtzuerhalten. Wenn wir auf jedem Gerät „Pixel Perfect“ beantragen möchten, müssten wir unzählige Optionen für dieselbe Schnittstelle erstellen, was die Vorteile des deklarativen Ansatzes vollständig ausgleichen wird.
* Pixeldichte (DPI/PPI): Die Geräte haben eine unterschiedliche Pixeldichte. Das gleiche Element mit der Größe von 100 “virtuellen” Pixeln auf einem Gerät mit hoher Dichte sieht viel kleiner aus als bei einem Gerät mit niedrigem Dichte, wenn Sie die Skalierung nicht berücksichtigen. Deklarative Rahmenbedingungen werden von physischen Pixeln abstrahiert und arbeiten mit logischen Einheiten.
* Dynamischer Inhalt: Inhalt in modernen Anwendungen ist häufig dynamisch – sein Volumen und die Struktur können variieren. Wenn wir hart auf die Pixel gerissen würden, würde jede Änderung des Textes oder des Bildes zum “Zusammenbruch” des Layouts führen.
* Verschiedene Plattformen: Zusätzlich zur Vielfalt der Geräte gibt es verschiedene Betriebssysteme (iOS, Android, Web, Desktop). Jede Plattform verfügt über eigene Design, Standardsteuerungen und Schriftarten. Ein Versuch, auf allen Plattformen eine absolut identische Pixel -Perfect -Schnittstelle zu erstellen, würde zu einem unnatürlichen Typ und einer schlechten Benutzererfahrung führen.

Die alten Ansätze gingen nicht verschwunden, sondern entwickelten

Es ist wichtig zu verstehen, dass der Ansatz zu Schnittstellen keine binäre Wahl zwischen “imperativ” und “deklarativ” ist. Historisch gesehen gab es für jede Plattform ihre eigenen Werkzeuge und Ansätze zur Erstellung von Schnittstellen.

* Native Schnittstellendateien: Für iOS waren es XIB/Storyboards für Android-XML-Markierungsdateien. Diese Dateien sind ein Pixel-Perfekt-Wysiwyg-Layout, das dann wie im Editor im Radio angezeigt wird. Dieser Ansatz ist nirgendwo verschwunden und entwickelt sich weiter und integriert sich in moderne deklarative Rahmen. Zum Beispiel haben Swiftui in Apple und Jetpack in Android auf dem Pfad eines rein deklarativen Code eingeschaltet, behielten gleichzeitig die Möglichkeit, ein klassisches Layout zu verwenden.
* Hybridlösungen: häufig in realen Projekten wird eine Kombination von Ansätzen verwendet. Beispielsweise kann die Grundstruktur der Anwendung deklarativ implementiert werden und für spezifische, die eine genaue Positionierung von Elementen, niedrigere Level, imperative Methoden erfordern, oder native Komponenten, die unter Berücksichtigung der Einzelheiten der Plattform entwickelt wurden.

vom Monolith zur Anpassungsfähigkeit: Wie die Entwicklung von Geräten eine deklarative Meile bildete

Die Welt der digitalen Schnittstellen hat sich in den letzten Jahrzehnten enorme Veränderungen verändert. Von stationären Computern mit festen Genehmigungen kamen wir in die Ära des exponentiellen Wachstums der Vielfalt der Benutzergeräte . Heute sollten unsere Bewerbungen gleich gut funktionieren:

* Smartphones aller Formfaktoren und Bildschirmgrößen.
* Tablets mit ihren einzigartigen Ausrichtungsmodi und einem getrennten Bildschirm.
* Laptops und Desktops mit verschiedenen Monitorengenehmigungen.
* TVS- und Medienzentren , kontrolliert remote. Es ist bemerkenswert, dass selbst für Fernseher, deren Bemerkungen mit einem Minimum an Schaltflächen, oder umgekehrt, mit vielen Funktionen überladen sind, selbst für die Schnittstellen so einfach sind, dass der Code keine spezifische Anpassung für diese Eingabefunktionen benötigt. Die Schnittstelle sollte “als ob für sich selbst” funktionieren, ohne eine zusätzliche Beschreibung des “Wie” mit einer bestimmten Fernbedienung zu interagieren.
* Smart Watches und Wearable -Geräte mit minimalistischen Bildschirmen.
* Virtual Reality Helme (VR) , die einen völlig neuen Ansatz für eine räumliche Schnittstelle erfordern.
* Augmented Reality Device Devices (AR) , die Informationen über die reale Welt anwenden.
* Automobilinformationen und Unterhaltungssysteme .
* Und sogar Haushaltsgeräte : Von Kühlschränken mit sensorischen Bildschirmen und Waschmaschinen mit interaktiven Displays bis hin zu intelligenten Öfen und Systemen des Smart House.

Jedes dieser Geräte verfügt über eigene Merkmale: physikalische Dimensionen, Parteienverhältnisse, Pixeldichte, Eingabemethoden (Touchscreen, Maus, Controller, Gesten, Stimmbefehle) und vor allem die Feinheiten der Benutzerumgebung . Beispielsweise erfordert ein VR Shlesh ein tiefes Eintauchen und eine Smartphone-schnelle und intuitive Arbeit unterwegs, während die Kühlschrankschnittstelle für schnelle Navigation genauso einfach und groß sein sollte.

Klassischer Ansatz: Die Belastung für die Unterstützung einzelner Schnittstellen

In der Zeit der Dominanz von Desktops und der ersten mobilen Geräte war das übliche Geschäft die Erstellung und Unterstützung von von einzelnen Schnittstellendateien oder sogar eines vollständig separaten Schnittstellencodes für jede Plattform .

* Die Entwicklung unter iOS erforderte häufig die Verwendung von Storyboards oder XIB-Dateien in Xcode, das Code auf Objective-C oder Swift schreibt.
* Für Android wurden die XML -Markierungsdateien und der Code auf Java oder Kotlin erstellt.
* Web -Schnittstellen haben HTML/CSS/JavaScript eingeschaltet.
* Für Anwendungen c ++ auf verschiedenen Desktop -Plattformen wurden ihre spezifischen Frameworks und Tools verwendet:
* In Windows waren dies MFC (Microsoft Foundation Classes), Win32 -API mit manuellen Zeichnungselementen oder Verwendung von Ressourcendateien für Dialogfenster und Steuerelemente.
* Kakao (Objektiv-C/Swift) oder die alte Kohlenstoff-API zur direkten Kontrolle der grafischen Grenzfläche wurden in macOS verwendet.
* In Linux/UNIX-ähnlichen Systemen wurden häufig Bibliotheken wie GTK+ oder QT verwendet, die ihre Widgets und Mechanismen zum Erstellen von Schnittstellen bereitstellten, häufig über XML-ähnliche Markierungsdateien (z.

Dieser Ansatz sorgte für eine maximale Kontrolle über jede Plattform, sodass Sie alle spezifischen Funktionen und nativen Elemente berücksichtigen können. Er hatte jedoch einen großen Nachteil: Duplizierung von Bemühungen und enorme Kosten für Unterstützung . Die geringste Änderung des Designs oder der Funktionalität erforderte die Einführung eines Rechts auf mehrere unabhängige Codebasen. Dies wurde zu einem echten Albtraum für Entwicklerteams, verlangsamte die Ausgabe neuer Funktionen und erhöhte die Wahrscheinlichkeit von Fehlern.

deklarative Meilen: Eine einzelne Sprache für Vielfalt

Als Reaktion auf diese schnelle Komplikation erschien die deklarativen Meilen als dominantes Paradigma. Framws wie React, Vue, Swiftui, Jetpack Compose und andere sind nicht nur eine neue Art, Code zu schreiben, sondern eine grundlegende Verschiebung des Denkens.

Die Hauptidee des deklarativen Ansatzes : Anstatt das System zu sagen, wie man jedes Element zeichnet (imperativ), beschreiben wir „was“ wir sehen wollen (deklarativ). Wir setzen die Eigenschaften und den Zustand der Schnittstelle, und das Framework entscheidet, wie Sie sie am besten auf einem bestimmten Gerät anzeigen können.

Dies wurde dank der folgenden wichtigen Vorteile möglich:

1. Abstraktion aus den Details der Plattform: deklarative Fraimvorki sind speziell so konzipiert, dass sie die Details mit niedrigem Level für jede Plattform vergessen. Der Entwickler beschreibt die Komponenten und ihre Beziehungen auf einer höheren Abstraktionsebene unter Verwendung eines einzelnen, übertragenen Codes.
2. Automatische Anpassung und Reaktionsfähigkeit: Freiimvorki Übernehmen Sie die Verantwortung für die automatische Skalierung , ändern Sie das Layout und die Anpassung von Elementen in verschiedene Größen von Bildschirmen, Pixeldichte und Eingabemethoden. Dies wird durch die Verwendung flexibler Layoutsysteme wie Flexbox oder Grid und Konzepte erreicht, die “logischen Pixeln” oder “DP” ähneln.
3.. Dies vereinfacht den Testprozess und bietet vorhersehbarere Benutzererfahrung.
V. Die Teams können sich auf Funktionalität und Design konzentrieren und nicht auf wiederholte Umschreiben derselben Schnittstelle.
5. Freiimvorki kann aktualisiert werden, um neue Technologien zu unterstützen, und Ihr bereits geschriebener Code erhält. Diese Unterstützung ist relativ nahtlos.

Schlussfolgerung

Die deklarative Meile ist nicht nur ein Modetrend, sondern auch die notwendige evolutionäre Stufe , die durch die schnelle Entwicklung von Benutzergeräten verursacht wird, einschließlich der Sphäre des Internet der Dinge (IoT) und intelligente Haushaltsgeräte. Es ermöglicht Entwicklern und Designern, komplexe, adaptive und gleichmäßige Schnittstellen zu erstellen, ohne in endlosen spezifischen Implementierungen für jede Plattform zu ertrinken. Der Übergang von der imperativen Kontrolle über jedes Pixel zur deklarativen Beschreibung des gewünschten Zustands ist eine Erkenntnis, dass in der Welt der zukünftigen Schnittstellen flexibel, übertragen und intuitiv unabhängig davon, welcher Bildschirm angezeigt wird.

Programmierer, Designer und Benutzer müssen lernen, wie man in dieser neuen Welt lebt. Die zusätzlichen Details des Pixel Perfect, das auf ein bestimmtes Gerät oder eine bestimmte Auflösung ausgelegt ist, führen zu unnötigen Zeitkosten für die Entwicklung und Unterstützung. Darüber hinaus funktionieren solche harten Layouts möglicherweise nicht auf Geräten mit nicht standardmäßigen Schnittstellen wie begrenzten Eingangsfernsehern, VR- und AR-Verschiebungen sowie anderen Geräten der Zukunft, von denen wir heute noch nicht einmal wissen. Flexibilität und Anpassungsfähigkeit – Dies sind die Schlüssel zur Schaffung erfolgreicher Schnittstellen in der modernen Welt.

Vibe-Core-Tricks: Warum LLM immer noch nicht mit festem, trockenem und sauberem funktioniert

Mit der Entwicklung von großsprachigen Modellen (LLM) wie Chatgpt verwenden immer mehr Entwickler sie, um Code, Designarchitektur und Beschleunigung der Integration zu generieren. Bei der praktischen Anwendung wird jedoch spürbar: Die klassischen Prinzipien der Architektur – solide, trocken, sauber – verstehen Sie die Besonderheiten der LLM -Codgendation schlecht.

Dies bedeutet nicht, dass die Prinzipien veraltet sind – im Gegenteil, sie arbeiten perfekt zur manuellen Entwicklung. Aber mit LLM muss der Ansatz angepasst werden.

Warum LLM nicht mit architektonischen Prinzipien fertig werden kann

Kapselung

Die Zusammenfassung erfordert das Verständnis der Grenzen zwischen Teilen des Systems, Kenntnissen über die Absichten des Entwicklers sowie den strengen Zugriffsbeschränkungen. LLM vereinfacht häufig die Struktur, macht Felder ohne Grund öffentlich oder dupliziert die Implementierung. Dies macht den Code anfälliger für Fehler und verstößt gegen die architektonischen Grenzen.

Abstracts und Schnittstellen

Entwurfsmuster wie eine abstrakte Fabrik oder Strategie erfordern eine ganzheitliche Sicht des Systems und das Verständnis seiner Dynamik. Modelle können eine Schnittstelle ohne klaren Zweck erstellen, ohne die Implementierung zu gewährleisten, oder gegen die Verbindung zwischen Schichten verstoßen. Das Ergebnis ist eine überschüssige oder nicht funktionsfähige Architektur.

trocken (Donolt wiederholt sich)

LLM bemüht sich nicht, den sich wiederholenden Code zu minimieren – im Gegenteil, es ist für sie einfacher, Blöcke zu duplizieren, als allgemeine Logik zu erstellen. Obwohl sie auf Anfrage auf Anfrage eingerichtet werden können, neigen Modelle neigen dazu, „selbstfassende“ Fragmente zu erzeugen, auch wenn dies zu Redundanz führt.

saubere Architektur

Clean impliziert eine strenge Hierarchie, Unabhängigkeit von Frameworks, gerichtete Abhängigkeit und minimale Verbindung zwischen Schichten. Die Erzeugung einer solchen Struktur erfordert ein globales Verständnis des Systems – und LLM arbeiten auf der Ebene der Wahrscheinlichkeit von Wörtern, nicht auf architektonischer Integrität. Daher ist der Code unter Verstoß gegen die Anweisungen der Abhängigkeit und eine vereinfachte Aufteilung in Ebenen gemischt.

Was funktioniert besser bei der Arbeit mit LLM

Nass statt trocken
Der nasses (zweimal alles schreiben) ist praktischer bei der Arbeit mit LLM. Die Duplikation von Code erfordert keinen Kontext aus dem Modell der Aufbewahrung, was bedeutet, dass das Ergebnis vorhersehbar ist und einfacher zu korrekt ist. Es reduziert auch die Wahrscheinlichkeit von nicht offenen Verbindungen und Fehler.

Darüber hinaus hilft die Duplikation, den kurzen Speicher des Modells zu kompensieren: Wenn ein bestimmtes Logikfragment an mehreren Stellen gefunden wird, berücksichtigt LLM es mit größerer Wahrscheinlichkeit mit weiterer Generation. Dies vereinfacht die Begleitung und erhöht den Widerstand gegen “Vergessen”.

einfache Strukturen anstelle von Kapselung

Vermeiden Sie eine komplexe Kapselung und stützen sich auf die direkte Übertragung von Daten zwischen den Teilen des Codes und können sowohl die Generation als auch das Debuggen erheblich vereinfachen. Dies gilt insbesondere für eine schnelle iterative Entwicklung oder Schaffung von MVP.

vereinfachte Architektur

Eine einfache, flache Struktur des Projekts mit einer minimalen Menge an Abhängigkeiten und Abstraktionen liefert während der Erzeugung ein stabileres Ergebnis. Das Modell passt einen solchen Code leichter an und verletzt die erwarteten Verbindungen zwischen den Komponenten.

SDK -Integration – Manuell zuverlässig


Die meisten Sprachmodelle werden auf veralteten Dokumentationsversionen geschult. Bei der Erstellung von Anweisungen zur Installation von SDK werden daher häufig Fehler angezeigt: veraltete Befehle, irrelevante Parameter oder Links zu unzugänglichen Ressourcen. Praxis zeigt: Es ist am besten, offizielle Dokumentation und manuelle Abstimmung zu verwenden und LLM eine Hilfsrolle zu hinterlassen – beispielsweise eine Vorlagencode oder eine Anpassung von Konfigurationen zu generieren.

Warum funktionieren die Prinzipien noch – aber mit manueller Entwicklung

Es ist wichtig zu verstehen, dass die Schwierigkeiten von festem, trockenem und sauberem Zusammenhang die Codhegeneration durch LLM betreffen. Wenn der Entwickler den Code manuell schreibt, demonstrieren diese Prinzipien weiterhin seinen Wert: Sie reduzieren die Verbundenheit, vereinfachen die Unterstützung und erhöhen die Lesbarkeit und Flexibilität des Projekts.

Dies liegt an der Tatsache, dass menschliches Denken anfällig für die Verallgemeinerung ist. Wir suchen nach Mustern, wir bringen wiederholte Logik in einzelne Entitäten und erstellen Muster. Wahrscheinlich hat dieses Verhalten evolutionäre Wurzeln: Reduzierung der Anzahl der Informationen spart kognitive Ressourcen.

LLM handelt anders: Sie erleben keine Lasten aus dem Datenvolumen und streben nicht nach Einsparungen. Im Gegenteil, es ist für sie einfacher, mit doppelten, fragmentierten Informationen zu arbeiten, als komplexe Abstraktionen aufzubauen und aufrechtzuerhalten. Aus diesem Grund ist es für sie einfacher, mit dem Code ohne Kapselung fertig zu werden, mit wiederholenden Strukturen und minimaler architektonischer Schwere.

Schlussfolgerung

Großsprachenmodelle sind ein nützliches Instrument in der Entwicklung, insbesondere in den frühen Stadien oder beim Erstellen eines Hilfscode. Es ist jedoch wichtig, den Ansatz an sie anzupassen: die Architektur zu vereinfachen, die Abstraktion zu begrenzen, komplexe Abhängigkeiten zu vermeiden und bei der Konfiguration von SDK nicht auf sie zu verlassen.

Die Prinzipien von fester, trocken und sauber sind immer noch relevant, aber sie haben den besten Effekt in den Händen einer Person. Bei der Arbeit mit LLM ist es vernünftig, einen vereinfachten, praktischen Stil zu verwenden, der es Ihnen ermöglicht, einen zuverlässigen und verständlichen Code zu erhalten, der leicht manuell abschließen kann. Und wo LLM vergisst – die Duplizierung von Code hilft ihm, sich zu erinnern.

Portierung der Surreal Engine C++ auf WebAssembly

In diesem Beitrag beschreibe ich, wie ich die Surreal Engine-Spiel-Engine auf WebAssembly portiert habe.

Surreal Engine – eine Spiel-Engine, die die meisten Funktionen der Unreal Engine 1 implementiert, berühmte Spiele auf dieser Engine – Unreal Tournament 99, Unreal, Deus Ex, Undying. Es bezieht sich auf klassische Engines, die hauptsächlich in einer Single-Threaded-Ausführungsumgebung arbeiteten.

Anfangs hatte ich die Idee, ein Projekt zu übernehmen, das ich nicht in angemessener Zeit abschließen konnte, und so meinen Twitch-Followern zu zeigen, dass es Projekte gibt, die selbst ich nicht schaffen kann. Während meines ersten Streams wurde mir plötzlich klar, dass die Aufgabe, Surreal Engine C++ mit Emscripten auf WebAssembly zu portieren, machbar ist.

Surreal Engine Emscripten Demo

Nach einem Monat kann ich meine Gabel- und Motorbaugruppe auf WebAssembly demonstrieren:
https://demensdeum.com/demos/SurrealEngine/

Die Steuerung erfolgt wie im Original über die Tastaturpfeile. Als nächstes plane ich, es für die mobile Steuerung (Tachi) anzupassen und dabei die richtige Beleuchtung und andere grafische Funktionen des Unreal Tournament 99-Renderings hinzuzufügen.

Wo soll ich anfangen?

Das erste, was ich sagen möchte, ist, dass jedes Projekt mit Emscripten von C++ nach WebAssembly portiert werden kann. Die Frage ist nur, wie vollständig die Funktionalität sein wird. Wählen Sie ein Projekt, dessen Bibliotheksports bereits für Emscripten verfügbar sind; im Fall von Surreal Engine haben Sie großes Glück, denn Die Engine verwendet die Bibliotheken SDL 2, OpenAL – Sie sind beide auf Emscripten portiert. Allerdings kommt als Grafik-API Vulkan zum Einsatz, was aktuell nicht für HTML5 verfügbar ist, an der Implementierung von WebGPU wird gearbeitet, befindet sich aber ebenfalls im Entwurfsstadium und es ist auch unbekannt, wie einfach die weitere Portierung von Vulkan auf WebGPU sein wird , nachdem es vollständig standardisiert ist. Daher musste ich mein eigenes grundlegendes OpenGL-ES/WebGL-Rendering für die Surreal Engine schreiben.

Erstellung des Projekts

System in Surreal Engine erstellen – CMake, was auch die Portierung vereinfacht, weil Emscripten stellt seinen nativen Buildern – emcmake, emmake.
Die Surreal Engine-Portierung basierte auf dem Code meines neuesten Spiels in WebGL/OpenGL ES und C++ namens Death-Mask. Dadurch war die Entwicklung viel einfacher, ich hatte alle notwendigen Build-Flags und Codebeispiele dabei.

Einer der wichtigsten Punkte in CMakeLists.txt sind die Build-Flags für Emscripten, unten ist ein Beispiel aus der Projektdatei:


-s MAX_WEBGL_VERSION=2 \

-s EXCEPTION_DEBUG \

-fexceptions \

--preload-file UnrealTournament/ \

--preload-file SurrealEngine.pk3 \

--bind \

--use-preload-plugins \

-Wall \

-Wextra \

-Werror=return-type \

-s USE_SDL=2 \

-s ASSERTIONS=1 \

-w \

-g4 \

-s DISABLE_EXCEPTION_CATCHING=0 \

-O3 \

--no-heap-copy \

-s ALLOW_MEMORY_GROWTH=1 \

-s EXIT_RUNTIME=1")

Das Build-Skript selbst:


emmake make -j 16

cp SurrealEngine.data /srv/http/SurrealEngine/SurrealEngine.data

cp SurrealEngine.js /srv/http/SurrealEngine/SurrealEngine.js

cp SurrealEngine.wasm /srv/http/SurrealEngine/SurrealEngine.wasm

cp ../buildScripts/Emscripten/index.html /srv/http/SurrealEngine/index.html

cp ../buildScripts/Emscripten/background.png /srv/http/SurrealEngine/background.png

Als nächstes bereiten wir den Index vor .html , das den Projektdateisystem-Preloader enthält. Zum Hochladen ins Web habe ich die Unreal Tournament Demo-Version 338 verwendet. Wie Sie der CMake-Datei entnehmen können, wurde der entpackte Spielordner zum Build-Verzeichnis hinzugefügt und als Preload-Datei für Emscripten verlinkt.

Hauptcodeänderungen

Dann war es notwendig, die Spielschleife des Spiels zu ändern, man kann keine Endlosschleife ausführen, das führt zum Einfrieren des Browsers, stattdessen muss man emscripten_set_main_loop verwenden, über diese Funktion habe ich in meiner Notiz von 2017 geschrieben „< a href="https://demensdeum.com /blog/ru/2017/03/29/porting-sdl-c-game-to-html5-emscripten/" rel="noopener" target="_blank">SDL C++-Spiel auf HTML5 (Emscripten) portieren“
Wir ändern den Code zum Beenden der while-Schleife in if, zeigen dann die Hauptklasse der Spiel-Engine, die die Spielschleife enthält, im globalen Bereich an und schreiben eine globale Funktion, die den Spielschleifenschritt vom globalen Objekt aus aufruft :


#include <emscripten.h>

Engine *EMSCRIPTEN_GLOBAL_GAME_ENGINE = nullptr;

void emscripten_game_loop_step() {

	EMSCRIPTEN_GLOBAL_GAME_ENGINE->Run();

}

#endif

Danach müssen Sie sicherstellen, dass in der Anwendung keine Hintergrundthreads vorhanden sind. Wenn ja, dann bereiten Sie sich darauf vor, diese für die Single-Thread-Ausführung neu zu schreiben, oder verwenden Sie die phtread-Bibliothek in Emscripten.
Der Hintergrund-Thread in Surreal Engine wird zum Abspielen von Musik verwendet. Vom Haupt-Engine-Thread kommen Daten über den aktuellen Titel, die Notwendigkeit, Musik abzuspielen, oder dessen Fehlen. Anschließend erhält der Hintergrund-Thread über einen Mutex einen neuen Status und beginnt mit der Wiedergabe neuer Musik , oder pausiert es. Der Hintergrundstream wird auch zum Puffern von Musik während der Wiedergabe verwendet.
Meine Versuche, die Surreal Engine für Emscripten mit pthread zu erstellen, waren erfolglos, da die SDL2- und OpenAL-Ports ohne pthread-Unterstützung erstellt wurden und ich sie nicht aus Gründen der Musik neu erstellen wollte. Daher habe ich die Funktionalität des Hintergrundmusik-Streams mithilfe einer Schleife auf die Single-Threaded-Ausführung übertragen. Durch das Entfernen von pthread-Aufrufen aus dem C++-Code habe ich die Pufferung und Musikwiedergabe in den Hauptthread verschoben, damit es keine Verzögerungen gibt, ich habe den Puffer um einige Sekunden erhöht.

Als nächstes werde ich spezifische Implementierungen von Grafik und Sound beschreiben.

Vulkan wird nicht unterstützt!

Ja, Vulkan wird in HTML5 nicht unterstützt, obwohl alle Marketingbroschüren die plattformübergreifende und breite Plattformunterstützung als Hauptvorteil von Vulkan darstellen. Aus diesem Grund musste ich meinen eigenen grundlegenden Grafikrenderer für einen vereinfachten OpenGL-Typ schreiben – ES, es wird auf mobilen Geräten verwendet, enthält manchmal nicht die modischen Funktionen des modernen OpenGL, lässt sich aber sehr gut auf WebGL portieren, was genau das ist, was Emscripten implementiert. Das Schreiben des grundlegenden Kachel-Renderings, des BSP-Renderings für die einfachste GUI-Anzeige und des Renderns von Modellen und Karten wurde in zwei Wochen abgeschlossen. Dies war vielleicht der schwierigste Teil des Projekts. Es liegt noch viel Arbeit vor uns, die volle Funktionalität des Surreal Engine-Renderings zu implementieren, daher ist jede Hilfe von Lesern in Form von Code und Pull-Requests willkommen.

OpenAL unterstützt!

Das große Glück ist, dass Surreal Engine OpenAL für die Audioausgabe verwendet. Nachdem ich eine einfache Hallo-Welt in OpenAL geschrieben und sie mit Emscripten in WebAssembly zusammengestellt hatte, wurde mir klar, wie einfach alles war, und ich machte mich an die Portierung des Sounds.
Nach mehreren Stunden des Debuggens stellte sich heraus, dass die OpenAL-Implementierung von Emscripten mehrere Fehler aufweist. Beispielsweise gab die Methode beim Initialisieren des Lesens der Anzahl der Monokanäle eine unendliche Zahl zurück, und nachdem versucht wurde, einen Vektor unendlicher Größe zu initialisieren, C++ stürzt mit der Ausnahme vector::length_error ab.

Wir haben es geschafft, dies zu umgehen, indem wir die Anzahl der Monokanäle auf 2048 fest codiert haben:


		alcGetIntegerv(alDevice, ALC_STEREO_SOURCES, 1, &stereoSources);



#if __EMSCRIPTEN__

		monoSources = 2048; // for some reason Emscripten's OpenAL gives infinite monoSources count, bug?

#endif

Gibt es ein Netzwerk?

Surreal Engine unterstützt derzeit kein Online-Spielen, das Spielen mit Bots wird unterstützt, aber wir brauchen jemanden, der KI für diese Bots schreibt. Theoretisch können Sie mithilfe von Websockets ein Netzwerkspiel auf WebAssembly/Emscripten implementieren.

Schlussfolgerung

Abschließend möchte ich sagen, dass die Portierung der Surreal Engine aufgrund der Verwendung von Bibliotheken, für die es Emscripten-Portierungen gibt, sowie meiner bisherigen Erfahrung bei der Implementierung eines Spiels in C++ für WebAssembly recht reibungslos verlief auf Emscripten. Nachfolgend finden Sie Links zu Wissensquellen und Repositories zum Thema.
M-M-M-MONSTER TÖTEN!

Außerdem, wenn Sie dem Projekt helfen möchten, vorzugsweise mit WebGL/OpenGL ES-Rendering-Code, dann schreiben Sie mir per Telegram:
https://t.me/demenscave

Links

https://demensdeum.com/demos/SurrealEngine/
https://github.com/demensdeum/SurrealEngine-Emscripten

https://github.com/dpjudas/SurrealEngine

Schalten Sie die Hintergrundbeleuchtung der USB-Tastatur unter macOS ein

Ich habe kürzlich eine sehr preiswerte Getorix GK-45X USB-Tastatur mit RGB-Hintergrundbeleuchtung gekauft. Nachdem ich es an ein MacBook Pro mit M1-Prozessor angeschlossen hatte, stellte sich heraus, dass die RGB-Hintergrundbeleuchtung nicht funktionierte. Selbst durch Drücken der magischen Kombination Fn + Scroll Lock konnte die Hintergrundbeleuchtung nicht eingeschaltet werden; nur die Hintergrundbeleuchtung des MacBook-Bildschirms änderte sich.
Es gibt mehrere Lösungen für dieses Problem, nämlich OpenRGB (funktioniert nicht), HID-LED-Test (funktioniert nicht). Nur das Dienstprogramm kvmswitch hat funktioniert:
https://github.com/stoutput/OSX-KVM

Sie müssen es von GitHub herunterladen und die Ausführung über das Terminal im Bereich „Sicherheit“ der Systemeinstellungen zulassen.
Wie ich der Beschreibung entnehme, sendet das Dienstprogramm nach dem Start einen Tastendruck auf Fn + Scroll Lock und schaltet so die Hintergrundbeleuchtung der Tastatur ein/aus.

Baumsortierung

Baumsortierung – Sortierung mithilfe eines binären Suchbaums. Zeitkomplexität – O(n²). In einem solchen Baum hat jeder Knoten links Zahlen, die kleiner sind als der Knoten, rechts sind es mehr als der Knoten. Wenn wir von der Wurzel kommen und die Werte von links nach rechts drucken, erhalten wir eine sortierte Liste von Zahlen . Überraschend, oder?

Betrachten Sie das binäre Suchbaumdiagramm:

Derrick Coetzee (gemeinfrei)

Versuchen Sie, die Zahlen manuell abzulesen, beginnend beim vorletzten linken Knoten der unteren linken Ecke, für jeden Knoten links – einen Knoten – rechts.

Es wird so aussehen:

  1. Vorletzter Knoten unten links – 3.
  2. Es hat einen linken Zweig – 1.
  3. Nehmen Sie diese Nummer (1)
  4. Als nächstes nehmen wir Scheitelpunkt 3 (1, 3)
  5. Auf der rechten Seite befindet sich Zweig 6, der jedoch Zweige enthält. Deshalb lesen wir es genauso.
  6. Linker Zweig von Knoten 6 Nummer 4 (1, 3, 4)
  7. Der Knoten selbst ist 6 (1, 3, 4, 6)
  8. Rechts 7 (1, 3, 4, 6, 7)
  9. Gehen Sie zum Wurzelknoten hoch – 8 (1,3, 4,6, 7, 8)
  10. Alles auf der rechten Seite drucken wir analog aus
  11. Wir erhalten die endgültige Liste – 1, 3, 4, 6, 7, 8, 10, 13, 14

Um den Algorithmus im Code zu implementieren, benötigen Sie zwei Funktionen:

  1. Zusammenstellen eines binären Suchbaums
  2. Den binären Suchbaum in der richtigen Reihenfolge ausdrucken

Der binäre Suchbaum wird auf die gleiche Weise zusammengestellt, wie er gelesen wird. An jeden Knoten wird links oder rechts eine Zahl angehängt, je nachdem, ob er kleiner oder größer ist.

Beispiel in Lua:


function Node:new(value, lhs, rhs)
    output = {}
    setmetatable(output, self)
    self.__index = self  
    output.value = value
    output.lhs = lhs
    output.rhs = rhs
    output.counter = 1
    return output  
end

function Node:Increment()
    self.counter = self.counter + 1
end

function Node:Insert(value)
    if self.lhs ~= nil and self.lhs.value > value then
        self.lhs:Insert(value)
        return
    end

    if self.rhs ~= nil and self.rhs.value < value then
        self.rhs:Insert(value)
        return
    end

    if self.value == value then
        self:Increment()
        return
    elseif self.value > value then
        if self.lhs == nil then
            self.lhs = Node:new(value, nil, nil)
        else
            self.lhs:Insert(value)
        end
        return
    else
        if self.rhs == nil then
            self.rhs = Node:new(value, nil, nil)
        else
            self.rhs:Insert(value)
        end
        return
    end
end

function Node:InOrder(output)
    if self.lhs ~= nil then
       output = self.lhs:InOrder(output)
    end
    output = self:printSelf(output)
    if self.rhs ~= nil then
        output = self.rhs:InOrder(output)
    end
    return output
end

function Node:printSelf(output)
    for i=0,self.counter-1 do
        output = output .. tostring(self.value) .. " "
    end
    return output
end

function PrintArray(numbers)
    output = ""
    for i=0,#numbers do
        output = output .. tostring(numbers[i]) .. " "
    end    
    print(output)
end

function Treesort(numbers)
    rootNode = Node:new(numbers[0], nil, nil)
    for i=1,#numbers do
        rootNode:Insert(numbers[i])
    end
    print(rootNode:InOrder(""))
end


numbersCount = 10
maxNumber = 9

numbers = {}

for i=0,numbersCount-1 do
    numbers[i] = math.random(0, maxNumber)
end

PrintArray(numbers)
Treesort(numbers)

Важный нюанс что для чисел которые равны вершине придумано множество интересных механизмов подцепления к ноде, я же просто добавил счетчик к классу вершины, при распечатке числа возвращаются по счетчику.

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/treesort

Источники

TreeSort Algorithm Explained and Implemented with Examples in Java | Sorting Algorithms | Geekific – YouTube

Tree sort – YouTube

Convert Sorted Array to Binary Search Tree (LeetCode 108. Algorithm Explained) – YouTube

Sorting algorithms/Tree sort on a linked list – Rosetta Code

Tree Sort – GeeksforGeeks

Tree sort – Wikipedia

How to handle duplicates in Binary Search Tree? – GeeksforGeeks

Tree Sort | GeeksforGeeks – YouTube

Eimersortierung

Bucket Sort – Sortierung nach Buckets. Der Algorithmus ähnelt der Zählsortierung, mit dem Unterschied, dass die Zahlen in „Buckets“-Bereichen gesammelt werden, dann die Buckets mit einem anderen, ausreichend produktiven Sortieralgorithmus sortiert werden und der letzte Schritt darin besteht, den „Buckets“-Bereich zu entfalten um eins, was zu einer sortierten Liste führt

Die zeitliche Komplexität des Algorithmus beträgt O(nk). Der Algorithmus arbeitet in linearer Zeit für Daten, die einem Gleichverteilungsgesetz gehorchen. Vereinfacht ausgedrückt müssen die Elemente in einem bestimmten Bereich liegen, ohne „Spitzen“, zum Beispiel Zahlen von 0,0 bis 1,0. Wenn unter solchen Zahlen 4 oder 999 sind, dann gilt eine solche Reihe nach den Hofgesetzen nicht mehr als „gerade“.

Implementierungsbeispiel in Julia:

    buckets = Vector{Vector{Int}}()
    
    for i in 0:bucketsCount - 1
        bucket = Vector{Int}()
        push!(buckets, bucket)
    end

    maxNumber = maximum(numbers)

    for i in 0:length(numbers) - 1
        bucketIndex = 1 + Int(floor(bucketsCount * numbers[1 + i] / (maxNumber + 1)))
        push!(buckets[bucketIndex], numbers[1 + i])
    end

    for i in 0:length(buckets) - 1
        bucketIndex = 1 + i
        buckets[bucketIndex] = sort(buckets[bucketIndex])
    end

    flat = [(buckets...)...]
    print(flat, "\n")

end

numbersCount = 10
maxNumber = 10
numbers = rand(1:maxNumber, numbersCount)
print(numbers,"\n")
bucketsCount = 10
bucketSort(numbers, bucketsCount)

На производительность алгоритма также влияет число ведер, для большего количества чисел лучше взять большее число ведер (Algorithms in a nutshell by George T. Heineman)

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/bucketSort

Источники

https://www.youtube.com/watch?v=VuXbEb5ywrU
https://www.youtube.com/watch?v=ELrhrrCjDOA
https://medium.com/karuna-sehgal/an-introduction-to-bucket-sort-62aa5325d124
https://www.geeksforgeeks.org/bucket-sort-2/
https://ru.wikipedia.org/wiki/%D0%91%D0%BB%D0%BE%D1%87%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
https://www.youtube.com/watch?v=LPrF9yEKTks
https://en.wikipedia.org/wiki/Bucket_sort
https://julialang.org/
https://www.oreilly.com/library/view/algorithms-in-a/9780596516246/ch04s08.html

Radixsort

Radix-Sortierung – Basissortierung. Der Algorithmus ähnelt der Zählsortierung darin, dass es keinen Vergleich von Elementen gibt; stattdessen werden Elemente *Zeichen für Zeichen* in *Buckets* (Buckets) gruppiert, der Bucket wird anhand des Index des aktuellen Zahlenzeichens ausgewählt. Zeitkomplexität – O(nd).

Es funktioniert ungefähr so:

  • Die Eingabe erfolgt aus den Zahlen 6, 12, 44, 9
  • Wir werden 10 Buckets mit Listen (0-9) erstellen, in die wir Zahlen Stück für Stück hinzufügen/sortieren.

Weiter:

  1. Starten Sie eine Schleife mit Zähler i bis zur maximalen Anzahl von Zeichen in der Zahl
  2. Durch den Index i von rechts nach links erhalten wir ein Symbol für jede Zahl; wenn es kein Symbol gibt, dann gehen wir davon aus, dass es Null ist
  3. Konvertieren Sie das Symbol in eine Zahl
  4. Wählen Sie einen Bucket nach Indexnummer aus und geben Sie dort die ganze Zahl ein
  5. Nachdem Sie mit der Suche durch die Zahlen fertig sind, wandeln Sie alle Buckets wieder in eine Zahlenliste um
  6. Erhalten Sie Zahlen nach Rang sortiert
  7. Wiederholen Sie den Vorgang, bis alle Ziffern verschwunden sind

Beispiel für Radix-Sortierung in Scala:


import scala.util.Random.nextInt



object RadixSort {

    def main(args: Array[String]) = {

        var maxNumber = 200

        var numbersCount = 30

        var maxLength = maxNumber.toString.length() - 1



        var referenceNumbers = LazyList.continually(nextInt(maxNumber + 1)).take(numbersCount).toList

        var numbers = referenceNumbers

        

        var buckets = List.fill(10)(ListBuffer[Int]())



        for( i <- 0 to maxLength) { numbers.foreach( number => {

                    var numberString = number.toString

                    if (numberString.length() > i) {

                        var index = numberString.length() - i - 1

                        var character = numberString.charAt(index).toString

                        var characterInteger = character.toInt  

                        buckets.apply(characterInteger) += number

                    }

                    else {

                        buckets.apply(0) += number

                    }

                }

            )

            numbers = buckets.flatten

            buckets.foreach(x => x.clear())

        }

        println(referenceNumbers)

        println(numbers)

        println(s"Validation result: ${numbers == referenceNumbers.sorted}")

    }

}

Der Algorithmus verfügt auch über eine Version zur parallelen Ausführung, beispielsweise auf einer GPU; Es gibt auch eine Möglichkeit zum Sortieren von Bits, die sehr interessant und wirklich atemberaubend sein muss!

Links

https://gitlab .com/demensdeum/algorithms/-/blob/master/sortAlgorithms/radixSort/radixSort.scala

Quellen

https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%80%D0%B0%D0%B7%D1%80%D1%8F%D 0%B4%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0% BA%D0%B0
https://www.geeksforgeeks.org/radix-sort/

https://www.youtube.com/watch?v=toAlAJKojos

https://github.com/gyatskov/radix-sort

Haufensort

Heapsort – Pyramidensortierung. Zeitliche Komplexität des Algorithmus – O(n log n), schnell, oder? Ich würde das Sortieren das Sortieren fallender Kieselsteine ​​nennen. Es scheint mir, dass man es am einfachsten visuell erklären kann.

Die Eingabe ist eine Liste von Zahlen, zum Beispiel:
5, 0, 7, 2, 3, 9, 4

Von links nach rechts wird eine Datenstruktur erstellt – ein Binärbaum, oder wie ich es nenne – Pyramide. Pyramidenelemente können maximal zwei untergeordnete Elemente, aber nur ein oberstes Element haben.

Lassen Sie uns einen Binärbaum erstellen:
⠀⠀5
⠀0⠀7
2 3 9 4

Wenn Sie die Pyramide längere Zeit betrachten, können Sie erkennen, dass es sich nur um Zahlen aus einer Reihe handelt, die nacheinander auftauchen. Die Anzahl der Elemente in jeder Etage wird mit zwei multipliziert.

Als nächstes beginnt der Spaß: Sortieren wir die Pyramide von unten nach oben mit der Methode der fallenden Kieselsteine ​​(aufhäufen). Mit dem Sortieren könnte man ab der letzten Etage beginnen (2 3 9 4), aber es hat keinen Sinn, weil Es gibt keine Etage darunter, in die man fallen könnte.

Daher beginnen wir, Elemente aus der vorletzten Etage (0 7) fallen zu lassen
⠀⠀5
⠀0⠀7
2 3 9 4

Das erste fallende Element wird von rechts ausgewählt, in unserem Fall ist es 7, dann schauen wir uns an, was darunter liegt, und darunter sind 9 und 4, neun ist größer als vier, und auch neun ist größer als Sieben! Wir lassen 7 auf 9 fallen und heben 9 auf Platz 7.
⠀⠀5
⠀0⠀9
2 3 7 4

Als nächstes verstehen wir, dass die Sieben nirgendwo tiefer fallen kann, und gehen weiter zur Zahl 0, die sich im vorletzten Stockwerk auf der linken Seite befindet:
⠀⠀5
⠀0⠀9
2 3 7 4

Mal sehen, was sich darunter verbirgt – 2 und 3, zwei ist kleiner als drei, drei ist mehr als null, also vertauschen wir null und drei:
⠀⠀5
⠀3⠀9
2 0 7 4

Wenn Sie das Ende der Etage erreichen, gehen Sie in die darüber liegende Etage und lassen Sie dort, wenn möglich, alles ab.
Das Ergebnis ist eine Datenstruktur – ein Heap, nämlich Max Heap, weil Oben ist das größte Element:
⠀⠀9
⠀3⠀7
2 0 5 4

Wenn Sie es in eine Array-Darstellung zurückführen, erhalten Sie eine Liste:
[9, 3, 7, 2, 0, 5, 4]

Daraus können wir schließen, dass wir durch Vertauschen des ersten und letzten Elements die erste Zahl an der endgültigen sortierten Position erhalten, nämlich 9 sollte am Ende der sortierten Liste stehen, Plätze vertauschen:
[4, 3, 7, 2, 0, 5, 9]

Sehen wir uns einen Binärbaum an:
⠀⠀4
⠀3⠀7
2 0 5 9

Das Ergebnis ist eine Situation, in der der untere Teil des Baums sortiert ist. Sie müssen lediglich 4 an der richtigen Position ablegen, den Algorithmus wiederholen, aber die bereits sortierten Zahlen, nämlich 9, nicht berücksichtigen:
⠀⠀4
⠀3⠀7
2 0 5 9

⠀⠀7
⠀3⠀4
2 0 5 9

⠀⠀7
⠀3⠀5
2 0 4 9

Es stellte sich heraus, dass wir, nachdem wir 4 verloren hatten, die nächstgrößte Zahl nach 9 erhöht hatten – 7. Vertauschen Sie die letzte unsortierte Zahl (4) und die größte Zahl (7)
⠀⠀4
⠀3⠀5
2 0 7 9

Es stellt sich heraus, dass wir jetzt zwei Zahlen an der richtigen Endposition haben:
4, 3, 5, 2, 0, 7, 9

Als nächstes wiederholen wir den Sortieralgorithmus und ignorieren die bereits sortierten. Am Ende erhalten wir ein Heap Typ:
⠀⠀0
⠀2⠀3
4 5 7 9

Oder als Liste:
0, 2, 3, 4, 5, 7, 9

Implementierung

Der Algorithmus ist normalerweise in drei Funktionen unterteilt:

  1. Einen Heap erstellen
  2. Sifting-Algorithmus (Heapify)
  3. Ersetzen des letzten unsortierten Elements durch das erste

Der Heap wird erstellt, indem die vorletzte Zeile des Binärbaums mithilfe der Heapify-Funktion von rechts nach links bis zum Ende des Arrays durchlaufen wird. Als nächstes im Zyklus erfolgt die erste Ersetzung der Zahlen, danach fällt/bleibt das erste Element an Ort und Stelle, wodurch das größte Element an die erste Stelle fällt, der Zyklus wird mit einer Verringerung der Teilnehmerzahl um eins wiederholt, weil Nach jedem Durchlauf bleiben sortierte Zahlen am Ende der Liste.

Heapsort-Beispiel in Ruby:






module Colors



    BLUE = "\033[94m"



    RED = "\033[31m"



    STOP = "\033[0m"



end







def heapsort(rawNumbers)



    numbers = rawNumbers.dup







    def swap(numbers, from, to)



        temp = numbers[from]



        numbers[from] = numbers[to]



        numbers[to] = temp



    end







    def heapify(numbers)



        count = numbers.length()



        lastParentNode = (count - 2) / 2







        for start in lastParentNode.downto(0)



            siftDown(numbers, start, count - 1)



            start -= 1 



        end







        if DEMO



            puts "--- heapify ends ---"



        end



    end







    def siftDown(numbers, start, rightBound)      



        cursor = start



        printBinaryHeap(numbers, cursor, rightBound)







        def calculateLhsChildIndex(cursor)



            return cursor * 2 + 1



        end







        def calculateRhsChildIndex(cursor)



            return cursor * 2 + 2



        end            







        while calculateLhsChildIndex(cursor) <= rightBound



            lhsChildIndex = calculateLhsChildIndex(cursor)



            rhsChildIndex = calculateRhsChildIndex(cursor)







            lhsNumber = numbers[lhsChildIndex]



            biggerChildIndex = lhsChildIndex







            if rhsChildIndex <= rightBound



                rhsNumber = numbers[rhsChildIndex]



                if lhsNumber < rhsNumber



                    biggerChildIndex = rhsChildIndex



                end



            end







            if numbers[cursor] < numbers[biggerChildIndex]



                swap(numbers, cursor, biggerChildIndex)



                cursor = biggerChildIndex



            else



                break



            end



            printBinaryHeap(numbers, cursor, rightBound)



        end



        printBinaryHeap(numbers, cursor, rightBound)



    end







    def printBinaryHeap(numbers, nodeIndex = -1, rightBound = -1)



        if DEMO == false



            return



        end



        perLineWidth = (numbers.length() * 4).to_i



        linesCount = Math.log2(numbers.length()).ceil()



        xPrinterCount = 1



        cursor = 0



        spacing = 3



        for y in (0..linesCount)



            line = perLineWidth.times.map { " " }



            spacing = spacing == 3 ? 4 : 3



            printIndex = (perLineWidth / 2) - (spacing * xPrinterCount) / 2



            for x in (0..xPrinterCount - 1)



                if cursor >= numbers.length



                    break



                end



                if nodeIndex != -1 && cursor == nodeIndex



                    line[printIndex] = "%s%s%s" % [Colors::RED, numbers[cursor].to_s, Colors::STOP]



                elsif rightBound != -1 && cursor > rightBound



                    line[printIndex] = "%s%s%s" % [Colors::BLUE, numbers[cursor].to_s, Colors::STOP]



                else



                    line[printIndex] = numbers[cursor].to_s



                end



                cursor += 1



                printIndex += spacing



            end



            print line.join()



            xPrinterCount *= 2           



            print "\n"            



        end



    end







    heapify(numbers)



    rightBound = numbers.length() - 1







    while rightBound > 0



        swap(numbers, 0, rightBound)   



        rightBound -= 1



        siftDown(numbers, 0, rightBound)     



    end







    return numbers



end







numbersCount = 14



maximalNumber = 10



numbers = numbersCount.times.map { Random.rand(maximalNumber) }



print numbers



print "\n---\n"







start = Time.now



sortedNumbers = heapsort(numbers)



finish = Time.now



heapSortTime = start - finish







start = Time.now



referenceSortedNumbers = numbers.sort()



finish = Time.now



referenceSortTime = start - finish







print "Reference sort: "



print referenceSortedNumbers



print "\n"



print "Reference sort time: %f\n" % referenceSortTime



print "Heap sort:      "



print sortedNumbers



print "\n"



if DEMO == false



    print "Heap sort time:      %f\n" % heapSortTime



else



    print "Disable DEMO for performance measure\n"



end







if sortedNumbers != referenceSortedNumbers



    puts "Validation failed"



    exit 1



else



    puts "Validation success"



    exit 0



end

Dieser Algorithmus ist ohne Visualisierung nicht leicht zu verstehen, daher empfehle ich als Erstes, eine Funktion zu schreiben, die die aktuelle Ansicht des Binärbaums druckt.

Links

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/heapsort/heapsort.rb

Quellen

http://rosettacode.org/wiki/Sorting_algorithms/Heapsort
https://www.youtube.com/watch?v=LbB357_RwlY

https://habr.com/ru/company/ otus/blog/460087/

https://ru.wikipedia.org/wiki/Pyramid_sort

https://neerc.ifmo.ru/wiki /index.php?title=Heap_sort

https://wiki5.ru/wiki/Heapsort

https://wiki.c2.com/?HeapSort

https://ru.wikipedia.org/wiki/Tree (Datenstruktur)

https://ru.wikipedia.org/wiki/Heap (Datenstruktur)

https://www.youtube.com/watch?v=2DmK_H7IdTo

https://www.youtube.com/watch?v=kU4KBD4NFtw

https://www.youtube.com/watch?v=DU1uG5310x0

https://www.youtube.com/watch?v =BzQGPA_v-vc

https://www.geeksforgeeks.org/ array-representation-of-binary-heap/

https://habr.com/ru/post/112222/

https://www.cs.usfca. edu/~galles/visualization/BST.html

https://www.youtube.com/watch?v=EQzqHWtsKq4

https://medium.com/@dimko1/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC% D1 %8B-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-heapsort-796ba965018b

https://ru.wikibrief.org/wiki/Heapsort

https://www.youtube.com/watch?v=GUUpmrTnNbw

Bumblebee All Troubles

Recently, it turned out that users of modern Nvidia GPUs under Arch Linux do not need to use the bumblebee package at all, for example, for me it did not detect an external monitor when connected. I recommend removing the bumblebee package and all related packages, and installing prime using the instructions on the Arch Wiki.
Next, to launch all games on Steam and 3D applications, add prime-run, for Steam this is done like this prime-run %command% in additional launch options.
To check the correctness, you can use glxgears, prime-run glxgears.
https://bbs.archlinux.org/viewtopic.php? pid=2048195#p2048195

Quicksort

Quicksort ist ein Sortieralgorithmus nach dem Prinzip „Teile und herrsche“. Rekursiv, Stück für Stück, analysieren wir das Zahlenarray, ordnen die Zahlen ausgehend vom ausgewählten Referenzelement in kleinerer und größerer Reihenfolge an und fügen das Referenzelement selbst in den Cutoff zwischen ihnen ein. Nach mehreren rekursiven Iterationen erhalten Sie eine sortierte Liste. Zeitkomplexität O(n2).

Schema:

  1. Wir beginnen damit, eine Liste von Elementen von außen zu erhalten, die Sortiergrenzen. Im ersten Schritt werden die Sortiergrenzen von Anfang bis Ende festgelegt.
  2. Überprüfen Sie, dass sich die Start- und Endgrenzen nicht überschneiden. Wenn dies passiert, ist es Zeit, den Vorgang abzuschließen
  3. Wählen Sie ein Element aus der Liste aus und nennen Sie es Pivot
  4. Bewegen Sie es am letzten Index nach rechts bis zum Ende, damit es nicht im Weg ist
  5. Erstellen Sie einen Zähler mit *kleineren Zahlen*, die immer noch Null sind
  6. Durchlaufen Sie die Liste von links nach rechts, bis einschließlich zum letzten Index, an dem sich das Referenzelement befindet
  7. Wir vergleichen jedes Element mit dem Referenzelement
  8. Wenn er kleiner als der Referenzwert ist, tauschen wir ihn entsprechend dem Index des Zählers kleinerer Zahlen aus. Erhöhen Sie den Zähler kleinerer Zahlen.
  9. Wenn die Schleife das Stützelement erreicht, halten wir an und tauschen das Stützelement mit dem Element entsprechend dem Zähler der kleineren Zahlen aus.
  10. Wir führen den Algorithmus separat für den kleineren linken Teil der Liste und separat für den größeren rechten Teil der Liste aus.
  11. Infolgedessen werden alle rekursiven Iterationen aufgrund des Eincheckpunkts 2 angehalten
  12. Erhalten Sie eine sortierte Liste

Quicksort wurde vom Wissenschaftler Charles Anthony Richard Hoare an der Moskauer Staatsuniversität erfunden. Nachdem er Russisch gelernt hatte, studierte er Computerübersetzung sowie Wahrscheinlichkeitstheorie an der Kolmogorov-Schule. 1960 verließ er aufgrund der politischen Krise die Sowjetunion.

Beispielimplementierung in Rust:


use rand::Rng;

fn swap(numbers: &mut [i64], from: usize, to: usize) {
    let temp = numbers[from];
    numbers[from] = numbers[to];
    numbers[to] = temp;
}

fn quicksort(numbers: &mut [i64], left: usize, right: usize) {
    if left >= right {
        return
    }
    let length = right - left;
    if length <= 1 {
        return
    }
    let pivot_index = left + (length / 2);
    let pivot = numbers[pivot_index];

    let last_index = right - 1;
    swap(numbers, pivot_index, last_index);

    let mut less_insert_index = left;

    for i in left..last_index {
        if numbers[i] < pivot {
            swap(numbers, i, less_insert_index);
            less_insert_index += 1;
        }
    }
    swap(numbers, last_index, less_insert_index);
    quicksort(numbers, left, less_insert_index);
    quicksort(numbers, less_insert_index + 1, right);
}

fn main() {
    let mut numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    let mut reference_numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

    let mut rng = rand::thread_rng();
    for i in 0..numbers.len() {
        numbers[i] = rng.gen_range(-10..10);
        reference_numbers[i] = numbers[i];
    }

    reference_numbers.sort();

  println!("Numbers           {:?}", numbers);
  let length = numbers.len();
  quicksort(&mut numbers, 0, length);
  println!("Numbers           {:?}", numbers);
  println!("Reference numbers {:?}", reference_numbers);

  if numbers != reference_numbers {
    println!("Validation failed");
    std::process::exit(1);
  }
  else {
    println!("Validation success!");
    std::process::exit(0);
  }
}

Wenn nichts klar ist, empfehle ich Ihnen, sich das Video von Rob Edwards von der University of San Diego anzusehen https://www.youtube.com/watch?v=ZHVk2blR45Q Es zeigt ganz einfach Schritt für Schritt das Wesen und die Implementierung des Algorithmus.

Links

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/quickSort

Quellen

https://www.youtube.com/watch?v =4s-aG6yGGLU
https://www.youtube.com/watch?v=ywWBy6J5gz8
https://www.youtube.com/watch?v=Hoixgm4-P4M
https://ru.wikipedia.org/wiki/Быстрая_сортировка
https://www.youtube.com/watch?v=Hoixgm4-P4M
https://www.youtube.com/watch?v=XE4VP_8Y0BU
https://www.youtube.com/watch?v=MZaf_9IZCrc
https://www.youtube.com/watch?v=ZHVk2blR45Q
http://rosettacode.org/wiki/Sorting_algorithms/Quicksort
https://www.youtube.com/watch?v=4s-aG6yGGLU
https://www.youtube.com/watch?v=dQw4w9WgXcQ
https://www.youtube.com/watch?v=maibrCbZWKw
https://www.geeksforgeeks.org/quick-sort/
https://www.youtube.com/watch?v=uXBnyYuwPe8

Binäre Einfügungssortierung

Binary Insertion Sort ist eine Variante der Insertion Sort, bei der die Einfügeposition mithilfe der binären Suche ermittelt wird. Die zeitliche Komplexität des Algorithmus beträgt O(n2)

Der Algorithmus funktioniert folgendermaßen:

  1. Eine Schleife beginnt bei Null bis zum Ende der Liste
  2. In der Schleife wird eine Zahl zum Sortieren ausgewählt, die Zahl wird in einer separaten Variablen gespeichert
  3. Die binäre Suche sucht nach dem Index, um diese Zahl gegen die Zahlen auf der linken Seite einzufügen
  4. Sobald der Index gefunden wurde, werden die Zahlen auf der linken Seite beginnend beim Einfügeindex um eine Position nach rechts verschoben. Dabei wird die zu sortierende Nummer gelöscht.
  5. Die zuvor gespeicherte Nummer wird am Einfügeindex eingefügt
  6. Am Ende der Schleife wird die gesamte Liste sortiert

Bei einer binären Suche kann es sein, dass die Nummer nicht gefunden wird und der Index nicht zurückgegeben wird. Aufgrund der Besonderheit der binären Suche wird die Zahl gefunden, die der gesuchten Zahl am nächsten kommt. Um den Index zurückzugeben, müssen Sie ihn mit der gesuchten Zahl vergleichen. Wenn die gesuchte Zahl kleiner ist, sollte die gesuchte Zahl bei sein der Index links, und wenn größer oder gleich, dann rechts.

Go-Code:


import (
	"fmt"
	"math/rand"
	"time"
)

const numbersCount = 20
const maximalNumber = 100

func binarySearch(numbers []int, item int, low int, high int) int {
	for high > low {
		center := (low + high) / 2
		if numbers[center] < item { low = center + 1 } else if numbers[center] > item {
			high = center - 1
		} else {
			return center
		}
	}

	if numbers[low] < item {
		return low + 1
	} else {
		return low
	}
}

func main() {
	rand.Seed(time.Now().Unix())
	var numbers [numbersCount]int
	for i := 0; i < numbersCount; i++ {
		numbers[i] = rand.Intn(maximalNumber)
	}
	fmt.Println(numbers)

	for i := 1; i < len(numbers); i++ { searchAreaLastIndex := i - 1 insertNumber := numbers[i] insertIndex := binarySearch(numbers[:], insertNumber, 0, searchAreaLastIndex) for x := searchAreaLastIndex; x >= insertIndex; x-- {
			numbers[x+1] = numbers[x]
		}
		numbers[insertIndex] = insertNumber
	}
	fmt.Println(numbers)
}

Links

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/binaryInsertionSort/binaryInsertionSort.go

Quellen

https://www.geeksforgeeks.org/binary-insertion- sort/
https://www.youtube.com/watch?v=-OVB5pOZJug

Muschelsortierung

Shell Sort – eine Variante der Einfügungssortierung mit vorläufiger Kämmung eines Zahlenarrays.

Wir müssen uns daran erinnern, wie die Einfügungssortierung funktioniert:

1. Eine Schleife wird von Null bis zum Ende der Schleife gestartet, wodurch das Array in zwei Teile geteilt wird
2. Für den linken Teil wird eine zweite Schleife gestartet, die Elemente von rechts nach links vergleicht. Das kleinere Element auf der rechten Seite wird gelöscht, bis ein kleineres Element auf der linken Seite gefunden wird
3. Am Ende beider Schleifen erhalten wir eine sortierte Liste

Es war einmal der Informatiker Donald Schell, der sich fragte, wie man den Einfügungssortierungsalgorithmus verbessern könnte. Er kam auch auf die Idee, das Array zunächst in zwei Zyklen zu durchlaufen, jedoch in einem bestimmten Abstand, und den „Kamm“ schrittweise zu verkleinern, bis daraus ein regulärer Einfügungssortierungsalgorithmus wird. Alles ist wirklich so einfach, keine Fallstricke. Zu den beiden oben genannten Zyklen fügen wir einen weiteren hinzu, in dem wir die Größe des „Kamms“ schrittweise reduzieren. Das Einzige, was Sie tun müssen, ist, beim Vergleich den Abstand zu überprüfen, damit er nicht über das Array hinausgeht.

Ein wirklich interessantes Thema ist die Auswahl der Reihenfolge zum Ändern der Vergleichslänge bei jeder Iteration der ersten Schleife. Dies ist deshalb interessant, weil die Leistung des Algorithmus davon abhängt.

Die Tabelle bekannter Optionen und Zeitkomplexität finden Sie hier: https: //en .wikipedia.org/wiki/Shellsort#Gap_sequences

An der Berechnung des idealen Abstands waren verschiedene Personen beteiligt; für sie war dieses Thema offenbar so interessant. Könnten sie nicht einfach Ruby ausführen und den schnellsten sort()-Algorithmus aufrufen?

Im Allgemeinen haben diese seltsamen Leute Dissertationen zum Thema der Berechnung des Abstands/der Lücke des „Kamms“ für den Shell-Algorithmus geschrieben. Ich habe einfach die Ergebnisse ihrer Arbeit verwendet und fünf Arten von Sequenzen überprüft: Hibbard, Knuth-Pratt, Chiura, Sedgwick.

import time
import random
from functools import reduce
import math

DEMO_MODE = False

if input("Demo Mode Y/N? ").upper() == "Y":
    DEMO_MODE = True

class Colors:
    BLUE = '\033[94m'
    RED = '\033[31m'
    END = '\033[0m'

def swap(list, lhs, rhs):
    list[lhs], list[rhs] = list[rhs], list[lhs]
    return list

def colorPrintoutStep(numbers: List[int], lhs: int, rhs: int):
    for index, number in enumerate(numbers):
        if index == lhs:
            print(f"{Colors.BLUE}", end = "")
        elif index == rhs:
            print(f"{Colors.RED}", end = "")
        print(f"{number},", end = "")
        if index == lhs or index == rhs:
            print(f"{Colors.END}", end = "")
        if index == lhs or index == rhs:
            print(f"{Colors.END}", end = "")
    print("\n")
    input(">")

def ShellSortLoop(numbers: List[int], distanceSequence: List[int]):
    distanceSequenceIterator = reversed(distanceSequence)
    while distance:= next(distanceSequenceIterator, None):
        for sortArea in range(0, len(numbers)):
            for rhs in reversed(range(distance, sortArea + 1)):
                lhs = rhs - distance
                if DEMO_MODE:
                    print(f"Distance: {distance}")
                    colorPrintoutStep(numbers, lhs, rhs)
                if numbers[lhs] > numbers[rhs]:
                    swap(numbers, lhs, rhs)
                else:
                    break

def ShellSort(numbers: List[int]):
    global ShellSequence
    ShellSortLoop(numbers, ShellSequence)

def HibbardSort(numbers: List[int]):
    global HibbardSequence
    ShellSortLoop(numbers, HibbardSequence)

def ShellPlusKnuttPrattSort(numbers: List[int]):
    global KnuttPrattSequence
    ShellSortLoop(numbers, KnuttPrattSequence)

def ShellPlusCiuraSort(numbers: List[int]):
    global CiuraSequence
    ShellSortLoop(numbers, CiuraSequence)

def ShellPlusSedgewickSort(numbers: List[int]):
    global SedgewickSequence
    ShellSortLoop(numbers, SedgewickSequence)

def insertionSort(numbers: List[int]):
    global insertionSortDistanceSequence
    ShellSortLoop(numbers, insertionSortDistanceSequence)

def defaultSort(numbers: List[int]):
    numbers.sort()

def measureExecution(inputNumbers: List[int], algorithmName: str, algorithm):
    if DEMO_MODE:
        print(f"{algorithmName} started")
    numbers = inputNumbers.copy()
    startTime = time.perf_counter()
    algorithm(numbers)
    endTime = time.perf_counter()
    print(f"{algorithmName} performance: {endTime - startTime}")

def sortedNumbersAsString(inputNumbers: List[int], algorithm) -> str:
    numbers = inputNumbers.copy()
    algorithm(numbers)
    return str(numbers)

if DEMO_MODE:
    maximalNumber = 10
    numbersCount = 10
else:
    maximalNumber = 10
    numbersCount = random.randint(10000, 20000)

randomNumbers = [random.randrange(1, maximalNumber) for i in range(numbersCount)]

ShellSequenceGenerator = lambda n: reduce(lambda x, _: x + [int(x[-1]/2)], range(int(math.log(numbersCount, 2))), [int(numbersCount / 2)])
ShellSequence = ShellSequenceGenerator(randomNumbers)
ShellSequence.reverse()
ShellSequence.pop()

HibbardSequence = [
    0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095,
    8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575,
    2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727,
    268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591
]

KnuttPrattSequence = [
    1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 
    797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 
    1743392200, 5230176601, 15690529804, 47071589413
]

CiuraSequence = [
            1, 4, 10, 23, 57, 132, 301, 701, 1750, 4376, 
            10941, 27353, 68383, 170958, 427396, 1068491, 
            2671228, 6678071, 16695178, 41737946, 104344866, 
            260862166, 652155416, 1630388541
]

SedgewickSequence = [
            1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905,
            8929, 16001, 36289, 64769, 146305, 260609, 587521, 
            1045505, 2354689, 4188161, 9427969, 16764929, 37730305, 
            67084289, 150958081, 268386305, 603906049, 1073643521, 
            2415771649, 4294770689, 9663381505, 17179475969
]

insertionSortDistanceSequence = [1]

algorithms = {
    "Default Python Sort": defaultSort,
    "Shell Sort": ShellSort,
    "Shell + Hibbard" : HibbardSort,
    "Shell + Prat, Knutt": ShellPlusKnuttPrattSort,
    "Shell + Ciura Sort": ShellPlusCiuraSort,
    "Shell + Sedgewick Sort": ShellPlusSedgewickSort,
    "Insertion Sort": insertionSort
}

for name, algorithm in algorithms.items():
    measureExecution(randomNumbers, name, algorithm)

reference = sortedNumbersAsString(randomNumbers, defaultSort)

for name, algorithm in algorithms.items():
    if sortedNumbersAsString(randomNumbers, algorithm) != reference:
        print("Sorting validation failed")
        exit(1)

print("Sorting validation success")
exit(0)

In meiner Implementierung sind für einen zufälligen Satz von Zahlen die schnellsten Lücken Sedgwick und Hibbard.

mypy

Ich möchte auch den statischen Typisierungsanalysator für Python 3 erwähnen – mypy. Hilft bei der Bewältigung der Probleme, die Sprachen mit dynamischer Eingabe innewohnen, indem es die Möglichkeit ausschließt, etwas dort festzuhalten, wo es nicht benötigt wird.

Wie erfahrene Programmierer sagen: „Statisches Tippen ist nicht erforderlich, wenn Sie ein Team von Profis haben.“ Eines Tages werden wir alle Profis, wir werden Code in völliger Einheit und Verständnis mit Maschinen schreiben, aber im Moment können Sie ähnliche Dienstprogramme verwenden und statisch typisierte Sprachen.

Links

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/shellSort
http://mypy-lang.org/

Quellen

https://dl.acm.org/doi/10.1145/368370.368387
https://en.wikipedia.org/wiki/Shellsort
http://rosettacode.org/wiki/Sorting_algorithms/Shell_sort
https://ru.wikipedia.org/wiki/Сортировка_Шелла
https://neerc.ifmo.ru/wiki/index.php?title=Сортировка_Шелла
https://twitter.com/gvanrossum/status/700741601966985216

Doppelte Auswahlsortierung

Doppelte Auswahlsortierung – eine Unterart der Auswahlsortierung, die anscheinend doppelt so schnell sein sollte. Der Vanilla-Algorithmus durchläuft die Liste der Zahlen doppelt, findet die Mindestzahl und tauscht die Plätze mit der aktuellen Zahl, auf die die Schleife auf der Ebene darüber zeigt. Die Sortierung mit doppelter Auswahl sucht nach den minimalen und maximalen Zahlen und ersetzt dann die beiden Ziffern, auf die die Schleife auf der Ebene darüber zeigt – zwei Zahlen links und rechts. Diese ganze Orgie endet, wenn die Cursor der zu ersetzenden Zahlen in der Mitte der Liste gefunden werden und als Ergebnis sortierte Zahlen links und rechts von der visuellen Mitte erhalten werden.
Die zeitliche Komplexität des Algorithmus ähnelt der von Selection Sort – O(n2), aber angeblich gibt es eine Beschleunigung von 30 %.

Grenzzustand

Bereits in diesem Stadium können Sie sich den Moment einer Kollision vorstellen, zum Beispiel, wenn die Zahl des linken Cursors (die Mindestzahl) auf die Höchstzahl in der Liste zeigt, dann wird die Mindestzahl neu angeordnet, die Neuordnung der Höchstzahl bricht sofort zusammen. Daher beinhalten alle Implementierungen des Algorithmus die Prüfung auf solche Fälle und das Ersetzen von Indizes durch korrekte. In meiner Implementierung hat eine Prüfung gereicht:

  maximalNumberIndex = minimalNumberIndex;
}

Реализация на Cito

Cito – язык либ, язык транслятор. На нем можно писать для C, C++, C#, Java, JavaScript, Python, Swift, TypeScript, OpenCL C, при этом совершенно ничего не зная про эти языки. Исходный код на языке Cito транслируется в исходный код на поддерживаемых языках, далее можно использовать как библиотеку, либо напрямую, исправив сгенеренный код руками. Эдакий Write once – translate to anything.
Double Selection Sort на cito:

{
    public static int[] sort(int[]# numbers, int length)
    {
        int[]# sortedNumbers = new int[length];
        for (int i = 0; i < length; i++) {
            sortedNumbers[i] = numbers[i];
        }
        for (int leftCursor = 0; leftCursor < length / 2; leftCursor++) {
            int minimalNumberIndex = leftCursor;
            int minimalNumber = sortedNumbers[leftCursor];

            int rightCursor = length - (leftCursor + 1);
            int maximalNumberIndex = rightCursor;
            int maximalNumber = sortedNumbers[maximalNumberIndex];

            for (int cursor = leftCursor; cursor <= rightCursor; cursor++) { int cursorNumber = sortedNumbers[cursor]; if (minimalNumber > cursorNumber) {
                    minimalNumber = cursorNumber;
                    minimalNumberIndex = cursor;
                }
                if (maximalNumber < cursorNumber) {
                    maximalNumber = cursorNumber;
                    maximalNumberIndex = cursor;
                }
            }

            if (leftCursor == maximalNumberIndex) {
                maximalNumberIndex = minimalNumberIndex;
            }

            int fromNumber = sortedNumbers[leftCursor];
            int toNumber = sortedNumbers[minimalNumberIndex];
            sortedNumbers[minimalNumberIndex] = fromNumber;
            sortedNumbers[leftCursor] = toNumber;

            fromNumber = sortedNumbers[rightCursor];
            toNumber = sortedNumbers[maximalNumberIndex];
            sortedNumbers[maximalNumberIndex] = fromNumber;
            sortedNumbers[rightCursor] = toNumber;
        }
        return sortedNumbers;
    }
}

Links

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/doubleSelectionSort
https://github.com/pfusik/cito

Quellen

https://www.researchgate.net/publication/330084245_Improved_Double_Selection_Sort_using_Algorithm
http://algolab.valemak.com/selection-double
https://www.geeksforgeeks.org/sorting-algorithm-slightly-improves-selection-sort/

Cocktail-Shaker-Sorte

Cocktail-Shaker-Sortierung – Schüttlersortierung, eine Variante der bidirektionalen Blasensortierung.
Der Algorithmus funktioniert wie folgt:

  1. Die anfängliche Suchrichtung in der Schleife wird ausgewählt (normalerweise von links nach rechts)
  2. Als nächstes werden in der Schleife die Zahlen paarweise überprüft
  3. Wenn das nächste Element größer ist, werden sie vertauscht
  4. Wenn der Suchvorgang abgeschlossen ist, beginnt er erneut mit umgekehrter Richtung
  5. Die Suche wird wiederholt, bis keine Permutationen mehr vorhanden sind

Die zeitliche Komplexität des Algorithmus ist ähnlich wie bei einer Blase – O(n2).

Beispiel für die Implementierung in PHP:

<?php

function cocktailShakeSort($numbers)
{
    echo implode(",", $numbers),"\n";
    $direction = false;
    $sorted = false;
    do {
        $direction = !$direction;        
        $firstIndex = $direction == true ? 0 : count($numbers) - 1;
        $lastIndex = $direction == true ? count($numbers) - 1 : 0;
        
        $sorted = true;
        for (
            $i = $firstIndex;
            $direction == true ? $i < $lastIndex : $i > $lastIndex;
            $direction == true ? $i++ : $i--
        ) {
            $lhsIndex = $direction ? $i : $i - 1;
            $rhsIndex = $direction ? $i + 1 : $i;

            $lhs = $numbers[$lhsIndex];
            $rhs = $numbers[$rhsIndex];

            if ($lhs > $rhs) {
                $numbers[$lhsIndex] = $rhs;
                $numbers[$rhsIndex] = $lhs;
                $sorted = false;
            }
        }
    } while ($sorted == false);

    echo implode(",", $numbers);
}

$numbers = [2, 1, 4, 3, 69, 35, 55, 7, 7, 2, 6, 203, 9];
cocktailShakeSort($numbers);

?>

Ссылки

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/cocktailShakerSort/cocktailShakerSort.php

Источники

https://www.youtube.com/watch?v=njClLBoEbfI
https://www.geeksforgeeks.org/cocktail-sort/
https://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort

…And Primus for All

In this note I will describe the launch of Steam games on the Linux distribution Arch Linux in the configuration of an Intel + Nvidia laptop

Counter-Strike: Global Offensive

The only configuration that worked for me is Primus-vk + Vulkan.

Install the required packages:
pacman -S vulkan-intel lib32-vulkan-intel nvidia-utils lib32-nvidia-utils vulkan-icd-loader lib32-vulkan-icd-loader primus_vk

Next, add launch options for Counter-Strike: Global Offensive:
pvkrun %command% -vulkan -console -fullscreen

Should work!

Sid Meier’s Civilization VI

Works in conjunction – Primus + OpenGL + LD_PRELOAD.

Install the Primus package:
pacman -S primus

Next, add launch options for Sid Meier’s Civilization VI:
LD_PRELOAD='/usr/lib/libfreetype.so.6:/usr/lib/libbrotlicommon.so.1:/usr/lib/libbrotlidec.so.1' primusrun %command%

LD_PRELOAD pushes the Freetype compression and font libraries.

Dota 2

Works in conjunction – Primus + OpenGL + removal of locks at startup.

Install the Primus package:
pacman -S primus

Next, add launch options for Dota 2:
primusrun %command% -gl -console

If the game doesn’t start with fcntl(5) for /tmp/source_engine_2808995433.lock failed, then try deleting the /tmp/source_engine_2808995433.lock file
rm /tmp/source_engine_2808995433.lock
Usually the lock file is left over from the last game session unless the game was closed naturally.

How to check?

The easiest way to check the launch of applications on a discrete Nvidia graphics card is through the nvidia-smi utility:

For games on the Source engine, you can check through the game console using the mat_info command:

References

https://wiki.archlinux.org/title/Steam/Game-specific_troubleshooting
https://help.steampowered.com/en/faqs/view/145A-FE54-F37B-278A
https://bbs.archlinux.org/viewtopic.php?id=277708

Schlafsortierung

Schlafsortierung – Sleep Sort, ein weiterer Vertreter deterministischer seltsamer Sortieralgorithmen.

Es funktioniert so:

  1. Durchläuft eine Liste von Elementen
  2. Für jede Schleife wird ein separater Thread gestartet
  3. Der Thread schläft für eine gewisse Zeit – Elementwert und Wertausgabe nach dem Ruhezustand
  4. Warten Sie am Ende der Schleife, bis der längste Ruhezustand des Threads abgeschlossen ist, und zeigen Sie die sortierte Liste an

Beispielcode für den Schlafsortierungsalgorithmus in C:

#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

typedef struct {
    int number;
} ThreadPayload;

void *sortNumber(void *args) {
    ThreadPayload *payload = (ThreadPayload*) args;
    const int number = payload->number;
    free(payload);
    usleep(number * 1000);
    printf("%d ", number);
    return NULL;
}

int main(int argc, char *argv[]) {
    const int numbers[] = {2, 42, 1, 87, 7, 9, 5, 35};
    const int length = sizeof(numbers) / sizeof(int);

    int maximal = 0;
    pthread_t maximalThreadID;

    printf("Sorting: ");
    for (int i = 0; i < length; i++) { pthread_t threadID; int number = numbers[i]; printf("%d ", number); ThreadPayload *payload = malloc(sizeof(ThreadPayload)); payload->number = number;
        pthread_create(&threadID, NULL, sortNumber, (void *) payload);
        if (maximal < number) {
            maximal = number;
            maximalThreadID = threadID;
        }
    }
    printf("\n");
    printf("Sorted: ");
    pthread_join(maximalThreadID, NULL);
    printf("\n");
    return 0;
}

In dieser Implementierung habe ich die Funktion usleep für Mikrosekunden verwendet, wobei der Wert mit 1000 multipliziert wurde, d. h. in Millisekunden.
Zeitliche Komplexität des Algorithmus – O(sehr lang)

Links

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/sleepSort

Quellen

https://codoholicconfessions.wordpress. com/2017/05/21/strangest-sorting-algorithms/
https://twitter.com/javascriptdaily/status/856267407106682880?lang=en
https://stackoverflow.com/questions/6474318/what-is-the-time-complexity-of-the-sleep-sort

Stalin-Sorte

Stalin Sort – Sortieren durch, einer der Sortieralgorithmen mit Datenverlust.
Der Algorithmus ist sehr produktiv und effizient, Zeitkomplexität O(n).

Es funktioniert so:

  1. Durchlaufen Sie das Array und vergleichen Sie das aktuelle Element mit dem nächsten
  2. Wenn das nächste Element kleiner als das aktuelle ist, entfernen Sie es
  3. Als Ergebnis erhalten wir ein sortiertes Array in O(n)

Beispiel für die Ausgabe des Algorithmus:

Gulag: [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
Element 2 sent to Gulag
Element 4 sent to Gulag
Element 8 sent to Gulag
Element 5 sent to Gulag
Element 0 sent to Gulag
Element 35 sent to Gulag
Element 10 sent to Gulag
Numbers: [1, 3, 4, 6, 42]
Gulag: [2, 4, 8, 5, 0, 35, 10]

Python 3-Code:

gulag = []

print(f"Numbers: {numbers}")
print(f"Gulag: {numbers}")

i = 0
maximal = numbers[0]

while i < len(numbers):
    element = numbers[i]
    if maximal > element:
        print(f"Element {element} sent to Gulag")
        gulag.append(element)
        del numbers[i]
    else:
        maximal = element        
        i += 1

print(f"Numbers: {numbers}")
print(f"Gulag: {gulag}")

Zu den Nachteilen gehört der Datenverlust, aber wenn wir uns einer utopischen, idealen, sortierten Liste in O(n) nähern, wie sonst?

Links

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/stalinSort

Quellen

https://github.com/gustavo-depaula/stalin-sort
https://www.youtube.com/shorts/juRL-Xn-E00
https://www.youtube.com/watch?v=L78i2YcyYfk

Auswahlsortierung

Auswahl sortieren – Auswahlsortieralgorithmus. Was wählen? Aber die Mindestanzahl!!!
Zeitliche Komplexität des Algorithmus – O(n2)

Der Algorithmus funktioniert wie folgt:

  1. Wir gehen das Array in einer Schleife von links nach rechts durch, merken uns den aktuellen Startindex und die Nummer am Index, nennen wir es Nummer A
  2. Innerhalb der Schleife führen wir einen weiteren aus, um von links nach rechts zu gehen und nach etwas zu suchen, das kleiner als A ist
  3. Wenn wir die kleinere finden, merken wir uns den Index, jetzt wird die kleinere zur Zahl A
  4. Wenn die innere Schleife endet, tauschen Sie die Zahl am Startindex und die Zahl A aus
  5. Nachdem wir die obere Schleife vollständig durchlaufen haben, erhalten wir ein sortiertes Array

Beispiel für die Ausführung eines Algorithmus:

(29, 49, 66, 35, 7, 12, 80)
29 > 7
(7, 49, 66, 35, 29, 12, 80)
Round 1 ENDED
Round 2
(7, 49, 66, 35, 29, 12, 80)
49 > 35
35 > 29
29 > 12
(7, 12, 66, 35, 29, 49, 80)
Round 2 ENDED
Round 3
(7, 12, 66, 35, 29, 49, 80)
66 > 35
35 > 29
(7, 12, 29, 35, 66, 49, 80)
Round 3 ENDED
Round 4
(7, 12, 29, 35, 66, 49, 80)
(7, 12, 29, 35, 66, 49, 80)
Round 4 ENDED
Round 5
(7, 12, 29, 35, 66, 49, 80)
66 > 49
(7, 12, 29, 35, 49, 66, 80)
Round 5 ENDED
Round 6
(7, 12, 29, 35, 49, 66, 80)
(7, 12, 29, 35, 49, 66, 80)
Round 6 ENDED
Sorted: (7, 12, 29, 35, 49, 66, 80)

Ich habe keine Objective-C-Implementierung im Rosetta-Code gefunden , schrieb ich selbst:

#include <Foundation/Foundation.h>

@implementation SelectionSort
- (void)performSort:(NSMutableArray *)numbers
{
   NSLog(@"%@", numbers);   
   for (int startIndex = 0; startIndex < numbers.count-1; startIndex++) {
      int minimalNumberIndex = startIndex;
      for (int i = startIndex + 1; i < numbers.count; i++) {
         id lhs = [numbers objectAtIndex: minimalNumberIndex];
         id rhs = [numbers objectAtIndex: i];
         if ([lhs isGreaterThan: rhs]) {
            minimalNumberIndex = i;
         }
      }
      id temporary = [numbers objectAtIndex: minimalNumberIndex];
      [numbers setObject: [numbers objectAtIndex: startIndex] 
               atIndexedSubscript: minimalNumberIndex];
      [numbers setObject: temporary
               atIndexedSubscript: startIndex];
   }
   NSLog(@"%@", numbers);
}

@end

Собрать и запустить можно либо на MacOS/Xcode, либо на любой операционной системе поддерживающей GNUstep, например у меня собирается Clang на Arch Linux.
Скрипт сборки:

        main.m \
        -lobjc \
        `gnustep-config --objc-flags` \
        `gnustep-config --objc-libs` \
        -I /usr/include/GNUstepBase \
        -I /usr/lib/gcc/x86_64-pc-linux-gnu/12.1.0/include/ \
        -lgnustep-base \
        -o SelectionSort \

Links

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/selectionSort

Sources

https://rosettacode.org/wiki/Sorting_algorithms/Selection_sort
https://ru.wikipedia.org/wiki/Сортировка_выбором
https://en.wikipedia.org/wiki/Selection_sort
https://www.youtube.com/watch?v=LJ7GYbX7qpM

Zählsortierung

Zählsortierung – Zählsortieralgorithmus. Bezüglich? Ja! Einfach so!

Der Algorithmus umfasst mindestens zwei Arrays, das erste – Liste der zu sortierenden Ganzzahlen, zweite – ein Array der Größe = (maximale Anzahl – minimale Anzahl) + 1, das zunächst nur Nullen enthält. Als nächstes werden die Zahlen aus dem ersten Array aussortiert und das Zahlenelement wird verwendet, um einen Index im zweiten Array zu erhalten, der um eins erhöht wird. Nachdem wir die gesamte Liste durchgegangen sind, erhalten wir ein vollständig gefülltes zweites Array mit der Anzahl der Wiederholungen der Zahlen aus dem ersten. Der Algorithmus hat einen erheblichen Overhead – Das zweite Array enthält auch Nullen für Zahlen, die nicht in der ersten Liste enthalten sind, die sogenannten. Overhead aus dem Speicher

Nachdem wir das zweite Array erhalten haben, durchlaufen wir es und schreiben die nach Index sortierte Version der Zahl, wobei wir den Zähler auf Null dekrementieren. Ein Nullzähler wird zunächst ignoriert.

Ein Beispiel für den nicht optimierten Betrieb des Zählsortieralgorithmus:

  1. Eingabearray 1,9,1,4,6,4,4
  2. Dann ist das zu zählende Array 0,1,2,3,4,5,6,7,8,9 (Mindestzahl 0, Höchstzahl 9)
  3. Mit Gesamtzählern 0,2,0,0,3,0,1,0,0,1
  4. Gesamt sortiertes Array 1,1,4,4,4,6,9

Algorithmuscode in Python 3:


numbers = [42, 89, 69, 777, 22, 35, 42, 69, 42, 90, 777]

minimal = min(numbers)
maximal = max(numbers)
countListRange = maximal - minimal
countListRange += 1
countList = [0] * countListRange

print(numbers)
print(f"Minimal number: {minimal}")
print(f"Maximal number: {maximal}")
print(f"Count list size: {countListRange}")

for number in numbers:
    index = number - minimal
    countList[index] += 1

replacingIndex = 0
for index, count in enumerate(countList):
    for i in range(count):
        outputNumber = minimal + index
        numbers[replacingIndex] = outputNumber
        replacingIndex += 1

print(numbers)

Из-за использования двух массивов, временная сложность алгоритма O(n + k)

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/countingSort

Источники

https://www.youtube.com/watch?v=6dk_csyWif0
https://www.youtube.com/watch?v=OKd534EWcdk
https://en.wikipedia.org/wiki/Counting_sort
https://rosettacode.org/wiki/Sorting_algorithms/Counting_sort
https://pro-prof.com/forums/topic/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-%D0%BF%D0%BE%D0%B4%D1%81%D1%87%D0%B5%D1%82%D0%BE%D0%BC

Bogosort

Pseudosortierung oder Sumpfsortierung, einer der nutzlosesten Sortieralgorithmen.

Es funktioniert so:
1. Die Eingabe ist ein Array von Zahlen
2. Eine Reihe von Zahlen wird zufällig gemischt (shuffle)
3. Prüft, ob das Array sortiert ist
4. Wenn nicht sortiert, wird das Array erneut gemischt
5. All diese Aktionen werden wiederholt, bis das Array zufällig sortiert ist.

Wie Sie sehen können, ist die Leistung dieses Algorithmus schrecklich. Kluge Leute glauben, dass sogar O(n * n!) d. h. Es besteht die Möglichkeit, dass Sie viele Jahre lang beim Würfeln zum Ruhm des Gottes des Chaos stecken bleiben. Das Array wird nie sortiert, oder vielleicht wird es sortiert?

Implementierung

Um es in TypeScript zu implementieren, musste ich die folgenden Funktionen implementieren:
1. Mischen Sie ein Array von Objekten
2. Array-Vergleich
3. Generieren einer Zufallszahl im Bereich von Null bis zu einer Zahl (sic!)
4. Druckfortschritt, weil es scheint, dass das Sortieren endlos weitergeht

Unten finden Sie den TypeScript-Implementierungscode:

const randomInteger = (maximal: number) => Math.floor(Math.random() * maximal);
const isEqual = (lhs: any[], rhs: any[]) => lhs.every((val, index) => val === rhs[index]);
const shuffle = (array: any[]) => {
    for (var i = 0; i < array.length; i++) { var destination = randomInteger(array.length-1); var temp = array[i]; array[i] = array[destination]; array[destination] = temp; } } let numbers: number[] = Array.from({length: 10}, ()=>randomInteger(10));
const originalNumbers = [...numbers];
const sortedNumbers = [...numbers].sort();

let numberOfRuns = 1;

do {
    if (numberOfRuns % 1000 == 0) {
        printoutProcess(originalNumbers, numbers, numberOfRuns);
    }
    shuffle(numbers);
    numberOfRuns++;
} while (isEqual(numbers, sortedNumbers) == false)

console.log(`Success!`);
console.log(`Run number: ${numberOfRuns}`)
console.log(`Original numbers: ${originalNumbers}`);
console.log(`Current numbers: ${originalNumbers}`);
console.log(`Sorted numbers: ${sortedNumbers}`);

Для отладки можно использовать VSCode и плагин TypeScript Debugger от kakumei.

Как долго

Вывод работы алгоритма:

src/bogosort.ts:1
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 8,7,0,2,4,7,2,5,9,5, try number: 145000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 7,5,2,4,9,8,0,5,2,7, try number: 146000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 0,2,7,4,9,5,7,5,8,2, try number: 147000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 5,9,7,8,5,4,2,7,0,2, try number: 148000
src/bogosort.ts:2
Success!
src/bogosort.ts:24
Run number: 148798
src/bogosort.ts:25
Original numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:26
Current numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:27
Sorted numbers: 0,2,2,4,5,5,7,7,8,9

Для массива из 10 чисел Богосорт перемешивал исходный массив 148798 раз, многовато да?
Алгоритм можно использовать как учебный, для понимания возможностей языка с которым предстоит работать на рынке. Лично я был удивлен узнав что в ванильных JS и TS до сих пор нет своего алгоритма перемешивания массивов, генерации целого числа в диапазоне, доступа к хэшам объектов для быстрого сравнения.

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/bogosort
https://www.typescriptlang.org/
https://marketplace.visualstudio.com/items?itemName=kakumei.ts-debug

Источники

https://www.youtube.com/watch?v=r2N3scbd_jg
https://en.wikipedia.org/wiki/Bogosort

GoF-Muster

Liste der Gang-of-Four-Muster – Die gleichen Muster, die dazu führen können, dass Sie bei einem Vorstellungsgespräch scheitern.

Generative Muster

Strukturelle Muster

Verhaltensmuster

Musterinterpreter

Was ist enthalten

Das Interpreter-Muster bezieht sich auf Verhaltensentwurfsmuster. Mit diesem Muster können Sie Ihre eigene Programmiersprache implementieren, indem Sie mit einem AST-Baum arbeiten, dessen Eckpunkte terminale und nicht-terminale Ausdrücke sind, die die Interpret-Methode implementieren, die die Funktionalität der Sprache bereitstellt.

  • Terminalausdruck – zum Beispiel die Zeichenfolgenkonstante – “Hallo Welt”
  • Nicht-terminaler Ausdruck – zum Beispiel Print(“Hello World”), enthält Print und ein Argument aus dem Terminalausdruck “Hello World”

Was ist der Unterschied? Der Unterschied besteht darin, dass die Interpretation bei terminalen Ausdrücken endet, bei nicht-terminalen Ausdrücken jedoch ausführlich über alle eingehenden Eckpunkte/Argumente hinweg fortgesetzt wird. Wenn der AST-Baum nur aus nicht-terminalen Ausdrücken bestünde, würde die Anwendung niemals abgeschlossen werden, weil Für jeden Prozess ist eine gewisse Endlichkeit erforderlich. Diese Endlichkeit ist das, was terminale Ausdrücke ausmachen. Sie enthalten normalerweise Daten, zum Beispiel Zeichenfolgen.

Ein Beispiel für einen AST-Baum finden Sie unten:


Dcoetzee, CC0, über Wikimedia Commons

Wie Sie sehen können, sind Terminalausdrücke konstant und variabel, nichtterminale Ausdrücke sind der Rest.

Was nicht enthalten ist

Die Interpreter-Implementierung umfasst nicht das Parsen der in den AST-Baum eingegebenen Sprachzeichenfolge. Es reicht aus, Klassen von Terminal- und Nicht-Terminal-Ausdrücken zu implementieren, Methoden mit dem Kontextargument am Eingang zu interpretieren, einen AST-Ausdrucksbaum zu erstellen und die Interpret-Methode am Stammausdruck auszuführen. Ein Kontext kann verwendet werden, um den Anwendungsstatus zur Laufzeit zu speichern.

Implementierung

Das Muster beinhaltet:

  • Client – ​​​​gibt den AST-Baum zurück und führt Interpret(context) für den Wurzelknoten (Client) aus
  • Kontext – enthält den Status der Anwendung, der bei der Interpretation an Ausdrücke übergeben wird (Kontext)
  • Abstrakter Ausdruck – eine abstrakte Klasse, die die Methode Interpret(context) (Expression) enthält
  • Terminalausdruck ist ein endgültiger Ausdruck, ein Nachkomme eines abstrakten Ausdrucks (TerminalExpression)
  • Ein nicht-terminaler Ausdruck ist kein endlicher Ausdruck; er enthält Zeiger auf Scheitelpunkte tief im AST-Baum. Untergeordnete Scheitelpunkte wirken sich normalerweise auf das Ergebnis der Interpretation des nicht-terminalen Ausdrucks aus (NonTerminalExpression).

Client-Beispiel in C#

        static void Main(string[] args)
        {
            var context = new Context();
            var initialProgram = new PerformExpression(
                new IExpression[] {
                    new SetExpression("alpha", "1"),
                    new GetExpression("alpha"),
                    new PrintExpression(
                        new IExpression[] {
                            new ConstantExpression("Hello Interpreter Pattern")
                        }
                    )
                }
            );
            System.Console.WriteLine(initialProgram.interpret(context));
        }
}

Beispiel für einen abstrakten Ausdruck in C#

{
    String interpret(Context context);
}

Beispiel für einen Terminalausdruck in C# (String-Konstante)

{
    private String constant;

    public ConstantExpression(String constant) {
        this.constant = constant;
    }

    override public String interpret(Context context) {
        return constant;
    }
}

Beispiel eines nichtterminalen Ausdrucks in C# (Starten und Verketten der Ergebnisse untergeordneter Scheitelpunkte unter Verwendung des Trennzeichens „;“

{
    public PerformExpression(IExpression[] leafs) : base(leafs) {
        this.leafs = leafs;
    }
    
    override public String interpret(Context context) {
        var output = "";
        foreach (var leaf in leafs) {
            output += leaf.interpret(context) + ";";
        }
        return output;
    }
}

Können Sie es funktionell umsetzen?

Bekanntlich sind alle Turing-vollständigen Sprachen gleichwertig. Ist es möglich, das objektorientierte Muster auf die funktionale Programmiersprache zu übertragen?

Für ein Experiment nehmen wir eine FP-Sprache für das Web namens Elm. In Elm gibt es keine Klassen, aber Datensätze und Typen. Daher sind die folgenden Datensätze und Typen an der Implementierung beteiligt:

  • Ausdruck – Auflistung aller möglichen Sprachausdrücke (Ausdruck)
  • Untergeordneter Ausdruck – ein Ausdruck, der dem nichtterminalen Ausdruck (ExpressionLeaf) untergeordnet ist
  • Kontext – ein Datensatz, der den Status der Anwendung speichert (Kontext)
  • Funktionen, die Interpret(Kontext)-Methoden implementieren – alle notwendigen Funktionen, die die Funktionalität von Terminal- und Nicht-Terminal-Ausdrücken implementieren
  • Hilfsdatensätze des Interpreter-Status – notwendig für den korrekten Betrieb des Interpreters, sie speichern den Interpreter-Status und den Kontext

Ein Beispiel für eine Funktion, die die Interpretation für den gesamten Satz möglicher Ausdrücke in Elm implementiert:

  case input.expression of
    Constant text ->
      { 
        output = text, 
        context = input.context 
      }
    Perform leafs ->
      let inputs = List.map (\leaf -> { expressionLeaf = leaf, context = input.context } ) leafs in
        let startLeaf = { expressionLeaf = (Node (Constant "")), context = { variables = Dict.empty } } in
          let outputExpressionInput = List.foldl mergeContextsAndRunLeafs startLeaf inputs in
            {
              output = (runExpressionLeaf outputExpressionInput).output,
              context = input.context
            }
    Print printExpression ->
      run 
      { 
        expression = printExpression, 
        context = input.context 
      }
    Set key value ->
      let variables = Dict.insert key value input.context.variables in
      {
        output = "OK",
        context = { variables = variables }
      }
    Get key ->
      {
        output = Maybe.withDefault ("No value for key: " ++ key) (Dict.get key input.context.variables),
        context = input.context
      }

Was ist mit dem Parsen?

Das Parsen von Quellcode in einen AST-Baum ist nicht im Interpreter-Muster enthalten; es gibt mehrere Ansätze zum Parsen von Quellcode, aber dazu ein anderes Mal mehr.
Bei der Implementierung des Interpreters für Elm habe ich einen einfachen Parser im AST-Baum geschrieben, der aus zwei Funktionen besteht: Parsen eines Scheitelpunkts und Parsen untergeordneter Scheitelpunkte.

parseLeafs state =
    let tokensQueue = state.tokensQueue in
        let popped = pop state.tokensQueue in
            let tokensQueueTail = tail state.tokensQueue in
                if popped == "Nothing" then
                    state
                else if popped == "Perform(" then
                    {
                        tokensQueue = tokensQueue,
                        result = (state.result ++ [Node (parse tokensQueue)])
                    }
                else if popped == ")" then
                    parseLeafs {
                        tokensQueue = tokensQueueTail,
                        result = state.result
                    }
                else if popped == "Set" then
                    let key = pop tokensQueueTail in
                        let value = pop (tail tokensQueueTail) in
                            parseLeafs {
                                tokensQueue = tail (tail tokensQueueTail),
                                result = (state.result ++ [Node (Set key value)])
                            }
                else if popped == "Get" then
                    let key = pop tokensQueueTail in
                        parseLeafs {
                            tokensQueue = tail tokensQueueTail,
                            result = (state.result ++ [Node (Get key)])
                        }
                else 
                    parseLeafs {
                        tokensQueue = tokensQueueTail,
                        result = (state.result ++ [Node (Constant popped)])
                    }

parse tokensQueue =
    let popped = pop tokensQueue in
        let tokensQueueTail = tail tokensQueue in
            if popped == "Perform(" then
                Perform (
                    parseLeafs {
                        tokensQueue = tokensQueueTail, 
                        result = []
                    }
                ).result
            else if popped == "Set" then
                let key = pop tokensQueueTail in
                    let value = pop (tail tokensQueueTail) in
                        Set key value
            else if popped == "Print" then
                Print (parse tokensQueueTail)
            else
                Constant popped

Links

https://gitlab.com/demensdeum /patterns/-/tree/master/interpreter/elm
https://gitlab.com/demensdeum/patterns/-/tree/master/interpreter/csharp

Quellen

https://en.wikipedia.org/wiki/Interpreter_pattern
https://elm-lang.org/
https://docs.microsoft.com/en-us/dotnet/csharp/

RGB-Bild zu Grau

In diesem Beitrag beschreibe ich den Algorithmus zum Konvertieren eines RGB-Puffers in Grau (Graustufen).
Und das geht ganz einfach: Jeder Pixel-Farbkanal des Puffers wird nach einer bestimmten Formel konvertiert und die Ausgabe ist ein Graubild.
Durchschnittsmethode:

red = average;
green = average;
blue = average;

Складываем 3 цветовых канала и делим на 3.

Однако существует еще один метод – метод средневзвешенный, он учитывает цветовосприятие человека:

red = luminance;
green = luminance;
blue = luminance;

Какой метод лучше использовать? Да какой вам больше подходит для конкретной задачи. Далее сравнение методов с помощью тестовой цветовой сетки:

Пример реализации на JavaScript + HTML 5

    image,
    canvas,
    weightedAverage
) {
    const context = canvas.getContext('2d');

    const imageWeight = image.width;
    const imageHeight = image.height;

    canvas.width = imageWeight;
    canvas.height = imageHeight;

    context.drawImage(image, 0, 0);

    let pixels = context
        .getImageData(
            0,
            0,
            imageWeight,
            imageHeight
        );

    for (let y = 0; y & lt; pixels.height; y++) {
        for (let x = 0; x & lt; pixels.width; x++) {
            const i = (y * 4) * pixels.width + x * 4;

            let red = pixels.data[i];
            let green = pixels.data[i + 1];
            let blue = pixels.data[i + 2]

            const average = (red + green + blue) / 3;
            const luminance = 0.2126 * red +
                0.7152 * green +
                0.0722 * blue;

            red = weightedAverage ? luminance : average;
            green = weightedAverage ? luminance : average;
            blue = weightedAverage ? luminance : average;

            pixels.data[i] = red;
            pixels.data[i + 1] = green;
            pixels.data[i + 2] = blue;
        }
    }
    context
        .putImageData(
            pixels,
            0,
            0,
            0,
            0,
            pixels.width,
            pixels.height
        );
}

Источники

https://www.baeldung.com/cs/convert-rgb-to-grayscale
https://twitter.com/mudasobwa/status/1528046455587495940
https://rosettacode.org/wiki/Grayscale_image

Ссылки

http://papugi.demensdeum.repl.co/

Благодарности

Спасибо Aleksei Matiushkin (https://twitter.com/mudasobwa) за наводку на Rosetta Code

So führen Sie CSGO auf dem MacBook M1 aus

Wenn Sie beim Starten von CSGO auf einem MacBook M1 den Fehler SDL_GetDesktopDisplayMode_REAL erhalten, gehen Sie wie unten beschrieben vor.
1. Fügen Sie Steam für CSGO Startoptionen hinzu:
-w 1440 -h 900 -fullscreen
2. Starten Sie CSGO über Steam
3. Klicken Sie auf Ignorieren oder Immer ignorieren, um den Fehler SDL_GetDesktopDisplayMode_REAL
anzuzeigen4. Viel Spaß