Добавление элемента в отсортированный массив

← →
AlexXn (2004-07-29 12:13) [0]

Как быстро добавить элемент в отсортированный массив(список)

← →
Sandman25 © (2004-07-29 12:13) [1]

Двоичным поиском

← →
Гаврила © (2004-07-29 12:14) [2]

пример двоичного поиска - в TStringList, смотри исходник Classes.pas

← →
Sandman25 © (2004-07-29 12:16) [3]

Кстати, быстро добавить в отсортированный список не получится.

← →
AlexXn (2004-07-29 12:19) [4]

>Sandman25
мне нужно найти именно место куда вставить. Так вот как это сделать быстро
>Гаврила
про двоичный поиск - это я в курсе. Но это найти существующий элемент. А нужно найти место для несуществующего

← →
Sandman25 © (2004-07-29 12:25) [5]

>А нужно найти место для несуществующего

А это как раз там, где был бы найден элемент, если бы он существовал.
То есть слева элементы меньше него, справа - больше.

← →
Poirot © (2004-07-29 12:25) [6]

хы))
а если ты добавишь эл-т используя бинарное дерево, то потом при прямом или обратном обходе ты соответственно буишь получать отсортированный массивЖ)
Ну вообщем предлагаю использовать дерево в качестве массива:)))

← →
Anatoly Podgoretsky © (2004-07-29 12:26) [7]

В массив быстро не получится, а вот в список есть вероятность.

← →
Sandman25 © (2004-07-29 12:29) [8]

[7] Anatoly Podgoretsky © (29.07.04 12:26)

С массивом тоже есть вероятность :)

← →
TUser © (2004-07-29 12:33) [9]

В список можно добавить быстро, но нельзя быстро найти место, куда вставлять. Ооочень не уверен, но м.б. в случае массива поможет Move. Правильтнее использовать представление этих данных в виде того или иного дерева, например бинарного.
См. Ахо и др., Структуры данных и алгоритмы.

← →
Гаврила © (2004-07-29 12:37) [10]

> про двоичный поиск - это я в курсе. Но это найти существующий
> элемент. А нужно найти место для несуществующего

Тот алгоритм, который приведен для TStringList, сделает все как надо. Смотри метод Add - он как раз вставляет элемент в нужное место в случае сортированного списка

← →
Anatoly Podgoretsky © (2004-07-29 12:38) [11]

Sandman25 © (29.07.04 12:29) [8]
С массивом нет никакой вероятности, все одназначно.

TUser © (29.07.04 12:33) [9]
Это тоже не одназначно, линейный список является массивом. Смотри выше про массивы. Пока не будет уточнения какой список, будет только вероятность.

← →
Sandman25 © (2004-07-29 12:41) [12]

[11] Anatoly Podgoretsky © (29.07.04 12:38)

>В массив быстро не получится, а вот в список есть вероятность.

А если у нас случайно так получилось, что вставляемый элемент должен быть самым последним? Неужели быстро все равно не получится? :)

← →
TUser © (2004-07-29 12:57) [13]

Anatoly Podgoretsky © (29.07.04 12:38) [11]
Я имел в виду связные списки.

← →
Anatoly Podgoretsky © (2004-07-29 13:28) [14]

Sandman25 © (29.07.04 12:41) [12]
Так это и есть вероятность, а вот в свящаный список сама вставка очень быстро, а если список двунапраленый или есть линейный список индексов, то и поиск можно органиховать очень быстро, методом деления по полам. Вставка в связаный список хоть в начало, хоть в середину, хоть в конец занимает одинаковое время.

← →
TUser © (2004-07-29 13:31) [15]

Что-то я не понял про то, как быстро организовать бинарныйпоискв св.списке, даже если он двунаправленный. Все равно надо перебрать все элементы, пока не найдем нужный. Или не так? Объясните, plz.

← →
Romkin © (2004-07-29 13:45) [16]

Мудрите вы все. Есть отсортированный массив, надо вставить элемент. Уширяем массив на 1 ячейку, записываем наш элемент последним, и делаем следующее:
сравниваем вставляемый элемент с предыдущим, если он меньше - меняем их местами, снова его на новом месте сравниваем... И так пока предыдущий не окажется меньшим или равным.
А вот вставка с двоичным посиком идет медленнее!

← →
Poirot © (2004-07-29 13:51) [17]

м.. а ели он самый первый, а массив большой?
Впринципе есть среднее время и вплне возможно они будут сравнимы по порядку..
Тут уже ИМХО опыт поможет!

← →
Romkin © (2004-07-29 13:57) [18]

В обычный массив вы в любом случае вставите элемент за время О(N). В среднем, при условии равномерно распределенных вставляемых элементов, вы переберете половину массива.
А с двоичным поиском: сначала ищем, куда вставить, это О(log N), а потом-то все равно надо сместить элементы, большие вставляемого на одну позицию, место освободить. Правда, в отличие от моего метода, это можно сделать через move, что эффективнее, чем переставлять по одному, как я предложил.
Но ведь есть же множество типов данных, которые позволяют делать такие операции гораздо быстрее

← →
Sandman25 © (2004-07-29 14:10) [19]

[11] Anatoly Podgoretsky © (29.07.04 12:38)

С массивом нет никакой вероятности, все одназначно.

[14] Anatoly Podgoretsky © (29.07.04 13:28)

Так это и есть вероятность

:)

← →
Sandman25 © (2004-07-29 14:13) [20]

[18] Romkin © (29.07.04 13:57)

Не нужно забывать про сравнения.
При двоичном будет log2N сравнений, а при пузырьковом - N/2, что гораздо больше. Причем сравнение может оказаться дорогой операцией.

← →
default © (2004-07-29 14:16) [21]

поконкретней бы автор обрисовал свою задачу
почему ТАК важна скорость, ...

← →
Думкин © (2004-07-29 14:20) [22]

> [20] Sandman25 © (29.07.04 14:13)

Вот-вот. Сравнение может фактически и съедать все время. И время будет определяться числом сравнений.

← →
Palladin © (2004-07-29 14:20) [23]

> Romkin © (29.07.04 13:57)

Это гораздоэффективней, предложенного "пузырька". И для общих случаев самое оптимальное. Есть поиск более быстрый чем бинарный, интерполяционный. Кнут, однако, всем голова...

> Но ведь есть же множество типов данных,

Да есть, но самое эффективное по скорости доступа к элементам это массив. А обычно именно доступ и важен...

← →
Romkin © (2004-07-29 14:22) [24]

Уговорили :)))

← →
Romkin © (2004-07-29 14:25) [25]

Жаль, REPLE нет :(

← →
Sandman25 © (2004-07-29 14:28) [26]

[23] Palladin © (29.07.04 14:20)

Это если первый элемент равен 1, сотый равен 100, а нам нужно найти 58, то мы сразу лезем проверять 58 элемент?

← →
Anatoly Podgoretsky © (2004-07-29 14:33) [27]

Вопрос про добавление, а не про поиск.
А автор до сих пор молчит, хихикает что ли?

← →
Думкин © (2004-07-29 14:36) [28]

Обычно быстро надо, если надо много раз вставить. А если так то лучше надописывать, а потом отсортировать и все.

А это вопрос на какую фразу? :)

Вставка в сортированный список бинарным поиском абсолютно глупое занятие, даже если он будет двусвязный и даже если будет хранить текущий индекс, это очень скажется на ресурсо емкости, и тот же хранимый индекс придется при вставке сдвигать, для этого опять придется пройтись по всем элементам до конца. Именно в списке пузырек и есть самое эффективное. Зато, блин, как быстро элемент вставится... капля быстродействия в море неоптимизированности...

На Есть поиск более быстрый чем бинарный, интерполяционный :)
Линейная интерполяция

> [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] |

:) Блин... не наглядней...

Спасибо! Понятно.

> [32] Palladin © (29.07.04 14:55)

В общем случае, если известно примерное распределение можно применять и другие функции. Бинарный и линейный - частные случаи.

Эт точно... Можно даже сказать крайние случаи...

d=trunc((j-i)*(K-K[i])/(K[j]-K[i]))
лучше так
d=trunc((K-K[i])/((K[j]-K[i])/(j-i)))
так лучше виден смысл этой простенькой формулы с простеньким смыслом)

Хе :)

Если уж на то пошло, то еще лучше так
Step=(K[j]-K[i])/(j-j);
d=(K-K[i])/Step;

Что то день сегодня на напряженный для форума...

← →
AlexXn (2004-07-29 15:57) [40]

Спасибо за все ответы всем.
Я вовсе не хихикаю :-)) просто инет у нас "переодический"
если обрисовать картину:
есть список (TList), отсортированный и достаточно большой(около 100К элементов). Необходимо в него добавить элемент. Естественно аккуратно добавить, чтобы не пересортировывать. А добавляется ну скажем не редко :-))) Вот почему важна скорость

Добавление элемента в отсортированный массив Найти похожие ветки