Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 60
Я извиняюсь, но что такое O( )?
Оценка сложности алгоритма ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое
Простите, вот правильная ссылка «O»_большое_и_«o»_малое
А что здесь делают выпускники Щукинского театрального?
А остальное всё понятно?
Стоит слегка прояснить ситуацию для тех кто не в теме:
CSS правила читаются справа налево — и чем меньше элементов попадает под самый правый селектор, тем лучше, плюс еще надо учитывать скорость работы самого селектора, где #id < .class < tag (не берем старый IE в расчет)
Термин «специфичность селектора» вроде как уже закреплен за вычислением приоритета селектора вида (X,Y,Z)
CSS правила читаются справа налево — и чем меньше элементов попадает под самый правый селектор, тем лучше, плюс еще надо учитывать скорость работы самого селектора, где #id < .class < tag (не берем старый IE в расчет)
Термин «специфичность селектора» вроде как уже закреплен за вычислением приоритета селектора вида (X,Y,Z)
Что такое «скорость работы самого селектора» и это вот "#id < .class < tag"?
Наверное это скорость нахождения элемента по определенному селекотру а "#id < .class < tag"? наверное значит: что по ИД будет искаться наиболее быстро, потом по классу, а потом по имени тэга
td { color:red } и #id { color:red } имеют в принципе одну и ту же сложность. Если представить что DOM элемент внутри выглядит как-то так:struct Element {
symbol_t tag;
symbol_t id;
...
}(symbol_t это int) то сравнение с id и сравнение с tag идентично.
Честно говоря не знаю откуда эта «мулечка» про "#id < .class < tag" появилась.
То что id нужен один только, а теги все нужно перебирать на скорость разве не влияет?
Ну во первых никто не гарантирует что элемент с данным id он один. Уникальность id это рекомендация. Не более.
С точки зрения CSS id это такой же атрибут как и любой другой. Просто #id селектор имеет больший вес. Все CSS имплементации раcсчитанны на «неуникальность» ID.
Про скорость. Представь себе документ в начальном состоянии. Расчет стилей в этом случае это все те же O(N*S*D). id никак не помогают.
С точки зрения CSS id это такой же атрибут как и любой другой. Просто #id селектор имеет больший вес. Все CSS имплементации раcсчитанны на «неуникальность» ID.
Про скорость. Представь себе документ в начальном состоянии. Расчет стилей в этом случае это все те же O(N*S*D). id никак не помогают.
Не гарантирована уникальность id, да. Но неужели настолько много страниц, где половина элементов с одним id, что никто не делает по нему индекс?
Ну мне кажется, что всё-равно придётся перебирать все элементы
Индекс по ID нужен для эффективного исполнения функции
Если же у тебя есть, скажем, такие CSS правила
и ты меняешь класс у body c mode1 на mode2 то ты просто обязан пересчитать все стили внутри body. При этом есть у элемента ID или нет — не важно абсолютно.
getElementByID().Если же у тебя есть, скажем, такие CSS правила
body.mode1 #one { color:red }
body.mode2 #one { color:green }
body.mode1 a { color:blue }
body.mode2 a { color:orange }и ты меняешь класс у body c mode1 на mode2 то ты просто обязан пересчитать все стили внутри body. При этом есть у элемента ID или нет — не важно абсолютно.
Интересный-то случай — это когда там не только
#one, но и т.д. до #forty-two, правильно? А составление индекса и S обращений к нему (с перебором предков или без такового) — совсем не то же, что S полных переборов (которые подразумевает Ваша формула для общего случая с N*S).Давай представим такой документ
И набор правил
Для определения полной картины нужно пройтись по всем N=10 элементам и последовательно проверить оба селектора (S=2).
Итого строго по формуле O(N*S*D) -> 10*2*1 = 20 операций проверки селекторов.
Никакие индексы тут не помогут.
<div #n0>0</div> <div #n1>1</div> <div #n2>2</div> <div #n3>3</div> ... <div #n9>9</div>
И набор правил
div { background:gold; }
#n1 { color:red; }
Для определения полной картины нужно пройтись по всем N=10 элементам и последовательно проверить оба селектора (S=2).
Итого строго по формуле O(N*S*D) -> 10*2*1 = 20 операций проверки селекторов.
Никакие индексы тут не помогут.
Взорвать-то получилось? Покажите пример css с экспоненциальной сложностью
Рекомендации отличные. Google Page Speed говорит то же самое.
Хочу большего раскрытия темы. Не могли бы вы показать, например, алгоритм назначения стилей? В псевдокоде хотя бы. Плюс хочется узнать про другие оптимизации. Сейчас, как я понимаю, для каждого элемента DOM просматривается список стилей. Не думаю, что это делается полным его перебором. В одной из реализаций HTML-движка (Cobra), при парсинге CSS правила сразу разделяются на правила для элемента, для класса и для id (правая часть селектора) и перебор делается уже в одной из этих трех категорий.
Дальше интересует порядок назначения стилей. Что id-стиль имеет больший приоритет, чем class, а псевдокласс — еще больше (?). Напоследок хочу заметить, что по-идее, каждый элемент имеет стили по-умолчанию от браузера (имеющие наименьший приоритет).
Дальше интересует порядок назначения стилей. Что id-стиль имеет больший приоритет, чем class, а псевдокласс — еще больше (?). Напоследок хочу заметить, что по-идее, каждый элемент имеет стили по-умолчанию от браузера (имеющие наименьший приоритет).
Рекомендую прочитать статью и комментарии к ней web-standards.ru/articles/parent-selector/
Статью прочитал, но не увидел ответов на свои вопросы. Заметка интересна, скорее верстальщикам крупных порталов (см. последние два коммента там). Я же интересуюсь общими особенностями работы со стилями.
Конкретно мне надо сделать применение MapCSS. Специфика там другая, но знать как это делается для «обычного» CSS было бы весьма полезно.
Конкретно мне надо сделать применение MapCSS. Специфика там другая, но знать как это делается для «обычного» CSS было бы весьма полезно.
Алгоритм прост и изложен здесь www.w3.org/TR/CSS2/cascade.html#cascade
Есть набор из S правил (selector/properties). Этот набор сортируется по selector specificity.
И для каждого DOM элемента n просматриваются все S правил в указаном порядке.
Для составных селекторов сначала проверяется самый правый селектор и далее справа налево по цепочке parents.
С точки зрения CPU эти вот два селектора:
имеют одинаковую сложность (у меня это сравнение двух int).
А селектор:
несколько более сложен для определения(у меня это — поиск int в массиве int)
Есть набор из S правил (selector/properties). Этот набор сортируется по selector specificity.
И для каждого DOM элемента n просматриваются все S правил в указаном порядке.
Для составных селекторов сначала проверяется самый правый селектор и далее справа налево по цепочке parents.
С точки зрения CPU эти вот два селектора:
td { color:red }
#id { color:red } имеют одинаковую сложность (у меня это сравнение двух int).
А селектор:
.cls1 { color:red } несколько более сложен для определения(у меня это — поиск int в массиве int)
имеют одинаковую сложность (у меня это сравнение двух int).
у вас СВОЙ движок???
Ну да. Sciter и HTMLayout используют мой h-smile core.
Ответ на вопрос о приоритетах селекторов: www.w3.org/TR/selectors/#specificity
+ картинка в тему:
(частично отвечает на вопрос).
+ картинка в тему:
(частично отвечает на вопрос).
Точно ли производится сравнение каждого dom-элемента с каждым селектором? Может быть, в каких-то случаях наоборот все же?
Просто логика подсказывает, что процентное соотношение элементов, совпавших хоть с каким-то селектором, длвольно мало. Соответственно, может иметь смысл отталкиваться именно от селектора, а не от dom. И кажется, что задача найти все подходящие селектору элементы в большинстве случаев хорошо укладывается в индексы.
Просто логика подсказывает, что процентное соотношение элементов, совпавших хоть с каким-то селектором, длвольно мало. Соответственно, может иметь смысл отталкиваться именно от селектора, а не от dom. И кажется, что задача найти все подходящие селектору элементы в большинстве случаев хорошо укладывается в индексы.
WebKit например вообще не поддерживает динамические атрибут-селекторы.
А вы ничего не путаете? Я этим успешно пользуюсь в OS X приложении с встроенным WebView, все работает.
А вы ничего не путаете? Я этим успешно пользуюсь в OS X приложении с встроенным WebView, все работает.
Вот баг про это: bugs.webkit.org/show_bug.cgi?id=60752
Хотя он и закрыт прошлым годом но до Андроидов и iOS эти изменения не дошли и по всйе видимости не дойдут.
Вот можно проверить: terrainformatica.com/w3/webkit-attr-sel.htm
Хотя он и закрыт прошлым годом но до Андроидов и iOS эти изменения не дошли и по всйе видимости не дойдут.
Вот можно проверить: terrainformatica.com/w3/webkit-attr-sel.htm
Большое спасибо за разъяснения. Недавно столкнулся с этим наглядно. В последнем проекте на перетаскивании шла проверка пересечений. Элементу, если он доступен для drop, присваивался класс highlighted. Body также был доступен для drop, и ему периодически присваивался/отнимался класс highlighted, что вызывало заметный лаг. Когда body перестали присваивать класс, все пошло заметно шустрее, но главное не была понятна причина — казалось бы, лишь класс. Теперь все ясно.
Вот примерно это и лечит БЭМ
БЭМ лечит только неконкретность, сводя глубину к единице. Число селекторов, однако, разрастается до числа элементов (не из БЭМ, а N из статьи). Это действительно может до нескольких раз облегчить выборку по селектору. Но в динамике, как и замечено в статье, ситуация не поменяется, а именно она часто наиболее наглядна.
Плюс некоторые классы все равно хочется сделать общими.
Плюс некоторые классы все равно хочется сделать общими.
Представим себе HTML документ который после парсера превратился в DOM дерево состоящее из N элементов. Система стилей данного документя состоит из S CSS правил. Тогда вычислительная сложность процедуры назначения стилей всем элементам DOM выражается так:
O( N * S * D )
Где D это метрика «глубины» (depth) дерева и используемых селекторов.
Нет, она не обязательно выражается именно так. Вы привели оценку сверху, она оценивает производительность тупого лобового решения полным перебором без каких-либо индексов и оптимизаций. Однако можно придумать и реализовать много разных эвристик, ну и естественно могут быть более эффективные алгоритмы.
Кроме того, есть принципиальное различие между начальным рисованием и перерисовкой / изменением документа — какие-то эффективные алгоритмы могут работать только во втором случае, а все или почти все фокусируются на начальной загрузке.
Посмотрите, например:
webo.in/articles/habrahabr/38-css-efficiency-tests-3/
www.stevesouders.com/blog/2009/03/10/performance-impact-of-css-selectors/
developer.mozilla.org/en/Writing_Efficient_CSS
www.shauninman.com/archive/2008/05/05/css_qualified_selectors — комментарии dave hyatt
Нет, она не обязательно выражается именно так.
Именно так selector complexity и выражается если следовать спецификации.
По поводу оптимизаций… да они могут уменьшить нагрузку в некоторых случаях.
Скажем есть эвристика которая неким магическим образом исключает из просмотра половину style rules т.е.
можно записать
Собственно это проблема и есть основная причина по которой в CSS никогда не будет селекторов типа:
Ибо в таком случае (has-something-inside selectors) сложность скачком возрастает до квадратичной — O(N2). Это вообще убьет Web.
Именно так selector complexity и выражается если следовать спецификации.
По поводу оптимизаций… да они могут уменьшить нагрузку в некоторых случаях.
Скажем есть эвристика которая неким магическим образом исключает из просмотра половину style rules т.е.
можно записать
O( N * (S*0.5) * D ) что c точки зрения теории равно всё тем же O( N * S * D ). Если есть сомнения то вот en.wikipedia.org/wiki/Big_O_notationСобственно это проблема и есть основная причина по которой в CSS никогда не будет селекторов типа:
body:has(a.cool) { color:red } Ибо в таком случае (has-something-inside selectors) сложность скачком возрастает до квадратичной — O(N2). Это вообще убьет Web.
Чем в смысле сложности
body:has(a.cool) отличается от body a.cool?Для того чтобы проверить элемент body на предмет соответствия body:has(a.cool) селектору нужно просмотреть все N-1 его детей. Т.е. не просто сам элемент и его D parents, а еще и детей.
Т.е. в общем случае сложность выражается как
Т.е. в общем случае сложность выражается как
O(N*S*D*N) -> O(N2). N² — очень грубая оценка на суммарное количество детей всех элементов. Тут, по сути, тот же самый перебор пар элементов, являющихся потомками друг друга, только стиль устанавливается не внутреннему элементу пары, а внешнему. Количество таких пар вы в другом случае почему-то оцениваете менее грубо — N*D.
N2 с точки зрения computational complexity theory есть точная оценка сложности :has(...) селектора.
Представим себе такой документ:
и правило
Количество элементов внутри root элемента здесь N=3
Назначаем стили:
Для первого DIV (root) элемента требуется просмотр n=3 детей (пока найдем <a>).
Для второго DIV элемента n=2
Для третьего n=1
Итого 6 просмотров, что для данного случая N * (N + 1) / 2
Что и есть O(N2) сложность с точки зрения теории.
Представим себе такой документ:
<div>
<div>
<div>
<a>...</a>
</div>
</div>
</div>
и правило
div:has(a) { color:red }
Количество элементов внутри root элемента здесь N=3
Назначаем стили:
Для первого DIV (root) элемента требуется просмотр n=3 детей (пока найдем <a>).
Для второго DIV элемента n=2
Для третьего n=1
Итого 6 просмотров, что для данного случая N * (N + 1) / 2
Что и есть O(N2) сложность с точки зрения теории.
Теоретически — да, может быть D=N. Но для чего в таком случае у Вас вообще обозначение D?
D есть метрика глубины самого DOM и используемых descendant selectors.
Если система стилей не использует descendant selectors, а имеет только два правила (S=2):
то D в этом случае равно 1. Системе не требутеся просматривать parent chain на предмет ответа уволетворяет ли селектор или нет.
Если же мы имеем набор правил вида
то для проверки таких селекторов нам нужно просмотреть весь parent chain каждого элемента. В худшем случае на полную глубину вплоть до root (html) элемента включительно. В этом случае метрика D есть средняя глубина элементов в DOM.
Т.е. метрика D не точная — зависит от конфигурации дерева.
Если система стилей не использует descendant selectors, а имеет только два правила (S=2):
#id {color:red}
.cls {color:blue}
то D в этом случае равно 1. Системе не требутеся просматривать parent chain на предмет ответа уволетворяет ли селектор или нет.
Если же мы имеем набор правил вида
.super #id {color:red}
.super .cls {color:blue}
то для проверки таких селекторов нам нужно просмотреть весь parent chain каждого элемента. В худшем случае на полную глубину вплоть до root (html) элемента включительно. В этом случае метрика D есть средняя глубина элементов в DOM.
Т.е. метрика D не точная — зависит от конфигурации дерева.
> Именно так selector complexity и выражается если следовать спецификации.
ссылочку в студию, пожалуйста, на доказательство асимптотической оптимальности полного перебора :)
ну и заодно давайте определимся, какая именно спецификация.
что до практических применений, то эвристик довольно много, начиная от простейшего хэширования по тэгнейму, класснейму и стилю (так кстати делает вебкит), и заканчивая изящными штуками с регулярными выражениями. они там очень коротенько упоминают и саму трансляцию опускают, но если я правильно всё понял, то, например: если в css есть правила
body div.x a.y {..}
a.z { ...}
body.p div > a {… }
body.v * {..}
то можно транфсормировать их в:
body{CLASSES} {ELEMENTS} div{CLASSES}.x{CLASSES} {ELEMENTS} a{CLASSES}.y{CLASSES}
a{CLASSES}.z{CLASSES
body{CLASSES}.p{CLASSES} {ELEMENTS} div{CLASSES} a{CLASSES}
body{CLASSES}.v{CLASSES} ([^ ]+)
где
{CLASSES} означает ([^. ]+)*
{ELEMENTS} означает ([^ ]+ )*([^ ]+)
далее склеиваем их в (rule_1 | rule_2… | rule_N)$
итого, мы получаем 1 регулярное выражение (за время, я полагаю, O(S*ln(S)) ?)
теперь при обходе дерева элементов записываем, где мы находимся.
например, html body p div.a.x b (не найдено)
html body a.z.x (найдено)
html body p div.x a.y (найдено)
на поиск по регекспу тратится O(длина строки) = O(D), верно?
итого O(S*ln(S) + D*N)
естественно, это сложность только поиска (плюс я упускаю пока момент с определением, какие именно правила подошли. но он тоже решается, навскидку будет +D*N*ln(S)).
но ещё эти правила нужно применять, и тут ваша оценка скорее всего верна.
ссылочку в студию, пожалуйста, на доказательство асимптотической оптимальности полного перебора :)
ну и заодно давайте определимся, какая именно спецификация.
что до практических применений, то эвристик довольно много, начиная от простейшего хэширования по тэгнейму, класснейму и стилю (так кстати делает вебкит), и заканчивая изящными штуками с регулярными выражениями. они там очень коротенько упоминают и саму трансляцию опускают, но если я правильно всё понял, то, например: если в css есть правила
body div.x a.y {..}
a.z { ...}
body.p div > a {… }
body.v * {..}
то можно транфсормировать их в:
body{CLASSES} {ELEMENTS} div{CLASSES}.x{CLASSES} {ELEMENTS} a{CLASSES}.y{CLASSES}
a{CLASSES}.z{CLASSES
body{CLASSES}.p{CLASSES} {ELEMENTS} div{CLASSES} a{CLASSES}
body{CLASSES}.v{CLASSES} ([^ ]+)
где
{CLASSES} означает ([^. ]+)*
{ELEMENTS} означает ([^ ]+ )*([^ ]+)
далее склеиваем их в (rule_1 | rule_2… | rule_N)$
итого, мы получаем 1 регулярное выражение (за время, я полагаю, O(S*ln(S)) ?)
теперь при обходе дерева элементов записываем, где мы находимся.
например, html body p div.a.x b (не найдено)
html body a.z.x (найдено)
html body p div.x a.y (найдено)
на поиск по регекспу тратится O(длина строки) = O(D), верно?
итого O(S*ln(S) + D*N)
естественно, это сложность только поиска (плюс я упускаю пока момент с определением, какие именно правила подошли. но он тоже решается, навскидку будет +D*N*ln(S)).
но ещё эти правила нужно применять, и тут ваша оценка скорее всего верна.
В этом тексте четыре запятые
Например если вы захотите преключать режим отображения документа c помощью изменения значения некоего DOM атрибута «mode» и пары правил вида body[mode=first] .widget {color:red} и body[mode=second] .widget {color:green} то у вас ничего не получится (в WebKit).
Неправда.
У меня в хроме работает.
(Пишу сайт с режимами)
Неправда.
У меня в хроме работает.
(Пишу сайт с режимами)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Про вычислительную сложность алгоритмов HTML и CSS