Shell Sort – eine Variante der Einfügungssortierung mit vorläufiger Kämmung eines Zahlenarrays.
Wir müssen uns daran erinnern, wie die Einfügungssortierung funktioniert:
1. Eine Schleife wird von Null bis zum Ende der Schleife gestartet, wodurch das Array in zwei Teile geteilt wird 2. Für den linken Teil wird eine zweite Schleife gestartet, die Elemente von rechts nach links vergleicht. Das kleinere Element auf der rechten Seite wird gelöscht, bis ein kleineres Element auf der linken Seite gefunden wird 3. Am Ende beider Schleifen erhalten wir eine sortierte Liste
Es war einmal der Informatiker Donald Schell, der sich fragte, wie man den Einfügungssortierungsalgorithmus verbessern könnte. Er kam auch auf die Idee, das Array zunächst in zwei Zyklen zu durchlaufen, jedoch in einem bestimmten Abstand, und den „Kamm“ schrittweise zu verkleinern, bis daraus ein regulärer Einfügungssortierungsalgorithmus wird. Alles ist wirklich so einfach, keine Fallstricke. Zu den beiden oben genannten Zyklen fügen wir einen weiteren hinzu, in dem wir die Größe des „Kamms“ schrittweise reduzieren. Das Einzige, was Sie tun müssen, ist, beim Vergleich den Abstand zu überprüfen, damit er nicht über das Array hinausgeht.
Ein wirklich interessantes Thema ist die Auswahl der Reihenfolge zum Ändern der Vergleichslänge bei jeder Iteration der ersten Schleife. Dies ist deshalb interessant, weil die Leistung des Algorithmus davon abhängt.
An der Berechnung des idealen Abstands waren verschiedene Personen beteiligt; für sie war dieses Thema offenbar so interessant. Könnten sie nicht einfach Ruby ausführen und den schnellsten sort()-Algorithmus aufrufen?
Im Allgemeinen haben diese seltsamen Leute Dissertationen zum Thema der Berechnung des Abstands/der Lücke des „Kamms“ für den Shell-Algorithmus geschrieben. Ich habe einfach die Ergebnisse ihrer Arbeit verwendet und fünf Arten von Sequenzen überprüft: Hibbard, Knuth-Pratt, Chiura, Sedgwick.
import time
import random
from functools import reduce
import math
DEMO_MODE = False
if input("Demo Mode Y/N? ").upper() == "Y":
DEMO_MODE = True
class Colors:
BLUE = '\033[94m'
RED = '\033[31m'
END = '\033[0m'
def swap(list, lhs, rhs):
list[lhs], list[rhs] = list[rhs], list[lhs]
return list
def colorPrintoutStep(numbers: List[int], lhs: int, rhs: int):
for index, number in enumerate(numbers):
if index == lhs:
print(f"{Colors.BLUE}", end = "")
elif index == rhs:
print(f"{Colors.RED}", end = "")
print(f"{number},", end = "")
if index == lhs or index == rhs:
print(f"{Colors.END}", end = "")
if index == lhs or index == rhs:
print(f"{Colors.END}", end = "")
print("\n")
input(">")
def ShellSortLoop(numbers: List[int], distanceSequence: List[int]):
distanceSequenceIterator = reversed(distanceSequence)
while distance:= next(distanceSequenceIterator, None):
for sortArea in range(0, len(numbers)):
for rhs in reversed(range(distance, sortArea + 1)):
lhs = rhs - distance
if DEMO_MODE:
print(f"Distance: {distance}")
colorPrintoutStep(numbers, lhs, rhs)
if numbers[lhs] > numbers[rhs]:
swap(numbers, lhs, rhs)
else:
break
def ShellSort(numbers: List[int]):
global ShellSequence
ShellSortLoop(numbers, ShellSequence)
def HibbardSort(numbers: List[int]):
global HibbardSequence
ShellSortLoop(numbers, HibbardSequence)
def ShellPlusKnuttPrattSort(numbers: List[int]):
global KnuttPrattSequence
ShellSortLoop(numbers, KnuttPrattSequence)
def ShellPlusCiuraSort(numbers: List[int]):
global CiuraSequence
ShellSortLoop(numbers, CiuraSequence)
def ShellPlusSedgewickSort(numbers: List[int]):
global SedgewickSequence
ShellSortLoop(numbers, SedgewickSequence)
def insertionSort(numbers: List[int]):
global insertionSortDistanceSequence
ShellSortLoop(numbers, insertionSortDistanceSequence)
def defaultSort(numbers: List[int]):
numbers.sort()
def measureExecution(inputNumbers: List[int], algorithmName: str, algorithm):
if DEMO_MODE:
print(f"{algorithmName} started")
numbers = inputNumbers.copy()
startTime = time.perf_counter()
algorithm(numbers)
endTime = time.perf_counter()
print(f"{algorithmName} performance: {endTime - startTime}")
def sortedNumbersAsString(inputNumbers: List[int], algorithm) -> str:
numbers = inputNumbers.copy()
algorithm(numbers)
return str(numbers)
if DEMO_MODE:
maximalNumber = 10
numbersCount = 10
else:
maximalNumber = 10
numbersCount = random.randint(10000, 20000)
randomNumbers = [random.randrange(1, maximalNumber) for i in range(numbersCount)]
ShellSequenceGenerator = lambda n: reduce(lambda x, _: x + [int(x[-1]/2)], range(int(math.log(numbersCount, 2))), [int(numbersCount / 2)])
ShellSequence = ShellSequenceGenerator(randomNumbers)
ShellSequence.reverse()
ShellSequence.pop()
HibbardSequence = [
0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095,
8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575,
2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727,
268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591
]
KnuttPrattSequence = [
1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720,
797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733,
1743392200, 5230176601, 15690529804, 47071589413
]
CiuraSequence = [
1, 4, 10, 23, 57, 132, 301, 701, 1750, 4376,
10941, 27353, 68383, 170958, 427396, 1068491,
2671228, 6678071, 16695178, 41737946, 104344866,
260862166, 652155416, 1630388541
]
SedgewickSequence = [
1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905,
8929, 16001, 36289, 64769, 146305, 260609, 587521,
1045505, 2354689, 4188161, 9427969, 16764929, 37730305,
67084289, 150958081, 268386305, 603906049, 1073643521,
2415771649, 4294770689, 9663381505, 17179475969
]
insertionSortDistanceSequence = [1]
algorithms = {
"Default Python Sort": defaultSort,
"Shell Sort": ShellSort,
"Shell + Hibbard" : HibbardSort,
"Shell + Prat, Knutt": ShellPlusKnuttPrattSort,
"Shell + Ciura Sort": ShellPlusCiuraSort,
"Shell + Sedgewick Sort": ShellPlusSedgewickSort,
"Insertion Sort": insertionSort
}
for name, algorithm in algorithms.items():
measureExecution(randomNumbers, name, algorithm)
reference = sortedNumbersAsString(randomNumbers, defaultSort)
for name, algorithm in algorithms.items():
if sortedNumbersAsString(randomNumbers, algorithm) != reference:
print("Sorting validation failed")
exit(1)
print("Sorting validation success")
exit(0)
In meiner Implementierung sind für einen zufälligen Satz von Zahlen die schnellsten Lücken Sedgwick und Hibbard.
mypy
Ich möchte auch den statischen Typisierungsanalysator für Python 3 erwähnen – mypy. Hilft bei der Bewältigung der Probleme, die Sprachen mit dynamischer Eingabe innewohnen, indem es die Möglichkeit ausschließt, etwas dort festzuhalten, wo es nicht benötigt wird.
Wie erfahrene Programmierer sagen: „Statisches Tippen ist nicht erforderlich, wenn Sie ein Team von Profis haben.“ Eines Tages werden wir alle Profis, wir werden Code in völliger Einheit und Verständnis mit Maschinen schreiben, aber im Moment können Sie ähnliche Dienstprogramme verwenden und statisch typisierte Sprachen.
Doppelte Auswahlsortierung – eine Unterart der Auswahlsortierung, die anscheinend doppelt so schnell sein sollte. Der Vanilla-Algorithmus durchläuft die Liste der Zahlen doppelt, findet die Mindestzahl und tauscht die Plätze mit der aktuellen Zahl, auf die die Schleife auf der Ebene darüber zeigt. Die Sortierung mit doppelter Auswahl sucht nach den minimalen und maximalen Zahlen und ersetzt dann die beiden Ziffern, auf die die Schleife auf der Ebene darüber zeigt – zwei Zahlen links und rechts. Diese ganze Orgie endet, wenn die Cursor der zu ersetzenden Zahlen in der Mitte der Liste gefunden werden und als Ergebnis sortierte Zahlen links und rechts von der visuellen Mitte erhalten werden. Die zeitliche Komplexität des Algorithmus ähnelt der von Selection Sort – O(n2), aber angeblich gibt es eine Beschleunigung von 30 %.
Grenzzustand
Bereits in diesem Stadium können Sie sich den Moment einer Kollision vorstellen, zum Beispiel, wenn die Zahl des linken Cursors (die Mindestzahl) auf die Höchstzahl in der Liste zeigt, dann wird die Mindestzahl neu angeordnet, die Neuordnung der Höchstzahl bricht sofort zusammen. Daher beinhalten alle Implementierungen des Algorithmus die Prüfung auf solche Fälle und das Ersetzen von Indizes durch korrekte. In meiner Implementierung hat eine Prüfung gereicht:
maximalNumberIndex = minimalNumberIndex;
}
Реализация на Cito
Cito – язык либ, язык транслятор. На нем можно писать для C, C++, C#, Java, JavaScript, Python, Swift, TypeScript, OpenCL C, при этом совершенно ничего не зная про эти языки. Исходный код на языке Cito транслируется в исходный код на поддерживаемых языках, далее можно использовать как библиотеку, либо напрямую, исправив сгенеренный код руками. Эдакий Write once – translate to anything.
Double Selection Sort на cito:
{
public static int[] sort(int[]# numbers, int length)
{
int[]# sortedNumbers = new int[length];
for (int i = 0; i < length; i++) {
sortedNumbers[i] = numbers[i];
}
for (int leftCursor = 0; leftCursor < length / 2; leftCursor++) {
int minimalNumberIndex = leftCursor;
int minimalNumber = sortedNumbers[leftCursor];
int rightCursor = length - (leftCursor + 1);
int maximalNumberIndex = rightCursor;
int maximalNumber = sortedNumbers[maximalNumberIndex];
for (int cursor = leftCursor; cursor <= rightCursor; cursor++) { int cursorNumber = sortedNumbers[cursor]; if (minimalNumber > cursorNumber) {
minimalNumber = cursorNumber;
minimalNumberIndex = cursor;
}
if (maximalNumber < cursorNumber) {
maximalNumber = cursorNumber;
maximalNumberIndex = cursor;
}
}
if (leftCursor == maximalNumberIndex) {
maximalNumberIndex = minimalNumberIndex;
}
int fromNumber = sortedNumbers[leftCursor];
int toNumber = sortedNumbers[minimalNumberIndex];
sortedNumbers[minimalNumberIndex] = fromNumber;
sortedNumbers[leftCursor] = toNumber;
fromNumber = sortedNumbers[rightCursor];
toNumber = sortedNumbers[maximalNumberIndex];
sortedNumbers[maximalNumberIndex] = fromNumber;
sortedNumbers[rightCursor] = toNumber;
}
return sortedNumbers;
}
}
If the game doesn’t start with fcntl(5) for /tmp/source_engine_2808995433.lock failed, then try deleting the /tmp/source_engine_2808995433.lock file rm /tmp/source_engine_2808995433.lock
Usually the lock file is left over from the last game session unless the game was closed naturally.
How to check?
The easiest way to check the launch of applications on a discrete Nvidia graphics card is through the nvidia-smi utility:
For games on the Source engine, you can check through the game console using the mat_info command:
Schlafsortierung – Sleep Sort, ein weiterer Vertreter deterministischer seltsamer Sortieralgorithmen.
Es funktioniert so:
Durchläuft eine Liste von Elementen
Für jede Schleife wird ein separater Thread gestartet
Der Thread schläft für eine gewisse Zeit – Elementwert und Wertausgabe nach dem Ruhezustand
Warten Sie am Ende der Schleife, bis der längste Ruhezustand des Threads abgeschlossen ist, und zeigen Sie die sortierte Liste an
Beispielcode für den Schlafsortierungsalgorithmus in C:
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
typedef struct {
int number;
} ThreadPayload;
void *sortNumber(void *args) {
ThreadPayload *payload = (ThreadPayload*) args;
const int number = payload->number;
free(payload);
usleep(number * 1000);
printf("%d ", number);
return NULL;
}
int main(int argc, char *argv[]) {
const int numbers[] = {2, 42, 1, 87, 7, 9, 5, 35};
const int length = sizeof(numbers) / sizeof(int);
int maximal = 0;
pthread_t maximalThreadID;
printf("Sorting: ");
for (int i = 0; i < length; i++) { pthread_t threadID; int number = numbers[i]; printf("%d ", number); ThreadPayload *payload = malloc(sizeof(ThreadPayload)); payload->number = number;
pthread_create(&threadID, NULL, sortNumber, (void *) payload);
if (maximal < number) {
maximal = number;
maximalThreadID = threadID;
}
}
printf("\n");
printf("Sorted: ");
pthread_join(maximalThreadID, NULL);
printf("\n");
return 0;
}
In dieser Implementierung habe ich die Funktion usleep für Mikrosekunden verwendet, wobei der Wert mit 1000 multipliziert wurde, d. h. in Millisekunden. Zeitliche Komplexität des Algorithmus – O(sehr lang)
Stalin Sort – Sortieren durch, einer der Sortieralgorithmen mit Datenverlust. Der Algorithmus ist sehr produktiv und effizient, Zeitkomplexität O(n).
Es funktioniert so:
Durchlaufen Sie das Array und vergleichen Sie das aktuelle Element mit dem nächsten
Wenn das nächste Element kleiner als das aktuelle ist, entfernen Sie es
Als Ergebnis erhalten wir ein sortiertes Array in O(n)
Beispiel für die Ausgabe des Algorithmus:
Gulag: [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
Element 2 sent to Gulag
Element 4 sent to Gulag
Element 8 sent to Gulag
Element 5 sent to Gulag
Element 0 sent to Gulag
Element 35 sent to Gulag
Element 10 sent to Gulag
Numbers: [1, 3, 4, 6, 42]
Gulag: [2, 4, 8, 5, 0, 35, 10]
Python 3-Code:
gulag = []
print(f"Numbers: {numbers}")
print(f"Gulag: {numbers}")
i = 0
maximal = numbers[0]
while i < len(numbers):
element = numbers[i]
if maximal > element:
print(f"Element {element} sent to Gulag")
gulag.append(element)
del numbers[i]
else:
maximal = element
i += 1
print(f"Numbers: {numbers}")
print(f"Gulag: {gulag}")
Zu den Nachteilen gehört der Datenverlust, aber wenn wir uns einer utopischen, idealen, sortierten Liste in O(n) nähern, wie sonst?
Ich habe keine Objective-C-Implementierung im Rosetta-Code gefunden , schrieb ich selbst:
#include <Foundation/Foundation.h>
@implementation SelectionSort
- (void)performSort:(NSMutableArray *)numbers
{
NSLog(@"%@", numbers);
for (int startIndex = 0; startIndex < numbers.count-1; startIndex++) {
int minimalNumberIndex = startIndex;
for (int i = startIndex + 1; i < numbers.count; i++) {
id lhs = [numbers objectAtIndex: minimalNumberIndex];
id rhs = [numbers objectAtIndex: i];
if ([lhs isGreaterThan: rhs]) {
minimalNumberIndex = i;
}
}
id temporary = [numbers objectAtIndex: minimalNumberIndex];
[numbers setObject: [numbers objectAtIndex: startIndex]
atIndexedSubscript: minimalNumberIndex];
[numbers setObject: temporary
atIndexedSubscript: startIndex];
}
NSLog(@"%@", numbers);
}
@end
Собрать и запустить можно либо на MacOS/Xcode, либо на любой операционной системе поддерживающей GNUstep, например у меня собирается Clang на Arch Linux.
Скрипт сборки:
Der Algorithmus umfasst mindestens zwei Arrays, das erste – Liste der zu sortierenden Ganzzahlen, zweite – ein Array der Größe = (maximale Anzahl – minimale Anzahl) + 1, das zunächst nur Nullen enthält. Als nächstes werden die Zahlen aus dem ersten Array aussortiert und das Zahlenelement wird verwendet, um einen Index im zweiten Array zu erhalten, der um eins erhöht wird. Nachdem wir die gesamte Liste durchgegangen sind, erhalten wir ein vollständig gefülltes zweites Array mit der Anzahl der Wiederholungen der Zahlen aus dem ersten. Der Algorithmus hat einen erheblichen Overhead – Das zweite Array enthält auch Nullen für Zahlen, die nicht in der ersten Liste enthalten sind, die sogenannten. Overhead aus dem Speicher
Nachdem wir das zweite Array erhalten haben, durchlaufen wir es und schreiben die nach Index sortierte Version der Zahl, wobei wir den Zähler auf Null dekrementieren. Ein Nullzähler wird zunächst ignoriert.
Ein Beispiel für den nicht optimierten Betrieb des Zählsortieralgorithmus:
Eingabearray 1,9,1,4,6,4,4
Dann ist das zu zählende Array 0,1,2,3,4,5,6,7,8,9 (Mindestzahl 0, Höchstzahl 9)
Mit Gesamtzählern 0,2,0,0,3,0,1,0,0,1
Gesamt sortiertes Array 1,1,4,4,4,6,9
Algorithmuscode in Python 3:
numbers = [42, 89, 69, 777, 22, 35, 42, 69, 42, 90, 777]
minimal = min(numbers)
maximal = max(numbers)
countListRange = maximal - minimal
countListRange += 1
countList = [0] * countListRange
print(numbers)
print(f"Minimal number: {minimal}")
print(f"Maximal number: {maximal}")
print(f"Count list size: {countListRange}")
for number in numbers:
index = number - minimal
countList[index] += 1
replacingIndex = 0
for index, count in enumerate(countList):
for i in range(count):
outputNumber = minimal + index
numbers[replacingIndex] = outputNumber
replacingIndex += 1
print(numbers)
Из-за использования двух массивов, временная сложность алгоритма O(n + k)
Pseudosortierung oder Sumpfsortierung, einer der nutzlosesten Sortieralgorithmen.
Es funktioniert so: 1. Die Eingabe ist ein Array von Zahlen 2. Eine Reihe von Zahlen wird zufällig gemischt (shuffle) 3. Prüft, ob das Array sortiert ist 4. Wenn nicht sortiert, wird das Array erneut gemischt 5. All diese Aktionen werden wiederholt, bis das Array zufällig sortiert ist.
Wie Sie sehen können, ist die Leistung dieses Algorithmus schrecklich. Kluge Leute glauben, dass sogar O(n * n!) d. h. Es besteht die Möglichkeit, dass Sie viele Jahre lang beim Würfeln zum Ruhm des Gottes des Chaos stecken bleiben. Das Array wird nie sortiert, oder vielleicht wird es sortiert?
Implementierung
Um es in TypeScript zu implementieren, musste ich die folgenden Funktionen implementieren: 1. Mischen Sie ein Array von Objekten 2. Array-Vergleich 3. Generieren einer Zufallszahl im Bereich von Null bis zu einer Zahl (sic!) 4. Druckfortschritt, weil es scheint, dass das Sortieren endlos weitergeht
Unten finden Sie den TypeScript-Implementierungscode:
const randomInteger = (maximal: number) => Math.floor(Math.random() * maximal);
const isEqual = (lhs: any[], rhs: any[]) => lhs.every((val, index) => val === rhs[index]);
const shuffle = (array: any[]) => {
for (var i = 0; i < array.length; i++) { var destination = randomInteger(array.length-1); var temp = array[i]; array[i] = array[destination]; array[destination] = temp; } } let numbers: number[] = Array.from({length: 10}, ()=>randomInteger(10));
const originalNumbers = [...numbers];
const sortedNumbers = [...numbers].sort();
let numberOfRuns = 1;
do {
if (numberOfRuns % 1000 == 0) {
printoutProcess(originalNumbers, numbers, numberOfRuns);
}
shuffle(numbers);
numberOfRuns++;
} while (isEqual(numbers, sortedNumbers) == false)
console.log(`Success!`);
console.log(`Run number: ${numberOfRuns}`)
console.log(`Original numbers: ${originalNumbers}`);
console.log(`Current numbers: ${originalNumbers}`);
console.log(`Sorted numbers: ${sortedNumbers}`);
Для отладки можно использовать VSCode и плагин TypeScript Debugger от kakumei.
Как долго
Вывод работы алгоритма:
src/bogosort.ts:1
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 8,7,0,2,4,7,2,5,9,5, try number: 145000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 7,5,2,4,9,8,0,5,2,7, try number: 146000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 0,2,7,4,9,5,7,5,8,2, try number: 147000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 5,9,7,8,5,4,2,7,0,2, try number: 148000
src/bogosort.ts:2
Success!
src/bogosort.ts:24
Run number: 148798
src/bogosort.ts:25
Original numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:26
Current numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:27
Sorted numbers: 0,2,2,4,5,5,7,7,8,9
Для массива из 10 чисел Богосорт перемешивал исходный массив 148798 раз, многовато да?
Алгоритм можно использовать как учебный, для понимания возможностей языка с которым предстоит работать на рынке. Лично я был удивлен узнав что в ванильных JS и TS до сих пор нет своего алгоритма перемешивания массивов, генерации целого числа в диапазоне, доступа к хэшам объектов для быстрого сравнения.
Das Interpreter-Muster bezieht sich auf Verhaltensentwurfsmuster. Mit diesem Muster können Sie Ihre eigene Programmiersprache implementieren, indem Sie mit einem AST-Baum arbeiten, dessen Eckpunkte terminale und nicht-terminale Ausdrücke sind, die die Interpret-Methode implementieren, die die Funktionalität der Sprache bereitstellt.
Terminalausdruck – zum Beispiel die Zeichenfolgenkonstante – “Hallo Welt”
Nicht-terminaler Ausdruck – zum Beispiel Print(“Hello World”), enthält Print und ein Argument aus dem Terminalausdruck “Hello World”
Was ist der Unterschied? Der Unterschied besteht darin, dass die Interpretation bei terminalen Ausdrücken endet, bei nicht-terminalen Ausdrücken jedoch ausführlich über alle eingehenden Eckpunkte/Argumente hinweg fortgesetzt wird. Wenn der AST-Baum nur aus nicht-terminalen Ausdrücken bestünde, würde die Anwendung niemals abgeschlossen werden, weil Für jeden Prozess ist eine gewisse Endlichkeit erforderlich. Diese Endlichkeit ist das, was terminale Ausdrücke ausmachen. Sie enthalten normalerweise Daten, zum Beispiel Zeichenfolgen.
Ein Beispiel für einen AST-Baum finden Sie unten:
Dcoetzee, CC0, über Wikimedia Commons
Wie Sie sehen können, sind Terminalausdrücke konstant und variabel, nichtterminale Ausdrücke sind der Rest.
Was nicht enthalten ist
Die Interpreter-Implementierung umfasst nicht das Parsen der in den AST-Baum eingegebenen Sprachzeichenfolge. Es reicht aus, Klassen von Terminal- und Nicht-Terminal-Ausdrücken zu implementieren, Methoden mit dem Kontextargument am Eingang zu interpretieren, einen AST-Ausdrucksbaum zu erstellen und die Interpret-Methode am Stammausdruck auszuführen. Ein Kontext kann verwendet werden, um den Anwendungsstatus zur Laufzeit zu speichern.
Implementierung
Das Muster beinhaltet:
Client – gibt den AST-Baum zurück und führt Interpret(context) für den Wurzelknoten (Client) aus
Kontext – enthält den Status der Anwendung, der bei der Interpretation an Ausdrücke übergeben wird (Kontext)
Abstrakter Ausdruck – eine abstrakte Klasse, die die Methode Interpret(context) (Expression) enthält
Terminalausdruck ist ein endgültiger Ausdruck, ein Nachkomme eines abstrakten Ausdrucks (TerminalExpression)
Ein nicht-terminaler Ausdruck ist kein endlicher Ausdruck; er enthält Zeiger auf Scheitelpunkte tief im AST-Baum. Untergeordnete Scheitelpunkte wirken sich normalerweise auf das Ergebnis der Interpretation des nicht-terminalen Ausdrucks aus (NonTerminalExpression).
Client-Beispiel in C#
static void Main(string[] args)
{
var context = new Context();
var initialProgram = new PerformExpression(
new IExpression[] {
new SetExpression("alpha", "1"),
new GetExpression("alpha"),
new PrintExpression(
new IExpression[] {
new ConstantExpression("Hello Interpreter Pattern")
}
)
}
);
System.Console.WriteLine(initialProgram.interpret(context));
}
}
Beispiel für einen abstrakten Ausdruck in C#
{
String interpret(Context context);
}
Beispiel für einen Terminalausdruck in C# (String-Konstante)
Beispiel eines nichtterminalen Ausdrucks in C# (Starten und Verketten der Ergebnisse untergeordneter Scheitelpunkte unter Verwendung des Trennzeichens „;“
{
public PerformExpression(IExpression[] leafs) : base(leafs) {
this.leafs = leafs;
}
override public String interpret(Context context) {
var output = "";
foreach (var leaf in leafs) {
output += leaf.interpret(context) + ";";
}
return output;
}
}
Können Sie es funktionell umsetzen?
Bekanntlich sind alle Turing-vollständigen Sprachen gleichwertig. Ist es möglich, das objektorientierte Muster auf die funktionale Programmiersprache zu übertragen?
Für ein Experiment nehmen wir eine FP-Sprache für das Web namens Elm. In Elm gibt es keine Klassen, aber Datensätze und Typen. Daher sind die folgenden Datensätze und Typen an der Implementierung beteiligt:
Ausdruck – Auflistung aller möglichen Sprachausdrücke (Ausdruck)
Untergeordneter Ausdruck – ein Ausdruck, der dem nichtterminalen Ausdruck (ExpressionLeaf) untergeordnet ist
Kontext – ein Datensatz, der den Status der Anwendung speichert (Kontext)
Funktionen, die Interpret(Kontext)-Methoden implementieren – alle notwendigen Funktionen, die die Funktionalität von Terminal- und Nicht-Terminal-Ausdrücken implementieren
Hilfsdatensätze des Interpreter-Status – notwendig für den korrekten Betrieb des Interpreters, sie speichern den Interpreter-Status und den Kontext
Ein Beispiel für eine Funktion, die die Interpretation für den gesamten Satz möglicher Ausdrücke in Elm implementiert:
case input.expression of
Constant text ->
{
output = text,
context = input.context
}
Perform leafs ->
let inputs = List.map (\leaf -> { expressionLeaf = leaf, context = input.context } ) leafs in
let startLeaf = { expressionLeaf = (Node (Constant "")), context = { variables = Dict.empty } } in
let outputExpressionInput = List.foldl mergeContextsAndRunLeafs startLeaf inputs in
{
output = (runExpressionLeaf outputExpressionInput).output,
context = input.context
}
Print printExpression ->
run
{
expression = printExpression,
context = input.context
}
Set key value ->
let variables = Dict.insert key value input.context.variables in
{
output = "OK",
context = { variables = variables }
}
Get key ->
{
output = Maybe.withDefault ("No value for key: " ++ key) (Dict.get key input.context.variables),
context = input.context
}
Was ist mit dem Parsen?
Das Parsen von Quellcode in einen AST-Baum ist nicht im Interpreter-Muster enthalten; es gibt mehrere Ansätze zum Parsen von Quellcode, aber dazu ein anderes Mal mehr. Bei der Implementierung des Interpreters für Elm habe ich einen einfachen Parser im AST-Baum geschrieben, der aus zwei Funktionen besteht: Parsen eines Scheitelpunkts und Parsen untergeordneter Scheitelpunkte.
parseLeafs state =
let tokensQueue = state.tokensQueue in
let popped = pop state.tokensQueue in
let tokensQueueTail = tail state.tokensQueue in
if popped == "Nothing" then
state
else if popped == "Perform(" then
{
tokensQueue = tokensQueue,
result = (state.result ++ [Node (parse tokensQueue)])
}
else if popped == ")" then
parseLeafs {
tokensQueue = tokensQueueTail,
result = state.result
}
else if popped == "Set" then
let key = pop tokensQueueTail in
let value = pop (tail tokensQueueTail) in
parseLeafs {
tokensQueue = tail (tail tokensQueueTail),
result = (state.result ++ [Node (Set key value)])
}
else if popped == "Get" then
let key = pop tokensQueueTail in
parseLeafs {
tokensQueue = tail tokensQueueTail,
result = (state.result ++ [Node (Get key)])
}
else
parseLeafs {
tokensQueue = tokensQueueTail,
result = (state.result ++ [Node (Constant popped)])
}
parse tokensQueue =
let popped = pop tokensQueue in
let tokensQueueTail = tail tokensQueue in
if popped == "Perform(" then
Perform (
parseLeafs {
tokensQueue = tokensQueueTail,
result = []
}
).result
else if popped == "Set" then
let key = pop tokensQueueTail in
let value = pop (tail tokensQueueTail) in
Set key value
else if popped == "Print" then
Print (parse tokensQueueTail)
else
Constant popped
In diesem Beitrag beschreibe ich den Algorithmus zum Konvertieren eines RGB-Puffers in Grau (Graustufen). Und das geht ganz einfach: Jeder Pixel-Farbkanal des Puffers wird nach einer bestimmten Formel konvertiert und die Ausgabe ist ein Graubild. Durchschnittsmethode:
red = average;
green = average;
blue = average;
Складываем 3 цветовых канала и делим на 3.
Однако существует еще один метод – метод средневзвешенный, он учитывает цветовосприятие человека:
red = luminance;
green = luminance;
blue = luminance;
Какой метод лучше использовать? Да какой вам больше подходит для конкретной задачи. Далее сравнение методов с помощью тестовой цветовой сетки:
Пример реализации на JavaScript + HTML 5
image,
canvas,
weightedAverage
) {
const context = canvas.getContext('2d');
const imageWeight = image.width;
const imageHeight = image.height;
canvas.width = imageWeight;
canvas.height = imageHeight;
context.drawImage(image, 0, 0);
let pixels = context
.getImageData(
0,
0,
imageWeight,
imageHeight
);
for (let y = 0; y & lt; pixels.height; y++) {
for (let x = 0; x & lt; pixels.width; x++) {
const i = (y * 4) * pixels.width + x * 4;
let red = pixels.data[i];
let green = pixels.data[i + 1];
let blue = pixels.data[i + 2]
const average = (red + green + blue) / 3;
const luminance = 0.2126 * red +
0.7152 * green +
0.0722 * blue;
red = weightedAverage ? luminance : average;
green = weightedAverage ? luminance : average;
blue = weightedAverage ? luminance : average;
pixels.data[i] = red;
pixels.data[i + 1] = green;
pixels.data[i + 2] = blue;
}
}
context
.putImageData(
pixels,
0,
0,
0,
0,
pixels.width,
pixels.height
);
}
Wenn Sie beim Starten von CSGO auf einem MacBook M1 den Fehler SDL_GetDesktopDisplayMode_REAL erhalten, gehen Sie wie unten beschrieben vor. 1. Fügen Sie Steam für CSGO Startoptionen hinzu: -w 1440 -h 900 -fullscreen 2. Starten Sie CSGO über Steam 3. Klicken Sie auf Ignorieren oder Immer ignorieren, um den Fehler SDL_GetDesktopDisplayMode_REAL anzuzeigen4. Viel Spaß
Ich präsentiere Ihnen eine Übersetzung der ersten Seiten von Alan Turings Artikel – „ÜBER BERECHNBAREN ZAHLEN MIT ANWENDUNG AUF DAS AUFLÖSUNGSPROBLEM“ 1936. Die ersten Kapitel enthalten eine Beschreibung von Computern, die später die Grundlage für die moderne Informatik bildeten.
Die vollständige Übersetzung des Artikels und der Erklärung kann im Buch des amerikanischen Popularisierers Charles Petzold mit dem Titel „Reading Turing“ nachgelesen werden. Eine Reise durch Turings wegweisenden Artikel über Berechenbarkeit und Turing-Maschinen. (ISBN 978-5-97060-231-7, 978-0-470-22905-7)
ÜBER BERECHNBARE ZAHLEN MIT ANWENDUNG AUF DAS AUFLÖSUNGSPROBLEM
A. M. TURING
[Eingegangen am 28. Mai 1936 – gelesen am 12. November 1936]
Berechenbare Zahlen können kurz als reelle Zahlen beschrieben werden, deren Ausdrücke als Dezimalbrüche auf endlich viele Arten berechnet werden können. Obwohl dieser Artikel Zahlen auf den ersten Blick als berechenbar behandelt, ist es fast genauso einfach, berechenbare Funktionen einer ganzzahligen Variablen, einer reellen Variablen, einer berechenbaren Variablen, berechenbarer Prädikate und dergleichen zu definieren und zu untersuchen. Die grundlegenden Probleme, die mit diesen berechenbaren Objekten verbunden sind, sind jedoch jeweils dieselben. Für eine detaillierte Betrachtung habe ich berechenbare Zahlen als berechenbares Objekt gewählt, da die Methode, sie zu berücksichtigen, am wenigsten umständlich ist. Ich hoffe, bald die Beziehung zwischen berechenbaren Zahlen und berechenbaren Funktionen usw. beschreiben zu können. Gleichzeitig wird auf dem Gebiet der Theorie der Funktionen einer reellen Variablen, ausgedrückt in berechenbaren Zahlen, geforscht. Nach meiner Definition ist eine reelle Zahl berechenbar, wenn ihre Darstellung als Dezimalbruch von einer Maschine geschrieben werden kann.
In den Absätzen 9 und 10 gebe ich einige Argumente an, um zu zeigen, dass berechenbare Zahlen alle Zahlen umfassen, von denen man natürlich annimmt, dass sie berechenbar sind. Insbesondere zeige ich, dass einige große Zahlenklassen berechenbar sind. Dazu gehören beispielsweise die Realteile aller algebraischen Zahlen, die Realteile der Nullstellen von Bessel-Funktionen, die Zahlen π, e und andere. Allerdings umfassen berechenbare Zahlen nicht alle definierbaren Zahlen, wie das folgende Beispiel einer definierbaren Zahl zeigt, die nicht berechenbar ist.
Obwohl die Klasse der berechenbaren Zahlen sehr groß ist und in vielerlei Hinsicht der Klasse der reellen Zahlen ähnelt, ist sie dennoch aufzählbar. In §8 betrachte ich bestimmte Argumente, die gegenteilig zu sein scheinen. Bei richtiger Anwendung eines dieser Argumente ergeben sich Schlussfolgerungen, die auf den ersten Blick denen von Gödel* ähneln. Diese Ergebnisse haben äußerst wichtige Anwendungsmöglichkeiten. Insbesondere kann, wie unten gezeigt (§11), das Auflösungsproblem nicht gelöst werden.
In seinem jüngsten Artikel führte Alonzo Church** die Idee der „effektiven Berechenbarkeit“ ein, die meiner Vorstellung von „Berechenbarkeit“ entspricht, aber eine völlig andere Definition hat. Zu ähnlichen Schlussfolgerungen kommt auch Church hinsichtlich der Lösungsproblematik. Der Beweis der Äquivalenz von „Berechenbarkeit“ und „Fähigkeit, effektiv gezählt zu werden“ wird im Anhang dieses Artikels vorgelegt.
1. Computer
Wir haben bereits gesagt, dass berechenbare Zahlen diejenigen Zahlen sind, deren Dezimalstellen mit endlichen Mitteln abzählbar sind. Hier ist eine klarere Definition erforderlich. Dieser Artikel wird keinen wirklichen Versuch unternehmen, die hier gegebenen Definitionen zu rechtfertigen, bis wir zu §9 kommen. Vorerst möchte ich nur anmerken, dass der (logische) Grund (dafür) darin besteht, dass das menschliche Gedächtnis zwangsläufig begrenzt ist.
Vergleichen wir eine Person, die gerade eine reelle Zahl berechnet, mit einer Maschine, die nur eine endliche Anzahl von Bedingungen q1, q2, …, qR erfüllen kann; Nennen wir diese Bedingungen „M-Konfigurationen“. Diese (also so definierte) Maschine ist mit einem „Band“ (analog zu Papier) ausgestattet. Dieses durch die Maschine laufende Band ist in Abschnitte unterteilt. Nennen wir sie „Quadrate“. Jedes dieser Quadrate kann eine Art „Symbol“ enthalten. Zu jedem Zeitpunkt gibt es nur ein solches Quadrat, sagen wir das r-te, das das Symbol „in dieser Maschine“ enthält. Nennen wir ein solches Quadrat ein „gescanntes Symbol“. Ein „gescanntes Zeichen“ ist das einzige Zeichen, das der Maschine sozusagen „direkt bekannt“ ist. Durch Ändern seiner M-Konfiguration kann sich die Maschine jedoch effektiv an einige der Zeichen erinnern, die sie zuvor „gesehen“ (gescannt) hat. Das mögliche Verhalten der Maschine zu jedem Zeitpunkt wird durch die m-Konfiguration qn und das gescannte Symbol*** bestimmt. Nennen wir dieses Symbolpaar qn, „Konfiguration“. Die so bezeichnete Konfiguration bestimmt das mögliche Verhalten einer bestimmten Maschine. In einigen dieser Konfigurationen, in denen das gescannte Quadrat leer ist (dh kein Zeichen enthält), schreibt das Gerät ein neues Zeichen auf das gescannte Quadrat und in anderen dieser Konfigurationen löscht es das gescannte Zeichen. Diese Maschine ist auch in der Lage, sich zu bewegen, um ein anderes Quadrat zu scannen, auf diese Weise kann sie sich jedoch nur zu dem benachbarten Quadrat rechts oder links bewegen. Zusätzlich zu diesen Vorgängen kann die M-Konfiguration der Maschine geändert werden. In diesem Fall bilden einige der geschriebenen Zeichen eine Ziffernfolge, die den Dezimalteil der zu berechnenden reellen Zahl darstellt. Der Rest wird nichts weiter als ungenaue Markierungen sein, um „dem Gedächtnis zu helfen“. In diesem Fall können nur die oben genannten ungenauen Markierungen gelöscht werden.
Ich behaupte, dass die hier betrachteten Operationen alle Operationen umfassen, die in der Berechnung verwendet werden. Die Begründung dieser Aussage ist für den Leser, der sich mit der Maschinentheorie auskennt, leichter zu verstehen. Daher werde ich im nächsten Abschnitt die betreffende Theorie weiter entwickeln, basierend auf einem Verständnis der Bedeutung der Begriffe „Maschine“, „Band“, „gescannt“ usw. *Gödel „Über die formal unentscheidbaren Sätze der Principia Mathematics (veröffentlicht von Whitehead und Russell 1910, 1912 und 1913) und verwandte Systeme, Teil I“, Journal of Mathematics. Physik, Monatsheft Nr. 38 (für 1931, S. 173-198. ** Alonzo Church, „An Undecidable Problem in Elementary Number Theory“, American J. of Math., Nr. 58 (1936), S. 345-363. *** Alonzo Church, „A Note on the Problem of Resolution“, J. of Symbolic Logic, Nr. 1 (1936), S. 40-41
Im Jahr 1936 beschrieb der Wissenschaftler Alan Turing in seiner Veröffentlichung „On Computable Numbers, With An Application to Entscheidungsproblem“ den Einsatz einer universellen Rechenmaschine, die dem Problem der Lösbarkeit in der Mathematik ein Ende setzen könnte. Daraus kommt er zu dem Schluss, dass eine solche Maschine nichts richtig lösen könnte, wenn das Ergebnis ihrer Arbeit invertiert und auf sich selbst zurückgeführt würde. Es stellt sich heraus, dass es unmöglich ist, ein *ideales* Antivirenprogramm, einen *idealen* Kachelsetzer, ein Programm, das ideale Phrasen für Ihren Absturz vorschlägt usw. zu erstellen. Paradox!
Diese universelle Rechenmaschine kann jedoch zur Implementierung jedes beliebigen Algorithmus verwendet werden, den sich der britische Geheimdienst zunutze machte, indem er Turing engagierte und die Entwicklung einer „Bombe“-Maschine zur Entschlüsselung deutscher Nachrichten während des Zweiten Weltkriegs ermöglichte.
Das Folgende ist eine OOP-Modellierung eines Einzelbandcomputers in der Dart-Sprache, basierend auf dem Originaldokument.
Eine Turingmaschine besteht aus einem in Abschnitte unterteilten Film, jeder Abschnitt enthält ein Symbol, die Symbole können gelesen oder geschrieben werden. Beispiel einer Filmklasse:
final _map = Map<int, String>();
String read({required int at}) {
return _map[at] ?? "";
}
void write({required String symbol, required int at}) {
_map[at] = symbol;
}
}
Es gibt auch ein „Scan-Quadrat“, es kann sich über den Film bewegen, Informationen lesen oder schreiben, in moderner Sprache – Magnetkopf. Beispiel einer Magnetkopfklasse:
Die Maschine enthält „M-Konfigurationen“, anhand derer sie entscheiden kann, was als nächstes zu tun ist. In moderner Sprache – Staaten und Zustandsverwalter. Beispiel für einen Statushandler:
FiniteStateControlDelegate? delegate = null;
void handle({required String symbol}) {
if (symbol == OPCODE_PRINT) {
final argument = delegate?.nextSymbol();
print(argument);
}
else if (symbol == OPCODE_GENERATE_RANDOM_NUMBER_FROM_ZERO_TO_AND_WRITE_AFTER) {
final to = int.tryParse(delegate!.nextSymbol())!;
final value = new Random().nextInt(to);
delegate!.nextSymbol();
delegate!.write(value.toString());
}
else if (symbol == OPCODE_INPUT_TO_NEXT) {
final input = stdin.readLineSync()!;
delegate?.nextSymbol();
delegate?.write(input);
}
else if (symbol == OPCODE_COPY_FROM_TO) {
final currentIndex = delegate!.index();
и т.д.
Danach müssen Sie „Konfigurationen“ erstellen. In der modernen Sprache sind dies Operationscodes (Opcodes) und ihre Handler. Beispiel-Opcodes:
const OPCODE_PRINT = "print";
const OPCODE_INCREMENT_NEXT = "increment next";
const OPCODE_DECREMENT_NEXT = "decrement next";
const OPCODE_IF_PREVIOUS_NOT_EQUAL = "if previous not equal";
const OPCODE_MOVE_TO_INDEX = "move to index";
const OPCODE_COPY_FROM_TO = "copy from index to index";
const OPCODE_INPUT_TO_NEXT = "input to next";
const OPCODE_GENERATE_RANDOM_NUMBER_FROM_ZERO_TO_AND_WRITE_AFTER = "generate random number from zero to next and write after";
Vergessen Sie nicht, einen Opcode und einen Stop-Handler zu erstellen, sonst können Sie das Auflösungsproblem nicht beweisen oder nicht beweisen (sic!).
Jetzt verbinden wir mithilfe des „Mediator“-Musters alle Klassen in der Turing-Maschine-Klasse, erstellen eine Instanz der Klasse, zeichnen das Programm mit einem Tonbandgerät auf, laden das Band und Sie können es verwenden!
Für mich persönlich blieb die Frage, was primär war, interessant – Schaffung eines Universalrechners bzw. Beweis des „Entscheidungsproblems“, wodurch als Nebenprodukt ein Rechner entstand.
Kassetten
Zum Spaß habe ich mehrere Kassettenprogramme für meine Version der Maschine aufgenommen.
Hallo Welt
hello world
stop
Считаем до 16-ти
0
if previous not equal
16
copy from index to index
1
8
print
?
move to index
0
else
copy from index to index
1
16
print
?
print
Finished!
stop
Самой интересной задачей было написание Quine программы, которая печатает свой исходный код, для одноленточной машины. Первые 8 часов мне казалось что эта задача не решаема с таким малым количеством опкодов, однако всего через 16 часов оказалось что я был не прав.
In dieser Notiz beschreibe ich den Prozess des Lesens des Joysticks, des Änderns der Position des Sprites, des horizontalen Umdrehens, des Sega Genesis-Emulators und möglicherweise der Konsole selbst.
Das Lesen von Klicks und die Verarbeitung von „Ereignissen“ eines Shogi-Joysticks erfolgt nach folgendem Schema:
Anfrage nach einer Kombination von Bits gedrückter Tasten
Teile gedrückter Tasten lesen
Verarbeitung auf der Ebene der Spiellogik
Um das Skelett-Sprite zu verschieben, müssen wir Variablen der aktuellen Position speichern.
RAM
Spiellogikvariablen werden im RAM gespeichert; bisher ist noch nichts Besseres erfunden worden. Lassen Sie uns Variablenadressen deklarieren und den Rendering-Code ändern:
Wie Sie sehen, beginnt die für die Arbeit verfügbare Adresse bei 0xFF0000 und endet bei 0xFFFFFF, insgesamt stehen uns 64 KB Speicher zur Verfügung. Skeleton-Positionen werden bei SkeletonXpos, SkeletonYpos, horizontale Drehung bei SkeletonHorizontalFlip deklariert.
Joypad
In Analogie zu VDP erfolgt die Arbeit mit Joypads über zwei separate Ports – Steuerport und Datenport, für den ersten 0xA10009 und 0xA10003 Co-Nr. Bei der Arbeit mit einem Joypad gibt es eine interessante Funktion: Zuerst müssen Sie eine Tastenkombination für die Abfrage anfordern und dann, nachdem Sie auf ein Update am Bus gewartet haben, die erforderlichen Tastendrücke lesen. Für die C/B- und D-Pad-Tasten ist dies 0x40, Beispiel unten:
move.b #$40,joypad_one_control_port; C/B/Dpad
nop ; bus sync
nop ; bus sync
move.b joypad_one_data_port,d2
rts
Im Register d2 bleibt der Zustand der gedrückten oder nicht gedrückten Tasten erhalten, im Allgemeinen bleibt das, was über den Datumsport angefordert wurde, erhalten. Gehen Sie anschließend zum Motorola 68000-Register-Viewer Ihres Lieblingsemulators und sehen Sie, was das d2-Register je nach Tastenanschlägen entspricht. Auf clevere Weise können Sie es im Handbuch herausfinden, aber wir verlassen uns nicht auf ihr Wort. Weiterverarbeitung gedrückter Tasten im d2
-Register
cmp #$FFFFFF7B,d2; handle left
beq MoveLeft
cmp #$FFFFFF77,d2; handle right
beq MoveRight
cmp #$FFFFFF7E,d2; handle up
beq MoveUp
cmp #$FFFFFF7D,d2; handle down
beq MoveDown
rts
Проверять нужно конечно отдельные биты, а не целыми словами, но пока и так сойдет. Теперь осталось самое простое – написать обработчики всех событий перемещения по 4-м направлениям. Для этого меняем переменные в RAM, и запускаем процедуру перерисовки.
Пример для перемещения влево + изменение горизонтального флипа:
После добавления всех обработчиков и сборки, вы увидите как скелет перемещается и поворачивается по экрану, но слишком быстро, быстрее самого ежа Соника.
Не так быстро!
Чтобы замедлить скорость игрового цикла, существуют несколько техник, я выбрал самую простую и не затрагивающую работу с внешними портами – подсчет цифры через регистр пока она не станет равна нулю.
Danach läuft das Skelett langsamer, was erforderlich war. Wie ich weiß, ist die häufigste Option zum „Verlangsamen“ das Zählen der vertikalen Synchronisierungsflagge. Sie können zählen, wie oft der Bildschirm gezeichnet wurde, und sind somit an eine bestimmte Anzahl an Bildern pro Sekunde gebunden.
In diesem Beitrag beschreibe ich, wie man Sprites mit dem VDP-Emulator der Sega Genesis-Konsole zeichnet. Der Prozess des Renderns von Sprites ist dem Rendern von Kacheln sehr ähnlich:
Mit ImaGenesis konvertieren wir es in CRAM-Farben und VRAM-Muster für Assembler. Danach erhalten wir zwei Dateien im ASM-Format, dann schreiben wir die Farben auf die Wortgröße um und die Kacheln müssen zum Zeichnen in der richtigen Reihenfolge platziert werden. Interessante Informationen: Sie können die automatische VDP-Inkrementierung über das 0xF-Register auf die Wortgröße umstellen. Dadurch wird die Adresserhöhung aus dem CRAM-Farbfüllcode entfernt.
VRAM
Das Shogi-Handbuch enthält die korrekte Reihenfolge der Kacheln für große Sprites, aber wir sind schlauer, also übernehmen wir die Indizes aus dem Blog ChibiAkumas, beginnen wir mit dem Zählen ab Index 0:
0 4 8 12
1 5 9 13
2 6 10 14
3 7 11 15
Warum steht alles auf dem Kopf? Was willst du, die Konsole ist japanisch! Es könnte sogar von rechts nach links sein! Lassen Sie uns die Reihenfolge in der ASM-Sprite-Datei manuell ändern:
Um ein Sprite zu zeichnen, müssen Sie nur noch die Sprite-Tabelle ausfüllen
Sprite-Tabelle
Die Sprite-Tabelle wird im VRAM gefüllt, die Adresse ihres Standorts wird in das VDP-Register 0x05 eingetragen, die Adresse ist wieder knifflig, man kann es im Handbuch sehen, ein Beispiel für Adresse F000:
Ок, теперь запишем наш спрайт в таблицу. Для этого нужно заполнить “структуру” данных состоящую из четырех word. Бинарное описание структуры вы можете найти в мануале. Лично я сделал проще, таблицу спрайтов можно редактировать вручную в эмуляторе Exodus.
Die Strukturparameter sind aus dem Namen ersichtlich, zum Beispiel XPos, YPos – Koordinaten, Kacheln – Nummer der Startkachel zum Zeichnen, HSize, VSize – Sprite-Größen durch Hinzufügen der Teile 8×8, HFlip, VFlip – Hardware-Rotation des Sprites horizontal und vertikal. Es ist sehr wichtig, sich daran zu erinnern, dass Sprites außerhalb des Bildschirms sein können. Dies ist das richtige Verhalten, weil… Off-Screen-Sprites aus dem Speicher entladen – eine ziemlich ressourcenintensive Aktivität. Nachdem die Daten im Emulator eingegeben wurden, müssen sie vom VRAM an die Adresse 0xF000 kopiert werden. Exodus unterstützt diese Funktion ebenfalls. Analog zum Zeichnen von Kacheln greifen wir zunächst auf den VDP-Steuerport zu, um mit dem Schreiben an der Adresse 0xF000 zu beginnen, und schreiben dann die Struktur in den Datenport. Ich möchte Sie daran erinnern, dass die Beschreibung der VRAM-Adressierung im Handbuch oder im Blog Namenloser Algorithmus .
Kurz gesagt funktioniert die VDP-Adressierung folgendermaßen: [..DC BA98 7654 3210 …. …. …. ..FE] Dabei ist Hex die Bitposition in der gewünschten Adresse. Die ersten beiden Bits geben die Art des angeforderten Befehls an, zum Beispiel 01 – in den VRAM schreiben. Für die Adresse 0XF000 ergibt sich dann: 0111 0000 0000 0000 0000 0000 0000 0011 (70000003)
In diesem Beitrag beschreibe ich, wie man mithilfe von Assembler ein Bild aus Kacheln auf dem Sega Genesis-Emulator anzeigt. Das Splash-Bild von Demens Deum im Exodus-Emulator sieht folgendermaßen aus:
Die Ausgabe eines PNG-Bildes mithilfe von Kacheln erfolgt Schritt für Schritt:
Verkleinerung des Bildes auf die Größe des Shogi-Bildschirms
Konvertieren Sie PNG in Assembly-Datencode, getrennt in Farben und Kacheln
Laden einer Farbpalette in CRAM
Laden von Kacheln/Mustern in VRAM
Laden von Kachelindizes an Plane A/B-Adressen im VRAM
Sie können das Bild mit Ihrem bevorzugten Grafikeditor wie Blender auf die Größe des Shogi-Bildschirms verkleinern.
PNG-Konvertierung
Zum Konvertieren von Bildern können Sie das ImaGenesis-Tool verwenden; für die Arbeit unter Wine sind Visual Basic 6-Bibliotheken erforderlich, diese können mit winetricks (winetricks vb6run) installiert werden, oder RICHTX32.OCX kann aus dem Internet heruntergeladen und abgelegt werden für den ordnungsgemäßen Betrieb im Anwendungsordner.< /p>
In ImaGenesis müssen Sie 4-Bit-Farbe auswählen und Farben und Kacheln in zwei Dateien im Assembler-Format exportieren. Als nächstes müssen Sie in der Datei mit den Farben jede Farbe in ein Wort (2 Bytes) einfügen. Dazu verwenden Sie den Opcode dc.w.
Wie Sie dem obigen Beispiel entnehmen können, handelt es sich bei den Kacheln um ein 8×8-Raster, das aus CRAM-Farbpalettenindizes besteht.
Farben im CRAM
Das Laden in den CRAM erfolgt durch Setzen eines Farbladebefehls an eine bestimmte CRAM-Adresse im Steuerport (vdp-Steuerung). Das Befehlsformat ist im Sega Genesis Software Manual (1989) beschrieben. Ich füge nur hinzu, dass Sie nur 0x20000 zur Adresse hinzufügen müssen, um zur nächsten Farbe zu wechseln.
Als nächstes müssen Sie die Farbe in den Datenport (vdp-Daten) laden; Der einfachste Weg, das Laden zu verstehen, ist das folgende Beispiel:
Als nächstes erfolgt das Laden von Kacheln/Mustern in den VRAM-Videospeicher. Wählen Sie dazu eine Adresse im VRAM aus, zum Beispiel 0x00000000. Analog zum CRAM kontaktieren wir den VDP-Steuerport mit einem Befehl zum Schreiben in den VRAM und die Startadresse.
Danach können Sie Langwörter in den VRAM hochladen; im Vergleich zum CRAM müssen Sie nicht für jedes Langwort die Adresse angeben, da es einen VRAM-Auto-Inkrementierungsmodus gibt. Sie können es mit dem VDP-Registerflag 0x0F (dc.b $02)
Jetzt müssen wir den Bildschirm entsprechend ihrem Index mit Kacheln füllen. Dazu wird VRAM an der Plane A/B-Adresse gefüllt, die in den VDP-Registern (0x02, 0x04) eingetragen ist. Weitere Informationen zur kniffligen Adressierung finden Sie im Handbuch von Sega; in meinem Beispiel ist die VRAM-Adresse 0xC000, laden wir die Indizes dort hoch.
Ihr Bild füllt ohnehin den VRAM-Bereich außerhalb des Bildschirms aus. Nach dem Zeichnen des Bildschirmbereichs sollte Ihr Renderer also mit dem Zeichnen aufhören und wieder fortfahren, wenn sich der Cursor in eine neue Zeile bewegt. Es gibt viele Möglichkeiten, dies zu implementieren; ich habe die einfachste Version des Zählens auf zwei Registern des Bildbreitenzählers und des Cursorpositionszählers verwendet.
Codebeispiel:
move.w #0,d0 ; column index
move.w #1,d1 ; tile index
move.l #$40000003,(vdp_control_port) ; initial drawing location
move.l #2500,d7 ; how many tiles to draw (entire screen ~2500)
imageWidth = 31
screenWidth = 64
FillBackgroundStep:
cmp.w #imageWidth,d0
ble.w FillBackgroundStepFill
FillBackgroundStep2:
cmp.w #imageWidth,d0
bgt.w FillBackgroundStepSkip
FillBackgroundStep3:
add #1,d0
cmp.w #screenWidth,d0
bge.w FillBackgroundStepNewRow
FillBackgroundStep4:
dbra d7,FillBackgroundStep ; loop to next tile
Stuck:
nop
jmp Stuck
FillBackgroundStepNewRow:
move.w #0,d0
jmp FillBackgroundStep4
FillBackgroundStepFill:
move.w d1,(vdp_data_port) ; copy the pattern to VPD
add #1,d1
jmp FillBackgroundStep2
FillBackgroundStepSkip:
move.w #0,(vdp_data_port) ; copy the pattern to VPD
jmp FillBackgroundStep3
Danach müssen Sie nur noch das ROM mit Vasm zusammenbauen, den Simulator starten und sich das Bild ansehen.
Debuggen
Es wird nicht alles auf Anhieb klappen, daher möchte ich die folgenden Exodus-Emulator-Tools empfehlen:
M68k-Prozessor-Debugger
Ändern der Anzahl der m68k-Prozessorzyklen (für den Zeitlupenmodus im Debugger)
Zuschauer CRAM, VRAM, Plane A/B
Lesen Sie sorgfältig die Dokumentation für m68k und die verwendeten Opcodes (nicht alles ist so offensichtlich, wie es auf den ersten Blick scheint)
Beispiele für Spielcode/Demontage auf Github ansehen
Unterprogramme von Prozessorausnahmen implementieren und verarbeiten
Zeiger auf Prozessor-Ausnahme-Subroutinen werden im ROM-Header platziert; es gibt auch ein Projekt auf GitHub mit einem interaktiven Laufzeit-Debugger für Sega, genannt genesis-debugger.
Verwenden Sie alle verfügbaren Tools, haben Sie eine nette Codierung der alten Schule und vielleicht ist Blast Processing dabei!
In diesem Beitrag beschreibe ich, wie man Farben in Assemblersprache in die Shogi-Palette lädt. Das Endergebnis im Exodus-Emulator sieht folgendermaßen aus:
Um den Prozess zu vereinfachen, finden Sie im Internet ein PDF mit dem Titel Genesis Software Manual (1989). Es beschreibt den gesamten Prozess sehr detailliert. Tatsächlich handelt es sich bei dieser Notiz um einen Kommentar zum Originalhandbuch.< /p>
Um Farben auf den VDP-Chip des Sega-Emulators zu schreiben, müssen Sie die folgenden Dinge tun:
TMSS-Schutz deaktivieren
Korrekte Parameter in VDP-Register schreiben
Schreiben Sie die gewünschten Farben in CRAM
Für den Zusammenbau verwenden wir vasmm68k_mot und einen bevorzugten Texteditor, zum Beispiel Echo. Der Zusammenbau erfolgt mit dem Befehl:
Порты VDP
VDP чип общается с M68K через два порта в оперативной памяти – порт контроля и порт данных.
По сути:
Через порт контроля можно выставлять значения регистрам VDP.
Также порт контроля является указателем на ту часть VDP (VRAM, CRAM, VSRAM etc.) через которую передаются данные через порт данных
Интересная информация: Сега сохранила совместимость с играми Master System, на что указывает MODE 4 из мануала разработчика, в нем VDP переключается в режим Master System.
Объявим порты контроля и данных:
vdp_data_port = $C00000
Отключить систему защиты TMSS
Защита от нелицензионных игр TMSS имеет несколько вариантов разблокировки, например требуется чтобы до обращения к VDP в адресном регистре A1 лежала строка “SEGA”.
MOVE.B A1,D0; Получаем версию хардвары цифрой из A1 в регистр D0
ANDI.B 0x0F,D0; По маске берем последние биты, чтобы ничего не сломать
BEQ.B SkipTmss; Если версия равна 0, скорее всего это японка или эмулятор без включенного TMSS, тогда идем в сабрутину SkipTmss
MOVE.L "SEGA",A1; Или записываем строку SEGA в A1
Korrekte Parameter in VDP-Register schreiben
Warum überhaupt die richtigen Parameter in den VDP-Registern einstellen? Der Grundgedanke ist, dass VDP viel kann. Sie müssen es also vor dem Rendern mit den erforderlichen Funktionen initialisieren, sonst versteht es einfach nicht, was Sie von ihm erwarten.
Jedes Register ist für eine bestimmte Einstellung/Betriebsart verantwortlich. Das Segov-Handbuch gibt alle Bits/Flags für jedes der 24 Register an, eine Beschreibung der Register selbst.
Nehmen wir vorgefertigte Parameter mit Kommentaren aus dem Bigevilcorporation-Blog:
VDPReg0: dc.b $14 ; 0: H interrupt on, palettes on
VDPReg1: dc.b $74 ; 1: V interrupt on, display on, DMA on, Genesis mode on
VDPReg2: dc.b $30 ; 2: Pattern table for Scroll Plane A at VRAM $C000
; (bits 3-5 = bits 13-15)
VDPReg3: dc.b $00 ; 3: Pattern table for Window Plane at VRAM $0000
; (disabled) (bits 1-5 = bits 11-15)
VDPReg4: dc.b $07 ; 4: Pattern table for Scroll Plane B at VRAM $E000
; (bits 0-2 = bits 11-15)
VDPReg5: dc.b $78 ; 5: Sprite table at VRAM $F000 (bits 0-6 = bits 9-15)
VDPReg6: dc.b $00 ; 6: Unused
VDPReg7: dc.b $00 ; 7: Background colour - bits 0-3 = colour,
; bits 4-5 = palette
VDPReg8: dc.b $00 ; 8: Unused
VDPReg9: dc.b $00 ; 9: Unused
VDPRegA: dc.b $FF ; 10: Frequency of Horiz. interrupt in Rasters
; (number of lines travelled by the beam)
VDPRegB: dc.b $00 ; 11: External interrupts off, V scroll fullscreen,
; H scroll fullscreen
VDPRegC: dc.b $81 ; 12: Shadows and highlights off, interlace off,
; H40 mode (320 x 224 screen res)
VDPRegD: dc.b $3F ; 13: Horiz. scroll table at VRAM $FC00 (bits 0-5)
VDPRegE: dc.b $00 ; 14: Unused
VDPRegF: dc.b $02 ; 15: Autoincrement 2 bytes
VDPReg10: dc.b $01 ; 16: Vert. scroll 32, Horiz. scroll 64
VDPReg11: dc.b $00 ; 17: Window Plane X pos 0 left
; (pos in bits 0-4, left/right in bit 7)
VDPReg12: dc.b $00 ; 18: Window Plane Y pos 0 up
; (pos in bits 0-4, up/down in bit 7)
VDPReg13: dc.b $FF ; 19: DMA length lo byte
VDPReg14: dc.b $FF ; 20: DMA length hi byte
VDPReg15: dc.b $00 ; 21: DMA source address lo byte
VDPReg16: dc.b $00 ; 22: DMA source address mid byte
VDPReg17: dc.b $80 ; 23: DMA source address hi byte,
; memory-to-VRAM mode (bits 6-7)
Ok, jetzt gehen wir zum Steuerport und schreiben alle Flags in die VDP-Register:
move.l #VDPRegisters,a0 ; Пишем адрес таблицы параметров в A1
move.l #$18,d0 ; Счетчик цикла - 24 = 18 (HEX) в D0
move.l #$00008000,d1 ; Готовим команду на запись в регистр VDP по индексу 0, по мануалу - 1000 0000 0000 0000 (BIN) = 8000 (HEX)
FillInitialStateForVDPRegistersLoop:
move.b (a0)+,d1 ; Записываем в D1 итоговое значение регистра VDP из таблицы параметров, на отправку в порт контроля VDP
move.w d1,vdp_control_port ; Отправляем итоговую команду + значение из D1 в порт контроля VDP
add.w #$0100,d1 ; Поднимаем индекс регистра VDP на 1 (бинарное сложение +1 к индексу по мануалу Сеги)
dbra d0,FillInitialStateForVDPRegistersLoop ; Уменьшаем счетчик регистров, продолжаем цикл если необходимо
Самое сложное это прочитать мануал и понять в каком формате подаются данные на порт контроля, опытные разработчики разберутся сразу, а вот неопытные… Немного подумают и поймут, что синтаксис для записи регистров такой:
0B100(5 бит – индекс регистра)(8 бит/байт – значение)
0B1000001001000101 – записать в регистр VDP 2 (00010), значение флажков 01000101.
Записать нужные цвета в CRAM
Далее идем писать два цвета в память цветов CRAM (Color RAM). Для этого пишем в порт контроля команду на доступ к цвету по индексу 0 в CRAM и отправляем по дата порту цвет. Все!
Пример:
move.l #$C0000000,vdp_control_port ; Доступ к цвету по индексу 0 в CRAM через порт контроля
move.w #228,d0; Цвет в D0
move.w d0,vdp_data_port; Отправляем цвет в порт данных
Nachdem Sie den Emulator in Exodus erstellt und ausgeführt haben, sollte Ihr Bildschirm mit der Farbe 228 gefüllt sein.
Füllen wir es mit einer zweiten Farbe, basierend auf dem letzten Byte 127.
move.l #$C07f0000,vdp_control_port ; Доступ к цвету по байту 127 в CRAM через порт контроля
move.w #69,d0; Цвет в D0
move.w d0,vdp_data_port; Отправляем цвет в порт данных
Der erste Artikel über das Schreiben von Spielen für die klassische Sega Genesis-Konsole in Motorola 68000 Assembly.
Lassen Sie uns die einfachste Endlosschleife für Sega schreiben. Dafür benötigen wir: einen Assembler, einen Emulator mit Disassembler, einen bevorzugten Texteditor, ein grundlegendes Verständnis der Struktur von Sega Rum.
Für die Entwicklung verwende ich meinen eigenen Assembler/Disassembler Gen68KryBaby:
Das Tool ist in Python 3 entwickelt, zum Zusammenstellen wird eine Datei mit der Erweiterung .asm oder .gen68KryBabyDisasm als Eingabe bereitgestellt, die Ausgabe ist eine Datei mit der Erweiterung .gen68KryBabyAsm.bin, die im Emulator oder auf ausgeführt werden kann eine echte Konsole (Vorsicht, weggehen, die Konsole könnte explodieren!)
Das Zerlegen von ROMs wird ebenfalls unterstützt. Dazu müssen Sie eine ROM-Datei als Eingabe übermitteln, ohne die Erweiterungen .asm oder .gen68KryBabyDisasm. Die Opcode-Unterstützung wird abhängig von meinem Interesse am Thema und der Beteiligung von Mitwirkenden steigen oder sinken.
Struktur
Der Sega-ROM-Header belegt die ersten 512 Bytes. Es enthält Informationen über das Spiel, den Namen, unterstützte Peripheriegeräte, Prüfsumme und andere Systemflags. Ich gehe davon aus, dass die Konsole ohne Titel nicht einmal auf den Rum schaut und denkt, dass er falsch ist, und sagt: „Was gibst du mir hier?“
Nach dem Header kommt das Unterprogramm/Reset-Unterprogramm, in dem der m68K-Prozessor seine Arbeit beginnt. Okay, es ist eine Kleinigkeit – Opcodes (Operationscodes) finden, nämlich nichts tun (!) und zur Unterroutine an der Adresse im Speicher wechseln. Wenn Sie googeln, können Sie den NOP-Opcode finden, der nichts tut, und den JSR-Opcode, der einen bedingungslosen Sprung zur Argumentadresse ausführt, das heißt, er bewegt den Schlitten einfach ohne irgendwelche Launen dorthin, wo wir ihn fragen.
Alles zusammenfügen
Der Header-Donor für die ROM war eines der Spiele in der Beta-Version, derzeit als Hex-Daten aufgezeichnet.
Код программы со-но представляет из себя объявление сабрутины Reset/EntryPoint в 512 (0x200) байте, NOP, возврат каретки к 0x00000200, таким образом мы получим бесконечный цикл.
Запускаем ром 1infiniteloop.asm.gen68KryBabyAsm.bin в режиме дебаггера эмулятора Exodus/Gens, смотрим что m68K корректно считывает NOP, и бесконечно прыгает к EntryPoint в 0x200 на JSR
Здесь должен быть Соник показывающий V, но он уехал на Вакен.
In dieser Notiz werde ich über die Bedeutung von Architekturentscheidungen bei der Entwicklung, der Unterstützung einer Anwendung und in einer Teamentwicklungsumgebung schreiben.
In meiner Jugend habe ich an einer Taxi-Bestellanwendung gearbeitet. Im Programm können Sie einen Abholpunkt und einen Abgabepunkt auswählen, die Fahrtkosten und die Tarifart berechnen und tatsächlich ein Taxi bestellen. Ich habe die Anwendung in der letzten Phase des Vorabstarts erhalten; nach dem Hinzufügen mehrerer Korrekturen wurde die Anwendung im AppStore veröffentlicht. Bereits zu diesem Zeitpunkt war dem gesamten Team klar, dass die Implementierung sehr schlecht war, keine Entwurfsmuster verwendet wurden, alle Komponenten des Systems eng miteinander verbunden waren und es im Allgemeinen möglich war, es in eine große kontinuierliche Klasse (Gottobjekt) zu schreiben. Es hätte sich nichts geändert, so wie die Klassen ihre Verantwortungsgrenzen durcheinander brachten und sich in ihrer Gesamtmasse in einer toten Kopplung überlappten. Später beschloss das Management, die Anwendung unter Verwendung der richtigen Architektur von Grund auf neu zu schreiben, was auch geschah und das Endprodukt für mehrere Dutzend B2B-Kunden implementiert wurde.
Ich werde jedoch einen merkwürdigen Vorfall aus der Architektur der Vergangenheit beschreiben, von dem ich manchmal mitten in der Nacht schweißgebadet aufwache oder mich mitten am Tag plötzlich daran erinnere und hysterisch zu lachen beginne. Die Sache ist die, dass ich den Kerl an der Stange beim ersten Mal nicht treffen konnte, was den Großteil der Bewerbung zum Scheitern brachte, aber das Wichtigste zuerst.
Es war ein gewöhnlicher Arbeitstag, einer der Kunden erhielt die Aufgabe, das Anwendungsdesign leicht zu verfeinern – Es ist einfach, das Symbol in der Mitte des Auswahlbildschirms für die Abholadresse um ein paar Pixel nach oben zu verschieben. Nun, nachdem ich die Aufgabe professionell auf 10 Minuten geschätzt hatte, hob ich das Symbol um 20 Pixel an, völlig ahnungslos, und beschloss, den Taxiauftrag zu überprüfen.
Was? Die App zeigt den Bestellbutton nicht mehr an? Wie ist das passiert?
Ich traute meinen Augen nicht; nachdem ich das Symbol um 20 Pixel erhöht hatte, zeigte die Anwendung die Schaltfläche „Bestellung fortsetzen“ nicht mehr an. Nachdem ich die Änderung rückgängig gemacht hatte, sah ich die Schaltfläche wieder. Hier stimmte etwas nicht. Nachdem ich 20 Minuten im Debugger verbracht hatte, hatte ich es ein wenig satt, die vielen Aufrufe überlappender Klassen abzuwickeln, aber ich entdeckte, dass *das Verschieben des Bildes die Logik der Anwendung wirklich verändert*
Es drehte sich alles um das Symbol in der Mitte – Ein Mann auf einer Stange, der beim Bewegen der Karte nach oben sprang, um die Bewegung der Kamera zu animieren. Auf diese Animation folgte das Verschwinden des Knopfes unten. Anscheinend ging das Programm davon aus, dass der um 20 Pixel verschobene Mann einen Sprung machte, und versteckte daher gemäß seiner internen Logik die Bestätigungsschaltfläche.
Wie kann das passieren? Hängt der *Zustand* des Bildschirms wirklich nicht vom Muster der Zustandsmaschine ab, sondern von der *Darstellung* der Position des Mannes auf der Stange?
Es stellte sich heraus, dass jedes Mal, wenn die Karte gezeichnet wurde, die Anwendung *visuell* in die Mitte des Bildschirms gestochen und überprüft, was dort war. Wenn sich ein Mann auf einer Stange befindet, bedeutet dies, dass die Kartenverschiebungsanimation beendet ist und angezeigt werden muss Taste. Wenn der Mann nicht da ist, wird die Karte verschoben und die Schaltfläche muss ausgeblendet werden.
Im obigen Beispiel ist alles in Ordnung, erstens ist es ein Beispiel für Goldberg-Maschinen (abstruse Maschinen), zweitens ein Beispiel für die Zurückhaltung des Entwicklers, irgendwie mit anderen Entwicklern im Team zu interagieren (versuchen Sie, es ohne herauszufinden). Drittens können Sie alle Probleme nach SOLID, Mustern (Code-Smells), MVC-Verletzungen und vielem mehr auflisten.
Versuchen Sie, dies nicht zu tun, entwickeln Sie sich in alle möglichen Richtungen und helfen Sie Ihren Kollegen bei ihrer Arbeit. Frohes neues Jahr euch allen.
In diesem Beitrag beschreibe ich die Arbeit mit dem Fasttext-Textklassifikator.
Fasttext – Bibliothek für maschinelles Lernen zur Textklassifizierung. Versuchen wir ihr beizubringen, eine Metal-Band anhand des Songtitels zu identifizieren. Dazu nutzen wir überwachtes Lernen anhand eines Datensatzes.
Lassen Sie uns einen Datensatz von Liedern mit Gruppennamen erstellen:
В результате мы получим список классов на которые похож данный пример, с указанием уровня похожести цифрой, в нашем случае похожесть названия песни Bleed на одну из групп датасета.
Для того чтобы модель fasttext умела работать с датасетом выходящим за границы обучающей выборки, используют режим autotune с использованием файла валидации (файл тест). Во время автотюна fasttext подбирает оптимальные гиперпараметры модели, проводя валидацию результата на выборке из тест файла. Время автотюна ограничивается пользователем в самостоятельно, с помощью передачи аргумента autotuneDuration.
Пример создания модели с использованием файла тест:
In dieser Notiz beschreibe ich den Prozess des Aufrufs von C-Funktionen aus dem Assembler. Versuchen wir, printf(“Hello World!\n”); aufzurufen. und Exit(0);
message: db "Hello, world!", 10, 0
section .text
extern printf
extern exit
global main
main:
xor rax, rax
mov rdi, message
call printf
xor rdi, rdi
call exit
Alles ist viel einfacher als es scheint. Im Abschnitt .rodata beschreiben wir statische Daten, in diesem Fall die Zeile „Hallo Welt!“, 10 ist ein Zeilenumbruchzeichen und wir vergessen auch nicht, es auf Null zu setzen.
Im Codeabschnitt deklarieren wir die externen Funktionen printf, Exit der stdio- und stdlib-Bibliotheken und deklarieren auch die Eingabefunktion main:
extern printf
extern exit
global main
Wir übergeben 0 von der Rax-Funktion an das Rückgaberegister. Sie können mov rax, 0; aber um es zu beschleunigen, benutzen sie xor rax, rax; Als nächstes übergeben wir einen Zeiger auf die Zeichenfolge an das erste Argument:
In diesem Beitrag beschreibe ich den Prozess der Einrichtung der IDE und schreibe den ersten Hello World in x86_64-Assembler für das Ubuntu-Linux-Betriebssystem. Beginnen wir mit der Installation der SASM-IDE, Nasm-Assembler:
Hello World-Code aus dem Blog James Fisher, angepasst für Assemblierung und Debugging in SASM. In der SASM-Dokumentation heißt es, dass der Einstiegspunkt eine Funktion namens „main“ sein muss, da sonst das Debuggen und Kompilieren des Codes fehlerhaft ist. Was haben wir in diesem Code gemacht? Habe einen Systemaufruf getätigt – Zugriff auf den Kernel des Linux-Betriebssystems mit korrekten Argumenten in Registern, einem Zeiger auf eine Zeichenfolge im Datenabschnitt.
Unter der Lupe
Sehen wir uns den Code genauer an:
global – директива ассемблера позволяющая задавать глобальные символы со строковыми именами. Хорошая аналогия – интерфейсы заголовочных файлов языков C/C++. В данном случае мы задаем символ main для функции входа.
section – директива ассемблера позволяющая задавать секции (сегменты) кода. Директивы section или segment равнозначны. В секции .text помещается код программы.
Обьявляем начало функции main. В ассемблере функции называются подпрограммами (subroutine)
Первая машинная команда mov – помещает значение из аргумента 1 в аргумент 2. В данном случае мы переносим значение регистра rbp в rsp. Из комментария можно понять что эту строку добавил SASM для упрощения отладки. Видимо это личные дела между SASM и дебаггером gdb.
Далее посмотрим на код до сегмента данных .rodata, два вызова syscall, первый выводит строку Hello World, второй обеспечивает выход из приложения с корректным кодом 0.
Представим себе что регистры это переменные с именами rax, rdi, rsi, rdx, r10, r8, r9. По аналогии с высокоуровневыми языками, перевернем вертикальное представление ассемблера в горизонтальное, тогда вызов syscall будет выглядеть так:
Тогда вызов печати текста:
Вызов exit с корректным кодом 0:
Рассмотрим аргументы подробнее, в заголовочном файле asm/unistd_64.h находим номер функции __NR_write – 1, далее в документации смотрим аргументы для write:
ssize_t write(int fd, const void *buf, size_t count);
Первый аргумент – файловый дескриптор, второй – буфер с данными, третий – счетчик байт для записи в дескриптор. Ищем номер файлового дескриптора для стандартного вывода, в мануале по stdout находим код 1. Далее дело за малым, передать указатель на буфер строки Hello World из секции данных .rodata – msg, счетчик байт – msglen, передать в регистры rax, rdi, rsi, rdx корректные аргументы и вызвать syscall.
Обозначение константных строк и длины описывается в мануале nasm:
Mit der Hash-Tabelle können Sie eine assoziative Array-Datenstruktur (Wörterbuch) mit einer durchschnittlichen Leistung von O(1) für Einfüge-, Lösch- und Suchvorgänge implementieren.
Unten finden Sie ein Beispiel für die einfachste Implementierung einer Hash-Map in nodeJS:
Wie funktioniert es? Passen Sie auf Ihre Hände auf:
Innerhalb der Hash-Map befindet sich ein Array
Im Array-Element befindet sich ein Zeiger auf den ersten Knoten der verknüpften Liste
Speicher wird für ein Array von Zeigern zugewiesen (z. B. 65535 Elemente)
Sie implementieren eine Hash-Funktion, der Wörterbuchschlüssel ist die Eingabe, und am Ausgang kann sie alles tun, aber am Ende gibt sie den Index des Array-Elements zurück
So funktioniert die Aufnahme:
Am Eingang liegt ein Schlüsselpaar – Wert
Hash-Funktion gibt Index nach Schlüssel zurück
Einen verknüpften Listenknoten aus einem Array nach Index abrufen
Überprüfen Sie, ob es mit dem Schlüssel übereinstimmt
Wenn es übereinstimmt, ersetzen Sie den Wert
Wenn es nicht übereinstimmt, fahren Sie mit dem nächsten Knoten fort, bis wir einen Knoten mit dem erforderlichen Schlüssel finden oder finden.
Wenn der Knoten immer noch nicht gefunden wird, erstellen Sie ihn am Ende der verknüpften Liste
So funktioniert die Suche nach Schlüssel:
Am Eingang liegt ein Schlüsselpaar – Wert
Hash-Funktion gibt Index nach Schlüssel zurück
Einen verknüpften Listenknoten aus einem Array nach Index abrufen
Überprüfen Sie, ob es mit dem Schlüssel übereinstimmt
Wenn es übereinstimmt, wird der Wert zurückgegeben
Wenn es nicht übereinstimmt, fahren Sie mit dem nächsten Knoten fort, bis wir einen Knoten mit dem erforderlichen Schlüssel finden oder finden.
Warum brauchen wir eine verknüpfte Liste innerhalb eines Arrays? Aufgrund möglicher Kollisionen bei der Berechnung der Hash-Funktion. In diesem Fall befinden sich mehrere verschiedene Schlüssel-Wert-Paare am selben Index im Array. In diesem Fall wird die verknüpfte Liste durchlaufen, um den erforderlichen Schlüssel zu finden.
Um mit Ressourcen in Android über ndk zu arbeiten – C++ gibt es mehrere Möglichkeiten:
Verwenden Sie den Zugriff auf Ressourcen aus einer APK-Datei mit AssetManager
Laden Sie Ressourcen aus dem Internet herunter, entpacken Sie sie in das Anwendungsverzeichnis und verwenden Sie sie mit Standard-C++-Methoden
Kombinierte Methode – Greifen Sie über AssetManager auf das Archiv mit Ressourcen in der APK zu, entpacken Sie sie in das Anwendungsverzeichnis und verwenden Sie sie dann mit Standard-C++-Methoden
Als nächstes werde ich die kombinierte Zugriffsmethode beschreiben, die in der Flame Steel Engine-Spiel-Engine verwendet wird. Wenn Sie SDL verwenden, können Sie den Zugriff auf Ressourcen von einer APK aus vereinfachen. Die Bibliothek umschließt Aufrufe an AssetManager und bietet Schnittstellen ähnlich wie stdio (fopen, fread, fclose usw.).
Nachdem Sie das Archiv von der APK in den Puffer heruntergeladen haben, müssen Sie das aktuelle Arbeitsverzeichnis in das Anwendungsverzeichnis ändern. Es steht der Anwendung zur Verfügung, ohne dass zusätzliche Berechtigungen eingeholt werden müssen. Dazu verwenden wir einen SDL-Wrapper:
chdir(SDL_AndroidGetInternalStoragePath());
Als nächstes schreiben Sie das Archiv mit fopen, fwrite, fclose aus dem Puffer in das aktuelle Arbeitsverzeichnis. Sobald sich das Archiv in einem für C++ zugänglichen Verzeichnis befindet, entpacken Sie es. Zip-Archive können mit einer Kombination aus zwei Bibliotheken entpackt werden – minizip und zlib, das erste kann mit der Struktur von Archiven arbeiten, während das zweite Daten entpackt. Um mehr Kontrolle zu erlangen und die Portierung zu vereinfachen, habe ich mein eigenes Archivformat ohne Komprimierung namens FSCest (Flame Steel Chest) implementiert. Dieses Format unterstützt das Archivieren eines Verzeichnisses mit Dateien und das Entpacken; Es gibt keine Unterstützung für die Ordnerhierarchie; Sie können nur mit Dateien arbeiten. Wir verbinden den Header der FSCest-Bibliothek, entpacken das Archiv:
Nach dem Entpacken haben die C/C++-Schnittstellen Zugriff auf die Dateien aus dem Archiv. Daher musste ich nicht die gesamte Arbeit mit Dateien in der Engine neu schreiben, sondern fügte nur das Entpacken von Dateien in der Startphase hinzu.
Angenommen, wir müssen einen einfachen Bytecode-Interpreter implementieren. Welchen Ansatz zur Implementierung dieser Aufgabe sollten wir wählen?
Datenstruktur Der Stack bietet die Möglichkeit, eine einfache Bytecode-Maschine zu implementieren. Funktionen und Implementierungen von Stack-Maschinen werden in vielen Artikeln im westlichen und inländischen Internet beschrieben; ich möchte nur erwähnen, dass die Java Virtual Machine ein Beispiel für eine Stack-Maschine ist.
Das Funktionsprinzip der Maschine ist einfach: Ein Programm mit Daten und Operationscodes (Opcodes) wird dem Eingang zugeführt und die erforderlichen Operationen werden durch Manipulationen am Stapel implementiert. Schauen wir uns ein Beispiel-Bytecode-Programm von meiner Stack-Maschine an:
пMVkcatS olleHП
Am Ausgang erhalten wir die Zeichenfolge „Hello StackVM“. Die Stapelmaschine liest das Programm von links nach rechts und lädt Daten Zeichen für Zeichen auf den Stapel, wenn ein Opcode im Symbol – implementiert den Befehl mithilfe des Stapels.
Beispiel für die Implementierung einer Stack-Maschine in nodejs:
Umgekehrte polnische Notation (RPN)
Stack -Maschinen sind auch einfach zum Implementieren von Taschenrechnern zu verwenden. Dafür verwenden sie umgekehrte polnische Notation (Postfix -Notation). Beispiel einer regulären Infix-Notation: 2*2+3*4
Konvertiert in RPN: 22*34*+
Um den Postfix-Datensatz zu zählen, verwenden wir eine Stapelmaschine: 2– an die Spitze des Stapels (Stapel: 2) 2– an die Spitze des Stapels (Stapel: 2,2) *– Holen Sie sich zweimal die Oberseite des Stapels, multiplizieren Sie das Ergebnis und senden Sie es an die Oberseite des Stapels (Stapel: 4) 3– an die Spitze des Stapels (Stapel: 4, 3) 4– an die Spitze des Stapels (Stapel: 4, 3, 4) *– Holen Sie sich zweimal die Oberseite des Stapels, multiplizieren Sie das Ergebnis und senden Sie es an die Oberseite des Stapels (Stapel: 4, 12) +– Holen Sie sich zweimal die Spitze des Stapels, addieren Sie das Ergebnis und senden Sie es an die Spitze des Stapels (Stapel: 16)
Wie Sie sehen können – Das Ergebnis der Operationen 16 verbleibt auf dem Stapel. Es kann durch Implementierung von Stapeldruck-Opcodes gedruckt werden, zum Beispiel: p22*34*+P
P – Stapeldruck-Start-Opcode, p – Opcode zum Fertigstellen des Stapeldrucks und zum Senden der letzten Zeile zum Rendern. Um arithmetische Operationen von Infix in Postfix umzuwandeln, wird der Algorithmus „Sorting Yard“ von Edsger Dijkstra verwendet. Ein Beispiel für die Implementierung finden Sie oben oder im Repository des NodeJS-Maschinenstack-Projekts unten.
Ich beschreibe weiterhin den Skelettanimationsalgorithmus, wie er in der Flame Steel Engine implementiert ist.
Da der Algorithmus der komplexeste von allen ist, die ich implementiert habe, können in den Notizen zum Entwicklungsprozess Fehler auftreten. Im vorherigen Artikel über diesen Algorithmus habe ich einen Fehler gemacht; das Array von Knochen wird für jedes Netz separat und nicht für das gesamte Modell an den Shader übertragen.
Knotenhierarchie
Damit der Algorithmus korrekt funktioniert, ist es notwendig, dass das Modell eine Verbindung zwischen den Knochen untereinander enthält (Grafik). Stellen wir uns eine Situation vor, in der zwei Animationen gleichzeitig abgespielt werden – Springe und hebe deine rechte Hand. Die Sprunganimation muss das Modell entlang der Y-Achse anheben, während die Animation zum Anheben des Arms dies berücksichtigen und beim Springen mit dem Modell ansteigen muss, sonst bleibt der Arm von selbst an Ort und Stelle.
Wir werden die Verbindung von Knoten für diesen Fall beschreiben – Der Körper enthält die Hand. Bei der Ausarbeitung des Algorithmus wird der Knochengraph ausgelesen, alle Animationen werden mit den richtigen Verbindungen berücksichtigt. Im Speicher des Modells wird das Diagramm getrennt von allen Animationen gespeichert, nur um die Konnektivität der Knochen des Modells widerzuspiegeln.
Interpolation auf der CPU
Im letzten Artikel habe ich das Prinzip des Renderns von Skelettanimationen beschrieben – „Transformationsmatrizen werden bei jedem Rendering-Frame von der CPU an den Shader übertragen.“
Jeder Rendering-Frame wird auf der CPU verarbeitet; für jeden Mesh-Bone erhält die Engine die endgültige Transformationsmatrix mithilfe von Positionsinterpolation, Drehung und Zoom. Während der Interpolation der endgültigen Knochenmatrix wird für alle aktiven Knotenanimationen ein Durchlauf durch den Knotenbaum durchgeführt, die endgültige Matrix wird mit den übergeordneten Matrix multipliziert und dann zum Rendern an den Vertex-Shader gesendet.
Vektoren werden zur Positionsinterpolation und Vergrößerung verwendet; Quaternionen werden zur Rotation verwendet, weil Sie sind im Gegensatz zu Euler-Winkeln sehr einfach zu interpolieren (SLERP) und auch sehr einfach als Transformationsmatrix darzustellen.
So vereinfachen Sie die Implementierung
Um das Debuggen des Vertex-Shaders zu vereinfachen, habe ich mithilfe des Makros FSGLOGLNEWAGERENDERER_CPU_BASED_VERTEX_MODS_ENABLED eine Simulation des Vertex-Shaders auf der CPU hinzugefügt. Der Grafikkartenhersteller NVIDIA verfügt über ein Dienstprogramm zum Debuggen von Shader-Code, Nsight. Vielleicht kann es auch die Entwicklung komplexer Vertex-/Pixel-Shader-Algorithmen vereinfachen, aber ich konnte seine Funktionalität nie ausreichend auf der CPU testen.
Im nächsten Artikel möchte ich das Mischen mehrerer Animationen beschreiben und die verbleibenden Lücken schließen.
In diesem Beitrag beschreibe ich eine Möglichkeit, mithilfe der Tiny-JS-Bibliothek Unterstützung für JavaScript-Skripte zu einer C++-Anwendung hinzuzufügen.
Tiny-JS ist eine Bibliothek zum Einbetten in C++, die die Ausführung von JavaScript-Code ermöglicht und Bindungen unterstützt (die Möglichkeit, C++-Code aus Skripten aufzurufen)
Zuerst wollte ich die beliebten Bibliotheken ChaiScript, Duktape oder Connect Lua verwenden, aber aufgrund von Abhängigkeiten und möglichen Schwierigkeiten bei der Portabilität auf verschiedene Plattformen entschied ich mich, eine einfache, minimale, aber leistungsstarke MIT Tiny-Bibliothek zu finden; JS erfüllt diese Kriterien. Der einzige Nachteil dieser Bibliothek ist die fehlende Unterstützung/Entwicklung durch den Autor, ihr Code ist jedoch recht einfach, sodass Sie bei Bedarf die Unterstützung übernehmen können.
In diesem Beitrag beschreibe ich das Verfahren zum Erstellen einer C++-SDL-Anwendung für iOS unter Linux, zum Signieren eines IPA-Archivs ohne kostenpflichtiges Apple Developer-Abonnement und zum Installieren auf einem sauberen Gerät (iPad) mit macOS ohne Jailbreak.< /p>
Im Moment müssen Sie Xcode dmg herunterladen und das SDK von dort kopieren, um den cctools-Port zu erstellen. Dieser Schritt ist unter macOS einfacher durchzuführen; kopieren Sie einfach die erforderlichen SDK-Dateien aus dem installierten Xcode. Nach erfolgreicher Assemblierung enthält das Terminal den Pfad zur Cross-Compiler-Toolchain.
Als nächstes können Sie mit der Erstellung der SDL-Anwendung für iOS beginnen. Öffnen wir cmake und fügen die notwendigen Änderungen hinzu, um den C++-Code zu erstellen:
In meinem Fall werden die Bibliotheken SDL, SDL_Image und SDL_mixer vorab in Xcode unter macOS für die statische Verknüpfung kompiliert; Von Xcode kopierte Frameworks. Außerdem wurde die Bibliothek libclang_rt.ios.a hinzugefügt, die iOS-spezifische Laufzeitaufrufe enthält, beispielsweise isOSVersionAtLeast. Für die Arbeit mit OpenGL ES ist ein Makro enthalten, das ähnlich wie bei Android nicht unterstützte Funktionen in der mobilen Version deaktiviert.
Nachdem Sie alle Build-Probleme gelöst haben, sollten Sie die zusammengestellte Binärdatei für arm erhalten. Betrachten wir als Nächstes die Ausführung der zusammengestellten Binärdatei auf einem Gerät ohne Jailbreak.
Installieren Sie unter macOS Xcode, registrieren Sie sich im Apple-Portal, ohne für das Entwicklerprogramm zu bezahlen. Fügen Sie ein Konto in Xcode hinzu -> Einstellungen -> Konten, erstellen Sie eine leere Anwendung und bauen Sie auf einem echten Gerät auf. Während der Montage wird das Gerät dem kostenlosen Entwicklerkonto hinzugefügt. Nach der Zusammenstellung und dem Start müssen Sie das Archiv erstellen. Wählen Sie dazu „Generisches iOS-Gerät und -Produkt“ aus. Archiv. Sobald das Archiv erstellt ist, extrahieren Sie die Dateien „embedded.mobileprovision“ und „PkgInfo“ daraus. Suchen Sie im Build-Protokoll auf dem Gerät die Codesign-Zeile mit dem richtigen Signaturschlüssel und den Pfad zur Berechtigungsdatei mit der Erweiterung app.xcent und kopieren Sie sie.
Kopieren Sie den .app-Ordner aus dem Archiv, ersetzen Sie die Binärdatei im Archiv durch eine, die von einem Cross-Compiler unter Linux kompiliert wurde (z. B. SpaceJaguar.app/SpaceJaguar), fügen Sie dann die erforderlichen Ressourcen zur .app hinzu und überprüfen Sie die Integrität der Dateien „PkgInfo“ und „embedded.mobileprovision“ in der .app aus dem Archiv, ggf. erneut kopieren. Wir signieren die .app erneut mit dem Codesign-Befehl – Codesign erfordert einen Eingabeschlüssel für sign, den Pfad zur Berechtigungsdatei (kann mit der Erweiterung .plist umbenannt werden)
Erstellen Sie nach dem erneuten Signieren einen Payload-Ordner, verschieben Sie den Ordner mit der Erweiterung .app dorthin, erstellen Sie ein Zip-Archiv mit Payload im Stammverzeichnis und benennen Sie das Archiv mit der Erweiterung .ipa um. Öffnen Sie anschließend in Xcode die Geräteliste und ziehen Sie das neue ipa per Drag & Drop in die Anwendungsliste des Geräts. Die Installation über Apple Configurator 2 funktioniert bei dieser Methode nicht. Wenn die Neusignierung korrekt durchgeführt wurde, wird die Anwendung mit der neuen Binärdatei auf einem iOS-Gerät (z. B. iPad) mit einem 7-Tage-Zertifikat installiert, das reicht für den Testzeitraum.
We use cookies on our website. By clicking “Accept”, you consent to the use of ALL the cookies. Мы используем куки на сайте. Нажимая "ПРИНЯТЬ" вы соглашаетесь с этим.
This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
.gif)
