16 заметок с тегом

программирование

Алгоритмы сортировки

Классификация

  1. По степени роста сложности
  2. По использованию дополнительной памяти
  3. Рекурсивный или нет
  4. По устойчивости
  5. По методу сортировки: вставка, слияние, обмен

Распространенные алгоритмы

  • Сортировка пузырьком
  • Сортировка вставками
  • Сортировка выбором
  • Сортировка слиянием
  • Быстрая сортировка

Ссылка на сайт с гифками, которые демонстрируют работу алгоритмов: https://www.toptal.com/developers/sorting-algorithms

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

Самая стандартная и простая сортировка. Выполняет проходы по массиву и перемещает наибольший элемент в конец массива.

Лучший вариант Средний вариант Худший вариант
Степень сложности O(n) O(n^2) O(n^2)
Рост памяти O(1) O(1) O(1)
public void Sort(int[] inputArray)
{
	for (int i = 0; i < inputArray.Length; i++) {
		for (int j = 1; j < inputArray.Length; j++) {
			if (inputArray[j-1] > inputArray[j]) {
				Swap(inputArray, j-1, j);
			}
		}
	}
}

public void Swap(int[] inputArray, int indexLeft, int indexRight)
{
	if (indexLeft == indexRight) return;
	var temp = inputArray[indexLeft];
	inputArray[indexLeft] = inputArray[indexRight];
	inputArray[indexRight] = temp;
}

Сортировка вставками
Также достаточно простой алгоритм, на каждом этапе которого выбирается один элемент массива, для которого осуществляется поиск позиции для вставки.

Лучший вариант Средний вариант Худший вариант
Степень сложности O(n) O(n^2) O(n^2)
Рост памяти O(1) O(1) O(1)
public static void Sort(int[] inputArray)
{
	int currentElementIndex= 1;
	while (currentElementIndex < inputArray.Length)
	{
		if (inputArray[currentElementIndex] < inputArray[currentElementIndex - 1]) {
			var newIndex = FindIndex(inputArray, inputArray[currentElementIndex]);
			Insert(inputArray, newIndex, currentElementIndex);
		}
		currentElementIndex++;
	}
}

public static int FindIndex(int[] inputArray, int element)
{
	for (int i = 0; i < inputArray.Length; i++)
	{
		if (inputArray[i] > element) {
			return i;
		}
	}
	return 0;
}

public static void Insert(int[] inputArray, int indexLeft, int indexRight)
{
	if (indexLeft == indexRight) return;
	var temp = inputArray[indexLeft];
	inputArray[indexLeft] = inputArray[indexRight];
	for (int current = indexRight; current > indexLeft; current--) {
		inputArray[current] = inputArray[current-1];
	}
	inputArray[indexLeft + 1] = temp;
}

Сортировка выбором
На каждом своем шаге отыскивает наименьший элемент в неотсортированной части массива и устанавливает его в соответствующую позицию массива.

Лучший вариант Средний вариант Худший вариант
Степень сложности O(n) O(n^2) O(n^2)
Рост памяти O(1) O(1) O(1)
public static void Sort(int[] input) {
	for (int i = 0; i < input.Length; i++) {
		var smallestElementIndex = FindIndexOfSmallestElement(input, i);
		Swap(input, smallestElementIndex, i);
	}
}

public static int FindIndexOfSmallestElement(int[] input, int startFrom = 0) {
	var smallestElementValue = input[startFrom];
	var smallestElementIndex = startFrom;
	for (int i = startFrom + 1; i < input.Length; i++)
	{
		if (smallestElementValue > input[i]) {
			smallestElementValue = input[i];
			smallestElementIndex = i;
		}
	}
	return smallestElementIndex;
}

public static void Swap(int[] input, int indexLeft, int indexRight)
{
	if (indexLeft == indexRight) return;
	var temp = input[indexLeft];
	input[indexLeft] = input[indexRight];
	input[indexRight] = temp;
}

Сортировка слиянием
Разбивает массив на подмассивы примерно одинакового размера, рекурсивно разбивает до тех пор, пока размер массива будет равен 1. После этого происходит сортировка частей и их соединение в один.

Лучший вариант Средний вариант Худший вариант
Степень сложности O(n log n) O(n log n) O(n log n)
Рост памяти O(n) O(n) O(n)
public static void Sort(int[] input) {
	if (input.Length <= 1) {
		return;
	}
	
	// Поделили массивы
	var leftSize = input.Length / 2;
	var rightSize = input.Length - leftSize;
	var left = new int[leftSize];
	var right = new int[rightSize];
	
	// Скопировали данные из основного массива
	Array.Copy(input, 0, left, 0, leftSize);
	Array.Copy(input, leftSize, right, 0, rightSize);
	
	Sort(left);
	Sort(right);
	
	Merge(input, left, right);
}

public static void Merge(int[] input, int[] left, int[] right) {
	var leftIndex = 0;
	var rightIndex = 0;
	var leftAndRightSize = left.Length + right.Length;
	
	for (int i = 0; i < leftAndRightSize; i++) {
		if (leftIndex >= left.Length) {
			input[i] = right[rightIndex];
			rightIndex++;
		}
		else if (rightIndex >= right.Length) {
			input[i] = left[leftIndex];
			leftIndex++;
		}
		else if (left[leftIndex] < right[rightIndex]) {
			input[i] = left[leftIndex];
			leftIndex++;
		}
		else {
			input[i] = right[rightIndex];
			rightIndex++;
		}
	}
}

Быстрая сортировка
Один из самых быстрых алгоритмов, о чем говорит название.

Этапы сортировки:
• Случайный выбор опорного элемента массива (pivotValue), относительно которого переупорядочиваются элементы массива.
• Переместить все значения, которые больше опорного, вправо, а все значения, что меньше опорного, влево.
• Повторить алгоритм для неотсортированной левой и правой части массива, пока каждый элемент не окажется на своей позиции.

Лучший вариант Средний вариант Худший вариант
Степень сложности O(n log n) O(n log n) O(n^2)
Рост памяти O(1) O(1) O(1)
public static void Sort(int[] input, int leftIndex, int rightIndex) {
	var i = leftIndex;
	var j = rightIndex;
	var pivot = input[(leftIndex + rightIndex) >> 1];
	
	while (i <= j) {
		while (input[i] < pivot) {
			i++;
		}
		while (input[j] > pivot) {
			j--;
		}
		
		if (i <= j) {
			Swap(input, i, j);
			j--;
			i++;
		}
		
		if (leftIndex < j) {
			Sort(input, leftIndex, j);
		}
		
		if (rightIndex > i) {
			Sort(input, i, rightIndex);
		}
	}
}

public static void Swap(int[] input, int indexLeft, int indexRight)
{
	if (indexLeft == indexRight) return;
	var temp = input[indexLeft];
	input[indexLeft] = input[indexRight];
	input[indexRight] = temp;
}
 Нет комментариев    55   18 дн   алгоритмы   программирование
 Нет комментариев    45   1 мес   программирование

Название для Unit-тестов

Способы именования юнит-тестов.

  1. MethodName_StateUnderTest_ExpectedBehavior
Пример:
IsAdult_AgeLessThan18_False 
WithdrawMoney_InvalidAccount_ExceptionThrown
  1. MethodName_ExpectedBehavior_StateUnderTest
Пример: 
IsAdult_False_AgeLessThan18
WithdrawMoney_ThrowsException_IfAccountIsInvalid
  1. Feature to be tested — удобный тем, что делает модульные тесты альтернативной формой документации.
Примеры: 
IsNotAnAdultIfAgeLessThan18
FailToWithdrawMoneyIfAccountIsInvalid
  1. Should_ExpectedBehavior_When_StateUnderTest
Примеры: 
Should_ThrowException_When_AgeLessThan18
Should_FailToWithdrawMoney_ForInvalidAccount
  1. When_StateUnderTest_Expect_ExpectedBehavior
Примеры: 
When_AgeLessThan18_Expect_isAdultAsFalse
When_InvalidAccount_Expect_WithdrawMoneyToFail
  1. Given_Preconditions_When_StateUnderTest_Then_ExpectedBehavior — Идея состоит в том, чтобы разбить тесты на три части таким образом, чтобы можно было найти предварительные условия, проверка состояния во время теста и ожидаемое поведение, которое должно быть написано в вышеуказанном формате.
Пример:
Given_UserIsAuthenticated_When_InvalidAccountNumberIsUsedToWithdrawMoney_Then_TransactionsWillFail
  1. MethodName_WithStateUnderTest_ShouldExpectedBehavior
Пример:
Login_WithDisabledTwoFactorSmsAuth_ShouldReturnSignInAndReturnRedirectToActionResult

Источник: https://bool.dev/blog/detail/kak-pravilno-imenovat-unit-testu

 Нет комментариев    34   1 мес   программирование

36

Просто советую всем посмотреть. Особенно программистам.

 Нет комментариев    71   1 мес   мысли   программирование

Изучение нового языка программирования

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

Что надо знать

  • Тулинг для билда
  • Менеджер пакетов
  • Базовые идеи
  • Философия
  • 5-10 популярных библиотек
    • Как ходить в веб
    • Как работать с БД
    • и т. д.
  • 5-10 известных людей
  • 5-10 продуктов, которые используют этот язык

Настоятельно советую посмотреть этот доклад.

 Нет комментариев    52   1 мес   программирование

Правила использования AutoMapper в .NET

Оригинал статьи: https://bool.dev/blog/detail/pravila-ispolzovaniya-automapper-v-net

Конфигурация
✔ Используйте инициализировать AutoMapper один раз в Mapper.Initialize в AppDomain startup в устаревшем ASP.NET
✔ Используйте использовать пакет AutoMapper.Extensions.Microsoft.DependencyInjection в ASP.NET Core с services.AddAutoMapper(assembly[])
✔ Используйте конфигурацию маппингов в профайле
✔ Рассмотрите организацию классов профайлов близко к типам назначения, которые они настраивают (иными словами в UserProfile должны быть маппинги классов связанных с юзером)
✔ Рассмотрите использование параметров конфигурации поддерживаемых LINQ, по сравнению с параметрами, не поддерживаемыми LINQ
Х Избегайте before/after map конфигурацию
Х Не размещайте логику которая строго не относится к поведению при маппинге данных
Х Не используйте MapFrom, когда элемент и так может быть автоматически смаплен
Х Не используйте AutoMapper, за исключением случаев, когда тип назначения представляет собой уплощенное подмножество свойств типа источника
Х Не используйте AutoMapper для поддержки сложной многоуровневой архитектуры
Х Избегайте использования AutoMapper, когда у вас значительный процент конфигурации прописан в форме Ignore или MapFrom
Х Не используйте доступ к статичному Mapper классу внутри профайла
Х Не используйте DI контейнер для регистрации всех профилей
Х Не используйте инджект зависимостей в профайлы
Х Не используйте CreateMap на каждый запрос
Х Не используйте inline maps

Моделирование
✔ Используйте не большие DTO
✔ Необходимо создавать внутренние типы в DTO для типов элементов, которые не могут быть сведены
✔ Следует помещать общие простые «computed property» в source модель
✔ Следует помещать «computed property» которые специфичны для dest модели в dest модель
Х Избегайте совмесное использование DTO между маппингами
Х Не создавайте DTO с «circular» ассоциациями
Х Избегайте изменения имен членов DTO для управления сереализацией

Выполнение
✔ Рассмотрите возможность использования query projection поверх in-memory mapping’a​
✔ Необходимо использовать mapping опции для runtime-resolved значений в проекциях.
✔ Используйте опции mappinga для разрешения контекстуализированных сервисов в in-memory mapping’e
Х Не абстрагируйте и не инкапсулируйте mapping за интерфейсом

 Нет комментариев    54   1 мес   c#   программирование

Коллекции в .NET

Сегодня мы рассмотрим следующие интерфейсы:

  • IEnumerable
  • IQueryable
  • ICollection
  • IList
  • ISet
  • IDictionary
  • Queue и Stack

Все эти интерфейсы находятся в пространствах имен System.Collection и System.Collection.Generic. Первый тип коллекций стоит избегать, так как они имеют худшую производительность и не обеспечивают безопасность типов.

IEnumerable

Данный интерфейс является базовым для всех коллекций. В нем объявлен только один метод, который позволяет обходить элементы коллекции в цикле. Нельзя изменить данные из IEnumerable.

IQueryable

Всякий раз, когда мы сталкиваемся с большим количеством данных необходимо подумать, какую коллекцию или какой тип использовать для работы с ними. В отличии от IEnumerable — IQueryable предлагает высокую производительность в случае работы с большим объемом данных. IQueryable предварительно фильтрует данные по запросу а затем отправляет только отфильтрованные данные клиенту.

Разница между IQueryable и IEnumerable

Основное отличие между этими интерфейсами в том, что IEnumerable работает со всем массивом данных, а IQueryable с отфильтрованным. IEnumerable получает все данные на стороне сервера и загружает их в память а затем позволяет сделать фильтрацию по данным из памяти. Когда делается запрос к базе данных, IQueryable выполняет запрос на серверной стороне и в запросе применяет фильтрацию.

Когда что использовать?

IEnumerable IQueryable
Может двигаться только вперед по коллекции, он не может идти назад может двигаться только вперед по коллекции, он не может идти назад
Хорошо подходит для работы с данными в памяти (списки, массивы) Лучше работает с запросами к базе данных (вне памяти)
Подходит для LINQ to Object и LINQ to XML Подходит для LINQ to SQL
Поддерживает отложенное выполнение (Lazy Evaluation) Поддерживает отложенное выполнение (Lazy Evaluation)
Не поддерживает произвольные запросы Поддерживает произвольные запросы (используя CreateQuery и метод Execute)
Не поддерживает ленивую загрузку (lazy loading) Поддерживает ленивую загрузку (lazy loading)
Методы расширения, работающие с IEnumerable принимают функциональные объекты Методы расширения, работающие с IQueryable принимают объекты выражения (expression tree)

ICollection

Этот интерфейс содержит методы, которые позволяют манипулировать элементами коллекции. Также содержит свойство Count.

IList

Расширяет коллекции методами поиска по индексу и индексатором.

ISet

Интерфейс ISet описывает набор уникальных элементов, которые не гарантируют сохранение их порядка в списке. Методы интерфейса реализуют различные стандартные операции над множествами из теории множеств. Следующие методы модифицируют существующую коллекцию:

ISet<int> set = new HashSet<int> { 1, 2, 3, 4, 5 };
 
set.UnionWith(new[] { 5, 6 });              // set = { 1, 2, 3, 4, 5, 6 }
set.IntersectWith(new[] { 3, 4, 5, 6, 7 }); // set = { 3, 4, 5, 6 }
set.ExceptWith(new[] { 6, 7 });             // set = { 3, 4, 5 }
set.SymmetricExceptWith(new[] { 4, 5, 6 }); // set = { 3, 6 }

Остальные только выполняют проверки над коллекцией и возвращают логическое значение (bool):

ISet<int> set = new HashSet<int> { 1, 2, 3, 4, 5 };
 
var isSubset = set.IsSubsetOf(new[] { 1, 2, 3, 4, 5 }); // = true
var isProperSubset = set.IsProperSubsetOf(new[] { 1, 2, 3, 4, 5 }); // = false
var isSuperset = set.IsSupersetOf(new[] { 1, 2, 3, 4, 5 }); // = true
var isProperSuperset = set.IsProperSupersetOf(new[] { 1, 2, 3, 4, 5 }); // = false
var equals = set.SetEquals(new[] { 1, 2, 3, 4, 5 }); // = true
var overlaps = set.Overlaps(new[] { 5, 6 }); // = true

IDictionary

В отличие от предыдущих двух, этот предназначен для хранения пар ключ-значение вместо отдельных значений, т. е. он использует KeyValuePair в качестве универсального параметра в ICollection.
Также он не позволяет хранить несколько элементов с одинаковым ключом.

Реализуют его следующие классы:

  1. Dictionary — обычный словарь.
  2. SortedDictionary — отсортированный список, реализован как словарь. Быстрее вставляет и удаляет элементы.
  3. SortedList — отсортированный список, который основан на массиве. Использует меньше памяти, чем SortedDictionary.

Queue и Stack

Класс Queue реализует принцип FIFO (first in, first out) — первым пришел, первым вышел.
Класс Stack похож на класс Queue, но он реализует принцип LIFO (последний пришел, первый вышел). Единственный элемент, который непосредственно доступен в этой коллекции, — это тот, который был добавлен совсем недавно.

Потокобезопасность

Обычные generic классы в Base Class Library имеют один очень важный недостаток, если вам нужно использовать их в многопоточных приложениях: они не являются поточно-ориентированными или по крайней мере, не полностью потокобезопасные.

Base Class Library содержит класс ReaderWriterLockSlim, который можно использовать для реализации этой конкретной функции относительно простым способом. Содержит 2 метода:

  1. EnterReadLock и ExitReadLock
  2. EnterWriteLock и ExitWriteLock

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

Immutable Collections

Immutable (неизменяемые) коллекции не включены в библиотеку базовых классов. Чтобы использовать их в проекте должен быть установлен пакет NuGet System.Collections.Immutable.

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

Ссылки

  1. https://bool.dev/blog/detail/sravnenie-kollektsiy-v-net
  2. https://bool.dev/blog/detail/kak-pravilno-vybrat-net-kollektsiyu
 Нет комментариев    79   1 мес   .net   c#   программирование

Первый проект

Нашел в старой переписке скриншоты игры, которую я делал когда только изучал программирование на C#. Игру делал на Unity в сеттинге сталкера. Дальше одной локации и простенького управления не зашло. Жаль что видео не сохранились.

Это был 2014 год.

Также пробовал моделировать в 3ds Max.

 Нет комментариев    83   1 мес   c#   unity3d   программирование

Структуры данных: связанные списки

Связанные списки — структура данных, элемент которой содержит собственные данные, так и одну или две ссылки на следующий и/или предыдущий элемент. Связанный список работает как массив, который растет и уменьшаться при необходимости из произвольной точки массива.

Наиболее используемые типы списков:

  1. Односвязный список
+-------+------+    +-------+-------+ 
| Hello |  *---+--->| world | null  +
+-------+------+    +-------+-------+
  1. Двусвязный список
+----------+---------+       +----------+----------+ 
|          |     *---|------>|          |          |
|  Hello   |         |       |          |  world   |
|          |         |<------|---*      |          |
+----------+---------+       +----------+----------+
  1. Кольцевой список
.        +-------<----------<--------------<--------+
         |                                          |
+-----+--+---+    +-----+------+    +-----+-----+   |
| 12  |  *---+--->| 15  |   *--+--->| 25  |  *--+---+
+-----+------+    +-----+------+    +-----+-----+



Быстродействие

  • Добавляет элемент в конец/начало списка — O(1)
  • Удаляет первый элемент списка со значением, равным переданному — O(n)
  • Поиск элемента — O(n)
  • Копирование а массив — O(n)
  • Получить количество — O(1)

Преимущества

  1. Элементы могут быть удалены или добавлены из середины списка
  2. Нет необходимости объявлять разvер списка при инициализации
  3. Эффективное удаление и добавление элементов

Недостатки

  1. Связанные списки не имеют возможности произвольного доступа к элементам — т. е. нет возможности получить элемент внутри списка, без того что бы пройтись по всем элементам до него.
  2. Для работы списков требуется динамическое выделение памяти, что может привести к утечкам памяти.

Ссылки

  1. https://metanit.com/sharp/algoritm/2.1.php
  2. https://rtfm.co.ua/c-svyazannye-spiski/
  3. https://ru.wikipedia.org/wiki/Связный_список
  4. https://tproger.ru/translations/linked-list-for-beginners/
  5. https://medium.com/outco/reversing-a-linked-list-easy-as-1-2-3-560fbffe2088
 Нет комментариев    61   1 мес   программирование   структуры данных

Работа с файлами в Powershell

Получение списка файлов

  • Get-ChildItem $path — отобразит список файлов по указанному пути.
  • Get-ChildItem -Force $path — отобразит список файлов (включая скрытые) по указанному пути.
  • Get-ChildItem -Force $path -Recurse — отобразит список всех файлов, а также вложенных.

Копирование файлов и папок

  • New-Item -Path $path -ItemType «directory | file» — создает объект в файловой системе.

Удаление всех файлов и папок, содержащихся в папке

  • Remove-Item $path — удалит все файлы по указанному пути, но будет предлагать подтверждения.
  • Remove-Item $path -Recurse — удалит все файлы без подтверждения.

Работа с содержимым файла

  • Get-Content -Path $path — вычитать содержимое файла.
  • Add-Content -Path $path «Additional content» — дописывает в конец файла текст.
  • Set-Content -Path $path -Value «New content» — позволяет перезаписать содержимое файла
  • Get-Date | Set-Content $path — также можно использовать в качестве пайпалайна
  • Out-File -FilePath $path — отправляет вывод в файл.
  • Out-File -FilePath $path -Append — дописывает данные в конец файла
 Нет комментариев    39   2 мес   powershell   программирование
Ранее Ctrl + ↓