Blog

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

- List<> это такой массив, но с более удобными методами;

- При расширении листа - увеличивается массив x2, а данные копируются;

Но был еще дополнительный вопрос:

Vector3[] arr = ; // 1 элемент или больше
List<Vector3> list = ; // 1 элемент или больше
arr[0].x = 123f;
list[0].x = 123f;

Где сломается такой код?

- Нигде

- arr[0].x

- list[0].x

- В обоих случаях

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

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. Если осталась последняя нода - она просто становится корнем всего дерева.

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

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

Условие всегда ленивое и хочет побыстрее выйти. Если v1 будет true, то что там дальше его не будет интересовать:

if (v1 == true || v2 == true) {...}

Таким образом, если у нас есть такой код:

var v1 = CalcV1();
var v2 = CalcV2();
if (v1 == true || v2 == true) {...}

Выглядит хоть и симпатично, но совершенно непроизводительно.

Лучше писать так:

if (CalcV1() == true || CalcV2() == true) {...}

Естественнно нужно понимать, что CalcV2 вызываться не будет, если CalcV1 вернет true, поэтому не нужно на это расчитывать. Но я надеюсь, что вы это знаете :)

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

Пример:

77777
77555
75557
75577
77775

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

77777
77666
76667
76677
77775

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

Мы часто пишем подобные методы:

List<int> GetItems() {
   var items = new List<int>();
   ...
   return items; 
} 

В этом методе мы просто собираем элементы и возвращаем.

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

void GetItems(List<int> items) {
   ... 
} 

Таким образом контроль над списком может быть таким:

var list = GetFromPool();
GetItems(list);
...
ReturnToPool(list);

Когда мы начинали делать проект, в юнити не было возможности отключить Garbage Collector. А нам было нужно)

У нас геймплей был динамичный и любые "провисания" из-за gc плохо влияли на ощущения от игры. Поэтому мы решили его отключить. Раньше для этого нужно было делать хаки, а сейчас уже есть возможность это сделать нормально: https://docs.unity3d.com/Manual/performance-disabling-garbage-collection.html

В нашем кейсе в геймплее мы очень бережно относились (да и относимся) к аллокациям, всё на пулах, поэтому перед началом боя мы выключаем GC, а после боя - включаем и собираем мусор.

Такое решение на самом деле в последствии нам помогло на различных платформах в свое время: на ps4 и switch GC.Collect мог занимать до пары секунд. Надеюсь, что сейчас уже нет таких проблем, но 10 лет назад - были 🙂

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

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 в тот момент времени.

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

Destroy - это маркер, который говорит, что мы хотели бы удалить объект, но это не произойдет моментально. Юнити отложит удаление до конца кадра и он будет удален позже.

Object.Destroy(gameObject
if (gameObject != null) {
     // gameObject is alive
}

DestroyImmediate - это фактическое удаление, т.е. когда нужно удалить объект прямо здесь и сейчас.

Object.DestroyImmediate(gameObject
gameObject // тут он уже помер

Дело в том, что DestroyImmediate ломает юнити флоу, т.к. с точки зрения всех юнити-колбэков они выполнятся моментально, а не в нужном порядке, например, при использовании DefaultExecutionOrder.

При этом DestroyImmediate имеет дополнительный флаг, который позволяет убить ассет из проекта, про что стоит не забывать :)

И ремарка: Object.Destroy/Object.DestroyImmediate могут убить то, что вы туда передаете, т.е. передали компонент - убивается компонент, передали go - убивается go, текстуру - текстура и т.д. Иногда встречаю код вида Object.Destroy(component), при этом явно хотели убивать не компонент, а go.

Любой n-мерный массив можно представить в виде одномерного:

arr[x, y] = arr[x * width + y]

И да, это будет быстрее, чем двумерный массив.