Re[5]: подскажите контейнер
От: uzhas Ниоткуда  
Дата: 03.02.14 12:14
Оценка:
Здравствуйте, AlexDoberman, Вы писали:

AD>есть некий фреймверк который отображает items

AD>для этого ему (фреймверку ) я должен передать model из которой он извлечет данные


AD>
AD>class CModel
AD>{
AD>public:
AD>    size_t count();
AD>    TItem  data(size_t index);
AD>}
AD>


AD>дальше он показывает показывает model.

AD>соответственно данные добавляются новые / удаляются / редактируются (при всем этом должен поддерживаться сортировка)
AD>вот как то так.
AD>Соответственно после каждой каждой модификации данный модуль отображения должен перерисовать данные

в данной постановке можно было бы вообще отказаться от поиска по index, т.к. мы заранее знаем, что индексы будут подсовываться в возрастающем порядке
нам достаточно внутри хранить некий итератор, который будет инкрементиться после вызова data(index). можем ассерты вставить на то, что индексы подсовываются по порядку
для этой задачи самый простой set может подойти
Re[7]: подскажите контейнер
От: Erop Россия  
Дата: 03.02.14 12:14
Оценка:
Здравствуйте, AlexDoberman, Вы писали:

AD>правильно я понимаю что как только возникает дерево , то сразу произвольный доступ по индексу мы выполняем за log n ?

Нет, не правильно.
1) "произвольный доступ" может быть не таким уж и произвольным. Например, может быть какой-то важный паттерн доступа, который и надо оптимизировать.
2) Дерево может быть и с индексом.

Ещё раз говорю, что пусть у меня в каждом узле хранится число узлов в растущем из этого узла поддереве. Тогда операции "промотать 100500 элементов влево/вправо" и апдейты индекса тоже могут оказаться существенно дешевле...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[6]: подскажите контейнер
От: AlexDoberman  
Дата: 03.02.14 12:18
Оценка: +1
Здравствуйте, Erop, Вы писали:

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



E>Если второе, то моет просто можно приделать в модель механизм кэширования позиции и строить инекс не на всю коллекуию. а только на нужную часть? Ну там постранично, например?


да я впринципе уже так и сделал
т.е. я ввел преположение что при сканированиии он запрашивает элементы последовательно. i, i+1 , ... i+k
Re[6]: подскажите контейнер
От: Erop Россия  
Дата: 03.02.14 12:33
Оценка:
Здравствуйте, uzhas, Вы писали:

U>в данной постановке можно было бы вообще отказаться от поиска по index, т.к. мы заранее знаем, что индексы будут подсовываться в возрастающем порядке

U>нам достаточно внутри хранить некий итератор, который будет инкрементиться после вызова data(index). можем ассерты вставить на то, что индексы подсовываются по порядку
U>для этой задачи самый простой set может подойти

Зачем assert'ы?
Лучше обработать + дебаг-средство по сбору статистики...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[8]: подскажите контейнер
От: AlexDoberman  
Дата: 03.02.14 12:35
Оценка:
Здравствуйте, Erop, Вы писали:

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


AD>>правильно я понимаю что как только возникает дерево , то сразу произвольный доступ по индексу мы выполняем за log n ?

E>Нет, не правильно.
E>1) "произвольный доступ" может быть не таким уж и произвольным. Например, может быть какой-то важный паттерн доступа, который и надо оптимизировать.
E>2) Дерево может быть и с индексом.

E>Ещё раз говорю, что пусть у меня в каждом узле хранится число узлов в растущем из этого узла поддереве. Тогда операции "промотать 100500 элементов влево/вправо" и апдейты индекса тоже могут оказаться существенно дешевле...


может я конечно туплю , но промотать 100500 элементов мы все равно только за логарифмическое время можем? (начинаем с головы)
Или после выполнения поиска , мы запоминаем позицию в дереве ,и просто следующий поиск мы как то начинаем с запомненой позиции и учитываем доп инфу в узлах ?
Re[6]: подскажите контейнер
От: night beast СССР  
Дата: 03.02.14 13:04
Оценка:
Здравствуйте, Erop, Вы писали:

NB>>чуть быстрее вектора с некоторых случаях работает.

E>Ну эти "некоторые случаи", в основном, сводятся к добавлению/удалению в начало, а это вроде как не особо надо ТС...
E>Тут, скорее, может стоило бы посмотреть в сторону какой-то деревянной коллекции с индексом в векторе, который строится,перестраивается по требованию и, возможно, по кускам.

у тебя какой-то неправильный дек.
наши деки обычно реализованы через вектор чанков.
Re[3]: подскажите контейнер
От: Кодт Россия  
Дата: 03.02.14 13:04
Оценка: +2
Здравствуйте, AlexDoberman, Вы писали:

AD>тут можно идею доп деревьев чуть поподробнее ? без учета нагрузки на фрагментацию памяти

AD>какой из показателей вставка , удаление , проход улучшиться ?

Если хранить размеры поддеревьев, то скорость произвольного доступа по индексу из линейной (std::advance(begin,N)) превратится в логарифмическую.
Спрашивать у гугля, ясеня и рсдн ключевое слово "augmented red black tree"
Перекуём баги на фичи!
Re: подскажите контейнер
От: __Nicolay Россия  
Дата: 03.02.14 13:52
Оценка: 2 (1)
Здравствуйте, Аноним, Вы писали:

А>Всем добрый день!!


А>какие могут быть еще варианты ?


avlarray
Re[9]: подскажите контейнер
От: Erop Россия  
Дата: 03.02.14 14:33
Оценка:
Здравствуйте, AlexDoberman, Вы писали:

AD>может я конечно туплю , но промотать 100500 элементов мы все равно только за логарифмическое время можем? (начинаем с головы)


Ну, если дерево прошитое, то есть узлы хранят указатели на родителей, то ходить можно вообще локально. Типа идём всё время вниз влево, пока можем, потом начинаем выходить наружу и сворачивать правее, при возможности, и т. д...
Конечно иногда мы будем подниматься на несколько узлов, но в среднем это даст О(1) на узел, а в худшем O9( ln N ), и, довольно таки редко...
Мало того, если на надо не на один влево/вправо, а например, на 100, то использую инфу о размере поддеревьев, это дело можно сильно оптимизировать, так как можно проматывать узлы сразу поддеревьями...

просто нарисуй дерево, как граф на бумажке, и подумай, как написать алгоритм, который позволяет перейти от любого узла к следующему при переборе в ширину или в глубину, например, и всё поймёшь.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[7]: подскажите контейнер
От: Erop Россия  
Дата: 03.02.14 14:35
Оценка: +2
Здравствуйте, night beast, Вы писали:


NB>у тебя какой-то неправильный дек.

NB>наши деки обычно реализованы через вектор чанков.

И что это даёт при вставке с раздвижкой в случайное место?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[8]: подскажите контейнер
От: night beast СССР  
Дата: 03.02.14 15:20
Оценка: +1 :)
Здравствуйте, Erop, Вы писали:

E>Здравствуйте, night beast, Вы писали:



NB>>у тебя какой-то неправильный дек.

NB>>наши деки обычно реализованы через вектор чанков.

E>И что это даёт при вставке с раздвижкой в случайное место?


тупанул. чето думал, что чанки могут быть частично заполненными.
Re[10]: подскажите контейнер
От: AlexDoberman  
Дата: 03.02.14 15:33
Оценка:
Здравствуйте, Erop, Вы писали:

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


AD>>может я конечно туплю , но промотать 100500 элементов мы все равно только за логарифмическое время можем? (начинаем с головы)


E>Ну, если дерево прошитое, то есть узлы хранят указатели на родителей, то ходить можно вообще локально. Типа идём всё время вниз влево, пока можем, потом начинаем выходить наружу и сворачивать правее, при возможности, и т. д...

E>Конечно иногда мы будем подниматься на несколько узлов, но в среднем это даст О(1) на узел, а в худшем O9( ln N ), и, довольно таки редко...
E>Мало того, если на надо не на один влево/вправо, а например, на 100, то использую инфу о размере поддеревьев, это дело можно сильно оптимизировать, так как можно проматывать узлы сразу поддеревьями...

E>просто нарисуй дерево, как граф на бумажке, и подумай, как написать алгоритм, который позволяет перейти от любого узла к следующему при переборе в ширину или в глубину, например, и всё поймёшь.


ок , спасибо я понял принцип ))
Re[9]: подскажите контейнер
От: Erop Россия  
Дата: 03.02.14 20:30
Оценка:
Здравствуйте, night beast, Вы писали:


NB>тупанул. чето думал, что чанки могут быть частично заполненными.


Обычно такой "дек" называют B-дерево Только тогда уж выгоднее его невырожденным делать
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[4]: подскажите контейнер
От: TimurSPB Интернет  
Дата: 03.02.14 20:32
Оценка: :)
Здравствуйте, Erop, Вы писали:

E>Здравствуйте, night beast, Вы писали:


NB>>деку можно попробовать.

E>А что это даст?
кода не подходит std::vector или std::map, говорят "попробуй деку"
Make flame.politics Great Again!
Re[10]: подскажите контейнер
От: night beast СССР  
Дата: 04.02.14 05:14
Оценка: :)
Здравствуйте, Erop, Вы писали:


NB>>тупанул. чето думал, что чанки могут быть частично заполненными.


E>Обычно такой "дек" называют B-дерево Только тогда уж выгоднее его невырожденным делать


ну, В-дерево -- это все же дерево, а тут вложенность всего одна будет. недодерево такое
Re[11]: подскажите контейнер
От: Erop Россия  
Дата: 04.02.14 08:25
Оценка:
Здравствуйте, night beast, Вы писали:

NB>ну, В-дерево -- это все же дерево, а тут вложенность всего одна будет. недодерево такое


Ну, в целом, да. Но если у нас число элементов в чанке всё равно непредсказуемое, то есть смысл искать нужную чанку не линейно, а логарифмически, то есть такую структуру данных логичнее немного допилить и получить не вырожденное B-дерево, а обычное...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[12]: подскажите контейнер
От: night beast СССР  
Дата: 04.02.14 08:38
Оценка:
Здравствуйте, Erop, Вы писали:

NB>>ну, В-дерево -- это все же дерево, а тут вложенность всего одна будет. недодерево такое


E>Ну, в целом, да. Но если у нас число элементов в чанке всё равно непредсказуемое, то есть смысл искать нужную чанку не линейно, а логарифмически,


да. в чанке хранить индекс первого элемента. тогда и поиск будет логарифмический. но при инсерте придется все чанки апдейтить.

E>то есть такую структуру данных логичнее немного допилить и получить не вырожденное B-дерево, а обычное...


хз. возможно.
Re[13]: подскажите контейнер
От: Erop Россия  
Дата: 04.02.14 08:41
Оценка:
Здравствуйте, night beast, Вы писали:

NB>да. в чанке хранить индекс первого элемента. тогда и поиск будет логарифмический. но при инсерте придется все чанки апдейтить.

Зачем так сложно? B-дерево, почти такое же сложное, но работать будет лучше

NB> хз. возможно.


Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re: подскажите контейнер
От: antonio_banderas Россия  
Дата: 08.02.14 07:45
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Сравнение сложности операций

А> vector : map
А>вставка: n*log(n) , log(n)
А>удаление: n*log(n) , log(n)
А>проход: n , n*n

Если что, полный обход мэпа std::map это О(n), а не О(n*n).

А>отсюда я делаю вывод выбрать 1 вариант.

А>какие могут быть еще варианты ?

Я так и не понял, для чего тебе это надо.
Опиши плз саму задачу.
Re[2]: подскажите контейнер
От: Кодт Россия  
Дата: 08.02.14 10:02
Оценка:
Здравствуйте, antonio_banderas, Вы писали:

_>Если что, полный обход мэпа std::map это О(n), а не О(n*n).


Это если обход последовательный. А если прыжками в произвольную точку, то — в наивном исполнении он такой же, как у списка, т.е. O(n*n), а в дополненном — O(n*logn).
Перекуём баги на фичи!
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.