Аннотация:
В статье приводится пример реализации нестандартного контейнера, позволяющего обеспечить приемлемую скорость доступа к произвольному элементу и вставки/удаления в произвольную позицию.
Re: Создание эффективного контейнера для работы со списком б
А>Авторы: А>Алексей Семенюк
А>Аннотация: А>В статье приводится пример реализации нестандартного контейнера, позволяющего обеспечить приемлемую скорость доступа к произвольному элементу и вставки/удаления в произвольную позицию.
Ну что ж, аннотация достойная, да и содержание не подкачало.
Еще бы саму статью почитать...
А>Авторы: А>Алексей Семенюк
А>Аннотация: А>В статье приводится пример реализации нестандартного контейнера, позволяющего обеспечить приемлемую скорость доступа к произвольному элементу и вставки/удаления в произвольную позицию.
Это какое-то ноу-хау или просто std::list<std::vector<xxx> >?
Re[2]: Создание эффективного контейнера для работы со списко
Здравствуйте, _AK_, Вы писали:
_AK>Здравствуйте, Аноним, Вы писали:
А>>Статья:
А>>Авторы: А>>Алексей Семенюк
А>>Аннотация: А>>В статье приводится пример реализации нестандартного контейнера, позволяющего обеспечить приемлемую скорость доступа к произвольному элементу и вставки/удаления в произвольную позицию.
_AK>Это какое-то ноу-хау или просто std::list<std::vector<xxx> >?
А это разве не deque?
Re: Создание эффективного контейнера для работы со списком б
То есть вместо std::list<T> организовать
1. статический массив определенного размера
2. переменная показывающая количество элементов в массиве
3. И соответственно переменные указатели на предыдущую и следующую страницы. Этим увеличим скорость прохода и скорость при балансировке страниц.
Правда здесь существенна зависимость от элемента массива, но можно держать и ссылку.
Здесь выигрыш в том, что поиск будет происходить только по дереву, а вставка и соответственно копирование будет ограничиваться размером массива в сегменте.
При случае когда все элементы в кэше это может и недавать определенного выигрыша, при поиске — вставке, но когда данные не попадают в кэш для memmove в помощь придет DDR память, в отличие от прохождении по списку элементов находящихся в разных областях памяти. И соответственно сам поиск значительно быстрее.
Возможно организовать и аналог Б+ дерева, только в узловых элементах массива содержать ссылку на страницу и количество элементовна странице, а в дополнительных переменных держать общее количество элементов в подчиненных страницах.
Если же рассматривать скорость вставки то на примере Б+ дерева вставка структуры (Key,Value) состоящих из итнов миллиона случайных элементов на Athlon XP 2400+ состовляет порядка 1.4 сек, половина на поиск (хотя и на дженериках но с виртуальным компаратором) половина на вставку с емкостью массива в 64 элемента.
Во всяком случае интересно было бы посмотреть на результаты хотя бы при первом подходе.
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Re[2]: Создание эффективного контейнера для работы со списко
От:
Аноним
Дата:
18.06.04 11:26
Оценка:
Здравствуйте, _AK_, Вы писали:
_AK>Здравствуйте, Аноним, Вы писали:
А>>Статья:
А>>Авторы: А>>Алексей Семенюк
А>>Аннотация: А>>В статье приводится пример реализации нестандартного контейнера, позволяющего обеспечить приемлемую скорость доступа к произвольному элементу и вставки/удаления в произвольную позицию.
_AK>Это какое-то ноу-хау или просто std::list<std::vector<xxx> >?
Это точно не std::list<std::vector<xxx> >. Пусть будет ноу-хау
Алексей Семенюк
Re[2]: Создание эффективного контейнера для работы со списко
S> То есть вместо std::list<T> организовать S>1. статический массив определенного размера S>2. переменная показывающая количество элементов в массиве S>3. И соответственно переменные указатели на предыдущую и следующую страницы. Этим увеличим скорость прохода и скорость при балансировке страниц.
Если я все правильно понял, это описание deque
После того, как статью дописал, подумал, что вместо связки binary_tree+linked_list можно использовать
binary_tree+deque(s), т.е. в узлах дерева хранить не указатели на элементы списка, а deque, (т.е. на каждый узел по deque). В принципе сделать такую реализацию не сложно, т.к. многое мз уже написанного кода можно использовать повторно. Если будет время и это будет кому-то сильно интересно, можно взяться.
Хотя в чем выигрышь такой конструкции по сравнению с тем что уже сделано я не вижу, разве что только ускорится доступ к произвольному элементу последовательности. В минусе то, что вставка/удаление элементов будет дороже и скорость обхода последовательности с исп. const_iterator замедлиться (реализация const_iterator будет идентична iterator).
Вообщем не все так однозначно.
S> Правда здесь существенна зависимость от элемента массива, но можно держать и ссылку.
S> Здесь выигрыш в том, что поиск будет происходить только по дереву, а вставка и соответственно копирование будет ограничиваться размером массива в сегменте. S> При случае когда все элементы в кэше это может и недавать определенного выигрыша, при поиске — вставке, но когда данные не попадают в кэш для memmove в помощь придет DDR память, в отличие от прохождении по списку элементов находящихся в разных областях памяти. И соответственно сам поиск значительно быстрее.
S> Возможно организовать и аналог Б+ дерева, только в узловых элементах массива содержать ссылку на страницу и количество элементовна странице, а в дополнительных переменных держать общее количество элементов в подчиненных страницах.
S> Если же рассматривать скорость вставки то на примере Б+ дерева вставка структуры (Key,Value) состоящих из итнов миллиона случайных элементов на Athlon XP 2400+ состовляет порядка 1.4 сек, половина на поиск (хотя и на дженериках но с виртуальным компаратором) половина на вставку с емкостью массива в 64 элемента. S> Во всяком случае интересно было бы посмотреть на результаты хотя бы при первом подходе.
Алексей Семенюк.
Re[2]: Создание эффективного контейнера для работы со списко
Здравствуйте, jazzer, Вы писали:
J>Здравствуйте, Аноним, Вы писали:
А>>Статья:
А>>Авторы: А>>Алексей Семенюк
А>>Аннотация: А>>В статье приводится пример реализации нестандартного контейнера, позволяющего обеспечить приемлемую скорость доступа к произвольному элементу и вставки/удаления в произвольную позицию.
J>Ну что ж, аннотация достойная, да и содержание не подкачало. J>Еще бы саму статью почитать...
Спасибо
Re[2]: Создание эффективного контейнера для работы со списко
Здравствуйте, Lorenzo_LAMAS, Вы писали:
J>>Еще бы саму статью почитать...
L_L>Какую такую статью? Просто ставь оценку и проходи, не задерживай
L_L>Если серьезно, то я не догнал. Где статья то? Если она недоступна, то нафига топик?
Статья в журнале.
Re[3]: Создание эффективного контейнера для работы со списко
Здравствуйте, <Аноним>, Вы писали:
А>Здравствуйте, Serginio1, Вы писали:
S>>Здравствуйте, Алексей Семенюк, Вы писали:
S>>Попытаюсь посоветовать организацию сегмента анологичную организации страниц в Б+ дереве S>>http://www.rsdn.ru/Forum/Message.aspx?mid=525083&only=1
S>> То есть вместо std::list<T> организовать S>>1. статический массив определенного размера S>>2. переменная показывающая количество элементов в массиве S>>3. И соответственно переменные указатели на предыдущую и следующую страницы. Этим увеличим скорость прохода и скорость при балансировке страниц. А>Если я все правильно понял, это описание deque
Вот любители всяких там deque.
public class seg<T>
{
T PageItems[n]; // например n =64;int Count;
seg<T> Parent;
seg<T> Left;
seg<T> Right;
}
А>После того, как статью дописал, подумал, что вместо связки binary_tree+linked_list можно использовать А>binary_tree+deque(s), т.е. в узлах дерева хранить не указатели на элементы списка, а deque, (т.е. на каждый узел по deque). В принципе сделать такую реализацию не сложно, т.к. многое мз уже написанного кода можно использовать повторно. Если будет время и это будет кому-то сильно интересно, можно взяться. А>Хотя в чем выигрышь такой конструкции по сравнению с тем что уже сделано я не вижу, разве что только ускорится доступ к произвольному А>элементу последовательности. В минусе то, что вставка/удаление элементов будет дороже
Пример я тебе уже приводил. Приводил на милионных элементах вставка, с реорганизацией дерева состовляет порядка 1.4 сек.
Смотрим твои результаты 56 сек. Затраты на поиск у тебя намного выше.
А> и скорость обхода последовательности с исп. const_iterator замедлиться (реализация const_iterator будет идентична iterator). А>Вообщем не все так однозначно.
Проход очень быстрый примерно такой
internal struct Bookmark<K, V>
{
internal LeafPage<K, V> _page;
internal int _index;
public bool IsNull
{
get { return _page == null; }
}
public bool Next()
{
_index++;
if (_index >= _page.Count)
{
if (_page.NextPage == null)
return false;
else
{
_index = 0;
_page = _page.NextPage;
}
}
return true;
}
public bool Prior()
{
_index--;
if (_index < 0)
{
if (_page.PriorPage == null)
{ return false; }
else
{
_page = _page.PriorPage;
_index = _page.Count - 1;
}
}
return true;
}
public bool Selected
{
get
{
return ((_page != null) && (_page.Count > 0) && (_index >= 0)
&& (_index < _page.Count));
}
}
Проход по миллиону элементов при таком подходе 2 сотые сек. (точно не помню)
S>> Правда здесь существенна зависимость от элемента массива, но можно держать и ссылку.
S>> Здесь выигрыш в том, что поиск будет происходить только по дереву, а вставка и соответственно копирование будет ограничиваться размером массива в сегменте. S>> При случае когда все элементы в кэше это может и недавать определенного выигрыша, при поиске — вставке, но когда данные не попадают в кэш для memmove в помощь придет DDR память, в отличие от прохождении по списку элементов находящихся в разных областях памяти. И соответственно сам поиск значительно быстрее.
S>> Возможно организовать и аналог Б+ дерева, только в узловых элементах массива содержать ссылку на страницу и количество элементовна странице, а в дополнительных переменных держать общее количество элементов в подчиненных страницах.
S>> Если же рассматривать скорость вставки то на примере Б+ дерева вставка структуры (Key,Value) состоящих из итнов миллиона случайных элементов на Athlon XP 2400+ состовляет порядка 1.4 сек, половина на поиск (хотя и на дженериках но с виртуальным компаратором) половина на вставку с емкостью массива в 64 элемента. S>> Во всяком случае интересно было бы посмотреть на результаты хотя бы при первом подходе.
А>Алексей Семенюк.
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Re[4]: Создание эффективного контейнера для работы со списко
public V Value
{
get { return _page.PageItems[_index].Value; }
set { _page.PageItems[_index].Value = value; }
}
public K Key
{
get { return _page.PageItems[_index].Key; }
}
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Re[4]: Создание эффективного контейнера для работы со списко
писал про сортированный список, тут другой случай:
обход элементов осуществляется в том же порядке, в каком они были добавлены в контейнер. В этом фишка
S>Здравствуйте, <Аноним>, Вы писали:
А>>Здравствуйте, Serginio1, Вы писали:
S>>>Здравствуйте, Алексей Семенюк, Вы писали:
S>>>Попытаюсь посоветовать организацию сегмента анологичную организации страниц в Б+ дереве S>>>http://www.rsdn.ru/Forum/Message.aspx?mid=525083&only=1
S>>> То есть вместо std::list<T> организовать S>>>1. статический массив определенного размера S>>>2. переменная показывающая количество элементов в массиве S>>>3. И соответственно переменные указатели на предыдущую и следующую страницы. Этим увеличим скорость прохода и скорость при балансировке страниц. А>>Если я все правильно понял, это описание deque S> Вот любители всяких там deque. S>
S> public class seg<T>
S> {
S> T PageItems[n]; // например n =64;
S> int Count;
S> seg<T> Parent;
S> seg<T> Left;
S> seg<T> Right;
S> }
S>
А>>После того, как статью дописал, подумал, что вместо связки binary_tree+linked_list можно использовать А>>binary_tree+deque(s), т.е. в узлах дерева хранить не указатели на элементы списка, а deque, (т.е. на каждый узел по deque). В принципе сделать такую реализацию не сложно, т.к. многое мз уже написанного кода можно использовать повторно. Если будет время и это будет кому-то сильно интересно, можно взяться. А>>Хотя в чем выигрышь такой конструкции по сравнению с тем что уже сделано я не вижу, разве что только ускорится доступ к произвольному А>элементу последовательности. В минусе то, что вставка/удаление элементов будет дороже S> Пример я тебе уже приводил. Приводил на милионных элементах вставка, с реорганизацией дерева состовляет порядка 1.4 сек. S> Смотрим твои результаты 56 сек. Затраты на поиск у тебя намного выше.
А>> и скорость обхода последовательности с исп. const_iterator замедлиться (реализация const_iterator будет идентична iterator). А>>Вообщем не все так однозначно. S> Проход очень быстрый примерно такой
S>
S>> Правда здесь существенна зависимость от элемента массива, но можно держать и ссылку.
S>>> Здесь выигрыш в том, что поиск будет происходить только по дереву, а вставка и соответственно копирование будет ограничиваться размером массива в сегменте. S>>> При случае когда все элементы в кэше это может и недавать определенного выигрыша, при поиске — вставке, но когда данные не попадают в кэш для memmove в помощь придет DDR память, в отличие от прохождении по списку элементов находящихся в разных областях памяти. И соответственно сам поиск значительно быстрее.
S>>> Возможно организовать и аналог Б+ дерева, только в узловых элементах массива содержать ссылку на страницу и количество элементовна странице, а в дополнительных переменных держать общее количество элементов в подчиненных страницах.
S>>> Если же рассматривать скорость вставки то на примере Б+ дерева вставка структуры (Key,Value) состоящих из итнов миллиона случайных элементов на Athlon XP 2400+ состовляет порядка 1.4 сек, половина на поиск (хотя и на дженериках но с виртуальным компаратором) половина на вставку с емкостью массива в 64 элемента. S>>> Во всяком случае интересно было бы посмотреть на результаты хотя бы при первом подходе.
А>>Алексей Семенюк.
Re[5]: Создание эффективного контейнера для работы со списко
писал про сортированный список, тут другой случай: A>обход элементов осуществляется в том же порядке, в каком они были добавлены в контейнер. В этом фишка
Так в массивы они добавляются именно в ту позицию в которую ты хочешь. Просто в Б+ деревьях эта позиция определяется бинарным поиском,
у тебя иначе, но сами структуры данных близки.
То есть находишь сегмент
public class seg<T>
{
T PageItems[n]; // например n =64;int Count;
seg<T> Parent;
seg<T> Left;
seg<T> Right;
}
Находишь позицию куда вставить раздвигаешь массив и вставляешь элемент в нужную позицию.
Если массив полностью заполнен перекидываешь элементы вправо или влево или выделяешь новый сенмент. и перекидываешь половину элементов.
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Re[4]: Создание эффективного контейнера для работы со списко
писал про сортированный список, тут другой случай: A>>обход элементов осуществляется в том же порядке, в каком они были добавлены в контейнер. В этом фишка
S> Так в массивы они добавляются именно в ту позицию в которую ты хочешь. Просто в Б+ деревьях эта позиция определяется бинарным поиском, S> у тебя иначе, но сами структуры данных близки.
Так и у меня бинарным поиском позиция ищется. Потом правда приходится немного по мписку пройтись, чтобы точно позицию получить.
S> То есть находишь сегмент
S>
S> public class seg<T>
S> {
S> T PageItems[n]; // например n =64;
S> int Count;
S> seg<T> Parent;
S> seg<T> Left;
S> seg<T> Right;
S> }
S>
S> Находишь позицию куда вставить раздвигаешь массив и вставляешь элемент в нужную позицию. S> Если массив полностью заполнен перекидываешь элементы вправо или влево или выделяешь новый сенмент. и перекидываешь половину элементов.
Вообщем я идею понял более-менее.
Re[6]: Создание эффективного контейнера для работы со списко
писал про сортированный список, тут другой случай: A>>обход элементов осуществляется в том же порядке, в каком они были добавлены в контейнер. В этом фишка
S> Так в массивы они добавляются именно в ту позицию в которую ты хочешь. Просто в Б+ деревьях эта позиция определяется бинарным поиском, S> у тебя иначе, но сами структуры данных близки. S> То есть находишь сегмент
S>
S> public class seg<T>
S> {
S> T PageItems[n]; // например n =64;
S> int Count;
seg<T>> Parent;
seg<T>> Left;
seg<T>> Right;
S> }
S>
S> Находишь позицию куда вставить раздвигаешь массив и вставляешь элемент в нужную позицию. S> Если массив полностью заполнен перекидываешь элементы вправо или влево или выделяешь новый сенмент. и перекидываешь половину элементов.
Только прошу прощения в твоем варианте должна быть такого плана
public class seg<T>
{
T PageItems[n]; // например n =64;
int Count;
seg<T>> Parent;
seg<T>> ChildLeft;
seg<T>> ChildRight;
seg<T>> Prior; // указатель на следующий сегмент
seg<T>> Next; // указатель на следующий сегмент
}
Я думаю так понятней будет. И соответственно проход быстрый.
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Re[7]: Создание эффективного контейнера для работы со списко
S>> Так в массивы они добавляются именно в ту позицию в которую ты хочешь. Просто в Б+ деревьях эта позиция определяется бинарным поиском, S>> у тебя иначе, но сами структуры данных близки. A>Так и у меня бинарным поиском позиция ищется. Потом правда приходится немного по мписку пройтись, чтобы точно позицию получить.
Вот про это то я как раз и говорю.
Кстати добавил бы тест на поиск массиве рассортированных IDX на запоненном slist и list в полном диапозоне. При не попадании в кэш поиск твоим методом должен сильно тормозится.
И оценить время на построение дерева.
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Re[8]: Создание эффективного контейнера для работы со списко
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, alsemm, Вы писали:
S>>> Так в массивы они добавляются именно в ту позицию в которую ты хочешь. Просто в Б+ деревьях эта позиция определяется бинарным поиском, S>>> у тебя иначе, но сами структуры данных близки. A>>Так и у меня бинарным поиском позиция ищется. Потом правда приходится немного по мписку пройтись, чтобы точно позицию получить. S> Вот про это то я как раз и говорю.
Да, есть там такая мерзость.
S> Кстати добавил бы тест на поиск массиве рассортированных IDX на запоненном slist и list в полном диапозоне. При не попадании в кэш поиск твоим методом должен сильно тормозится.
На словах непонятно, псевдокод приведи чего сравнивать.
S> И оценить время на построение дерева.
Согласен, лишним не будет.
