Комментарии 57
T=1.6*n^2 * [мин/Гб^2]
Решение же очевидно — очистить этот репозиторий нахрен n->min.
winmgmt /salvagerepository
winmgmt /resetrepository
Как линейное время превращается в Windows в O(n²)
Никак. Линейное время всегда O(n^2).
Функция f входит в множество O(n2), если существует константа C и номер N, такие что для любых n > N верно |f(n)| < C*n2.
В этом смысле, любая функция из множества O(n) также принадлежит множеству O(n2), т.е. множество O(n) является подмножеством O(n2).
Более формально правильным названием статьи было бы «Как линейное время превращается в Ω(n^2)», т.к. Ω — это наоборот, нижняя граница. Другое дело, что на практике часто всё-таки на такие различия между обозначениями внимания не обращают.
Какое утверждение вы пытаетесь сделать
Тот же вопрос хочется задать и вам. Если вы хотели сообщить, что знаете о существовании не только «O» большого, но и о других обозначениях асимптотики, то так и надо было говорить. Но это необязательно, ибо статья не замахивается на роль труда по теории алгоритмов, а в жизни все используют «О» большое для примерного обозначения сложности и не заморачиваются.
Тот же вопрос хочется задать и вам.
Я не спрашивал вас о том, чего вам хочется. Если вам непонятен смысл моего вопроса, попробуйте прочесть его повторно проверяя непонятные вам слова в толковом словаре.
А вопросы надо задать в той форме, чтобы на них было, что ответить.
> Практический же — что не просто выполняется неравенство, но и нет более адекватной оценки, то есть если пишут O(n^2), то O(n log n), O(n) и т.п. не подходят.
Твое указание на то, что O(n^2) в академическом понимании включает в себя в том числе линейную сложность, кстати, также абсолютно ничего не добавляет полезного к статье. Ибо все поняли, что O(n^2) в данном контексте указывает на сложность квадратическую.
Ты своим комментарием, очевидно, пытаешься показать, что знаешь академическое определение «О» большого.
Ложь. Можешь в качестве доказательства привести скриншотик моего комментария, не забыв подчеркнуть красным те слова, которые по твоему мнению пытаются это показать. Ну или можешь прочесть комментарий и попробовать понять его, в конце-концов.
если пишут O(n^2), то O(n log n), O(n) и т.п. не подходят.
Не «не подходят», а «неизвестно». Для того, чтобы показать, что они не подходят, есть нотация Ω(n).
Твое указание на то, что O(n^2) в академическом понимании включает в себя в том числе линейную сложность, кстати, также абсолютно ничего не добавляет полезного к статье.
Опять ты читаешь мой комментарий и не понимаешь смысл. Я не указываю на то, о чём ты пишешь. Я указываю на допущенную автором при использовании формальной нотации ошибку.
Когда ты беседуешь в курилке с мужиками, говори как угодно — хоть просто «эн квадрат». Когда ты пишешь статью на более-менее серьёзном ресурсе — используй нотацию правильно. Или ты назовёшь системный блок процессором в своей статье? Тоже ведь будет всем понятно что ты имел в виду, да? Однако некорректное использование терминологии кое-что скажет твоим читателям о тебе. Если конкретно для тебя это неважно — это не значит что мой комментарий не имеет смысла.
Мне этот практический подход больше импонирует потому, что даёт оценку полезности лучше, чем формальный :) Иногда нельзя по этому принципу сравнить два подхода, или две оценки, но это таки редко.
К сожалению, другие обозначения из этой серии не дают нужного. Θ — не учитывает случаи, когда в результате счастливого попадания в «мягкий» вариант затраты оказались меньше. Например, пусть мы знаем, что ни один элемент не отстоит больше чем на 10 позиций от своей позиции после сортировки; тогда пузырёк и вставки будут O(n), но это 10 будет заложено в C. Ω — ещё хуже — жёсткая нижняя оценка или не подходит вообще, или не имеет смысла.
Так что приходиться довольствоваться «внешним» по отношению к самому знаку пониманием «нет более сильной оценки» или «оценка достаточно сильна для наших целей».
Не предел, а при x больше некоторого (если рассматриваем стремление к бесконечности, как нужно для алгоритмов в CS) или ближе некоторого ε (как в математике). Это условие я пропустил как наверняка очевидное участникам дискуссии.
> Вопрос амортизированных/лучших/худших случаев уже куда интереснее, да.
Угу. Тут поэтому давно назрело как-то уточнить символы, пока же используются словесные добавления.
Как злобный пример — стоимость вставки в хэш-таблицу классической закрытой адресации. Формально O(1), но амортизированное O(1). GCC STL, Java и прочие — что, таки писать, что O(n)? Так неэффективно для (n-1)/n (условно) случаев, когда ресайзинга нет. O(1)? Неверно для случая ресайзинга.
Остаётся писать: Θ(1) без ресайзинга и Θ(n) с оным. Мне эти муки выбора напомнили анекдот про Хрущёва среди свиней…
(Disclaimer: переполнение одной корзины в хэш-таблице не учитываем, а то и в этом случае Θ(n) получится. А счастье было так близко.)
Интересно, опишите тогда квадратичное время
Если в рабочее время, так это может быть куда интереснее обычной работы. Только вот коллег отвлекает...
/verifyrepository
Performs a consistency check on the WMI repository. When you add the /verifyrepository switch without the argument, then the live repository currently used by WMI is verified.
Антивирусами проверял — тишина. В следующий раз попробую провести расследование по описанной схеме.
для начала журнал событий посмотреть, у меня в таких случаях обычно была проблема с дисками.
Машина рабочая, перегружается редко, описанное поведение наблюдается 1-2 раза в неделю и ничем не лечится до перезагрузки. Последние 3 дня, например, всё в порядке.
Больше всего удивляет тишина в диспетчере задач — загрузка процессора — единицы процентов, а всё тормозит. Загрузку дисков тоже смотрел и расследовал — не нашёл ничего заслуживающего внимания.
Что-то мне это так не понравилось — кому понравятся оставшиеся куски памяти от сотен тысяч процессов одного и того же модуля — пошел гуглить имя процесса, смутно ощущая, что я про что-то вот прям похожее читал на хабре. И точно!
Именно та же картина: за три дня после перезагрузки счетчик хендлов (смотрел в sysinternals process manager) уехал за 300000. Приложение прибил, количество хэндлов в системе за несколько секунд упало до 167000.
В сервисах нашел эту дрянь, но gui изменить тип запуска не дает, так что изменил в реестре (HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SynTPEnhService) значение Start с 2 (авто) на 4 (запрет).
Через несколько месяцев, правда, оно вернулось. Просто повторил, пока полет нормальный.
О, долго мучился с такой-же проблемой. Даже систему переустанавливал и начал уже грешить на железо, как тут выше многие советуют. Но смущало все же то, что во-первых в журнале событий все чинно, а во-вторых, ubuntu на той-же машине работала без нареканий (на подвисания во всяком случае).
Собственно, эта статья и вдохновила разобраться таки в причинах этого безобразия с помощью ETW/xperf.
В общем, в моем случае тригерром подвисаний стала комбинация из нескольких вещей:
- При смене темы оформления в процессе explorer-а лочится UI поток.
- Смена цвета акцента означает смену темы оформления
- В настройках персонализации стояла галочка automatically pick an accent color from my background
- Там же в качестве фона было выбрано слайд-шоу со сменой картинки каждую минуту.
Собственно, дальше уже наверное понятно, что происходило. Каждую минуту смена фона раб. стола запускала цепочку "смена фона -> смена цвета акцента -> смена темы -> блокировка UI потока эксплорера -> фризы и подвисания всего UI".
Я конечно допускаю, что первоисточник проблемы может быть и не в этом, а где-то глубже. Ибо после перезагрузки подвисало намного меньше, чем после десятков часов работы, и на чистой системе до установки всего софта тоже сильных подвисаний вроде бы замечено не было. Но глубже копать у меня уже мотивации не было, т.к. проблема ушла после снятия одной галочки, а весь установленный софт мне все равно нужен для работы.
В общем,
TLDR; Если включена смена фонов рабочего стола и выбор цвета акцента в зависимости от фона — попробуйте что-то из этого отключить.
Последнюю неделю тормоза не выплывали ни разу. Не знаю точно с чем связано — слишком много переменных. Во-первых отключил (как минимум временно) Windows Defender. Периодически наблюдал, что он на постоянку выжирает 30-40% CPU, правда его временное отключение ситуации с тормозами не меняло, но не уверен. Во-вторых за неделю несколько раз накатывались апдейты на винду и студию, приходилось перезагружаться.
Продолжаю наблюдение.
Из того что конкретно напрягало — заметные лаги в Visual Studio, и в целом система стала плохо отзывчивой.
Запустил Performance Analyzer и начал эмпирическим путём искать подозрительные вещи.
Из того, что привлекло внимание — MS Outlook заспамил вкладку Thread: Set Ideal Processor, при том, что я с ним не работал. Сама загрузка процессора аутлуком минимальна, но количество событий большое и постоянное. Процессы, связанные с Visual Studio бросают события только в момент работы с ними, а вот именно Outlook спамит без передышки.
После того, как закрыл его — все лаги как рукой сняло.
Дальше пока не разбирался, появится время — более детально гляну отчёт.
помогло вот это (чего-то делалось минут 5-7, в командной строке только росли проценты завершения):
Нажмите Win+X,
выберите командная строка(администратор) или PowerShell(администратор).
В открывшемся окне напечатайте
Dism /Online /Cleanup-Image /RestoreHealth и нажмите Enter.
Дождитесь окончания этой команды.
Сообщите результат.
Напечатайте sfc /scannow и нажмите Enter.
Источник <answers.microsoft.com/ru-ru/windows/forum/all/%D0%B2-windows-10-1809-%D0%BD%D0%B5/a4302417-cb72-4f35-84a3-069abec622a6>
Любопытно, что 1,6 — это приблизительное значение золотого сечения
Возможно, им просто не приходит к голову запускать раз в час проверку репозитория. Я так не понял из статьи, зачем это было сделано.
А это не дефолтное поведение Винды? Надо бы в Планировщике такую задачу поискать.
Так проблема не в репе, а в алгоритмах что ее смотрят. Возможно хеши считаются каждый раз на каждый файл перед сверкой со следующим файлом, а может и еще чего. По крайней мере сверка "каждый с каждым" очень хорошо подходит и под определение репы, и под n^2
Как линейное время превращается в Windows в O(n²)