Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

Страницы: 1 2 3 >
AlexXn © (2004-07-29 12:13:00)
Как быстро добавить элемент в отсортированный массив(список)

TUser (2004-07-30 10:00:00) [1]
А я все-таки за деревья, раз там 100льКо элементов и часто вставляются. Находится за логарифмическое время, + примерно столько же времени на вставку.

Anatoly Podgoretsky (2004-07-30 09:54:00) [2]
AlexXn (29.07.04 15:57) [40]
TList это линейный список, значит смотри что выше сказано про массивы.

Думкин (2004-07-30 06:34:00) [3]
> [47] Arm79 (30.07.04 00:21)

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

Palladin (2004-07-30 03:05:00) [4]
Лучше б, решение для строк и объектов побыстрей чем бинарный придумали...

Palladin (2004-07-30 02:58:00) [5]
Вот замучили... метод деления пополам, он же бинарный поиск, уже рассмотрен на несколько постов выше всех ваших...

Sergey Kaminski (2004-07-30 01:31:00) [6]
>> Arm79 (30.07.04 00:21) [47]

THashedStringList есть и в Д6

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

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

KADAN (2004-07-30 00:12:00) [9]
Вопрос вдогонку:
распределение не равномерное, но и не известно заранее. если использовать линейный поиск, каким образом лучше сужать отрезок, брать левую или правую часть или есть варианты получше?

Хм... (2004-07-29 20:16:00) [10]

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

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

Palladin (2004-07-29 20:10:00) [11]
Горячий финский парень.

Хм... (2004-07-29 20:08:00) [12]
Так вопрос-то в том, что нужно вставить элемент в отсортированныймассив или список. Зачем перебирать все элементы? Не сортировать же снова. Делить пополам, сравнивать последний элемент левой половины с всатвляемым элементом, если не подходит по условию - больше не возвращаться к левой половине. Далее правую половину пополам и т.д. В связном списке вставка - задача для начинающих. В массиве - установить новую длинну, от позиции, где должен быть вставлен элемент все элементы сдвинуть вправо и в освободившееся место вставить новый.

Palladin (2004-07-29 19:42:00) [13]
Это очень большое НО... Единственное в качестве ключа использовать хэш... Однако уникальное сопоставение строк и ключей опять же...

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

Думкин (2004-07-29 17:56:00) [14]
Но....
1. Для чисел, а не для строк.
2. Для линейно упорядоченных
3. Шел домой думаал, пришел не понял но 1,2.

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

Palladin (2004-07-29 15:35:00) [16]
Что то день сегодня на напряженный для форума...

Palladin (2004-07-29 15:32:00) [17]
Хе :)

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

default (2004-07-29 15:23:00) [18]
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:07:00) [19]
Эт точно... Можно даже сказать крайние случаи...

Думкин (2004-07-29 15:04:00) [20]
> [32] Palladin © (29.07.04 14:55)

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

Страницы: 1 2 3 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »