Comments 10
В формальном определении вы забыли пояснить что такое n, а без этого определение не определение. Объяснение на примерах возможно, но не круто.
Хэш от значения это все же ещё не индекс в массиве, как это выглядит в вашем объяснении.
Queryable на собесах это обычно IQueryable и это уже о другом, а не о linq.
Говорить о сложности count в общем смысле немного странно, если мы не говорим как оно будет вычистяться.
В реальном проекте с вероятностью 99 процентов вы не увидите ничего кроме list, dictionary и hashset. Ну может ещё ConcurrentDictionary.
В общем не проходит статья собес на джуна в итоге.
Ничего себе у вас требования к джунам. :) Я бы наоборот взял - человек хотя бы разбирался, пусть даже и споткнулся где-то в деталях.
Если вы имели в виду "на сеньора", то соглашусь.
n - это аргумент, там же написано очень много раз, что это размер данных.
Про queryable указано лишь для того, что если нужна коллекция для чтения, перебора в foreach и фильтрации/сортировки/выборки, то лучше взять тип IEnumerable + LINQ, а не List, например.
Там написано, что хеш-функция рассчитывается от значения ключа, и это значение полученной хеш-функции является индексом, по которому хранится значение. Это одна из возможных реализаций хеш-таблицы.
Приятнее когда кандидат начинает с того, что алгоритм обрабатывает некие данные, в которых можно указать количество элементов. Тогда сложность алгоритма - это время выполнения в зависимости от этого количества элементов.
Про queryable указано лишь для того, что если нужна коллекция для чтения, перебора в foreach и фильтрации/сортировки/выборки, то лучше взять тип IEnumerable + LINQ, а не List, например.
Вот это вообще непонятно. Лучше то что лучше в данной ситуации. А IQueryable появляется когда появляется внешний источник данных и ExpressionTree. Linq работает с IEnumarable а не IQueryable.
Там написано, что хеш-функция рассчитывается от значения ключа, и это значение полученной хеш-функции является индексом, по которому хранится значение.
Хэш от ключа, это просто большое целое число. Чтобы вычислить индекс с массиве нужно еще поделить и взять остаток.
Быстрый поиск и извлечение данных:
А от чего не упомянули FrozenDictionary<TKey,TValue> и FrozenSet<T>? Они же созданные именно для поиска элементов.
Хотя мне больше интересно как определение сложность поможет оценить скорость выполнения или затраты по мапяти, если детали реализации того или иного метода могут изменяться от версии к версии .NET, не считая использования векторизации в методах LINQ, которых прибавляется с каждой версией .NET?
В моей голове это очевидно - для упрощения сложности (например для перехода от N^2 к N или log N) потребуется больше памяти (без деталей), но это уменьшит время за счёт как раз таки определения\упрощения сложности.
В этом суть математики - абстрагирование от деталей. Математика вводит О() нотацию в которой сложность алгоритма может бы оценена независимо от деталей реализации или даже языка программирования.
Linq в любом случае работает так, чтобы класс сложности использованного алгоритма был оптимальным. В рамках концепции сложности только это нас интересует.
Существует ли плагин подсказывающий оценочно в баллах насколько усложнен метод? Видел подобное для ангуляра, но там были обидные комментарии, если переборщить со вложенностью :)
Что нужно знать при написании алгоритмов на .NET