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/

RGB изображение в серое

В этой заметке я опишу алгоритм перевода RGB буфера в серый (Grayscale).
А делается это довольно просто, каждый пиксель цветовой канал буфера преобразуется по определенной формуле и на выходе получается изображение серого цвета.
Метод среднего:

const average = (red + green + blue) / 3;
red = average;
green = average;
blue = average;

Складываем 3 цветовых канала и делим на 3.

Однако существует еще один метод – метод средневзвешенный, он учитывает цветовосприятие человека:

const luminance = 0.2126 * red + 0.7152 * green + 0.0722 * blue;
red = luminance;
green = luminance;
blue = luminance;

Какой метод лучше использовать? Да какой вам больше подходит для конкретной задачи. Далее сравнение методов с помощью тестовой цветовой сетки:

Пример реализации на JavaScript + HTML 5

function rgb2grayscale(
    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
        );
}

Источники

https://www.baeldung.com/cs/convert-rgb-to-grayscale
https://twitter.com/mudasobwa/status/1528046455587495940
https://rosettacode.org/wiki/Grayscale_image

Ссылки

http://papugi.demensdeum.repl.co/

Благодарности

Спасибо Aleksei Matiushkin (https://twitter.com/mudasobwa) за наводку на Rosetta Code

Как запустить CSGO на Macbook M1

Если у вас вылезает ошибка SDL_GetDesktopDisplayMode_REAL на Macbook M1 при запуске CSGO, то делайте как написано дальше.
1. Добавьте параметры запуска в Steam для CSGO:
-w 1440 -h 900 -fullscreen
2. Запустите CSGO через Steam
3. Нажмите Игнорировать или Всегда игорировать на ошибке SDL_GetDesktopDisplayMode_REAL
4. Наслаждайтесь

Вычислительные машины Тьюринга

Представляю вашему вниманию перевод первых страниц статьи Алана Тьюринга – “О ВЫЧИСЛИМЫХ ЧИСЛАХ С ПРИЛОЖЕНИЕМ К ПРОБЛЕМЕ РАЗРЕШЕНИЯ” 1936 года. Первые главы содержат описание вычислительных машин, которые в дальнейшем стали основой для современной вычислительной техники.

Полный перевод статьи и пояснение можно прочитать в книге американского популяризатора Чарлза Петцольда, под названием “Читаем Тьюринга. Путешествие по исторической статье Тьюринга о вычислимости и машинах Тьюринга” (ISBN 978-5-97060-231-7, 978-0-470-22905-7)

Оригинальная статья:
https://www.astro.puc.cl/~rparra/tools/PAPERS/turing_1936.pdf

О ВЫЧИСЛИМЫХ ЧИСЛАХ С ПРИЛОЖЕНИЕМ К ПРОБЛЕМЕ РАЗРЕШЕНИЯ

А. М. ТЬЮРИНГ

[Получено 28 мая 1936 г. — Прочитано 12 ноября 1936 г.]

«Вычислимые» (computable) числа могут быть кратко описаны как действительные числа, выражения которых в виде десятичных дробей исчислимы (calculable) конечным числом средств. Хотя на первый взгляд в данной статье как вычислимые рассматриваются именно числа, почти так же легко определять и исследовать вычислимые функции целой переменной, действительной переменной, вычислимой переменной, вычислимые предикаты и тому подобное. Однако же, фундаментальные проблемы, связанные с указанными вычислимыми объектами, в каждом случае одни и те же. Для детального рассмотрения в качестве вычислимого объекта я выбрал именно вычислимые числа потому, что методика их рассмотрения наименее громоздкая. Надеюсь в скором времени описать взаимоотношения вычислимых чисел с вычислимыми функциями и так далее. При этом будут проведены исследования в области теории функций действительной переменной, выраженной в терминах вычислимых чисел. По моему определению, действительное число является вычислимым, если его представление в виде десятичной дроби может быть записано машиной.

В параграфах 9 и 10 я привожу некоторые доводы, чтобы показать, что вычислимые числа включают в себя все числа, которые естественно считать вычислимыми. В частности, я показываю, что некоторые большие классы чисел вычислимы. Они включают, например, действительные части всех алгебраических чисел, действительные части нулей функций Бесселя, числа π, e и прочие. Однако вычислимые числа включают в себя не все определимые числа, в подтверждение чего приведен пример определимого числа, которое не является вычислимым.

Хотя класс вычислимых чисел очень велик и во многих отношениях похож на класс действительных чисел, он все же поддается перечислению, то есть является перечислимым (enumerable). В §8 я рассматриваю определенные доводы, которые, казалось бы, доказывают обратное предположение. При корректном применении одного из этих доводов делаются выводы, на первый взгляд, аналогичные выводам Геделя*. Данные результаты имеют чрезвычайно важные способы применения. В частности, как показано ниже (§11), не может иметь решения проблема разрешения.

В своей недавней статье Алонзо Черч** представил идею «способности поддаваться эффективному исчислению» (effective calculability), которая эквивалентна моей идее «вычислимости» (computability), но имеет совершенно иное определение. Черч также приходит к аналогичным выводам относительно проблемы разрешения. Доказательство эквивалентности «вычислимости» и «способности поддаваться эффективному исчислению» изложено в приложении к настоящей статье.

1. Вычислительные машины

Мы уже говорили, что вычислимые числа — это такие числа, десятичные разряды которых исчислимы конечными средствами. Тут требуется более четкое определение. В настоящей статье не будет предпринято никаких реальных попыток обосновать приведенные здесь определения до тех пор, пока мы не дойдем до §9. Пока лишь замечу, что (логическое) обоснование (этого) заключается в том, что человеческая память в силу необходимости ограничена.

Сопоставим человека в процессе вычисления действительного числа с машиной, которая способна выполнять только конечное число условий q1, q2, …, qR; назовем эти условия «m-конфигурациями». Данная (то есть так определенная) машина снабжена «лентой» (аналогом бумаги). Такая лента, проходящая через машину, разделена на секции. Назовем их «квадратами». Каждый такой квадрат может содержать какой-то «символ». В любой момент существует и при том только один такой квадрат, скажем, r-й, содержащий символ который находится «в данной машине». Назовем такой квадрат «отсканированным символом». «Отсканированный символ» — это единственный такой символ, о котором машина, образно выражаясь, «непосредственно осведомлена». Однако при изменении своей m-конфигурации машина может эффективно запоминать некоторые символы, которые она «увидела» (отсканировала) ранее. Возможное поведение машины в любой момент определяется m-конфигурацией qn и отсканированным символом***. Назовем данную пару символов qn, «конфигурацией». Обозначенная таким образом конфигурация определяет возможное поведение данной машины. В некоторых из таких конфигураций, в которых отсканированный квадрат является пустым (т. е. не содержит символа), данная машина записывает новый символ на отсканированном квадрате, а в других из таких конфигураций она стирает отсканированный символ. Данная машина также способна перейти к сканированию другого квадрата, но так она может переместиться лишь на соседний квадрат вправо или влево. В дополнение к любой из этих операций можно изменить m-конфигурацию машины. При этом некоторые из записанных символов сформируют последовательность цифр, являющуюся десятичной частью вычисляемого действительного числа. Остальные из них представят собой не более чем неточные отметки с тем, чтобы «помочь памяти». При этом стиранию могут подвергаться лишь вышеупомянутые неточные отметки.

Я утверждаю, что рассматриваемые здесь операции включают в себя все те операции, которые используются при вычислении. Обоснование данного утверждения легче понять читателю, имеющему представление о теории машин. Поэтому в следующем разделе я продолжу развивать рассматриваемую теорию, опираясь на понимание значения терминов «машина», «лента», «отсканированный» и т. д.

*Гедель «О формально неразрешимых предложениях «Принципов математики» (опубликованных Уайтехдом и Расселом в 1910, 1912 и 1913 гг.) и родственных систем, часть I», журнал по мат. физике, ежемесячный бюллетень на немецком языке № 38 (за 1931 год , стр. 173-198.
** Алонзо Черч, «Неразрешимая проблема элементарной теории чисел», American J. of Math., («Американский журнал математики»), № 58 (за 1936 год), стр. 345-363.
*** Алонсо Черч, «Замечание о проблеме разрешения», J. of Symbolic Logic («Журнал математической логики»), №1 (за 1936 год), стр. 40-41