Здравствуйте, AlexDoberman, Вы писали:
AD>есть некий фреймверк который отображает items AD>для этого ему (фреймверку ) я должен передать model из которой он извлечет данные
AD>дальше он показывает показывает model. AD>соответственно данные добавляются новые / удаляются / редактируются (при всем этом должен поддерживаться сортировка) AD>вот как то так. AD>Соответственно после каждой каждой модификации данный модуль отображения должен перерисовать данные
в данной постановке можно было бы вообще отказаться от поиска по index, т.к. мы заранее знаем, что индексы будут подсовываться в возрастающем порядке
нам достаточно внутри хранить некий итератор, который будет инкрементиться после вызова data(index). можем ассерты вставить на то, что индексы подсовываются по порядку
для этой задачи самый простой set может подойти
Здравствуйте, AlexDoberman, Вы писали:
AD>правильно я понимаю что как только возникает дерево , то сразу произвольный доступ по индексу мы выполняем за log n ?
Нет, не правильно.
1) "произвольный доступ" может быть не таким уж и произвольным. Например, может быть какой-то важный паттерн доступа, который и надо оптимизировать.
2) Дерево может быть и с индексом.
Ещё раз говорю, что пусть у меня в каждом узле хранится число узлов в растущем из этого узла поддереве. Тогда операции "промотать 100500 элементов влево/вправо" и апдейты индекса тоже могут оказаться существенно дешевле...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, AlexDoberman, Вы писали:
E>Если второе, то моет просто можно приделать в модель механизм кэширования позиции и строить инекс не на всю коллекуию. а только на нужную часть? Ну там постранично, например?
да я впринципе уже так и сделал
т.е. я ввел преположение что при сканированиии он запрашивает элементы последовательно. i, i+1 , ... i+k
Здравствуйте, uzhas, Вы писали:
U>в данной постановке можно было бы вообще отказаться от поиска по index, т.к. мы заранее знаем, что индексы будут подсовываться в возрастающем порядке U>нам достаточно внутри хранить некий итератор, который будет инкрементиться после вызова data(index). можем ассерты вставить на то, что индексы подсовываются по порядку U>для этой задачи самый простой set может подойти
Зачем assert'ы?
Лучше обработать + дебаг-средство по сбору статистики...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, AlexDoberman, Вы писали:
AD>>правильно я понимаю что как только возникает дерево , то сразу произвольный доступ по индексу мы выполняем за log n ? E>Нет, не правильно. E>1) "произвольный доступ" может быть не таким уж и произвольным. Например, может быть какой-то важный паттерн доступа, который и надо оптимизировать. E>2) Дерево может быть и с индексом.
E>Ещё раз говорю, что пусть у меня в каждом узле хранится число узлов в растущем из этого узла поддереве. Тогда операции "промотать 100500 элементов влево/вправо" и апдейты индекса тоже могут оказаться существенно дешевле...
может я конечно туплю , но промотать 100500 элементов мы все равно только за логарифмическое время можем? (начинаем с головы)
Или после выполнения поиска , мы запоминаем позицию в дереве ,и просто следующий поиск мы как то начинаем с запомненой позиции и учитываем доп инфу в узлах ?
Здравствуйте, Erop, Вы писали:
NB>>чуть быстрее вектора с некоторых случаях работает. E>Ну эти "некоторые случаи", в основном, сводятся к добавлению/удалению в начало, а это вроде как не особо надо ТС... E>Тут, скорее, может стоило бы посмотреть в сторону какой-то деревянной коллекции с индексом в векторе, который строится,перестраивается по требованию и, возможно, по кускам.
у тебя какой-то неправильный дек.
наши деки обычно реализованы через вектор чанков.
Здравствуйте, AlexDoberman, Вы писали:
AD>тут можно идею доп деревьев чуть поподробнее ? без учета нагрузки на фрагментацию памяти AD>какой из показателей вставка , удаление , проход улучшиться ?
Если хранить размеры поддеревьев, то скорость произвольного доступа по индексу из линейной (std::advance(begin,N)) превратится в логарифмическую.
Спрашивать у гугля, ясеня и рсдн ключевое слово "augmented red black tree"
Здравствуйте, AlexDoberman, Вы писали:
AD>может я конечно туплю , но промотать 100500 элементов мы все равно только за логарифмическое время можем? (начинаем с головы)
Ну, если дерево прошитое, то есть узлы хранят указатели на родителей, то ходить можно вообще локально. Типа идём всё время вниз влево, пока можем, потом начинаем выходить наружу и сворачивать правее, при возможности, и т. д...
Конечно иногда мы будем подниматься на несколько узлов, но в среднем это даст О(1) на узел, а в худшем O9( ln N ), и, довольно таки редко...
Мало того, если на надо не на один влево/вправо, а например, на 100, то использую инфу о размере поддеревьев, это дело можно сильно оптимизировать, так как можно проматывать узлы сразу поддеревьями...
просто нарисуй дерево, как граф на бумажке, и подумай, как написать алгоритм, который позволяет перейти от любого узла к следующему при переборе в ширину или в глубину, например, и всё поймёшь.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
NB>у тебя какой-то неправильный дек. NB>наши деки обычно реализованы через вектор чанков.
И что это даёт при вставке с раздвижкой в случайное место?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, night beast, Вы писали:
NB>>у тебя какой-то неправильный дек. NB>>наши деки обычно реализованы через вектор чанков.
E>И что это даёт при вставке с раздвижкой в случайное место?
тупанул. чето думал, что чанки могут быть частично заполненными.
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, AlexDoberman, Вы писали:
AD>>может я конечно туплю , но промотать 100500 элементов мы все равно только за логарифмическое время можем? (начинаем с головы)
E>Ну, если дерево прошитое, то есть узлы хранят указатели на родителей, то ходить можно вообще локально. Типа идём всё время вниз влево, пока можем, потом начинаем выходить наружу и сворачивать правее, при возможности, и т. д... E>Конечно иногда мы будем подниматься на несколько узлов, но в среднем это даст О(1) на узел, а в худшем O9( ln N ), и, довольно таки редко... E>Мало того, если на надо не на один влево/вправо, а например, на 100, то использую инфу о размере поддеревьев, это дело можно сильно оптимизировать, так как можно проматывать узлы сразу поддеревьями...
E>просто нарисуй дерево, как граф на бумажке, и подумай, как написать алгоритм, который позволяет перейти от любого узла к следующему при переборе в ширину или в глубину, например, и всё поймёшь.
NB>тупанул. чето думал, что чанки могут быть частично заполненными.
Обычно такой "дек" называют B-дерево Только тогда уж выгоднее его невырожденным делать
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, night beast, Вы писали:
NB>>деку можно попробовать. E>А что это даст?
кода не подходит std::vector или std::map, говорят "попробуй деку"
NB>>тупанул. чето думал, что чанки могут быть частично заполненными.
E>Обычно такой "дек" называют B-дерево Только тогда уж выгоднее его невырожденным делать
ну, В-дерево -- это все же дерево, а тут вложенность всего одна будет. недодерево такое
Здравствуйте, night beast, Вы писали:
NB>ну, В-дерево -- это все же дерево, а тут вложенность всего одна будет. недодерево такое
Ну, в целом, да. Но если у нас число элементов в чанке всё равно непредсказуемое, то есть смысл искать нужную чанку не линейно, а логарифмически, то есть такую структуру данных логичнее немного допилить и получить не вырожденное B-дерево, а обычное...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
NB>>ну, В-дерево -- это все же дерево, а тут вложенность всего одна будет. недодерево такое
E>Ну, в целом, да. Но если у нас число элементов в чанке всё равно непредсказуемое, то есть смысл искать нужную чанку не линейно, а логарифмически,
да. в чанке хранить индекс первого элемента. тогда и поиск будет логарифмический. но при инсерте придется все чанки апдейтить.
E>то есть такую структуру данных логичнее немного допилить и получить не вырожденное B-дерево, а обычное...
Здравствуйте, night beast, Вы писали:
NB>да. в чанке хранить индекс первого элемента. тогда и поиск будет логарифмический. но при инсерте придется все чанки апдейтить.
Зачем так сложно? B-дерево, почти такое же сложное, но работать будет лучше
NB> хз. возможно.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, antonio_banderas, Вы писали:
_>Если что, полный обход мэпа std::map это О(n), а не О(n*n).
Это если обход последовательный. А если прыжками в произвольную точку, то — в наивном исполнении он такой же, как у списка, т.е. O(n*n), а в дополненном — O(n*logn).