Réparer un disque dur lent sous Windows 10

Cette note est dédiée à tous les utilisateurs de disques durs qui n’abandonnent pas.


Original (Mae Mu)

Après 1 an et demi d’utilisation de l’ordinateur portable HP Pavilion avec un double disque dur (Windows 10) et SSD (Ubuntu), j’ai commencé à remarquer des temps de chargement très longs pour les applications, une absence de réponse générale de l’interface et des blocages sur les opérations les plus simples. sous Windows 10. Le problème a été minimisé dans la mesure où il est devenu possible d’utiliser à nouveau l’ordinateur portable. Ensuite, je décrirai les étapes que j’ai suivies pour résoudre le problème.

Diagnostic

Pour commencer la recherche, nous devons éliminer tout type de canular ; commençons par déterminer les principales causes des pannes de disque dur. Qu’est-ce qui peut mal se passer lorsque l’on travaille avec un disque dur ? Des problèmes peuvent survenir au niveau physique de l’électronique et au niveau des données logiques et logicielles.
Les problèmes électroniques incluent des éléments tels que : une alimentation électrique d’ordinateur/ordinateur portable qui ne fonctionne pas, des problèmes avec la batterie de l’ordinateur portable ; usure des composants du disque dur, problèmes dans les circuits et puces des composants internes du disque, erreurs de micrologiciel, conséquences de chocs/chutes du disque ou problèmes similaires avec d’autres appareils qui affectent son fonctionnement.
L’usure critique d’un disque dur est considérée comme le moment où un tel nombre de secteurs défectueux (bloc défectueux) apparaît qu’un fonctionnement ultérieur du disque est impossible. Ces blocs sont bloqués par le firmware du disque dur, les données sont transférées automatiquement vers d’autres secteurs et ne devraient affecter le fonctionnement du disque qu’à un certain moment critique.
Les problèmes de logique du programme incluent des erreurs dans le système de fichiers dues à un fonctionnement incorrect des applications, aux actions de l’utilisateur : éteindre l’appareil lorsqu’il est chaud, terminer les processus d’enregistrement sans arrêter correctement les applications, des erreurs dans les pilotes, les services du système d’exploitation.
Sans outils de diagnostic électronique spécialisés, nous ne pouvons que vérifier l’exactitude du niveau du logiciel ; ce faisant, des problèmes électroniques peuvent être découverts, qui sont généralement éliminés par la méthode de réparation en bloc (remplacement de composants/puces) ; Ensuite, nous examinerons les méthodes de diagnostic logiciel utilisant des utilitaires de diagnostic. Il convient de noter que tous les utilitaires doivent être lancés sur le système avec la priorité maximale, car d’autres applications peuvent interférer avec les mesures de performances et bloquer la lecture/écriture du disque, ce qui entraînera des résultats de diagnostic incorrects.

INTELLIGENT

S.M.A.R.T. système de surveillance de l’état des périphériques de stockage – HDD, SDD, eMMC, etc. Vous permet d’évaluer l’usure de l’appareil, d’afficher le nombre de blocs défectueux et de prendre d’autres actions en fonction des données. Vous pouvez afficher SMART dans différentes applications pour travailler avec des disques ; je préfère utiliser les utilitaires du fabricant. Pour mon disque dur Seagate, j’ai utilisé l’utilitaire SeaTools, pour lequel l’état était affiché comme BON, c’est-à-dire que le micrologiciel du disque pense que tout va bien.

Utilitaires du fabricant

Les utilitaires du fabricant du disque proposent des tests pour vérifier son fonctionnement. SeaTools propose plusieurs types de tests, vous pouvez tous les utiliser pour localiser le problème. Des tests simples et rapides peuvent ne révéler aucun problème, préférez donc les tests longs. Dans mon cas, seul Long Test a trouvé des erreurs.

Slowride

Pour vérifier l’exactitude de la lecture, trouver des blocs lents ou morts, j’ai écrit une application slowride, cela fonctionne sur un principe très simple – ouvre un descripteur de périphérique de bloc, avec les paramètres utilisateur spécifiés, lit les données de l’ensemble du périphérique, avec des mesures de temps, la sortie de blocs lents. Le programme s’arrête à la première erreur ; dans ce cas, vous devrez passer à des utilitaires de suppression de données plus sérieux, car il n’est pas possible de lire les données du disque avec des méthodes simples.
Dans mon cas, la lecture de l’intégralité du disque s’est effectuée correctement, avec une légère baisse de vitesse – 90 Mo/s (5 400 tr/min) en une seconde, sur certaines zones du disque. D’où on pourrait conclure que j’avais affaire à un problème logiciel.

Analyse acoustique

Cette méthode ne s’applique pas aux méthodes de diagnostic logiciel, mais il est très important de résoudre le problème. Par exemple, si l’alimentation électrique fonctionne partiellement, le disque dur peut geler/geler et émettre un clic fort.
Dans mon cas, lorsque je travaillais avec un disque sous Windows 10, j’ai entendu quelque chose de familier à tous les propriétaires de disque dur,
bruit de craquement fort de la tête du disque qui va et vient lorsque vous essayez de faire quelque chose dans le système d’exploitation, mais le son était presque constant, cela m’a fait penser qu’il y avait trop de fragmentation disque, surcharge du disque avec les services en arrière-plan.

Réparer

Aucun problème électronique n’a été détecté lors des diagnostics logiciels ; la lecture bloc par bloc de l’intégralité du disque s’est terminée correctement, mais SeaTools a montré des erreurs lors du test long.

Utilitaires du fabricant

En plus des diagnostics, le logiciel du fabricant du disque fournit des procédures de correction des erreurs. Dans SeaTools, le bouton Réparer tout en est responsable ; après avoir confirmé votre consentement à la perte potentielle de données, le processus de correction commencera. Ce correctif a-t-il été utile dans mon cas ? Non, le disque a continué à fonctionner bruyamment et lentement, mais le test long n’a plus montré d’erreurs.

CHKDSK

CHKSDK est un utilitaire Microsoft permettant de dépanner les erreurs logicielles des systèmes de fichiers Windows. Au fil du temps, ces erreurs s’accumulent sur le disque et peuvent grandement interférer avec le travail, conduisant notamment à l’impossibilité de lire/écrire des données. Vous pouvez trouver des instructions d’utilisation de l’utilitaire sur le site Web de Microsoft, mais je vous recommande d’utiliser tous les indicateurs possibles pour corriger les erreurs (au moment de la rédaction, il s’agit de /r /b /f) ; Vous devez exécuter l’analyse avec les droits d’administrateur via le terminal Windows (cmd), pour la partition système, elle aura lieu au démarrage du système, et cela peut prendre très longtemps, dans mon cas, cela a pris 12 heures.
Ce correctif a-t-il été utile dans mon cas ? Non.

Défragmentation de disque

Les données sur le disque sont traitées en blocs ; les fichiers volumineux sont généralement écrits en plusieurs blocs/fragments. Au fil du temps, de nombreux fichiers supprimés créent des blocs vides qui ne sont pas à proximité, de ce fait, lors de l’écriture de fichiers, ils remplissent ces vides et la tête de disque doit parcourir physiquement de longues distances. Ce problème est appelé fragmentation et seuls les utilisateurs de disques durs en sont confrontés. Lors de plusieurs correctifs, la fragmentation de mon disque dur était de 41%, visuellement cela ressemblait à ceci :

Autrement dit, tout va mal. Vous pouvez voir la fragmentation et la défragmenter à l’aide de l’utilitaire Defragger ou du défragmenteur intégré. Vous pouvez également activer le service « Optimiser les lecteurs ». sous Windows 10, planifiez la défragmentation dans le panneau de configuration. Seuls les disques durs nécessitent une défragmentation ; il n’est pas conseillé de l’activer pour les disques SSD, car cela entraînerait une usure accélérée du disque, apparemment pour cette raison, la défragmentation en arrière-plan est désactivée par défaut.

Une autre option de défragmentation est également connue : transférer des données sur un autre disque, formater le disque et recopier les données. Dans ce cas, les données seront écrites dans des secteurs complètement vides, tout en conservant la structure logique correcte pour le fonctionnement du système. Cette option pose de nombreux problèmes lors de la réinitialisation des métadonnées potentiellement critiques qui peuvent ne pas bouger lors d’une copie normale.

Désactiver les services

À l’aide de l’utilitaire Process Monitor vous pouvez suivre les processus qui chargent le disque dur avec leur travail, activez simplement les colonnes IO Write/Read. Après avoir recherché cette chronique, j’ai désactivé le service Xbox Game Bar, le service d’accélération en arrière-plan bien connu pour les programmes Superfetch sous le nouveau nom SysMain, via le panneau des services du panneau de configuration. Superfetch doit constamment analyser les applications que l’utilisateur utilise et accélérer leur lancement en les mettant en cache dans la RAM ; dans mon cas, cela a conduit au chargement en arrière-plan de l’ensemble du disque et à l’incapacité de travailler.

Nettoyer le disque

J’ai également supprimé les anciennes applications et les fichiers inutiles, libérant ainsi des secteurs pour une fragmentation correcte, simplifiant le fonctionnement du système d’exploitation, réduisant le nombre de services et de programmes inutiles et lourds.

Total

Qu’est-ce qui a le plus aidé ? Une différence notable de performances a été obtenue après la défragmentation du disque ; les blocages spontanés ont été éliminés en désactivant les services Xbox et Superfetch. Ces problèmes ne se produiraient-ils pas si j’avais utilisé un SSD ? Il n’y aurait certainement aucun problème de fonctionnement lent dû à la fragmentation, les problèmes de services devraient de toute façon être résolus et les erreurs logicielles ne dépendent pas du type de lecteur. Dans un avenir proche, je prévois une transition complète vers le SSD, mais pour l’instant « Vive les crêpes, les crêpes pour toujours ! »

Liens

http://www.outsidethebox.ms/why-windows-8-defragments-your-ssd-and-how-you-can-avoid-this/
https://channel9.msdn.com/Shows/The-Defrag-Show
https://www.seagate.com/ru/ru/support/downloads/seatools/
https://www.ccleaner.com/defraggler/download
https://docs.microsoft.com/en-us/windows-server/administration/windows-commands/chkdsk
https://gitlab.com/demensdeum/slowride/

Écrire un serveur backend en C++ FCGI

Une brève note sur la façon dont j’ai écrit la partie serveur pour l’éditeur 3D Cube Art Project, le serveur doit enregistrer et afficher le travail des utilisateurs de la version Web, en leur donnant des URL courtes à l’aide du bouton Enregistrer. Au début, je voulais utiliser Swift/PHP/Ruby/JS ou un langage moderne similaire pour le backend, mais après avoir examiné les caractéristiques de mon VPS, j’ai décidé d’écrire le serveur en C/C++.
Vous devez d’abord installer libfcgi sur le serveur et le module de support fcgi pour votre serveur Web, exemple pour Ubuntu et Apache :

sudo apt install libfcgi libapache2-mod-fcgid

Ensuite, nous configurons le module dans la configuration :

FcgidMaxProcessesPerClass – nombre maximum de processus par classe, je l’ai défini sur 1 processus car je ne m’attends pas à une charge importante.
AddHandler fcgid-script .fcgi – extension de fichier avec laquelle le module fcgi doit démarrer.
Ajoutez à la config le dossier à partir duquel les applications cgi seront lancées :

Ensuite, nous écrivons une application en C/C++ avec le support fcgi, l’assemblons et la copions dans le dossier /var/www/html/cgi-bin.
Exemples de code et de script de build :
https://gitlab.com/demensdeum/cube-art-project-server/-/blob/master/src/cubeArtProjectServer.cpp
https://gitlab.com/demensdeum/cube-art-project-server/-/blob/master/src/build.sh
Après cela, vous devrez redémarrer votre serveur Web :

systemctl restart apache2

Ensuite, entrez les autorisations nécessaires pour exécuter le dossier cgi-bin via chmod.
Après cela, votre programme cgi devrait fonctionner via un navigateur en utilisant le lien, exemple pour le serveur Cube Art Project :
http://192.243.103.70/cgi-bin/cubeArtProject/cubeArtProjectServer.fcgi
Si quelque chose ne fonctionne pas, consultez les journaux du serveur Web ou connectez-vous avec un débogueur au processus en cours ; le processus de débogage ne doit pas différer du processus de débogage d’une application client standard.

Sources

https://habr.com/ru/post/154187/
http://chriswu.me/blog/writing-hello-world-in-fcgi-with-c-plus-plus/

Code source

https://gitlab.com/demensdeum/cube-art -serveur-de-projet

Portage d’une application C++ SDL sur Android

Dans cet article, je décrirai mon expérience de portage d’un prototype d’éditeur 3D Cube Art Projectsur Android.
Tout d’abord, regardons le résultat : un éditeur avec un curseur cubique 3D rouge est exécuté dans l’émulateur :

Pour réussir l’assemblage, vous deviez procéder comme suit :

  1. Installez les derniers SDK et NDK Android (plus la version du NDK est récente, mieux c’est).
  2. Téléchargez le code source SDL2, puis prenez le modèle à partir de là pour créer l’application Android.
  3. Ajoutez une image SDL et un mélangeur SDL à l’assemblage.
  4. Ajouter les bibliothèques de mon moteur de jeu et de mon kit d’outils, leurs dépendances (GLM, JSON pour Modern C++)
  5. Adapter les fichiers d’assemblage pour Gradle.
  6. Adapter le code C++ pour la compatibilité avec Android, modifications affectées aux composants dépendants de la plate-forme (OpenGL ES, initialisation du contexte graphique)
  7. Créez et testez le projet sur l’émulateur.

Modèle de projet

Chargement des sources SDL, SDL Image, SDL Mixer :
https://www.libsdl.org/download-2.0.php
Le dossier docs contient des instructions détaillées pour travailler avec le modèle de projet Android ; copiez le répertoire du projet Android dans un dossier séparé, créez un lien symbolique ou copiez le dossier SDL dans Android-project/app/jni.
Nous substituons l’identifiant correct au drapeau avd, lançons l’émulateur Android depuis le répertoire Sdk :

cd ~/Android/Sdk/emulator
./emulator -avd Pixel_2_API_24

Spécifiez les chemins dans le script, assemblez le projet :

rm -rf app/build || true
export ANDROID_HOME=/home/demensdeum/Android/Sdk/
export ANDROID_NDK_HOME=/home/demensdeum/Android/android-ndk-r21-beta2/
./gradlew clean build
./gradlew installDebug

Le modèle de projet SDL avec le code C du fichier doit être assemblé

android-sdl-test-app/cube-art-project-android/app/jni/src/YourSourceHere.c

Dépendances

Téléchargez le code source dans les archives pour SDL_image, SDL_mixer :
https://www.libsdl.org/projects/SDL_image/
https://www.libsdl.org/projects/SDL_mixer/

Chargement des dépendances de votre projet, par exemple mes bibliothèques partagées :
https://gitlab.com/demensdeum/FlameSteelCore/
https://gitlab.com/demensdeum/FlameSteelCommonTraits
https://gitlab.com/demensdeum/FlameSteelBattleHorn
https://gitlab.com/demensdeum/FlameSteelEngineGameToolkit/
https://gitlab.com/demensdeum/FlameSteelEngineGameToolkitFSGL
https://gitlab.com/demensdeum/FSGL
https://gitlab.com/demensdeum/cube-art-project

Nous téléchargeons tout cela dans app/jni, chaque « module » dans un dossier séparé, par exemple app/jni/FSGL. Ensuite, vous avez la possibilité de trouver des générateurs fonctionnels pour les fichiers Application.mk et Android.mk, je ne les ai pas trouvés, mais il existe peut-être une solution simple basée sur CMake. Suivez les liens et commencez à vous familiariser avec le format de fichier d’assemblage pour Android NDK :
https://developer.android.com/ndk/guides/application_mk
https://developer.android.com/ndk/guides/android_mk

Vous devriez également en savoir plus sur les différentes implémentations d’APP_STL dans NDK :
https://developer.android.com/ndk/guides/cpp-support.html

Après familiarisation, nous créons un fichier Android.mk pour chaque « module », suivi d’un exemple de fichier d’assemblage de la bibliothèque partagée Cube-Art-Project :

LOCAL_PATH := $(call my-dir)
include $(CLEAR_VARS)

APP_STL := c++_static
APP_CPPFLAGS := -fexceptions
LOCAL_MODULE := CubeArtProject
LOCAL_C_INCLUDES := $(LOCAL_PATH)/src $(LOCAL_PATH)/../include $(LOCAL_PATH)/../include/FlameSteelCommonTraits/src/FlameSteelCommonTraits
LOCAL_EXPORT_C_INCLUDES = $(LOCAL_PATH)/src/

define walk
$(wildcard $(1)) $(foreach e, $(wildcard $(1)/*), $(call walk, $(e)))
endef

ALLFILES = $(call walk, $(LOCAL_PATH)/src)
FILE_LIST := $(filter %.cpp, $(ALLFILES))
$(info CubeArtProject source code files list)
$(info $(FILE_LIST))
LOCAL_SRC_FILES := $(FILE_LIST:$(LOCAL_PATH)/%=%)

LOCAL_SHARED_LIBRARIES += FlameSteelCore
LOCAL_SHARED_LIBRARIES += FlameSteelBattleHorn
LOCAL_SHARED_LIBRARIES += FlameSteelCommonTraits
LOCAL_SHARED_LIBRARIES += FlameSteelEngineGameToolkit
LOCAL_SHARED_LIBRARIES += FlameSteelEngineGameToolkitFSGL
LOCAL_SHARED_LIBRARIES += FSGL
LOCAL_SHARED_LIBRARIES += SDL2
LOCAL_SHARED_LIBRARIES += SDL2_image

LOCAL_LDFLAGS := -static-libstdc++
include $(BUILD_SHARED_LIBRARY)

Tout utilisateur expérimenté de CMake comprendra cette configuration dès les premières lignes, les formats sont très similaires, Android.mk n’a pas GLOB_RECURSIVE, vous devez donc rechercher de manière récursive les fichiers sources à l’aide de la fonction walk.

Nous modifions Application.mk, Android.mk pour créer du code C++ et non C :

APP_ABI := armeabi-v7a arm64-v8a x86 x86_64
APP_PLATFORM=android-16
APP_STL := c++_static
APP_CPPFLAGS := -fexceptions

Renommer YourSourceHere.c -> YourSourceHere.cpp, récupérer les entrées, modifier le chemin dans l’assembly, par exemple :

app/jni/src/Android.mk:LOCAL_SRC_FILES := YourSourceHere.cpp

Ensuite, essayez de construire le projet, si vous voyez des erreurs du compilateur concernant l’absence d’en-têtes, puis vérifiez l’exactitude des chemins dans Android.mk ; S’il y a des erreurs de l’éditeur de liens comme « référence non définie », vérifiez que les fichiers de code source dans les assemblys sont correctement spécifiés ; les listes peuvent être tracées en spécifiant $(info $(FILE_LIST)) dans le fichier Android.mk. N’oubliez pas le mécanisme de double liaison, en utilisant des modules dans la clé LOCAL_SHARED_LIBRARIES et en corrigeant la liaison via LD, par exemple pour FSGL :

LOCAL_LDLIBS := -lEGL -lGLESv2

Adaptation et lancement

J’ai dû modifier certaines choses, par exemple supprimer GLEW des versions pour iOS et Android, renommer certains appels OpenGL, ajouter le suffixe EOS (glGenVertexArrays -> glGenVertexArraysOES), inclure une macro pour les fonctions de débogage modernes manquantes , la cerise sur le gâteau est l’inclusion implicite des en-têtes GLES2 indiquant la macro GL_GLEXT_PROTOTYPES 1 :

#define GL_GLEXT_PROTOTYPES 1
#include "SDL_opengles2.h"

J’ai aussi observé un écran noir aux premiers lancements avec une erreur du type “E/libEGL: validate_display:255 error 3008 (EGL_BAD_DISPLAY)”, j’ai changé l’initialisation de la fenêtre SDL, le profil OpenGL et tout a fonctionné :

SDL_DisplayMode mode;
SDL_GetDisplayMode(0,0,&mode);
int width = mode.w;
int height = mode.h;

window = SDL_CreateWindow(
            title,
            0,
            0,
            width,
            height,
            SDL_WINDOW_OPENGL | SDL_WINDOW_FULLSCREEN | SDL_WINDOW_RESIZABLE
        );

SDL_GL_SetAttribute( SDL_GL_CONTEXT_PROFILE_MASK, SDL_GL_CONTEXT_PROFILE_ES );

Sur l’émulateur, l’application est installée par défaut avec l’icône SDL et le nom « Jeu ».

Il me reste juste à explorer la possibilité de générer automatiquement des fichiers d’assembly basés sur CMake, ou de migrer des assemblys pour toutes les plateformes vers Gradle ; cependant, CMake reste le choix de facto pour le développement C++ en cours.

Code source

https://gitlab.com/demensdeum/android- sdl-test-app
https://gitlab.com/demensdeum/android-sdl-test-app/tree/master/cube-art-project-android

Sources

https://developer.android.com/ ndk/guides/cpp-support.html
https://developer.android.com/ndk/guides/application_mk
https://developer.android.com/ndk/guides/android_mk
https://lazyfoo.net/tutorials/SDL/52_hello_mobile/android_windows/index.php
https://medium.com/androiddevelopers/getting-started-with-c-and-android-native-activities-2213b402ffff

Monde à l’envers

Pour développer un nouveau projet, Cube Art Project a adopté la méthodologie Test Driven Development. Dans cette approche, un test pour une fonctionnalité spécifique de l’application est d’abord implémenté, puis la fonctionnalité spécifique est implémentée. Je considère que le gros avantage de cette approche réside dans la mise en œuvre des interfaces finales, qui sont aussi peu impliquées que possible dans les détails de mise en œuvre, avant le début du développement des fonctionnalités. Avec cette approche, le test dicte la poursuite de l’implémentation, ajoutant tous les avantages de la programmation contractuelle, lorsque les interfaces sont des contrats pour une implémentation spécifique.
Projet d’art cubique – Un éditeur 3D dans lequel l’utilisateur construit des figures à partir de cubes ; il n’y a pas si longtemps, ce genre était très populaire. Puisqu’il s’agit d’une application graphique, j’ai décidé d’ajouter des tests avec validation de capture d’écran.
Pour valider les captures d’écran, vous devez les récupérer depuis le contexte OpenGL, cela se fait à l’aide de la fonction glReadPixels. La description des arguments de la fonction est simple : position de départ, largeur, hauteur, format (RGB/RGBA/etc.), pointeur vers le tampon de sortie ; toute personne ayant travaillé avec SDL ou ayant de l’expérience avec les tampons de données en C remplacera simplement les arguments nécessaires. Cependant, je pense qu’il est nécessaire de décrire une fonctionnalité intéressante du tampon de sortie glReadPixels : les pixels y sont stockés de bas en haut, tandis que dans SDL_Surface, toutes les opérations de base se déroulent de haut en bas.
Autrement dit, après avoir chargé une capture d’écran de référence à partir d’un fichier png, je n’ai pas pu comparer directement les deux tampons, car l’un d’eux était à l’envers.
Pour retourner le tampon de sortie d’OpenGL, vous devez le remplir en soustrayant la hauteur de la capture d’écran pour la coordonnée Y. Cependant, il convient de considérer qu’il y a une chance d’aller au-delà des limites du tampon si vous n’en soustrayez pas une lors du remplissage, ce qui le fera. conduire à une corruption de la mémoire.
Comme j’essaie toujours d’utiliser le paradigme POO de « programmation par interfaces », au lieu d’un accès direct à la mémoire de type C par pointeur, lorsque j’ai essayé d’écrire des données en dehors du tampon, l’objet m’en a informé grâce à la validation des limites dans la méthode. .
Le code final pour la méthode permettant d’obtenir une capture d’écran de haut en bas :

    auto width = params->width;
    auto height = params->height;

    auto colorComponentsCount = 3;
    GLubyte *bytes = (GLubyte *)malloc(colorComponentsCount * width * height);
    glReadPixels(0, 0, width, height, GL_RGB, GL_UNSIGNED_BYTE, bytes);

    auto screenshot = make_shared(width, height);

    for (auto y = 0; y < height; y++) {
        for (auto x = 0; x < width; x++) {
            auto byteX = x * colorComponentsCount;
            auto byteIndex = byteX + (y * (width * colorComponentsCount));
            auto redColorByte = bytes[byteIndex];
            auto greenColorByte = bytes[byteIndex + 1];
            auto blueColorByte = bytes[byteIndex + 2];
            auto color = make_shared(redColorByte, greenColorByte, blueColorByte, 255);
            screenshot->setColorAtXY(color, x, height - y - 1);
        }
    }

    free(bytes);

Sources

https://community.khronos.org/ t/glreadpixels-fliped-image/26561
https://stackoverflow.com/questions/8346115/why-are-bmps-stored-upside-down

Code source

https://gitlab.com/demensdeum/cube- art-project-bootstrap

Sous-chaîne commune la plus longue

Dans cet article, je décrirai un algorithme permettant de résoudre le plus grand problème de sous-chaîne courant. Supposons que nous essayions de décrypter des données binaires chiffrées. Essayons d’abord de trouver des modèles communs en recherchant la plus grande sous-chaîne.
Exemple de chaîne d’entrée :
adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
Nous recherchons une chaîne qui se répète deux fois :
EN-TÊTE DE DONNÉES ??

Préfixes

Tout d’abord, écrivons une méthode pour comparer les préfixes de deux chaînes, laissons-la renvoyer la chaîne résultante dans laquelle les caractères du préfixe de gauche sont égaux aux caractères du préfixe de droite.
Par exemple, pour les lignes :

        val lhs = "asdfWUKI"
        val rhs = "asdfIKUW"

Chaîne de résultat – asdf
Exemple en Kotlin :

fun longestPrefix(lhs: String, rhs: String): String {
        val maximalLength = min(lhs.length-1, rhs.length -1)
        for (i in 0..maximalLength) {
            val xChar = lhs.take(i)
            val yChar = rhs.take(i)
                if (xChar != yChar) {
                    return lhs.substring(0, i-1)
                }
        }
        return lhs.substring(0,maximalLength)
}

Force Brute

Lorsque les choses ne fonctionnent pas bien, vous devriez recourir à la force brute. En utilisant la méthode longestPrefix, nous allons parcourir la chaîne en deux boucles, la première prend la chaîne de i à la fin, la seconde de i + 1 à la fin, les transmet pour rechercher le plus grand préfixe. La complexité temporelle de cet algorithme est d’environ O(n^2) ~ O(n*^3).
Exemple en Kotlin :

fun searchLongestRepeatedSubstring(searchString: String): String {
        var longestRepeatedSubstring = ""
        for (x in 0..searchString.length-1) {
            val lhs = searchString.substring(x)
            for (y in x+1..searchString.length-1) {
                val rhs = searchString.substring(y)
                val longestPrefix = longestPrefix(lhs, rhs)
                if (longestRepeatedSubstring.length < longestPrefix.length) {
                    longestRepeatedSubstring = longestPrefix
                }
            }
        }
        return longestRepeatedSubstring
}

Tableau de suffixes

Pour une solution plus élégante, nous avons besoin d'un outil : une structure de données appelée "Suffix Array". Cette structure de données est un tableau de sous-chaînes remplies dans une boucle, où chaque sous-chaîne commence du caractère suivant de la ligne jusqu'à la fin.
Par exemple, pour la ligne :

adasDATAHEADER??

Le tableau de suffixes ressemble à ceci :

adasDATAHEADER??
dasDATAHEADER??
asDATAHEADER??
sDATAHEADER??
DATAHEADER??
ATAHEADER??
TAHEADER??
AHEADER??
HEADER??
EADER??
ADER??
DER??
ER??
R??
??
?

On résout en triant

Trions le tableau de suffixes, puis parcourons tous les éléments dans une boucle où l'élément actuel est dans la main gauche (à gauche), le suivant est dans la main droite (à droite) et calculons le préfixe le plus long en utilisant le plus longPrefix méthode.
Exemple en Kotlin :

fun searchLongestRepeatedSubstring(searchString: String): String {
    val suffixTree = suffixArray(searchString)
    val sortedSuffixTree = suffixTree.sorted()

    var longestRepeatedSubstring = ""
    for (i in 0..sortedSuffixTree.count() - 2) {
        val lhs = sortedSuffixTree[i]
        val rhs = sortedSuffixTree[i+1]
        val longestPrefix = longestPrefix(lhs, rhs)
        if (longestRepeatedSubstring.length < longestPrefix.length) {
            longestRepeatedSubstring = longestPrefix
        }
    }
    return longestRepeatedSubstring
}

La complexité temporelle de l'algorithme est O(N log N), ce qui est bien meilleur qu'une solution simple.

Sources

https://en.wikipedia.org/wiki/Longest_common_substring_problem

Code source

https://gitlab.com/demensdeum/algorithms

Tri par insertion, tri par fusion

Tri par insertion

Tri par insertion – chaque élément est comparé aux précédents de la liste et l’élément est échangé avec le plus grand, le cas échéant, sinon la boucle de comparaison interne s’arrête. Étant donné que les éléments sont triés du premier au dernier, chaque élément est comparé à une liste déjà triée, ce qui *éventuellement* réduit le temps d’exécution global. La complexité temporelle de l’algorithme est O(n^2), c’est-à-dire identique à la variété des bulles.

Fusionner le tri

Tri par fusion – la liste est divisée en groupes d’un élément, puis les groupes sont « fusionnés » par paires avec comparaison simultanée. Dans mon implémentation, lors de la fusion de paires, les éléments de gauche sont comparés aux éléments de droite, puis déplacés vers la liste résultante si les éléments de gauche ont disparu, alors tous les éléments de droite sont ajoutés à la liste résultante ; liste (leur comparaison supplémentaire est inutile, puisque tous les éléments des groupes passent par des itérations de tri)< br />Le travail de cet algorithme est très simple à paralléliser ; l’étape de fusion des paires peut être effectuée en threads, en attendant la fin des itérations dans le répartiteur.
Résultat de l’algorithme pour l’exécution monothread :

["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["Alice", "John"], ["#1", "Mike"], ["20", "Артем"], ["60", "60"], ["DoubleTrouble"]]
[["#1", "Alice", "John", "Mike"], ["20", "60", "60", "Артем"], ["DoubleTrouble"]]
[["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"], ["DoubleTrouble"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

Sortie de l’algorithme pour l’exécution multithread :

["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["20", "Артем"], ["Alice", "John"], ["60", "60"], ["#1", "Mike"], ["DoubleTrouble"]]
[["#1", "60", "60", "Mike"], ["20", "Alice", "John", "Артем"], ["DoubleTrouble"]]
[["DoubleTrouble"], ["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

La complexité temporelle de l’algorithme est O(n*log(n)), ce qui est légèrement meilleur que O(n^2)

Sources

https://en.wikipedia.org/wiki/Insertion_sort
https://en.wikipedia.org/wiki/Merge_sort

Code source

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

Tri à bulles à Erlang

Le tri par bulles est assez ennuyeux, mais il devient plus intéressant si vous essayez de l’implémenter dans un langage fonctionnel pour les télécommunications – c’est à dire. Erlang.

Nous avons une liste de numéros, nous devons la trier. L’algorithme de tri à bulles parcourt toute la liste, en itérant et en comparant les nombres par paires. Lors de la vérification, ce qui suit se produit : un nombre plus petit est ajouté à la liste de sortie, ou les nombres sont intervertis dans la liste actuelle s’il y en a moins à droite, la recherche continue avec le numéro suivant dans l’itération ; Ce parcours est répété jusqu’à ce qu’il n’y ait plus de remplacements dans la liste.

En pratique, cela ne vaut pas la peine d’être utilisé en raison de la grande complexité temporelle de l’algorithme – O(n^2); Je l’ai implémenté en Erlang, dans le style impératif, mais si vous êtes intéressé, vous pouvez rechercher de meilleures options :

-module(bubbleSort).
-export([main/1]).

startBubbleSort([CurrentHead|Tail]) ->
    compareHeads(CurrentHead, Tail, [], [CurrentHead|Tail]).

compareHeads(CurrentHead, [NextHead|Tail], [], OriginalList) ->   
    if
        CurrentHead < NextHead ->
            compareHeads(NextHead, Tail, [CurrentHead], OriginalList);
        true ->
            compareHeads(CurrentHead, Tail, [NextHead], OriginalList)
    end;
    
compareHeads(CurrentHead, [NextHead|Tail], OriginalOutputList, OriginalList) ->
    if
        CurrentHead < NextHead ->
            OutputList = OriginalOutputList ++ [CurrentHead],
            compareHeads(NextHead, Tail, OutputList, OriginalList);
        true ->
            OutputList = OriginalOutputList ++ [NextHead],
            compareHeads(CurrentHead, Tail, OutputList, OriginalList)
    end;
  
compareHeads(CurrentHead, [], OriginalOutputList, OriginalList) ->
    OutputList = OriginalOutputList ++ [CurrentHead],
    if
        OriginalList == OutputList ->
            io:format("OutputList: ~w~n", [OutputList]);
        true ->
            startBubbleSort(OutputList)
    end.
  
main(_) ->
    UnsortedList = [69,7,4,44,2,9,10,6,26,1],
    startBubbleSort(UnsortedList).

Installation et lancement

Dans Ubuntu, Erlang est très facile à installer ; il suffit de taper sudo apt install erlang dans le terminal. Dans ce langage, chaque fichier doit être un module, avec une liste de fonctions pouvant être utilisées en externe – exporter. Les fonctionnalités intéressantes du langage incluent l’absence de variables, uniquement des constantes, l’absence de syntaxe standard pour la POO (ce qui n’empêche pas l’utilisation de techniques de POO), et bien sûr des calculs parallèles sans verrous basés sur le modèle d’acteur.

Vous pouvez exécuter le module soit via la console erl interactive, en exécutant une commande après l’autre, soit plus simplement via l’escript bubbleSort.erl ; Dans différents cas, le fichier aura un aspect différent, par exemple, pour escript, vous devez créer une fonction principale à partir de laquelle il démarrera.

Sources

https://www.erlang.org/
https://habr.com/ru/post/197364/

Code source

https://gitlab.com/ demensdeum/algorithms/blob/master/bubbleSort/bubbleSort.erl

Algorithme de comparaison lexicographique

L’algorithme de comparaison de chaînes lexicographiques fonctionne très simplement : les codes de caractères sont comparés en boucle et le résultat est renvoyé si les caractères ne sont pas égaux.

Un exemple pour le langage C peut être trouvé ici :
https://github.com/gcc-mirror/gcc/blob/master/libiberty/memcmp.c

Il convient de prendre en compte le fait que vous devez comparer les caractères dans un seul encodage statique, par exemple dans Swift, j’ai utilisé la comparaison caractère par caractère en UTF-32. L’option de tri de tableau utilisant memcmp fonctionnera exactement pour les caractères à un octet, dans d’autres cas (codages de longueur variable), l’ordre peut être incorrect. Je n’exclus pas la possibilité d’une implémentation basée sur des encodages de longueur variable, mais ce sera très probablement un ordre de grandeur plus compliqué.

La complexité temporelle de l’algorithme est O(1) dans le meilleur des cas, O(n) dans la moyenne et le pire des cas

Sources

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

Sources

https://gitlab.com/demensdeum /algorithms/blob/master/lexiCompare/lexiCompare.swift

Développement de jeux pour ZX Spectrum en C

Cet article absurde est dédié au développement d’un jeu pour l’ancien ordinateur ZX Spectrum en C. Jetons un coup d’œil au beau mec :

Sa production a commencé en 1982 et a été produite jusqu’en 1992. Caractéristiques techniques de la machine : processeur Z80 8 bits, 16-128 Ko de mémoire et autres extensions, comme la puce sonore AY-3-8910.

Dans le cadre du concours Yandex Retro Games Battle 2019 pour cette machine, j’ai écrit un jeu appelé Interceptor 2020. Comme je n’ai pas eu le temps d’apprendre le langage assembleur pour le Z80, j’ai décidé de le développer en C. En tant que chaîne d’outils, j’ai choisi un ensemble prêt à l’emploi – z88dk, qui contient des compilateurs C et de nombreuses bibliothèques auxiliaires pour accélérer la mise en œuvre des applications pour Spectrum. Il prend également en charge de nombreuses autres machines Z80, telles que les calculatrices MSX et Texas Instruments.

Ensuite, je décrirai mon survol superficiel de l’architecture informatique, la chaîne d’outils z88dk, et montrerai comment j’ai réussi à mettre en œuvre l’approche POO et à utiliser des modèles de conception.

Fonctionnalités d’installation

L’installation de z88dk doit être effectuée conformément au manuel du référentiel, cependant, pour les utilisateurs d’Ubuntu, je voudrais noter une fonctionnalité – Si vous avez déjà installé des compilateurs pour Z80 à partir de packages deb, vous devez les supprimer, puisque z88dk y accédera à partir du dossier bin par défaut en raison de l’incompatibilité des versions du compilateur de la chaîne d’outils, vous ne pourrez probablement rien compiler.< /p>

Bonjour tout le monde

Écrire Hello World est très simple :

#include 

void main()
{
    printf("Hello World");
}

Il est encore plus simple de compiler un fichier tap :

zcc +zx -lndos -create-app -o helloworld helloworld.c

Pour l’exécuter, utilisez n’importe quel émulateur ZX Spectrum prenant en charge les fichiers Tap, par exemple en ligne :
http://jsspeccy.zxdemo.org/

Dessinez sur l’image en plein écran

tl;dr Les images sont dessinées en tuiles, des tuiles de taille 8×8 pixels, les tuiles elles-mêmes sont intégrées dans la police Spectrum, puis l’image est imprimée sous forme de ligne à partir des index.

La bibliothèque de sortie de sprites et de tuiles sp1 génère des tuiles en utilisant UDG. L’image est traduite en un ensemble d’UDG individuels (tuiles), puis assemblés sur l’écran à l’aide d’indices. Il ne faut pas oublier que UDG est utilisé pour afficher du texte, et si votre image contient un très grand ensemble de tuiles (par exemple, plus de 128 tuiles), alors vous devrez dépasser les limites de l’ensemble et effacer le spectre par défaut. fonte. Pour contourner cette limitation, j’ai utilisé une base de 128 – 255 en simplifiant les images tout en laissant la police d’origine en place. À propos de la simplification des images ci-dessous.

Pour dessiner des images en plein écran, vous devez vous armer de trois utilitaires :
Gimp
img2spec
png2c-z88dk

Il existe un moyen pour les vrais hommes ZX, les vrais guerriers rétro, celui-ci consiste à ouvrir un éditeur graphique à l’aide de la palette Spectrum, connaissant les caractéristiques de la sortie de l’image, à la préparer manuellement et à la télécharger en utilisant png2c-z88dk ou png2scr.< /p>

Le moyen le plus simple – prenez une image 32 bits, changez le nombre de couleurs sur 3-4 dans Gimp, modifiez-la légèrement, puis importez-la dans img2spec afin de ne pas travailler manuellement avec les restrictions de couleur, exportez png et convertissez-la en tableau C en utilisant png2c- z88dk.

N’oubliez pas que pour une exportation réussie, chaque vignette ne peut pas contenir plus de deux couleurs.

En conséquence, vous recevrez un fichier h contenant le nombre de tuiles uniques, s’il y en a plus de ~128, alors simplifiez l’image dans Gimp (augmentez la répétabilité) et effectuez la procédure d’exportation sur une nouvelle. .

Après l’exportation, vous chargez littéralement la « police » des vignettes et imprimez le « texte » des index des vignettes sur l’écran. Vous trouverez ci-dessous un exemple de la « classe » de rendu :

// грузим шрифт в память
    unsigned char *pt = fullscreenImage->tiles;

    for (i = 0; i < fullscreenImage->tilesLength; i++, pt += 8) {
            sp1_TileEntry(fullscreenImage->tilesBase + i, pt);
    }

    // ставим курсор в 0,0
    sp1_SetPrintPos(&ps0, 0, 0);

    // печатаем строку
    sp1_PrintString(&ps0, fullscreenImage->ptiles);

Dessiner des sprites sur l’écran

Ensuite, je décrirai une méthode pour dessiner des sprites de 16 à 16 pixels sur l’écran. Je n’ai pas abordé l’animation et le changement de couleurs, parce que… C’est trivial qu’à ce stade déjà, comme je suppose, j’ai manqué de mémoire. Par conséquent, le jeu ne contient que des sprites monochromes transparents.

Nous dessinons une image png monochrome 16×16 dans Gimp, puis en utilisant png2sp1sprite nous la traduisons en un fichier d’assemblage asm, en code C nous déclarons des tableaux à partir du fichier d’assemblage et ajoutons le fichier au stade de l’assemblage.< /p>

Après l’étape de déclaration de la ressource sprite, celle-ci doit être ajoutée à l’écran à la position souhaitée, ci-dessous un exemple de code pour la « classe » de l’objet du jeu :

    struct sp1_ss *bubble_sprite = sp1_CreateSpr(SP1_DRAW_MASK2LB, SP1_TYPE_2BYTE, 3, 0, 0);
    sp1_AddColSpr(bubble_sprite, SP1_DRAW_MASK2,    SP1_TYPE_2BYTE, col2-col1, 0);
    sp1_AddColSpr(bubble_sprite, SP1_DRAW_MASK2RB,  SP1_TYPE_2BYTE, 0, 0);
    sp1_IterateSprChar(bubble_sprite, initialiseColour);

À partir des noms des fonctions, vous pouvez comprendre approximativement la signification de « – allouez de la mémoire pour le sprite, ajoutez deux colonnes 8×8, ajoutez une couleur pour le sprite.

La position du sprite est indiquée dans chaque image :

sp1_MoveSprPix(gameObject->gameObjectSprite, Renderer_fullScreenRect, gameObject->sprite_col, gameObject->x, gameObject->y);

Émulation de la POO

Il n’y a pas de syntaxe pour la POO en C, que devez-vous faire si vous le souhaitez toujours ? Vous devez connecter votre esprit et être éclairé par l’idée qu’il n’existe pas d’équipement POO ; tout revient finalement à l’une des architectures de machines, dans lesquelles il n’y a tout simplement aucun concept d’objet et d’autres abstractions qui lui sont associées.< /p>

Ce fait m’a empêché pendant très longtemps de comprendre pourquoi la POO est nécessaire, pourquoi il est nécessaire de l’utiliser si en fin de compte tout se résume au code machine.

Cependant, après avoir travaillé dans le développement de produits, j’ai découvert les plaisirs de ce paradigme de programmation, principalement, bien sûr, la flexibilité du développement, les mécanismes de protection du code, avec la bonne approche, la réduction de l’entropie, la simplification du travail d’équipe. Tous les avantages ci-dessus découlent de trois piliers : polymorphisme, encapsulation, héritage.

Il convient également de noter la simplification de la résolution des problèmes liés à l’architecture des applications, car 80 % des problèmes architecturaux ont été résolus par des informaticiens au siècle dernier et décrits dans la littérature sur les modèles de conception. Ensuite, je décrirai les façons d’ajouter une syntaxe de type POO au C.

Il est plus pratique de prendre des structures C comme base pour stocker les données d’une instance de classe. Bien sûr, vous pouvez utiliser un tampon d’octets, créer votre propre structure pour les classes, les méthodes, mais pourquoi réinventer la roue ? Après tout, nous réinventons déjà la syntaxe.

Données de classe

Exemple de champs de données « classe » GameObject :

struct GameObjectStruct {
    struct sp1_ss *gameObjectSprite;
    unsigned char *sprite_col;
    unsigned char x;
    unsigned char y;
    unsigned char referenceCount;
    unsigned char beforeHideX;
    unsigned char beforeHideY;
};
typedef struct GameObjectStruct GameObject;

Enregistrez notre classe sous « GameObject.h », faites #include « GameObject.h » au bon endroit et utilisez-la.

Méthodes de classe

Compte tenu de l’expérience des développeurs du langage Objective-C, la signature d’une méthode de classe sera constituée de fonctions dans une portée globale, le premier argument sera toujours la structure des données, suivi des arguments de la méthode. Vous trouverez ci-dessous un exemple de « méthode » de la « classe » GameObject :

void GameObject_hide(GameObject *gameObject) {
    gameObject->beforeHideX = gameObject->x;
    gameObject->beforeHideY = gameObject->y;
    gameObject->y = 200;
}

L’appel de méthode ressemble à ceci :

GameObject_hide(gameObject);

Les constructeurs et les destructeurs sont implémentés de la même manière. Il est possible d’implémenter un constructeur en tant qu’allocateur et initialiseur de champ, mais je préfère contrôler l’allocation et l’initialisation des objets séparément.

Travailler avec la mémoire

Gestion manuelle de la mémoire du formulaire à l’aide de malloc et free enveloppé dans des macros new et delete pour correspondre à C++ :

#define new(X) (X*)malloc(sizeof(X))
#define delete(X) free(X)

Pour les objets utilisés par plusieurs classes à la fois, une gestion semi-manuelle de la mémoire est implémentée sur la base d’un comptage de références, à l’image et à la ressemblance de l’ancien mécanisme Objective-C Runtime ARC :

void GameObject_retain(GameObject *gameObject) {
    gameObject->referenceCount++;
}

void GameObject_release(GameObject *gameObject) {
    gameObject->referenceCount--;

    if (gameObject->referenceCount < 1) { sp1_MoveSprAbs(gameObject->gameObjectSprite, &Renderer_fullScreenRect, NULL, 0, 34, 0, 0);
        sp1_DeleteSpr(gameObject->gameObjectSprite);
        delete(gameObject);
    }
}

Ainsi, chaque classe doit déclarer l’utilisation d’un objet partagé en utilisant retention, libérant ainsi la propriété via release. La version moderne d’ARC utilise des appels automatiques de rétention/libération.

Le son !

Le Spectrum dispose d’un tweeter capable de reproduire de la musique 1 bit ; les compositeurs de l’époque étaient capables de reproduire jusqu’à 4 canaux sonores simultanément.

Le Spectrum 128k contient une puce sonore distincte AY-3-8910, qui peut lire de la musique de suivi.

Une bibliothèque est proposée pour utiliser le tweeter dans le z88dk

Ce qui reste à apprendre

Je souhaitais me familiariser avec Spectrum, implémenter le jeu à l’aide du z88dk et apprendre beaucoup de choses intéressantes. J’ai encore beaucoup à apprendre, par exemple l’assembleur Z80, car il me permet d’utiliser toute la puissance du Spectrum, de travailler avec des banques de mémoire et de travailler avec la puce sonore AY-3-8910. J’espère participer au concours l’année prochaine !

Liens

https://rgb.yandex
https://vk.com/sinc_lair
https://www.z88dk.org/forum/

Code source

https://gitlab.com/demensdeum/ zx-projects/tree/master/interceptor2020

Recherche binaire

Supposons que nous ayons besoin de savoir si l’adresse e-mail « demensdeum@gmail.com » est incluse dans la liste des adresses e-mail autorisées pour la réception de lettres. .

Parcourons toute la liste du premier au dernier élément, en vérifiant si l’élément est égal à l’adresse spécifiée – Implémentons un algorithme de recherche linéaire. Mais cela prendra beaucoup de temps, n’est-ce pas ?

Pour répondre à cette question, utilisez la notation « Complexité temporelle des algorithmes », « O ». Le temps de fonctionnement de la recherche linéaire dans le pire des cas est égal au nième nombre d’éléments du tableau, écrivons cela en notation « O » – Sur). Ensuite, nous devons expliquer que pour tout algorithme connu, il existe trois indicateurs de performance : temps d’exécution dans le meilleur des cas, le pire des cas et la moyenne. Par exemple, l’adresse mail « demensdeum@gmail.com » est dans le premier index du tableau, elle sera alors trouvée dans la première étape de l’algorithme, il s’ensuit que le temps d’exécution est au mieux – O(1); et si à la fin de la liste, alors c’est le pire des cas – O(n)

Mais qu’en est-il des détails de la mise en œuvre logicielle et des performances matérielles ? Ils devraient influencer Big O ? Maintenant, respirez et imaginez que le calcul de la complexité temporelle soit calculé pour une machine idéale abstraite, dans laquelle il n’y a que cet algorithme et rien d’autre.

Algorithme

Ok, il s’avère que la recherche linéaire est assez lente, essayons d’utiliser la recherche binaire. Pour commencer, il convient de préciser que nous ne travaillerons pas avec des données binaires ; ce nom a été donné à cette méthode en raison des particularités de son travail. Initialement, nous trions le tableau en ordre lexicographique, puis l’algorithme prend la plage de l’ensemble du tableau, obtient l’élément central de la plage, le compare lexicographiquement, et en fonction du résultat de la comparaison, décide quelle plage utiliser pour poursuivre la recherche – la moitié supérieure du courant ou la moitié inférieure. Autrement dit, à chaque étape de recherche, une décision est prise parmi deux options possibles : logique binaire. Cette étape est répétée jusqu’à ce que le mot soit trouvé ou non (l’intersection des indices inférieur et supérieur de la plage se produit).

Performances de cet algorithme – le meilleur des cas est lorsqu’un élément est immédiatement trouvé au milieu du tableau O(1), le pire des cas d’énumération est O(log n)

Pièges

Lors de l’implémentation de la recherche binaire, j’ai non seulement rencontré le problème intéressant du manque de standardisation de la comparaison lexicographique dans les bibliothèques de langages de programmation, mais j’ai même découvert l’absence d’un standard unifié pour l’implémentation localeCompare dans JavaScript. La norme ECMAScript permet différentes implémentations de cette fonction, c’est pourquoi lors du tri à l’aide de localeCompare, des résultats complètement différents peuvent être observés sur différents moteurs JavaScript.

Par conséquent, pour que l’algorithme fonctionne correctement, il faut trier et utiliser uniquement le même algorithme de comparaison lexicographique, sinon rien ne fonctionnera. Co-mais si, par exemple, vous essayez de trier un tableau dans Scala et d’effectuer une recherche à l’aide de nodejs, sans implémenter votre propre tri/tri d’une implémentation, alors rien ne vous attend sauf une déception humaine.

Sources

Qu’est-ce que la comparaison lexicographique et que représente-t-elle ?
Почему для вычисления сложности алгоритмов используется log N вместо lb N?
Двоичный поиск
Знай сложности алгоритмов
https://stackoverflow.com/questions/52941016/sorting-in-localecompare-in-javascript

Code source

https://gitlab.com/demensdeum/algorithms

Façade à motifs


La façade fait référence aux modèles de conception structurelle. Il fournit une interface unique qui permet de travailler avec des systèmes complexes, permettant aux clients de ne pas avoir de détails d’implémentation sur ces systèmes, simplifiant ainsi leur code et implémentant un couplage lâche entre les clients et les systèmes de niveau inférieur. GoF a un bon exemple de façade – un compilateur de langage de programmation qui offre à différents clients poursuivant différents objectifs la possibilité d’assembler du code via une interface de façade de compilateur unique.

Sources

https://refactoring.guru/ru/design-patterns/facade
https://www.amazon.com/Design-Patterns-Elements-Reusable-Object-Oriented/dp/0201633612

Modèle d’usine abstrait

Usine abstraite– fournit une interface pour créer des objets associés, sans spécifier de classes spécifiques.

J’aime vraiment le nom alternatif de ce modèle : ; Kit (Kit)

Elle est très similaire à la Méthode d’usine, cependant, les Usines abstraites doivent décrire la relation entre les objets en cours de création, sinon il s’agit simplement d’un Objet divin. l’anti-modèle qui crée tout est aléatoire.

Imaginez développer un framework AR pour lunettes ; nous affichons sur l’écran des flèches de navigation intérieures, des icônes de magasins, des lieux intéressants, des fenêtres et des boutons avec des informations sur tout endroit où se trouve actuellement l’utilisateur.

Dans le même temps, nous avons besoin de pouvoir personnaliser l’apparence et le comportement des contrôles de l’environnement AR. C’est précisément dans ce cas que vous devez utiliser le modèle Set.

Écrivons l’interface de Abstract Factory et des Abstract Products – protocoles parents, éléments de l’environnement AR :

protocol ARFactory {
    func arrow() -> ARArrow
    func icon() -> ARIcon
    func button() -> ARButton
    func window() -> ARWindow
}

protocol ARArrow {
    var image: { get }
    func handleSelection()
}

protocol ARIcon {
    var image: { get }
    var title: String
}

protocol ARButton {
    var title: String
    func handleSelection()
}

protocol ARWindow {
    var title: String
    var draw(canvas: Canvas)
}

Les développeurs de kits devront désormais implémenter une Concrete Factory basée sur l’interface Abstract Factory, et ils devront implémenter tous les éléments ensemble ; le reste de l’application pourra travailler avec l’usine sans changer leur code.< /p>

Sources

https://refactoring.guru/ru/design-patterns /usine-abstraite
https://www.amazon.com/Design-Patterns-Elements-Reusable-Object-Oriented/dp/0201633612

Méthode d’usine

Le modèle Factory Method fait référence à des modèles de conception génératifs.
Ce modèle décrit la création d’une interface pour créer un objet d’une classe spécifique. Cela semble simple, non ?

En théorie

Supposons que nous développions un cadre pour travailler avec des lunettes AR. Lorsque vous inclinez la tête sur le côté, un menu d’applications disponibles devrait apparaître devant les yeux de l’utilisateur. Les applications seront développées par des sociétés tierces, clientes de notre framework. Naturellement, nous ne savons pas quelles applications, icônes, noms doivent apparaître, nous devons donc fournir une interface pour implémenter l’icône et les informations associées sur l’application. Appelons-le Produit :

protocol Product {
 var name: String { get }
 var image: Image { get }
 var executablePath: String { get }
}

Ensuite, nous devons fournir une interface afin que nos clients puissent mettre en œuvre la délivrance d’une gamme d’applications pour leur Produit spécifique – un tableau d’icônes d’application avec des noms, que nous dessinerons déjà dans le framework.

Écrivons cette interface – Interface Creator contenant une Méthode Factory renvoyant un tableau de Produits.

protocol Creator {
 func factoryMethod() -> [Product]
}

En pratique

Le premier client de notre framework AR était la société 7B – principal fournisseur de logiciels pour cafetières au Honduras. Ils souhaitent vendre des lunettes de réalité augmentée capables de préparer du café, de vérifier si l’eau ou les grains sont pleins et d’indiquer le chemin jusqu’à la cafetière la plus proche en utilisant le mode carte intérieure.

Ils se chargent du développement du logiciel ; nous sommes uniquement tenus de fournir une documentation sur les interfaces Creator et Produit pour le bon affichage de la liste des applications et leurs suites. lancer.

Après avoir transféré la documentation, la société 7B, à l’aide de l’interface Creator , implémente le Specific Creator – classe renvoyant un tableau d’icônes d’application. Les applications d’icônes elles-mêmes sont des classes Produit spécifique qui implémentent l’interface Produit.

Exemple de code pour Produits spécifiques :

class CoffeeMachineLocator: implements Product {
 let name = “7B Coffee Machine Locator v.3000”
 let image = Image.atPath(“images/locator.tga”)
 let executablePath = “CoffeeMachineLocator.wasm”
}

class iPuchinno: implements Product {
 let name = “iPuchinno 1.0.3”
 let image = Image.atPath(“images/puchino.pvrtc”)
 let executablePath = “neutron/ipuchBugFixFinalNoFreezeFixAlpha4.js”
}

Classe Concrete Creator, offrant un éventail de deux applications :

class 7BAppsCreator: implements Creator {
 func factoryMethod() -> [Product] {
  return [CoffeeMachineLocator(), iPuchinno()]
 }
}

Après cela, la société 7B compile la bibliothèque de Concrete Products, Concrete Creator et la combine avec notre framework, commence à vendre des lunettes AR pour ses cafetières, ajouts de notre part non requis.

Sources

https://refactoring.guru/ru/design-patterns/command
https://www.amazon.com/Design-Patterns-Elements-Reusable-Object-Oriented/dp/0201633612

Commande de modèle

Le modèle de commande fait référence aux modèles de conception comportementale.

C’est le modèle avec lequel je suis resté le plus longtemps, il est si simple qu’il en est très complexe. Mais personnellement, je trouve que la beauté de l’auto-apprentissage est que vous avez tout le temps du monde pour rechercher un certain sujet sous tous les angles.

Ainsi, dans le GoF, l’applicabilité est décrite de manière assez succincte et claire :
Encapsule une requête en tant qu’objet, vous permettant de paramétrer des clients avec différentes requêtes, d’utiliser des files d’attente, de consigner les requêtes et d’effectuer des opérations d’annulation.

Implémentons maintenant une version simple de la commande à partir de la description :

string fakeTrumpsRequest = “SELECT * from Users where name beginsWith DonaldTrump”

Nous avons encapsulé la requête dans un objet de classe chaîne, il peut être utilisé pour configurer les clients, ajouter des commandes à la file d’attente, enregistrer, annuler (en utilisant le modèle « Snapshot »)

Il me semble que cela suffit amplement pour effectuer des requêtes SQL et autres, mais il y a ensuite des détails d’implémentation, différentes options d’application, la base de code du modèle, les rôles client et les classes auxiliaires.

Pièces matérielles

Le

modèle de commande commence par un protocole de commande, qui contient une seule méthode execute(). Vient ensuite la Commande spécifique et le récepteur. Le CC implémente l’opération sur le récepteur, décrit la connexion entre le récepteur et l’action. Quelque chose n’est pas clair ? Moi aussi, mais passons à autre chose. Le Client crée une instance d’une Commande Spécifique, l’associe au Récepteur. Invocateur – objet qui exécute le processus de lancement des Commandes.

Essayons maintenant de comprendre à l’aide d’un exemple, disons que nous voulons mettre à jour myOS sur myPhone, pour ce faire, nous lançons l’application myOS_Update !, nous y appuyons sur le bouton Mettre à jour maintenant, après 10 secondes, le système le fera ! signaler une mise à jour réussie.

Le client dans l’exemple ci-dessus est l’application myOS_Update!, l’Invoker est le bouton “Mettre à jour maintenant !”, il lance la Commande spécifique mettre à jour le système à l’aide de la méthode execute(), qui accède au Récepteur– Démon de mise à jour du système d’exploitation.

Utiliser un exemple

Acceptons l’interface utilisateur de l’application myOS_Update ! si bon qu’ils ont décidé de le vendre en tant que produit distinct pour fournir une interface permettant de mettre à jour d’autres systèmes d’exploitation. Dans ce cas, nous implémenterons une application avec prise en charge des extensions via des bibliothèques, dans les bibliothèques il y aura des implémentations de Commandes spécifiques, récepteurs, nous laisserons Invoker statique/immuable. , Client, protocole Commandes.

Ainsi, il n’est pas nécessaire de prendre en charge le code mutable, puisque notre code restera inchangé, des problèmes ne peuvent survenir que lorsqu’il est implémenté côté client, en raison d’erreurs dans le code de leurs Commandes spécifiques et Récepteurs. De plus, dans cette implémentation, il n’est pas nécessaire de transférer le code source de l’application principale, c’est-à-dire que nous avons encapsulé les commandes et les interactions de l’interface utilisateur à l’aide du modèle Command.

Sources

https://refactoring.guru/ru/design-patterns/command
https://www.amazon.com/Design-Patterns-Elements-Reusable-Object-Oriented/dp/0201633612

Création d’applications macOS pour Ubuntu OSXCross CMake

Dans cet article, je décrirai la création d’applications C++ multiplateformes pour macOS sur une machine de build Ubuntu à l’aide de CMake et osxcross.
Tout d’abord, installez la chaîne d’outils osxcross :
https://github.com/tpoechtrager/osxcross
L’installation se déroule en 3 étapes, téléchargement des dépendances :

cd tools
./get_dependencies.sh

Téléchargez XCode.xip depuis le site officiel d’Apple, puis téléchargez le SDK depuis XCode :

./gen_sdk_package_pbzx.sh /media/demensdeum/2CE62A79E62A4404/LinuxSupportStorage/xcode111.xip

J’espère que vous avez lu le contrat de licence XCode lors de la dernière étape ? Ensuite, créez la chaîne d’outils avec le préfixe requis :

INSTALLPREFIX=/home/demensdeum/Apps/osxcross ./build.sh 

Vous pouvez maintenant utiliser osxcross à partir du répertoire de préfixes de l’étape précédente. Ajoutons une nouvelle macro de build pour CMake, écrivons tout ce qui est nécessaire :

if (OSXCROSS)
SET(CMAKE_SYSTEM_NAME Darwin)
SET(CMAKE_C_COMPILER o64-clang)
SET(CMAKE_CXX_COMPILER o64-clang++)
SET(CMAKE_C_COMPILER_AR x86_64-apple-darwin19-ar)
SET(CMAKE_CXX_COMPILER_AR x86_64-apple-darwin19-ar)
SET(CMAKE_LINKER x86_64-apple-darwin19-ld)
SET(ENV{OSXCROSS_MP_INC} 1)
endif()

La liaison dynamique n’a pas fonctionné pour moi, nous exportons donc les bibliothèques de manière statique :

if (OSXCROSS)
add_library(FlameSteelCore STATIC ${SOURCE_FILES})
else()

Ensuite, vous pourriez être confronté au fait que vous ne disposez pas des bibliothèques nécessaires pour osxcross, j’ai rencontré ce problème lors de l’utilisation de SDL2. osxcross prend en charge les packages de bibliothèques prêts à l’emploi – macports. Par exemple, en installant SDL2-mixer :

osxcross-macports -v install libsdl2_mixer

Après cela, vous pouvez commencer à créer des bibliothèques/applications comme d’habitude dans le lien cmake-make, n’oubliez pas de spécifier des liens statiques de bibliothèques si nécessaire.

Assemblage manuel des bibliothèques

Actuellement, j’ai rencontré le problème d’un archivage incorrect des bibliothèques lors de la liaison statique ; lors de la construction de l’application finale, je reçois l’erreur :

file was built for archive which is not the architecture being linked (x86_64)

Très similaire à ce ticket, nous avons réussi à implémenter un solution de contournement qui permet à l’assemblage de se terminer correctement. Décompressons la bibliothèque statique et recréons-la à l’aide de l’archiveur osxcross :

ar x ../libFlameSteelCore.a
rm ../libFlameSteelCore.a
x86_64-apple-darwin19-ar rcs ../libFlameSteelCore.a *.o

Personnellement, je considère aussi que l’un des problèmes est le manque de possibilité d’exécuter des applications macOS directement sur Ubuntu (au moins avec certaines fonctionnalités). Bien sûr, il existe un projet darling, mais le support laisse encore beaucoup à désirer.

Sources

https://github.com/tpoechtrager/osxcross

Construire pour Windows sous Ubuntu MinGW CMake

Dans cet article, je décrirai le processus de création de bibliothèques et d’applications pour Windows à l’aide de la chaîne d’outils MinGW32 sur Ubuntu.
Installez wine, mingw :

sudo apt-get install wine mingw-w64

Après cela, vous pouvez déjà créer des applications C/C++ pour Windows :

# C
i686-w64-mingw32-gcc helloWorld.c -o helloWorld32.exe      # 32-bit
x86_64-w64-mingw32-gcc helloWorld.c -o helloWorld64.exe    # 64-bit
 
# C++
i686-w64-mingw32-g++ helloWorld.cc -o helloWorld32.exe     # 32-bit
x86_64-w64-mingw32-g++ helloWorld.cc -o helloWorld64.exe   # 64-bit

L’exe collecté peut être vérifié à l’aide de wine.

Ensuite, regardons les modifications apportées à la build CMake, le fichier CMakeLists.txt, en ajoutant des éléments spécifiques à MinGW au fichier de build :

if (MINGW32)
set(CMAKE_SYSTEM_NAME Windows)
SET(CMAKE_C_COMPILER i686-w64-mingw32-gcc)
SET(CMAKE_CXX_COMPILER i686-w64-mingw32-g++)
SET(CMAKE_RC_COMPILER i686-w64-mingw32-windres)
set(CMAKE_RANLIB i686-w64-mingw32-ranlib)
endif()

// для сборки shared dll
elseif (MINGW32)
add_library(FlameSteelEngineGameToolkit.dll SHARED ${SOURCE_FILES})
else()

// обязательно линкуем со всеми зависимостями
if (MINGW32)
target_link_libraries(
                        FlameSteelEngineGameToolkit.dll 
                        -static-libgcc
                        -static-libstdc++
                        SDL2 
                        SDL2_mixer 
                        /home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelCore/FlameSteelCore.dll
                        /home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelBattleHorn/FlameSteelBattleHorn.dll
                        /home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelCommonTraits/FlameSteelCommonTraits.dll)

set_target_properties(FlameSteelEngineGameToolkit.dll PROPERTIES
        PREFIX ""
        SUFFIX ""
        LINK_FLAGS "-Wl,--add-stdcall-alias"
        POSITION_INDEPENDENT_CODE 0 # this is to avoid MinGW warning; 
        # MinGW generates position-independent-code for DLL by default
)
else()

Collecte :

cmake -DMINGW32=1 .
make

Le résultat sera une DLL ou un exe, selon ce que vous collectez. Pour un exemple fonctionnel, vous pouvez consulter le référentiel du nouveau Cube-Art-Project et ses bibliothèques :
https://gitlab.com/demensdeum/cube-art-project
https://gitlab.com/demensdeum/FlameSteelEngineGameToolkitFSGL
https://gitlab.com/demensdeum/cube-art-project-bootstrap

Sources
https://arrayfire.com/cross-compile-to-windows-from-linux/

Test automatique Emscripten simple pour ChromeDriver

Dans cette note, je décrirai l’implémentation de l’exécution d’un autotest pour le ChromeDriver du navigateur Chrome, qui exécute un module d’autotest traduit du C++ à l’aide d’Emscripten, lit la sortie de la console et renvoie le résultat du test.
Vous devez d’abord installer Selenium, pour Python 3-Ubuntu, cela se fait comme ceci :

pip3 install selenium

Ensuite, téléchargez ChromeDriver depuis le site officiel, placez chromedriver dans /usr/local/bin, par exemple, après quoi vous pourrez commencer à implémenter l’autotest.
Ci-dessous, je vais donner le code d’autotest qui lance le navigateur Chrome avec la page d’autotest ouverte sur Emscripten, vérifie la présence du texte “Test de la fenêtre réussi” :

import time
from selenium import webdriver
from selenium.webdriver.common.keys import Keys
from selenium.webdriver.common.desired_capabilities import DesiredCapabilities

capabilities = DesiredCapabilities.CHROME
capabilities['goog:loggingPrefs'] = { 'browser':'ALL' }
driver = webdriver.Chrome()
driver.get("http://localhost/windowInitializeTest/indexFullscreen.html")

time.sleep(2)

exitCode = 1

for entry in driver.get_log('browser'):
    if entry["source"] == "console-api":
        message = entry["message"]
        if "Window test succeded" in message:
            print("Test succeded")
            exitCode = 0

driver.close()
exit(exitCode)

Enregistrez le test sous main.py et exécutez python3 main.py

Construire un projet avec des dépendances pour Emscripten

Dans cet article, je décrirai la construction d’un projet composé de plusieurs bibliothèques utilisant Emscripten.
Pour le moment, Emscripten ne prend pas en charge la création de bibliothèques partagées, la première étape consiste donc à transférer toutes les bibliothèques de Partagé vers Statique. Emscripten fonctionne avec ses propres fichiers d’inclusion, le problème de visibilité des fichiers d’en-tête doit donc être résolu en transmettant un lien symbolique du répertoire système vers la chaîne d’outils Emscripten :

ln -s /usr/local/include/FlameSteelFramework $EMSDK/fastcomp/emscripten/system/include/FlameSteelFramework

Si vous utilisez CMake, vous devez alors modifier SHARED->STATIC dans le fichier CMakeLists.txt de la méthode add_library. Vous pouvez créer une bibliothèque/application pour des liens statiques supplémentaires à l’aide des commandes :

emcmake cmake .
emmake make

Ensuite, vous devrez construire l’application principale en spécifiant les fichiers de bibliothèque *.a au stade de la liaison. Je n’ai pas pu spécifier un chemin relatif ; la construction s’est terminée correctement uniquement après avoir spécifié les chemins complets dans le fichier CMakeLists.txt :

elseif(EMSCRIPTEN)
target_link_libraries(${FSEGT_PROJECT_NAME} GL GLEW 
/home/demensdeum/Sources/cube-art-project-bootstrap/cube-art-project/sharedLib/libCubeArtProject.a 
/home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelEngineGameToolkitFSGL/libFlameSteelEngineGameToolkitFSGL.a 
/home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelEngineGameToolkit/libFlameSteelEngineGameToolkit.a 
/home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelCore/libFlameSteelCore.a 
/home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelBattleHorn/libFlameSteelBattleHorn.a 
/home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FSGL/libFSGL.a 
/home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelCommonTraits/libFlameSteelCommonTraits.a)
else()

Sources

https://emscripten.org/ docs/compiling/Building-Projects.html#using-libraries

Bibliothèque partagée CMake C++

J’ai récemment décidé de séparer toutes les parties des bibliothèques partagées FlameSteelFramework, puis je montrerai un exemple de fichier CMakeLists.txt pour FlameSteelCore :

cmake_minimum_required(VERSION 3.5)

project (FlameSteelCore)
set(CMAKE_BUILD_TYPE Release)

include_directories(${CMAKE_CURRENT_SOURCE_DIR}/src)

file(GLOB_RECURSE SOURCE_FILES
    "src/FlameSteelCore/*.cpp"
)

add_library(FlameSteelCore SHARED ${SOURCE_FILES})

install(DIRECTORY "${CMAKE_SOURCE_DIR}/src/FlameSteelCore"
        DESTINATION include/FlameSteelFramework
        FILES_MATCHING
        PATTERN "*.h"
)

install(TARGETS FlameSteelCore DESTINATION lib)

Commandes exécutées par CMake : collecte tous les fichiers avec l’extension *.cpp du répertoire src/FlameSteelCore/ dans une bibliothèque partagée, copie tous les en-têtes avec l’extension *.h de src/FlameSteelCore pour inclure/FlameSteelFramework (dans mon cas c’est /usr/ local/include/FlameSteelFramework), copie la bibliothèque partagée dans le répertoire lib (/usr/local/lib)
Après l’installation, il peut être nécessaire de mettre à jour le cache LD – sudo ldconfig.
Pour construire et installer sur Ubuntu (si vous disposez de la bonne chaîne d’outils de construction), exécutez simplement les commandes suivantes :

cmake . && make && sudo make install

Pour tester le processus d’installation, je passe le préfixe make au dossier local makeInstallTestPlayground :

cmake -DCMAKE_INSTALL_PREFIX:PATH=/home/demensdeum/makeInstallTestPlayground . && make && make install

Références

https : //stackoverflow.com/questions/17511496/how-to-create-a-shared-library-with-cmake
https://stackoverflow.com/questions/6003374/what-is-cmake-equivalent-of-configure-prefix-dir-make-all-install

Interpréteur de langage C++ – S’accrocher

Il n’y a pas longtemps, je suis tombé sur un projet intéressant appelé Cling, un interpréteur de langage C++ qui peut, entre autres, fonctionner de manière interactive depuis la console. Vous pouvez consulter le projet sur le lien suivant : https://github.com/root -projet/ s’accrocher
L’installation pour Ubuntu est simple : téléchargez l’archive pour la version requise, décompressez-la, accédez au dossier bin et exécutez cling dans le terminal.
Vous trouverez ci-dessous un exemple de chargement de la bibliothèque FlameSteelCore, d’initialisation de l’objet, d’impression de l’identifiant :

Exceptions Emscripten perdues et problèmes d’expression régulière

Exception perdue

Une fonctionnalité intéressante d’Emscripten : lorsque vous démarrez une boucle de jeu via emscripten_set_main_loop, vous devez vous rappeler que la gestion des exceptions doit être ré-ajoutée via try catch directement dans la méthode de boucle, car Le runtime perd le bloc try catch de l’extérieur.
Le moyen le plus simple est d’afficher le texte d’erreur à l’aide du navigateur à l’aide de l’alerte javascript :

            catch (const std::exception &exc)
            {
                const char *errorText = exc.what();
                cout << "Exception: " << errorText << "; Stop execution" << endl;

                EM_ASM_(
                {
                    var errorText = UTF8ToString($0);
                    alert(errorText);

                }, errorText);

                abort();

Expression rationnelle trop complexe

L'implémentation std de regex peut lever une exception error_complexity si elle considère que l'expression régulière est trop complexe. Cela se produit dans l'implémentation actuelle d'emscripten, je vous suggère donc d'implémenter des tests d'analyse via des expressions régulières ou d'utiliser des implémentations d'expressions régulières tierces.

Générateur de modèles

Le pattern Builder appartient à un groupe de patterns dont l’existence ne m’est pas particulièrement claire, je constate la redondance évidente de celui-ci. Appartient au groupe des modèles de conception génératifs. Utilisé pour implémenter une interface simple pour créer des objets complexes.

Applicabilité

Simplification de l’interface. Cela peut faciliter la création d’un objet dans des constructeurs avec un grand nombre d’arguments, et améliorer objectivement la lisibilité du code.

Exemple en C++ sans builder :

auto weapon = new Weapon(“Claws”);
monster->weapon = weapon;
auto health = new MonsterHealth(100);
monster->health = health;

Пример со строителем на C++:

                  .addWeapon(“Claws”)
                  .addHealth(100)
                  .build();

Однако в языках поддерживающих именованные аргументы (named arguments), необходимость использовать именно для этого случая отпадает.

Пример на Swift с использованием named arguments:

let monster = Monster(weapon: “Claws”, health: 100)

Immuabilité. Grâce au générateur, vous pouvez assurer l’encapsulation de l’objet créé jusqu’à l’étape d’assemblage final. Ici, vous devez bien réfléchir pour savoir si l’utilisation d’un modèle vous évitera la dynamique élevée de l’environnement dans lequel vous travaillez ; peut-être que l’utilisation du modèle ne donnera rien, en raison du simple manque de culture d’utilisation de l’encapsulation au sein de l’équipe de développement ; .

Interaction avec les composants à différentes étapes de la création de l’objet. En utilisant également le modèle, il est possible d’assurer la création étape par étape d’un objet lors de l’interaction avec d’autres composants du système. Très probablement, c’est très utile (?)

Critique

Bien sûr, vous devez réfléchir *soigneusement* à la question de savoir s’il vaut la peine de généraliser l’utilisation du modèle dans votre projet. Des langages dotés d’une syntaxe moderne et d’un IDE avancé éliminent le besoin d’utiliser le Builder, en termes d’amélioration de la lisibilité du code (voir le point sur les arguments nommés)
Ce modèle aurait-il dû être utilisé en 1994, lorsque le livre du GoF a été publié ? Très probablement oui, cependant, à en juger par la base de code Open source de ces années-là, peu de gens l’utilisaient.

Sources

https://refactoring.guru/ru/design-patterns/builder

Composition de motifs

Le modèle composite fait référence à des modèles de conception structurelle ; dans les sources nationales, il est connu sous le nom de « compositeur ».
Disons que nous développons une application – photo album. L’utilisateur peut créer des dossiers, y ajouter des photos et effectuer d’autres manipulations. Vous avez absolument besoin de pouvoir afficher le nombre de fichiers dans les dossiers, le nombre total de tous les fichiers et dossiers.
Il est évident qu’il faut utiliser un arbre, mais comment implémenter une architecture arborescente avec une interface simple et pratique ? Le motif Composite vient à la rescousse.

Sheila dans Moonducks

Ensuite, dans le répertoire, nous implémentons la méthode dataCount() – en parcourant tous les éléments du tableau de composants, en additionnant tous leurs dataCount.
Tout est prêt !
Voici un exemple dans Go :
package main

import "fmt"

type component interface {

dataCount() int

}

type file struct {

}

type directory struct {

c []component

}

func (f file) dataCount() int {

return 1

}

func (d directory) dataCount() int {

var outputDataCount int = 0

for _, v := range d.c {
outputDataCount += v.dataCount()
}

return outputDataCount

}

func (d *directory) addComponent(c component) {

d.c = append(d.c, c)

}

func main() {

var f file
var rd directory
rd.addComponent(f)
rd.addComponent(f)
rd.addComponent(f)
rd.addComponent(f)

fmt.Println(rd.dataCount())

var sd directory
sd.addComponent(f)

rd.addComponent(sd)
rd.addComponent(sd)
rd.addComponent(sd)

fmt.Println(sd.dataCount())
fmt.Println(rd.dataCount())

}

Sources

https://refactoring.guru/ru/design-patterns/ composite

Adaptateur de motif

Benjamín Núñez González

Le modèle Adaptateur fait référence aux modèles de conception structurelle.

L’adaptateur permet la conversion de données/interface entre deux classes/interfaces.

Supposons que nous développions un système permettant de déterminer les objectifs d’un acheteur dans un magasin, basé sur des réseaux de neurones. Le système reçoit un flux vidéo d’une caméra du magasin, identifie les clients par leur comportement et les classe en groupes. Types de groupes – est venu acheter (acheteur potentiel), juste pour regarder (spectateur), est venu voler quelque chose (voleur), est venu rendre la marchandise (acheteur insatisfait), est venu ivre / défoncé (chahuteur potentiel).

Comme tous les développeurs expérimentés, nous trouvons un réseau neuronal prêt à l’emploi qui peut classer les espèces de singes dans une cage sur la base d’un flux vidéo, que l’Institut zoologique du zoo de Berlin a aimablement mis à disposition gratuitement, le recycler sur un flux vidéo du magasin et obtenez un système de pointe fonctionnel.

Il y a juste un petit problème – le flux vidéo est encodé au format mpeg2 et notre système ne prend en charge que OGG Theora. Nous n’avons pas le code source du système, la seule chose que nous pouvons faire est de « » modifier l’ensemble de données et entraîner le réseau neuronal. Ce qu’il faut faire? Écrivez une classe d’adaptateur qui transférera le flux depuis mpeg2 -> OGG Theora et l’enverra au réseau neuronal.

Selon le schéma classique, le modèle implique le client, la cible, l’adapté et l’adaptateur. Le client dans ce cas est un réseau de neurones qui reçoit un flux vidéo dans OGG Theora, cible – l’interface avec laquelle il interagit, adaptée – interface d’envoi de flux vidéo en mpeg2, adaptateur – convertit mpeg2 en OGG Theora et l’envoie via l’interface cible.

Est-ce que tout semble simple ?

Sources

https://ru.wikipedia.org/wiki/Adapter_ (design_pattern)
https://refactoring.guru/ru/design-patterns/adapter

Modèle de délégué

Le modèle de délégué est l’un des principaux modèles de conception.
Disons que nous développons une application pour salon de coiffure. L’application dispose d’un calendrier pour sélectionner un jour d’enregistrement ; en appuyant sur la date, une liste de barbiers avec un choix devrait s’ouvrir.
Implémentons une liaison naïve des composants du système, combinons le calendrier et l’écran à l’aide de pointeurs les uns vers les autres pour implémenter un affichage de liste :


// псевдокод

class BarbershopScreen {
   let calendar: Calendar

   func showBarbersList(date: Date) {
      showSelectionSheet(barbers(forDate: date))
   }
}

class Calendar {
    let screen: BarbershopScreen

    func handleTap(on date: Date) {
        screen.showBarbersList(date: date)
    }
}

Au bout de quelques jours, les exigences changent ; avant d’afficher la liste, vous devez présenter des offres avec un choix de prestations (taille de barbe, etc.), mais pas toujours, tous les jours sauf le samedi.
On ajoute au calendrier une vérification si c’est samedi ou non, selon cela, on appelle la méthode de la liste des barbiers ou de la liste des services, pour plus de clarté je vais démontrer :


// псевдокод

class BarbershopScreen {
   let calendar: Calendar

   func showBarbersList(date: Date) {
      showSelectionSheet(barbers(forDate: date))
   }

   func showOffersList() {
      showSelectionSheet(offers)
   }
}

class Calendar {
    let screen: BarbershopScreen

    func handleTap(on date: Date)  {
        if date.day != .saturday {
             screen.showOffersList()
        }
        else {
             screen.showBarbersList(date: date)
        }
    }
}

Une semaine plus tard, on nous demande d’ajouter un calendrier à l’écran de commentaires, et à ce moment-là, les premiers oups architecturaux se produisent !
Ce qu’il faut faire? Le calendrier est étroitement lié à l’écran de rendez-vous chez la coupe de cheveux.
Ouah! Pouah! oh-oh
Si vous continuez à travailler avec cette architecture d’application folle, vous devez faire une copie de l’intégralité de la classe de calendrier et associer cette copie à l’écran de commentaires.
Ok, ça a l’air bien, puis nous avons ajouté quelques écrans supplémentaires et plusieurs copies du calendrier, et puis le moment X est arrivé. On nous a demandé de modifier la conception du calendrier, ce qui signifie que nous devons maintenant trouver toutes les copies du calendrier et ajouter les mêmes modifications à toutes. Cette « approche » affecte grandement la vitesse de développement et augmente le risque de commettre une erreur. En conséquence, de tels projets se retrouvent dans un état d’échec, lorsque même l’auteur de l’architecture originale ne comprend plus comment fonctionnent les copies de ses classes, et que d’autres hacks ajoutés en cours de route s’effondrent à la volée.
Que fallait-il faire, ou mieux encore, que n’était-il pas trop tard pour commencer à faire ? Utilisez le modèle de délégation !
La délégation est un moyen de transmettre les événements de classe via une interface commune. Vous trouverez ci-dessous un exemple de délégué pour un calendrier :

protocol CalendarDelegate {
   func calendar(_ calendar: Calendar, didSelect date: Date)
}

Ajoutons maintenant le code permettant de travailler avec le délégué à l’exemple de code :


// псевдокод

class BarbershopScreen: CalendarDelegate {
   let calendar: Calendar

   init() {
       calendar.delegate = self
   }

   func calendar(_ calendar: Calendar, didSelect date: Date) {
        if date.day != .saturday {
            showOffersList()
        }
        else {
             showBarbersList(date: date)
        }
   }

   func showBarbersList(date: Date) {
      showSelectionSheet(barbers(forDate: date))
   }

   func showOffersList() {
      showSelectionSheet(offers)
   }
}

class Calendar {
    weak var delegate: CalendarDelegate

    func handleTap(on date: Date)  {
        delegate?.calendar(self, didSelect: date)
    }
}

En conséquence, nous avons complètement dissocié le calendrier de l’écran ; lors de la sélection d’une date dans le calendrier, il transmet l’événement de sélection de date – *délègue* le traitement des événements à l’abonné ; L’abonné est l’écran.
Quels avantages tirons-nous de cette approche ? Nous pouvons désormais modifier la logique du calendrier et de l’écran indépendamment les uns des autres sans dupliquer les classes, ce qui simplifie davantage la prise en charge ; De cette manière, le « principe de responsabilité exclusive » pour la mise en œuvre des composants du système est mis en œuvre et le principe DRY est respecté.
Lors de l’utilisation de la délégation, vous pouvez ajouter, modifier la logique d’affichage des fenêtres, l’ordre de tout ce qui apparaît à l’écran, et cela n’affectera en rien le calendrier et les autres classes, qui ne devraient objectivement pas participer à des processus qui ne leur sont pas directement liés.< br />Alternativement, les programmeurs qui ne se dérangent pas trop utilisent l’envoi de messages via un bus commun, sans écrire d’interface protocole/délégué séparée, où il serait préférable d’utiliser la délégation. J’ai parlé des inconvénients de cette approche dans un article précédent : “Modèle d’observateur.”

Sources

https://refactoring.guru/ru/replace-inheritance -avec-délégation

Modèle d’observateur

Le modèle Observer fait référence à des modèles de conception comportementale.
Le modèle permet d’envoyer un changement d’état d’un objet aux abonnés à l’aide d’une interface commune.
Disons que nous développons un messager pour les programmeurs, nous avons un écran de discussion dans l’application. Lorsque vous recevez un message avec le texte « problème » et « erreur » ou « quelque chose ne va pas », vous devez colorer l’écran de la liste d’erreurs et l’écran des paramètres en rouge.
Ensuite, je décrirai 2 options pour résoudre le problème, la première est simple mais extrêmement difficile à prendre en charge, et la seconde est beaucoup plus stable en termes de support, mais vous oblige à tourner la tête lors de la mise en œuvre initiale.

Bus commun

Toutes les implémentations du modèle contiennent l’envoi de messages lorsque les données changent, l’abonnement aux messages et un traitement ultérieur dans les méthodes. L’option de bus partagé contient un seul objet (généralement un singleton) qui distribue les messages aux destinataires.
La simplicité de mise en œuvre est la suivante :

  1. L’objet envoie un message abstrait au bus partagé
  2. Un autre objet abonné au bus partagé récupère le message et décide de le traiter ou non.

L’une des options d’implémentation disponibles auprès d’Apple (sous-système NSNotificationCenter), ajout d’une correspondance entre l’en-tête du message et le nom de la méthode appelée par le destinataire lors de la livraison.
Le plus gros inconvénient de cette approche – Si vous modifiez davantage le message, vous devrez d’abord vous souvenir, puis modifier manuellement tous les endroits où il est traité et envoyé. Il existe un cas de mise en œuvre initiale rapide, suivie d’un support long et complexe qui nécessite une base de connaissances pour un fonctionnement correct.

Délégué multidiffusion

Dans cette implémentation, nous créerons la classe déléguée multicast finale ; tout comme dans le cas d’un bus partagé, les objets peuvent s’y abonner pour recevoir des « messages » ou des « événements », mais le travail d’analyse et de filtrage des messages est non affecté aux objets. Au lieu de cela, les classes d’abonnés doivent implémenter les méthodes de multidiffusion du délégué avec lesquelles il les notifie.
Ceci est implémenté en utilisant des interfaces/protocoles délégués ; lorsque l’interface générale change, l’application ne sera plus construite, il sera alors nécessaire de refaire tous les emplacements de traitement d’un message donné, sans avoir besoin de maintenir une base de connaissances distincte. pour me souvenir de ces lieux. Le compilateur est votre ami.
Cette approche augmente la productivité de l’équipe, car il n’est pas nécessaire d’écrire ou de stocker de la documentation, il n’est pas nécessaire qu’un nouveau développeur essaie de comprendre comment un message et ses arguments sont traités, mais ils travaillent avec une interface pratique et compréhensible. , c’est ainsi qu’est implémenté le paradigme de la documentation par le code.
Le délégué de multidiffusion lui-même est basé sur le modèle de délégué, dont je parlerai dans le prochain article.

Sources

https://refactoring.gu/ru/design-patterns/observer

Modèle de proxy

Le modèle Proxy fait référence à des modèles de conception structurelle.
Le modèle décrit la technique de travail avec une classe via une couche de classe – ; procuration. Un proxy vous permet de modifier les fonctionnalités de la classe d’origine, avec la possibilité de conserver le comportement d’origine, tout en conservant l’interface de classe d’origine.
Imaginons la situation – en 2015, l’un des pays d’Europe occidentale a décidé d’enregistrer toutes les demandes adressées aux sites Internet des utilisateurs du pays, afin d’améliorer les statistiques et une compréhension approfondie des sentiments politiques des citoyens.
Imaginons le pseudocode d’une implémentation naïve de la passerelle que les citoyens utilisent pour accéder à Internet :

class InternetRouter {

    private let internet: Internet

    init(internet: Internet) {
        self.internet = internet
    }

    func handle(request: Request, from client: Client) -> Data {
        return self.internet.handle(request)
    }

}

Dans le code ci-dessus, nous créons une classe de routeur Internet avec un pointeur vers un objet qui fournit un accès à Internet. Lorsqu’un client fait une demande de site Web, nous renvoyons une réponse depuis Internet.

En utilisant le modèle Proxy et l’anti-modèle singleton, nous ajouterons une fonctionnalité pour enregistrer le nom et l’URL du client :

class InternetRouterProxy {

    private let internetRouter: InternetRouter

    init(internet: Internet) {
        self.internetRouter = InternetRouter(internet: internet)
    }

    func handle(request: Request, from client: Client) -> Data {

        Logger.shared.log(“Client name: \(client.name), requested URL: \(request.URL)”)

        return self.internetRouter.handle(request: request, from: client)
    }

}

En raison de la préservation de l’interface InternetRouter d’origine dans la classe proxy InternetRouterProxy, il suffit de remplacer la classe d’initialisation d’InternerRouter par son proxy, aucune autre modification de la base de code n’est requise.

Sources

https://refactoring.guru/ru/design-patterns/ mandataire

Modèle Prototype

Le modèle prototype appartient au groupe des modèles de conception génératifs.
Disons que nous développons des applications de rencontres Tender. Selon notre modèle commercial, nous avons la possibilité payante de faire des copies de votre propre profil, en changeant automatiquement le nom et l’ordre des photos par endroits. Cela a été fait pour que l’utilisateur puisse avoir la possibilité de gérer plusieurs profils à la fois avec un groupe d’amis différent dans l’application.
En cliquant sur le bouton pour créer une copie du profil, nous devons mettre en œuvre la copie du profil, la génération automatique d’un nom et le retriage des photos.
Implémentation naïve du pseudocode :

fun didPressOnCopyProfileButton() {
    let profileCopy = new Profile()
    profileCopy.name = generateRandomName()
    profileCopy.age = profile.age
    profileCopy.photos = profile.photos.randomize()
    storage.save(profileCopy)
}

Imaginons maintenant que d’autres membres de l’équipe aient fait un copier-coller du code de copie ou l’aient créé à partir de zéro, et qu’après cela, un nouveau champ ait été ajouté – ; goûts. Ce champ stocke le nombre de likes du profil, vous devez maintenant mettre à jour *tous* les endroits où la copie s’effectue manuellement en ajoutant un nouveau champ. La maintenance du code, ainsi que les tests, prennent beaucoup de temps et sont difficiles.
Pour résoudre ce problème, le modèle de conception Prototype a été inventé. Créons un protocole de copie général, avec une méthode copy() qui renvoie une copie d’un objet avec les champs nécessaires. Après avoir modifié les champs d’entité, vous n’aurez besoin de mettre à jour qu’une seule méthode copy(), au lieu de rechercher et de mettre à jour manuellement tous les emplacements contenant du code de copie.

Sources

https://refactoring.guru/ru/design-patterns/prototype

Machine à états et modèle Condition

Dans cet article, je vais décrire l’utilisation de la machine à états (State Machine), montrer une implémentation simple, une implémentation utilisant le modèle State. Il convient de mentionner qu’il n’est pas souhaitable d’utiliser le modèle d’État s’il y a moins de trois États, car cela conduit généralement à une complexité inutile dans la lisibilité du code et à des problèmes de support associés – tout doit être modéré.

MEAACT PHOTO / STUART PRICE.

Seigneur des drapeaux

Supposons que nous développions un écran de lecteur vidéo pour le système multimédia d’un avion civil, le lecteur doit être capable de charger un flux vidéo, de le lire, de permettre à l’utilisateur d’arrêter le processus de téléchargement, de rembobiner et d’effectuer d’autres opérations habituelles pour un joueur.
Supposons que le lecteur ait mis en cache le morceau suivant du flux vidéo, vérifié qu’il y a suffisamment de morceaux pour la lecture, commencé à lire le fragment à l’utilisateur et continue en même temps à télécharger le suivant.
À ce stade, l’utilisateur revient au milieu de la vidéo, c’est-à-dire qu’il doit maintenant arrêter de lire le fragment en cours et commencer le chargement à partir d’une nouvelle position. Cependant, il existe des situations dans lesquelles cela ne peut pas être fait : l’utilisateur ne peut pas contrôler la lecture du flux vidéo pendant qu’on lui montre une vidéo sur la sécurité aérienne. Vérifions l’indicateur isSafetyVideoPlaying pour vérifier cette situation.
Le système doit également être capable de mettre en pause la vidéo en cours et de diffuser une alerte du capitaine et de l’équipage du navire via le lecteur. Ajoutons un autre indicateur isAnnouncementPlaying. De plus, il est obligatoire de ne pas mettre la lecture en pause lors de l’affichage de l’aide sur l’utilisation du lecteur, un autre indicateur est HelpPresenting.

Exemple de pseudocode du lecteur multimédia :

class MediaPlayer {

    public var isHelpPresenting = false
    public var isCaching = false
    public var isMediaPlaying: Bool = false
    public var isAnnouncementPlaying = false
    public var isSafetyVideoPlaying = false

    public var currentMedia: Media = null

    fun play(media: Media) {

        if isMediaPlaying == false, isAnnouncementPlaying == false, isSafetyVideoPlaying == false {

            if isCaching == false {
                if isHelpPresenting == false {
                    media.playAfterHelpClosed()
                }
                else {
                    media.playAfterCaching()
                }
            }
    }

    fun pause() {
        if isAnnouncementPlaying == false, isSafetyVideoPlaying == false {
            currentMedia.pause()
        }
    }
}

L’exemple ci-dessus est difficile à lire et à maintenir en raison d’une grande variabilité (entropie). Cet exemple est basé sur mon expérience de travail avec la base de code de *de nombreux* projets qui n’utilisaient pas de machine à états.
Chaque case à cocher doit spécifiquement « contrôler » les éléments de l’interface et la logique métier de l’application ; le développeur, en ajoutant une autre case à cocher, doit être capable de jongler avec eux, en vérifiant et revérifiant le tout plusieurs fois avec toutes les options possibles.
En remplaçant dans la formule « 2 ^ nombre de cases à cocher », vous pouvez obtenir 2 ^ 6 = 64 options pour le comportement de l’application pour seulement 6 cases à cocher, toutes ces combinaisons de cases à cocher devront être cochées et gérées manuellement.
Du côté du développeur, l’ajout de nouvelles fonctionnalités avec un tel système ressemble à ceci :
– Nous devons ajouter la possibilité d’afficher la page du navigateur de la compagnie aérienne, et elle devrait être réduite comme pour les films si les membres de l’équipage annoncent quelque chose.
– D’accord, je vais le faire. (Oh putain, je vais devoir ajouter un autre drapeau et revérifier tous les endroits où les drapeaux se croisent, ça fait beaucoup de choses à changer !)

C’est aussi un point faible du système de drapeaux : ; apporter des modifications au comportement de l’application. Il est très difficile d’imaginer comment modifier rapidement et de manière flexible un comportement en fonction des indicateurs, si après avoir modifié un seul indicateur, vous devez tout revérifier. Cette approche du développement entraîne beaucoup de problèmes, une perte de temps et d’argent.

Entrez dans la machine

Si vous regardez attentivement les drapeaux, vous comprendrez qu’en fait nous essayons de traiter des processus spécifiques se produisant dans le monde réel. Nous les listons : mode normal, affichage d’une vidéo de sécurité, diffusion d’un message du capitaine ou des membres d’équipage. Pour chaque processus, un ensemble de règles est connu qui modifie le comportement de l’application.
Selon les règles du modèle de machine à états (machine à états), nous listerons tous les processus en tant qu’états dans l’énumération, ajouterons un concept tel qu’un état au code du joueur, implémenterons un comportement basé sur l’état en supprimant les combinaisons sur les drapeaux. Ainsi, nous réduirons les options de test exactement au nombre d’états.

Pseudocode :

enum MediaPlayerState {
	mediaPlaying,
	mediaCaching,
	crewSpeaking,
	safetyVideoPlaying,
	presentingHelp
}

class MediaPlayer {
	fun play(media: Media) {
		media.play()
	}

	func pause() {
		media.pause()
	}
}

class MediaPlayerStateMachine {
	public state: MediaPlayerState
	public mediaPlayer: MediaPlayer
	public currentMedia: Media

	//.. init (mediaPlayer) etc

	public fun set(state: MediaPlayerState) {
		switch state {
			case mediaPlaying:
				mediaPlayer.play(currentMedia)
			case mediaCaching, crewSpeaking,
			safetyVideoPlaying, presentingHelp:
				mediaPlayer.pause()
		}
	}
}

L’énorme différence entre un système de drapeaux et une machine à états réside dans l’entonnoir de commutation d’état logique dans la méthode set(state: ..), il vous permet de traduire la compréhension humaine de l’état en code de programme, sans avoir à jouer à la logique. jeux de conversion de drapeaux en états avec prise en charge ultérieure du code.

État du modèle

Ensuite, je montrerai la différence entre l’implémentation naïve de la machine à états et le modèle d’état. Imaginons que nous devions ajouter 10 états ; en conséquence, la classe des machines à états atteindrait la taille d’un objet divin, ce qui serait difficile et coûteux à maintenir. Bien sûr, cette implémentation est meilleure que l’implémentation du flag (avec le système de flag, le développeur se tirera une balle en premier, et sinon, voyant 2 ^ 10 = 1024 variations, QA se pendra, mais si les deux *ne le font pas remarquerez* la complexité de la tâche, alors l’utilisateur dont l’application est simple remarquera qu’il refusera de travailler avec une certaine combinaison de drapeaux)
S’il y a un grand nombre d’états, il est nécessaire d’utiliser le modèle State.
Ajoutons un ensemble de règles au protocole d’État :

protocol State {
    func playMedia(media: Media, context: MediaPlayerContext)
    func shouldCacheMedia(context: MediaPlayerContext)
    func crewSpeaking(context: MediaPlayerContext)
    func safetyVideoPlaying(context:MediaPlayerContext)
    func presentHelp(context: MediaPlayerContext)
}

Déplaçons l’implémentation de l’ensemble de règles dans des états distincts, par exemple, le code d’un état :

class CrewSpeakingState: State {
	func playMedia(context: MediaPlayerContext) {
		showWarning(“Can’ t play media - listen to announce!”)
	}

	func mediaCaching(context: MediaPlayerContext) {
		showActivityIndicator()
	}

	func crewSpeaking(context: MediaPlayerContext) {
		set(volume: 100)
	}

	func safetyVideoPlaying(context: MediaPlayerContext) {
		set(volume: 100)
	}

	func presentHelp(context: MediaPlayerContext) {
		showWarning(“Can’ t present help - listen to announce!”)
	}
}

Ensuite, créons un contexte avec lequel chaque état fonctionnera et intégrons la machine à états :

final class MediaPlayerContext {
	private
	var state: State

	public fun set(state: State) {
		self.state = state
	}

	public fun play(media: Media) {
		state.play(media: media, context: this)
	}

	…
	остальные возможные события
}

Les composants d’application fonctionnent avec le contexte via des méthodes publiques ; les objets d’état décident eux-mêmes de l’état vers lequel effectuer la transition à l’aide de la machine à états à l’intérieur du contexte.
Ainsi, nous avons implémenté la décomposition God Object, maintenir un état changeant sera beaucoup plus facile, grâce au compilateur qui suit les modifications du protocole, réduisant la complexité de compréhension des états en raison de la réduction du nombre de lignes de code, et se concentrant sur résoudre un problème d’État spécifique. Vous pouvez également désormais partager le travail en équipe, en confiant la mise en œuvre d’un état spécifique aux membres de l’équipe, sans vous soucier de la nécessité de « résoudre » les conflits, ce qui se produit lorsque vous travaillez avec une grande classe de machines à états.

Sources

https://refactoring.guru/ru/design-patterns/state

Animation squelettique (Partie 1 – shader)

Dans cet article, je décrirai ma compréhension de l’animation squelettique, qui est utilisée dans tous les moteurs 3D modernes pour animer des personnages, des environnements de jeu, etc.
Je vais commencer la description par la partie la plus tangible : vertex shader, car l’ensemble du chemin de calcul, aussi complexe soit-il, se termine par le transfert des données préparées pour l’affichage vers le vertex shader.

L’animation du squelette, après avoir été traitée sur le CPU, passe dans le vertex shader.
Laissez-moi vous rappeler la formule du sommet sans animation squelettique :
gl_Position = projectionMatrix * viewMatrix * modelMatrix * sommet;
Pour ceux qui ne comprennent pas comment est née cette formule, vous pouvez lire mon article décrivant le principe du travail avec des matrices pour afficher du contenu 3D dans le contexte d’OpenGL.
Pour le reste – formule pour implémenter l’animation squelettique :
” vec4 animéVertex = bone0matrix * sommet * bone0weight +”
“bone1matrix * sommet * bone1weight +”
“bone2matrix * sommet * bone2weight +”
“bone3matrix * sommet * bone3weight;\n”
” gl_Position = projectionMatrix * viewMatrix * modelMatrix * animationVertex;\n”

C’est-à-dire que nous multiplions la matrice de transformation osseuse finale par le sommet et par le poids de cette matrice par rapport au sommet. Chaque sommet peut être animé par 4 os, la force de l’impact est régulée par le paramètre poids de l’os, la somme des impacts doit être égale à un.
Que faire si moins de 4 os affectent le sommet ? Nous devons diviser le poids entre eux et rendre l’impact du reste égal à zéro.
Mathématiquement, multiplier un poids par une matrice est appelé « multiplication matricielle-scalaire ». La multiplication par un scalaire vous permet de résumer l’effet des matrices sur le sommet résultant.

Les matrices de transformation osseuse elles-mêmes sont transmises sous forme de tableau. De plus, le tableau contient des matrices pour l’ensemble du modèle dans son ensemble, et non pour chaque maillage séparément.

Mais pour chaque sommet les informations suivantes sont transmises séparément :
– Index de la matrice qui affecte le sommet
– Poids de la matrice qui affecte le sommet
Plus d’un os est transmis, généralement l’effet de 4 os sur le sommet est utilisé.
Aussi, la somme des poids des 4 dés doit toujours être égale à un.
Voyons ensuite à quoi cela ressemble dans le shader.
Tableau matriciel :
“uniform mat4 bonesMatrices[kMaxBones];”

Informations sur l’effet de 4 os sur chaque sommet :
“attribut vec2 bone0info;”
“attribut vec2 bone1info;”
“attribut vec2 bone2info;”
“attribut vec2 bone3info;”

vec2 – dans la coordonnée X, nous stockons l’index de l’os (et le convertissons en int dans le shader), dans la coordonnée Y, nous stockons le poids de l’impact de l’os sur le sommet. Pourquoi devez-vous transmettre ces données dans un vecteur bidimensionnel ? Parce que GLSL ne prend pas en charge la transmission de structures lisibles en C avec des champs valides au shader.

Ci-dessous, je vais donner un exemple d’obtention des informations nécessaires à partir d’un vecteur pour une substitution ultérieure dans la formule animationVertex :

“int bone0Index = int(bone0info.x);”
“float bone0weight = bone0info.y;”
“mat4 bone0matrix = bonesMatrices[bone0Index];”

“int bone1Index = int(bone1info.x);”
“float bone1weight = bone1info.y;”
“mat4 bone1matrix = bonesMatrices[bone1Index];”

“int bone2Index = int(bone2info.x);”
“float bone2weight = bone2info.y;”
“mat4 bone2matrix = bonesMatrices[bone2Index];”

“int bone3Index = int(bone3info.x);”
“float bone3weight = bone3info.y;”
“mat4 bone3matrix = bonesMatrices[bone3Index];”

Maintenant, la structure des sommets renseignée sur le processeur devrait ressembler à ceci :
x, y, z, u, v, bone0index, bone0weight, bone1index, bone1weight, bone2index, bone2weight, bone3index, bone3weight

La structure du vertex buffer est remplie une fois lors du chargement du modèle, mais les matrices de transformation sont transférées du CPU vers le shader à chaque image de rendu.

Dans les parties restantes, je décrirai le principe de calcul de l’animation sur le CPU, avant de la transférer vers le vertex shader, je décrirai l’arbre des nœuds osseux, en parcourant la hiérarchie animation-modèle-nœuds-mesh, la matrice interpolation.

Sources

http://ogldev.atspace.co. fr/www/tutorial38/tutorial38.html

Code source

https://gitlab.com/demensdeum/skeletal-animation