ハッシュテーブル

ハッシュ テーブルを使用すると、挿入、削除、検索操作の平均パフォーマンス O(1) の連想配列 (ディクショナリ) データ構造を実装できます。

以下は、nodeJS でのハッシュ マップの最も単純な実装の例です。

どのように機能するのでしょうか?手に注意してください:

  • ハッシュ マップ内には配列があります
  • 配列要素内には、リンクされたリストの最初のノードへのポインタがあります
  • メモリはポインタの配列(たとえば、65535 要素)に割り当てられます
  • ハッシュ関数を実装しており、辞書キーが入力であり、出力では何でもできますが、最終的には配列要素のインデックスを返します

録音の仕組み:

  • 入り口にはキーペアがあります –値
  • ハッシュ関数はキーごとにインデックスを返します
  • インデックスを使用して配列からリンク リスト ノードを取得する
  • キーと一致するかどうかを確認します
  • 一致する場合は、値を置き換えます
  • 一致しない場合は、必要なキーを持つノードが見つかるまで、次のノードに進みます。
  • それでもノードが見つからない場合は、リンク リストの最後にノードを作成します

キーによる検索の仕組み:

  • 入り口にはキーペアがあります –値
  • ハッシュ関数はキーごとにインデックスを返します
  • インデックスを使用して配列からリンク リスト ノードを取得する
  • キーと一致するかどうかを確認します
  • 一致する場合は値を返します
  • 一致しない場合は、必要なキーを持つノードが見つかるまで、次のノードに進みます。

なぜ配列内にリンクされたリストが必要なのでしょうか?ハッシュ関数の計算時に衝突が発生する可能性があるため。この場合、いくつかの異なるキーと値のペアが配列内の同じインデックスに配置されます。この場合、必要なキーを見つけるためにリンク リストが走査されます。

ソース

https://ru.wikipedia.org/wiki/ハッシュ テーブル
https://www.youtube.com/watch?v=wg8hZxMRwcw

ソースコード

https://gitlab.com/demensdeum/data Structures

Android C++ でのリソースの操作

ndk を介して Android のリソースを操作するには – C++ にはいくつかのオプションがあります:

<オル>

  • AssetManager を使用して APK ファイルからリソースにアクセスする
  • インターネットからリソースをダウンロードし、アプリケーション ディレクトリに解凍し、標準の C++ メソッドを使用して使用します
  • 複合メソッド – AssetManager 経由で APK 内のリソースを含むアーカイブにアクセスし、それらをアプリケーション ディレクトリに解凍して、標準の C++ メソッドを使用して使用します
  • 次に、Flame Steel Engine ゲーム エンジンで使用される結合アクセス方法について説明します。
    SDL を使用すると、apk からリソースへのアクセスを簡素化できます。ライブラリは AssetManager への呼び出しをラップし、stdio (fopen、fread、fclose など) と同様のインターフェイスを提供します。

    SDL_RWops *io = SDL_RWFromFile("files.fschest", "r");
    
    

    APK からバッファにアーカイブをダウンロードした後、現在の作業ディレクトリをアプリケーション ディレクトリに変更する必要があります。追加のアクセス許可を取得せずにアプリケーションで使用できるようになります。これを行うには、SDL ラッパーを使用します。

    chdir(SDL_AndroidGetInternalStoragePath());
    
    

    次に、fopen、fwrite、fclose を使用して、バッファから現在の作業ディレクトリにアーカイブを書き込みます。アーカイブが C++ にアクセスできるディレクトリに配置されたら、解凍します。 ZIP アーカイブは、2 つのライブラリを組み合わせて使用​​して解凍できます。 minizip と zlib、最初のものはアーカイブの構造を操作でき、2 つ目はデータを解凍します。
    より制御しやすく移植を容易にするために、FSChest (Flame Steel Chest) と呼ばれる独自のゼロ圧縮アーカイブ形式を実装しました。この形式は、ファイルを含むディレクトリのアーカイブと解凍をサポートします。フォルダー階層はサポートされていないため、ファイルのみを操作できます。
    FSChest ライブラリのヘッダーを接続し、アーカイブを解凍します。

    #include "fschest.h" 
    FSCHEST_extractChestToDirectory(archivePath, SDL_AndroidGetInternalStoragePath()); 
    
    

    解凍後、C/C++ インターフェイスはアーカイブのファイルにアクセスできるようになります。したがって、エンジン内のファイルに関するすべての作業を書き直す必要はなく、起動段階でファイルの解凍を追加するだけで済みました。

    ソース

    https://developer.android.com/ndk/参照/グループ/アセット

    ソースコード

    https://gitlab.com/demensdeum/space-ジャガー アクション RPG
    https://gitlab.com/demensdeum/fschest

    スタックマシンとRPN

    単純なバイトコード インタープリターを実装する必要があるとします。このタスクを実装するにはどのようなアプローチを選択すればよいでしょうか?

    データ構造 スタックは、単純なバイトコード マシンを実装する機能を提供します。スタック マシンの機能と実装については、欧米および国内のインターネット上の多くの記事で説明されています。Java 仮想マシンはスタック マシンの一例であることだけを述べておきます。

    マシンの動作原理は単純で、データと操作コード (オペコード) を含むプログラムが入力に供給され、必要な操作はスタックによる操作を使用して実装されます。私のスタック マシンのバイトコード プログラムの例を見てみましょう。

    пMVkcatS olleHП
     
    

    出力では、文字列「Hello StackVM」を受け取ります。スタック マシンはプログラムを左から右に読み取り、オペコードがシンボル – に現れるとデータを 1 文字ずつスタックにロードします。スタックを使用してコマンドを実装します。

    nodejs でのスタック マシンの実装例:

    逆ポーランド記法 (RPN)

    スタック マシンは、逆ポーランド記法 (後置記法) を使用するため、計算機の実装にも簡単に使用できます。
    通常の中置記法の例:
    2*2+3*4

    RPN に変換します:
    22*34*+

    接尾辞レコードをカウントするには、スタック マシンを使用します。
    2–スタックの先頭(スタック: 2)へ
    2–スタックの先頭(スタック: 2,2)
    *–スタックの先頭を2回取得し、その結果を乗算してスタックの先頭(スタック: 4)に送信します
    3–スタックの先頭(スタック: 4、3)へ
    4–スタックの一番上(スタック: 4、3、4)へ
    *–スタックの先頭を 2 回取得し、その結果を乗算してスタックの先頭 (スタック: 4、12) に送信します。
    +–スタックの先頭を 2 回取得し、結果を追加して、スタックの先頭 (スタック: 16) に送信します。

    ご覧のとおり –操作 16 の結果はスタックに残ります。たとえば、スタック印刷オペコードを実装することで印刷できます。
    p22*34*+P

    P–スタック印刷開始オペコード、p –スタックの印刷を終了し、レンダリングのために最終行を送信するためのオペコード。
    算術演算を中置演算から後置演算に変換するには、「Sorting Yard」と呼ばれるエドガー ダイクストラのアルゴリズムが使用されます。実装の例は上記、または以下の Nodejs マシン スタック プロジェクトのリポジトリで見ることができます。

    ソース

    https:/ /tech.badoo.com/ru/article/579/interpretatory-bajt-kodov-svoimi-rukami/
    https://ru.wikipedia.org/wiki/Обратная_польская_запись

    ソースコード

    https://gitlab.com/demensdeum/stackvm/< /p>

    スケルタルアニメーション (パート 2 – ノード階層、補間)

    引き続き、Flame Steel Engine に実装されているスケルトン アニメーション アルゴリズムについて説明します。

    このアルゴリズムは私が実装したアルゴリズムの中で最も複雑であるため、開発プロセスに関するメモにエラーが表示される場合があります。このアルゴリズムに関する前回の記事では、ボーンの配列がモデル全体ではなく、メッシュごとに個別にシェーダーに転送されるという間違いを犯しました。

    ノード階層

    アルゴリズムが正しく動作するには、モデルにボーンとボーン間の接続 (グラフ) が含まれている必要があります。 2 つのアニメーションが同時に再生される状況を想像してみましょう。ジャンプして右手を上げる。ジャンプ アニメーションはモデルを Y 軸に沿って持ち上げる必要がありますが、腕を上げるアニメーションはこれを考慮して、モデルがジャンプするときにモデルと一緒に上昇する必要があります。そうしないと、腕は自動的に所定の位置に留まります。

    この場合のノードの接続について説明します –体には手が含まれています。アルゴリズムを作成するとき、骨グラフが読み取られ、すべてのアニメーションが正しい接続で考慮されます。モデルのメモリ内では、グラフはモデルのボーンの接続性を反映するためだけに、すべてのアニメーションとは別に保存されます。

    CPU での補間

    前回の記事では、スケルトン アニメーションのレンダリングの原理について説明しました。 「変換マトリックスは、レンダリング フレームごとに CPU からシェーダーに転送されます。」

    各レンダリング フレームは CPU で処理され、メッシュ ボーンごとに、エンジンは位置補間、回転、ズームを使用して最終的な変換行列を受け取ります。最終的なボーン マトリックスの補間中、すべてのアクティブなノード アニメーションに対してノード ツリーを通じてパスが作成され、最終的なマトリックスが親のマトリックスと乗算されて、レンダリングのために頂点シェーダーに送信されます。

    ベクトルは位置補間と拡大に使用され、クォータニオンは回転に使用されます。オイラー角とは異なり、補間 (SLERP) が非常に簡単で、変換行列として表すことも非常に簡単です。

    実装を簡素化する方法

    頂点シェーダーのデバッグを容易にするために、FSGLOGLNEWAGERENDERER_CPU_BASED_VERTEX_MODS_ENABLED マクロを使用して、CPU 上に頂点シェーダーのシミュレーションを追加しました。ビデオ カード メーカーである NVIDIA は、シェーダー コードをデバッグするためのユーティリティ Nsight を提供しています。これにより、複雑な頂点/ピクセル シェーダー アルゴリズムの開発も簡素化できる可能性がありますが、CPU でのシミュレーションだけでは十分な機能をテストできませんでした。

    次の記事では、複数のアニメーションの混合について説明し、残りのギャップを埋める予定です。

    ソース

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

    C++ での JavaScript スクリプトのサポートの追加

    この投稿では、Tiny-JS ライブラリを使用して C++ アプリケーションに JavaScript スクリプトのサポートを追加する方法について説明します。

    Tiny-JS は、C++ に埋め込むためのライブラリであり、バインディング (スクリプトから C++ コードを呼び出す機能) のサポートとともに JavaScript コードの実行を提供します。

    最初は、人気のあるライブラリである ChaiScript、Duktape、または connect Lua を使用したいと考えていましたが、依存関係や、さまざまなプラットフォームへの移植が困難になる可能性があるため、シンプルで最小限だが強力な MIT JS ライブラリを見つけることにしました。 JS はこれらの基準を満たしています。このライブラリの唯一の欠点は、作成者によるサポート/開発がないことですが、コードは非常にシンプルなので、必要に応じてサポートを引き継ぐことができます。

    リポジトリから Tiny-JS をダウンロードします。
    https://github.com/gfwilliams/tiny-js

    次に、スクリプトを担当するコードに Tiny-JS ヘッダーを追加します。

    #include "tiny-js/TinyJS.h"
    #include "tiny-js/TinyJS_Functions.h"
    
    

    TinyJS .cpp ファイルをビルド ステージに追加すると、スクリプトの読み込みと実行の作成を開始できます。

    ライブラリの使用例はリポジトリで入手できます。
    https://github.com/gfwilliams/tiny-js/blob/master/Script.cpp
    https://github.com/gfwilliams/tiny-js/blob/wiki/CodeExamples.md

    ハンドラー クラスの実装例は、SpaceJaguar プロジェクトにあります。
    https://gitlab.com/demensdeum/space-jaguar-action-rpg/-/blob/master/project/src/Controllers/SpaceJaguarScriptController/SpaceJaguarScriptController.h
    https://gitlab.com/demensdeum/space-jaguar-action-rpg/-/blob/master/project/src/Controllers/SpaceJaguarScriptController/SpaceJaguarScriptController.cpp

    アプリケーションに追加されたゲーム スクリプトの例:
    https://gitlab.com/demensdeum/space-jaguar-action-rpg/-/blob/master/project/resources/com.demensdeum.spacejaguaractionrpg.scripts.sceneController.js

    ソース

    https://github.com/gfwilliams/tiny-js
    https://github.com/dbohdan/embedded-scripting-languages
    https://github.com/AlexKotik/embeddable-scripting-languages

    Linux 上で iOS 用の C++ SDL アプリケーションを構築する

    この投稿では、Linux 上で iOS 用の C++ SDL アプリケーションを構築し、有料の Apple Developer サブスクリプションなしで ipa アーカイブに署名し、ジェイルブレイクなしで macOS を使用してクリーンなデバイス (iPad) にアプリケーションをインストールする手順について説明します。< /p>

    まず、Linux 用のビルド ツールチェーンをインストールしましょう。
    https://github.com/tpoechtrager/cctools-port

    ツールチェーンをリポジトリからダウンロードし、Godot Engine Web サイトの指示に従ってインストールを完了する必要があります。
    https://docs.godotengine.org/ru/latest/development/compiling/cross-compiling_for_ios_on_linux.html

    現時点では、Xcode dmg をダウンロードし、そこから SDK をコピーして cctools-port をビルドする必要があります。この段階は macOS で簡単に完了でき、インストールされた Xcode から必要な SDK ファイルをコピーするだけです。アセンブリが成功すると、ターミナルにはクロスコンパイラー ツールチェーンへのパスが含まれます。

    次に、iOS 用の SDL アプリケーションの構築を開始できます。 cmake を開いて、C++ コードをビルドするために必要な変更を追加しましょう。

    SET(CMAKE_SYSTEM_NAME Darwin)
    SET(CMAKE_C_COMPILER arm-apple-darwin11-clang)
    SET(CMAKE_CXX_COMPILER arm-apple-darwin11-clang++)
    SET(CMAKE_LINKER arm-apple-darwin11-ld)
    
    

    これで、cmake と make を使用してコンパイルできるようになりますが、$PATH をクロスコンパイラー ツールチェーンに追加することを忘れないでください。

    
    PATH=$PATH:~/Sources/cctools-port/usage_examples/ios_toolchain/target/bin
    
    

    フレームワークや SDL と正しくリンクするために、それらを cmake に記述します。たとえば、ゲーム Space Jaguar の依存関係です。

    
    target_link_libraries(
    ${FSEGT_PROJECT_NAME}
    ${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libclang_rt.ios.a
    ${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libSDL2.a
    ${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libSDL2_mixer.a
    ${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libSDL2_image.a
    "${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreServices.framework"
    "${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/ImageIO.framework"
    "${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/Metal.framework"
    "${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/AVFoundation.framework"
    "${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/GameController.framework"
    "${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreMotion.framework"
    "${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreGraphics.framework"
    "${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/AudioToolbox.framework"
    "${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreAudio.framework"
    "${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/QuartzCore.framework"
    "${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/OpenGLES.framework"
    "${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/UIKit.framework"
    "${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/Foundation.framework"
    )
    
    

    私の場合、SDL、SDL_Image、SDL_mixer ライブラリは、静的リンクのために事前に macOS 上の Xcode でコンパイルされています。 Xcode からコピーされたフレームワーク。 libclang_rt.ios.a ライブラリも追加されました。これには、iOS 固有のランタイム呼び出し (isOSVersionAtLeast など) が含まれます。 Android と同様に、OpenGL ES を操作して、モバイル バージョンでサポートされていない機能を無効にするためのマクロが含まれています。

    ビルドの問題をすべて解決したら、arm 用にアセンブルされたバイナリを取得する必要があります。次に、ジェイルブレイクなしでデバイス上でアセンブルされたバイナリを実行することを検討してみましょう。

    macOS では、開発者プログラムの料金を支払わずに、Xcode をインストールし、Apple ポータルに登録します。 Xcode でアカウントを追加します ->設定 ->アカウント、空のアプリケーションを作成し、実際のデバイス上に構築します。組み立て中に、デバイスは無料の開発者アカウントに追加されます。アセンブリと起動後、アーカイブを構築する必要があります。これを行うには、[汎用 iOS デバイスと製品] を選択します。アーカイブ。アーカイブが構築されたら、そこからembedded.mobileprovisionファイルとPkgInfoファイルを抽出します。デバイスへのビルド ログから、正しい署名キーを含むコードデザイン行、拡張子 app.xcent を持つ資格ファイルへのパスを見つけてコピーします。

    アーカイブから .app フォルダーをコピーし、アーカイブ内のバイナリを Linux のクロスコンパイラーでコンパイルされたバイナリ (SpaceJaguar.app/SpaceJaguar など) に置き換えてから、必要なリソースを .app に追加し、アーカイブからの .app 内の PkgInfo およびembedded.mobileprovision ファイルの整合性を確認するには、必要に応じて再度コピーします。 codesign コマンド – を使用して .app に再署名します。 codedesign には、署名用の入力キー、資格ファイルへのパス (.plist 拡張子で名前変更可能) が必要です。

    再署名した後、Payload フォルダーを作成し、.app 拡張子の付いたフォルダーをそこに移動し、ルートに Payload を含む zip アーカイブを作成し、.ipa 拡張子を付けてアーカイブの名前を変更します。その後、Xcode でデバイスのリストを開き、新しい ipa をデバイスのアプリケーションのリストにドラッグ アンド ドロップします。この方法では、Apple Configurator 2 によるインストールは機能しません。再署名が正しく行われると、新しいバイナリを含むアプリケーションが 7 日間の証明書とともに iOS デバイス (iPad など) にインストールされます。テスト期間にはこれで十分です。

    ソース

    https://github.com/tpoechtrager/cctools-port
    https://docs.godotengine.org/ru/latest/development/compiling/cross-compiling_for_ios_on_linux.html
    https://jonnyzzz.com/blog/2018/06/13/link-error-3/
    https://stackoverflow.com/questions/6896029/re-sign-ipa-iphone
    https://developer.apple.com/library/archive/documentation/Security/Conceptual/CodeSigningGuide/Procedures/Procedures.html

    ゲームのビジョン #4

    Games Vision ゲームに関する非常に一貫性のないコラムの第 4 版。

    World Of Horror (クロスプラットフォーム、パンスタズ) – ローグライク早期アクセス ゲームスタイル的には、え、何? RPG 要素を備えたテキスト ホラー アドベンチャー? 80 年代のゲームを彷彿とさせるグラフィックで、バリエーションのある 1 ビットまたは 2 ビットのパレットから選択できます。

    最初はコントロールが奇妙に見えますが、時間が経つにつれて慣れてきます。それがローグライクの理由であり、あらゆる面で驚きと独創性を備えているからです。素晴らしいチップチューン音楽、80年代後半の日本の美学、伊藤潤二の作品にインスピレーションを得たビジュアル、ラヴクラフト風の奇妙な物語、ほぼ無限のリプレイ性
    他に何が必要ですか?
    評価: 9/10

    永遠の城 [リマスター] (PC、ダニエレ)ヴィシナンツォ、ジュリオ ペローネ、レナード メンキアーリ) – Another World スタイルのモダンなゲーム、Flashback。パレットは特別に CGA カラーに縮小されています。このゲームの説明は、その作成の伝説から始める必要があります。1987 年頃、Eternal Castle の開発者の子供たちの 1 人がこのゲームを見て、一生そのことを覚えていました。その結果、ゲームはリリースされませんでした。ソースコードは2019年に発見され復元され、改良版がリリースされました。ただし、Steam の説明には、これは 1987 年のベストセラーのリマスターであるという情報が含まれていますが、その年にはその名前のゲームはリリースされていませんでした。何が真実で何が嘘であるかはあなた次第です。

    グラフィックスとゲームプレイは明らかに古き良き時代を懐かしむ人向けに作られており、ゲームがフリーズしたように見える瞬間がよくありますが、実際には移動ボタンやアクション ボタンを押すだけで何が起こるかを確認できます。画面上で起こっていること。このギミックは、古いゲームではよく使われていたぎこちなさやコントロールの喪失感を生み出しますが、最近のゲームでは完全に放棄されています。
    評価: 8/10

    死と死税金 (PC、プレースホルダー ゲームワークス) –裁判官と死刑執行人として一人の人間として働くことを夢見たことがありますか?長い黒いローブ、金属の三つ編み、指の関節を鳴らすのは好きですか? 「避けて通れないのは死と税金だけ」というあなたにぴったりのゲーム
    です。
    これは死の天使のユニークなシミュレーターです。誰が生き、誰が死ぬかを選択する必要があります。殺すか命を与えるかに加えて、スマートフォンでニュースフィードを読んで、自分の選択が地球の世界にどのような影響を与えるかを知ることができます。また、フェイス(運命)という名前の直属の上司とコミュニケーションを取り、アイテムやテーブル用のあらゆる種類の器具を購入する必要があります。たとえば、私は自分自身に残忍なサボテンを購入しました。鏡に向かって話すのを忘れないでください。とても楽しいです。マイナス点の中でも、ゲーム内で数日経つと、ゲームが少し単調になってしまうという、全体的な親密さは注目に値します。評価: 8/10

    Windows 10で遅いHDDを修正する

    このメモは、諦めていないすべてのハード ドライブ ユーザーに捧げます。


    Original (Mae Mu)

    デュアル HDD (Windows 10) と SSD (Ubuntu) を搭載した HP Pavilion ラップトップを 1 年半使用した後、アプリケーションのロード時間が非常に長いこと、インターフェイスが全般的に応答しなくなっていること、最も単純な操作でフリーズすることに気づき始めました。 Windows 10 では、問題は最小限に抑えられ、ラップトップを再び使用できるようになりました。次に、問題を解決するために私が行った手順について説明します。

    診断

    調査を開始するには、あらゆる種類のデマを排除する必要があります。まず、ハードドライブ障害の主な原因を特定しましょう。ハードドライブを使用するときに問題が発生する可能性がありますか?問題は、電子機器の物理レベルおよび論理的なソフトウェア データ レベルで発生する可能性があります。
    電子機器の問題には、コンピュータやラップトップの電源が機能しない、ラップトップのバッテリの問題などが含まれます。ハードドライブのコンポーネントの磨耗、ドライブの内部コンポーネントの回路やチップの問題、ファームウェアのエラー、ドライブの衝撃や落下による影響、または動作に影響を与える他のデバイスの同様の問題。
    ハードドライブの重大な摩耗は、ドライブのそれ以上の操作が不可能になるほどの数の不良セクタ (不良ブロック) が発生した瞬間であると考えられます。これらのブロックはハード ドライブのファームウェアによってブロックされ、データは自動的に他のセクターに転送され、特定の重大な瞬間までディスクの動作に影響を与えることはありません。
    プログラム ロジックの問題には、アプリケーションの誤った操作によるファイル システムのエラー、ユーザーのアクション (熱いときにデバイスの電源を切る、アプリケーションを正しく停止せずに録画プロセスを完了する)、ドライバー、オペレーティング システム サービスのエラーが含まれます。
    特殊な電子機器診断ツールがなければ、ソフトウェア レベルの正確性を確認することしかできません。その過程で電子機器の問題が発見される可能性がありますが、通常はブロック修復方法 (コンポーネント/チップの交換) によって解決されます。次に、診断ユーティリティを使用したソフトウェアの診断方法を検討します。すべてのユーティリティはシステム上で最優先で起動する必要があることに注意してください。他のアプリケーションがパフォーマンス測定を妨害し、ディスクの読み取り/書き込みをブロックする可能性があり、その結果、不正確な診断結果が得られる可能性があります。

    スマート

    S.M.A.R.T. ストレージ デバイス ステータス監視システム – HDD、SDD、eMMC など。デバイスの摩耗を評価し、不良ブロックの数を表示し、データに基づいてさらなるアクションを実行できます。 SMART は、ディスクを操作するためのさまざまなアプリケーションで表示できます。私は、メーカーが提供するユーティリティを使用することを好みます。 Seagate ハード ドライブの場合は、SeaTools ユーティリティを使用しました。ステータスは GOOD と表示されました。つまり、ディスク ファームウェアはすべてが正常であると判断しています。

    メーカーのユーティリティ

    ディスク製造元のユーティリティは、その動作を検証するためのテストを提供しています。 SeaTools にはいくつかの種類のテストがあり、それらをすべて使用して問題の場所を特定できます。簡単なテストでは問題が見つからない可能性があるため、長いテストを推奨します。私の場合、Long Test のみでエラーが見つかりました。

    スローライド

    読み取りの正確性を確認し、遅いブロックやデッドブロックを見つけるために、アプリケーション を作成しました。スローライドは、非常に単純な原理で動作します。指定されたユーザー設定を使用してブロック デバイス記述子を開き、デバイス全体のデータを読み取り、時間測定、低速ブロックの出力を行います。この場合、プログラムは最初のエラーで停止します。単純な方法ではディスク データを読み取ることができないため、より深刻なデータ削除ユーティリティに進む必要があります。
    私の場合、ディスク全体の読み取りは正しく実行されましたが、速度はわずかに低下しました。ディスクの一部の領域では、1 秒間に 90MB/秒 (5400rpm)。このことから、ソフトウェアの問題に対処していると結論付けることができます。

    音響分析

    この方法はソフトウェア診断方法には適用されませんが、問題を解決することは非常に重要です。たとえば、電源が部分的に動作している場合、ハードドライブがフリーズ/フリーズし、カチッという音が大きくなることがあります
    。私の場合、Windows 10 でディスクを操作しているときに、HDD 所有者なら誰でもよく知っている、 オペレーティング システムで何かを実行しようとすると、ディスク ヘッドが往復する大きなパチパチという音が聞こえますが、その音はほぼ一定であり、断片化が多すぎるのではないかと思いました。ディスク、バックグラウンド サービスによるディスクの過負荷。

    修正中

    ソフトウェア診断中に電子機器の問題は検出されず、ディスク全体のブロックごとの読み取りは正常に完了しましたが、SeaTools はロング テスト中にエラーを示しました。

    メーカーのユーティリティ

    診断に加えて、ディスク製造元のソフトウェアはエラー修正手順を提供します。 SeaTools では、[すべて修復] ボタンがこれを担当します。データ損失の可能性への同意を確認した後、修正プロセスが開始されます。この修正は私の場合に役に立ちましたか?いいえ、ディスクは引き続き大音量でゆっくりと動作しましたが、ロング テストではエラーが表示されなくなりました。

    CHKDSK

    CHKSDK は、Windows ファイル システムのソフトウェア エラーをトラブルシューティングするための Microsoft ユーティリティです。時間の経過とともに、このようなエラーはディスク上に蓄積され、データの読み取り/書き込みがまったくできなくなるなど、作業に大きな支障をきたす可能性があります。このユーティリティの使用手順は Microsoft Web サイトで見つけることができますが、エラーを修正するには可能な限りすべてのフラグを使用することをお勧めします (この記事の執筆時点では、これは /r /b /f です)。 Windows ターミナル (cmd) を介して管理者権限でスキャンを実行する必要があります。システム パーティションの場合、スキャンはシステム起動時に実行され、非常に長い時間がかかる場合があります。私の場合は 12 時間かかりました。
    この修正は私の場合に役に立ちましたか?いいえ。

    ディスクのデフラグ

    ディスク上のデータはブロック単位で処理され、大きなファイルは通常、複数のブロック/フラグメントに書き込まれます。時間が経つにつれて、削除されたファイルの多くは、近くにない空のブロックを作成します。そのため、ファイルを書き込むときに、これらの空いたブロックが埋められ、ディスク ヘッドが物理的に長距離を移動する必要があります。この問題は断片化と呼ばれ、ハード ドライブ ユーザーのみが経験します。数回の修正時点で、ハードドライブの断片化は 41% でした。視覚的には次のように見えました。

    つまり、すべてが悪いということです。デフラッガー ユーティリティまたは組み込みのデフラグ ツールを使用して、断片化を確認し、デフラグすることができます。 「ドライブの最適化」サービスを有効にすることもできます。 Windows 10 では、コントロール パネルでデフラグのスケジュールを設定します。 デフラグが必要なのは HDD ドライブのみです。SSD ドライブに対してデフラグを有効にすることはお勧めできません。これにより、ディスクの摩耗が加速します。このため、バックグラウンドでのデフラグはデフォルトで無効になっているようです。

    代替のデフラグ オプションも知られています –データを別のディスクに転送し、ディスクをフォーマットし、データをコピーして戻します。この場合、システム動作に適した正しい論理構造を維持しながら、データは完全に空のセクタに書き込まれます。このオプションには、通常のコピー中に移動できない可能性がある重要なメタデータをリセットする際に問題が伴います。

    サービスを無効にする

    Mark Russinovich のユーティリティの使用 プロセス モニター IO 書き込み/読み取り列を有効にするだけで、ハード ドライブにロードするプロセスをその作業とともに追跡できます。このコラムを調査した後、コントロール パネルのサービス パネルから、新しい名前 SysMain の Superfetch プログラム用のよく知られたバックグラウンド アクセラレーション サービスである Xbox Game Bar サービスを無効にしました。 Superfetch は、ユーザーが使用するアプリケーションを常に分析し、RAM にキャッシュすることでアプリケーションの起動を高速化する必要があります。これにより、ディスク全体がバックグラウンドで読み込まれ、動作できなくなりました。

    ディスクのクリーニング

    また、古いアプリケーションや不要なファイルも削除しました。これにより、適切な断片化のためにセクターが解放され、オペレーティング システムの操作が簡素化され、無駄で重いサービスやプログラムの数が減りました。

    合計

    何が最も役に立ちましたか?ディスクをデフラグするとパフォーマンスに顕著な違いが見られ、Xbox サービスと Superfetch サービスを無効にすることで自然発生的なフリーズが解消されました。 SSD を使用していれば、これらの問題は発生しなかったのでしょうか?断片化による動作の遅さの問題はまったくありません。サービスの問題はいずれにしても修正する必要があり、ソフトウェア エラーはドライブの種類に依存しません。近い将来、SSD への完全な移行を計画していますが、今のところは「パンケーキ万歳、パンケーキ永遠に!」

    リンク

    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/

    ブロックデバイスのSlowrideベンチマーク

    スローライド – /dev/sd* への root アクセスを持つ POSIX 互換オペレーティング システムのブロック デバイスの読み取り速度をチェックするためのユーティリティ。読み取りパフォーマンスを診断するための時間しきい値を使用して、ブロック デバイスの読み取りパフォーマンスをテストできます。
    デバイス全体で 100mb ブロックを読み取り、2 秒のしきい値を超えるブロックを出力するコマンド:

    sudo ./slowride /dev/sda 100 2000
    
    

    ソースコード

    https://gitlab.com/demensdeum/slowride

    スペースジャガー 3DアクションRPG

    長い間新しいプロジェクトを発表していませんでした) 私が取り組み始めている次のプロジェクト –スペース ジャガーと呼ばれる 3D アクション RPG ジャグという名前の屈強な男と、行方不明の父親を探す彼の困難な冒険についての SF 設定の物語。過去のプロジェクト (デスマスク、キューブ アート プロジェクト) の開発を使用した、Flame Steel Engine (またはおそらく他の人気のあるエンジン) の 3D グラフィックス、多くの参考資料を含むコメディ プロット、アーケード バトルとボスが登場します。フルバージョンのリリース日についてはまだ話す準備ができていません。ゲームは分割してリリースする予定です。

    プロジェクト リポジトリ:
    https://gitlab.com/demensdeum/space-jaguar-action-rpg

    C++ FCGI でのバックエンド サーバーの作成

    3D エディタ Cube Art Project のサーバー部分をどのように書いたかについての簡単なメモです。サーバーは Web バージョン ユーザーの作業を保存して表示し、保存ボタンを使用して短い URL を提供する必要があります。当初はバックエンドにSwift/PHP/Ruby/JSなどの最新言語を使いたかったのですが、VPSの特性を見てサーバーをC/C++で書くことにしました。
    まず、サーバーに libfcgi をインストールし、Web サーバー用の fcgi サポート モジュール (Ubuntu と Apache など) をインストールする必要があります。

    sudo apt install libfcgi libapache2-mod-fcgid
    
    

    次に、config でモジュールを構成します。

    FcgidMaxProcessesPerClass –クラスあたりの最大プロセス数ですが、大きな負荷が予想されないため1プロセスに設定しました。
    AddHandler fcgid-script .fcgi – fcgi モジュールを開始するファイル拡張子。
    CGI アプリケーションの起動元となるフォルダーを構成に追加します。

    次に、fcgi サポートを備えた C/C++ でアプリケーションを作成し、アセンブルして、/var/www/html/cgi-bin フォルダーにコピーします。
    コードとビルド スクリプトの例:
    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
    この後、Web サーバーを再起動する必要があります。

    systemctl restart apache2
    
    

    次に、chmod 経由で cgi-bin フォルダーを実行するために必要な権限を入力します。
    この後、CGI プログラムは、Cube Art Project サーバーの例のリンクを使用してブラウザ経由で動作するはずです。
    http://192.243.103.70/cgi-bin/cubeArtProject/cubeArtProjectServer.fcgi
    何かが動作しない場合は、Web サーバーのログを確認するか、デバッガーを使用して実行中のプロセスに接続します。デバッグ プロセスは、通常のクライアント アプリケーションのデバッグ プロセスと異なっていてはなりません。

    ソース

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

    ソースコード

    https://gitlab.com/demensdeum/cube-art -プロジェクトサーバー

    キューブアートプロジェクト

    キューブ アート プロジェクト –立方体 3D エディタ
    ステージ上を移動したり、WSAD + E ボタンを使用して立方体を構築および削除したり、マウス ホイールを回転して立方体の色を変更したりする素晴らしい機会が得られます。現在サポートされている色は 16 色の​​みですが、将来的には多くの改善が予定されています。

    ウェブ版
    https://demensdeum.com/games/CubeArtProjectWEB/

    Windows
    https://demensdeum.com/games/CubeArtProjectReleases/CubeArtProjectWin32.zip

    macOS
    https://demensdeum.com/games/CubeArtProjectReleases/CubeArtProjectMacOS.zip

    Linux (x86-64)
    https://demensdeum.com/games/CubeArtProjectReleases/CubeArtProjectLinux86_64.zip

    アンドロイド
    (コンセプト、USB マウスが必要)
    https://demensdeum.com/games/CubeArtProjectReleases/CubeArtProject.apk

    ソースコード
    https://gitlab.com/demensdeum/cube-art-project-bootstrap
    https://gitlab.com/demensdeum/cube-art-project-server

    テクノロジー: SDLEmscriptenMinGWGlewGLM, Cpp-JSON

    C++ SDL アプリケーションの Android への移植

    この投稿では、3D エディタのプロトタイプを移植した私の経験について説明します キューブ アート プロジェクト
    まず、赤い 3D キューブ カーソルを持つエディタがエミュレータで実行されている結果を見てみましょう。

    組み立てを成功させるには、次のことを行う必要がありました:

    <オル>

  • 最新の Android SDK と NDK をインストールします(NDK バージョンは新しいほど良いです)
  • SDL2 ソース コードをダウンロードし、そこからテンプレートを取得して Android アプリケーションを構築します。
  • SDL イメージ、SDL ミキサーをアセンブリに追加します。
  • ゲーム エンジンとツールキットのライブラリ、それらの依存関係 (GLM、モダン C++ 用の JSON) を追加します
  • アセンブリ ファイルを Gradle に適合させる。
  • Android との互換性のために C++ コードを調整し、影響を受けるプラットフォーム依存コンポーネント(OpenGL ES、グラフィックス コンテキストの初期化)を変更する
  • エミュレータ上でプロジェクトをビルドしてテストします。
  • プロジェクト テンプレート

    ソース SDL、SDL イメージ、SDL ミキサーの読み込み:
    https://www.libsdl.org/download-2.0.php
    docs フォルダーには、Android プロジェクト テンプレートを使用するための詳細な手順が含まれています。 android-project ディレクトリを別のフォルダーにコピーするか、シンボリックリンクを作成するか、SDL フォルダーを android-project/app/jni にコピーします。
    avd フラグを正しい識別子に置き換えて、Sdk:

    ディレクトリから Android エミュレータを起動します。

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

    スクリプトでパスを指定し、プロジェクトをアセンブルします。

    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
    
    

    ファイルからの C コードを含む SDL プロジェクト テンプレートをアセンブルする必要があります

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

    依存関係

    SDL_image、SDL_mixer のソース コードをアーカイブからダウンロードします。
    https://www.libsdl.org/projects/SDL_image/
    https://www.libsdl.org/projects/SDL_mixer/

    プロジェクトの依存関係(共有ライブラリなど)を読み込みます。
    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

    これらすべてを app/jni にアップロードし、各「モジュール」を別のフォルダー (例: app/jni/FSGL) にアップロードします。次に、Application.mk および Android.mk ファイルの動作するジェネレーターを見つけるオプションがあります。私はそれらを見つけられませんでしたが、おそらく CMake に基づく簡単な解決策があるでしょう。リンクをクリックして、Android NDK のアセンブリ ファイル形式について学び始めてください。
    https://developer.android.com/ndk/guides/application_mk
    https://developer.android.com/ndk/guides/android_mk

    NDK のさまざまな APP_STL 実装についてもお読みください。
    https://developer.android.com/ndk/guides/cpp-support.html

    慣れた後、「モジュール」ごとに Android.mk ファイルを作成し、続いて共有ライブラリ 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)
    
    

    経験豊富な CMake ユーザーなら最初の行からこの構成を理解できるでしょう。形式は非常に似ており、Android.mk には GLOB_RECURSIVE がないため、walk 関数を使用してソース ファイルを再帰的に検索する必要があります。

    C コードではなく C++ をビルドするために Application.mk、Android.mk を変更します。

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

    YourSourceHere.c -> YourSourceHere.cpp の名前を変更し、エントリを grep し、アセンブリ内のパスを変更します。

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

    次に、プロジェクトをビルドしてみます。ヘッダーがないことに関するコンパイラーからのエラーが表示された場合は、Android.mk 内のパスが正しいことを確認してください。 「未定義の参照」などのリンカーからのエラーがある場合は、アセンブリ内のソース コード ファイルが正しく指定されていることを確認してください。リストは、Android.mk ファイルで $(info $(FILE_LIST)) を指定することで追跡できます。 LOCAL_SHARED_LIBRARIES キーのモジュールを使用し、FSGL などの LD を介して正しいリンクを使用する、二重リンク メカニズムを忘れないでください。

    LOCAL_LDLIBS := -lEGL -lGLESv2
    
    

    適応と発売

    いくつかの点を変更する必要がありました。たとえば、iOS および Android のビルドから GLEW を削除し、一部の OpenGL 呼び出しの名前を変更し、EOS ポストフィックス (glGenVertexArrays -> glGenVertexArraysOES) を追加し、欠落している最新のデバッグ関数用のマクロを追加しました。おまけに、マクロを示す GLES2 ヘッダーが暗黙的に組み込まれていることです。 GL_GLEXT_PROTOTYPES 1:

    #define GL_GLEXT_PROTOTYPES 1
    #include "SDL_opengles2.h"
    
    

    また、最初の起動時に黒い画面が表示され、「E/libEGL: validate_display:255 error 3008 (EGL_BAD_DISPLAY)」のようなエラーが表示され、SDL ウィンドウの初期化、OpenGL プロファイルが変更され、すべてが機能しました。

    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 );
    

    エミュレータでは、アプリケーションはデフォルトで SDL アイコンと「Game」という名前でインストールされます。

    CMake に基づいてアセンブリ ファイルを自動的に生成するか、すべてのプラットフォームのアセンブリを Gradle に移行する可能性を検討する必要があります。ただし、CMake は現在進行中の C++ 開発における事実上の選択肢であり続けています。

    ソースコード

    https://gitlab.com/demensdeum/android- sdl-テスト-アプリ
    https://gitlab.com/demensdeum/android-sdl-test-app/tree/master/cube-art-project-android

    ソース

    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

    LazyFoo プロダクションの Web サイト

    おそらく、私のプロジェクトや新しい開発がほぼ常に始まる Web サイトについて言及する価値があると思います。これは LazyFoo Productions Web サイトです。ここでは、複雑な API の使用例、一見互換性のないものを組み合わせる方法など、非常にハードコアなトピックに対する答えを見つけることができます。システム (Android/C++) と動作原理の詳細な説明、実際に動作するコード例。

    https://lazyfoo.net/

    逆さまの世界

    新しいプロジェクトを開発するために、Cube Art Project はテスト駆動開発手法を採用しました。このアプローチでは、アプリケーションの特定の機能のテストが最初に実装され、次に特定の機能が実装されます。このアプローチの大きな利点は、機能の開発が開始される前に、実装の詳細にできるだけ関与しない最終インターフェイスの実装であると考えています。このアプローチでは、インターフェイスが特定の実装のコントラクトである場合、テストによってさらなる実装が決定され、コントラクト プログラミングの利点がすべて追加されます。
    キューブアートプロジェクト –ユーザーが立方体からフィギュアを構築する 3D エディターは、少し前までは非常に人気がありました。これはグラフィカルなアプリケーションなので、スクリーンショット検証を含むテストを追加することにしました。
    スクリーンショットを検証するには、OpenGL コンテキストからスクリーンショットを取得する必要があります。これは glReadPixels 関数を使用して行われます。関数の引数の説明は簡単です –開始位置、幅、高さ、形式 (RGB/RGBA/など)、出力バッファへのポインタ。SDL を使用したことがある人、または C でデータ バッファを使用した経験がある人は、必要な引数を単純に置き換えることができます。ただし、glReadPixels 出力バッファの興味深い機能について説明する必要があると思います。SDL_Surface ではすべての基本操作が上から下に行われるのに対し、ピクセルは下から上に保存されます。
    つまり、png ファイルから参照スクリーンショットをロードしたのですが、2 つのバッファーの 1 つが上下逆だったため、2 つのバッファーを直接比較できませんでした。
    OpenGL から出力バッファーを反転するには、Y 座標のスクリーンショットの高さを減算して出力バッファーを埋める必要がありますが、埋めるときに 1 を減算しないとバッファーの制限を超える可能性があることを考慮する価値があります。メモリ破損の原因となります。
    私は常に C のようなポインタによる直接メモリ アクセスではなく、「インターフェイスによるプログラミング」という OOP パラダイムを使用しようとしているため、バッファの外にデータを書き込もうとすると、メソッドの境界検証のおかげでオブジェクトがこれを通知してくれました。 。
    トップダウン スタイルでスクリーンショットを取得するメソッドの最終コード:

        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);
    
    

    ソース

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

    ソースコード

    https://gitlab.com/demensdeum/cube-アートプロジェクトブートストラップ

    最長の共通部分文字列

    この投稿では、最大共通部分文字列問題を解決するためのアルゴリズムについて説明します。暗号化されたバイナリ データを復号化しようとしているとします。まず、最大の部分文字列を検索して共通のパターンを見つけてみましょう。
    入力文字列の例:
    adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
    2 回繰り返される文字列を探しています。
    データヘッダー??

    プレフィックス

    まず、2 つの文字列の接頭辞を比較するメソッドを作成しましょう。左側の接頭辞の文字が右側の接頭辞の文字と等しい結果の文字列を返します。
    たとえば、行の場合は次のようになります。

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

    結果文字列 –空自
    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)
    }
    
    

    ブルートフォース

    物事がうまくいかないときは、強引な手段に頼るべきです。 longestPrefix メソッドを使用して、文字列を 2 つのループで処理します。最初のループでは i から最後までの文字列を取得し、2 番目のループでは i + 1 から最後までの文字列を渡して、最大のプレフィックスを検索します。このアルゴリズムの時間計算量は約 O(n^2) ~ O(n*^3) です。
    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
    }
    
    

    サフィックス配列

    より洗練されたソリューションには、「Suffix Array」と呼ばれるデータ構造というツールが必要です。このデータ構造は、ループ内に埋められた部分文字列の配列であり、各部分文字列は行の次の文字から始まり、最後まで続きます。
    たとえば、次の行の場合:

    adasDATAHEADER??
    
    

    サフィックス配列は次のようになります:

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

    並べ替えることで解決します

    サフィックス配列をソートしてから、現在の要素が左側 (lhs) にあり、次の要素が右側 (rhs) にあるループ内のすべての要素を調べて、longestPrefix を使用して最長のプレフィックスを計算します。方法
    について。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
    }
    
    

    アルゴリズムの時間計算量は O(N log N) であり、単純な解決策よりもはるかに優れています。

    ソース

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

    ソースコード

    https://gitlab.com/demensdeum/algorithms

    挿入ソート、マージソート

    挿入並べ替え

    挿入並べ替え –各要素はリスト内の前の要素と比較され、 大きい方の要素があればその要素と交換されます。それ以外の場合は内部比較ループが実行されます。止まります。要素は最初から最後までソートされるため、各要素はすでにソートされたリストと比較され、*おそらく* 全体の実行時間が短縮されます。アルゴリズムの時間計算量は O(n^2)、つまりバブルの種類と同じです。

    並べ替えを結合

    並べ替えを結合–リストは 1 つの要素のグループに分割され、その後、それらのグループがペアで「マージ」され、同時に比較されます。私の実装では、ペアをマージするときに、左側の要素が右側の要素と比較され、左側の要素がなくなった場合は、右側のすべての要素が結果のリストに追加されます。 list (グループ内のすべての要素が繰り返しソートされるため、追加の比較は不要です)< br />このアルゴリズムの作業は並列化するのが非常に簡単です。ペアを結合する段階は、ディスパッチャーでの反復の終了を待ってスレッドで実行できます。
    シングルスレッド実行のアルゴリズムの出力:

    ["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", "Артем"]
    
    

    マルチスレッド実行のアルゴリズムの出力:

    ["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", "Артем"]
    
    

    アルゴリズムの時間計算量は O(n*log(n)) で、O(n^2) よりわずかに優れています

    ソース

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

    ソースコード

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

    Erlang のバブルソート

    バブル ソートは非常に退屈ですが、通信用の関数型言語で実装してみるとさらに面白くなります。アーラン。

    数値のリストがあるので、それを並べ替える必要があります。バブル ソート アルゴリズムは、リスト全体を調べて、数値をペアごとに反復して比較します。チェック中に次の処理が行われます。出力リストに小さい番号が追加されるか、現在のリスト内の番号が交換されます。右側の番号が小さい場合は、反復内の次の番号で検索が続行されます。この走査は、リストに置換がなくなるまで繰り返されます。

    実際には、アルゴリズムの時間の複雑さのため、使用する価値はありません – O(n^2);私は Erlang で命令型スタイルで実装しましたが、興味がある場合は、より良いオプションを探すことができます。

    -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).
    
    

    インストールと起動

    Ubuntu では、Erlang のインストールは非常に簡単です。ターミナルに sudo apt install erlang と入力するだけです。この言語では、各ファイルは外部で使用できる関数のリストを含むモジュールである必要があります。輸出。この言語の興味深い特徴には、変数がなく定数のみであること、OOP の標準構文がないこと (OOP テクニックの使用を妨げるものではありません)、そしてもちろんアクター モデルに基づくロックなしの並列計算が含まれます。

    モジュールは、対話型 erl コンソールを使用してコマンドを次々に実行するか、あるいはもっと簡単に escript bubbleSort.erl を使用して実行できます。ケースが異なると、ファイルの外観も異なります。たとえば、escript の場合は、開始元となる main 関数を作成する必要があります。

    ソース

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

    ソースコード

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

    辞書編集的比較アルゴリズム

    辞書編集文字列比較アルゴリズムは非常に簡単に動作します。文字コードはループ内で比較され、文字が等しくない場合は結果が返されます。

    C 言語の例は次の場所にあります。
    https://github.com/gcc-mirror/gcc/blob/master/libiberty/memcmp.c

    単一の静的エンコーディングで文字を比較する必要があることを考慮する必要があります。たとえば、Swift では UTF-32 で文字ごとの比較を使用しました。 memcmp を使用した配列ソート オプションは、シングルバイト文字に対しては正確に機能しますが、その他の場合 (可変長エンコーディング)、順序が正しくない可能性があります。可変長エンコーディングに基づいた実装の可能性は排除しませんが、おそらく桁違いに複雑になるでしょう。

    アルゴリズムの時間計算量は、最良の場合は O(1)、平均および最悪の場合は O(n) です

    ソース

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

    ソース

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

    C による ZX Spectrum のゲーム開発

    このナンセンスな投稿は、C 言語の古い ZX Spectrum コンピューター用のゲーム開発に特化しています。ハンサムな男を見てみましょう。

    1982 年に生産が開始され、1992 年まで生産されました。マシンの技術的特徴: 8 ビット Z80 プロセッサ、16 ~ 128 kb のメモリ、およびAY-3-8910 サウンド チップ

    などのその他の拡張機能。

    このマシンのコンペティション Yandex Retro Games Battle 2019 の一環として、私はゲームを書きましたZ80のアセンブリ言語を学ぶ時間がなかったので、Cで開発することにしました。ツールチェーンとして、既製のセットを選択しました。 z88dk には、Spectrum 用アプリケーションの実装を高速化するための C コンパイラーと多くの補助ライブラリが含まれています。また、MSX、Texas Instruments 電卓など、他の多くの Z80 マシンもサポートしています。

    次に、コンピューター アーキテクチャである z88dk ツールチェーンに関する私の表面的な飛行について説明し、OOP アプローチを実装し、デザイン パターンを使用する方法を示します。

    インストール機能

    z88dk のインストールは、リポジトリのマニュアルに従って実行する必要がありますが、Ubuntu ユーザー向けに、次の機能に注意してください。 Z80 用のコンパイラが deb パッケージからインストールされている場合は、それらを削除する必要があります。ツールチェーン コンパイラのバージョンに互換性がないため、z88dk はデフォルトで bin フォルダからコンパイラにアクセスするため、おそらく何もコンパイルできなくなります。 /p>

    ハローワールド

    Hello World の記述は非常に簡単です。

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

    タップ ファイルのコンパイルはさらに簡単です。

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

    実行するには、オンラインなど、タップ ファイルをサポートする ZX Spectrum エミュレータを使用します。
    http://jsspeccy.zxdemo.org/

    全画面で画像に描画します

    tl;dr 画像はタイル (サイズ 8×8 ピクセルのタイル) で描画され、タイル自体は Spectrum フォントに組み込まれ、画像はインデックスからの線として印刷されます。

    スプライトおよびタイル出力ライブラリ sp1 は、UDG を使用してタイルを出力します。画像は個々の UDG (タイル) のセットに変換され、インデックスを使用して画面上で組み立てられます。 UDG はテキストを表示するために使用され、画像に非常に大きなタイルのセット (たとえば、128 タイルを超える) が含まれている場合は、セットの境界を越えてデフォルトのスペクトルを消去する必要があることに注意してください。フォント。この制限を回避するために、ベース 128 – を使用しました。元のフォントをそのまま残しながら画像を簡素化することで、255 を作成します。以下の写真の簡略化について。

    全画面画像を描画するには、次の 3 つのユーティリティを準備する必要があります。
    ギンプ
    img2スペック
    png2c-z88dk

    本物の ZX マン、本物のレトロ戦士には方法があります。これは、スペクトル パレットを使用してグラフィック エディタを開き、画像出力の機能を把握し、画像出力を手動で準備し、png2c-z88dk または png2scr を使用してアップロードすることです。< /p>

    より簡単な方法 – 32 ビット画像を取得し、Gimp で色数を 3 ~ 4 に切り替え、少し編集してから、色制限を手動で処理しないように img2spec にインポートし、png をエクスポートして、png2c を使用して C 配列に変換します。 z88dk。

    エクスポートを成功させるには、各タイルに 2 色以上を含めることはできないことに注意してください。

    その結果、一意のタイルの数を含む h ファイルを受け取ります。タイル数が 128 を超える場合は、Gimp で画像を簡略化し (再現性を高め)、新しいタイルに対してエクスポート手順を実行します。 .

    エクスポート後、文字通りタイルから「フォント」をロードし、タイル インデックスからの「テキスト」を画面に印刷します。以下は、レンダリング「クラス」の例です。

    // грузим шрифт в память
        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);
    

    画面上にスプライトを描画する

    次に、画面上に 16×16 ピクセルのスプライトを描画する方法を説明します。アニメーションや色の変更まではできなかったので…おそらくこの段階ですでにメモリが不足していることは些細なことです。したがって、ゲームには透明なモノクロ スプライトのみが含まれています。

    Gimp でモノクロの PNG イメージ 16×16 を描画し、png2sp1sprite を使用してそれを asm アセンブリ ファイルに変換し、C コードでアセンブリ ファイルから配列を宣言し、アセンブリ段階でファイルを追加します。< /p>

    スプライト リソースを宣言する段階の後、スプライト リソースを画面の目的の位置に追加する必要があります。以下は、ゲーム オブジェクトの「クラス」のコードの例です。

        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);
    

    関数の名前から – の意味はおおよそ理解できます。スプライトにメモリを割り当て、8×8 列を 2 つ追加し、スプライトに色を追加します。

    スプライトの位置は各フレームに示されます。

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

    OOP のエミュレーション

    C には OOP の構文がありません。それでも本当に使いたい場合はどうすればよいでしょうか? OOP 機器などというものは存在せず、最終的にはすべてがマシン アーキテクチャの 1 つに行き着き、そこにはオブジェクトやそれに関連する他の抽象概念がまったく存在しないという考えに心をつなぎ、啓発される必要があります。< /p>

    この事実により、私は長い間、なぜ OOP が必要なのか、最終的にすべてがマシンコードになるのになぜ OOP を使用する必要があるのか​​を理解することができませんでした。

    しかし、製品開発に携わった後、主に開発の柔軟性、適切なアプローチによるコード保護メカニズム、エントロピーの削減、チーム作業の簡素化など、このプログラミング パラダイムの楽しさを発見しました。上記のメリットはすべて、3 つの柱から生まれています。ポリモーフィズム、カプセル化、継承。

    アプリケーション アーキテクチャに関連する問題の解決が簡素化されていることも注目に値します。アーキテクチャ上の問題の 80% は前世紀にコンピュータ科学者によって解決され、デザイン パターンに関する文献で説明されているからです。次に、OOP のような構文を C に追加する方法について説明します。

    クラス インスタンスのデータを格納するための基礎として C 構造体を使用する方が便利です。もちろん、バイト バッファを使用したり、クラスやメソッドの独自の構造を作成したりすることはできますが、なぜ車輪の再発明が必要なのでしょうか?結局のところ、私たちはすでに構文を再発明しつつあるのです。

    クラスデータ

    ゲームオブジェクトの「クラス」データフィールドの例:

    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;
    

    クラスを「GameObject.h」として保存し、適切な場所に #include 「GameObject.h」を実行して使用します。

    クラスメソッド

    Objective-C 言語の開発者の経験を考慮すると、クラス メソッドのシグネチャはグローバル スコープの関数となり、最初の引数は常にデータ構造となり、その後にメソッド引数が続きます。以下は、「クラス」GameObject の「メソッド」の例です。

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

    メソッド呼び出しは次のようになります。

    GameObject_hide(gameObject);
    

    コンストラクターとデストラクターは同じ方法で実装されます。コンストラクターをアロケーターおよびフィールド初期化子として実装することは可能ですが、私はオブジェクトの割り当てと初期化を個別に制御することを好みます。

    メモリの操作

    C++ と一致するように、新しいマクロと削除マクロでラップされた malloc と free を使用したフォームの手動メモリ管理:

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

    複数のクラスで同時に使用されるオブジェクトの場合、古い Objective-C ランタイム 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);
        }
    }
    

    したがって、各クラスは、retain を使用して共有オブジェクトの使用を宣言し、release を通じて所有権を解放する必要があります。最新バージョンの ARC では、自動保持/解放呼び出しが使用されます。

    響け!

    Spectrum には 1 ビット音楽を再生できるツイーターがあり、当時の作曲家は最大 4 つのサウンド チャンネルを同時に再生できました。

    Spectrum 128k には、トラッカー ミュージックを再生できる別個のサウンド チップ AY-3-8910 が含まれています。

    z88dk のツイーターを使用するためのライブラリが提供されています

    今後学ばなければならないこと

    私は、Spectrum について知り、z88dk を使用してゲームを実装し、多くの興味深いことを学ぶことに興味がありました。たとえば、Z80 アセンブラを使用すると、Spectrum のフルパワーを使用したり、メモリ バンクを操作したり、AY-3-8910 サウンド チップを操作したりできるため、まだ学ぶべきことがたくさんあります。来年もコンテストに参加したいと思っています!

    リンク

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

    ソースコード

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

    二分探索

    電子メール アドレス「demensdeum@gmail.com」が、手紙の受信が許可されている電子メール アドレスのリストに含まれているかどうかを確認する必要があるとします。 .

    最初の要素から最後の要素までリスト全体を調べて、その要素が指定されたアドレスと等しいかどうかを確認してみましょう –線形探索アルゴリズムを実装してみましょう。しかし、これには長い時間がかかりますか?

    この質問に答えるには、「アルゴリズムの時間計算量」の「O」表記を使用します。最悪の場合の線形探索の動作時間は配列要素の n 番目の数に等しいので、これを「O」表記で書きましょう –の上)。次に、既知のアルゴリズムには 3 つのパフォーマンス指標があることを説明する必要があります。最良の場合、最悪の場合、および平均的な場合の実行時間。たとえば、メール アドレス「demensdeum@gmail.com」は配列の最初のインデックスにあり、次の最初のステップで見つかります。このアルゴリズムを使用すると、実行時間はせいぜい – ということになります。 O(1);そして、リストの最後にある場合、これは最悪のケースです。 O(n)

    しかし、ソフトウェアの実装やハードウェアのパフォーマンスの詳細についてはどうなのでしょうか?それらは Big O に影響を与えるはずです。ここで一呼吸置いて、時間計算量の計算が、このアルゴリズムのみが存在し、他には何も存在しない、抽象的な理想的なマシンに対して計算されると想像してください。

    アルゴリズム

    OK、線形探索はかなり遅いことがわかりました。二分探索を使ってみましょう。まず、バイナリ データを処理しないことを明確にしておきます。この名前は、その動作の特殊性のためにこのメソッドに付けられました。最初に配列を 辞書編集順の場合、アルゴリズムは配列全体の範囲を取得し、範囲の中央の要素を取得し、それを比較します辞書順に基づいて、比較の結果に応じて、さらに検索するためにどの範囲を使用するかを決定します。現在の上半分または下半分。つまり、各検索ステップで、可能な 2 つの候補から決定が行われます。バイナリロジック。このステップは、単語が見つかるか見つからない (範囲の下位インデックスと上位インデックスの交差が発生する) まで繰り返されます。

    このアルゴリズムのパフォーマンス –最良のケースは要素が配列 O(1) の中央ですぐに見つかった場合であり、列挙の最悪のケースは O(log n) です。

    落とし穴

    二分探索を実装する際、 プログラミング言語ライブラリにおける辞書編集の比較の標準化が欠如という興味深い問題に遭遇しただけでなく、 実装のための統一標準が存在しないことさえ発見しました。 localeJavaScript 内で比較します。 ECMAScript 標準では、この関数のさまざまな実装が許可されています。そのため、localeCompare を使用して並べ替える場合、異なる JavaScript エンジンではまったく異なる結果が観察される可能性があります。

    したがって、アルゴリズムが正しく機能するには、同じ辞書編集比較アルゴリズムのみを並べ替えて使用する必要があり、そうでないと何も機能しません。しかし、たとえば、ある実装の独自のソート/ソートを実装せずに、Scala で配列をソートし、nodejs を使用して検索しようとすると、人間性への失望以外に何も待つことはありません。

    ソース

    辞書編集的比較とは何ですか?また、それは何を表しますか?
    Почему для вычисления сложности алгоритмов используется log N вместо lb N?
    Двоичный поиск
    Знай сложности алгоритмов
    https://stackoverflow.com/questions/52941016/sorting-in-localecompare-in-javascript

    ソースコード

    https://gitlab.com/demensdeum/algorithms

    パターンファサード


    ファサードとは、構造設計パターンを指します。複雑なシステムの操作を可能にする単一のインターフェイスを提供し、クライアントがこれらのシステムに関する実装の詳細を持たないようにできるため、コードが簡素化され、クライアントと下位レベルのシステム間の疎結合が実装されます。 GoF にはファサードの良い例があります。さまざまな目標を追求するさまざまなクライアントに、単一のコンパイラ ファサード インターフェイスを通じてコードをアセンブルする機能を提供するプログラミング言語コンパイラ。

    ソース

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

    抽象的な工場パターン

    抽象ファクトリー–特定のクラスを指定せずに、関連オブジェクトを作成するためのインターフェイスを提供します。

    このパターンの別名がとても気に入っています – キット (キット)

    これはファクトリ メソッドに非常に似ていますが、抽象ファクトリは作成されるオブジェクト間の関係を記述する必要があります。そうでない場合は、単なる神オブジェクトになります。 すべてを生み出すアンチパターンは行き当たりばったりです。

    メガネ用の AR フレームワークを開発するところを想像してください。屋内ナビゲーションの矢印、店舗のアイコン、興味深い場所、ウィンドウ、ユーザーが現在いる場所に関する情報を含むボタンを画面上に表示します。

    同時に、AR 環境コントロールの外観と動作をカスタマイズする機能も必要です。この場合にこそ、Set パターンを使用する必要があります。

    Abstract FactoryAbstract Products のインターフェースを書いてみましょう –親プロトコル、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)
    }
    

    キット開発者は、Abstract Factory インターフェイスに基づいて Concrete Factory を実装する必要があります。また、アプリケーションの残りの部分は、コードを変更せずにファクトリで動作できるように、すべての要素をまとめて実装する必要があります。< /p>

    ソース

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

    ファクトリーメソッド

    ファクトリー メソッド パターンは、ジェネレーティブ デザイン パターンを指します。
    このパターンは、特定のクラスのオブジェクトを作成するためのインターフェイスの作成を記述します。簡単そうに思えますよね?

    理論上

    AR メガネを操作するためのフレームワークを開発しているとします。頭を横に傾けると、利用可能なアプリケーションのメニューがユーザーの目の前に表示されるはずです。アプリケーションは、当社のフレームワークのクライアントであるサードパーティ企業によって開発されます。当然のことながら、どのアプリケーション、アイコン、名前が表示されるべきかわからないため、アイコンとアプリケーションに関する関連情報を実装するためのインターフェイスを提供する必要があります。これを製品:

    と呼びましょう。

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

    次に、クライアントが特定の製品用の一連のアプリケーションの発行を実装できるように、インターフェイスを提供する必要があります。名前が付いたアプリケーション アイコンの配列。これはフレームワーク内ですでに描画されています。

    このインターフェースを書いてみましょう – プロダクトの配列を返すファクトリ メソッドを含むクリエイターインターフェース。

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

    実際に

    AR フレームワークの最初のクライアントは 7B – 社でした。 ホンジュラスのコーヒーメーカー用ソフトウェアの大手サプライヤー。彼らは、屋内マップ モードを使用して、コーヒーを淹れたり、水や豆が入っているかどうかを確認したり、最寄りのコーヒー メーカーへの道を示す機能を備えた拡張現実グラスを販売したいと考えています。

    彼らはソフトウェアの開発を引き受けます。私たちは、アプリケーションのリストとその詳細を正しく表示するために、クリエイター インターフェイスと 製品 インターフェイスに関するドキュメントを提供することのみを求められます。

    ドキュメントを転送した後、7B 社は Creator インターフェースを使用して Specific Creator を実装します。アプリケーションアイコンの配列を返すクラス。アイコン アプリケーション自体は、製品 インターフェースを実装する特定の製品 クラスです。

    特定の製品のコード例:

    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”
    }
    

    クラス Concrete Creator は、2 つのアプリケーションの配列を提供します。

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

    この後、7B 社はコンクリート製品コンクリート クリエーターのライブラリを編集し、それを当社のフレームワークと組み合わせて、コーヒー メーカー用の AR グラスの販売を開始します。 私たちの側での追加は必要ありません

    ソース

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

    パターンコマンド

    コマンド パターンは動作設計パターンを指します。

    これは私が長い間こだわってきたパターンです。単純すぎて非常に複雑です。しかし、個人的には、独学の素晴らしさは、特定のトピックをあらゆる角度から研究するための時間をいつでも手に入れられることだと思います。

    したがって、GoF では、適用可能性が非常に簡潔かつ明確に説明されています。
    リクエストをオブジェクトとしてカプセル化し、さまざまなリクエストでクライアントをパラメータ化し、キューを使用し、リクエストをログに記録し、キャンセル操作を実行できるようにします。

    次に、説明にあるコマンドの単純なバージョンを実装してみましょう。

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

    リクエストは文字列クラス オブジェクトにカプセル化されており、クライアントの設定、キューへのコマンドの追加、ログ記録、キャンセル(「スナップショット」パターンを使用)に使用できます。

    SQL クエリなどを実行するにはこれで十分だと思いますが、実装の詳細、さまざまなアプリケーション オプション、パターンのコード ベース、クライアント ロール、補助クラスも大きく異なります。

    マテリアルパーツ

    コマンド パターンは、単一の execute() メソッドを含む コマンド プロトコル で始まります。次に特定のコマンドとレシーバーが続きます。CC はレシーバー上で操作を実装し、レシーバーとアクションの間の接続を記述します。何か不明な点はありますか?私もそうですが、先に進みましょう。 クライアント特定のコマンドのインスタンスを作成し、 それをレシーバーに関連付けます。 依頼者コマンドを起動するプロセスを実行するオブジェクト。

    例を使用してそれを理解してみましょう。myPhone で myOS を更新したいとします。これを行うには、myOS_Update アプリケーションを起動します。その中で [Update Now] ボタンを押すと、10 秒後にシステムが更新されます。アップデートが成功したことを報告します。

    上記の例のクライアント は myOS_Update! アプリケーション、呼び出し元 は「今すぐ更新!」ボタンで、特定のコマンド を起動します。 b>レシーバーにアクセスするexecute() メソッドを使用してシステムを更新します–オペレーティング システムのアップデート デーモン。

    使用例

    myOS_Update アプリケーションの UI を受け入れましょう。非常に優れていたため、他のオペレーティング システムを更新するためのインターフェイスを提供するために、別の製品として販売することにしました。この場合、ライブラリを介して拡張機能をサポートするアプリケーションを実装します。ライブラリには特定のコマンド、 レシーバーの実装があり、静的/不変の呼び出し元は残します。 、クライアント、プロトコルコマンド

    したがって、コードは変更されないままであるため、変更可能なコードをサポートする必要はありません。特定のコマンド のコード内のエラーにより、クライアント側で実装された場合にのみ問題が発生する可能性があります。 受信機。また、この実装では、メイン アプリケーションのソース コードを転送する必要はありません。つまり、コマンド パターンを使用してコマンドと UI インタラクションをカプセル化しました。

    ソース

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

    Ubuntu OSXCros CMake 用の macOS アプリケーションの構築

    この投稿では、CMake と osxcross を使用して、Ubuntu ビルド マシン上で macOS 用のクロスプラットフォーム C++ アプリケーションを構築する方法について説明します。
    まず、osxcross ツールチェーンをインストールします。
    https://github.com/tpoechtrager/osxcross
    インストールは 3 段階で行われ、依存関係をダウンロードします。

    cd tools
    ./get_dependencies.sh
    

    Apple 公式 Web サイトから XCode.xip をダウンロードし、XCode から SDK をダウンロードします。

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

    最後のステップで XCode 使用許諾契約を読んでいただければ幸いです。次に、必要なプレフィックスを使用してツールチェーンを構築します。

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

    これで、前の手順のプレフィックス ディレクトリから osxcross を使用できるようになります。 CMake の新しいビルド マクロを追加して、必要なものをすべて記述してみましょう。

    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()
    

    動的リンクが成功しなかったため、ライブラリを静的にエクスポートします。

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

    次に、osxcross に必要なライブラリがないという事実に直面するかもしれません。私は SDL2 を使用しているときにこれに遭遇しました。 osxcross は既製のライブラリ パッケージをサポートしています –マックポート。たとえば、SDL2-mixer をインストールする場合は次のようになります。

    osxcross-macports -v install libsdl2_mixer
    

    この後、cmake-make リンクで通常どおりライブラリ/アプリケーションの構築を開始できます。必要に応じてライブラリの静的リンクを指定することを忘れないでください。

    ライブラリの手動アセンブリ

    現在、最終的なアプリケーションを構築するときに、静的リンク中にライブラリが正しくアーカイブされないという問題が発生し、次のエラーが発生します。

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

    このチケットと非常によく似た、回避策を実行すると、アセンブリが正しく完了します。静的ライブラリを解凍し、osxcross アーカイバを使用して新たにビルドしましょう。

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

    私は個人的に、macOS アプリケーションを Ubuntu 上で直接実行する機能 (少なくとも一部の機能) が欠如していることも問題の 1 つであると考えています。もちろん、プロジェクトがあります ダーリンですが、サポートにはまだ改善の余地がたくさんあります。

    ソース

    https://github.com/tpoechtrager/osxcross

    Ubuntu MinGW CMake で Windows 用にビルドする

    この投稿では、Ubuntu で MinGW32 ツールチェーンを使用して Windows 用のライブラリとアプリケーションを構築するプロセスについて説明します。
    wine をインストールします。

    sudo apt-get install wine mingw-w64
    

    これで、Windows 用の C/C++ アプリケーションを構築できるようになります。

    # 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
    

    収集したexeはwineを使用して確認できます。

    次に、CMake ビルド、CMakeLists.txt ファイルへの変更を見てみましょう。MinGW 固有のものをビルド ファイルに追加します。

    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()
    

    収集中:

    cmake -DMINGW32=1 .
    make
    

    出力は、収集している内容に応じて dll または exe になります。実際の例として、新しい Cube-Art-Project とそのライブラリのリポジトリをご覧ください。
    https://gitlab.com/demensdeum/cube-art-project
    https://gitlab.com/demensdeum/FlameSteelEngineGameToolkitFSGL
    https://gitlab.com/demensdeum/cube-art-project-bootstrap

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

    ChromeDriver の簡単な Emscripten 自動テスト

    このノートでは、Chrome ブラウザの ChromeDriver の自動テストを実行する実装について説明します。これは、Emscripten を使用して C++ から翻訳されたモジュール自動テストを実行し、コンソール出力を読み取り、テスト結果を返します。
    まず、Selenium をインストールする必要があります。Python 3-Ubuntu の場合、これは次のように行われます。

    pip3 install selenium
    

    次に、公式 Web サイトから ChromeDriver をダウンロードし、chromedriver を /usr/local/bin に配置します。その後、自動テストの実装を開始できます。
    以下に、Emscripten で自動テスト ページを開いた状態で Chrome ブラウザを起動し、「Window test succeded」というテキストの存在をチェックする自動テスト コードを示します。

    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)
    

    テストを main.py として保存し、python3 main.py を実行します