Re[8]: Массив с быстрой вставкой/удалением - Алгоритмы

IE>http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D1%83%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%B0%D1%8F_%D0%BE%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C

IE>(она же очередь с двуями концами, double-ended queue, deque)

Извините, упустил, так как в общем случае There are at least two common ways to efficiently implement a deque: with a modified dynamic array or with a doubly linked list, а конкретно deque из C++ упоминается вскользь ближе к концу. Но все равно тема константности размера не раскрыта.

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

IE>>http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D1%83%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%B0%D1%8F_%D0%BE%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C

IE>>(она же очередь с двуями концами, double-ended queue, deque)

lxa>Извините, упустил, так как в общем случае There are at least two common ways to efficiently implement a deque: with a modified dynamic array or with a doubly linked list, а конкретно deque из C++ упоминается вскользь ближе к концу. Но все равно тема константности размера не раскрыта.

Согласен, два способа реализации. "тема константности". Что вы имеете в виду?

А>Согласен, два способа реализации. "тема константности". Что вы имеете в виду?

Указано, что "размер очередей не меняется никогда", то есть это константа.

Здравствуйте, 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)

Вставка в начало и удаление с конца — O (1)

Количство очередей — N^1/2, а не 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)

ну и теперь умножь на число таких очередей ниже

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

I>ну и теперь умножь на число таких очередей ниже

Умножать не надо. в последующих очередях только операция вставки в начало и удаление с конца — O (1)

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

IE>Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.

IE>Подробное описание можно найти здесь http://igushev.ru/papers/igusharray/

IE>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!

ставлю тест:

#include <stdio.h>
#include <stdexcept>
#include <vector>
#include "igush_array.h"

int main()
{
#if 0
        IgushArray<int> arr;
#else
        std::vector<int> arr;
#endif
        for(int i=20000; i>=0; i--)
        {
                arr.insert(arr.begin(), i);
        }
        return 0;
}

IgushArray<int>
real 32.76
user 32.51
sys 0.03

std::vector<int>
real 0.18
user 0.18
sys 0.00

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

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

IE>>Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.

IE>>Подробное описание можно найти здесь http://igushev.ru/papers/igusharray/

IE>>Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!

I>ставлю тест:

I>

I>#include <stdio.h>
I>#include <stdexcept>
I>#include <vector>
I>#include "igush_array.h"

I>int main()
I>{
I>#if 0
I>        IgushArray<int> arr;
I>#else
I>        std::vector<int> arr;
I>#endif
I>        for(int i=20000; i>=0; i--)
I>        {
I>                arr.insert(arr.begin(), i);
I>        }
I>        return 0;
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

вставка 10000:

IgushArray<int>
real 8.20
user 8.14
sys 0.00

std::vector<int>
real 0.05
user 0.04
sys 0.00

разница в 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>>#include <stdio.h>
I>>#include <stdexcept>
I>>#include <vector>
I>>#include "igush_array.h"

I>>int main()
I>>{
I>>#if 0
I>>        IgushArray<int> arr;
I>>#else
I>>        std::vector<int> arr;
I>>#endif
I>>        for(int i=20000; i>=0; i--)
I>>        {
I>>                arr.insert(arr.begin(), i);
I>>        }
I>>        return 0;
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

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

I>>

I>>#include <stdio.h>
I>>#include <stdexcept>
I>>#include <vector>
I>>#include "igush_array.h"

I>>int main()
I>>{
I>>#if 0
I>>        IgushArray<int> arr;
I>>#else
I>>        std::vector<int> arr;
I>>#endif
I>>        for(int i=20000; i>=0; i--)
I>>        {
I>>                arr.insert(arr.begin(), i);
I>>        }
I>>        return 0;
I>>}
I>>

I>разница в 4 раза при разнице числа элементов в 2 раза, что-то мне подсказывает, что все таки вставка O(n)
I>ну и видем, что std::vector<int> показывает результаты получше

Это операция вставки N элементов. Каждая вставка занммает N^1/2 (IgushArray) или N (vector).
Итого такое заполнение N^3/2 (IgushArray) или N^2 (vector).

Во-вторых структура чуствительна к заданию планируемого размера (через функцию reserve).

Сделайте, arr.reserve(n);

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

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

I>>>

I>>>#include <stdio.h>
I>>>#include <stdexcept>
I>>>#include <vector>
I>>>#include "igush_array.h"

I>>>int main()
I>>>{
I>>>#if 0
I>>>        IgushArray<int> arr;
I>>>#else
I>>>        std::vector<int> arr;
I>>>#endif
I>>>        for(int i=20000; i>=0; i--)
I>>>        {
I>>>                arr.insert(arr.begin(), i);
I>>>        }
I>>>        return 0;
I>>>}
I>>>

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

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

I>>>

I>>>#include <stdio.h>
I>>>#include <stdexcept>
I>>>#include <vector>
I>>>#include "igush_array.h"

I>>>int main()
I>>>{
I>>>#if 0
I>>>        IgushArray<int> arr;
I>>>#else
I>>>        std::vector<int> arr;
I>>>#endif
I>>>        for(int i=20000; i>=0; i--)
I>>>        {
I>>>                arr.insert(arr.begin(), i);
I>>>        }
I>>>        return 0;
I>>>}
I>>>

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

Здравствуйте, 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

Странно, у меня лучше результаты были при меньших числах.

Но я в основном тестировал вставкой одного элемента в середину структуры (обогнал vector уже при 100 тыс. элементах)

Вообще я выложил еще и тест-пак, там мой тест есть

Здравствуйте, 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 помоему из совсем другой оперы — это множество

От:	lxa	http://aliakseis.livejournal.com
Дата:	03.02.12 10:39
Оценка:

	От:	Аноним
	Дата:	03.02.12 10:46
	Оценка:

От:	lxa	http://aliakseis.livejournal.com
Дата:	03.02.12 10:55
Оценка:

От:	IgushevEdward	www.igushev.ru
Дата:	03.02.12 11:26
Оценка:

От:	lxa	http://aliakseis.livejournal.com
Дата:	03.02.12 11:44
Оценка: