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

← →
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]

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

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

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

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

← →
Sandman25 © (2004-07-29 14:42) [30]

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

← →
Palladin © (2004-07-29 14:53) [31]

> [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:55) [32]

← →
Palladin © (2004-07-29 14:57) [33]

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

← →
Sandman25 © (2004-07-29 14:58) [34]

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

← →
Думкин © (2004-07-29 15:04) [35]

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

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

← →
Palladin © (2004-07-29 15:07) [36]

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

← →
default © (2004-07-29 15:23) [37]

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

← →
Palladin © (2004-07-29 15:32) [38]

Хе :)

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

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

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

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

Но....
1. Для чисел, а не для строк.
2. Для линейно упорядоченных
3. Шел домой думаал, пришел не понял но 1,2.

Это очень большое НО... Единственное в качестве ключа использовать хэш... Однако уникальное сопоставение строк и ключей опять же...

А с объектами еще хужее...

← →
Хм... (2004-07-29 20:08) [43]

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

Горячий финский парень.

← →
Хм... (2004-07-29 20:16) [45]

> Palladin © (29.07.04 20:10) [44]

Да, а Вы всё мастереете и мастереете. По Вашей манере ответов последенее время и без отличительного значка не ошибиться в том, что Вы настоящий мастер:)

Вопрос вдогонку:
распределение не равномерное, но и не известно заранее. если использовать линейный поиск, каким образом лучше сужать отрезок, брать левую или правую часть или есть варианты получше?

← →
Arm79 (2004-07-30 00:21) [47]

Позвольте и мне высказаться. Я в последнее время тоже занимался ускорением доступа к различным строкам, хранящимся в массиве или списке. Просто проектировал систему реал-тайм, вот и пришлось. Получилось менее 1 мс в поиске/добавлении в примерно 20000 строк. Более точно не стал считать, тк такая задержка при моих условиях вполне нормальна. Так вот, добавление строки в отсортированный список строк типа TStringList лучше всего делать с применением метода Add этого списка. Хочу отметить, что это действует, когда список отсортирован, иначе задержка увеличивается в десятки раз. Если Делфи 7, то вместо TStringList могу порекомендовать THashedStringList (пишу по памяти). Код своей программы не публикую, потому что с меня взято обязательство по сохраниению коммерческой тайны, но по почте отрывок из программы прислать могу. Правда код писался впопыхах, но гарантированно все работает. Все, что говорили выше, тоже правильно, но при разработке собственных списков. Мне пришлось, ко всему прочему, и собственные индексы разрабатывать. В моем случае ClientDataSet не подошел из-за медлительности.
Я считаю, что лучше использовать то, что и так есть. Недаром исходники Делфи считаются лучшим учебником. Это мое частное мнение, на абсолютное знание не претендую, буду рад любому замечанию.

← →
Arm79 (2004-07-30 00:30) [48]

Это я к чему. В коде используется метод "деления пополам" (извиняюсь за коверкание). Метод описан в Хм... (29.07.04 20:08) [43]. Все чудно работает

>> Arm79 (30.07.04 00:21) [47]

THashedStringList есть и в Д6

Вот замучили... метод деления пополам, он же бинарный поиск, уже рассмотрен на несколько постов выше всех ваших...

Лучше б, решение для строк и объектов побыстрей чем бинарный придумали...

> [47] Arm79 (30.07.04 00:21)

Ровно таким же и по тем же причинам и я занимался недавно. Но использовал более сложные структуры а не TStringList и т.п. У меня список объектов.
К сожалению ничего особо нового не придумал, поэтому
> [51] Palladin © (30.07.04 03:05)
для меня пока открыт.

AlexXn (29.07.04 15:57) [40]
TList это линейный список, значит смотри что выше сказано про массивы.

А я все-таки за деревья, раз там 100льКо элементов и часто вставляются. Находится за логарифмическое время, + примерно столько же времени на вставку.

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