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

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

Позднее Ctrl + ↑

Parallel, Asynchronous, Multithreading programming

Многопоточное программирование

Код может выполнятся в разных потоках. Например основной UI поток и набор потоков для обработки данных. В данном случае нет гарантии что потоки будут работать параллельно. Обычно это зависит от процессора. Потоки «абстрагируют» от пользователя низкоуровневые детали и позволяют выполнять более чем одну работу «параллельно».

Параллельное программирование

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

IEnumerable<Data> yourData = GetYourData();
var result = yourData.AsParallel() // начинаем обрабатывать параллельно
  .Select(d => d.CalcAmount()) // Вычисляем параллельно
  .Where(amount => amount > 0)
  .ToArray(); // Возврвщаемся к синхронной модели

Асинхронное программирование

Мы запускаем какую-то задачу, но не ждем ответа, а продолжаем делать свою работу. А когда будет готов ответ — нас уведомят. Обычно такие операции бывают при работе с сетью, диском или любыми другими продолжительными задачами.

Пример на C#.
У нас есть продолжительная асинхронная задача, которая обращается к БД. С помощью конструкций async/await мы организовываем асинхронную работу. Пока БД готовит для нас ответ, поток, который обслуживал этот метод возвращается в пулл потоков и может тем временем выполнять полезную работу. Как только БД отдаст ответ, нашему методу снова выделяется поток и продолжается работа.

var asyncResult = await Database.GetAllUsers(); // длительная асинхронная операция
var activeUsers = asyncResult.Where(user => user.IsActive).ToList(); // работаем с результатом асинхронной операции

Еще один забавный но наглядный пример

Вам нужно выкопать во дворе бассейн.

  1. Вы взяли лопату и копаете. Это однопоточная работа
  2. Вы пригласили друга Васю и копаете вместе, периодически задевая друг-друга лопатами. Это многопоточная работа
  3. Пока вы копаете бассейн, Вася копает канаву под водопровод. Никто никому не мешает. Это распараллеливание
  4. Вы пригласили бригаду землекопов, а сами с Васей пошли пить пиво. Когда бригада все сделает, к вам придут за деньгами. Это асинхронная работа.

Количество лопат в хозяйстве — это количество ядер в системе

Ссылки

Параллелизм против многопоточности против асинхронного программирования: разъяснение
Cтатья об async/await в C#
Многопоточное vs асинхронное программирование (stackoverflow)

 Нет комментариев    321   2019   dotnet   программирование
 Нет комментариев    643   2019   программирование

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

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.

 Нет комментариев    138   2019   dotnet   программирование

Небольшая заметка об индексах в 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. Индексы. Теоретические основы.
 Нет комментариев    256   2019   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
 Нет комментариев    376   2019   sql   программирование

GIN индекс

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

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

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

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

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

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

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

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

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

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

Псевдокод

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

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

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

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

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

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

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

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

 Нет комментариев    166   2019   алгоритмы   программирование   структуры данных

Хеш-таблица

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

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

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

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

 Нет комментариев    148   2019   dotnet   программирование   структуры данных

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

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

  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;
}
 Нет комментариев    217   2019   алгоритмы   программирование
 Нет комментариев    116   2019   программирование
Ранее Ctrl + ↓