Как стать автором
Обновить

Комментарии 57

T=1.6*n^2 * [мин/Гб^2]

Решение же очевидно — очистить этот репозиторий нахрен n->min.

winmgmt /salvagerepository
winmgmt /resetrepository
Ну да — чуть что — переустанавливай Windows.
Как линейное время превращается в Windows в O(n²)

Никак. Линейное время всегда O(n^2).
O(n) смотрит на эту реплику с недоумением.
Нет, O(n) смотрит на эту реплику и соглашается с ней.
Функция f входит в множество O(n), если существует константа C и номер N, такие что для любых n > N верно |f(n)| < C*n.
Функция f входит в множество O(n2), если существует константа C и номер N, такие что для любых n > N верно |f(n)| < C*n2.
В этом смысле, любая функция из множества O(n) также принадлежит множеству O(n2), т.е. множество O(n) является подмножеством O(n2).
Не могу понять, толлинг ли это, или вы серьезно. Но на всякий случай, вот вам википедия и
скриншотик с нее


Вы оба правы — линейная время это время O(n), но ведь любая функция из класса O(n) также входит в класс O(n^2) и например O(2^n). Просто само обозначение O(...) — это верхняя граница.
Более формально правильным названием статьи было бы «Как линейное время превращается в Ω(n^2)», т.к. Ω — это наоборот, нижняя граница. Другое дело, что на практике часто всё-таки на такие различия между обозначениями внимания не обращают.
Вроде для этого есть o(n^2), что по хорошему и нужно было использовать в этой статье, но видимо на матчасть редко обращают внимание судя по минусам у поста.
Спасибо за пояснение.
Различия между обозначениями в нотации bigO хорошо описаны например в Кормане
Я думаю, что он имеет ввиду то, что с формальной точки зрения все, что принадлежит O(n), так же принадлежит O(n^2). Другое дело, что если мы знаем, что алгоритм линейный, то мы опишем его как O(n), а не O(n^2), т.к. это более содержательное описание.
НЛО прилетело и опубликовало эту надпись здесь
Какое утверждение вы пытаетесь сделать и как оно следует из приведённой статьи?
Какое утверждение вы пытаетесь сделать

Тот же вопрос хочется задать и вам. Если вы хотели сообщить, что знаете о существовании не только «O» большого, но и о других обозначениях асимптотики, то так и надо было говорить. Но это необязательно, ибо статья не замахивается на роль труда по теории алгоритмов, а в жизни все используют «О» большое для примерного обозначения сложности и не заморачиваются.
Тот же вопрос хочется задать и вам.

Я не спрашивал вас о том, чего вам хочется. Если вам непонятен смысл моего вопроса, попробуйте прочесть его повторно проверяя непонятные вам слова в толковом словаре.
Друг, вот зря ты тратишь свою возможность комментирования раз в час на такие бессмысленные пассивно-агрессивные высказывания. Так и до комментария раз в день недолго.
А вопросы надо задать в той форме, чтобы на них было, что ответить.
Мужик, ты мне не друг и твоё мнение о моих возможностях меня не интересует. А на вопрос надо ответить ровно то, что ты пытался донести приводя ссылки на википедию и подчёркивая красным в скриншотике. Ибо на данный момент кроме определений терминов твой комментарий ничего не доводит; к тому комментарию, на который ты ответил, ничего не добавляет, не противоречит и не соглашается. Т.е. твой комментарий попросту не имеет смысла в контексте обсуждения. И как я понимаю, смысл уже не появится.
Окей, недруг, пытаюсь объяснить ещё раз. Ты своим комментарием, очевидно, пытаешься показать, что знаешь академическое определение «О» большого. Это круто, конечно. Но статья явно не замахивалась на академический труд. Позволю процитировать комментарий netch80 о практическом использовании нотации «О» большого:

> Практический же — что не просто выполняется неравенство, но и нет более адекватной оценки, то есть если пишут 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) в академическом понимании включает в себя в том числе линейную сложность, кстати, также абсолютно ничего не добавляет полезного к статье.

Опять ты читаешь мой комментарий и не понимаешь смысл. Я не указываю на то, о чём ты пишешь. Я указываю на допущенную автором при использовании формальной нотации ошибку.

Когда ты беседуешь в курилке с мужиками, говори как угодно — хоть просто «эн квадрат». Когда ты пишешь статью на более-менее серьёзном ресурсе — используй нотацию правильно. Или ты назовёшь системный блок процессором в своей статье? Тоже ведь будет всем понятно что ты имел в виду, да? Однако некорректное использование терминологии кое-что скажет твоим читателям о тебе. Если конкретно для тебя это неважно — это не значит что мой комментарий не имеет смысла.
Есть таки два понимания знака O(), формальный и практический. Формальный — что f(x) = O(g(x)) означает, что f(x) <= C*g(x), тогда линейное C*n безусловно O(n^2). Практический же — что не просто выполняется неравенство, но и нет более адекватной оценки, то есть если пишут O(n^2), то O(n log n), O(n) и т.п. не подходят.

Мне этот практический подход больше импонирует потому, что даёт оценку полезности лучше, чем формальный :) Иногда нельзя по этому принципу сравнить два подхода, или две оценки, но это таки редко.

К сожалению, другие обозначения из этой серии не дают нужного. Θ — не учитывает случаи, когда в результате счастливого попадания в «мягкий» вариант затраты оказались меньше. Например, пусть мы знаем, что ни один элемент не отстоит больше чем на 10 позиций от своей позиции после сортировки; тогда пузырёк и вставки будут O(n), но это 10 будет заложено в C. Ω — ещё хуже — жёсткая нижняя оценка или не подходит вообще, или не имеет смысла.

Так что приходиться довольствоваться «внешним» по отношению к самому знаку пониманием «нет более сильной оценки» или «оценка достаточно сильна для наших целей».
НЛО прилетело и опубликовало эту надпись здесь
> Не совсем, там предел при x к бесконечности.

Не предел, а при x больше некоторого (если рассматриваем стремление к бесконечности, как нужно для алгоритмов в CS) или ближе некоторого ε (как в математике). Это условие я пропустил как наверняка очевидное участникам дискуссии.

> Вопрос амортизированных/лучших/худших случаев уже куда интереснее, да.

Угу. Тут поэтому давно назрело как-то уточнить символы, пока же используются словесные добавления.
Как злобный пример — стоимость вставки в хэш-таблицу классической закрытой адресации. Формально O(1), но амортизированное O(1). GCC STL, Java и прочие — что, таки писать, что O(n)? Так неэффективно для (n-1)/n (условно) случаев, когда ресайзинга нет. O(1)? Неверно для случая ресайзинга.
Остаётся писать: Θ(1) без ресайзинга и Θ(n) с оным. Мне эти муки выбора напомнили анекдот про Хрущёва среди свиней…
(Disclaimer: переполнение одной корзины в хэш-таблице не учитываем, а то и в этом случае Θ(n) получится. А счастье было так близко.)
НЛО прилетело и опубликовало эту надпись здесь

Предела может не существовать, но "О большому" это не помешает. К примеру, можно написать что sin n = O(1)

НЛО прилетело и опубликовало эту надпись здесь

Интересно, опишите тогда квадратичное время

Согласно «скриншотику с википедии» квадратичное время — это O(n^2). Т.е. это любая функция от n, для которой можно указать такую константу C, что начиная с некоторого n_0 значение функции не будет превышать C n^2.
А мужик крут, потратил столько времени на поиск баги в Windows, написал об этом статью. А проблема в своём репозитории… Да кому она интересна?

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

Не в своём. Этот репозиторий — часть WMI — подсистемы Windows. Вот кусочек из документации, касающейся указанной в статье команды:
/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.
НЛО прилетело и опубликовало эту надпись здесь

Я думаю вы недостаточно часто пересобираете хром из сорцов

НЛО прилетело и опубликовало эту надпись здесь
Да, что-они там химичат сами в гугле. У меня корпоративаня машина со всеми вытекающими. Вин10 стоит с самого релиза. При этом размер папки 120МБ
В последнее время замечаю, что десятка начинает тупить. Тупит просто всё — даже курсор мышки передвигается рывками. В диспетчере задач всё глухо — загрузка минимальная. При этом железо достаточно свежее — шестиядерный i5-8400, 32 Gb RAM. Закрываю браузер, стопаю машины на локальном Hyper-V — лучше не становится. После перезагрузки всё опять нормально.
Антивирусами проверял — тишина. В следующий раз попробую провести расследование по описанной схеме.
если курсор мыши в винде передвигается рывками, надо начинать думать на железо
для начала журнал событий посмотреть, у меня в таких случаях обычно была проблема с дисками.
Это просто windows вам так намекает, что пора обновлять железо.
Мышь беспроводная?
Нет, дело точно не в мыши (да и проводная она). Я ведь тоже не первый день с компьютерами. Тормоза точно на уровне винды — рывки курсора — это только одно из проявление. Помимо этого есть задержки на открытии меню «пуск», диспетчера задач и т.д.
Машина рабочая, перегружается редко, описанное поведение наблюдается 1-2 раза в неделю и ничем не лечится до перезагрузки. Последние 3 дня, например, всё в порядке.
Больше всего удивляет тишина в диспетчере задач — загрузка процессора — единицы процентов, а всё тормозит. Загрузку дисков тоже смотрел и расследовал — не нашёл ничего заслуживающего внимания.
Температуру моста проверьте.
Ровно те же симптомы были. Запустил я (уже после перезагрузки) rammap, а там в выделенных кусочках памяти
вот такая прелесссть:
image

Что-то мне это так не понравилось — кому понравятся оставшиеся куски памяти от сотен тысяч процессов одного и того же модуля — пошел гуглить имя процесса, смутно ощущая, что я про что-то вот прям похожее читал на хабре. И точно!

Именно та же картина: за три дня после перезагрузки счетчик хендлов (смотрел в sysinternals process manager) уехал за 300000. Приложение прибил, количество хэндлов в системе за несколько секунд упало до 167000.

В сервисах нашел эту дрянь, но gui изменить тип запуска не дает, так что изменил в реестре (HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SynTPEnhService) значение Start с 2 (авто) на 4 (запрет).

Через несколько месяцев, правда, оно вернулось. Просто повторил, пока полет нормальный.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь

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


  1. При смене темы оформления в процессе explorer-а лочится UI поток.
  2. Смена цвета акцента означает смену темы оформления
  3. В настройках персонализации стояла галочка automatically pick an accent color from my background
  4. Там же в качестве фона было выбрано слайд-шоу со сменой картинки каждую минуту.

Собственно, дальше уже наверное понятно, что происходило. Каждую минуту смена фона раб. стола запускала цепочку "смена фона -> смена цвета акцента -> смена темы -> блокировка UI потока эксплорера -> фризы и подвисания всего UI".


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


В общем,
TLDR; Если включена смена фонов рабочего стола и выбор цвета акцента в зависимости от фона — попробуйте что-то из этого отключить.

Нет, у меня на рабочем столе Стармен на фоне Земли, давно уже.
Последнюю неделю тормоза не выплывали ни разу. Не знаю точно с чем связано — слишком много переменных. Во-первых отключил (как минимум временно) Windows Defender. Периодически наблюдал, что он на постоянку выжирает 30-40% CPU, правда его временное отключение ситуации с тормозами не меняло, но не уверен. Во-вторых за неделю несколько раз накатывались апдейты на винду и студию, приходилось перезагружаться.
Продолжаю наблюдение.
Довольно долго тормоза не проявлялись, но вот только что поймал те же симптомы.
Из того что конкретно напрягало — заметные лаги в Visual Studio, и в целом система стала плохо отзывчивой.
Запустил Performance Analyzer и начал эмпирическим путём искать подозрительные вещи.
Из того, что привлекло внимание — MS Outlook заспамил вкладку Thread: Set Ideal Processor, при том, что я с ним не работал. Сама загрузка процессора аутлуком минимальна, но количество событий большое и постоянное. Процессы, связанные с Visual Studio бросают события только в момент работы с ними, а вот именно Outlook спамит без передышки.
После того, как закрыл его — все лаги как рукой сняло.
Дальше пока не разбирался, появится время — более детально гляну отчёт.
Постоянная активность MS Outlook

Тупил интернет, радио онлайн начинало заикаться через 30-40 минут, перегрузка — 30-40 минут нормально, потом опять заики.
помогло вот это (чего-то делалось минут 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 — это приблизительное значение золотого сечения

Больше интересно другое. Сами разработчики windows, выходит, не сталкиваются с этой проблемой при сборках своих продуктов, так? Или они никогда не собирают на своих машинах?
Лет десять назад писали, что сборка Windows идёт на серверной ферме раз в неделю.
НЛО прилетело и опубликовало эту надпись здесь

Возможно, им просто не приходит к голову запускать раз в час проверку репозитория. Я так не понял из статьи, зачем это было сделано.

А это не дефолтное поведение Винды? Надо бы в Планировщике такую задачу поискать.

Не вижу у себя такой задачи.


Для дефолтного поведения это очень странная идея: WMI Repository обновляется, как правило, только с обновлениями винды. Зачем его вообще проверять раз в час?

Так проблема не в репе, а в алгоритмах что ее смотрят. Возможно хеши считаются каждый раз на каждый файл перед сверкой со следующим файлом, а может и еще чего. По крайней мере сверка "каждый с каждым" очень хорошо подходит и под определение репы, и под n^2

Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории