Unreal Engine auf dem MacBook M2

Wenn Sie den Unreal Engine 5 Editor auf einem MacBook mit einem Apple-Prozessor ausführen konnten, ist Ihnen vielleicht aufgefallen, dass dieses Ding ziemlich langsam ist.

Um die Leistung des Editors und der Engine zu steigern, stellen Sie Engine-Skalierbarkeitseinstellungen -> Mittel ein. Danach fängt die Engine an, alles nicht mehr so ​​schön zu zeichnen, aber Sie können normal mit der Engine auf Ihrem MacBook arbeiten.

Korrektur des mobilen Menüs in WordPress


document.addEventListener('DOMContentLoaded', function() {
    new navMenu('primary');
    new navMenu('woo');
});

Wenn Sie in Ihrem WordPress-Blog bei Verwendung des Seedlet-Themes auch das Blog-Menü unter iOS/Android mehrere Jahre lang nicht geöffnet hatten, dann fügen Sie einfach Folgendes hinzu:
Schließen Sie die Datei wp-content/themes/seedlet/assets/js/primary-navigation.js in die Funktion ein und fügen Sie neben dem Standardabonnementfenster EventListener „load“ hinzu.

Radio-Maximum-Electron

Radio Maximum Electron ist eine leistungsstarke und praktische Anwendung, mit der Sie den Stream des Radiosenders Radio Maximum auf Ihrem Computer mit den Betriebssystemen Windows, Linux und macOS hören können. Dieser Player kombiniert Benutzerfreundlichkeit mit hoher Funktionalität und ermöglicht Ihnen den Zugriff auf Live-Streaming mit minimalem Aufwand.

Laden Sie einfach die Anwendung von GitHub herunter:

https://github.com/demensdeum/Radio-Maximum-Electron/releases

Der Autor hat nichts mit Radio Maximum zu tun, er mag dieses Radio einfach wirklich.
Die Hauptfunktionalität wird vom Nativifier-Projekt implementiert

https://github.com/nativefier/nativefier

Lizenz für MIT-Build-Skripte, Runtime hat eine eigene Lizenz!

Unterwasser-Eisbären-Abenteuer

Ein einfaches Spiel mit endlos generierten Labyrinthen mit ThreeJS.

Entstanden im Rahmen eines 3-tägigen Game Jams „Start the Game“ zum Thema „Familienspiel“.

Ein Polarforscherjunges spazierte mit seiner Mutter über das Eis, als plötzlich eine Katastrophe geschah – das Eis brach und er fiel in das eisige Wasser des Ozeans. Mama hatte keine Zeit, ihn zu retten, und der Bär landete in einer mysteriösen Unterwasserhöhle. Zu seiner Überraschung stellte er fest, dass er unter Wasser atmen konnte. Es gibt nur einen Weg, dieser Falle zu entkommen – indem man die Tiefen des Meeres überwindet, Rätsel löst und aggressive Haie bekämpft, die man mit gezielten Apfelwürfen abwehren kann.

Sein Ziel ist es nun, einen Ausweg aus dieser Unterwasserfalle zu finden und zu seiner Mutter zurückzukehren, die Gefahren der Tiefsee zu überwinden und Rätsel zu lösen.

https://demensdeum.com/demos/arctica/

Nixy Player

Nixy Player – Kleine, erweiterbare, plattformübergreifende JavaScript-Laufzeitumgebung.

Plattformübergreifend: Verfügbar auf Windows, macOS und Linux sowie auf jeder anderen Plattform mit Unterstützung für C++ und dynamische Bibliotheken.
Leicht: Minimaler Ressourcenverbrauch bei effizienter Leistung.
Erweiterbar: Entwickelt für eine einfache Erweiterung mit Plugins und zusätzlichen Bibliotheken.

Die neuesten Veröffentlichungen und Updates finden Sie auf der Seite „Veröffentlichungen“:
https://github.com/demensdeum/NixyPlayer/releases/

Raiden Video Ripper

Raiden Video Ripper ist ein Open-Source-Projekt zur Videobearbeitung und Formatkonvertierung. Es basiert auf Qt 6 (Qt Creator) und ermöglicht das Zuschneiden und Konvertieren von Videos in die Formate MP4, GIF und WebM. Sie können auch Audio aus Videos extrahieren und in das MP3-Format konvertieren.
Интерфейс RaidenVideoRipper

Standbild aus COSTA RICA IN 4K 60fps HDR (ULTRA HD)
https://www.youtube.com/watch?v=LXb3EKWsInQ
Die neuesten Veröffentlichungen und Updates finden Sie auf der Seite „Veröffentlichungen“:
https://github.com/demensdeum/RaidenVideoRipper/releases

Donki Hills

Innerhalb eines Monats habe ich einen lustigen Gag gemacht, ein Parodiespiel mit der Unreal Engine 5. Die Entwicklung erfolgte im Twitch-Stream.

Die Geschichte dieses Spiels erzählt von einem gewöhnlichen Russen, James, der auf Tinder ein Mädchen, Maria, gefunden hat, aber aufgrund von Sanktionen und der Einstellung von Tinder in Russland den Kontakt zu ihr verloren hat. Jetzt bleibt ihm nur noch ein Screenshot ihres Fotos, über Google Maps findet er den Ort, an dem das Foto aufgenommen wurde – das Dorf Tikhie Donki in der Nähe von Nowosibirsk. James macht sich auf die Suche nach Maria.

https://demensdeum.itch.io/donki-hills

Roboterverteidiger

Sehr oft stoße ich bei Diskussionen über die korrekte Funktionsweise einer Softwarefunktion auf eine Situation, in der die Funktionalität aus der Sicht des Benutzers seltsam und unlogisch erschien. Die Diskussion mit dem Product Owner sah in etwa so aus:

– Hier liegt eindeutig ein Verhaltensproblem vor
– Nun, wir werden es veröffentlichen und wenn Benutzer anfangen, sich zu beschweren, werden wir es beheben
– ??? Naja, ok…

Es scheint ein funktionierender Plan zu sein, oder? Ein ziemlich optimaler Algorithmus für Teams mit kleinem Budget, engen Fristen, unzureichender Recherche/Fehlen eines UI/UX-Spezialisten. Benutzer werden sich beschweren, wenn etwas passiert, das ist in Ordnung.
Eine Google-Suche zeigt, dass die Quelle dieser Methode aus einem Artikel stammt – „Beschwerdegesteuerte Entwicklung“ von Coding Horror

Einmal habe ich Lebensmittel verkauft, darunter auch Arztwurst für 300 Rubel. Über ein Terminal in einem Supermarkt verließ ich den Laden mit dieser Wurst im vollen Vertrauen, dass sie bezahlt war – Das Terminal bot an, den Scheck nicht auszudrucken, und ich stimmte zu, um für diesen Scheck kein wertvolles Papier zu verschwenden. Während des „Stanzens“ der Ware für jedes Produkt gab das Terminal ein Quietschen von sich, das signalisierte, dass alles korrekt funktioniert hat. Außerdem ertönte ein akustisches Signal, und das Terminal blinkte mit der Hintergrundbeleuchtung des Barcode-Scanners.

Am nächsten Tag ging ich erneut zum Supermarkt, um Lebensmittel einzukaufen, und gab die Lebensmittel über das Terminal ab. Am Ausgang wurde ich von einem Mann mit südländischem Aussehen und dickem Bart empfangen, der mir ein Smartphone hinhielt und sagte: „ „Bist du das vor der Kamera?“, ich schaute auf sein Handy und sah mich in einem Melodic-Death-Metal-T-Shirt von Arch Enemy mit Totenköpfen und all dem, es gab keinen Grund daran zu zweifeln.
„Ja, ich bin es, was ist los?“, sagte der Mann mit zusammengekniffenen Augen, „Gestern hast du die Wurst nicht geschlagen.“… Wow

Nach einer kurzen Untersuchung darüber, wer er war und wie er zu diesen Schlussfolgerungen kam, zeigte er mir ein Video, das an der Decke des Ladens hängt. In dem Video schlage ich auf die Wurst, das Terminal blinkt mit der Hintergrundbeleuchtung des Scanners. Ich habe die Wurst in die Tüte gesteckt.

– Das Video zeigt, wie der Scanner funktioniert
– Hat nichts gebracht, zahlen Sie für die Wurst!

Ein wenig verblüfft über diese Einstellung, bat ich um ein Beschwerdebuch, um zu schreiben, dass das Terminal Softwareverbesserungen benötige, da es alle Anzeichen für einen korrekten Betrieb zeige, in Wirklichkeit aber einfach fehlerhaft sei, ohne dass dies auf dem Bildschirm angezeigt würde in irgendeiner Weise.

Nach 10 Minuten Streit mit ihm und seinem Chef, der sofort zur Verteidigung seines Angestellten und des beschissenen Terminals eilte, beschlossen sie, die Freundin des Administrators anzurufen, damit sie ein Beschwerdebuch mitbringt und das des Arztes schlägt Wurst.

An diesem Tag wurde mir klar, wie schwierig es für Benutzer wirklich ist, sich über Hardware- und Softwareprodukte zu beschweren, und dass höchstwahrscheinlich das Mantra „Die Leute werden sich beschweren“ gilt. „Lasst es uns reparieren“ funktioniert sehr schlecht. Der Hauptgrund sind Menschen, die kaputte Roboter und kaputte Softwarelösungen verteidigen. Der Einfachheit halber schlage ich vor, neue Begriffe einzuführen – Verteidiger kaputter Roboter und Verteidiger kaputter Systeme.

Normale Benutzer können sich nicht über die Fehlfunktion der Terminals beschweren, weil sie durch ZasRoshniks gestört werden, die aus irgendeinem Grund an die Maschinen, mit denen sie arbeiten, hängen und anfangen, sie zu lieben, sie vielleicht für eine Art belebte Wesenheiten halten und dabei vergessen, dass es nichts gibt dort leben.< /p>

Eine ähnliche Situation tritt bei ZaSSoshniki auf. Diese Leute können trotz Beschwerden von Benutzern und anderen Entwicklern Schaum vor dem Mund haben, um einige dumme Mängel in Frameworks, Programmiersprachen oder anderen Softwareprodukten zu verteidigen.
Ein typisches Gespräch mit ZaSSoshnik läuft wie folgt ab:

– Hier funktioniert etwas nicht, laut Dokumentation scheint alles korrekt zu sein
– Oh, Sie haben also nicht das Handbuch von 2005 gelesen, in dem unten in Kleinbuchstaben steht, dass Sie PROGRAM_START:6969
hinzufügen müssen
– ??? äh

Solche Menschen verstehen möglicherweise nicht, wie sie selbst zur Verbreitung von Problemen, Fehlern, Zeit- und Geldverschwendung bei sich selbst und anderen Menschen beitragen. Darunter leiden alle, denn die digitale Transformation ist unmöglich, wenn nicht offensichtliche Dinge und Probleme mit Software- und Hardwarelösungen vertuscht werden.
Mir ist die jüngste Geschichte eines Fehlers in der Horizon-Software der britischen Post bekannt, der Menschen in Schulden trieb, Ehen ruinierte und das Leben anderer Menschen jahrzehntelang ruinierte. All dies geschah aufgrund der Duldung von Leuten, die über Probleme in der Software schwiegen und so „schützten“. ihn.

Freunde, seid keine ZaSRoshniks und ZaSSoshniks, behandelt die Werkzeuge, mit denen ihr arbeitet, mit Vorsicht, sonst droht euch die völlige Versklavung beschissener, kaputter Systeme, wie Geiseln in der neuen digitalen Welt der Zukunft. Für diejenigen, die nicht – Stören Sie zumindest nicht andere Leute, die versuchen, auf nicht funktionierende, störende Software/Hardware aufmerksam zu machen, denn die Entwickler dieser Produkte haben zugestimmt – „Wenn Benutzer anfangen, sich zu beschweren, werden wir das Problem beheben.“

Quellen
https://blog.codinghorror.com/complaint-driven-development/< /a>
https://habr.com/ru/articles/554404/< br />
https://en.wikipedia.org/wiki/British_Post_Office_scandal

Erstellen einer bgfx-Emscripten-Anwendung

In diesem Beitrag beschreibe ich eine Möglichkeit, BGFX-Anwendungen für das Web (WebAssembly) mit Emscripten zu erstellen.

Die Installationsplattform ist Linux x86-64, zum Beispiel Arch Linux.

Lassen Sie uns zunächst Emscripten Version 3.1.51 installieren, sonst werden Sie keinen Erfolg haben, und zwar aufgrund der Änderung des Typs der dynamischen Bibliotheken in der neuesten Version von Emscripten. Mehr können Sie hier lesen:
https://github.com/bkaradzic/bgfx/discussions/3266

Das geht so:


git clone https://github.com/emscripten-core/emsdk.git



cd emsdk



./emsdk install 3.1.51



./emsdk activate 3.1.51



source ./emsdk_env.sh



Lassen Sie uns bgfx für WebAssembly zusammenbauen – Emscripten:


mkdir bgfx-build-test



cd bgfx-build-test



git clone https://github.com/bkaradzic/bx.git



git clone https://github.com/bkaradzic/bimg.git



git clone https://github.com/bkaradzic/bgfx.git



cd bgfx



emmake make wasm-debug



Als Ergebnis finden Sie im .build-Ordner Bitcode-Dateien mit der Erweiterung .bc, die mit Ihrer bgfx-Anwendung verknüpft werden müssen.
Sollte bgfx.bc, bx.bc, bimg.bc sein; Verschiedene Assemblys haben je nach Assemblytyp (Release/Debug) unterschiedliche Namen für diese Dateien.

Fügen Sie einen Link zur Datei CMakeLists.txt mit .bc-Dateien hinzu, zum Beispiel absolute Pfade zu Dateien aus dem bgfx-experiments-Projekt:


target_link_libraries(${PROJECT_NAME} SDL2 GL /home/demensdeum_stream/Sources/bgfx-build/bgfx/.build/wasm/bin/bgfxDebug.bc /home/demensdeum_stream/Sources/bgfx-build/bgfx/.build/wasm/bin/bxDebug.bc /home/demensdeum_stream/Sources/bgfx-build/bgfx/.build/wasm/bin/bimgDebug.bc)



Ändern Sie nun das native Fensterhandle in den Plattformdaten in „BGFX-Initialisierung“:


bgfx::PlatformData platformData{};



platformData.context = NULL;



platformData.backBuffer = NULL;



platformData.backBufferDS = NULL;



platformData.nwh = (void*)"#canvas";



Sie müssen außerdem den Rendertyp in OpenGL ändern:


bgfx::Init init;



init.type = bgfx::RendererType::OpenGL;







init.resolution.width = screenWidth;



init.resolution.height = screenHeight;



init.resolution.reset = BGFX_RESET_VSYNC;



init.platformData = platformData;







if (!bgfx::init(init))



{



    throw std::runtime_error("Failed to initialize bgfx");



}



GLSL-Shader auf 120 neu kompilieren:


shaderc -f "VertexShader.vs" -o "VertexShader.glsl" --type "v" -p "120"



shaderc -f "FragmentShader.fs" -o "FragmentShader.glsl" --type "f" -p "120"



Ja, aber .glsl-Dateien müssen zu CMakeLists.txt als –preload-file:

hinzugefügt werden


set(CMAKE_CXX_FLAGS ... <Остальная часть>



--preload-file VertexShader.glsl \



--preload-file FragmentShader.glsl \



Es bleibt noch, die Hauptrenderschleife in Ihrer Anwendung durch einen While-Funktionsaufruf über emscripten_set_main_loop zu ersetzen.

Sie können hier darüber lesen:
https ://demensdeum.com/blog/ru/2017/03/29/porting-sdl-c-game-to-html5-emscripten/

Als nächstes stellen Sie Ihr Emscripten-Projekt wie gewohnt zusammen, alles sollte funktionieren.
Interessant – Im Emscripten 3.1.51-Build scheint OpenAL zu fehlen (oder nur ich).

Quellcode des Projekts, der mit bgfx und Emscripten korrekt kompiliert wird:
https://github.com/demensdeum/ bgfx-experiments/tree/main/2-emscripten-build

Quellen

https://github.com/bkaradzic/bgfx/discussions/3266
https://bkaradzic.github.io/bgfx/build.html
https://emscripten.org/docs/getting_started/downloads.html
https ://demensdeum.com/blog/ru/2017/03/29/porting-sdl-c-game-to-html5-emscripten/
https://llvm.org/docs/BitCodeFormat.html

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

Flash Forever – Interceptor 2021

Recently, it turned out that Adobe Flash works quite stably under Wine. During a 4-hour stream, I made the game Interceptor 2021, which is a sequel to the game Interceptor 2020, written for the ZX Spectrum.

For those who are not in the know – the Flash technology provided interactivity on the web from 2000 to around 2015. Its shutdown was prompted by an open letter from Steve Jobs, in which he wrote that Flash should be consigned to history because it lagged on the iPhone. Since then, JS has become even more sluggish than Flash, and Flash itself has been wrapped in JS, making it possible to run it on anything thanks to the Ruffle player.

You can play it here:
https://demensdeum.com/demos/Interceptor2021

Video:
https://www.youtube.com/watch?v=-3b5PkBvHQk

Source code:
https://github.com/demensdeum/Interceptor-2021

Masons-DR-Demospiele

Masonry-AR ist ein Augmented-Reality-Spiel, in dem Sie in der realen Welt durch die Stadt navigieren und freimaurerisches Wissen aus Büchern sammeln müssen, um Geld zu erhalten und Gebiete für Ihren Freimaurerorden zu erobern. Das Spiel hat keinen Bezug zu echten Organisationen, alle Spiele sind zufällig.

Spieldemo:
https://demensdeum.com/demos/masonry-ar/client

Vicki:
https://demensdeum.com/masonry-ar-wiki-ru/

Quellcode:
https://github.com/demensdeum/Masonry-AR

CRUD-Repository

In dieser Notiz beschreibe ich die Grundprinzipien des bekannten klassischen CRUD-Musters und die Implementierung in der Swift-Sprache. Swift ist eine offene, plattformübergreifende Sprache, die für Windows, Linux, macOS, iOS und Android verfügbar ist.

Es gibt viele Lösungen zur Abstraktion von Datenspeicherung und Anwendungslogik. Eine solche Lösung ist der CRUD-Ansatz, ein Akronym für C– Erstellen, R -Lesen, U – Update, D– Löschen.
Typischerweise wird dieses Prinzip durch die Implementierung einer Schnittstelle zur Datenbank implementiert, in der Elemente mithilfe einer eindeutigen Kennung, beispielsweise einer ID, manipuliert werden. Für jeden Buchstaben CRUD – wird eine Schnittstelle erstellt. Erstellen (Objekt, ID), Lesen (ID), Aktualisieren (Objekt, ID), Löschen (Objekt, ID).
Wenn ein Objekt eine ID in sich selbst enthält, kann das ID-Argument in den Methoden (Create, Update, Delete) weggelassen werden, da das gesamte Objekt zusammen mit seinem Feld – Ausweis. Aber für – Für das Lesen ist eine ID erforderlich, da wir anhand der ID ein Objekt aus der Datenbank abrufen möchten.

Alle Namen sind fiktiv

Stellen wir uns vor, dass eine hypothetische AssistantAI-Anwendung mit dem kostenlosen EtherRelm-Datenbank-SDK erstellt wurde. Die Integration war einfach, die API war sehr praktisch und als Ergebnis wurde die Anwendung auf den Markt gebracht.
Plötzlich beschließt der SDK-Entwickler EtherRelm, es kostenpflichtig zu machen und legt den Preis auf 100 US-Dollar pro Jahr und Anwendungsbenutzer fest.
Was? Ja! Was sollen die Entwickler von AssistantAI jetzt tun, da sie bereits 1 Million aktive Benutzer haben! 100 Millionen US-Dollar zahlen?
Stattdessen wird beschlossen, die Übertragung der Anwendung in die plattformeigene RootData-Datenbank zu evaluieren. Nach Angaben der Programmierer wird eine solche Übertragung etwa sechs Monate dauern, wobei die Implementierung neuer Funktionen in der Anwendung nicht berücksichtigt ist. Nach einigem Überlegen wurde beschlossen, die Anwendung vom Markt zu nehmen und sie auf einem anderen kostenlosen plattformübergreifenden Framework mit integrierter BueMS-Datenbank neu zu schreiben. Dadurch wird das Problem mit der kostenpflichtigen Datenbank gelöst und die Entwicklung auf anderen Plattformen vereinfacht.
Ein Jahr später wurde die Anwendung in BueMS umgeschrieben, doch dann beschließt der Framework-Entwickler plötzlich, sie kostenpflichtig zu machen. Es stellt sich heraus, dass das Team zweimal in die gleiche Falle getappt ist; ob es beim zweiten Mal wieder herauskommt, ist eine ganz andere Geschichte.

Abstraktion zur Rettung

Diese Probleme hätten vermieden werden können, wenn Entwickler eine Abstraktion von Schnittstellen innerhalb der Anwendung verwendet hätten. Zu den drei Säulen von OOP – Polymorphismus, Kapselung, Vererbung, vor nicht allzu langer Zeit haben sie ein weiteres – Abstraktion.
Mit der Datenabstraktion können Sie Ideen und Modelle allgemein und mit einem Minimum an Details beschreiben und gleichzeitig genau genug sein, um spezifische Implementierungen zu implementieren, die zur Lösung von Geschäftsproblemen verwendet werden.
Wie können wir den Datenbankbetrieb abstrahieren, sodass die Anwendungslogik nicht davon abhängt? Wir verwenden den CRUD-Ansatz!

Ein vereinfachtes UML CRUD-Diagramm sieht so aus:

Beispiel mit einer fiktiven EtherRelm-Datenbank:

Beispiel mit einer echten SQLite-Datenbank:

Wie Sie bereits bemerkt haben, ändert sich beim Wechseln der Datenbank nur die CRUD-Schnittstelle, mit der die Anwendung interagiert. CRUD ist eine Implementierung des GoF-Musters – Adapter, weil Damit passen wir Anwendungsschnittstellen an beliebige Datenbanken an und kombinieren inkompatible Schnittstellen.
Worte sind leer, zeig mir den Code
Um Abstraktionen in Programmiersprachen zu implementieren, werden Schnittstellen/Protokolle/abstrakte Klassen verwendet. All dies sind Phänomene der gleichen Art. In Interviews werden Sie jedoch möglicherweise gebeten, den Unterschied zwischen ihnen zu benennen. Ich persönlich denke, dass dies nicht viel Sinn macht, weil Der einzige Verwendungszweck besteht darin, eine Datenabstraktion zu implementieren, andernfalls dient es dazu, das Gedächtnis des Befragten zu testen.
CRUD wird oft im Rahmen des Repository-Musters implementiert. Das Repository kann jedoch die CRUD-Schnittstelle implementieren oder auch nicht, alles hängt vom Einfallsreichtum des Entwicklers ab.

Stellen Sie sich einen ziemlich typischen Swift-Code für das Book-Struktur-Repository vor, der direkt mit der UserDefaults-Datenbank arbeitet:


struct Book: Codable {
	let title: String
	let author: String
}

class BookRepository {
	func save(book: Book) {
    		let record = try! JSONEncoder().encode(book)
    		UserDefaults.standard.set(record, forKey: book.title)
	}
    
	func get(bookWithTitle title: String) -> Book? {
    		guard let data = UserDefaults.standard.data(forKey: title) else { return nil }
    		let book = try! JSONDecoder().decode(Book.self, from: data)
    		return book
	}
    
	func delete(book: Book) {
    		UserDefaults.standard.removeObject(forKey: book.title)
	}
}

let book = Book(title: "Fear and Loathing in COBOL", author: "Sir Edsger ZX Spectrum")
let repository = BookRepository()
repository.save(book: book)
print(repository.get(bookWithTitle: book.title)!)
repository.delete(book: book)
guard repository.get(bookWithTitle: book.title) == nil else {
	print("Error: can't delete Book from repository!")
	exit(1)
}

Der obige Code scheint einfach zu sein, aber zählen wir die Anzahl der Verstöße gegen das DRY-Prinzip (Do not Repeat Yourself) und die Kohärenz des Codes:
Konnektivität zur UserDefaults-Datenbank
Konnektivität mit JSON-Encodern und -Decodern – JSONEncoder, JSONDecoder
Verbunden mit der Book-Struktur, aber wir benötigen ein abstraktes Repository, um nicht für jede Struktur, die wir in der Datenbank speichern, eine Repository-Klasse zu erstellen (DRY-Verletzung)

Ich sehe diese Art von CRUD-Repository-Code ziemlich oft, er kann verwendet werden, aber eine hohe Kopplung und Duplizierung des Codes führt dazu, dass seine Unterstützung mit der Zeit sehr kompliziert wird. Dies macht sich besonders bemerkbar, wenn Sie versuchen, zu einer anderen Datenbank zu wechseln, oder wenn Sie die interne Logik der Arbeit mit der Datenbank in allen in der Anwendung erstellten Repositorys ändern.
Anstatt Code zu duplizieren, halten Sie die Kopplung hoch – Schreiben wir ein Protokoll für das CRUD-Repository und abstrahieren so die Datenbankschnittstelle und die Anwendungsgeschäftslogik unter Berücksichtigung von DRY und implementieren eine geringe Kopplung:

    typealias Item = Codable
    typealias ItemIdentifier = String
    
    func create<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws
    func read<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier) async throws -> T
    func update<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws
    func delete(id: CRUDRepository.ItemIdentifier) async throws
}

Das CRUDRepository-Protokoll beschreibt Schnittstellen und zugehörige Datentypen für die weitere Implementierung eines bestimmten CRUD-Repositorys.

Als nächstes schreiben wir eine spezifische Implementierung für die UserDefaults-Datenbank:

    private typealias RecordIdentifier = String
    
    let tableName: String
    let dataTransformer: DataTransformer
    
    init(
   	 tableName: String = "",
   	 dataTransformer: DataTransformer = JSONDataTransformer()
    ) {
   	 self.tableName = tableName
   	 self.dataTransformer = dataTransformer
    }
    
    private func key(id: CRUDRepository.ItemIdentifier) -> RecordIdentifier {
   	 "database_\(tableName)_item_\(id)"
    }
   	 
    private func isExists(id: CRUDRepository.ItemIdentifier) async throws -> Bool {
   	 UserDefaults.standard.data(forKey: key(id: id)) != nil
    }
    
    func create<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws {
   	 let data = try await dataTransformer.encode(item)
   	 UserDefaults.standard.set(data, forKey: key(id: id))
   	 UserDefaults.standard.synchronize()
    }
    
    func read<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier) async throws -> T {
   	 guard let data = UserDefaults.standard.data(forKey: key(id: id)) else {
   		 throw CRUDRepositoryError.recordNotFound(id: id)
   	 }
   	 let item: T = try await dataTransformer.decode(data: data)
   	 return item
    }
    
    func update<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws {
   	 guard try await isExists(id: id) else {
   		 throw CRUDRepositoryError.recordNotFound(id: id)
   	 }
   	 let data = try await dataTransformer.encode(item)
   	 UserDefaults.standard.set(data, forKey: key(id: id))
   	 UserDefaults.standard.synchronize()
    }
    
    func delete(id: CRUDRepository.ItemIdentifier) async throws {
   	 guard try await isExists(id: id) else {
   		 throw CRUDRepositoryError.recordNotFound(id: id)
   	 }
   	 UserDefaults.standard.removeObject(forKey: key(id: id))
   	 UserDefaults.standard.synchronize()
    }
}

Der Code sieht lang aus, enthält aber eine vollständige konkrete Implementierung eines CRUD-Repositorys mit loser Kopplung, Details unten.
Typalias wurden zur Selbstdokumentation des Codes hinzugefügt.
Schwache Kopplung und starke Kopplung
Die Loslösung von einer bestimmten Struktur (Struktur) wird mithilfe des generischen T implementiert, das wiederum die Codable-Protokolle implementieren muss. Mit Codable können Sie Strukturen mithilfe von Klassen konvertieren, die die Protokolle TopLevelEncoder und TopLevelDecoder implementieren, beispielsweise JSONEncoder und JSONDecoder. Bei Verwendung von Basistypen (Int, String, Float usw.) ist es nicht erforderlich, zusätzlichen Code zum Konvertieren von Strukturen zu schreiben.

Die Entkopplung von einem bestimmten Encoder und Decoder erfolgt mithilfe der Abstraktion im DataTransformer-Protokoll:

	func encode<T: Encodable>(_ object: T) async throws -> Data
	func decode<T: Decodable>(data: Data) async throws -> T
}

Durch die Implementierung eines Datentransformators haben wir eine Abstraktion der Encoder- und Decoder-Schnittstellen implementiert und eine lose Kopplung implementiert, um die Arbeit mit verschiedenen Arten von Datenformaten sicherzustellen.

Das Folgende ist der Code für einen bestimmten DataTransformer, nämlich für JSON:

	func encode<T>(_ object: T) async throws -> Data where T : Encodable {
    		let data = try JSONEncoder().encode(object)
    		return data
	}
    
	func decode<T>(data: Data) async throws -> T where T : Decodable {
    		let item: T = try JSONDecoder().decode(T.self, from: data)
    		return item
	}
}

War es möglich?

Was hat sich geändert? Jetzt reicht es aus, ein bestimmtes Repository zu initialisieren, um mit jeder Struktur zu arbeiten, die das Codable-Protokoll implementiert, wodurch die Notwendigkeit entfällt, Code zu duplizieren und eine lose Kopplung der Anwendung zu implementieren.

Ein Beispiel für ein Client-CRUD mit einem bestimmten Repository, UserDefaults ist die Datenbank, JSON-Datenformat, Client-Struktur, außerdem ein Beispiel für das Schreiben und Lesen eines Arrays:


print("One item access example")

do {
	let clientRecordIdentifier = "client"
	let clientOne = Client(name: "Chill Client")
	let repository = UserDefaultsRepository(
    	tableName: "Clients Database",
    	dataTransformer: JSONDataTransformer()
	)
	try await repository.create(id: clientRecordIdentifier, item: clientOne)
	var clientRecord: Client = try await repository.read(id: clientRecordIdentifier)
	print("Client Name: \(clientRecord.name)")
	clientRecord.name = "Busy Client"
	try await repository.update(id: clientRecordIdentifier, item: clientRecord)
	let updatedClient: Client = try await repository.read(id: clientRecordIdentifier)
	print("Updated Client Name: \(updatedClient.name)")
	try await repository.delete(id: clientRecordIdentifier)
	let removedClientRecord: Client = try await repository.read(id: clientRecordIdentifier)
	print(removedClientRecord)
}
catch {
	print(error.localizedDescription)
}

print("Array access example")

let clientArrayRecordIdentifier = "clientArray"
let clientOne = Client(name: "Chill Client")
let repository = UserDefaultsRepository(
	tableName: "Clients Database",
	dataTransformer: JSONDataTransformer()
)
let array = [clientOne]
try await repository.create(id: clientArrayRecordIdentifier, item: array)
let savedArray: [Client] = try await repository.read(id: clientArrayRecordIdentifier)
print(savedArray.first!)

Während der ersten CRUD-Prüfung wurde eine Ausnahmebehandlung implementiert, bei der das Lesen des Remote-Elements nicht mehr möglich ist.

Datenbank wechseln

Jetzt zeige ich Ihnen, wie Sie Ihren aktuellen Code in eine andere Datenbank übertragen. Als Beispiel nehme ich den SQLite-Repository-Code, den ChatGPT generiert hat:


class SQLiteRepository: CRUDRepository {
    private typealias RecordIdentifier = String
    
    let tableName: String
    let dataTransformer: DataTransformer
    private var db: OpaquePointer?

    init(
   	 tableName: String,
   	 dataTransformer: DataTransformer = JSONDataTransformer()
    ) {
   	 self.tableName = tableName
   	 self.dataTransformer = dataTransformer
   	 self.db = openDatabase()
   	 createTableIfNeeded()
    }
    
    private func openDatabase() -> OpaquePointer? {
   	 var db: OpaquePointer? = nil
   	 let fileURL = try! FileManager.default
   		 .url(for: .documentDirectory, in: .userDomainMask, appropriateFor: nil, create: false)
   		 .appendingPathComponent("\(tableName).sqlite")
   	 if sqlite3_open(fileURL.path, &db) != SQLITE_OK {
   		 print("error opening database")
   		 return nil
   	 }
   	 return db
    }
    
    private func createTableIfNeeded() {
   	 let createTableString = """
   	 CREATE TABLE IF NOT EXISTS \(tableName) (
   	 id TEXT PRIMARY KEY NOT NULL,
   	 data BLOB NOT NULL
   	 );
   	 """
   	 var createTableStatement: OpaquePointer? = nil
   	 if sqlite3_prepare_v2(db, createTableString, -1, &createTableStatement, nil) == SQLITE_OK {
   		 if sqlite3_step(createTableStatement) == SQLITE_DONE {
       		 print("\(tableName) table created.")
   		 } else {
       		 print("\(tableName) table could not be created.")
   		 }
   	 } else {
   		 print("CREATE TABLE statement could not be prepared.")
   	 }
   	 sqlite3_finalize(createTableStatement)
    }
    
    private func isExists(id: CRUDRepository.ItemIdentifier) async throws -> Bool {
   	 let queryStatementString = "SELECT data FROM \(tableName) WHERE id = ?;"
   	 var queryStatement: OpaquePointer? = nil
   	 if sqlite3_prepare_v2(db, queryStatementString, -1, &queryStatement, nil) == SQLITE_OK {
   		 sqlite3_bind_text(queryStatement, 1, id, -1, nil)
   		 if sqlite3_step(queryStatement) == SQLITE_ROW {
       		 sqlite3_finalize(queryStatement)
       		 return true
   		 } else {
       		 sqlite3_finalize(queryStatement)
       		 return false
   		 }
   	 } else {
   		 print("SELECT statement could not be prepared.")
   		 throw CRUDRepositoryError.databaseError
   	 }
    }
    
    func create<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws {
   	 let insertStatementString = "INSERT INTO \(tableName) (id, data) VALUES (?, ?);"
   	 var insertStatement: OpaquePointer? = nil
   	 if sqlite3_prepare_v2(db, insertStatementString, -1, &insertStatement, nil) == SQLITE_OK {
   		 let data = try await dataTransformer.encode(item)
   		 sqlite3_bind_text(insertStatement, 1, id, -1, nil)
   		 sqlite3_bind_blob(insertStatement, 2, (data as NSData).bytes, Int32(data.count), nil)
   		 if sqlite3_step(insertStatement) == SQLITE_DONE {
       		 print("Successfully inserted row.")
   		 } else {
       		 print("Could not insert row.")
       		 throw CRUDRepositoryError.databaseError
   		 }
   	 } else {
   		 print("INSERT statement could not be prepared.")
   		 throw CRUDRepositoryError.databaseError
   	 }
   	 sqlite3_finalize(insertStatement)
    }
    
    func read<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier) async throws -> T {
   	 let queryStatementString = "SELECT data FROM \(tableName) WHERE id = ?;"
   	 var queryStatement: OpaquePointer? = nil
   	 var item: T?
   	 if sqlite3_prepare_v2(db, queryStatementString, -1, &queryStatement, nil) == SQLITE_OK {
   		 sqlite3_bind_text(queryStatement, 1, id, -1, nil)
   		 if sqlite3_step(queryStatement) == SQLITE_ROW {
       		 let queryResultCol1 = sqlite3_column_blob(queryStatement, 0)
       		 let queryResultCol1Length = sqlite3_column_bytes(queryStatement, 0)
       		 let data = Data(bytes: queryResultCol1, count: Int(queryResultCol1Length))
       		 item = try await dataTransformer.decode(data: data)
   		 } else {
       		 throw CRUDRepositoryError.recordNotFound(id: id)
   		 }
   	 } else {
   		 print("SELECT statement could not be prepared")
   		 throw CRUDRepositoryError.databaseError
   	 }
   	 sqlite3_finalize(queryStatement)
   	 return item!
    }
    
    func update<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws {
   	 guard try await isExists(id: id) else {
   		 throw CRUDRepositoryError.recordNotFound(id: id)
   	 }
   	 let updateStatementString = "UPDATE \(tableName) SET data = ? WHERE id = ?;"
   	 var updateStatement: OpaquePointer? = nil
   	 if sqlite3_prepare_v2(db, updateStatementString, -1, &updateStatement, nil) == SQLITE_OK {
   		 let data = try await dataTransformer.encode(item)
   		 sqlite3_bind_blob(updateStatement, 1, (data as NSData).bytes, Int32(data.count), nil)
   		 sqlite3_bind_text(updateStatement, 2, id, -1, nil)
   		 if sqlite3_step(updateStatement) == SQLITE_DONE {
       		 print("Successfully updated row.")
   		 } else {
       		 print("Could not update row.")
       		 throw CRUDRepositoryError.databaseError
   		 }
   	 } else {
   		 print("UPDATE statement could not be prepared.")
   		 throw CRUDRepositoryError.databaseError
   	 }
   	 sqlite3_finalize(updateStatement)
    }
    
    func delete(id: CRUDRepository.ItemIdentifier) async throws {
   	 guard try await isExists(id: id) else {
   		 throw CRUDRepositoryError.recordNotFound(id: id)
   	 }
   	 let deleteStatementString = "DELETE FROM \(tableName) WHERE id = ?;"
   	 var deleteStatement: OpaquePointer? = nil
   	 if sqlite3_prepare_v2(db, deleteStatementString, -1, &deleteStatement, nil) == SQLITE_OK {
   		 sqlite3_bind_text(deleteStatement, 1, id, -1, nil)
   		 if sqlite3_step(deleteStatement) == SQLITE_DONE {
       		 print("Successfully deleted row.")
   		 } else {
       		 print("Could not delete row.")
       		 throw CRUDRepositoryError.databaseError
   		 }
   	 } else {
   		 print("DELETE statement could not be prepared.")
   		 throw CRUDRepositoryError.databaseError
   	 }
   	 sqlite3_finalize(deleteStatement)
    }
}

Oder der CRUD-Code des Repositorys für das Dateisystem, der ebenfalls von ChatGPT generiert wurde:


class FileSystemRepository: CRUDRepository {
	private typealias RecordIdentifier = String
    
	let directoryName: String
	let dataTransformer: DataTransformer
	private let fileManager = FileManager.default
	private var directoryURL: URL
    
	init(
    	directoryName: String = "Database",
    	dataTransformer: DataTransformer = JSONDataTransformer()
	) {
    	self.directoryName = directoryName
    	self.dataTransformer = dataTransformer
   	 
    	let paths = fileManager.urls(for: .documentDirectory, in: .userDomainMask)
    	directoryURL = paths.first!.appendingPathComponent(directoryName)
   	 
    	if !fileManager.fileExists(atPath: directoryURL.path) {
        	try? fileManager.createDirectory(at: directoryURL, withIntermediateDirectories: true, attributes: nil)
    	}
	}
    
	private func fileURL(id: CRUDRepository.ItemIdentifier) -> URL {
    	return directoryURL.appendingPathComponent("item_\(id).json")
	}
    
	private func isExists(id: CRUDRepository.ItemIdentifier) async throws -> Bool {
    	return fileManager.fileExists(atPath: fileURL(id: id).path)
	}
    
	func create<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws {
    	let data = try await dataTransformer.encode(item)
    	let url = fileURL(id: id)
    	try data.write(to: url)
	}
    
	func read<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier) async throws -> T {
    	let url = fileURL(id: id)
    	guard let data = fileManager.contents(atPath: url.path) else {
        	throw CRUDRepositoryError.recordNotFound(id: id)
    	}
    	let item: T = try await dataTransformer.decode(data: data)
    	return item
	}
    
	func update<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws {
    	guard try await isExists(id: id) else {
        	throw CRUDRepositoryError.recordNotFound(id: id)
    	}
    	let data = try await dataTransformer.encode(item)
    	let url = fileURL(id: id)
    	try data.write(to: url)
	}
    
	func delete(id: CRUDRepository.ItemIdentifier) async throws {
    	guard try await isExists(id: id) else {
        	throw CRUDRepositoryError.recordNotFound(id: id)
    	}
    	let url = fileURL(id: id)
    	try fileManager.removeItem(at: url)
	}
}

Ersetzen Sie das Repository im Client-Code:


print("One item access example")

do {
	let clientRecordIdentifier = "client"
	let clientOne = Client(name: "Chill Client")
	let repository = FileSystemRepository(
    	directoryName: "Clients Database",
    	dataTransformer: JSONDataTransformer()
	)
	try await repository.create(id: clientRecordIdentifier, item: clientOne)
	var clientRecord: Client = try await repository.read(id: clientRecordIdentifier)
	print("Client Name: \(clientRecord.name)")
	clientRecord.name = "Busy Client"
	try await repository.update(id: clientRecordIdentifier, item: clientRecord)
	let updatedClient: Client = try await repository.read(id: clientRecordIdentifier)
	print("Updated Client Name: \(updatedClient.name)")
	try await repository.delete(id: clientRecordIdentifier)
	let removedClientRecord: Client = try await repository.read(id: clientRecordIdentifier)
	print(removedClientRecord)
}
catch {
	print(error.localizedDescription)
}

print("Array access example")

let clientArrayRecordIdentifier = "clientArray"
let clientOne = Client(name: "Chill Client")
let repository = FileSystemRepository(
	directoryName: "Clients Database",
	dataTransformer: JSONDataTransformer()
)
let array = [clientOne]
try await repository.create(id: clientArrayRecordIdentifier, item: array)
let savedArray: [Client] = try await repository.read(id: clientArrayRecordIdentifier)
print(savedArray.first!)

Die Initialisierung von UserDefaultsRepository wurde durch FileSystemRepository mit den entsprechenden Argumenten ersetzt.
Nachdem Sie die zweite Version des Client-Codes ausgeführt haben, finden Sie im Dokumentenordner ein Verzeichnis „Clients Database“, das eine Datei eines in JSON serialisierten Arrays mit einer Client-Struktur enthält.

Datenspeicherformat wechseln

Jetzt bitten wir ChatGPT, einen Encoder und Decoder für XML zu generieren:

	let formatExtension = "xml"
    
	func encode<T: Encodable>(_ item: T) async throws -> Data {
    	let encoder = PropertyListEncoder()
    	encoder.outputFormat = .xml
    	return try encoder.encode(item)
	}
    
	func decode<T: Decodable>(data: Data) async throws -> T {
    	let decoder = PropertyListDecoder()
    	return try decoder.decode(T.self, from: data)
	}
}

Dank der in Swift integrierten Typen wird die Aufgabe für ein neuronales Netzwerk elementar.

Ersetzen Sie JSON durch XML im Client-Code:


print("One item access example")

do {
	let clientRecordIdentifier = "client"
	let clientOne = Client(name: "Chill Client")
	let repository = FileSystemRepository(
    	directoryName: "Clients Database",
    	dataTransformer: XMLDataTransformer()
	)
	try await repository.create(id: clientRecordIdentifier, item: clientOne)
	var clientRecord: Client = try await repository.read(id: clientRecordIdentifier)
	print("Client Name: \(clientRecord.name)")
	clientRecord.name = "Busy Client"
	try await repository.update(id: clientRecordIdentifier, item: clientRecord)
	let updatedClient: Client = try await repository.read(id: clientRecordIdentifier)
	print("Updated Client Name: \(updatedClient.name)")
	try await repository.delete(id: clientRecordIdentifier)
	let removedClientRecord: Client = try await repository.read(id: clientRecordIdentifier)
	print(removedClientRecord)
}
catch {
	print(error.localizedDescription)
}

print("Array access example")

let clientArrayRecordIdentifier = "clientArray"
let clientOne = Client(name: "Chill Client")
let repository = FileSystemRepository(
	directoryName: "Clients Database",
	dataTransformer: XMLDataTransformer()
)
let array = [clientOne]
try await repository.create(id: clientArrayRecordIdentifier, item: array)
let savedArray: [Client] = try await repository.read(id: clientArrayRecordIdentifier)
print(savedArray.first!)

Der Client-Code wurde in nur einen Ausdruck JSONDataTransformer geändert -> XMLDataTransformer

Gesamt

CRUD-Repositorys sind eines der Entwurfsmuster, die zur Implementierung einer losen Kopplung von Anwendungsarchitekturkomponenten verwendet werden können. Eine weitere Lösung – unter Verwendung von ORM (Object-Relational Mapping), kurz gesagt, ORM verwendet einen Ansatz, bei dem Strukturen vollständig auf die Datenbank abgebildet werden und dann Änderungen an Modellen in der Datenbank angezeigt (zugeordnet (!)) werden sollen.
Aber das ist eine ganz andere Geschichte.

Eine vollständige Implementierung von CRUD-Repositorys für Swift ist verfügbar unter:
https://gitlab.com/demensdeum/crud-example

Swift wird übrigens schon lange außerhalb von macOS unterstützt; der Code aus dem Artikel wurde vollständig unter Arch Linux geschrieben und getestet.

Quellen

https://developer.apple.com/documentation/combine/topleveldecoder
https://developer.apple.com/documentation/combine/toplevelencoder
https://en.wikipedia.org/wiki/Create,_read,_update_and_delete

dd Ein-/Ausgabefehler

Was sollten Sie tun, wenn Sie beim Kopieren einer normalen Festplatte mit dd unter Linux einen Ein-/Ausgabefehler erhalten?

Situevina ist sehr traurig, aber lösbar. Höchstwahrscheinlich haben Sie es mit einer ausgefallenen Festplatte zu tun, die fehlerhafte Blöcke enthält, die nicht mehr verwendet, beschrieben oder gelesen werden können.

Überprüfen Sie eine solche Festplatte unbedingt mit S.M.A.R.T., da Ihnen höchstwahrscheinlich Festplattenfehler angezeigt werden. Dies war in meinem Fall der Fall; die Anzahl der fehlerhaften Blöcke war so groß, dass ich mich von der alten Festplatte verabschieden und sie durch eine neue SSD ersetzen musste.

Das Problem bestand darin, dass diese Diskette ein voll funktionsfähiges System mit lizenzierter Software enthielt, die für die Arbeit erforderlich war. Ich habe versucht, partimage zum schnellen Kopieren von Daten zu verwenden, aber plötzlich habe ich festgestellt, dass das Dienstprogramm nur ein Drittel der Festplatte kopiert. Dann endet es entweder mit einem Segfault oder mit einem anderen lustigen Sishny/Sipplusplus-Witz.

Als nächstes habe ich versucht, die Daten mit dd zu kopieren, und es stellte sich heraus, dass dd ungefähr an die gleiche Stelle wie partimage gelangt und dann ein Eingabe-/Ausgabefehler auftritt. Gleichzeitig haben alle möglichen lustigen Flags wie conv=noerr, skip oder etwas anderes überhaupt nicht geholfen.

Aber die Daten konnten mit einem GNU-Dienstprogramm namens ddrescue problemlos auf eine andere Festplatte kopiert werden.

После этого мои волосы стали шелковистыми, вернулась жена, дети и собака перестала кусать диван.

Большим плюсом ddrescue является наличие встроенного прогрессбара, поэтому не приходится костылять какие-то ухищрения навроде pv и всяких не особо красивых флажков dd. Также ddrescure показывает количество попыток прочитать данные; еще на вики написано что утилита обладает каким-то сверх алгоритмом для считывания поврежденных данных, оставим это на проверку людям которые любят ковыряться в исходниках, мы же не из этих да?

https://ru.wikipedia.org/wiki/Ddrescue
https://www.gnu.org/software/ddrescue/ddrescue_ru.html

ChatGPT

Hallo zusammen! In diesem Artikel möchte ich über ChatGPT sprechen – leistungsstarke Sprachmodellierung von OpenAI, die bei der Lösung einer Vielzahl von Textverarbeitungsproblemen helfen kann. Ich zeige Ihnen, wie dieses Tool funktioniert und wie es in der Praxis eingesetzt werden kann. Fangen wir an!

ChatGPT ist derzeit eines der weltweit besten Sprachmodelle auf Basis neuronaler Netze. Es wurde mit dem Ziel entwickelt, Entwicklern dabei zu helfen, intelligente Systeme zu erstellen, die in der Lage sind, natürliche Sprache zu erzeugen und mit den darin enthaltenen Menschen zu kommunizieren.

Einer der Hauptvorteile von ChatGPT ist seine Fähigkeit, Text kontextbezogen zu modellieren. Das bedeutet, dass das Modell frühere Dialoge berücksichtigt und diese nutzt, um die Situation genauer zu verstehen und eine natürlichere Reaktion zu generieren.

Sie können ChatGPT für eine Vielzahl von Aufgaben verwenden, wie zum Beispiel die Automatisierung des Kundensupports, die Erstellung von Chatbots, die Textgenerierung und vieles mehr.

Die neuronalen Netze hinter ChatGPT wurden anhand großer Textmengen trainiert, um äußerst genaue Vorhersagen zu gewährleisten. Dadurch kann das Modell natürlichen Text generieren, der den Dialog unterstützen und Fragen beantworten kann.

Mit ChatGPT können Sie Ihre eigenen Chatbots und andere intelligente Systeme erstellen, die mit Menschen in natürlicher Sprache interagieren können. Dies kann besonders in Branchen wie Tourismus, Einzelhandel und Kundenbetreuung nützlich sein.

Zusammenfassend lässt sich sagen, dass ChatGPT – Es ist ein leistungsstarkes Werkzeug zur Lösung verschiedener Sprachmodellierungsprobleme. Seine Fähigkeit zur kontextbezogenen Modellierung macht es besonders nützlich für die Erstellung von Chatbots und intelligenten Systemen.


Tatsächlich hat ChatGPT alles oben Genannte selbst geschrieben. Was? Ja? Ich bin selbst schockiert!

Sie können das Raster selbst hier ausprobieren:
https://chat.openai.com/chat

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.

Mitsume ga Tōru (NES) – Drittes Auge auf Dandy

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

Mitsume ga Tooru (三つ目がとおる Mitsume ga tōru?, wörtlich „dreiäugig“) ist ein Plattform-Videospiel, das 1992 von Natsume exklusiv für das Nintendo Entertainment System entwickelt wurde. Das Spiel basiert auf dem Manga und Anime Mitsume ga Tooru. Dies ist das zweite von Natsume entwickelte Anime-basierte Spiel. das vorherige war Mitsume ga Tooru: 3Lie-Mon, das zwei Jahre zuvor für die MSX-Plattform veröffentlicht wurde. In Russland ist das Spiel besser bekannt als „3 Eyes“ oder „3 Eyes“. Drittes Auge”.

Number 2

Comrades, I take pride in projects that were created on the basis of Flame Steel Framework 1 and specifically on Flame Steel Engine 1, namely Death-Mask, Cube Art Project, since all this was conceived as a big experiment, creating a multimedia framework alone that can work on the most platforms. I think the experiment ended successfully immediately after the release of the Cube Art Project.

Now about the decisions that I came to during the development of new projects on FSFramework 1

During the development of Space Jaguar and the Space Jaguar Galaxy Bastards shooter, it became clear that the Flame Steel Framework tools were already outdated, not even having time to become at least somewhat convenient.

Therefore, I decided to develop a completely new Flame Steel Framework 2. The main decision will be to switch to my Rise 2 transpiler language, and the Component System (ECS) will no longer be used architecturally, because. it turned out to be needed only within the framework of game logic with great dynamics. For this reason, in Flame Steel Framework 2, the component system will only be possible while using the scripting languages ​​that are planned to be implemented (at least Lua and JavaScript), an interesting feature is that these languages ​​​​are dynamic in nature, so additional creation of the component system is redundant.

You can follow the development of new projects on the blog and on Gitlab:

https://gitlab.com/demensdeum/rise2

https://gitlab.com/demensdeum/flamesteelengine2

https://gitlab.com/demensdeum/flame-steel-engine-2-demo-projects

https://gitlab.com/demensdeum/space-jaguar-action-rpg

https://gitlab.com/demensdeum/space-jaguar-galaxy-bastards

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

FatBoySize – Dienstprogramm zum Anzeigen der Größe von Ordnern und Dateien

FatBoySize – Dienstprogramm zum Anzeigen der Größe von Ordnern und Dateien im Terminal.
Funktioniert auf jedem System, das Python 3 unterstützt.

Ausführen: python3 fbs.py
Ausgabemodus 1: python3 fbs.py -v
Ausgabemodus 2: python3 fbs.py --version

Funktioniert nur für den aktuell geöffneten Pfad im Terminal.

Beispielergebnis:
python3 ~/Sources/my/fatboysize/fbs.py
.local -> 145.GB
Downloads -> 103.GB
.cache -> 37,0 GB
.android -> 11,6 GB
Quellen -> 8,63 GB

Wie Sie sehen können, ist der Ordner „Downloads“ recht klein, aber groß

Links

https://gitlab.com/demensdeum/fatboysize/p>