22 заметки с тегом

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

Лучшее объяснения работы семафора

A semaphore is like a nightclub: it has a certain capacity, enforced by a bouncer. Once it’s full, no more people can enter, and a queue builds up outside. Then, for each person that leaves, one person enters from the head of the queue. The constructor requires a minimum of two arguments: the number of places currently available in the nightclub and the club’s total capacity.

 Нет комментариев    7   1 д   .net   c#   программирование

Небольшая заметка об индексах в ms sql

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

Что из себя представляет индекс?

Внутри сервера они представлены в виде B-tree, где B означает сбалансированное, а не бинарное дерево.

Например мы хотим найти запись с Id = 2581.
Начиная с корня, выполняется поиск наименьшего значения ключа, большего или равного требуемому. Так мы найдем узел 18316, потом спустимся в узел 9031 и там мы увидим что есть прямая ссылка на лежащие данные по ключу 2581, после чего осуществляем вычитку данных.

Кластерный индекс

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

Не кластерный индекс

Структура такая же как и кластерного индекса, но с двумя отличиями:

  1. Не изменяет физическое упорядочивание данных.
  2. Страницы индекса состоят из ключа индекса и ссылки на строку.

SQL Server использует индекс для нахождения записей, совпадающих с условиями запроса.

Составной ключ в индексе

SQL Server позволяет создавать индексы по нескольким колонкам. Но в таком случае у нас появляется ограничение. Длинна составного ключа не должна быть больше 900 байт. Но бывают исключения, например у нас есть две колонки, каждая из которых длинной в 500 байт. Сервер создаст индекс, в случае если нет данных, которые будут превышать длину в 900 байт.

Также стоит помнить что индексы типа (Col1, Col2) и (Col2, Col1) разные.

Уникальные индексы

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

Статьи, которые советую почитать чтобы глубже разобраться в теме

  1. Очень хорошая статья о всех типах индексов, когда их стоит создавать и как использовать
  2. Индексы. Теоретические основы.
 Нет комментариев    61   1 мес   sql   программирование   структуры данных

Изучение SQL: рекурсивные запросы

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

Общий вид рекурсивного запроса

WITH <имя> (<список столбцов>)
AS (
	SELECT    -- анкорная часть
	UNION ALL -- рекурсивная часть
        SELECT FROM <имя>
        WHERE <условие продолжения интерации>
)

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

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

Наполнение таблицы.

Код запроса:

;WITH OrgStructure AS 
(
	SELECT Id, ParentId, EmployeeType, EmployeeName
	FROM Employees
	WHERE EmployeeName = 'Jim' -- отправная точка, нам надо найти менеджера сотрудника Jim

	UNION ALL

	SELECT e.Id, e.ParentId, e.EmployeeType, e.EmployeeName
	FROM Employees as e
	JOIN OrgStructure as os
	ON e.Id = os.ParentId
)

SELECT * FROM OrgStructure
WHERE EmployeeType = 'manager' -- указываем что мы ищем менеджера.

Пример 2
Найдем первые 10 чисел Фибоначчи:

;WITH FIBONACHI AS 
(
	SELECT
		1 Iteration,
		1 SecondValue,
		2 CurrentValue
	UNION ALL

	SELECT
		Iteration + 1,
		SecondValue = CurrentValue,
		CurrentValue = SecondValue + CurrentValue
	FROM FIBONACHI
	WHERE Iteration < 10
)
SELECT CurrentValue FROM FIBONACHI
 Нет комментариев    44   1 мес   sql   программирование

GIN индекс

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

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

Хорошая аналогия для этого метода — алфавитный указатель в конце книги, где для каждого термина приведен список страниц, где этот термин упоминается.

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

Алгоритм поиска Ли

Алгоритм поиска пути в планарном графе. Зачастую используется в схемотехнике и в играх (стратегиях) для поиска кратчайшего пути.

Алгоритм состоит из 3 шагов:

  1. Инициализация
  2. Распространение волны
  3. Восстановление пути

Также есть 2 способа поиска пути: ортогональный и ортогонально-диагональный. Ниже на скриншотах можно увидеть работу этих двух способов.

Ортогональный поиск.
Ортогонально-диагональный поиск.

Псевдокод

Взято из Википедии.

Инициализация

Пометить стартовую ячейку 
d := 0

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

ЦИКЛ
  ДЛЯ каждой ячейки loc, помеченной числом d
    пометить все соседние свободные непомеченные ячейки числом d + 1
  КЦ
  d := d + 1
ПОКА (финишная ячейка не помечена) И (есть возможность распространения волны)

Восстановление пути

ЕСЛИ финишная ячейка помечена
ТО
  перейти в финишную ячейку
  ЦИКЛ
    выбрать среди соседних ячейку, помеченную числом на 1 меньше числа в текущей ячейке
    перейти в выбранную ячейку и добавить её к пути
  ПОКА текущая ячейка — не стартовая
  ВОЗВРАТ путь найден
ИНАЧЕ
  ВОЗВРАТ путь не найден

Пример кода, который реализует алгоритм и выводит на экран путь (C#).

 Нет комментариев    57   1 мес   c#   алгоритмы   программирование   структуры данных

Хеш-таблица

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

Есть два основных способа реализации хеш-таблицы:

  1. Метода цепочек — данные с одинаковым хешем обьединяються в список.
  2. Метод открытой адресации — если при добавлении данных ячейка занята, то переходим к следующей, до тех пор пока не найдем свободную.

В .NET уже существует готовая реализация этой структуры: System.Collections.HasTable. Но с появлением обобщенных коллекций стал устаревшим. На его место пришел словарь — Dictionary. Так как в базовом объекте есть 2 метода Equal и GetHashCode мы можем в качестве ключа словаря использовать любой тип данных.

 Нет комментариев    56   2 мес   .net   программирование   структуры данных

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

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

  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;
}
 Нет комментариев    79   2 мес   алгоритмы   программирование
 Нет комментариев    60   3 мес   программирование

Название для 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

 Нет комментариев    50   3 мес   программирование

36

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

 Нет комментариев    88   3 мес   мысли   программирование
Ранее Ctrl + ↓