Тоже не совсем. Отвечу обоим сразу.

А>>занос в кучу — C
Могли бы Вы рассказать как это занос в кучу С? С — это константа?
Занос в кучу это logk для каждого элемента. Это будет делаться так: удаляем голову, ставим на ее место новый элемент и просеиваем вниз. Просеивание куда угодно — это O(logk).
Поэтому если у нас встретится массив такой что каждый новый элемент будет больше предыдущего (худший случай) — это потребует занос каждого нового элемента в кучу и выкидывание минимального — и это уже будет nlogk — общий случай. Откуда взялось C для заноса в кучу?

E>Кроме того, если уж ты считаешь, что k -- это константа, то можно и попроще.
E>Заводишь просто массив из k элементов, ну и заполняешь его по мере просмотра большого массива...

И второму автору — увы, O(n) не получается.
Допустим мы заполнили наш новый k-массив первыми элементами. Отлично. Теперь есть два момента:
1. Надо убирать дубликаты на каждом шаге.
Если на массиве у нас нет кучи — то тогда придется просматривать вcе k-элементов (sequential search) чтобы решить булет новый элемент дубликатом или нет. Это O(k).
2. Опять же если на массиве нет кучи — то при добавлении нового элемента мы должны найти последовательным поиском минимальный элемент и заменить на новый. Поиск минимального — это O(k) опять.
И это надо делать для каждого из n элементов. Итог: O(n*2*k) или O(nk).

E>Тоже O(N) получается...

Нет. Получается O(nk), что хуже против алгоритма с кучей сложность которого O(nlogk) — оно намного ниже.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, PaulMinelly, Вы писали:

DB>>>а где тут этюд?!
DB>>>более подходящий форум имхо — алгритмы

PM>>Да, этюда нет, надо бы передвинуть в алгоритмы. Не туда нажал, сорри

К>Как раз этюд.
К>Дайте народу поразмять извилину.
К>Решений-то много.

Какие решения еще решения Вы считаете правильными? Остальные посмотрел — не совсем понял. Круче nlogk — ничего не нашел. Radix sort — даст O(nk) — что является хуже алгоритма с кучей. Плюс избавление от дубликатов не понятно как.
Какие варианты из написанных Вы бы выделили особо? Я пытался над ними думать, но все не доходит до меня как можно еще извернуться за nlogk или ниже если не использовать кучу.

А если брать кучу размером k такую, что в голове находится наименьший элемент? Тогда будет сразу ясно, нужно ли добавлять очередной элемент.

Здравствуйте, PaulMinelly, Вы писали:

PM>Какие решения еще решения Вы считаете правильными? Остальные посмотрел — не совсем понял. Круче nlogk — ничего не нашел. Radix sort — даст O(nk) — что является хуже алгоритма с кучей. Плюс избавление от дубликатов не понятно как.

Радикс — O(nb), где b — разрядность.
Если b < logk, то выигрыш будет. Плюс, опять же, разные константы скорости — нужно смотреть, там с кешем может чёрти-что твориться, а может и не твориться.

А дубликаты убираются очень просто: бежим по отсортированному набору с головы и смотрим: если следующий элемент равен предыдущему, то выкидываем. До тех пор, пока не получим k уникальных.

PM>Какие варианты из написанных Вы бы выделили особо? Я пытался над ними думать, но все не доходит до меня как можно еще извернуться за nlogk или ниже если не использовать кучу.

1) Полная сортировка, затем берём первые k уникальных.

Быстрые сортировки (quick для массивов, merge для списков) — O(nlogn), на самом деле если logk сравним с logn, то не жалко и отсортировать.
Радикс — O(n*b).
Сортировка подсчётом — O(n+r) времени и O(r) памяти (битовый вектор) — где r — диапазон значений (logr = b).

Да, не забываем, что радикс и подсчёт применимы только для чисел с натуральным порядком. Для произвольного отношения порядка (в т.ч. над произвольными объектами — вещественные числа, строки) фокус не пройдёт.

2) Частичная сортировка.

Модификация частичной быстрой сортировки std::partial_sort — нужно параллельно подсчитывать число уникальных элементов (и выбрасывать их) и при необходимости досортировывать то, что оказалось после медианы. Обычный алгоритм подсчитывает число элементов вообще.
O(nlogk), наверное. Хотя надо подумать.

Модификация пирамидальной сортировки: упаковываем n, распаковываем первые k уникальных. O(nlogn) — нда, неприятно.

Очередь с приоритетами (поверх двоичного дерева, а не поверх пирамиды) — O(nlogk). Если дерево ещё и разместить в цельном блоке памяти, то кэш не будем насиловать.


Итак, выбираем из nlogk, nlogr, n+r.
По-моему, неплохой ассортимент.

Здравствуйте, PaulMinelly, Вы писали:


E>>Тоже O(N) получается...
PM>Нет. Получается O(nk), что хуже против алгоритма с кучей сложность которого O(nlogk) — оно намного ниже.
Это всё не понятно как считают. Типа нужен алгоритм, не зависящий от K, или зависимость от K не интересует?
Если второе, то понятно, например, почему занесение в кучу константа...

Здравствуйте, Roman Odaisky, Вы писали:

RO>А если брать кучу размером k такую, что в голове находится наименьший элемент? Тогда будет сразу ясно, нужно ли добавлять очередной элемент.

На самом деле можно иметь две кучи, и иметь ссылки между ними.
Тогда всегда можно будет знать кого выбрасывать и кого добавлять. Но что делать с дубликатами всё равно не понятно

Здравствуйте, PaulMinelly, Вы писали:

PM>4. Алгоритм поиска Хоара "Divide and Conquer" (тот что и про поиск медианы) — O(n) все круто, но отпадает.
PM>Потому что он эффективен для поска k-первых максимальных/минимальных чисел в массиве с _уникальными_ числами. У нас же массив содержит дубликаты. Поэтому применив поиск k-первых максимальных чисел мы получим ответ с дубликатами, нам же надо без дубликатов. Отпадает?

Не совсем. Забрасываем сначала все числа в хэш-таблицу, избавляясь от дубликатов. Это будет O(n) c использованием O(n) памяти. Затем используем алгоритм выше, это еще раз O(n).

PM>Какие еще могут быть идеи за O(n) и память O(1).

С O(1) памятью пока как-то идей нет.

Здравствуйте, Roman Odaisky, Вы писали:

RO>А если брать кучу размером k такую, что в голове находится наименьший элемент? Тогда будет сразу ясно, нужно ли добавлять очередной элемент.

Да, в min-heap сразу видно. Но сложность-то считается изходя из самого худшего входного набора n-элементов, т.е. худший это отсортированный уже входной массив в возрастающем порядке, когда мы каждый новый элемент будет больше инимальной головы кучи. Поэтому каждый элемент придется вставлять в кучу. Вот и O(nlogk) получается.

К>А вот тут меня сомнения обуяли — можно ли в куче эффективно бороться с дубликатами. Ведь она не обеспечивает строгий порядок.
К>Вот смотри: начали строить кучу из серии a,b,c,d,e.
К>Добавляем ещё одну d или e. В ветку b она не попадёт, поэтому про дубликаты мы не узнаем.

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

2
| \
5  9
|\  \
10 20

Мы вытащили еще один элемент со значением 10 из массива и хотим проверить надо ли вставлять его в кучу (есть ли там уже такой или еще нет). Поскольку у нас это minheap, то действия такие:
1. Выкидываем голову (2) и ставим 10 на место головы:

10
| \
5  9
|\  \
10 20

2. Просеиваем 10 вниз (это O(logk)) начиная обсматривать с левой ветки. Получаем:
К>

К>5
К>| \
К>10  9
К>|\  \
К>10 20 
К>

3. Видим что след.-левый элемент у нас 10 — значит дубликат есть, в кучу вставлять наш элемент не надо было. Что делаем?
Вертаем все назад. Это опять O(logk). Для этого надо где-то сохранять голову, чтобы ее не выкидывать совсем.
Допустим массив у нас содержит первые k-уникальных значений, а потом все дубликаты.
Хотя тогда общая сложность все равно будет O(n*2*logk) или O(n*logk). Фу, я уж подумал что и этого решения нет

Здравствуйте, PaulMinelly, Вы писали:

PM>Мы вытащили еще один элемент со значением 10 из массива и хотим проверить надо ли вставлять его в кучу (есть ли там уже такой или еще нет). Поскольку у нас это minheap, то действия такие:
PM>1. Выкидываем голову (2) и ставим 10 на место головы:
PM>

PM>10
PM>| \
PM>5  9
PM>|\  \
PM>10 20 
PM>

PM>2. Просеиваем 10 вниз (это O(logk)) начиная обсматривать с левой ветки. Получаем:
К>>

К>>5
К>>| \
К>>10  9
К>>|\  \
К>>10 20 
К>>

И почему с левой? А если 10 будет в правой?

PM>3. Видим что след.-левый элемент у нас 10 — значит дубликат есть, в кучу вставлять наш элемент не надо было. Что делаем?
PM>Вертаем все назад. Это опять O(logk). Для этого надо где-то сохранять голову, чтобы ее не выкидывать совсем.

Это все — фантазии, куча не предназначена для поиска. Сложность поиска в куче O(n).

PM>Допустим массив у нас содержит первые k-уникальных значений, а потом все дубликаты.
PM>Хотя тогда общая сложность все равно будет O(n*2*logk) или O(n*logk). Фу, я уж подумал что и этого решения нет

Здравствуйте, PaulMinelly, Вы писали:

PO>>Если известно, что k<<N, то куча вполне подойдет (Ее можно создать линейно).

PM>Да, k намного меньше чем N.
PM>Как создать кучу линейно? В том же самом массиве? Извлечение из кучи одного элемента будет O(logk) а всех элементов O(klogk) хотя вроде нормально.

Куча создается линейно следующим образом:
Для простоты предположим, что у нас в куче 2^p-1 элементов. Теперь возьмем все элементы предпоследнего уровня ([2^(p-2), 2^(p-1)-1]), и пробуем их опустить вниз. Затем поднимаемся на уровень выше и делаем то же самое и т.д. На практике это выглядит так:

for i = length(Heap)/2-1 downto 0
  do Pulldown(i)

Теперь надо доказать, что это O(n). Каждая операция Pulldown по сложности не превосходит O(logn), но это не учитывает позицию элементов в дереве. Ведь для предпоследнего ряда, например, нужно всего по одному вызову Pulldown, а для последнего вообще никаких действий не производится. Пусть у нас высота кучи h.
1 снизу ряд: для n/2 элементов выполняется 0*n/2 операций
2 снизу ряд: для n/4 элементов выполняется 1*n/4 операций
3 снизу ряд: для n/8 элементов выполняется 2*n/8 операций
4 снизу ряд: для n/16 элементов выполняется 3*n/16 операций.
...

Получаем ряд СУММА(i*n / 2^(i+1)), где i от 0 до высоты дерева-1. Выносим n.
n*СУММА(i / 2^(i+1)) <= n*СУММА(i / 2^i) 
Расмотрим теперь бесконечный ряд СУММА(i / 2^i). Покажем, что он равен 2.
СУММА(x^k) при |x| <1 как известно равен 1/(1-x)
продифференцируем это равенство по х и умножим обе части на x.
СУММА(k*x^k) = x / (1-x)^2
Подставим теперь наш x = 1/2, получили:
СУММА(k / 2^k) = 2

Вот и получили O(n)

_DA>И почему с левой? А если 10 будет в правой?

Черт, Вы правы, кучу нельзя заполнять как я написал, она заполняется справа налево (условно). Все точно, мы не сможем найти в ней дубликаты за logn время, только за O(n). Ужос. Куча отпадает. С ней сложность O(n*(klogk)).
Что хуже если исползьвать в качестве кучи упорядоченный массив с поиском и вставкой за O(k).

Тогда общая сложность отметания дубликатов и вставки каждого элемента в обычный set будет O(nk). Так же как с radixsort. Черт, неужели куча отпадает?


PM>>3. Видим что след.-левый элемент у нас 10 — значит дубликат есть, в кучу вставлять наш элемент не надо было. Что делаем?
PM>>Вертаем все назад. Это опять O(logk). Для этого надо где-то сохранять голову, чтобы ее не выкидывать совсем.

_DA>Это все — фантазии, куча не предназначена для поиска. Сложность поиска в куче O(n).

Здравствуйте, PaulMinelly, Вы писали:

_DA>>И почему с левой? А если 10 будет в правой?

PM>Черт, Вы правы, кучу нельзя заполнять как я написал, она заполняется справа налево (условно). Все точно, мы не сможем найти в ней дубликаты за logn время, только за O(n). Ужос. Куча отпадает. С ней сложность O(n*(klogk)).
PM>Что хуже если исползьвать в качестве кучи упорядоченный массив с поиском и вставкой за O(k).

PM>Тогда общая сложность отметания дубликатов и вставки каждого элемента в обычный set будет O(nk). Так же как с radixsort. Черт, неужели куча отпадает?

Что-то у тебя все перепуталось. Во-первых, с радиксом будет O(n*b), где b — разрядность. Во-вторых, с кучей даже без избавления от повторов будет O(nlogn). Если уж очень хочется использовать кучу, то как я предлагал ниже, можно использовать сначала хэш-таблицу, чтобы за O(n) избавиться от повторов, потом за O(n) построить кучу, а потом за O(klogn) вытащить k первых чисел. Будет O(n+klogn).
А еще.. тебе не понравилось предложенное мной решение за O(n)?

_DA>Что-то у тебя все перепуталось. Во-первых, с радиксом будет O(n*b), где b — разрядность.

А, ну да. Точно Ты прав.

_DA>Во-вторых, с кучей даже без избавления от повторов будет O(nlogn). Если уж очень хочется использовать кучу, то как я предлагал ниже, можно использовать сначала хэш-таблицу, чтобы за O(n) избавиться от повторов,
_DA>потом за O(n) построить кучу

А как можно за O(n) построить кучу ? В вики тоже написано что куча строится за O(n) — но я этого понять никак не могу и рядом написано что вставка в кучу занимает O(logn). Это я тоже понять не могу ведь куча строится вставками? N-вставок, каждая logn = получаем nlogn?
Или другими словами: я понимаю куча строится так. Например мы строим min-heap на массиве. Появился новый элемент, мы добавляем его в последнюю ячейку и просеиваем вверх. На определенной позиции он останавливается. Всего уровней в куче logn (хотя их вообще-то меньше в самом начале, и больше когда мы ближе к концу). То собственно кол-во вставок в кучу (чтобы ее создать) надо будет сделать O(nlogn). Или еще можно как-то хитро за O(n)?

_DA>, а потом за O(klogn) вытащить k первых чисел. Будет O(n+klogn).
_DA>А еще.. тебе не понравилось предложенное мной решение за O(n)?

Думаю мне надо сначала разобраться как строить кучу за O(n), потом размер хеш таблицы — и тогда я смогу сказать четко Я пока ламер в хеш таблицах, как хеш-функция работает — знаю, но как хеш таблица и ее коллизии (и как они разрешаются посредством bin — это для меня туман). Если мы создадим хеш таблицу — то она займет памяти 2^32? Или нет? (По размеру нашего integer'a?) или же ровно то кол-во уникальных элементов <=n сколько у нас получится?

Здравствуйте, PaulMinelly, Вы писали:

_DA>>Что-то у тебя все перепуталось. Во-первых, с радиксом будет O(n*b), где b — разрядность.

PM>А, ну да. Точно :) Ты прав.

_DA>>Во-вторых, с кучей даже без избавления от повторов будет O(nlogn). Если уж очень хочется использовать кучу, то как я предлагал ниже, можно использовать сначала хэш-таблицу, чтобы за O(n) избавиться от повторов,
_DA>>потом за O(n) построить кучу

PM>А как можно за O(n) построить кучу ? В вики тоже написано что куча строится за O(n) — но я этого понять никак не могу и рядом написано что вставка в кучу занимает O(logn). Это я тоже понять не могу ведь куча строится вставками? N-вставок, каждая logn = получаем nlogn?
PM>Или другими словами: я понимаю куча строится так. Например мы строим min-heap на массиве. Появился новый элемент, мы добавляем его в последнюю ячейку и просеиваем вверх. На определенной позиции он останавливается. Всего уровней в куче logn (хотя их вообще-то меньше в самом начале, и больше когда мы ближе к концу). То собственно кол-во вставок в кучу (чтобы ее создать) надо будет сделать O(nlogn). Или еще можно как-то хитро за O(n)?

А ты все сообщения этого топика читаешь? :) Я же тебе уже отвечал

Автор: _DAle_
Дата: 09.05.08

по поводу построения кучи за O(n). За O(n) куча строится из массива, на его же месте.

_DA>>, а потом за O(klogn) вытащить k первых чисел. Будет O(n+klogn).
_DA>>А еще.. тебе не понравилось предложенное мной решение за O(n)?

PM>Думаю мне надо сначала разобраться как строить кучу за O(n), потом размер хеш таблицы — и тогда я смогу сказать четко :) Я пока ламер в хеш таблицах, как хеш-функция работает — знаю, но как хеш таблица и ее коллизии (и как они разрешаются посредством bin — это для меня туман). Если мы создадим хеш таблицу — то она займет памяти 2^32? Или нет? (По размеру нашего integer'a?) или же ровно то кол-во уникальных элементов <=n сколько у нас получится?

Памяти нужно будет O(n), можно даже хэширование с открытой адресацией использовать. Я так понимаю, у тебя CLR есть, там есть хорошая глава про хэш-таблицы.

Здравствуйте, _DAle_, Вы писали:

_DA>Куча создается линейно следующим образом:
_DA>Для простоты предположим, что у нас в куче 2^p-1 элементов. Теперь возьмем все элементы предпоследнего уровня ([2^(p-2), 2^(p-1)-1]), и пробуем их опустить вниз. Затем поднимаемся на уровень выше и делаем то же самое и т.д. На практике это выглядит так:

_DA>

_DA>for i = length(Heap)/2-1 downto 0
_DA>  do Pulldown(i) 
_DA>

Погоди! Ты предполагаешь, что куча УЖЕ построена, после чего начинаешь мухлевать с её уровнями.
Или ты что-то иное имеешь в виду?

В порядке догадки:
— берём массив и нарубаем его на 1-, 2-, 4-, ..., -элементные подмассивы
— из каждого подмассива делаем кучу
— выполняем слияние этих куч (поскольку они уже частично упорядочены, то слияние проходит за меньшее время, чем если бы мы растили кучу поштучно)
Так?

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, _DAle_, Вы писали:

_DA>>Куча создается линейно следующим образом:
_DA>>Для простоты предположим, что у нас в куче 2^p-1 элементов. Теперь возьмем все элементы предпоследнего уровня ([2^(p-2), 2^(p-1)-1]), и пробуем их опустить вниз. Затем поднимаемся на уровень выше и делаем то же самое и т.д. На практике это выглядит так:

_DA>>

_DA>>for i = length(Heap)/2-1 downto 0
_DA>>  do Pulldown(i) 
_DA>>

К>Погоди! Ты предполагаешь, что куча УЖЕ построена, после чего начинаешь мухлевать с её уровнями.
К>Или ты что-то иное имеешь в виду?

Извиняюсь, что не совсем понятно написал. Я имею ввиду, что изначально у нас есть исходный никак не упорядоченный массив чисел, и мы in-place строим в нем кучу, последовательно с конца "опуская" ее элементы. В одной из реализаций STL это написано так:

    void _Make_heap(_RanIt _First, _RanIt _Last, _Diff *, _Ty *)
    {    // make nontrivial [_First, _Last) into a heap, using operator<
    _Diff _Bottom = _Last - _First;

    for (_Diff _Hole = _Bottom / 2; 0 < _Hole; )
        {    // reheap top half, bottom to top
        --_Hole;
        _Adjust_heap(_First, _Hole, _Bottom, _Ty(*(_First + _Hole)));
        }
    }

Здравствуйте, _DAle_, Вы писали:

PM>>Да, k намного меньше чем N.
PM>>Как создать кучу линейно? В том же самом массиве? Извлечение из кучи одного элемента будет O(logk) а всех элементов O(klogk) хотя вроде нормально.
<...>
_DA>Вот и получили O(n)

Вернее не при k << N, а при немного более сильном условии: "число элементов массива, превосходящих самое маленькое из отбираемых чисел есть o( N )"

1) Строим из массива кучу за O( N ) с наибольшим элементом в вершине
2) Добываем из кучи последовательно элементы, в порядке убывания, накапливая где-то уникальные наибольшие. Пока не наберём k наибольших уникальных.
Пусть для этого нам понадобится выбрать из кучи m элементов.
Очевидно, что сложность нашего алгоритма -- это O( N ) + O( m * ln N ), но по нашему условию m = o( N ), так что O( m ln N ) = O( N )...

_DA>>>

_DA>>>for i = length(Heap)/2-1 downto 0
_DA>>>  do Pulldown(i) 
_DA>>>

К>>Погоди! Ты предполагаешь, что куча УЖЕ построена, после чего начинаешь мухлевать с её уровнями.
К>>Или ты что-то иное имеешь в виду?

Допустим у нас уже есть массив k элементов, теперь мы хотим придать этому массиву свойство кучи, причем начинаем на нем строить кучу прямо inplace.
Начинаем пробегать массив слева на право и в левой части ЭТОГО же массива формируется куча (куча растет слева на право)- эта методика описана почти везде и классическая. Это O(klogk). Ее я понял хорошо Но как сделать тоже самое за O(k) имея тот же массив и делая тоже самое in-place (заметь в первом варианте мы тоже строим кучу на массиве и inplace но за O(klogk) — не понял.

Из того что прочитал в описании — остались вопросы:
1. Почему можно опускать предпоследний уровень в массиве? Разве это придаст свойство кучи предпоследнему уровню? Ведь у нас массив не отсортирован. Мы можем только:
— добавив элемент в конец кучи — просеить его вверх O(logk). Так мы можем сформровать кучу. На этом все наши возможности по построению кучи. Или нет?
2. Может ты имеешь ввиду когда мы строим кучу inplace в массиве k элементов, то на первом шаге у нас в куче не k, а только 1 элемент, на втором шаге — 2 элемента, потом 3, 4 ... k?
И что сложность будет сумма просеиваний: log1 + log2 + log3 + log4 + ... + logk или как? И чему сумма будет равна? lol, это какой-то амортизационный анализ?

Здравствуйте, PaulMinelly, Вы писали:

_DA>>>>for i = length(Heap)/2-1 downto 0
_DA>>>> do Pulldown(i)
_DA>>>>

К>>>Погоди! Ты предполагаешь, что куча УЖЕ построена, после чего начинаешь мухлевать с её уровнями.
К>>>Или ты что-то иное имеешь в виду?

PM>Допустим у нас уже есть массив k элементов, теперь мы хотим придать этому массиву свойство кучи, причем начинаем на нем строить кучу прямо inplace.
PM>Начинаем пробегать массив слева на право и в левой части ЭТОГО же массива формируется куча (куча растет слева на право)

Справа налево, в правой части.

PM> — эта методика описана почти везде и классическая. Это O(klogk).

Это O(n). И я вроде привел доказательство этого факта.

PM> Ее я понял хорошо :) Но как сделать тоже самое за O(k) имея тот же массив и делая тоже самое in-place (заметь в первом варианте мы тоже строим кучу на массиве и inplace но за O(klogk) — не понял.

PM>Из того что прочитал в описании — остались вопросы:
PM>1. Почему можно опускать предпоследний уровень в массиве? Разве это придаст свойство кучи предпоследнему уровню? Ведь у нас массив не отсортирован.

Опускать — это означает сравнивать с дочерними элементами и менять их местами так, чтобы выполнялось свойство кучи. То есть это та же операция, которая производится при удалении элемента, после установки последнего элемента в корень дерева. Примерно так:

while (pos*2+1 < size)
{
  newpos = pos*2+1;
  if (pos*2+2 < size && heap[pos*2+2] > heap[newpos]) newpos = pos*2+2;
  if (heap[pos] < heap[newpos])  
  {
    swap(heap[pos], heap[newpos]);
    pos = newpos;
  }
  else break;
}

Понятно, что, применив это к элементам предпоследнего ряда, у нас будет выполнятся свойство кучи для элементов предпоследнего ряда.

PM>Мы можем только:
PM>- добавив элемент в конец кучи — просеить его вверх O(logk). Так мы можем сформровать кучу. На этом все наши возможности по построению кучи. Или нет?
Нет. Я ведь и код уже привел из STL..
PM>2. Может ты имеешь ввиду когда мы строим кучу inplace в массиве k элементов, то на первом шаге у нас в куче не k, а только 1 элемент, на втором шаге — 2 элемента, потом 3, 4 ... k?

Нет, я совсем не это имею ввиду.
Наверное, я слишком плохо объясняю.