Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.
Здравствуйте, IgushevEdward, Вы писали:
IE>Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.
Скромное название вводит в заблуждение.
На самом деле это не массив в том виде, в котором это понимается в С++. Основной признак массива — это то, что ты можешь взять адрес одного элемента и получить доступ ко всем другим элементам посредством адресной арифметики.
Фактически у тебя получился гибрид std::list с std::vector'ом, причем достоинства и того, и другого слегка подрастерялись при слиянии.
IE>Подробное описание можно найти здесь http://igushev.ru/papers/igusharray/
Ну вот смотри: по сравнению с вектором твоя структура работает быстрее, это да. Но, к сожалению, вектор нельзя просто взять и заменить твоей структурой, потому что вектор (к примеру) можно использовать как буфер при вызове сишных или WinAPI-шных функций:
Если заменить в таком коде вектор на твой эррей, программа упадет.
Таким образом, твоя структура не является аналогом массива — это скорее аналог стд::листа с возможностью рандомного доступа к элементам (и с более медленной вставкой-удалением).
IE>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!
А какие достоинства имеет твоя структура по сравнению с std::list, кроме рандомных итераторов?
Здравствуйте, IgushevEdward, Вы писали:
IE>Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.
IE>Подробное описание можно найти здесь http://igushev.ru/papers/igusharray/
IE>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!
Из результатов видно, что время операции удаления std::vector растет линейно вместе с количеством элементов, а время операции удаления IgushArray растет как N1/2
M>Из результатов видно, что время операции удаления std::vector растет линейно вместе с количеством элементов, а время операции удаления IgushArray растет как N1/2
M>Ага. А N1/2 — это не линейно?
При копировании из word'а спетенное написание 1/2 пропало. Надо читать N^1/2. Сейчас поправлю
Здравствуйте, IgushevEdward, Вы писали:
IE>Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.
Во-первых, открой для себя std::deque. Та же страничная структура с итераторами произвольного доступа.
Во-вторых, сложность операций вставки и удаления по-прежнему остались O(N), только добавилась константа (учет разбивки на страницы). Тебе все равно приходится сдвигать _все_ элементы во всех страницах ниже текущей.
В третьих, твоя фраза
"Каждый элемент указывает на двусвязную очередь размера приблизительно N1/2"
совместно с
Для доступа произвольного элемента по его индексу в IgushArray, необходимо рассчитать индекс в массиве с помощью операции ( O (1) ), затем получить указатель ( O (1) ), рассчитать индекс в очереди при помощи K % deq_size операции ( O (1) ) и получить элемент в очереди. См. схему внизу. Как видно, операция доступа имеет константную сложность.
наводят на подозрения.
Либо страница у тебя оформлена как список, а тогда доступ к отдельному элементу не О(1), а O(N^1/2).
Либо как массив, но тогда вставка и удаление — O(N).
В четвертых,
"можно достаточно легко заменить std::vector в коде"
невозможно, ибо vector гарантирует расположение своих элементов в непрерывном блоке памяти, что дает возможность использования его для работы с сишным API. А у тебя страничная организация памяти.
IE>Подробное описание можно найти здесь http://igushev.ru/papers/igusharray/
IE>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!
_____________________
С уважением,
Stanislav V. Zudin
SVZ>"Каждый элемент указывает на двусвязную очередь размера приблизительно N1/2"
SVZ>совместно с SVZ>
SVZ>Для доступа произвольного элемента по его индексу в IgushArray, необходимо рассчитать индекс в массиве с помощью операции ( O (1) ), затем получить указатель ( O (1) ), рассчитать индекс в очереди при помощи K % deq_size операции ( O (1) ) и получить элемент в очереди. См. схему внизу. Как видно, операция доступа имеет константную сложность.
SVZ>наводят на подозрения. SVZ>Либо страница у тебя оформлена как список, а тогда доступ к отдельному элементу не О(1), а O(N^1/2). SVZ>Либо как массив, но тогда вставка и удаление — O(N).
Страница оформлена как двусвязная очередь реализованная в виде массива. Доступ к отдельному элементу O(1), встравка и удаление в середину линейная, но ее размеры в контексте всей структуры N^1/2, поэтому вставка в встраницу O(N^1/2)
Здравствуйте, IgushevEdward, Вы писали:
IE>Страница оформлена как двусвязная очередь реализованная в виде массива. Доступ к отдельному элементу O(1), встравка и удаление в середину линейная, но ее размеры в контексте всей структуры N^1/2, поэтому вставка в встраницу O(N^1/2)
Итак, давай посчитаем, во нам обойдется вставка нового элемента в 0-ю позицию.
Для всех N^1/2 страниц надо выполнить N^1/2 операций сдвига. Итого: N операций.
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Здравствуйте, IgushevEdward, Вы писали:
IE>>Страница оформлена как двусвязная очередь реализованная в виде массива. Доступ к отдельному элементу O(1), встравка и удаление в середину линейная, но ее размеры в контексте всей структуры N^1/2, поэтому вставка в встраницу O(N^1/2)
SVZ>Итак, давай посчитаем, во нам обойдется вставка нового элемента в 0-ю позицию. SVZ>Для всех N^1/2 страниц надо выполнить N^1/2 операций сдвига. Итого: N операций.
НЕТ!
Для первой страницы вставка нового элемента в 0 позицию — O(N^1/2).
Для всех оставльных страниц : ( вставить в начало, удалить с конца — O(1) ) * N^1/2 -> O(N^1/2)
SVZ>Во-первых, открой для себя std::deque. Та же страничная структура с итераторами произвольного доступа.
deque паскудно реализован, т.к. размер блока нельзя задавать, а встроенный он там маленький. Всего 8. Вот когда-то жаловался
Здравствуйте, Stanislav V. Zudin, Вы писали: SVZ>Во-первых, открой для себя std::deque. Та же страничная структура с итераторами произвольного доступа.
std::deque — вставка/удаление дорогое.
И его постраничная реализация дает "очень плохой" O(1).
К примеру, при реализации IgushArray ипользуется двусвязная очередь. Я сначала использовал std::deque, затем заменил на свою реализацию с фиксированным (вернее задается максимум на этапе конструирования) размером (эта информация имеется на этапе конструирования) -> результаты тестов сильно улучшились
Здравствуйте, IgushevEdward, Вы писали:
IE>Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>>Здравствуйте, IgushevEdward, Вы писали:
IE>>>Страница оформлена как двусвязная очередь реализованная в виде массива. Доступ к отдельному элементу O(1), встравка и удаление в середину линейная, но ее размеры в контексте всей структуры N^1/2, поэтому вставка в встраницу O(N^1/2)
SVZ>>Итак, давай посчитаем, во нам обойдется вставка нового элемента в 0-ю позицию. SVZ>>Для всех N^1/2 страниц надо выполнить N^1/2 операций сдвига. Итого: N операций.
IE>НЕТ!
IE>Для первой страницы вставка нового элемента в 0 позицию — O(N^1/2).
IE>Для всех оставльных страниц : ( вставить в начало, удалить с конца — O(1) ) * N^1/2 -> O(N^1/2)
IE>O(N^1/2) + O(N^1/2) -> O(N^1/2)
IE>Там есть очень понятная иллюстрация
Иллюстрация там замечательная.
Реализация списков на базе массива — в определенных условиях очень эффективное решение.
Но как тогда ты обеспечиваешь О(1) при получении элемента по индексу?
Допустим, есть массив из 9 значений:
arr[0] == 1
arr[1] == 2
...
arr[8] == 9
Внутри твоего контейнера будет 3 страницы на 3 элемента.
page0: 1 -> 2 -> 3
page1: 4 -> 5 -> 6
page2: 7 -> 8 -> 9
Вставляем в нулевую позицию значение 0:
+---------+
| |
V |
page0: 1 -> 2 0
+---------+
| |
V |
page1: 4 -> 5 3
+---------+
| |
V |
page2: 7 -> 8 6
page3: 9
Я правильно понимаю?
Тогда, чтобы получить индекс элемента на странице, придется бегать по списку, либо вводить дополнительную таблицу соответствия для хранения связи между индексом в массиве и положением в списке.
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Тогда, чтобы получить индекс элемента на странице, придется бегать по списку, либо вводить дополнительную таблицу соответствия для хранения связи между индексом в массиве и положением в списке.
Небольшое уточнение на всякий случай: страницы реализованы при помощи простых двусвязных очередей (доступ — константный, вставка/удаление в начало/конец — константные), а не списка
Структура имеет структуру на 9 элементов:
page[0] = {1 2 3}
page[1] = {4 5 6}
page[2] = {7 8 9}
Вам нужен элемент с индексом 5:
номер страницы: 5/3 -> страница 1 ( O(1) )
доступ к странице ( O(1) )
элемент в очереди 5%3 -> 2 ( O(1) )
достпу к элементу в очереди ( O(1) ) -> элемент с числом 6
4*O(1) -> O(1)
Здравствуйте, IgushevEdward, Вы писали:
IE>Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.
у меня массив с операцией вставки/удаления за O(1) и взятие индекса O(1). правда, за счет выделения дополнительной памяти. но с учетом того, что массив создается изначально на вырост, дополнительная память выбирается на 90% и потому оверида практически нет.
идея очень простая. массив состоит из "страниц" фиксированного размера. например, 16 Кб. страницы объединены в список. список проиндексирован. индексация многоуровневая (по мере роста массива, страницы объединяются в супер-страницы, а супер-страницы в супер-супер-страницы, в резултате чего расход на память под индексы O(log N) и им можно пренебречь.
изначально страницы заполнены меньше чем наполовину. и потому вставка/удаление элементов обходится очень дешево (мы двигаем только up to 16 кб блок памяти, даже если массив больше гига). если свободное пространство полностью выбрано -- создаем новую страницу, вставляя ее как список. при этом, конечно, нужно переиндексировать весь массив. благодаря фиксированному размеру "странц" переиндексация сводится к тупому сдвигу элементов таблицы индексов, размер которой пренебрежительно мал, т.е. такая операция очень быстрая.
в результате получается гибрид списка с массивом, обеспечивающий быстрый доступ к произвольному элементу и быструю операцию вставки/удаления элементов. особенно быстро работает вставка одного массива внутрь другого или удаление всех элементов от IDXn до IDXn+k, т.к. здесь будет одна вставка/удаления списка A в список B и небольшие передвижки в двух пограничных страницах.
но это не мое изобретение. такие структуры данных очень широко распростанены. в том числе и в файловых системах.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, IgushevEdward, Вы писали:
IE>Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.
IE>Подробное описание можно найти здесь http://igushev.ru/papers/igusharray/
IE>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!
Очевидно, что вам не знакома вот эта книга: Флорес И. Структуры и управление данными. М.: Радио и связь, 1982.
В ней подобные структуры описаны. И проведен анализ производительности.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
IE>К примеру, при реализации IgushArray ипользуется двусвязная очередь. Я сначала использовал std::deque, затем заменил на свою реализацию с фиксированным (вернее задается максимум на этапе конструирования) размером (эта информация имеется на этапе конструирования) -> результаты тестов сильно улучшились
Двусвязная очередь — имеется ввиду двусвязный список? IMO он все испортит — кольцевой буфер тут был бы еще туда-сюда... Более того, там ясно указано, что "размер очередей не меняется никогда", то есть это константа, то есть вставка/удаление не может быть O(N/2). Еще, если размер очередей каким-то образом влияет на вставку/удаление, то почему он не влияет на доступ, поскольку время доступа в списке зависит от его размера?
Здравствуйте, lxa, Вы писали:
IE>>К примеру, при реализации IgushArray ипользуется двусвязная очередь. Я сначала использовал std::deque, затем заменил на свою реализацию с фиксированным (вернее задается максимум на этапе конструирования) размером (эта информация имеется на этапе конструирования) -> результаты тестов сильно улучшились
lxa>Двусвязная очередь — имеется ввиду двусвязный список? IMO он все испортит — кольцевой буфер тут был бы еще туда-сюда... Более того, там ясно указано, что "размер очередей не меняется никогда", то есть это константа, то есть вставка/удаление не может быть O(N/2). Еще, если размер очередей каким-то образом влияет на вставку/удаление, то почему он не влияет на доступ, поскольку время доступа в списке зависит от его размера?
Здравствуйте, IgushevEdward, Вы писали:
IE>Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>>Тогда, чтобы получить индекс элемента на странице, придется бегать по списку, либо вводить дополнительную таблицу соответствия для хранения связи между индексом в массиве и положением в списке.
IE>Небольшое уточнение на всякий случай: страницы реализованы при помощи простых двусвязных очередей (доступ — константный, вставка/удаление в начало/конец — константные), а не списка
Не поленился, залез в код.
template <class T, class Alloc>
typename FixedDeque<T, Alloc>::iterator FixedDeque<T, Alloc>::insert(iterator it, const T& val)
{
if (size() + 1 > _max_size())
throw std::out_of_range("insert(): The size has been exceeded");
iterator to = end() + 1;
iterator from = end();
while (from != it) <--- !!!
_move(--to, *--from); <--- !!!
_move(from, val);
if (_end == _storage_end - 1)
_end = _storage_begin;
else
++_end;
return from;
}
Вот что делает выделенный цикл и какова получается сложность алгоритма в целом?
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, мыщъх, Вы писали:
М>Здравствуйте, IgushevEdward, Вы писали:
IE>>Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.
М>у меня массив с операцией вставки/удаления за O(1) и взятие индекса O(1). правда, за счет выделения дополнительной памяти. но с учетом того, что массив создается изначально на вырост, дополнительная память выбирается на 90% и потому оверида практически нет.
М>идея очень простая. массив состоит из "страниц" фиксированного размера. например, 16 Кб. страницы объединены в список. список проиндексирован. индексация многоуровневая (по мере роста массива, страницы объединяются в супер-страницы, а супер-страницы в супер-супер-страницы, в резултате чего расход на память под индексы O(log N) и им можно пренебречь.
М>изначально страницы заполнены меньше чем наполовину. и потому вставка/удаление элементов обходится очень дешево (мы двигаем только up to 16 кб блок памяти, даже если массив больше гига). если свободное пространство полностью выбрано -- создаем новую страницу, вставляя ее как список. при этом, конечно, нужно переиндексировать весь массив. благодаря фиксированному размеру "странц" переиндексация сводится к тупому сдвигу элементов таблицы индексов, размер которой пренебрежительно мал, т.е. такая операция очень быстрая.
М>в результате получается гибрид списка с массивом, обеспечивающий быстрый доступ к произвольному элементу и быструю операцию вставки/удаления элементов. особенно быстро работает вставка одного массива внутрь другого или удаление всех элементов от IDXn до IDXn+k, т.к. здесь будет одна вставка/удаления списка A в список B и небольшие передвижки в двух пограничных страницах.
На Б-дерево похоже по ощущениям.
М>но это не мое изобретение. такие структуры данных очень широко распростанены. в том числе и в файловых системах.
Ага.
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Здравствуйте, IgushevEdward, Вы писали:
IE>>Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>>>Тогда, чтобы получить индекс элемента на странице, придется бегать по списку, либо вводить дополнительную таблицу соответствия для хранения связи между индексом в массиве и положением в списке.
IE>>Небольшое уточнение на всякий случай: страницы реализованы при помощи простых двусвязных очередей (доступ — константный, вставка/удаление в начало/конец — константные), а не списка
SVZ>Не поленился, залез в код.
SVZ>
SVZ>template <class T, class Alloc>
SVZ>typename FixedDeque<T, Alloc>::iterator FixedDeque<T, Alloc>::insert(iterator it, const T& val)
SVZ>{
SVZ> if (size() + 1 > _max_size())
SVZ> throw std::out_of_range("insert(): The size has been exceeded");
SVZ> iterator to = end() + 1;
SVZ> iterator from = end();
SVZ> while (from != it) <--- !!!
SVZ> _move(--to, *--from); <--- !!!
SVZ> _move(from, val);
SVZ> if (_end == _storage_end - 1)
SVZ> _end = _storage_begin;
SVZ> else
SVZ> ++_end;
SVZ> return from;
SVZ>}
SVZ>
SVZ>Вот что делает выделенный цикл и какова получается сложность алгоритма в целом?
Во-первых, большое спасибо за такой интерес!
Да, вставка в очередь за линейное время. Размер очереди в контексте структуры O (N^1/2). Итого, с точки зрения структуры, вставка за O (N^1/2)
Здравствуйте, lxa, Вы писали:
А>>Согласен, два способа реализации. "тема константности". Что вы имеете в виду?
lxa>Указано, что "размер очередей не меняется никогда", то есть это константа.
Обычно очерерь реализуется через массивы или лист
Массивы: один массив заполняется, аллоцируется другой и так далее (получается что-то листа массивов)
Лист: тут все понятно
В IgushArray размер всех очередей фиксирован (кроме последней, она может быть меньше) и эту информацию можно использовать для того, чтобы реализовать DEQ через ОДИН массив
"Размер очередей никогда не менятеся" — это значит по мере работы со структурой (вствка и удаление) размер очередей не меняется (если вы что-то вставляется, то обязательно что-то удаляется)
Я имею ввиду — тут уже, возможно писали, что у Вас вставка/удаление получается O(N^1/2), из-за того, что O(N^1/2) якобы берут на себя deque. Но ведь их размер не меняется, то есть размер основного массива и соответственно время вставки/удаления пропорциональны N
Здравствуйте, lxa, Вы писали:
lxa>Я имею ввиду — тут уже, возможно писали, что у Вас вставка/удаление получается O(N^1/2), из-за того, что O(N^1/2) якобы берут на себя deque. Но ведь их размер не меняется, то есть размер основного массива и соответственно время вставки/удаления пропорциональны N
При вставке надо вставить всего в одном DEQ — это O (N^1/2)
( в остальных происходит вставка в начало и удаление с конца — O (1) ) * N^1/2 -> O(N^1/2)
O(N^1/2) + O(N^1/2) -> O(N^1/2)
Здравствуйте, IgushevEdward, Вы писали:
IE>( в остальных происходит вставка в начало и удаление с конца — O (1) ) * N^1/2 -> O(N^1/2)
IE>Вроде иллюстрация все показывает
Пооже, скорее в остальных происходит вставка в начало и удаление с конца — O (1) * N -> O(N)
Здравствуйте, lxa, Вы писали:
lxa>Здравствуйте, IgushevEdward, Вы писали:
IE>>( в остальных происходит вставка в начало и удаление с конца — O (1) ) * N^1/2 -> O(N^1/2)
IE>>Вроде иллюстрация все показывает
lxa>Пооже, скорее в остальных происходит вставка в начало и удаление с конца — O (1) * N -> O(N)
Здравствуйте, IgushevEdward, Вы писали:
IE>Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>>Здравствуйте, IgushevEdward, Вы писали:
IE>>>Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>>>>Тогда, чтобы получить индекс элемента на странице, придется бегать по списку, либо вводить дополнительную таблицу соответствия для хранения связи между индексом в массиве и положением в списке.
IE>>>Небольшое уточнение на всякий случай: страницы реализованы при помощи простых двусвязных очередей (доступ — константный, вставка/удаление в начало/конец — константные), а не списка
SVZ>>Не поленился, залез в код.
SVZ>>
SVZ>>template <class T, class Alloc>
SVZ>>typename FixedDeque<T, Alloc>::iterator FixedDeque<T, Alloc>::insert(iterator it, const T& val)
SVZ>>{
SVZ>> if (size() + 1 > _max_size())
SVZ>> throw std::out_of_range("insert(): The size has been exceeded");
SVZ>> iterator to = end() + 1;
SVZ>> iterator from = end();
SVZ>> while (from != it) <--- !!!
SVZ>> _move(--to, *--from); <--- !!!
SVZ>> _move(from, val);
SVZ>> if (_end == _storage_end - 1)
SVZ>> _end = _storage_begin;
SVZ>> else
SVZ>> ++_end;
SVZ>> return from;
SVZ>>}
SVZ>>
SVZ>>Вот что делает выделенный цикл и какова получается сложность алгоритма в целом?
IE>Во-первых, большое спасибо за такой интерес!
IE>Да, вставка в очередь за линейное время. Размер очереди в контексте структуры O (N^1/2). Итого, с точки зрения структуры, вставка за O (N^1/2)
Здравствуйте, IgushevEdward, Вы писали:
IE>Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.
IE>Подробное описание можно найти здесь http://igushev.ru/papers/igusharray/
IE>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!
Здравствуйте, ilnar, Вы писали:
I>Здравствуйте, IgushevEdward, Вы писали:
IE>>Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.
IE>>Подробное описание можно найти здесь http://igushev.ru/papers/igusharray/
IE>>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!
I>ставлю тест:
I>
разница в 4 раза при разнице числа элементов в 2 раза, что-то мне подсказывает, что все таки вставка O(n)
ну и видем, что std::vector<int> показывает результаты получше
Здравствуйте, ilnar, Вы писали:
I>Здравствуйте, ilnar, Вы писали:
I>>Здравствуйте, IgushevEdward, Вы писали:
IE>>>Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.
IE>>>Подробное описание можно найти здесь http://igushev.ru/papers/igusharray/
IE>>>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!
I>>ставлю тест:
I>>
I>>IgushArray<int> I>>real 32.76 I>>user 32.51 I>>sys 0.03
I>>std::vector<int> I>>real 0.18 I>>user 0.18 I>>sys 0.00
I>вставка 10000:
I>IgushArray<int> I>real 8.20 I>user 8.14 I>sys 0.00
I>std::vector<int> I>real 0.05 I>user 0.04 I>sys 0.00
I>разница в 4 раза при разнице числа элементов в 2 раза, что-то мне подсказывает, что все таки вставка O(n) I>ну и видем, что std::vector<int> показывает результаты получше
вставка 5000 тоже показывает, что вставка таки O(n)
real 208.81
user 205.11
sys 0.78
ну и стандартный вектор на 5000 вставках
real 1.07
user 1.06
sys 0.00
I>разница в 4 раза при разнице числа элементов в 2 раза, что-то мне подсказывает, что все таки вставка O(n) I>ну и видем, что std::vector<int> показывает результаты получше
Это операция вставки N элементов. Каждая вставка занммает N^1/2 (IgushArray) или N (vector).
Итого такое заполнение N^3/2 (IgushArray) или N^2 (vector).
Во-вторых структура чуствительна к заданию планируемого размера (через функцию reserve).
I>>разница в 4 раза при разнице числа элементов в 2 раза, что-то мне подсказывает, что все таки вставка O(n) I>>ну и видем, что std::vector<int> показывает результаты получше
IE>Это операция вставки N элементов. Каждая вставка занммает N^1/2 (IgushArray) или N (vector). IE>Итого такое заполнение N^3/2 (IgushArray) или N^2 (vector).
IE>Во-вторых структура чуствительна к заданию планируемого размера (через функцию reserve).
IE>Сделайте, arr.reserve(n);
Сделайте reserve и попробуйте тоже самое с 10 тыс., 100 тыс., 1 млн. объектов
I>>разница в 4 раза при разнице числа элементов в 2 раза, что-то мне подсказывает, что все таки вставка O(n) I>>ну и видем, что std::vector<int> показывает результаты получше
IE>Это операция вставки N элементов. Каждая вставка занммает N^1/2 (IgushArray) или N (vector). IE>Итого такое заполнение N^3/2 (IgushArray) или N^2 (vector).
так почему vector быстрее?
судя по рекомендации ниже, тут проблема с алгоритмом упреждающего выделения памяти для вашей структуры.
IE>Во-вторых структура чуствительна к заданию планируемого размера (через функцию reserve).
IE>Сделайте, arr.reserve(n);
сделал, стало заметно быстрее, НО
при 50000 IgushArray:
real 2.16
user 2.14
sys 0.00 vector:
real 1.08
user 1.04
sys 0.02
идем дальше, и наконец!!! победа)
при 500000 IgushArray:
real 69.98
user 68.77
sys 0.27 vector:
real 109.15
user 106.11
sys 0.77
Здравствуйте, IgushevEdward, Вы писали:
IE>Здравствуйте, ilnar, Вы писали:
I>>сделал, стало заметно быстрее, НО I>>при 50000 IgushArray: I>>real 2.16 I>>user 2.14 I>>sys 0.00 I>>vector: I>>real 1.08 I>>user 1.04 I>>sys 0.02
I>>идем дальше, и наконец!!! победа)
I>>при 500000 IgushArray: I>>real 69.98 I>>user 68.77 I>>sys 0.27 I>>vector: I>>real 109.15 I>>user 106.11 I>>sys 0.77
IE>Странно, у меня лучше результаты были при меньших числах.
IE>Но я в основном тестировал вставкой одного элемента в середину структуры (обогнал vector уже при 100 тыс. элементах)
IE>Вообще я выложил еще и тест-пак, там мой тест есть
чтобы взять тестпаки, их надо изучать, а там много, лень
поэтому наваял самое простое, про афишируемое преимучество в вставках.
Здравствуйте, ilnar, Вы писали:
I>Здравствуйте, IgushevEdward, Вы писали:
IE>>Здравствуйте, ilnar, Вы писали:
I>>>сделал, стало заметно быстрее, НО I>>>при 50000 IgushArray: I>>>real 2.16 I>>>user 2.14 I>>>sys 0.00 I>>>vector: I>>>real 1.08 I>>>user 1.04 I>>>sys 0.02
I>>>идем дальше, и наконец!!! победа)
I>>>при 500000 IgushArray: I>>>real 69.98 I>>>user 68.77 I>>>sys 0.27 I>>>vector: I>>>real 109.15 I>>>user 106.11 I>>>sys 0.77
IE>>Странно, у меня лучше результаты были при меньших числах.
IE>>Но я в основном тестировал вставкой одного элемента в середину структуры (обогнал vector уже при 100 тыс. элементах)
IE>>Вообще я выложил еще и тест-пак, там мой тест есть
I>чтобы взять тестпаки, их надо изучать, а там много, лень I>поэтому наваял самое простое, про афишируемое преимучество в вставках.
в любом случае, я бы отказался от такого кода в продакшене
если нужны быстрые вставки, и много памяти, то B-Tree, иначе стандартный вектор
Здравствуйте, ilnar, Вы писали:
I>в любом случае, я бы отказался от такого кода в продакшене I>если нужны быстрые вставки, и много памяти, то B-Tree, иначе стандартный вектор
Вы забыли про сохранение константного доступа в сочетании с быстрыми вставками и удалениями
B-Tree помоему из совсем другой оперы — это множество
Здравствуйте, IgushevEdward, Вы писали:
IE>Здравствуйте, ilnar, Вы писали:
I>>в любом случае, я бы отказался от такого кода в продакшене I>>если нужны быстрые вставки, и много памяти, то B-Tree, иначе стандартный вектор
IE>Вы забыли про сохранение константного доступа в сочетании с быстрыми вставками и удалениями
IE>B-Tree помоему из совсем другой оперы — это множество
это аналог map|multimap|... только оптимизированный под страничное использование памяти и большее оснвание при логарифме
Здравствуйте, IgushevEdward, Вы писали:
IE>Здравствуйте, ilnar, Вы писали:
I>>в любом случае, я бы отказался от такого кода в продакшене I>>если нужны быстрые вставки, и много памяти, то B-Tree, иначе стандартный вектор
IE>Вы забыли про сохранение константного доступа в сочетании с быстрыми вставками и удалениями
к сожалению, необходимость заранее знать размер портит картину ((
Здравствуйте, ilnar, Вы писали:
I>Здравствуйте, IgushevEdward, Вы писали:
IE>>Здравствуйте, ilnar, Вы писали:
I>>>в любом случае, я бы отказался от такого кода в продакшене I>>>если нужны быстрые вставки, и много памяти, то B-Tree, иначе стандартный вектор
IE>>Вы забыли про сохранение константного доступа в сочетании с быстрыми вставками и удалениями
I>к сожалению, необходимость заранее знать размер портит картину ((
Ну в случае со стандартным вектором это тоже желательно знать))
Здравствуйте, IgushevEdward, Вы писали:
IE>Здравствуйте, ilnar, Вы писали:
I>>Здравствуйте, IgushevEdward, Вы писали:
IE>>>Здравствуйте, ilnar, Вы писали:
I>>>>в любом случае, я бы отказался от такого кода в продакшене I>>>>если нужны быстрые вставки, и много памяти, то B-Tree, иначе стандартный вектор
IE>>>Вы забыли про сохранение константного доступа в сочетании с быстрыми вставками и удалениями
I>>к сожалению, необходимость заранее знать размер портит картину ((
IE>Ну в случае со стандартным вектором это тоже желательно знать))
там такое незнание не дает такую клоссальную деградацию в производительности
Здравствуйте, IgushevEdward, Вы писали:
IE>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!
Идея неплохая, но с неизменным размером страницы (очереди) оценка сложности некорректная. О-нотация подразумевает предел. Если одна страница имеет размер K, то вставка отнимает О(К) + О(N/K) операций, т.е. O(N). То, что при некоторых значениях N и K (K=N^1/2) получается число N^1/2, еще не дает правильную асимптотику. Нужен механизм динамического изменения размеров страниц, и тут нужно аккуратно с его сложностью.
Здравствуйте, D. Mon, Вы писали:
DM>Здравствуйте, IgushevEdward, Вы писали:
IE>>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!
DM>Идея неплохая, но с неизменным размером страницы (очереди) оценка сложности некорректная. О-нотация подразумевает предел. Если одна страница имеет размер K, то вставка отнимает О(К) + О(N/K) операций, т.е. O(N). То, что при некоторых значениях N и K (K=N^1/2) получается число N^1/2, еще не дает правильную асимптотику. Нужен механизм динамического изменения размеров страниц, и тут нужно аккуратно с его сложностью.
Хороший поинт! Для этого следует заранее резервировать необходимый размер функцией reserve()
Это как в хэш-таблицах, они тоже дают О(1), но надо следить за размерами, а не то выродится в O(N)
Здравствуйте, IgushevEdward, Вы писали:
IE>B-Tree помоему из совсем другой оперы — это множество
Б-дерево — это многоярусная страничная структура.
На его основе можно сделать как дерево поиска (set/map/multiset/multimap), так и как-бы-массив с доступом по индексу.
Изначально Б-деревья разрабатывались именно как страничные структуры — чтобы влезать в страницу оперативной памяти (минимизировать подкачку с диска), блок кучи или линейку кэша. Опять же, полупустые страницы с перспективой их заполнения уменьшают фрагментацию кучи.
Поэтому асимптотики там как на доступ, так и на изменение не O(1), а O(logN), но с хорошей константой.
Важный момент: у Б-дерева высота зависит от количества данных, а у ИнгушАррея — высота всегда равна 3 (массив деков, дек сам по себе двухуровневый).
Почему бы не сделать многоуровневый дек "по мотивам"? Формально, его высота — это O(logN), а следовательно, доступ будет логарифмический. Но какое основание у этого логарифма, э?
Выгода здесь, во-первых, в быстрой арифметике (размер каждой страницы — степень 2); во-вторых, перебалансировка будет случаться реже (не на каждое квадратное число, а на каждую степень степени 2).
Перекуём баги на фичи!
Re[3]: Массив с быстрой вставкой/удалением
От:
Аноним
Дата:
03.02.12 18:28
Оценка:
Здравствуйте, IgushevEdward, Вы писали:
IE>Хороший поинт! Для этого следует заранее резервировать необходимый размер функцией reserve()
Чтобы заранее резервировать размер, его нужно заранее знать.
Тогда уж ведем еще одно требование, для круглого счета: нужно заранее знать,в каком порядке мы будем вставлять элементы в свой массив.
И в этом случае нам не нужен ни супер-контейнер, ни даже функция reserve(): аллоцировали сразу весь нужный нам массив и записали в него значения в цикле тупо индексацией через operator[].
Сравним производительность std::vector и IgushArray в таких условиях?
Здравствуйте, Кодт, Вы писали:
К>Важный момент: у Б-дерева высота зависит от количества данных, а у ИнгушАррея — высота всегда равна 3 (массив деков, дек сам по себе двухуровневый).
Я так понял, что 2 — в деках строго по одному массиву.
К>Почему бы не сделать многоуровневый дек "по мотивам"? Формально, его высота — это O(logN), а следовательно, доступ будет логарифмический. Но какое основание у этого логарифма, э?
К>Выгода здесь, во-первых, в быстрой арифметике (размер каждой страницы — степень 2); во-вторых, перебалансировка будет случаться реже (не на каждое квадратное число, а на каждую степень степени 2).
В скале и кложуре так как раз вектора сделаны. Там основание 32.
Здравствуйте, D. Mon, Вы писали:
К>>Важный момент: у Б-дерева высота зависит от количества данных, а у ИнгушАррея — высота всегда равна 3 (массив деков, дек сам по себе двухуровневый). DM>Я так понял, что 2 — в деках строго по одному массиву.
Если там "дек на коленке", чисто proof of concept, то да. Но у такого дека дорогая вставка в голову.
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>За счет фиксированного размера дек получился простой, как плинтус. По реализации близок к кольцевому списку.
А, ну да. У нас же типичные операции групповые: вставить в голову и выдернуть из хвоста; вставить в хвост и выдернуть из головы. Для кольцевого списка такая пара вставить-выдернуть стоит O(1).
Единственно, что при перебалансировке будут одиночные вставки/удаления.
Отсюда мораль, кстати. Нужно ввести гистерезис — увеличивать размеры очередей при достижении верхнего порога количества элементов; уменьшать размеры при достижении нижнего порога. А в промежутке — только менять количество очередей (размер массива верхнего уровня).
Иначе у нас будет очень дорогой дребезг вокруг квадратного числа.
SVZ>На мой взгляд реализация контейнера получилась неплохая. Если додумать, что делать с начальным размером, то можно использовать и в рабочем коде.
В принципе, да.
Автору можно посоветовать — для красоты кода — сделать отдельно реализацию с примитивным интерфейсом (доступ по индексу), и отдельно — STL-like фронтэнд к нему.
Тогда и разные политики с начальным размером, с гистерезисом и т.д. легче вводить.
Здравствуйте, LaptevVV, Вы писали:
LVV>Здравствуйте, IgushevEdward, Вы писали:
IE>>Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.
IE>>Подробное описание можно найти здесь http://igushev.ru/papers/igusharray/
IE>>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)! LVV>Очевидно, что вам не знакома вот эта книга: Флорес И. Структуры и управление данными. М.: Радио и связь, 1982. LVV>В ней подобные структуры описаны. И проведен анализ производительности.
А в более современных книжках такое есть? А то Флорес как-то не находится.
Здравствуйте, Mazay, Вы писали:
IE>>>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)! LVV>>Очевидно, что вам не знакома вот эта книга: Флорес И. Структуры и управление данными. М.: Радио и связь, 1982. LVV>>В ней подобные структуры описаны. И проведен анализ производительности.
M>А в более современных книжках такое есть? А то Флорес как-то не находится.
Бумажного Флореса можно купить на ALIB.ru — это букинистический магазин. Компьютерного просто нет.
С момента изобретения Б-дереьев подобные структуры как-то исчезли из книжек.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
M>>Из результатов видно, что время операции удаления std::vector растет линейно вместе с количеством элементов, а время операции удаления IgushArray растет как N1/2
M>>Ага. А N1/2 — это не линейно?
IE>При копировании из word'а спетенное написание 1/2 пропало. Надо читать N^1/2. Сейчас поправлю
Так бы сразу и писал что на кольцевых очередях сделал. Список очередей это прикольно, ага.
С тестами что-то непонятное. Ты что, оптимизацию компилятора не включал? Я сейчас прогоняют твои тесты и у меня время совсем другое:
Accessing elements by number
Size: 1000 IgushArray: 0 vector: 0 Same time OK
Size: 10000 IgushArray: 0 vector: 0 Same time OK
Size: 100000 IgushArray: 0 vector: 0 Same time OK
Size: 1000000 IgushArray: 0 vector: 0 Same time OK
Size: 10000000 IgushArray: 0 vector: 0 Same time OK
---------------------------------------------------------------------------
Accessing elements by iterator
Size: 1000 IgushArray: 0 vector: 0 Same time OK
Size: 10000 IgushArray: 90 vector: 0 Worse: Infinity OK
Size: 100000 IgushArray: 870 vector: 0 Worse: Infinity OK
Size: 1000000 IgushArray: 11580 vector: 0 Worse: Infinity OK
Size: 10000000 IgushArray: 119840 vector: 0 Worse: Infinity OK
---------------------------------------------------------------------------
Inserting one element int the middle
Size: 1000 IgushArray: 0 vector: 0 Same time OK
Size: 10000 IgushArray: 0 vector: 0 Same time OK
Size: 100000 IgushArray: 0 vector: 60 Better: Infinity OK
Size: 1000000 IgushArray: 20 vector: 670 Better: 34 OK
Size: 10000000 IgushArray: 110 vector: 7960 Better: 72 OK
---------------------------------------------------------------------------
Erasing one element from the middle
Size: 1000 IgushArray: 0 vector: 0 Same time OK
Size: 10000 IgushArray: 0 vector: 0 Same time OK
Size: 100000 IgushArray: 10 vector: 20 Better: 2 OK
Size: 1000000 IgushArray: 10 vector: 670 Better: 67 OK
Size: 10000000 IgushArray: 60 vector: 7950 Better: 1.3e+02 OK
---------------------------------------------------------------------------
Inserting a number of elements at the middle
Size: 1000 Count: 1 IgushArray: 0 vector: 10 Better: Infinity OK
Size: 1000 Count: 10 IgushArray: 0 vector: 0 Same time OK
Size: 1000 Count: 100 IgushArray: 0 vector: 0 Same time OK
Size: 1000 Count: 1000 IgushArray: 20 vector: 0 Worse: Infinity OK
Size: 10000 Count: 1 IgushArray: 0 vector: 10 Better: Infinity OK
Size: 10000 Count: 10 IgushArray: 0 vector: 0 Same time OK
Size: 10000 Count: 100 IgushArray: 10 vector: 0 Worse: Infinity OK
Size: 10000 Count: 1000 IgushArray: 10 vector: 10 Same time OK
Size: 10000 Count: 10000 IgushArray: 80 vector: 20 Worse: 4 OK
Size: 100000 Count: 1 IgushArray: 10 vector: 70 Better: 7 OK
Size: 100000 Count: 10 IgushArray: 30 vector: 50 Better: 1.7 OK
Size: 100000 Count: 100 IgushArray: 310 vector: 50 Worse: 6.2 OK
Size: 100000 Count: 1000 IgushArray: 180 vector: 50 Worse: 3.6 OK
Size: 100000 Count: 10000 IgushArray: 620 vector: 60 Worse: 10 OK
Size: 100000 Count: 100000 IgushArray: 800 vector: 250 Worse: 3.2 OK
Size: 1000000 Count: 1 IgushArray: 10 vector: 800 Better: 80 OK
Size: 1000000 Count: 10 IgushArray: 110 vector: 830 Better: 7.5 OK
Size: 1000000 Count: 100 IgushArray: 940 vector: 750 Worse: 1.3 OK
Size: 1000000 Count: 1000 IgushArray: 30 vector: 720 Better: 24 OK
Size: 1000000 Count: 10000 IgushArray: 90 vector: 860 Better: 9.6 OK
Size: 1000000 Count: 100000 IgushArray: 790 vector: 1080 Better: 1.4 OK
Size: 1000000 Count: 1000000 IgushArray: 8030 vector: 3050 Worse: 2.6 OK
Size: 10000000 Count: 1 IgushArray: 90
Здравствуйте, Mazay, Вы писали:
M>С тестами что-то непонятное. Ты что, оптимизацию компилятора не включал? Я сейчас прогоняют твои тесты и у меня время совсем другое:
Здравствуйте, IgushevEdward, Вы писали:
IE>Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.
IE>Подробное описание можно найти здесь http://igushev.ru/papers/igusharray/
IE>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!
С теоретической точки зрения, поскольку у тебя очереди фиксированного размера, то они не зависят от числа элементов N и по отношению к нему являются константой, то есть сложность все равно линейная. Это, подчеркиваю, чисто логические рассуждения, и доводы про заранее приблизительно известное количество элементов здесь не работают.
С практической, если у тебя заранее есть оценка количества элементов, то это сильно меняет дело. std::vector'у тоже, вообще-то, можно сделать reserve.
Ну и вроде про std::vector сразу говорится, что он для вставки в середину и удаление из середины неоптимален. Так что выбор контейнера для сравнения неадекватен.
Здравствуйте, Аноним, Вы писали:
А>С теоретической точки зрения, поскольку у тебя очереди фиксированного размера, то они не зависят от числа элементов N и по отношению к нему являются константой, то есть сложность все равно линейная. Это, подчеркиваю, чисто логические рассуждения, и доводы про заранее приблизительно известное количество элементов здесь не работают.
Что-то не очень логические рассуждения.
Если у нас есть K очередей фиксированного размера M (K*M >= N), то
операция вставки складывается из
— вставки в произвольное место очереди и выпихивания с хвоста — O(M)
— O(K) переносов: вставка в голову и выпихивание с хвоста — для кольцевого буфера это O(1)
— вставки в голову у последней незаполненной очереди — O(1), либо создание новой очереди — O(M)
Итого O(K+M).
Аналогично, удаление складывается из
— выпихивания с головы последней очереди — O(1)
— O(K) переносов: вставка в хвост и выпихивание с головы
— удаление из произвольного места и вставка в хвост — O(M)
Итого, O(K+M).
Можно рассмотреть время заполнения массива N элементами в худшем случае, с учётом перебалансировок.
Не считал, но полагаю, что будет что-то вида O(N*sqrt(N)).
И это смотря как резервировать память под кольцевые буферы. Если как с векторами, с двукратным запасом... Надо тщательно посчитать.
Перекуём баги на фичи!
