Скорость...

← →
roadstar © (2004-03-17 15:24) [0]

Народ! Кто знает компонент, который работает с элементами быстрее, чем TList?
Заранее благодарен за ответы.

← →
Digitman © (2004-03-17 15:27) [1]

> компонент, который работает с элементами быстрее, чем TList

с чего ты взял, что он "медленно работает" ?

← →
Романов Р.В. © (2004-03-17 15:28) [2]

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

← →
Игорь Шевченко © (2004-03-17 15:34) [3]

> Кто знает компонент, который работает с элементами быстрее,
> чем TList

Статический массив с выключенной опцией Range Check :)

← →
RoadStar © (2004-03-17 15:35) [4]

> Digitman

Попробуй добавить 200000 указателей, а потом удалить эдак 50000 в любых местах. Довольно вяло получается, хотя добовляет он быстро!

> Романов Р.В.

Операции удаления элементов из списка (указателей).

← →
Романов Р.В. © (2004-03-17 15:37) [5]

Связаный список

← →
Романов Р.В. © (2004-03-17 15:40) [6]

Или удаляй врукопашную.
Если удаляешь в середине. Перемести хвостовые элементы вперед и удали последние.

← →
Digitman © (2004-03-17 15:44) [7]

> добавить 200000 указателей, а потом удалить эдак 50000 в
> любых местах

кто ж тебя заставляет их удалять ?) разумеется, всякий раз вызывается Move(), что и сказывается неблаготворно на общей производительности алгоритма ..

ты не удаляй элемент, а пиши в него nil

когда же возникает необходимость добавления нового эл-та (не в ходе первоначального заполнения, а уже в ходе последующей работы, когда первоначально заполненный список подвергается модификациям), ищи первое же вхождение nil-эл-та в списке и пиши туда новое значение

← →
RoadStar © (2004-03-17 15:48) [8]

> Романов Р.В.

Надо, чтоб список оставался отсортированным, поэтому перенос с конца не подойдет

← →
Digitman © (2004-03-17 15:55) [9]

> RoadStar

> Надо, чтоб список оставался отсортированным

TList не имеет автосортировки после изменения его состояния
если же ты к месту и не к месту вызываешь Sort() после каждой модификации списка - это твои проблемы ... значит, алгоритм не продуман ... и никакой иной списочный класс в этом случае не поможет тебе

← →
RoadStar © (2004-03-17 15:58) [10]

> Digitman

Sort() я и не вызываю, список формируется из файла, в котором записи уже отсортированы!

← →
Digitman © (2004-03-17 16:11) [11]

> RoadStar © (17.03.04 15:58) [10]

тогда я вообще не вижу проблем..

вместо явного удаления пиши nil в соотв.элемент
при этом список остается отсортированным - достаточно при его считывании/сканировании просто игнорировать nil-элементы

естественно, ощутимый выиинрыш в производительности алгоритма, построенного по такой логике, ты получишь только в том случае, если список заполняется однократно (при первоначальном считывании из файла), а затем его эл-ты лишь многократно считываются и/или удаляются тобой (т.е. операции вставки/модификации, требующие после выполнения немедленной сортировки обновленного списка, либо отсутствуют либо минимальны)

← →
Игорь Шевченко © (2004-03-17 16:14) [12]

> Надо, чтоб список оставался отсортированным

1) А как ты определяешь критерий для сортировки ?

2) Посмотри, как работает в classes.pas TStringList с свойством sorted равным true, сделай свой список по образу и подобию, все же быстрее будет.

> Игорь Шевченко

С чего бы быстрее-то , Игорь ?

Если у автора в какие-то моменты времени производятся массированные удаления произвольно выбираемых эл-тов, после чего состояние сортированности списка должно быть автоматически сохраняться либо быть явно восстановлено, то нет ничего дурнее автосортировки, подразумеваемой под Sorted = True .. после каждой модификации списка он будет подвергаться явно неоправданной сортировке ..

Удалил (записал nil) он блок из произвольно отобранных им по каким-то секретным критериям 50000 элементов, вызвал однократно после этой акции сортировку - и готово ! Быстро и со вкусом)

Спасибки всем за ответы!!!

← →
Mim (2004-03-17 18:16) [16]

Я вот думаю что проблема что tlist хранит
свои элементы в виде массива
то есть
oooooooooooooooqiwoooooo

и при удалении элемента i
ему приходтся переписывать все позжестоящие элементы по направлению вверх

oooooooooooooooqwoooooo

Если бы заменить массик на список элементов хранящих ссылки на предидущий и след элемент то удаление можно значительно упрастить

o <> q <> i <> w <> o

при удалении элемента i надо поравить ссылкук элемента q и ц

o <> q <> w <> o

Но в таком подходе усложняется доступ например к 5 му элементу, то есть доступ к элементу по номеру.

сделал свой аналог tlist, поудалял 50тыс,поставил на место удаленных nil, потом бежишься и двигаешь не весь массив, а только до следующего пустого места.
очень быстро.

Скорость... Найти похожие ветки