Угадай группу

В данной заметке я опишу работу с текстовым классификатором fasttext.

Fasttext – библиотека машинного обучения для классификации текстов. Попробуем научить ее определять метал группу по названию песни. Для этого используем обучение с учителем при помощи датасета.

Создадим датасет песен с названиями групп:

__label__metallica the house jack built
__label__metallica fuel
__label__metallica escape
__label__black_sabbath gypsy
__label__black_sabbath snowblind
__label__black_sabbath am i going insane
__label__anthrax anthrax
__label__anthrax i'm alive
__label__anthrax antisocial
[и т.д.]

Формат обучающей выборки:

{__label__класс} {пример из класса}

Обучим fasttext и сохраним модель:

model = fasttext.train_supervised("train.txt")
model.save_model("model.bin")

Загрузим обученную модель и попросим определить группу по названию песни:

model = fasttext.load_model("model.bin")
predictResult = model.predict("Bleed")
print(predictResult)

В результате мы получим список классов на которые похож данный пример, с указанием уровня похожести цифрой, в нашем случае похожесть названия песни Bleed на одну из групп датасета.
Для того чтобы модель fasttext умела работать с датасетом выходящим за границы обучающей выборки, используют режим autotune с использованием файла валидации (файл тест). Во время автотюна fasttext подбирает оптимальные гиперпараметры модели, проводя валидацию результата на выборке из тест файла. Время автотюна ограничивается пользователем в самостоятельно, с помощью передачи аргумента autotuneDuration.
Пример создания модели с использованием файла тест:

model = fasttext.train_supervised("train.txt", autotuneValidationFile="test.txt", autotuneDuration=10000)

Источники

https://fasttext.cc
https://gosha20777.github.io/tutorial/2018/04/12/fasttext-for-windows

Исходный код

https://gitlab.com/demensdeum/MachineLearning/-/tree/master/6bandClassifier

0

x86_64 Assembler + C = One Love

В данной заметке я опишу процесс вызова функций Си из ассемблера.
Попробуем вызвать printf(“Hello World!\n”); и exit(0);

section .rodata
    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

Все гораздо проще чем кажется, в секции .rodata мы опишем статичные данные, в данном случае строку “Hello, world!”, 10 это символ новой строки, также не забудем занулить ее.

В секции кода объявим внешние функции printf, exit библиотек stdio, stdlib, также объявим функцию входа main:

section .text
    extern printf
    extern exit
    global main

В регистр возврата из функции rax передаем 0, можно использовать mov rax, 0; но для ускорения используют xor rax, rax; Далее в первый аргумент передаем указатель на строку:

rdi, message

Далее вызываем внешнюю функцию Си printf:

main:
    xor	rax, rax
    mov	rdi, message    
    call printf
    xor rdi, rdi
    call exit

По аналогии делаем передачу 0 в первый аргумент и вызов exit:

    xor rdi, rdi
    call exit

Как говорят американцы:
Кто никого не слушает
Тот плов кушает @ Александр Пелевин

Источники

https://www.devdungeon.com/content/how-mix-c-and-assembly
https://nekosecurity.com/x86-64-assembly/part-3-nasm-anatomy-syscall-passing-argument
https://www.cs.uaf.edu/2017/fall/cs301/reference/x86_64.html

Исходный код

https://gitlab.com/demensdeum/assembly-playground

0

Hello World x86_64 ассемблер

В данной заметке я опишу процесс настройки IDE, написание первого Hello World на ассемблере x86_64 для операционной системы Ubuntu Linux.
Начнем с установки IDE SASM, ассемблера nasm:

sudo apt install sasm nasm

Далее запустим SASM и напишем Hello World:

global main

section .text

main:
    mov rbp, rsp      ; for correct debugging
    mov rax, 1        ; write(
    mov rdi, 1        ;   STDOUT_FILENO,
    mov rsi, msg      ;   "Hello, world!\n",
    mov rdx, msglen   ;   sizeof("Hello, world!\n")
    syscall           ; );

    mov rax, 60       ; exit(
    mov rdi, 0        ;   EXIT_SUCCESS
    syscall           ; );

section .rodata
    msg: db "Hello, world!"
    msglen: equ $-msg

Код Hello World взят из блога Джеймса Фишера, адаптирован для сборки и отладки в SASM. В документации SASM указано что точкой входа должна быть функция с именем main, иначе отладка и компиляция кода будет некорректной.
Что мы сделали в данном коде? Произвели вызов syscall – обращение к ядру операционной системы Linux с корректными аргументами в регистрах, указателем на строку в секции данных.

Под лупой

Рассмотрим код подробнее:

global main

global – директива ассемблера позволяющая задавать глобальные символы со строковыми именами. Хорошая аналогия – интерфейсы заголовочных файлов языков C/C++. В данном случае мы задаем символ main для функции входа.

section .text

section – директива ассемблера позволяющая задавать секции (сегменты) кода. Директивы section или segment равнозначны. В секции .text помещается код программы.

main:

Обьявляем начало функции main. В ассемблере функции называются подпрограммами (subroutine)

mov rbp, rsp

Первая машинная команда mov – помещает значение из аргумента 1 в аргумент 2. В данном случае мы переносим значение регистра rbp в rsp. Из комментария можно понять что эту строку добавил SASM для упрощения отладки. Видимо это личные дела между SASM и дебаггером gdb.

Далее посмотрим на код до сегмента данных .rodata, два вызова syscall, первый выводит строку Hello World, второй обеспечивает выход из приложения с корректным кодом 0.

Представим себе что регистры это переменные с именами rax, rdi, rsi, rdx, r10, r8, r9. По аналогии с высокоуровневыми языками, перевернем вертикальное представление ассемблера в горизонтальное, тогда вызов syscall будет выглядеть так:

syscall(rax, rdi, rsi, rdx, r10, r8, r9)

Тогда вызов печати текста:

syscall(1, 1, msg, msglen)

Вызов exit с корректным кодом 0:

syscall(60, 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:

message db 'hello, world'
msglen equ $-message

Достаточно просто да?

Источники

https://github.com/Dman95/SASM
https://www.nasm.us/xdoc/2.15.05/html/nasmdoc0.html
http://acm.mipt.ru/twiki/bin/view/Asm/HelloNasm
https://jameshfisher.com/2018/03/10/linux-assembly-hello-world/
http://www.ece.uah.edu/~milenka/cpe323-10S/labs/lab3.pdf
https://c9x.me/x86/html/file_module_x86_id_176.html
https://www.recurse.com/blog/7-understanding-c-by-learning-assembly
https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%BB%D0%BE%D0%B3_%D0%BF%D1%80%D0%BE%D1%86%D0%B5%D0%B4%D1%83%D1%80%D1%8B
https://www.tutorialspoint.com/assembly_programming/assembly_basic_syntax.html
https://nekosecurity.com/x86-64-assembly/part-3-nasm-anatomy-syscall-passing-argument
https://man7.org/linux/man-pages/man2/syscall.2.html
https://en.wikipedia.org/wiki/Write_(system_call)

Исходный код

https://gitlab.com/demensdeum/assembly-playground

0

Характеристики в Space Jaguar Action RPG

Первая статья про игру в разработке Space Jaguar Action RPG. В данной статье я опишу гемплейную особенность Ягуара – Характеристики.

Многие РПГ используют статичную систему характеристик персонажа, например характеристики из DnD (Сила, Телосложение, Ловкость, Интеллект, Мудрость, Обаяние), или Fallout – S.P.E.C.I.A.L (Сила, Восприятие, Выносливость, Харизма, Интеллект, Ловкость, Удача).

В Space Jaguar я планирую реализовать динамическую систему характеристик, например главный герой игры Джаг на старте имеет всего три характеристики – Владение блейдом (полусабля), теневые операции (заключение сделок в криминальном мире), плутовские способности (взлом замков, воровство). Во время игры персонажи будут наделяться и лишаться динамических характеристик в рамках игрового модуля, все проверки будут производится на основе уровня определенных характеристик необходимых для данной игровой ситуации. Например Джаг не сможет выиграть партию в шахматы, если не обладает характеристикой игры в шахматы, или не обладает достаточным уровнем для прохождения проверки.

Для упрощения логики проверок, каждой характеристике задается 6 значный код английскими буквами, имя, описание. Например для владения блейдом:

var bladeFightingAbility = new Object(); 
bladeFightingAbility.name = "BLADFG"; 
bladeFightingAbility.description = "Blade fighting ability"; 
bladeFightingAbility.points = 3;

Перед стартом игрового модуля можно будет просмотреть список публичных проверок необходимых для прохождения, также создатель может скрыть часть проверок для создания интересных игровых ситуаций.

Ноу-хау? Будет ли интересно? Лично я нахожу такую систему интересной, позволяющей одновременно обеспечить свободу творчества создателям игровых модулей, и возможность переноса персонажей из разных, но похожих по характеристикам, модулей для игроков.

0

Хеш таблица

Хеш таблица позволяет реализовать структуру данных ассоциативный массив (словарь), со средней производительностью O(1) для операций вставки, удаления, поиска.

Ниже пример простейшей реализации хэш мапы на nodeJS:

Как это работает? Следим за руками:

  • Внутри хеш мапы находится массив
  • Внутри элемента массива находится указатель на первую ноду связанного списка
  • Размечается память для массива указателей (например 65535 элементов)
  • Реализуют хеш функцию, на вход идет ключ словаря, а на выходе она может делать что угодно, но в итоге возвращает индекс элемента массива

Как работает запись:

  • На вход идет пара ключ – значение
  • Хэш функция возвращает индекс по ключу
  • Получаем ноду связанного списка из массива по индексу
  • Проверяем соответствует ли он ключу
  • Если соответствует, то заменяем значение
  • Если не соответствует, то переходим к следующей ноде, пока найдем либо, не найдем ноду с нужным ключом.
  • Если ноду так и не нашли, то создаем ее в конце связанного списка

Как работает поиск по ключу:

  • На вход идет пара ключ – значение
  • Хэш функция возвращает индекс по ключу
  • Получаем ноду связанного списка из массива по индексу
  • Проверяем соответствует ли он ключу
  • Если соответствует, то возвращаем значение
  • Если не соответствует, то переходим к следующей ноде, пока найдем либо, не найдем ноду с нужным ключом.

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

Источники

https://ru.wikipedia.org/wiki/Хеш-таблица
https://www.youtube.com/watch?v=wg8hZxMRwcw

Исходный код

https://gitlab.com/demensdeum/datastructures

0