Техдок – Page 6

Исправляем медленную работу HDD в Windows 10

Данная заметка посвящается всем, не сдающим позиции, пользователям жестких дисков.

Через 1.5 года использования ноутбука HP Pavilion в дуалбуте HDD (Windows 10) и SSD (Ubuntu) я стал замечать очень долгую загрузку приложений, общую неотзывчивость интерфейса, зависания на простейших операциях в Windows 10. Проблема была минимизирована до той степени, что пользоваться ноутбуком стало возможно снова. Далее опишу действия которые я предпринял для устранения проблемы.

Диагностика

Для начала исследования нужно устранить мистификацию любого порядка, для начала определим основные причины поломок жестких дисков. Что может пойти не так при работе с жестким диском? Проблемы могут возникать на физическом уровне электроники и на логическом, программном уровне данных.
К проблемам электроники относятся такие вещи как: нерабочий блок питания компьютера/ноутбука, проблемы с аккумулятором ноутбука; износ компонентов жесткого диска, неполадки в схемах и чипах внутренних компонентов диска, программные ошибки прошивки, последствия ударов/падений диска, либо аналогичные проблемы с другими устройствами которые влияют на его работу.
Критическим износом жесткого диска считается момент появления количества такого количества сбойных секторов (bad block) при котором дальнейшая эксплуатация диска невозможна. Данные блоки блокируются прошивкой жесткого диска, данные переносятся на другие сектора автоматически и не должны влиять на работу диска до определенного критического момента.
К проблемам программной логики относятся ошибки в файловой системе из-за некорректной работы приложений, действий пользователя: отключение устройства по горячему, завершение процессов записи без корректной остановки приложений, ошибки в драйверах, сервисах операционной системы.
Не имея специализированных средств диагностики электроники, нам остается только проверять корректность программного уровня, уже в процессе могут обнаружиться неполадки электроники, которые обычно устраняют методом блочного ремонта (замена компонентов/чипов); Далее рассмотрим методы программной диагностики с помощью диагностических утилит. Стоит заметить что все утилиты должны запускаться на системе с максимальным приоритетом, т.к. другие приложения могут помешать замерам производительности, блокировать диск на чтение/запись, что приведет к некорректным результатам диагностики.

SMART

S.M.A.R.T. система мониторинга состояния устройств хранения данных – HDD, SDD, eMMC и пр. Позволяет оценить износ устройства, просматривать количество сбойных блоков (bad block), опираясь на данные предпринять дальнейшие действия. Просматривать SMART можно в разных приложениях для работы с дисками, я предпочитаю использовать утилиты от производителя. Для своего жесткого диска Seagate я использовал утилиту SeaTools, для него состояние выводилось как GOOD, то есть прошивка диска считает что все хорошо.

Утилиты производителя

Утилиты производителя диска предоставляют тесты для проверки его работы. SeaTools имеет несколько видов тестов, можно использовать их все для локализации проблемы. Быстрые и простые тесты могут не выявить каких-либо проблем, поэтому предпочитайте долгие тесты. В моем случае только на Long Test были найдены ошибки.

Slowride

Для проверки корректности чтения, нахождения медленных или мертвых блоков, я написал приложение slowride, оно работает по очень простому принципу – открывает дескриптор блочного устройства, с заданными настройками пользователя производит чтения данных всего устройства, с замерами времени, выводом медленных блоков. Программа останавливается на первой же ошибке, в таком случае придется перейти к более серьезным утилитам для снятия данных, так как простыми методами данные диска прочитать не представляется возможным.
В моем случае чтение всего диска осуществлялось корректно, с небольшой просадкой по скорости – 90мб/сек (5400rpm) за одну секунду, на некоторых областях диска. Из чего можно было сделать вывод что я имею дело с программной проблемой.

Акустический анализ

Данный метод не относится к программным методам диагностики, однако является достаточно важным для устранения проблемы. Например при частично рабочем блоке питания, жесткий диск может подвисать/зависать издавая громкий щелчок.
В моем случае при работе с диском в Windows 10 я слышал знакомый всем владельцам HDD, громкий треск бегающей туда-сюда головки диска при попытке сделать что-либо в операционной системе, однако звук был почти постоянным, это навело меня на мысль о слишком большой фрагментации диска, перегрузе диска фоновыми сервисами.

Исправляем

Проблемы электроники во время программной диагностики обнаружены не были, поблочное чтение всего диска завершалось корректно, однако SeaTools показал ошибки на проверке Long Test.

Утилиты производителя

Софт производителя диска помимо диагностики предоставляет процедуры исправления ошибок. В SeaTools за это отвечает кнопка Fix All, после подтверждения согласия с потенциальной потерей данных, запустится процесс исправления. Помог ли в моем случае этот фикс? Нет, диск продолжил работать также громко и медленно, однако ошибок Long Test больше не показывал.

CHKDSK

CHKSDK это утилита компании Microsoft для устранения программных ошибок для файловых систем Windows. Со временем такие ошибки накапливаются на диске и могут очень сильно мешать работе, в том числе приводить к невозможности читать/писать какие-либо данные вообще. Инструкцию по использованию утилиты вы можете найти на сайте Microsoft, я же порекомендую использовать все возможные флаги для исправления ошибок (на момент написания заметки это /r /b /f); Запускать проверку нужно с правами администратора через терминал Windows (cmd), для системного раздела она будет проходить на загрузке системы, может проходить очень долгое время, в моем случае заняло 12 часов.
Помог ли этот фикс в моем случае? Нет.

Дефрагментация диска

Работа с данными на диске осуществляется блоками, большие файлы обычно записываются в несколько блоков/фрагментов. Со временем, множество удаленных файлов создают пустые блоки которые не находятся рядом, из-за этого при записи файлы заполняют эти пустоты, и головке диска приходится физически преодолевать большие расстояния. Данная проблема называется фрагментацией, и с ней сталкиваются только пользователи жестких дисков. На момент нескольких фиксов фрагментация моего жесткого диска составляла 41%, визуально это выглядело так:

То есть все плохо. Увидеть фрагментацию, провести дефрагментацию можно с помощью утилиты Defragger, либо встроенным дефрагментатором. Также можно включить сервис “Optimize drives” в Windows 10, проставить дефрагментацию по расписанию в контрольной панели. Дефрагментацию нужна только HDD дискам, включать для SSD дисков нежелательно, так как это приведет к ускоренному износу диска, видимо по этой причине фоновая дефрагментация отключена по умолчанию.

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

Отключаем сервисы

С помощью утилиты Марка Руссиновича Process Monitor можно отследить процессы которые загружают жесткий диск своими делами, достаточно включить колонки IO Write/Read. После исследования данной колонки я отключил сервис Xbox Game Bar, известный сервис фонового ускорения программ Superfetch под новым названием SysMain, через панель сервисов контрольной панели. Superfetch должен постоянно анализировать приложения которыми пользуется юзер и ускорять их запуск с помощью кэширования в оперативную память, в моем случае это приводило к фоновой загрузке всего диска и невозможности работы.

Чистим диск

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

Итог

Что помогло больше всего? Заметная разница в производительности была достигнута после дефрагментации диска, спонтанные зависания удалось устранить с помощью отключения сервисов Xbox и Superfetch. Не было бы этих проблем, если бы я пользовался SSD? Проблем с медленной работой при фрагментацией определенно не было бы, проблемы с сервисами устранять пришлось бы в любом случае, а программные ошибки не зависят от типа накопителя. В ближайшем будущем планирую полный переход на SSD, ну а пока “Да здравствуют блины, блины навсегда!”

Ссылки

http://www.outsidethebox.ms/why-windows-8-defragments-your-ssd-and-how-you-can-avoid-this/
https://channel9.msdn.com/Shows/The-Defrag-Show
https://www.seagate.com/ru/ru/support/downloads/seatools/
https://www.ccleaner.com/defraggler/download
https://docs.microsoft.com/en-us/windows-server/administration/windows-commands/chkdsk
https://gitlab.com/demensdeum/slowride/

Пишем бэкенд сервер на C++ FCGI

Краткая заметка о том как я писал серверную часть для 3д редактора Cube Art Project, сервер должен сохранять и выводить работы пользователей веб версии, отдавая им короткие URL по кнопке сохранения. Сначала я хотел использовать Swift/PHP/Ruby/JS или какой-то подобный современный язык для бэкэнда, но посмотрев на характеристики моей VPS было принято решение написать сервер на C/C++.
Для начала нужно установить на сервере libfcgi и модуль поддержки fcgi для вашего вебсервера, пример для Ubuntu и Apache:


sudo apt install libfcgi libapache2-mod-fcgid

Далее настраиваем модуль в конфиге:

FcgidMaxProcessesPerClass – максимальное количество процессов на класс, я поставил 1 процесс так как не расчитываю на большую нагрузку.
AddHandler fcgid-script .fcgi – расширение файла с которым должен стартовать модуль fcgi.
Добавляем в конфиг папку из которой будут запускаться cgi приложения:

Далее пишем приложение на C/C++ с поддержкой fcgi, собираем его, и копируем в папку /var/www/html/cgi-bin.
Примеры кода и скрипта сборки:
https://gitlab.com/demensdeum/cube-art-project-server/-/blob/master/src/cubeArtProjectServer.cpp
https://gitlab.com/demensdeum/cube-art-project-server/-/blob/master/src/build.sh
После этого нужно будет перезапустить ваш вебсервер:


systemctl restart apache2

Далее проставьте необходимые права на выполение папки cgi-bin через chmod.
После этого ваша cgi программа должна работать через браузер по ссылке, пример для сервера Cube Art Project:
http://192.243.103.70/cgi-bin/cubeArtProject/cubeArtProjectServer.fcgi
Если что-то не получается, то смотрите логи вебсервера, либо подключайтесь дебаггером к запущенному процессу, процесс отладки не должен отличаться от процесса отладки обычного клиентского приложения.

Источники

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

Исходный код

https://gitlab.com/demensdeum/cube-art-project-server

Портируем C++ SDL приложение на Android

В данной заметке я опишу свой опыт портирования прототипа 3D редактора Cube Art Project на Android.
Сначала посмотрим на результат, в эмуляторе запущен редактор с 3D курсором куба красного цвета:

Для успешной сборки нужно было сделать следующее:

Установить последний Android SDK и NDK (версию ндк чем свежее тем лучше).
Загрузить исходный код SDL2, взять оттуда шаблон для сборки андроид приложения.
Добавить SDL Image, SDL Mixer к сборке.
Добавить библиотеки моего игрового движка и тулкита, их зависимости (GLM, JSON for Modern C++)
Адаптировать файлы сборок для Gradle.
Адаптировать C++ код для совместимости с Android, изменения коснулись платформозависимых компонентов (OpenGL ES, инициализация графического контекста)
Собрать и проверить проект на эмуляторе.

Шаблон проекта

Загружаем исходники SDL, SDL Image, SDL Mixer:
https://www.libsdl.org/download-2.0.php
В папке docs есть подробная инструкция по работе с шаблоном андроид проекта; скопируем директорию android-project в отдельную папку, сделаем симлинк или скопируем папку SDL в android-project/app/jni.
Подставляем правильный идентификатор для флага avd, запускаем эмулятор андроида из директории Sdk:


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

Указываем пути в скрипте, собираем проект:


rm -rf app/build || true
export ANDROID_HOME=/home/demensdeum/Android/Sdk/
export ANDROID_NDK_HOME=/home/demensdeum/Android/android-ndk-r21-beta2/
./gradlew clean build
./gradlew installDebug

Должен собраться шаблон проекта SDL с кодом на Си из файла


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

Зависимости

Загружаем исходный код в архивах для SDL_image, SDL_mixer:
https://www.libsdl.org/projects/SDL_image/
https://www.libsdl.org/projects/SDL_mixer/

Загружаем зависимости вашего проекта, для примера мои shared библиотеки:
https://gitlab.com/demensdeum/FlameSteelCore/
https://gitlab.com/demensdeum/FlameSteelCommonTraits
https://gitlab.com/demensdeum/FlameSteelBattleHorn
https://gitlab.com/demensdeum/FlameSteelEngineGameToolkit/
https://gitlab.com/demensdeum/FlameSteelEngineGameToolkitFSGL
https://gitlab.com/demensdeum/FSGL
https://gitlab.com/demensdeum/cube-art-project

Все это выгружаем в app/jni, каждый “модуль” в отдельную папку, например app/jni/FSGL. Далее у вас есть вариант найти рабочие генераторы для файлов Application.mk и Android.mk, я не нашел, однако возможно есть простое решение на основе CMake. Переходим по ссылкам и начинаем знакомиться с форматом файлов сборки для Android NDK:
https://developer.android.com/ndk/guides/application_mk
https://developer.android.com/ndk/guides/android_mk

Также следует прочитать про разные APP_STL реализации в NDK:
https://developer.android.com/ndk/guides/cpp-support.html

После ознакомления создаем для каждого “модуля” файл Android.mk, далее пример файл сборки shared библиотеки Cube-Art-Project:


LOCAL_PATH := $(call my-dir)
include $(CLEAR_VARS)

APP_STL := c++_static
APP_CPPFLAGS := -fexceptions
LOCAL_MODULE := CubeArtProject
LOCAL_C_INCLUDES := $(LOCAL_PATH)/src $(LOCAL_PATH)/../include $(LOCAL_PATH)/../include/FlameSteelCommonTraits/src/FlameSteelCommonTraits
LOCAL_EXPORT_C_INCLUDES = $(LOCAL_PATH)/src/

define walk
$(wildcard $(1)) $(foreach e, $(wildcard $(1)/*), $(call walk, $(e)))
endef

ALLFILES = $(call walk, $(LOCAL_PATH)/src)
FILE_LIST := $(filter %.cpp, $(ALLFILES))
$(info CubeArtProject source code files list)
$(info $(FILE_LIST))
LOCAL_SRC_FILES := $(FILE_LIST:$(LOCAL_PATH)/%=%)

LOCAL_SHARED_LIBRARIES += FlameSteelCore
LOCAL_SHARED_LIBRARIES += FlameSteelBattleHorn
LOCAL_SHARED_LIBRARIES += FlameSteelCommonTraits
LOCAL_SHARED_LIBRARIES += FlameSteelEngineGameToolkit
LOCAL_SHARED_LIBRARIES += FlameSteelEngineGameToolkitFSGL
LOCAL_SHARED_LIBRARIES += FSGL
LOCAL_SHARED_LIBRARIES += SDL2
LOCAL_SHARED_LIBRARIES += SDL2_image

LOCAL_LDFLAGS := -static-libstdc++
include $(BUILD_SHARED_LIBRARY)

Любой опытный CMake пользователь поймет этот конфиг с первых строк, форматы очень похожи, в Android.mk отсутствует GLOB_RECURSIVE, поэтому приходится рекурсивно искать исходные файлы с помощью функции walk.

Меняем Application.mk, Android.mk со-но для сборки C++ а не Си кода:


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

Переименовываем YourSourceHere.c -> YourSourceHere.cpp, grep’аем по вхождениям, меняем путь в сборке, например:


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

Далее попробуйте собрать проект, если вы увидете ошибки от компилятора об отсутствии хидеров, то проверьте корректность путей в Android.mk; если ошибки будут от линковщика вида “undefined reference”, то проверьте корректность указания файлов исходного кода в сборках, оттрейсить списки можно через указание $(info $(FILE_LIST)) в Android.mk файле. Не забудьте о двойном механизме линковки, с помощью модулей в ключе LOCAL_SHARED_LIBRARIES и корректной линковке через LD, например для FSGL:


LOCAL_LDLIBS := -lEGL -lGLESv2

Адаптация и запуск

Пришлось поменять некоторые вещи, например убрать GLEW из сборок для iOS и Android, переименовать часть вызовов OpenGL, добавив постфикс EOS (glGenVertexArrays -> glGenVertexArraysOES), включать макрос отсутствующих модерновых функций дебага, вишенка на торте это неявный инклуд GLES2 хидеров с указанием макроса GL_GLEXT_PROTOTYPES 1:


#define GL_GLEXT_PROTOTYPES 1
#include "SDL_opengles2.h"

Также наблюдал черный экран на первых запусках с ошибкой вида “E/libEGL: validate_display:255 error 3008 (EGL_BAD_DISPLAY)”, поменял инициализацию окна SDL, профайла OpenGL и все заработало:


SDL_DisplayMode mode;
SDL_GetDisplayMode(0,0,&mode);
int width = mode.w;
int height = mode.h;

window = SDL_CreateWindow(
            title,
            0,
            0,
            width,
            height,
            SDL_WINDOW_OPENGL | SDL_WINDOW_FULLSCREEN | SDL_WINDOW_RESIZABLE
        );

SDL_GL_SetAttribute( SDL_GL_CONTEXT_PROFILE_MASK, SDL_GL_CONTEXT_PROFILE_ES );

На эмуляторе приложение по умолчанию устанавливается с иконкой SDL и именем “Game”.

Мне осталось исследовать возможность автоматической генерации файлов сборки на основе CMake, либо же мигрировать сборки для всех платформ на Gradle; однако CMake остается выбором дефакто для текущей разработки на C++.

Исходный код

https://gitlab.com/demensdeum/android-sdl-test-app
https://gitlab.com/demensdeum/android-sdl-test-app/tree/master/cube-art-project-android

Источники

https://developer.android.com/ndk/guides/cpp-support.html
https://developer.android.com/ndk/guides/application_mk
https://developer.android.com/ndk/guides/android_mk
https://lazyfoo.net/tutorials/SDL/52_hello_mobile/android_windows/index.php
https://medium.com/androiddevelopers/getting-started-with-c-and-android-native-activities-2213b402ffff

Перевернутый мир

Для разработки нового проекта Cube Art Project взял на вооружение методологию разработки Test Driven Development. В данном подходе сначала реализуется тест для определенного функционала приложения, а затем уже реализуется конкретный функционал. Большим плюсом в данном подходе я считаю реализацию финальных интерфейсов, максимально непосвященных в детали реализации, до начала разработки функционала. При таком подходе тест диктует дальнейшую реализацию, добавляются все преимущества контрактного программирования, когда интерфейсы являются контрактами для конкретной реализации.
Cube Art Project – 3D редактор в котором пользователь строит фигуры из кубов, не так давно этот жанр был очень популярен. Так как это графическое приложение, то я решил добавить тесты с валидацией скриншотов.
Для валидирования скриншотов нужно получить их из OpenGL контекста, делается это с помощью функции glReadPixels. Описание аргументов функции простейшие – начальная позиция, ширина, высота, формат (RGB/RGBA/проч.), указатель на выходной буфер, любому работавшему с SDL или имеющему опыт с буферами данных в Си будет просто подставить нужные аргументы. Однако считаю необходимым описать интересную особенность выходного буфера glReadPixels, пиксели в нем хранятся снизу вверх, а в SDL_Surface все базовые операции происходят сверху вниз.
То есть загрузив референсный скриншот из png файла, я не смог сравнить два буфера в лоб, так как один из них был перевернутым.
Чтобы перевернуть выходной буфер из OpenGL вам нужно заполнить его отнимая высоту скриншота для координаты Y. Однако стоить учесть что есть шансы выйти за пределы буфера, если не отнять единицу во время заполнения, что приведет к memory corruption.
Так как я повсеместно стараюсь использовать ООП парадигму “программирования интерфейсами”, вместо прямого Си-подобного доступа к памяти по указателю, то при попытке записать данные за пределами буфера объект мне об этом сообщил благодаря валидации границ в методе.
Итоговый код метода получения скриншота в стиле сверху-вниз:


    auto width = params->width;
    auto height = params->height;

    auto colorComponentsCount = 3;
    GLubyte *bytes = (GLubyte *)malloc(colorComponentsCount * width * height);
    glReadPixels(0, 0, width, height, GL_RGB, GL_UNSIGNED_BYTE, bytes);

    auto screenshot = make_shared(width, height);

    for (auto y = 0; y < height; y++) {
        for (auto x = 0; x < width; x++) {
            auto byteX = x * colorComponentsCount;
            auto byteIndex = byteX + (y * (width * colorComponentsCount));
            auto redColorByte = bytes[byteIndex];
            auto greenColorByte = bytes[byteIndex + 1];
            auto blueColorByte = bytes[byteIndex + 2];
            auto color = make_shared(redColorByte, greenColorByte, blueColorByte, 255);
            screenshot->setColorAtXY(color, x, height - y - 1);
        }
    }

    free(bytes);

Источники

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

Исходный код

https://gitlab.com/demensdeum/cube-art-project-bootstrap

Longest Common Substring

В данной заметке я опишу алгоритм решения задачи наибольшей общей подстроки. Допустим мы пытаемся расшифровать зашифрованные бинарные данные, для начала попробуем найти общие паттерны с помощью поиска наибольшей подстроки.
Входная строка для примера:
adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
Мы ищем повторяющуюся дважды строку:
DATAHEADER??

Префиксы

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


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

Результирующая строка – asdf
Пример на Kotlin:


fun longestPrefix(lhs: String, rhs: String): String {
        val maximalLength = min(lhs.length-1, rhs.length -1)
        for (i in 0..maximalLength) {
            val xChar = lhs.take(i)
            val yChar = rhs.take(i)
                if (xChar != yChar) {
                    return lhs.substring(0, i-1)
                }
        }
        return lhs.substring(0,maximalLength)
}

Brute Force

Когда не получается по хорошему, стоит прибегнуть к грубой силе. Используя метод longestPrefix пройдем по строке двумя циклами, первый берет строку от i до конца, второй от i + 1 до конца, передает их в поиск наибольшего префикса. Временная сложность данного алгоритма примерно равна O(n^2) ~ O(n*^3).
Пример на Kotlin:


fun searchLongestRepeatedSubstring(searchString: String): String {
        var longestRepeatedSubstring = ""
        for (x in 0..searchString.length-1) {
            val lhs = searchString.substring(x)
            for (y in x+1..searchString.length-1) {
                val rhs = searchString.substring(y)
                val longestPrefix = longestPrefix(lhs, rhs)
                if (longestRepeatedSubstring.length < longestPrefix.length) {
                    longestRepeatedSubstring = longestPrefix
                }
            }
        }
        return longestRepeatedSubstring
}

Суффиксный массив

Для более элегантного решения нам потребуется инструмент - структура данных под названием “Суффиксный массив”. Данная структура данных представляет из себя массив из подстрок заполняемых в цикле, где каждая подстрока начинается со следующего символа строки до конца.
Например для строки:


adasDATAHEADER??

Суффиксный массив выглядит так:


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

Решаем сортировкой

Отсортируем суффиксный массив, затем пройдем по всем элементам циклом где в левой руке (lhs) текущий элемент, в правой (rhs) следующий и вычислим самый длинный префикс с помощью метода longestPrefix.
Пример на Kotlin:


fun searchLongestRepeatedSubstring(searchString: String): String {
    val suffixTree = suffixArray(searchString)
    val sortedSuffixTree = suffixTree.sorted()

    var longestRepeatedSubstring = ""
    for (i in 0..sortedSuffixTree.count() - 2) {
        val lhs = sortedSuffixTree[i]
        val rhs = sortedSuffixTree[i+1]
        val longestPrefix = longestPrefix(lhs, rhs)
        if (longestRepeatedSubstring.length < longestPrefix.length) {
            longestRepeatedSubstring = longestPrefix
        }
    }
    return longestRepeatedSubstring
}

Временная сложность алгоритма O(N log N), что гораздо лучше решения в лоб.

Источники

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

Исходный код

https://gitlab.com/demensdeum/algorithms

Insertion Sort, Merge Sort

Insertion Sort

Сортировка вставками – каждый элемент сравнивается с предыдущими по списку и элемент меняется местами с большим, если таковой имеется, в ином случае внутренний цикл сравнения останавливается. Так как элементы сортируются с первого по последний, то каждый элемент сравнивается с уже отсортированным списком, что *возможно* уменьшит общее время работы. Временная сложность алгоритма O(n^2), то есть идентична баббл сорту.

Merge Sort

Сортировка слиянием – список разделяется на группы по одному элементу, затем группы “сливаются” попарно с одновременным сравнением. В моей реализации при слиянии пар элементы слева сравниваются с элементами справа, затем перемещаются в результирующий список, если элементы слева закончились, то происходит добавление всех элементов справа в результирующий список (их дополнительное сравнение излишне, так как все элементы в группах проходят итерации сортировки)
Работу данного алгоритма очень легко распараллелить, этап слияния пар можно выполнять в потоках, с ожиданием окончания итераций в диспетчере.
Вывод алгоритма для однопоточного выполнения:


["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["Alice", "John"], ["#1", "Mike"], ["20", "Артем"], ["60", "60"], ["DoubleTrouble"]]
[["#1", "Alice", "John", "Mike"], ["20", "60", "60", "Артем"], ["DoubleTrouble"]]
[["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"], ["DoubleTrouble"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

Вывод алгоритма для многопоточного выполнения:


["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["20", "Артем"], ["Alice", "John"], ["60", "60"], ["#1", "Mike"], ["DoubleTrouble"]]
[["#1", "60", "60", "Mike"], ["20", "Alice", "John", "Артем"], ["DoubleTrouble"]]
[["DoubleTrouble"], ["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

Временная сложность алгоритма O(n*log(n)), что немного лучше чем O(n^2)

Источники

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

Исходный код

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

Сортировка пузырьком на Erlang

Сортировка пузырьком это достаточно скучно, но становится интереснее если попробовать реализовать его на функциональном языке для телекома – Erlang.

У нас есть список из цифр, нам нужно его отсортировать. Алгоритм сортировки пузырьком проходит по всему списку, итерируя и сравнивая числа попарно. На проверке происходит следующее: меньшее число добавляется в выходной список, либо числа меняются местами в текущем списке если справа меньше, перебор продолжается со следующим по итерации числом. Данный обход повторяется до тех пор, пока в списке больше не будет замен.

На практике его использовать не стоит из-за большой временной сложности алгоритма – O(n^2); я реализовал его на языке Erlang, в императивном стиле, но если вам интересно то можете поискать лучшие варианты:


-module(bubbleSort).
-export([main/1]).

startBubbleSort([CurrentHead|Tail]) ->
    compareHeads(CurrentHead, Tail, [], [CurrentHead|Tail]).

compareHeads(CurrentHead, [NextHead|Tail], [], OriginalList) ->   
    if
        CurrentHead < NextHead ->
            compareHeads(NextHead, Tail, [CurrentHead], OriginalList);
        true ->
            compareHeads(CurrentHead, Tail, [NextHead], OriginalList)
    end;
    
compareHeads(CurrentHead, [NextHead|Tail], OriginalOutputList, OriginalList) ->
    if
        CurrentHead < NextHead ->
            OutputList = OriginalOutputList ++ [CurrentHead],
            compareHeads(NextHead, Tail, OutputList, OriginalList);
        true ->
            OutputList = OriginalOutputList ++ [NextHead],
            compareHeads(CurrentHead, Tail, OutputList, OriginalList)
    end;
  
compareHeads(CurrentHead, [], OriginalOutputList, OriginalList) ->
    OutputList = OriginalOutputList ++ [CurrentHead],
    if
        OriginalList == OutputList ->
            io:format("OutputList: ~w~n", [OutputList]);
        true ->
            startBubbleSort(OutputList)
    end.
  
main(_) ->
    UnsortedList = [69,7,4,44,2,9,10,6,26,1],
    startBubbleSort(UnsortedList).

Установка и запуск

В Ubuntu Эрланг установить очень просто, достаточно в терминале набрать команду sudo apt install erlang. В данном языке каждый файл должен представлять из себя модуль (module), со списком функций которые можно использовать извне – export. К интересным особенностям языка относится отсутствие переменных, только константы, отсутствие стандартного синтаксиса для ООП (что не мешает использовать ООП техники), и конечно же параллельные вычисления без блокировок на основе модели акторов.

Запустить модуль можно либо через интерактивную консоль erl, запуская одну команду за другой, либо проще через escript bubbleSort.erl; Для разных случаев файл будет выглядеть по разному, например для escript необходимо сделать функцию main, из которой он будет стартовать.

Источники

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

Исходный код

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

Алгоритм лексикографического сравнения

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

Пример для языка Си можно посмотреть здесь:
https://github.com/gcc-mirror/gcc/blob/master/libiberty/memcmp.c

Следует учитывать что сравнивать символы нужно в единой статичной кодировке, например в Swift я использовал посимвольное сравнение на UTF-32. Вариант сортировки массива с использованием memcmp сработает точно для однобайтовых символов, в остальных случаях (кодировки переменной длины) возможно порядок будет некорректен. Не исключаю возможности реализации на основе кодировок переменной длины, но скорее всего будет на порядок сложнее.

Временная сложность алгоритма в лучшем случае O(1), среднем и худшем O(n)

Источники

https://ru.wikipedia.org/wiki/Лексикографический_порядок

Исходники

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