Blog #algorithms

Допустим, что вам нужно найти середину связного списка, как это быстрее всего сделать? Завести 2 указателя, один будет шагать через один элемент, а второй - по каждому элементу. Таким образом когда первый указатель доберется до конца такого списка - второй будет указывать на середину. Так вот первый указатель называют "быстрым".

Недавно встретил такую задачку и хотел бы с вами поделиться:

На вход нашему методу передается некий граф, который содержит ноды вида

Node {
  int value;
  Node next;
}

Нам нужно найти ноду в этом графе, которая начинает бесконечный цикл.

Например:

1 -> 2 -> 3 -> 4 -> 2

Тут нода со значением 2 начинает цикл.

Если же ноды нет, то метод должен вернуть null.

Решение этой задачи довольно простое, если бы не одно условие: нужно найти решение без использования дополнительной памяти.

Насколько я помню, я встретил ее по теме "какие задачи не нужно задавать на собесах", т.к. если решения ты не знаешь - решить ее практически невозможно, но все равно - подумайте, ну а вдруг 🙂

p.s: задача была задана на собесе в компанию Apple.

Довольно простой вопрос, который решается банальной проверкой (v2.sqrMagnitude <= radius * radius). Мы такой вопрос часто задаем на собесах, но не только для того, чтобы выяснить считает ли человек через квадрат радиуса, а скорее для того, чтобы задать второй вопрос: "а в эллипс?". И вот на этом вопросе люди начинают сами себя закапывать. Кто-то придумывает несуществующие правила и теоремы, кто-то говорит, что мол "да я это не помню, там высшая математика, кому это вообще надо", ну а кто-то предлагает решение.

А самое интересное, что решение довольно простое, которое не требует никаких знаний и формул:

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

Catmull rom - это такая кривая, для построения которой нужно знать 4 точки. Особенность заключается в том, что кривая будет проходить через все 4 точки.

На практике мы такое часто используем, т.к. для построения, например, Безье требуются тангенты, расчет которых иногда затруднителен.

Алгоритм Хаффмана - самый простой и понятный алгоритм сжатия данных.

Представим, что у нас есть строка:
aaaaebbbaccaddae

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

1. Код должен быть короче для тех символов, которые встречаются чаще;
2. Код должен однозначно декодироваться, т.е. иметь уникальный префикс (т.е. нельзя выдать коды 0, 01, 10, т.к. в таком случае 00110010 может трактоваться по-разному).

Получится что-то типа такого:
a - 0

b - 100

c - 101

d - 110

e - 111

Теперь мы можем однозначно кодировать и декодировать строку:
0|0|0|0|111|100|100|100|0|101|101|0|110|110|0|111

Это алгоритм базового кодирования переменной длины.

А теперь что же предлагает нам алгоритм Хаффмана?
Предлагает построить нам бинарное дерево, где слева будут ноды с "0", а справа - с "1".
Принцип построение будет следующий:

1. Создаем ноды для каждого символа и положим их в очередь;
2. Пока в очереди больше одного элемента, делаем так:
   - Удаляем два узла, символы которых встречаются реже всего;
   - Создаем новую ноду, добавляем ее в очередь, а эти две помещаем чилдами, а частоту складываем.
3. Если осталась последняя нода - она просто становится корнем всего дерева.

Получится примерно следующее:

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

Алгоритм заливки. На самом деле ничего нового в нем нет, мы выбираем элемент массива, читаем из него данные и рекурсивно (https://t.me/unsafecsharp/115) обращаемся к элементу сверху, снизу, справа и слева. Таким образом мы обойдем все элементы, но нам нужно обойти лишь те, которые имеют те же данные, что и наш начальный элемент.

Пример:

77777
77555
75557
75577
77775

Если мы возьмем центральную 5, то результат заливки числом 6 будет таким:

77777
77666
76667
76677
77775

Алгоритм используется в различных областях. Например, в графах поиска пути (https://t.me/unsafecsharp/69) заливка используется для формирования «закрытых областей», чтобы можно было рано выйти при построении пути, если дойти до точки невозможно (области начальной точки не совпадают с конечной).

Допустим, у нас есть простой метод для перебора чего-либо:

class Node {
   public int value;
   public Node[] children; 
}  

Node FindRecursively(Node root, int value) {
   if (root.value == value) return root;
   for (int i = 0; i < root.children.Length; ++i) {
     var node = FindRecursively(root.children[i], value);
     if (node != null) return node;
   }
   return null; 
} 

Мы видим, что если на вход передать ноду графа и значение, то мы в итоге найдем нужную ноду, либо вернем null.

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

Что же делать?

Давайте избавимся от рекурсивного вызова метода. Самый простой вариант это сделать - использовать Stack или Queue:

Node Find(Node root, int value) {
   var queue = new Queue<Node>();
   queue.Enqueue(root);
   while (queue.Count > 0) {
     var node = queue.Dequeue();
     if (node.value == value) return node;
     for (int i = 0; i < node.children.Length; ++i) {
       queue.Enqueue(node.children[i]);
     }
   }
   return null; 
} 

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

Допустим, что у нас есть отсортированный массив чисел:

1 2 6 8 56 234 745 998 1010

Как нам определить, что в этом массиве есть какое-то число?

Самый простой вариант - пройти линейно от первого элемента до последнего. Таким образом мы получаем O(n) (Если кто не видел пост https://t.me/unsafecsharp/97).

Но как это сделать быстрее?

На этом месте те, кто не знает, может остановиться и подумать

На самом деле существует небольшой лайфхак: если вы видите что-нибудь отсортированное (массив это или матрица - не важно) и задача - поиск, то сложность всегда будет log(n). В теории можно придумать алгоритм, который будет еще умнее, но сложность от этого не изменится.

Итак, для начала нам нужно взять центральный индекс, то есть length / 2. После чего у нас массив разделится на два подмассива, при этом слева элементы будут всегда меньше искомого, а справа - больше.

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

Ищем 2:

[1 2 6 8 56 234 745 998 1010] 
[1 2 6 8 56]
[1 2 6]

Т.е. мы за 3 итерации нашли число. Вот это отбрасывание половины и есть log(n).

Мы знаем, что существует такой метод, который нам вернет случаное число (псевдослучайное, если точнее).

Итак, обычно это выглядит как-нибудь так:

var rnd = new Random(
var value = rnd.NextValue();

То есть есть некий класс рандома, который что-то делает и на выходе выдает "случайное" число. Как это работает?

На самом деле все довольно прозаично. Для того, чтобы выдать "случайное число", нужно знать некое другое число (или seed). Обычно дефолтное значение этого самого seed берется из тиков, времени, да чего угодно положительного.

Т.е. мы фактически в каждый момент времени уже имеем случайное число - это время.

А теперь каким образом работает этот самый rnd.NextValue()?

Random внутри себя хранит seed + в зависимости от реализации рандома может хранить другие параметры. Мне нравится больше всего самая простая реализация только с seed: 

struct Random {
   uint seed;
   uint NextValue() {
      var next = this.seed;
      this.seed += 123;
      return next;
   } 
} 

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

На этом месте можно рассмотреть вариант Unity.Mathematics:

uint next = seed;
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
return next;

По сути мы сдвигаем значение seed, получая "рандомное" число. Отсюда, кстати, и ограничение, что seed не может быть 0, т.к. чего бы мы там не двигали 0 всегда останется нулем.

Это я все к тому, что такой рандом можно передавать по сети и "откатывать", т.к. оно всегда будет выдавать некую последовательность чисел, основанную на этом самом seed. Т.е. взяв на одном клиенте 5 чисел, начиная с seed = 5:

5, 15, 60, 70, 1

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

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

Можно представить такую сортировку, которая отработает за O(n), если у нас на вход идут положительные числа, например, 0..100. Нам нужно всего лишь считать количество входных чисел:

++arr[number];

Где number - это наше число, а arr - хранилище для подсчета.

Таким образом на выходе мы получаем массив отсортированных чисел:

arr[0] = 1; // число 0 встречается 1 раз
arr[1] = 0; // число 1 встречается 0 раз
arr[2] = 5; // число 2 встречается 5 раз

Таким образом мы получаем результат такой сортировки:

022222...

Это сортировка подсчетом.

А теперь представим, что у нас числа 0..10000. Массив мы уже не заведем на 10к элементов, мы можем завести разряды, т.е. массив на 10 элементов:

arr = new int[10];

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

Допустим, у нас такие числа:

456 542 123 89 543

Первое что нам нужно сделать - это понять максимальный разряд (его можно передавать в метод сортировки, а можно получать из входных чисел). У нас он будет равен 3.

Ну и сам процесс сортировки:

1. Берем первый разряд и по нему раскладываем числа:

arr[2] = 542
arr[3] = 123 543
arr[6] = 456
arr[9] = 89

2. Теперь у получившихся чисел (542 123 543 456 89) мы берем следующий разряд:

arr[2] = 123
arr[4] = 542 543
arr[5] = 456
arr[8] = 89

3. И последний разряд (123 542 543 456 89) - у 89 мы дописываем 0:

arr[0] = 089
arr[1] = 123
arr[4] = 456
arr[5] = 542 543

Это довольно интересный алгоритм, сложность которого O(n), на практике, наверное, один из самых быстрых, если речь идет о сортировке положительных чисел.

Стоит заметить, что я рассмотрел только LSD (от младшего разряда к старшему) вариант сортировки, существует еще MSD (тоже наркота какая-то) или от старшего разряда к младшему.

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

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

Еще есть алгоритм Форчуна, результат которого идентичен, но принцип работы немного иной.

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

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

int Method(int n) {
     var sum = 0;
     for (int i = 0; i < n; ++i) {
         sum += i;
     }
     return sum; 
} 

Т.е. мы передаем в метод некое число n, которое обозначает количество итераций цикла внутри метода. Верхняя сложность такого алгоритма будет O(n). При этом если мы добавим в конец метода еще несколько строк:

for (int i = 0; i < 10; ++i) {
    sum += i;
}

то казалось бы, что сложность должна увеличиться на 10 (O(n + 10), но в О-нотации это будет константное время, а значит мы не будем учитывать это в сложности, т.е. сложность все еще останется O(n).

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

Вот для сравнения методы со сложностью O(n) и O(1).

Метод O(n):

int Method(int n) {
     var sum = 0;
     for (int i = 0; i < n; ++i) {
         sum += i;
     }
     return sum; 
} 

Метод O(1):

int Method() {
     var sum = 0;
     for (int i = 0; i < 100_000; ++i) {
         sum += i;
     }
     return sum; 
} 

Как видно из примера, любой вызов первого метода с n < 100_000 будет отрабатывать быстрее, чем второй метод с константным временем выполнения. Так что когда вам говорят, что какая-то коллекция работает за константное время на добавление элементов, например, то это совсем не означает что она делает это максимально эффективно.

Чтобы понять как они работают, нужно понять как работает Enumerator. Если коротко, то это некий объект, у которого есть метод MoveNext(), если его вызвать, то произойдет переключение на следующий шаг:

// step
yield return null;
// step 2

А теперь каким образом юнити собственно это делает. Раз у нас есть объект, мы можем добавить его в какой-нибудь список.

IEnumerator MyMethod() {
    // step 1
    yield return null;
    // step 2 
}

list.Add(MyMethod()); 

А теперь в update мы просто переключаем шаги:

for (int i = 0; i < list.Count; ++i) {
     if (item.MoveNext() == false) {
         item.Current // тут мы можем проверить возвращаемое значение, например, если там внутренняя корутина, то ее тоже хорошо бы выполнить 🙂
         list.RemoveAt(i);
         --i;
     }
}  

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

Корутины в юнити работают примерно таким образом. Еще я бы добавил, что при вызове StartCoroutine сразу выполняется первый шаг, т.е. вызывается MoveNext(), если он возрващает true, то значит дальше что-то есть и нужно добавлять корутину в список выполнения.

Т.е. нужно понять главное: корутины - это не какая-то особенная штуковина, которая работает только в юнити, это стандартный синтаксис и коллекции C#.