писал про сортированный список, тут другой случай: 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
Аааа, Семен Семеныч
Здравствуйте, Алексей Семенюк, Вы писали:
АС>Статья:
А почему нельзя было воспользоваться спецификой предметной области?
Вроде же в текстовых редакторах существует такая вещь, как "текущая строка", соответственно, кешируя последний запрошенный указатель, а также его индекс, можно было бы получить очень неплохую скорость поиска/редактирования.
Перемещения по тексту тоже обычно происходят последовательно — вверх/вниз на строку/экран. Зная номер текущей строки и имея двусвязный список, вполне реально быстро искать соседние буферы.
