Аннотация:
В статье приводится пример реализации нестандартного контейнера, позволяющего обеспечить приемлемую скорость доступа к произвольному элементу и вставки/удаления в произвольную позицию.
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> И оценить время на построение дерева.
Согласен, лишним не будет.
Re[7]: Создание эффективного контейнера для работы со списко
писал про сортированный список, тут другой случай: 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>> Если массив полностью заполнен перекидываешь элементы вправо или влево или выделяешь новый сенмент. и перекидываешь половину элементов.
S> Только прошу прощения в твоем варианте должна быть такого плана
S> public class seg<T> S> { S> T PageItems[n]; // например n =64; S> int Count; S> seg<T>> Parent; S> seg<T>> ChildLeft; S> seg<T>> ChildRight; S> seg<T>> Prior; // указатель на следующий сегмент S> seg<T>> Next; // указатель на следующий сегмент S> }
S> Я думаю так понятней будет. И соответственно проход быстрый.
Ага.
Re[9]: Создание эффективного контейнера для работы со списко
Здравствуйте, alsemm, Вы писали:
A>Здравствуйте, Serginio1, Вы писали:
S>>Здравствуйте, alsemm, Вы писали:
S>>>> Так в массивы они добавляются именно в ту позицию в которую ты хочешь. Просто в Б+ деревьях эта позиция определяется бинарным поиском, S>>>> у тебя иначе, но сами структуры данных близки. A>>>Так и у меня бинарным поиском позиция ищется. Потом правда приходится немного по мписку пройтись, чтобы точно позицию получить. S>> Вот про это то я как раз и говорю. A>Да, есть там такая мерзость.
S>> Кстати добавил бы тест на поиск массиве рассортированных IDX на запоненном slist и list в полном диапозоне. При не попадании в кэш поиск твоим методом должен сильно тормозится. A>На словах непонятно, псевдокод приведи чего сравнивать.
S>> И оценить время на построение дерева. A>Согласен, лишним не будет.
Делаем процедуру рперемешивания
public void unsortarray(Int32[] OrigArray)
{
Int32 j, k, tempbuff;
Random r = new Random(666666);
for (Int32 i = 0; i < OrigArray.Length; i++)
{
j = r.Next(OrigArray.Length - 1);
k = r.Next(OrigArray.Length - 1);
tempbuff = OrigArray[j];
OrigArray[j] = OrigArray[k];
OrigArray[k] = tempbuff;
}
}
Заполняем slist Затем получаем массив n элементов
for (Int32 ii = 0; ii < OrigArray.Length; ii++)
{
OrigArray[ii] = ii;
}
рассортировываем
unsortarray(OrigArray);
А затем производим поиск
timer.Start();
for (Int32 ii = 0; ii < OrigArray.Length; ii++)
{
if (!BT.NavigateKey(OrigArray[ii]))
{
textBox1.AppendText("i=" + ii.ToString() + " Не найден "
+ OrigArray[ii].ToString() + "]\r\n");
break;
}
}
TimeRunning = timer.Finish();
textBox1.AppendText("Поиск в Btree " + TimeRunning.ToString() + "\r\n");
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Re[10]: Создание эффективного контейнера для работы со списк
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, alsemm, Вы писали:
A>>Здравствуйте, Serginio1, Вы писали:
S>>>Здравствуйте, alsemm, Вы писали:
S>>>>> Так в массивы они добавляются именно в ту позицию в которую ты хочешь. Просто в Б+ деревьях эта позиция определяется бинарным поиском, S>>>>> у тебя иначе, но сами структуры данных близки. A>>>>Так и у меня бинарным поиском позиция ищется. Потом правда приходится немного по мписку пройтись, чтобы точно позицию получить. S>>> Вот про это то я как раз и говорю. A>>Да, есть там такая мерзость.
S>>> Кстати добавил бы тест на поиск массиве рассортированных IDX на запоненном slist и list в полном диапозоне. При не попадании в кэш поиск твоим методом должен сильно тормозится. A>>На словах непонятно, псевдокод приведи чего сравнивать.
S>>> И оценить время на построение дерева. A>>Согласен, лишним не будет.
S> Делаем процедуру рперемешивания
S>
S> public void unsortarray(Int32[] OrigArray)
S> {
S> Int32 j, k, tempbuff;
S> Random r = new Random(666666);
S> for (Int32 i = 0; i < OrigArray.Length; i++)
S> {
S> j = r.Next(OrigArray.Length - 1);
S> k = r.Next(OrigArray.Length - 1);
S> tempbuff = OrigArray[j];
S> OrigArray[j] = OrigArray[k];
S> OrigArray[k] = tempbuff;
S> }
S> }
S>
S> Заполняем slist Затем получаем массив n элементов S>
S> for (Int32 ii = 0; ii < OrigArray.Length; ii++)
S> {
S> OrigArray[ii] = ii;
S> }
S>
S> рассортировываем S>unsortarray(OrigArray);
S> А затем производим поиск S>
S> timer.Start();
S> for (Int32 ii = 0; ii < OrigArray.Length; ii++)
S> {
S> if (!BT.NavigateKey(OrigArray[ii]))
S> {
S> textBox1.AppendText("i=" + ii.ToString() + " Не найден "
S> + OrigArray[ii].ToString() + "]\r\n");
S> break;
S> }
S> }
S> TimeRunning = timer.Finish();
S> textBox1.AppendText("Поиск в Btree " + TimeRunning.ToString() + "\r\n");
S>
Идея ясна.
Тут сравнивай не сравнивай, slist будет точно лучше list-а, вопрос только на сколько. Хотя тест написать недолго
Re[11]: Создание эффективного контейнера для работы со списк
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, alsemm, Вы писали:
A>>Идея ясна.
A>>Тут сравнивай не сравнивай, slist будет точно лучше list-а, вопрос только на сколько. Хотя тест написать недолго
S> Ну и сравнить разные реализации slist. S> Кроме того можно оценить поисковую состовляющую при вставке. Хотя и приблизительно но порядок будет верным.
Это уже на вторую часть статьи тянет
Re[13]: Создание эффективного контейнера для работы со списк
A>>>Тут сравнивай не сравнивай, slist будет точно лучше list-а, вопрос только на сколько. Хотя тест написать недолго
S>> Ну и сравнить разные реализации slist. S>> Кроме того можно оценить поисковую состовляющую при вставке. Хотя и приблизительно но порядок будет верным. A>Это уже на вторую часть статьи тянет
Ну я думаю это не так уж и сложно. Реализация на массиве будет очень близка к list (правда итераторы написать но это не долго).
Просто меня сильно цифири в таблице 5 несколько смутили. На Б+ деревьях вставка
100 000 элементов порядка 0.07 сек.
1 000 000 элементов порядка 1.4
Вот и интересно посмотреть как скажется сегмент на массивах который и применяется в Б+ деревьях.
Отличаются только алгоритмы поиска и построения дерева
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Re: Создание эффективного контейнера для работы со списком б
Здравствуйте, Алексей Семенюк, Вы писали:
А>Аннотация: А>В статье приводится пример реализации нестандартного контейнера, позволяющего обеспечить приемлемую скорость доступа к произвольному элементу и вставки/удаления в произвольную позицию.
Здравствуйте, alsemm, Вы писали:
A>Тут сравнивай не сравнивай, slist будет точно лучше list-а, вопрос только на сколько. Хотя тест написать недолго
Ну увеличить скорость list и так достаточно просто
Напишу на C# такой класс.
public class Page<T>
{
T PageItems[n]; // например n =64;int Count;
ListArray<T> Owner;
seg<T>> LeftPage;
seg<T>> RightPage;
}
public clscc ListArray<T>
{
internal Page<T> CurrentPage; // Текущая страница с даннымиinternal Page<T> FirstPage;
internal Page<T> LastPage;
internal int _currentElementIndex; // Текущий индекс элемента в массиве internal int _count; // Количество элементов в объектеpublic Find(int idx)
{
if (idx<_count/2)
{
int k=idx;
CurrentPage=FirstPage;
while (k>=CurrentPage.Count)
{
k-=CurrentPage.Count;
CurrentPage=CurrentPage.RightPage;
}
_currentElementIndex=k;
}
else
{
int k=_count-idx;
CurrentPage=LastPage;
while (k>CurrentPage.Count)
{
k-=CurrentPage.Count;
CurrentPage=CurrentPage.LeftPage;
}
_currentElementIndex=CurrentPage.Count-k;
}
}
}
}
И соответственно вставку и удаление возму из своей TwoLevelSortedDictonary<K,V>
думаю будет понятно
private void Insert(K Key)
{
// Раздвигаем массив с текущей позиции, и вставляем ключ
Array.Copy(CurrentLeafPage.PageItems, _currentElementIndex, CurrentLeafPage.PageItems,
_currentElementIndex + 1, CurrentLeafPage.Count - _currentElementIndex);
CurrentLeafPage.Count++;
CurrentLeafPage.PageItems[_currentElementIndex].Key = Key;
// Произошли изменения увеличиваем текущую версию
version++;
_count++;
// Проверка на полное заполнение массиваif (CurrentLeafPage.Count == BTConst.MaxCount)
{
// Проверка на существование второго уровняif (_pageCount == 1)
{
// Второго уровня еще нет. Аналогичная операция и в Б+ деревьях
//Делим текущую страницу пополам
LeafPage<K,V> NewPage = new LeafPage<K,V>();
// Устанавливаем нужные ссылки в полях NextPage и PriorPage
CurrentLeafPage.NextPage = NewPage;
NewPage.PriorPage = CurrentLeafPage;
// Копируем половину данных из исходного массива в новый выделенный
Array.Copy(CurrentLeafPage.PageItems, BTConst.MidlCount, NewPage.PageItems, 0, BTConst.MidlCount);
// Очищаем освободившееся пространство
Array.Clear(CurrentLeafPage.PageItems, BTConst.MidlCount, BTConst.MidlCount);
// Создаем массив второго уровня и устанавливаем первые два его значения
NodeArray = new NodeItem[BTConst.MaxCount];
_pageCount = 2;
NodeArray[0].Key = CurrentLeafPage.PageItems[0].Key;
NodeArray[0].ChildPage = CurrentLeafPage;
NodeArray[1].Key = NewPage.PageItems[0].Key;
NodeArray[1].ChildPage = NewPage;
// Устанавливаем новое количество элементов на страницах
CurrentLeafPage.Count = BTConst.MidlCount;
NewPage.Count = BTConst.MidlCount;
// Проверяем новую текущую позицию вставленного элементаif (_currentElementIndex >= BTConst.MidlCount)
{
CurrentLeafPage = NewPage;
_currentElementIndex -= BTConst.MidlCount;
}
}
else
{
// Второй уровень уж существует. Попробуем перекинуть значения в влизлежащие страницы.
// Это не столь критично для вставки как при удалении, но есть варианты при вставке
//последовательных данных, когда страницы будут заполнены только на половину
// Но для того, что бы не перекидывать по малому количеству элементов желательно, что бы //соседняя страница была заполнена менее ?+1 емкости страницы
LeafPage<K,V> LeftPage = CurrentLeafPage.PriorPage;
if (LeftPage != null)
{
if (LeftPage.Count <= BTConst.MaxFill)
{
// можно перекинуть значения на левую страницу находим нужное количесво
// элементов для переброскиint MoveCount = (BTConst.MaxCount - LeftPage.Count) / 2;
// Копируем начальные элементы из текущей страницы в конец левой страницы
Array.Copy(CurrentLeafPage.PageItems, 0, LeftPage.PageItems, LeftPage.Count, MoveCount);
// Копируем оставшиеся элементы текущей страницы в начало
Array.Copy(CurrentLeafPage.PageItems, MoveCount, CurrentLeafPage.PageItems, 0, CurrentLeafPage.Count - MoveCount);
// Очищаем освободившееся место в текущем массиве
Array.Clear(CurrentLeafPage.PageItems, CurrentLeafPage.Count - MoveCount, MoveCount);
// Устанавливаем новое значение ключа в текущую позицию NodeArray
NodeArray[_currentPageIndex].Key = CurrentLeafPage.PageItems[0].Key;
// Проверяем новую текущую позицию вставленного элементаif (_currentElementIndex < MoveCount)
{
_currentElementIndex += LeftPage.Count;
CurrentLeafPage.Count -= MoveCount;
LeftPage.Count += MoveCount;
CurrentLeafPage = LeftPage;
}
else
{
_currentElementIndex -= MoveCount;
CurrentLeafPage.Count -= MoveCount;
LeftPage.Count += MoveCount;
}
return;
}
}
// С левой страницей не получилось попробуем с правой
LeafPage<K,V> RightPage = CurrentLeafPage.NextPage;
if (RightPage != null)
{
if (RightPage.Count <= BTConst.MaxFill)
{
int MoveCount = (BTConst.MaxCount - RightPage.Count) / 2;
Array.Copy(RightPage.PageItems, 0, RightPage.PageItems, MoveCount, RightPage.Count);
Array.Copy(CurrentLeafPage.PageItems, BTConst.MaxCount - MoveCount,
RightPage.PageItems, 0, MoveCount);
Array.Clear(CurrentLeafPage.PageItems, CurrentLeafPage.Count - MoveCount, MoveCount);
NodeArray[_currentPageIndex + 1].Key = RightPage.PageItems[0].Key;
CurrentLeafPage.Count -= MoveCount;
RightPage.Count += MoveCount;
if (_currentElementIndex >= CurrentLeafPage.Count)
{
_currentElementIndex -= CurrentLeafPage.Count;
CurrentLeafPage = RightPage;
}
return;
}
}
// Не получилось сбалансировать ну и ....
// Выделяемновую страницу и вставляем в NodeArray;
LeafPage<K,V> NewPage = new LeafPage<K,V>();
// Устанавливаем нужные ссылки в полях NextPage и PriorPage
NewPage.NextPage = CurrentLeafPage.NextPage;
NewPage.PriorPage = CurrentLeafPage;
CurrentLeafPage.NextPage = NewPage;
if (NewPage.NextPage != null)
NewPage.NextPage.PriorPage = NewPage;
// Действия аналогичные при выделения второго уровня
Array.Copy(CurrentLeafPage.PageItems, BTConst.MidlCount, NewPage.PageItems, 0, BTConst.MidlCount);
Array.Clear(CurrentLeafPage.PageItems, BTConst.MidlCount, BTConst.MidlCount);
Array.Copy(NodeArray, _currentPageIndex + 1, NodeArray, _currentPageIndex + 2, _pageCount - _currentPageIndex - 1);
NodeArray[_currentPageIndex + 1].Key = NewPage.PageItems[0].Key;
NodeArray[_currentPageIndex + 1].ChildPage = NewPage;
CurrentLeafPage.Count = BTConst.MidlCount;
NewPage.Count = BTConst.MidlCount;
// Проверяем текущую позицию вставляемого элемента if (_currentElementIndex >= BTConst.MidlCount)
{
CurrentLeafPage = NewPage;
_currentElementIndex -= BTConst.MidlCount;
}
_pageCount++;
//Проверяем вариант на полное заполнение NodeArray.
// Если заполненили полностью, то просто увеличиваем его в 2 раза
// В Б+ деревьях в этом случае выстраивается новый уровеньif (_pageCount == NodeArray.Length)
{
NodeItem[] NewNodeArray = new NodeItem[2 * _pageCount];
Array.Copy(NodeArray, 0, NewNodeArray, 0, _pageCount);
NodeArray = NewNodeArray;
}
}
}
}
В отличие от сишного memmove в ArrayCopy идет источник затем потребитель.
И соответственно удаление
/// Процедура удаления текущего элемента. При этом
///позиция верхнего уровня должна укпзыватьна текущую страницу
/// </summary>private void Delete()
{
CurrentLeafPage.Count--;
if (_currentElementIndex < CurrentLeafPage.Count)
{
Array.Copy(CurrentLeafPage.PageItems, _currentElementIndex + 1, CurrentLeafPage.PageItems, _currentElementIndex, CurrentLeafPage.Count - _currentElementIndex);
}
// Увеличиваем текущую верстю
version++;
// Очищаем освободившееся место
CurrentLeafPage.PageItems[CurrentLeafPage.Count] = KeyValuePair<K,V>.default;
// Проверим на удаление нулевого элемента, т.к. копия его ключа
// хранится в родительском массивеif ((_currentElementIndex == 0) && (_pageCount>1))
{
NodeArray[this._currentPageIndex].Key = CurrentLeafPage.PageItems[0].Key;
}
// Проверим новой количество элементов на странице и если их количество
// стало меньше половины емкости страницы займем их у ближайших страницif ((CurrentLeafPage.Count < BTConst.MidlCount) && (_pageCount > 0))
{
LeafPage<K,V> LeftPage = CurrentLeafPage.PriorPage;
// попробуем занять у левой страницыif (LeftPage != null)
{
if ((LeftPage.Count + CurrentLeafPage.Count) <= BTConst.MaxCount)
{
// Вариант когда из двух страниц делаем одну
// Всегда перекидываем в левую страницу
Array.Copy(CurrentLeafPage.PageItems, 0, LeftPage.PageItems, LeftPage.Count, CurrentLeafPage.Count);
LeftPage.NextPage = CurrentLeafPage.NextPage;
if (CurrentLeafPage.NextPage!=null)
CurrentLeafPage.NextPage.PriorPage = LeftPage;
// Устанавливаем новый текущий индекс
_currentElementIndex += LeftPage.Count;
// Устанавливаем новое количество элементов на странице
LeftPage.Count += CurrentLeafPage.Count;
CurrentLeafPage = LeftPage;
// Удаляем ссылку на текущую страницу из NodeArray
DeleteNodeItem(_currentPageIndex);
CheckLastPositionAeterDelete();
return;
}
// Следующие варианты аналогичны при переброске элементов при вставкеint MoveCount = (LeftPage.Count - CurrentLeafPage.Count) / 2;
Array.Copy(CurrentLeafPage.PageItems, 0, CurrentLeafPage.PageItems, MoveCount, CurrentLeafPage.Count);
Array.Copy(LeftPage.PageItems, LeftPage.Count - MoveCount, CurrentLeafPage.PageItems, 0, MoveCount);
Array.Clear(LeftPage.PageItems, LeftPage.Count - MoveCount, MoveCount);
NodeArray[_currentPageIndex].Key = CurrentLeafPage.PageItems[0].Key;
_currentElementIndex += MoveCount;
LeftPage.Count -= MoveCount;
CurrentLeafPage.Count += MoveCount;
CheckLastPositionAeterDelete();
return;
}
LeafPage<K,V> RightPage = CurrentLeafPage.NextPage;
if (RightPage != null)
{
if ((RightPage.Count + CurrentLeafPage.Count) <= BTConst.MaxCount)
{
Array.Copy(RightPage.PageItems, 0, CurrentLeafPage.PageItems, CurrentLeafPage.Count, RightPage.Count);
CurrentLeafPage.NextPage = RightPage.NextPage;
if (RightPage.NextPage!=null)
RightPage.NextPage.PriorPage = CurrentLeafPage;
CurrentLeafPage.Count += RightPage.Count;
DeleteNodeItem(_currentPageIndex + 1);
return;
}
int MoveCount = (RightPage.Count - CurrentLeafPage.Count) / 2;
Array.Copy(RightPage.PageItems, 0, CurrentLeafPage.PageItems, CurrentLeafPage.Count, MoveCount);
Array.Copy(RightPage.PageItems, MoveCount, RightPage.PageItems, 0, RightPage.Count - MoveCount);
Array.Clear(RightPage.PageItems, RightPage.Count - MoveCount, MoveCount);
NodeArray[_currentPageIndex + 1].Key = RightPage.PageItems[0].Key;
CurrentLeafPage.Count += MoveCount;
RightPage.Count -= MoveCount;
return;
}
}
}
Если сравнить затраты на вставку в vector и list ( к сожалению не знаю полной реализации но мои представления могут быть ошибочны, так что прошу прощения)
в vector затраты
поиск 1;
вставка N/2 * (sizeof(T)/4)(где N количество элементов)
в list
поиск N/4 (так как поиск может быть сначала или с конца)
вставка 3;
Для приведенного выше класса
поск N/k (где к средняя запоненность массива)
вставка MaxCount/2*(sizeof(T)/4) (MaxCount емкость массива на странице
Проинтегрировав по n для поиска затрат по заполнению с 0 по N в случайные позиции
Получим затрату например для интов
vector sqr(N)/4
list sqr(N)/8
Данное утверждение правда сильно зависит от используемой шины памяти и самой памяти, а также попадания данных в кэш
т.к. даже при копировании данных не попавших в кэш для вектора будет использоваться DDR эффект в отличие от лист
Для приведенного выше класса
sqr(N)/8/k + N*MaxCount/2
и взяв отношение
N/(N/k+4*MaxCount)
так для 10000 это будет и при MaxCount=128 и к 100
10000/(100+ 500) = 15
а при 100000
100000/(1000+500) = 60
То есть легко можно увеличить скорость в десятки разов.
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Re[12]: Создание эффективного контейнера для работы со списк
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, alsemm, Вы писали:
A>>Тут сравнивай не сравнивай, slist будет точно лучше list-а, вопрос только на сколько. Хотя тест написать недолго S> Ну увеличить скорость list и так достаточно просто
S> Напишу на C# такой класс.
кусь-кусь...
S> Если сравнить затраты на вставку в vector и list ( к сожалению не знаю полной реализации но мои представления могут быть ошибочны, так что прошу прощения) S> в vector затраты S> поиск 1; S> вставка N/2 * (sizeof(T)/4)(где N количество элементов)
sizeof(T)/4 — это чего такое?
И что это за оценка для вставки: худшая или средняя? я так понимаю, что средняя.
S> в list S> поиск N/4 (так как поиск может быть сначала или с конца)
Это в среднем, в худшем случае N/2 S> вставка 3;
Вставка для list-а всегде 1, 3-и то откуда?
S> Для приведенного выше класса
S> поск N/k (где к средняя запоненность массива) S> вставка MaxCount/2*(sizeof(T)/4) (MaxCount емкость массива на странице
S> Проинтегрировав по n для поиска затрат по заполнению с 0 по N в случайные позиции S> Получим затрату например для интов S> vector sqr(N)/4 S> list sqr(N)/8
Химия какя-то, это мне непонятно
S> Данное утверждение правда сильно зависит от используемой шины памяти и самой памяти, а также попадания данных в кэш S> т.к. даже при копировании данных не попавших в кэш для вектора будет использоваться DDR эффект в отличие от лист
S> Для приведенного выше класса
S> sqr(N)/8/k + N*MaxCount/2
S> и взяв отношение
S> N/(N/k+4*MaxCount) S> так для 10000 это будет и при MaxCount=128 и к 100 S> 10000/(100+ 500) = 15
S> а при 100000
S> 100000/(1000+500) = 60 S> То есть легко можно увеличить скорость в десятки разов.
Насчет скорости: все выглядит очень привлекательно, надо только реализацию сделать нормальную, а не на коленке и тогда уже замеры сделать, чтобы убедиться, что расчеты верны.
Re[13]: Создание эффективного контейнера для работы со списк
S>> Если сравнить затраты на вставку в vector и list ( к сожалению не знаю полной реализации но мои представления могут быть ошибочны, так что прошу прощения) S>> в vector затраты S>> поиск 1; S>> вставка N/2 * (sizeof(T)/4)(где N количество элементов) A>sizeof(T)/4 — это чего такое? A>И что это за оценка для вставки: худшая или средняя? я так понимаю, что средняя.
Берем за оценку копирования 1 инта все в среднем т.к. в задаче
S>> в list S>> поиск N/4 (так как поиск может быть сначала или с конца) A>Это в среднем, в худшем случае N/2 S>> вставка 3; A>Вставка для list-а всегде 1, 3-и то откуда?
Пусть будет 1 (аставка в двухсвязнй список всетаки затрагивает левый и правй элемент, но это мелочи сказывающиеся при непопадании в кэш)
S>> Для приведенного выше класса
S>> поск N/k (где к средняя запоненность массива) S>> вставка MaxCount/2*(sizeof(T)/4) (MaxCount емкость массива на странице
S>> Проинтегрировав по n для поиска затрат по заполнению с 0 по N в случайные позиции S>> Получим затрату например для интов S>> vector sqr(N)/4 S>> list sqr(N)/8 A>Химия какя-то, это мне непонятно
Ну почему, вполне согласутся с твоими данными в таблице пять хотя бы порядок.
S>> Данное утверждение правда сильно зависит от используемой шины памяти и самой памяти, а также попадания данных в кэш S>> т.к. даже при копировании данных не попавших в кэш для вектора будет использоваться DDR эффект в отличие от лист
S>> Для приведенного выше класса
S>> sqr(N)/8/k + N*MaxCount/2
S>> и взяв отношение
S>> N/(N/k+4*MaxCount) S>> так для 10000 это будет и при MaxCount=128 и к 100 S>> 10000/(100+ 500) = 15
S>> а при 100000
S>> 100000/(1000+500) = 60 S>> То есть легко можно увеличить скорость в десятки разов. A>Насчет скорости: все выглядит очень привлекательно, надо только реализацию сделать нормальную, а не на коленке и тогда уже замеры сделать, чтобы убедиться, что расчеты верны.
По поводу Б+ деревьев я тебе данные приводил. И код TwoLevelSortedDictonary<K,V> Delete() и Insert() оттуда.
Кстати TwoLevelSortedDictonary<K,V> прекрасно работает до миллиона, затем резко уступает Б+ деревьям, но как промежуточный вариант очень хорошь. Твой вариант с деревом очень симпатичен, но нужно сопоставить затраты на перестроение дерева и корректировку offset.
Кстати а почему не КЧД ????
Мой вариант тоже может быть как промежуточный.
Попробуй, просто у меня нет таких задач, а писать в сол не интересно. Могу сказать, что порядок будет очень близким к теоретическим,
а то и большим если сравнивать вектор с листом на больших данных.
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Re[14]: Создание эффективного контейнера для работы со списк
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, alsemm, Вы писали:
S>>> Если сравнить затраты на вставку в vector и list ( к сожалению не знаю полной реализации но мои представления могут быть ошибочны, так что прошу прощения) S>>> в vector затраты S>>> поиск 1; S>>> вставка N/2 * (sizeof(T)/4)(где N количество элементов) A>>sizeof(T)/4 — это чего такое? A>>И что это за оценка для вставки: худшая или средняя? я так понимаю, что средняя. S> Берем за оценку копирования 1 инта все в среднем т.к. в задаче
S>>> в list S>>> поиск N/4 (так как поиск может быть сначала или с конца) A>>Это в среднем, в худшем случае N/2 S>>> вставка 3; A>>Вставка для list-а всегде 1, 3-и то откуда? S> Пусть будет 1 (аставка в двухсвязнй список всетаки затрагивает левый и правй элемент, но это мелочи сказывающиеся при непопадании в кэш)
S>>> Для приведенного выше класса
S>>> поск N/k (где к средняя запоненность массива) S>>> вставка MaxCount/2*(sizeof(T)/4) (MaxCount емкость массива на странице
S>>> Проинтегрировав по n для поиска затрат по заполнению с 0 по N в случайные позиции S>>> Получим затрату например для интов S>>> vector sqr(N)/4 S>>> list sqr(N)/8 A>>Химия какя-то, это мне непонятно
S> Ну почему, вполне согласутся с твоими данными в таблице пять хотя бы порядок.
Химией я назвал sqrt, мне не понятно, как он появляется , ну да ладно.
S>>> Данное утверждение правда сильно зависит от используемой шины памяти и самой памяти, а также попадания данных в кэш S>>> т.к. даже при копировании данных не попавших в кэш для вектора будет использоваться DDR эффект в отличие от лист
S>>> Для приведенного выше класса
S>>> sqr(N)/8/k + N*MaxCount/2
S>>> и взяв отношение
S>>> N/(N/k+4*MaxCount) S>>> так для 10000 это будет и при MaxCount=128 и к 100 S>>> 10000/(100+ 500) = 15
S>>> а при 100000
S>>> 100000/(1000+500) = 60 S>>> То есть легко можно увеличить скорость в десятки разов. A>>Насчет скорости: все выглядит очень привлекательно, надо только реализацию сделать нормальную, а не на коленке и тогда уже замеры сделать, чтобы убедиться, что расчеты верны. S> По поводу Б+ деревьев я тебе данные приводил. И код TwoLevelSortedDictonary<K,V> Delete() и Insert() оттуда. S> Кстати TwoLevelSortedDictonary<K,V> прекрасно работает до миллиона, затем резко уступает Б+ деревьям, но как промежуточный вариант очень хорошь. Твой вариант с деревом очень симпатичен, но нужно сопоставить затраты на перестроение дерева и корректировку offset.
Да, этих замеров я не делал.
S> Кстати а почему не КЧД ????
Вообщем-то из-за изъяна в образовании: когда взялся писать slist я не знал, какие есть варианты самобалансирующихся Б дреревъев (и есть-ли такие вообще), поэтому полез в google, он на запрос "self balanced tree c++" первым выдал АВЛ и 2-3 деревъевя. АВЛ показались попроще
S> Мой вариант тоже может быть как промежуточный. S> Попробуй, просто у меня нет таких задач, а писать в сол не интересно. Могу сказать, что порядок будет очень близким к теоретическим, S> а то и большим если сравнивать вектор с листом на больших данных.
Ок.
Re[15]: Создание эффективного контейнера для работы со списк
S>>>> Проинтегрировав по n для поиска затрат по заполнению с 0 по N в случайные позиции S>>>> Получим затрату например для интов S>>>> vector sqr(N)/4 S>>>> list sqr(N)/8 A>>>Химия какя-то, это мне непонятно
S>> Ну почему, вполне согласутся с твоими данными в таблице пять хотя бы порядок. A>Химией я назвал sqrt, мне не понятно, как он появляется , ну да ладно.
Не знаю как в C++ в квадрате но помоему sqr (square of number) есть везде, sqrt (square root) это корень квадратны разница в t на конце
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Re[16]: Создание эффективного контейнера для работы со списк
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, alsemm, Вы писали:
S>>>>> Проинтегрировав по n для поиска затрат по заполнению с 0 по N в случайные позиции S>>>>> Получим затрату например для интов S>>>>> vector sqr(N)/4 S>>>>> list sqr(N)/8 A>>>>Химия какя-то, это мне непонятно
S>>> Ну почему, вполне согласутся с твоими данными в таблице пять хотя бы порядок. A>>Химией я назвал sqrt, мне не понятно, как он появляется , ну да ладно.
S> Не знаю как в C++ в квадрате но помоему sqr (square of number) есть везде, sqrt (square root) это корень квадратны разница в t на конце
Что такое sqrt я знаю. Я не понимаю как он в формулу попадает.
Re[17]: Создание эффективного контейнера для работы со списк
S>> Не знаю как в C++ в квадрате но помоему sqr (square of number) есть везде, sqrt (square root) это корень квадратны разница в t на конце A>Что такое sqrt я знаю. Я не понимаю как он в формулу попадает.
sqr<> sqrt
sqr(N) = N*N
интеграл от 0 по N n/2 dn = N*N/4;
Во сейчас вспомню интеграл от log(n) по основаню 2. Это затраты на поиск в дереве
дай бог памяти (ой и давнож это было) будет
(N*Log(n) -N)/ Ln(2)
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Re[18]: Создание эффективного контейнера для работы со списк
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, alsemm, Вы писали:
S>>> Не знаю как в C++ в квадрате но помоему sqr (square of number) есть везде, sqrt (square root) это корень квадратны разница в t на конце A>>Что такое sqrt я знаю. Я не понимаю как он в формулу попадает. S> sqr<> sqrt S> sqr(N) = N*N
????
По вашему sqrt(16) = 256, а мне казалось, что sqrt(16) = 4, вот pow(N, 2) = N*N. S> интеграл от 0 по N n/2 dn = N*N/4;
S> Во сейчас вспомню интеграл от log(n) по основаню 2. Это затраты на поиск в дереве S> дай бог памяти (ой и давнож это было) будет S> (N*Log(n) -N)/ Ln(2)
Re[19]: Создание эффективного контейнера для работы со списк
A>???? A>По вашему sqrt(16) = 256, а мне казалось, что sqrt(16) = 4, вот pow(N, 2) = N*N. S>> интеграл от 0 по N n/2 dn = N*N/4;
Да не SQRT а SQR разница в T
пусть будет pow
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Re[20]: Создание эффективного контейнера для работы со списк
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, alsemm, Вы писали:
A>>???? A>>По вашему sqrt(16) = 256, а мне казалось, что sqrt(16) = 4, вот pow(N, 2) = N*N. S>>> интеграл от 0 по N n/2 dn = N*N/4; S> Да не SQRT а SQR разница в T S> пусть будет pow
Аааа, Семен Семеныч
Здравствуйте, Алексей Семенюк, Вы писали:
АС>Статья:
А почему нельзя было воспользоваться спецификой предметной области?
Вроде же в текстовых редакторах существует такая вещь, как "текущая строка", соответственно, кешируя последний запрошенный указатель, а также его индекс, можно было бы получить очень неплохую скорость поиска/редактирования.
Перемещения по тексту тоже обычно происходят последовательно — вверх/вниз на строку/экран. Зная номер текущей строки и имея двусвязный список, вполне реально быстро искать соседние буферы.
Или нет?
Re[3]: Создание эффективного контейнера для работы со списко
Здравствуйте, alsemm, Вы писали:
A>Здравствуйте, c-smile, Вы писали:
CS>>Здравствуйте, Алексей Семенюк, Вы писали:
А>>>Аннотация: А>>>В статье приводится пример реализации нестандартного контейнера, позволяющего обеспечить приемлемую скорость доступа к произвольному элементу и вставки/удаления в произвольную позицию.
CS>>А это случайно не про sparse arrays статья ? A>Нет, статья не про разряженные массивы
ЗЫ. А на счет реализации — я бы концы строк держал в std::vector<char*>
и не мучался. В векторе вставка для POD типов реализована через memmov,
что дает приемлемые показатели быстродействия даже для 10000 строк.
Serge.
Hасколько проще была бы жизнь, если бы она была в исходниках.
Re[4]: Создание эффективного контейнера для работы со списко
...
S>Похоже, это очередная реализация skip list.
CS>>>Ссылки по теме: CS>>>http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node9.html
Идем по ссылке и читаем что есть разряженный массив:
This chapter explores sparse arrays. A sparse array is an array where nearly all of the elements have the same value (usually zero), and this value is a constant, known ahead of time.
Вроде не то.
CS>>>http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node47.html CS>>>http://math.nist.gov/sparselib++/
S>ЗЫ. А на счет реализации — я бы концы строк держал в std::vector<char*> S>и не мучался. В векторе вставка для POD типов реализована через memmov, S>что дает приемлемые показатели быстродействия даже для 10000 строк.
Согласен, производительность вставки/удаления будет приемлемой, так же как и доступ к строке по индексу. Но вот реализация int getLineFromChar(int chrIdx); будет тормозной.
Re[2]: Создание эффективного контейнера для работы со списко
Здравствуйте, eugals, Вы писали:
E>Здравствуйте, Алексей Семенюк, Вы писали:
АС>>Статья:
E>А почему нельзя было воспользоваться спецификой предметной области? E>Вроде же в текстовых редакторах существует такая вещь, как "текущая строка", соответственно, кешируя последний запрошенный указатель, а также его индекс, можно было бы получить очень неплохую скорость поиска/редактирования. E>Перемещения по тексту тоже обычно происходят последовательно — вверх/вниз на строку/экран. Зная номер текущей строки и имея двусвязный список, вполне реально быстро искать соседние буферы.
E>Или нет?
Все так. Однако бывает что и не последовательно (пример: в MSVC "Ctrl+G").
Забавно получается: вы предлашаете двухсвязный список, тут http://www.rsdn.ru/Forum/Message.aspx?mid=887921&only=1
S>>ЗЫ. А на счет реализации — я бы концы строк держал в std::vector<char*> S>>и не мучался. В векторе вставка для POD типов реализована через memmov, S>>что дает приемлемые показатели быстродействия даже для 10000 строк. A>Согласен, производительность вставки/удаления будет приемлемой, так же как и доступ к строке по индексу. Но вот реализация int getLineFromChar(int chrIdx); будет тормозной.
Если честно, я не совсем понял для чего эта функция вообще нужна. Обычно хранится пара номер строки/индекс в строке...
Serge.
Hасколько проще была бы жизнь, если бы она была в исходниках.
Re: Создание эффективного контейнера для работы со списком б
От:
Аноним
Дата:
15.04.05 04:46
Оценка:
АС>Статья:
Отличная статья.
Никак не могу разобратся только, как сделать segmented_list для очень большого списка таких структур
struct data
{
int id;
void *p;
}
для быстрого поиска по id.
объявляю:
typedef list <data> datalist;
typedef segmented_list <data> slist;
для того чтобы потом быстро искать:
int finding_id=23000;
sl.find(cmp_int_idx(finding_id));
главня проблема как объявить теперь этот:
class cmp_int_idx
Re[2]: Создание эффективного контейнера для работы со списко
От:
Аноним
Дата:
15.04.05 04:50
Оценка:
Здравствуйте, Аноним, Вы писали:
АС>>Статья: А>Отличная статья.
А>Никак не могу разобратся только, как сделать segmented_list для очень большого списка таких структур А>struct data А>{ А> int id; А> void *p; А>} А>для быстрого поиска по id.
А>объявляю: А>typedef list <data> datalist; А>typedef segmented_list <data> slist;
А>для того чтобы потом быстро искать: А>int finding_id=23000; А>sl.find(cmp_int_idx(finding_id));
А>главня проблема как объявить теперь этот: А>class cmp_int_idx
забыл сказать что добавил описание
class segmented_list
{
.............
public:
...........
