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

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

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

← →
Думкин © (2004-07-29 17:56) [41]

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

← →
Palladin © (2004-07-29 19:42) [42]

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

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

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

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

← →
Palladin © (2004-07-29 20:10) [44]

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

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

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

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

← →
KADAN © (2004-07-30 00:12) [46]

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

← →
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]. Все чудно работает

← →
Sergey Kaminski © (2004-07-30 01:31) [49]

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

THashedStringList есть и в Д6

← →
Palladin © (2004-07-30 02:58) [50]

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

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

> [47] Arm79 (30.07.04 00:21)

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

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

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

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