Вам O(1) по памяти или по времени? По памяти (как в статье) - полно: поиск максимума в массиве, поиск двух одинаковых элементов в двух массивах можно сделать за O(n^2) по времени и O(1) по памяти. Ещё такое можно, например, нам дают массив из n элементов (n от 1 до 10^9), но сами элементы от 1 до 100. Нам надо уметь очень быстро отвечать на запросы вида "сколько элементов в этом массиве меньше или равны x". Можно отсортировать массив и отвечать за log (n), а можно собрать массив count[i]: где i - это количество сколько раз элемент встретился в массиве, а потом предподсчитать префиксную сумму count[i] = count[i] + count[i - 1]. Тогда в каждом count[i] будет ответ на вопрос сколько элементов в массиве меньших чем i. В этом алгоритме его сложность по памяти совершенно не зависит от того какой длины входной массив - мы всегда выделяем массив из 100 элементов. Это тоже O(1) по памяти. По времени тоже можно подобрать. Тут вопрос спекулятивный. Есть люди, считающие что даже сложение чисел в процессоре не O(1). В голову пришёл пример - сколько дней прошло от одной даты до другой - там O(1) по времени.
Это означает, что сложность алгоритма не зависит от размера входных данных. Это не означает, что алгоритм быстрый, это просто означает, что какого размера не были бы данными, время работы/размер дополнительной памяти алгоритма будет всегда одинаковым (грубо говоря).
Когда в 2020 году проходил собеседование в Яндекс.Дзен, то одной из секций было написание таск шедулера на неком пуле потоков в ide за ноутбуком в присутствии двух интервьюеров. История циклична.
Все эти истории я распутывал именно из-за того, что пользователи писали в саппорт о тормозах, которые невозможно терпеть. После одного из ускорений один пользователь написал, что больше не надо синхронизировать походы в туалет с запуском программы.
Не уходили они скорее по причине почти полного отсутствия конкурентов, но новые версии запросто могли перестать покупать, если они тормозят.
Как вы можете знать что надо загуглить, если не знаете о существовании проблемы? Я видел код от адептов "я всегда могу загуглить, мне не нужны алгоритмы" и они писали: * поиск 3-х максимальных элементов в массиве за O(n log n)через сортировку; * поиск ноды в дереве по заданному пути (где ребёнка можно получить за O(1) из словаря по имени) за O(n^2) памяти и O(n^2) времени от токенов в пути - сеньор-помидор с 13 лет опыта; * нужно было в дереве раскрасить ноды; раскраска ноды зависит от цветов детей. Другой сеньор-помидор каждый раз переобходил всё дерево рекурсивно без кэширования. Я исправил только это и прога стала стартовать быстрее на 15 секунд; * есть кэш на чисто вычисляемое от некоторого класса, кэш хранится в хэшмапе. Зачем-то решили, что будет круто сделать класс ключа без переопределения equals и hashCode. Кэш был, обвязка вокруг него была. Всё равно всё вокруг тормозило. Там же была уверенность, что поиск по значению в хэшмапе тоже O(1).
и таких историй могу ещё принести. Люди не натренировали свой мозг оценивать сложность алгоритмов и писать решения, которые доказано (через инварианты, а не только тесты) работают на всех возможных входных данных.
На самом деле, здесь же истории: давайте долбанём много гигантских switch case потому что я не знаю о существовании паттерна visitor. Не зная о его существовании - невозможно пойти и загуглить его описание. Автор, которые принёс на ревью эти свитчи реально был уверен, что его реализация эффективна.
Зря забросили Кормена. Он как учебник по геометрии - приводит теоремы, доказательства их, учит сводить существующие задачи к известным и доказывать корректность алгоритма. Имхо, Кормен - мастрид каждому программисту. З.Ы.: Обе задачки за 15 минут суммарно.
«Удивление» на морде кошек, поэтому, — просто реакция на неизвестный объект. Смотря сначала на то, что происходит на экране телефона, а потом на хозяина, кошка не соотносит одно и другое. Животное просто реагирует на какое-то неизвестное ей существо и, чувствуя присутствие хозяина, обращается к нему за поддержкой. Реакцию кошек даже нельзя назвать удивлением: для человека свойственно переходить к антропоцентризму и всему вокруг навязывать наши человеческие интерпретации событий, но с этим нужно быть осторожнее.
Но если итерироваться не по параметру метода, а по любому филду, который может быть изменён из другого потока, то for по массиву проигрывает foreach: пруф посмотрите на ассемблер.
В 3, NV, 4 и т.д. эта штука называется V.A.T.S. Во втором и первом она называется прицельная стрельба (aimed shot). И во втором/первом её тоже может не быть, если взять перк «Стрельба навскидку» (Fast Shot), тогда будет тратиться меньше ОД на стрельбу, но прицельная будет недоступна.
Ну и в самом деле в 3 и NV спокойно играется без VATS, т.к. он сильно упрощает там стрельбу. Вот в 1,2, наоборот, без прицельной очень сложно играется.
Университет Джона-Хопкинса выкладывает на GitHub статистику по распространению, на основе которой строит свой дашборд, который появился одним из первых. Правда там нет отдельных данных по регионам РФ.
а это разве не проверка за выход за границы? Она на каждой итерации происходит.
На самом деле там всё зависит ещё и от того массив является локальной переменной или нет, статическим филдом или нет: sharplab
Вот такой For будет самым быстрым:
int For2() {
int sum = 0;
var tmpArray = array;
for (int i = 0; i < tmpArray.Length; i++) {
sum+=tmpArray[i];
}
return sum;
}
Вы слышали про Fallout: Sonora, Fallout: Nevada, Fallout 1.5: Ressurection, Fallout 2 Restoration Project, Olympus 2207 ?
Вам O(1) по памяти или по времени?
По памяти (как в статье) - полно: поиск максимума в массиве, поиск двух одинаковых элементов в двух массивах можно сделать за O(n^2) по времени и O(1) по памяти. Ещё такое можно, например, нам дают массив из n элементов (n от 1 до 10^9), но сами элементы от 1 до 100. Нам надо уметь очень быстро отвечать на запросы вида "сколько элементов в этом массиве меньше или равны x". Можно отсортировать массив и отвечать за log (n), а можно собрать массив count[i]: где i - это количество сколько раз элемент встретился в массиве, а потом предподсчитать префиксную сумму count[i] = count[i] + count[i - 1]. Тогда в каждом count[i] будет ответ на вопрос сколько элементов в массиве меньших чем i. В этом алгоритме его сложность по памяти совершенно не зависит от того какой длины входной массив - мы всегда выделяем массив из 100 элементов. Это тоже O(1) по памяти.
По времени тоже можно подобрать. Тут вопрос спекулятивный. Есть люди, считающие что даже сложение чисел в процессоре не O(1). В голову пришёл пример - сколько дней прошло от одной даты до другой - там O(1) по времени.
Это означает, что сложность алгоритма не зависит от размера входных данных. Это не означает, что алгоритм быстрый, это просто означает, что какого размера не были бы данными, время работы/размер дополнительной памяти алгоритма будет всегда одинаковым (грубо говоря).
Тут есть про это: https://ru.wikipedia.org/wiki/Временная_сложность_алгоритма
Когда в 2020 году проходил собеседование в
Яндекс.Дзен, то одной из секций было написание таск шедулера на неком пуле потоков в ide за ноутбуком в присутствии двух интервьюеров.История циклична.
Все эти истории я распутывал именно из-за того, что пользователи писали в саппорт о тормозах, которые невозможно терпеть. После одного из ускорений один пользователь написал, что больше не надо синхронизировать походы в туалет с запуском программы.
Не уходили они скорее по причине почти полного отсутствия конкурентов, но новые версии запросто могли перестать покупать, если они тормозят.
Как вы можете знать что надо загуглить, если не знаете о существовании проблемы?
Я видел код от адептов "я всегда могу загуглить, мне не нужны алгоритмы" и они писали:
* поиск 3-х максимальных элементов в массиве за O(n log n)через сортировку;
* поиск ноды в дереве по заданному пути (где ребёнка можно получить за O(1) из словаря по имени) за O(n^2) памяти и O(n^2) времени от токенов в пути - сеньор-помидор с 13 лет опыта;
* нужно было в дереве раскрасить ноды; раскраска ноды зависит от цветов детей. Другой сеньор-помидор каждый раз переобходил всё дерево рекурсивно без кэширования. Я исправил только это и прога стала стартовать быстрее на 15 секунд;
* есть кэш на чисто вычисляемое от некоторого класса, кэш хранится в хэшмапе. Зачем-то решили, что будет круто сделать класс ключа без переопределения equals и hashCode. Кэш был, обвязка вокруг него была. Всё равно всё вокруг тормозило. Там же была уверенность, что поиск по значению в хэшмапе тоже O(1).
и таких историй могу ещё принести. Люди не натренировали свой мозг оценивать сложность алгоритмов и писать решения, которые доказано (через инварианты, а не только тесты) работают на всех возможных входных данных.
На самом деле, здесь же истории: давайте долбанём много гигантских switch case потому что я не знаю о существовании паттерна visitor. Не зная о его существовании - невозможно пойти и загуглить его описание. Автор, которые принёс на ревью эти свитчи реально был уверен, что его реализация эффективна.
В первой очень простые ограничения. Там Беллман-Форд заходит, а пишется он, имхо, легче.
Зря забросили Кормена. Он как учебник по геометрии - приводит теоремы, доказательства их, учит сводить существующие задачи к известным и доказывать корректность алгоритма. Имхо, Кормен - мастрид каждому программисту.
З.Ы.: Обе задачки за 15 минут суммарно.
Hidden text
Во второй топологическую сортировку надо.
https://nplus1.ru/blog/2019/11/18/cats-and-mirrors
Потому что в общем виде это не совсем так.
пруф посмотрите на ассемблер.
Ну и в самом деле в 3 и NV спокойно играется без VATS, т.к. он сильно упрощает там стрельбу. Вот в 1,2, наоборот, без прицельной очень сложно играется.
Яндекс.Бар релизнули 15 ноября 2000 года (https://yandex.ru/company/press_releases/2000/11-15_00), а Google Toolbar — 11 декабря 2000 года (https://en.wikipedia.org/wiki/Google_Toolbar).
Кроме того, поиск по картинкам показал что гугл отдельно свой тулбар тоже продвигал, причём стоит оценить где:
www.itwriting.com/blog/3014-oracle-still-foisting-google-toolbar-on-java-users.html
Вот на такой строке не сработает
Надо использовать System.Globalization.StringInfo.
products.aspose.com/cells/family
L0023: jg L0013
а это разве не проверка за выход за границы? Она на каждой итерации происходит.
На самом деле там всё зависит ещё и от того массив является локальной переменной или нет, статическим филдом или нет:
sharplab
Вот такой For будет самым быстрым:
А вообще я люблю побенчмаркать разное и разобраться почему так, собираю интересности в один гист, там и for/foreach для массива есть: gist.github.com/tdkkdt/420422f2eee1c15393d383ba7c8d1b9a