Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную 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)
