Починяем Primus

В этой заметке опишу запуск Steam игр на дистрибутиве Линукса Arch Linux в конфигурации ноутбука Intel + Nvidia

Counter-Strike: Global Offensive

Единственная конфигурация которая у меня заработала – Primus-vk + Vulkan.

Установим нужные пакеты:
pacman -S vulkan-intel lib32-vulkan-intel nvidia-utils lib32-nvidia-utils vulkan-icd-loader lib32-vulkan-icd-loader primus_vk

Далее добавляем параметры запуска для Counter-Strike: Global Offensive:
pvkrun %command% -vulkan -console -fullscreen

Должно работать!

Sid Meier’s Civilization VI

Работает в связке – Primus + OpenGL + LD_PRELOAD.

Установим пакет Primus:
pacman -S primus

Далее добавляем параметры запуска для Sid Meier’s Civilization VI:
LD_PRELOAD='/usr/lib/libfreetype.so.6:/usr/lib/libbrotlicommon.so.1:/usr/lib/libbrotlidec.so.1' primusrun %command%

С помощью LD_PRELOAD подпихиваются библиотеки сжатия и шрифтов Freetype.

Dota 2

Работает в связке – Primus + OpenGL + удаление локов на запуске.

Установим пакет Primus:
pacman -S primus

Далее добавляем параметры запуска для Dota 2:
primusrun %command% -gl -console

Если игра не стартует с ошибкой fcntl(5) for /tmp/source_engine_2808995433.lock failed, то попробуйте удалить файл/tmp/source_engine_2808995433.lock
rm /tmp/source_engine_2808995433.lock
Обычно файл лока остается от прошлой игровой сессии, если игра не была закрыта естественным образом.

Как проверить?

Проще всего проверить запуск приложений на дискретной видеокарте Nvidia через утилиту nvidia-smi:

Для игр на движке Source проверить можно через игровую консоль с помощью команды mat_info:

Источники

https://wiki.archlinux.org/title/Steam/Game-specific_troubleshooting
https://help.steampowered.com/en/faqs/view/145A-FE54-F37B-278A
https://bbs.archlinux.org/viewtopic.php?id=277708

Sleep Sort

Sleep Sort – сортировка сном, еще один представитель детерменированных странных алгоритмов сортировки.

Работает следующим образом:

  1. Проходит циклом по списку элементов
  2. Для каждого цикла запускается отдельный поток
  3. В потоке шедулится сон (sleep) потока на время – значение элемента и вывод значения после сна
  4. По окончанию цикла, ждем ожидания завершения самого долгого сна потока, выводим отсортированный список

Пример кода алгоритма сортировки сном на C:

#include <stdio.h>
#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;
}

В этой реализации я использовал функцию usleep на микросекундах с умножением значения на 1000, т.е. на миллисекундах.
Временная сложность алгоритма – O(оч. долго)

Ссылки

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

Источники

https://codoholicconfessions.wordpress.com/2017/05/21/strangest-sorting-algorithms/
https://twitter.com/javascriptdaily/status/856267407106682880?lang=en
https://stackoverflow.com/questions/6474318/what-is-the-time-complexity-of-the-sleep-sort

Stalin Sort

Stalin Sort – сортировка навылет, один из алгоритмов сортировки с потерей данных.
Алгоритм очень производительный и эффективный, временная сложность O(n).

Работает следующим образом:

  1. Проходим циклом по массиву, сравнивая текущий элемент со следующим
  2. Если следующий элемент меньше текущего, то удаляем его
  3. В итоге получаем отсортированный массив за O(n)

Пример вывода работы алгоритма:

Numbers: [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
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]

Код на Питоне 3:

numbers = [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
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}")

Из недостатков можно отметить потерю данных, но если двигаться к утопичному, идеальному, отсортированному списку за O(n), то как иначе?

Ссылки

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

Источники

https://github.com/gustavo-depaula/stalin-sort
https://www.youtube.com/shorts/juRL-Xn-E00
https://www.youtube.com/watch?v=L78i2YcyYfk

Selection Sort

Selection Sort – алгоритм сортировки выбором. Выбором чего? А вот минимального числа!!!
Временная сложность алгоритма – О(n2)

Алгоритм работает следующим образом:

  1. Проходим массив циклом слева-направо, запоминаем текущий стартовый индекс и число по индексу, назовем числом A
  2. Внутри цикла запускаем еще один для прохода слева-направо в поисках меньшего чем A
  3. Когда находим меньший, запоминаем индекс, теперь меньший становится числом А
  4. Когда внутренний цикл заканчивается, меняем местами число по стартовому индексу и число А
  5. После полного прохода верхнего цикла, получаем отсортированный массив

Пример выполнения алгоритма:

Round 1
(29, 49, 66, 35, 7, 12, 80)
29 > 7
(7, 49, 66, 35, 29, 12, 80)
Round 1 ENDED
Round 2
(7, 49, 66, 35, 29, 12, 80)
49 > 35
35 > 29
29 > 12
(7, 12, 66, 35, 29, 49, 80)
Round 2 ENDED
Round 3
(7, 12, 66, 35, 29, 49, 80)
66 > 35
35 > 29
(7, 12, 29, 35, 66, 49, 80)
Round 3 ENDED
Round 4
(7, 12, 29, 35, 66, 49, 80)
(7, 12, 29, 35, 66, 49, 80)
Round 4 ENDED
Round 5
(7, 12, 29, 35, 66, 49, 80)
66 > 49
(7, 12, 29, 35, 49, 66, 80)
Round 5 ENDED
Round 6
(7, 12, 29, 35, 49, 66, 80)
(7, 12, 29, 35, 49, 66, 80)
Round 6 ENDED
Sorted: (7, 12, 29, 35, 49, 66, 80)

Не найдя Objective-C реализации на Rosetta Code, написал его сам:

#include "SelectionSort.h"
#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.
Скрипт сборки:

clang SelectionSort.m \
        main.m \
        -lobjc \
        `gnustep-config --objc-flags` \
        `gnustep-config --objc-libs` \
        -I /usr/include/GNUstepBase \
        -I /usr/lib/gcc/x86_64-pc-linux-gnu/12.1.0/include/ \
        -lgnustep-base \
        -o SelectionSort \

Links

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

Sources

https://rosettacode.org/wiki/Sorting_algorithms/Selection_sort
https://ru.wikipedia.org/wiki/Сортировка_выбором
https://en.wikipedia.org/wiki/Selection_sort
https://www.youtube.com/watch?v=LJ7GYbX7qpM

Counting Sort

Counting sort – алгоритм сортировки подсчетом. Всмысле? Да! Прям так!

В алгоритме участвуют минимум два массива, первый – список целых чисел которые надо отсортировать, второй – массив размером = (максимальное число – минимальное число) + 1, изначально содержащий одни нули. Далее перебираются цифры из первого массива, по элементу-числу получается индекс во втором массиве, который инкрементируют на единицу. После прохода по всему списку у нас получится полностью заполненный второй массив с количеством повторений чисел из первого. У алгоритма есть серьезная издержка – второй массив также содержит нули для чисел которых в первом списке нет, т.н. оверхед по памяти.

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

Пример неоптимизированной работы алгоритма сортировки подсчетом:

  1. Входой массив 1,9,1,4,6,4,4
  2. Тогда массив для подсчета будет 0,1,2,3,4,5,6,7,8,9 (минимальное число 0, максимальное 9)
  3. С итоговыми счетчиками 0,2,0,0,3,0,1,0,0,1
  4. Итого отсортированный массив 1,1,4,4,4,6,9

Код алгоритма на языке Python 3:

print("Counting Sort")

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)

Ссылки

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

Источники

https://www.youtube.com/watch?v=6dk_csyWif0
https://www.youtube.com/watch?v=OKd534EWcdk
https://en.wikipedia.org/wiki/Counting_sort
https://rosettacode.org/wiki/Sorting_algorithms/Counting_sort
https://pro-prof.com/forums/topic/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-%D0%BF%D0%BE%D0%B4%D1%81%D1%87%D0%B5%D1%82%D0%BE%D0%BC

Bogosort

Псевдо-сортировка или болотная сортировка, один из самых бесполезных алгоритмов сортировки.

Работает он так:
1. На вход подается массив из чисел
2. Массив из чисел перемешивается случайным образом (shuffle)
3. Проверяется отсортирован ли массив
4. Если не отсортирован, то массив перемешивается заново
5. Все это действо повторяется до тех пор, пока массив не отсортируется случайным образом.

Как можно увидеть – производительность этого алгоритма ужасна, умные люди считают что даже O(n * n!) т.е. есть шанс завязнуть кидая кубики во славу бога хаоса очень много лет, массив так и не отсортируется, а может отсортируется?

Реализация

Для реализации на TypeScript мне понадобилось реализовать следующие функции:
1. Перемешивание массива объектов
2. Сравнение массивов
3. Генерация случайного числа в диапазоне от нуля до числа (sic!)
4. Печать прогресса, т.к. кажется что сортировка выполняется бесконечно

Ниже код реализации на TypeScript:

const printoutProcess = (numbers: number[], sortedNumbers: number[], numberOfRuns: number) => console.log(`Still trying to sort: ${numbers}, current shuffle ${sortedNumbers}, try number: ${numberOfRuns}`);
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.

Как долго

Вывод работы алгоритма:

Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 2,9,7,8,0,7,4,5,2,5, try number: 144000
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 до сих пор нет своего алгоритма перемешивания массивов, генерации целого числа в диапазоне, доступа к хэшам объектов для быстрого сравнения.

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/bogosort
https://www.typescriptlang.org/
https://marketplace.visualstudio.com/items?itemName=kakumei.ts-debug

Источники

https://www.youtube.com/watch?v=r2N3scbd_jg
https://en.wikipedia.org/wiki/Bogosort

Паттерны GoF

Список паттернов банды четырех – те самые паттерны из-за которых вас могут валить на собеседовании.

Порождающие паттерны

Структурные паттерны

Паттерны поведения

Паттерн Интерпретатор

Что входит

Паттерн Интерпретатор относится к Поведенческим паттернам проектирования. Данный паттерн позволяет реализовать свой язык программирования, путем работы с AST древом, вершины которого представляют из себя терминальные и нетерминальные выражения, реализующие метод Interpret, обеспечивающий функционал языка.

  • Терминальное выражение – например константа строки – “Hello World”
  • Нетерминальное выражение – например Print(“Hello World”), содержит Print и аргумент из Терминального выражения “Hello World”

В чем разница? Разница в том что интерпретирование на терминальных выражениях заканчивается, а для нетерминальных продолжается вглубь по всем входящим вершинам/аргументам. Если бы AST древо состояло только из нетерминальных выражений, то выполнение приложения никогда бы не завершилось, т.к. требуется некая конечность любого процесса, этой конечность и выступают терминальные выражения, они обычно содержат данные, например строки.

Пример AST древа ниже:


Dcoetzee, CC0, via Wikimedia Commons

Как можно увидеть, терминальные выражения – constant и variable, нетерминальные – остальные.

Что не входит

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

Реализация

В паттерне участвуют:

  • Клиент – отдает AST-древо и запускает Interpret(context) для корневой вершины (Client)
  • Контекст – содержит состояние приложения, передается выражениям при интерпретации (Context)
  • Абстрактное выражение – абстрактный класс содержащий метод Interpret(context) (Expression)
  • Терминальное выражение – конечное выражение, потомок абстрактного выражения (TerminalExpression)
  • Нетерминальное выражение – не конечное выражение, содержит указатели на вершины вглубь AST-древа, подчиненные вершины обычно влияют на результат интерпретации нетерминального выражения (NonTerminalExpression)

Пример Клиента на C#

class Application {
        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));
        }
}

Пример Абстрактного выражения на C#

interface IExpression
{
    String interpret(Context context);
}

Пример Терминального выражения на C# (Строковая константа)

class ConstantExpression : TerminalExpression
{
    private String constant;

    public ConstantExpression(String constant) {
        this.constant = constant;
    }

    override public String interpret(Context context) {
        return constant;
    }
}

Пример Нетерминального выражения на C# (Запуск и конкатенация результатов подчиненных вершин, с использованием разделителя «;»

class PerformExpression : NonTerminalExpression
{
    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;
    }
}

Функционально сможешь?

Как известно все Тьюринг-полные языки эквивалентны. Можно ли перенести Объектно-Ориентированный паттерн на язык Функционального программирования?

Можно, для эксперимента возьмем ФП язык для веба под названием Elm. В Elm нет классов, но есть Записи (Records) и Типы (Types) поэтому в реализации участвуют следующие записи и типы:

  • Выражение – перечисление всех возможных выражений языка (Expression)
  • Подчиненное выражение – выражение являющееся подчиненным по отношению к Нетерминальному выражению (ExpressionLeaf)
  • Контекст – запись хранящая состояние приложения (Context)
  • Функции реализующие методы Interpret(context) – все необходимые функции реализующие функционал Терминальных, Нетерминальных выражений
  • Вспомогательные записи состояния Интерпретатора – необходимы для корректной работы Интерпретатора, хранят состояние Интерпретатора, контекст

Пример функции реализующей интерпретацию для всего набора возможных выражений на Elm:

run input = 
  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
      }

А парсить?

Парсинг исходного кода в AST-древо не входит в паттерн Интерпретатор, существует несколько подходов для парсинга исходного кода, но об этом как-нибудь в другой раз.
В реализации Интерпретатора для Elm я написал простейший парсер в AST-древо, состоящий из двух функций – парсинг вершины, парсинг подчиненных вершин.

parseLeafs: ParseLeafsState -> ParseLeafsState
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

Ссылки

https://gitlab.com/demensdeum/patterns/-/tree/master/interpreter/elm
https://gitlab.com/demensdeum/patterns/-/tree/master/interpreter/csharp

Источники

https://en.wikipedia.org/wiki/Interpreter_pattern
https://elm-lang.org/
https://docs.microsoft.com/en-us/dotnet/csharp/