Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, Wasilij, Вы писали:
W>>Просто после слов "Хорошо видно, что при увеличенном размере элемента деревья догоняют, а то и значительно обгоняют массивы" совсем за массивы обидно стало .
S> Тебя и указатели не спасут начиная где то с 20 000 элементов
А от чего меня надо спасать?
Здравствуйте, Wasilij, Вы писали:
W>>>Просто после слов "Хорошо видно, что при увеличенном размере элемента деревья догоняют, а то и значительно обгоняют массивы" совсем за массивы обидно стало .
S>> Тебя и указатели не спасут начиная где то с 20 000 элементов W>А от чего меня надо спасать?
От жутких тормозов. Алгоритм вставок имеет кватратичную зависимость от количества элементов (размера перносимой памяти при вставке)
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Делов-то
W>Не указатели на данные вместо данных, а указатели на элементы вместо элементов. Мысль была такая: если деревья двигают внутри себя элементы (присваиванием указателя node*), то почему массивы должены копировать эти элементы?
А разве массивы двигают? Вы, извиняюсь за дурацкий вопрос, код статье вообще скачивали?
А то, вы как бы приводите код который не совсем мой, а потом на его основе что-то критикуете, а потмо додумываю, что же вы на самом деле имели ввиду.
Что б было понятно.
Масиивы имеют своим элементом
class arrayElement
{
KEY key;
DATA data;
}
А вот деревья
class treeElement
{
node * left;
node * right;
node * parent;
KEY key;
DATA data;
}
Насколько я понимаю, вы предлагаете в массиве хранить arrayElement * вместо arrayElement. Чем это принципиально отличается от уже приведённых тестов с autoptr?
Либо, что более вероятно, я что-то не так понимаю.
Было бы! Кто кому что даст? Потому что ОЧЕНЬ желательно сравнивать в переделах одного компилятора и одного межеджера памяти.
Кстати интересно как редакиця посмотрит на дополнение к статье до её опубликования на сайте Хорошо бы дали добро, а то как-то некрасиво, статьи из 6/03 вроде ещё даже не начали выкладывать на сайт.
Здравствуйте, adontz, Вы писали:
A>Здравствуйте, Serginio1, Вы писали:
S>> Было бы интересно сравнить с Б+ деревьями. S>> http://www.rsdn.ru/mag/0603/btree.XML
A>Было бы! Кто кому что даст? Потому что ОЧЕНЬ желательно сравнивать в переделах одного компилятора и одного межеджера памяти. A>Кстати интересно как редакиця посмотрит на дополнение к статье до её опубликования на сайте Хорошо бы дали добро, а то как-то некрасиво, статьи из 6/03 вроде ещё даже не начали выкладывать на сайт.
Да я думаю ничего криминального не будет. Тем более что статья больше подходила под дженерики нежели под алгоритмы.
Например применение двоичных деревьев на экземплярах классов будет тормозить из-за write bariera, но можно оганизовать хип на массиве и держать в качестве ссылки индекс массива или что этого ( http://www.rsdn.ru/Forum/Message.aspx?mid=445372&only=1
Здравствуйте, adontz, Вы писали:
A>Здравствуйте, Wasilij, Вы писали:
W>>Не указатели на данные вместо данных, а указатели на элементы вместо элементов. Мысль была такая: если деревья двигают внутри себя элементы (присваиванием указателя node*), то почему массивы должены копировать эти элементы?
A>А разве массивы двигают? Вы, извиняюсь за дурацкий вопрос, код статье вообще скачивали?
Я и не сказал, что массивы двигают, я сказал массивы копируют элементы. Копируют элементы при сортировке, вставке, удалении. А чем меньше размер элемента, тем быстрее будет копирование.
Код скачивал.
Раз уж зашла речь о коде к статье... У меня VC 7.0 не открыл файл солюшина, сказал, что версия файла VC 7.1! Почему код к статье нельзя было привести в VC 6.0? Мелочь — а все-таки.
A>А то, вы как бы приводите код который не совсем мой, а потом на его основе что-то критикуете, а потмо додумываю, что же вы на самом деле имели ввиду.
Я имел в виду, что не совсем правильно говорить, будто при увеличении размера элемента, массивы будут работать медленее.
A>Что б было понятно. A>Масиивы имеют своим элементом A>
A>class arrayElement
A> {
A> KEY key;
A> DATA data;
A> }
A>
A>А вот деревья A>
A>class treeElement
A> {
A> node * left;
A> node * right;
A> node * parent;
A> KEY key;
A> DATA data;
A> }
A>
A>Насколько я понимаю, вы предлагаете в массиве хранить arrayElement * вместо arrayElement. Чем это принципиально отличается от уже приведённых тестов с autoptr?
Тем, что в тесте с autoptr копировался целиком элемент, его ключ и его данные, а моем варианте копируется только 4 байта — указатель на элемент.
Здравствуйте, Wasilij, Вы писали:
W>Раз уж зашла речь о коде к статье... У меня VC 7.0 не открыл файл солюшина, сказал, что версия файла VC 7.1! Почему код к статье нельзя было привести в VC 6.0? Мелочь — а все-таки.
Мда, нехорошо вышло Извиняюсь. Но с другой стороны если в vcproj заменить Version="7.10" на Version="7.00" может помочь.
А вообще, там всего 2 файле в Win32 EXE проекте. Можете пересоздать. Главное, если на на вычислении Height будет вылетать, увеличьте размер стека. Но на 1000 элементов вылетать не должно.
W>Я имел в виду, что не совсем правильно говорить, будто при увеличении размера элемента, массивы будут работать медленее.
Как же не будут? Вот вставьте элемент в начало — придётся сдвинуть всё что после. Если там 30 элементов по 3 байта это не страшно, а если 30 элементов, по 262144 байт? 7 мегов копировать?
W>Тем, что в тесте с autoptr копировался целиком элемент, его ключ и его данные, а моем варианте копируется только 4 байта — указатель на элемент.
Ууу. Ну тогда надо на shared_ptr тестировать. По другому не выйдет.
Здравствуйте, adontz, Вы писали:
A>Здравствуйте, Wasilij, Вы писали:
W>>Я имел в виду, что не совсем правильно говорить, будто при увеличении размера элемента, массивы будут работать медленее.
A>Как же не будут? Вот вставьте элемент в начало — придётся сдвинуть всё что после. Если там 30 элементов по 3 байта это не страшно, а если 30 элементов, по 262144 байт? 7 мегов копировать?
Так я и говорю, что если в массиве хранить элемент, то так оно и будет.
Но если в массиве хранить УКАЗАТЕЛЬ на элемент, то указатель будет всегда занимать 4 байта и не будет зависеть от размера элемента. Поэтому при вставке в начало массива из 30 элементов, по 262144 байт придется копировать только 4х30 байт, а не 7 мегов. 7 мегов будут спокойно лежать на своем месте.
W>Так я и говорю, что если в массиве хранить элемент, то так оно и будет. W>Но если в массиве хранить УКАЗАТЕЛЬ на элемент, то указатель будет всегда занимать 4 байта и не будет зависеть от размера элемента. Поэтому при вставке в начало массива из 30 элементов, по 262144 байт придется копировать только 4х30 байт, а не 7 мегов. 7 мегов будут спокойно лежать на своем месте.
А теперь 262144 элемента по 4 байта. В Б+ деревьях это будет около 0.1 сек. Сколько займет на массиве ?????
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Re[8]: Двоичные деревья поиска
От:
Аноним
Дата:
01.06.04 16:29
Оценка:
Здравствуйте, Wasilij, Вы писали:
W>Так я и говорю, что если в массиве хранить элемент, то так оно и будет. W>Но если в массиве хранить УКАЗАТЕЛЬ на элемент, то указатель будет всегда занимать 4 байта и не будет зависеть от размера элемента. Поэтому при вставке в начало массива из 30 элементов, по 262144 байт придется копировать только 4х30 байт, а не 7 мегов. 7 мегов будут спокойно лежать на своем месте.
Да, но дело в том, что в массиве всё равно надо копировать (на вставке и удалении). И после какого-то количества элементов, деревья, где копировать практически не надо (только на удалении и очень редко), всё равно окажутся быстрее.
.
!
Извиняюсь. Но с другой стороны если в vcproj заменить Version="7.10" на Version="7.00" может помочь.
