| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Добавление элемента в отсортированный массив
AlexXn © (2004-07-29 12:13:00)Как быстро добавить элемент в отсортированный массив(список)
Sandman25 (2004-07-29 14:58:00) [21]Спасибо! Понятно.
Palladin (2004-07-29 14:57:00) [22]:) Блин... не наглядней...
Palladin (2004-07-29 14:55:00) [23]
> [30] Sandman25 © (29.07.04 14:42)
Ну почти линейная.
d=trunc((j-i)*(K-K[i])/(K[j]-K[i]))
d расстояние первоначального сравнения. i и j номера соответственно первого и последнего элемента отрезка. Ki и Kj значения элементов в i и j позициях. Если все элементы исходного массива являются(или достаточно близки к ним) членами арифметической прогрессии, то поиск может пройти за одно сравнение. Если не найден нужный ключ с первого раза, то исходный отрезок поиска сужается и делается следующее сравнение с ключом расположенным на новом расстоянии d.
Вот так наглядней
|(j-i)*(K-K[i])|
d=trunc|--------------|
| K[j] - K[i] |
Palladin (2004-07-29 14:53:00) [24]
> [30] Sandman25 © (29.07.04 14:42)
Ну почти линейная.
d=trunc((j-i)*(K-K[i])/(K[j]-K[i]))
d расстояние первоначального сравнения. i и j номера соответственно первого и последнего элемента отрезка. Ki и Kj значения элементов в i и j позициях. Если все элементы исходного массива являются(или достаточно близки к ним) членами арифметической прогрессии, то поиск может пройти за одно сравнение. Если не найден нужный ключ с первого раза, то исходный отрезок поиска сужается и делается следующее сравнение с ключом расположенным на новом расстоянии d.
Вот так наглядней
|(j-i)*(K-K[i])|
d=trunc|--------------|
| K[j] - K[i] |
Sandman25 (2004-07-29 14:42:00) [25]На Есть поиск более быстрый чем бинарный, интерполяционный:)
Линейная интерполяция
Palladin (2004-07-29 14:37:00) [26]А это вопрос на какую фразу? :)
Вставка в сортированный список бинарным поиском абсолютно глупое занятие, даже если он будет двусвязный и даже если будет хранить текущий индекс, это очень скажется на ресурсо емкости, и тот же хранимый индекс придется при вставке сдвигать, для этого опять придется пройтись по всем элементам до конца. Именно в списке пузырек и есть самое эффективное. Зато, блин, как быстро элемент вставится... капля быстродействия в море неоптимизированности...
Думкин (2004-07-29 14:36:00) [27]Обычно быстро надо, если надо много раз вставить. А если так то лучше надописывать, а потом отсортировать и все.
Anatoly Podgoretsky (2004-07-29 14:33:00) [28]Вопрос про добавление, а не про поиск.
А автор до сих пор молчит, хихикает что ли?
Sandman25 (2004-07-29 14:28:00) [29][23] Palladin © (29.07.04 14:20)
Это если первый элемент равен 1, сотый равен 100, а нам нужно найти 58, то мы сразу лезем проверять 58 элемент?
Romkin (2004-07-29 14:25:00) [30]Жаль, REPLE нет :(
Romkin (2004-07-29 14:22:00) [31]Уговорили :)))
Palladin (2004-07-29 14:20:00) [32]
> Romkin © (29.07.04 13:57)
Это гораздоэффективней, предложенного "пузырька". И для общих случаев самое оптимальное. Есть поиск более быстрый чем бинарный, интерполяционный. Кнут, однако, всем голова...
> Но ведь есть же множество типов данных,
Да есть, но самое эффективное по скорости доступа к элементам это массив. А обычно именно доступ и важен...
Думкин (2004-07-29 14:20:00) [33]> [20] Sandman25 © (29.07.04 14:13)
Вот-вот. Сравнение может фактически и съедать все время. И время будет определяться числом сравнений.
default (2004-07-29 14:16:00) [34]поконкретней бы автор обрисовал свою задачу
почему ТАК важна скорость, ...
Sandman25 (2004-07-29 14:13:00) [35][18] Romkin © (29.07.04 13:57)
Не нужно забывать про сравнения.
При двоичном будет log2N сравнений, а при пузырьковом - N/2, что гораздо больше. Причем сравнение может оказаться дорогой операцией.
Sandman25 (2004-07-29 14:10:00) [36][11] Anatoly Podgoretsky © (29.07.04 12:38)
С массивом нет никакой вероятности, все одназначно.
[14] Anatoly Podgoretsky © (29.07.04 13:28)
Так это и есть вероятность
:)
Romkin (2004-07-29 13:57:00) [37]В обычный массив вы в любом случае вставите элемент за время О(N). В среднем, при условии равномерно распределенных вставляемых элементов, вы переберете половину массива.
А с двоичным поиском: сначала ищем, куда вставить, это О(log N), а потом-то все равно надо сместить элементы, большие вставляемого на одну позицию, место освободить. Правда, в отличие от моего метода, это можно сделать через move, что эффективнее, чем переставлять по одному, как я предложил.
Но ведь есть же множество типов данных, которые позволяют делать такие операции гораздо быстрее
Poirot (2004-07-29 13:51:00) [38]м.. а ели он самый первый, а массив большой?
Впринципе есть среднее время и вплне возможно они будут сравнимы по порядку..
Тут уже ИМХО опыт поможет!
Romkin (2004-07-29 13:45:00) [39]Мудрите вы все. Есть отсортированный массив, надо вставить элемент. Уширяем массив на 1 ячейку, записываем наш элемент последним, и делаем следующее:
сравниваем вставляемый элемент с предыдущим, если он меньше - меняем их местами, снова его на новом месте сравниваем... И так пока предыдущий не окажется меньшим или равным.
А вот вставкас двоичным посиком идет медленнее!
TUser (2004-07-29 13:31:00) [40]Что-то я не понял про то, как быстро организовать бинарныйпоискв св.списке, даже если он двунаправленный. Все равно надо перебрать все элементы, пока не найдем нужный. Или не так? Объясните, plz.
| |
Страницы: 