массив

← →
race1 (2002-10-18 15:54) [0]

у меня есть боольшой массив (1000-2000 эл-ов, у каждого эл-та ещё 50-100 эл-ов), и мы должны удалить к примеру 2-ой эл-т в массиве. как это сделать наибыстрейшим образом? я делаю перемещением всех элементов от 2-ки до конца массива и потом SetLength делаем длину массива меньше. Существует ли др. способ? ещё - мы много раз проходимся по эл-там массива, и часто удаляем, поэтому надо самым быстрым способом!

← →
MBo (2002-10-18 15:56) [1]

TList!!!

← →
MegaVolt (2002-10-18 16:26) [2]

однозначно :) TList!!! или если есть желание можно самому сделать динамический двунаправленный список смотря что больше подходит для работы.
Список позволит быстренько перемещатся вперёд назад и удалять вставлять элементы очень быстро. Однако перемещение на нужный элемент потребует перебора по очереди.
TList наоборот позволяет быстро получать доступ но при удалении элемента из середины он сдвигает все остальны что занимает время хотя и минимальное

← →
han_malign (2002-10-18 16:35) [3]

Азы структур данных:
если элементы массива не сортированы то оптимален связный список, если сортирован то ИМХО двоичное дерево
Ну, что такое двоичное дерево, я думаю объяснять не нужно.
Связный список(не помню на каком курсе, но напомнить стоит)
type PArrayItem=^TArrayItem; TArrayItem=record Content: TSomeType; NextItem: PArrayItem; end;
это односторонне связанный список, если нужен проход в обе стороны то добавляется PrevItem

Добавление элемента после заданного(для двухсвязного)
New(NewItem); NewItem.Content:=MyCreateContent;
NewItem.NextItem:=CurItem.NextItem;
CurItem.NextItem:=NewItem;
NewItem.PrevItem:=CurItem;
if(NewItem.NextItem<>nil)//не конец списка
then NewItem.NextItem.PrevItem:=NewItem;

удаление
if(CurItem.NextItem<>nil)//не конец списка
then CurItem.NextItem.PrevItem:=CurItem.PrevItem;
if(CurItem.PrevItem<>nil)//не начало списка
then CurItem.PrevItem.NextItem:=CurItem.NextItem;
OldItem:=CurItem;
if(CurItem.NextItem<>nil)//не конец списка
then CurItem:=CurItem.NextItem
else CurItem:=CurItem.PrevItem;
//если CurItem=nil- список пустж
MyFreeContent(OldItem.Content);//не забыть освободить память содержимого
Dispose(OldItem);

передвижение
CurItem:=CurItem.NextItem;
CurItem:=CurItem.PrevItem;
CurItem=nil - конец списка

Главное не терять начало и конец списка, в большинстве задач они нужны

З.Ы. Можно удалять и вставлять длительные блоки
в C++ STL CList сделан именно на связных списках, Паскалевский TList - массивный, для больших элементов - избыточность данных минимальна.

← →
Толик (2002-10-18 17:28) [4]

to MBo © (18.10.02 15:56)
TList - это тот же массив. Так что быстрее не получится.
Самая наибольшая скорость вставки у связного (двусвязного) списка. Массив же оптимизирован для обращения к элементу по индексу.

← →
MBo (2002-10-18 17:32) [5]

>Толик
Вероятно, получится. В TList хранится указатель на данные, и в subj-вом случае (как я его понял) нужно будет сдвигать в SizeOf(бооольшой элемент)/SizeOf(Pointer) меньше данных.

← →
MegaVolt (2002-10-18 17:35) [6]

Толик: Tlist масив указателей и их перемещение идёт гораздо быстрее чем просто перемещение массива целиком особенно большого!!! В этом и есть выигрыш. Примененять массив или двунаправленный список зависит от задачи: какая операция чаще всего встречается ту структуру и нужно применять.

← →
han_malign (2002-10-18 17:41) [7]

2 MBo
в данном случае элемент массива, насколько я понял, сам является динамическим массивом, так что это все равно сдвиг массива указателей(TDynArrayOfSomething = pointer, но с "compiller magic"(c)Borlant System.pas), но частый сдвиг примерно (1000..2000)*4 байт, при активной работе, уже даст замедление в несколько раз.
> Существует ли др. способ? ещё - мы много раз проходимся по эл-там массива, и часто удаляем, поэтому надо самым быстрым способом!

← →
MBo (2002-10-18 17:52) [8]

>сам является динамическим массивом
Все может быть. Может, автор расшифрует

← →
Толик (2002-10-18 18:34) [9]

to MBo © (18.10.02 17:32)
Я так понял, что речь идёт о динамическом массиве, так что после удаления эл-та приходится cдвигать эл-ты на DeleteCount * SizeOf(pointer) байт. Так что то на то и выходит.

← →
MBo (2002-10-18 18:51) [10]

>han_malign
>Толик
Перечитал вопрос ;) Вы правы про дин. массив

← →
race1 (2002-10-19 12:16) [11]

спасибо всем за ответы, я решил поступить как посоветовал han_malign, но у меня появился вопрос - я создал новый поинтер, и теперь предыдущиму поинтеру мне нужно NextItem сделать текущий созданный поинтер, т.е. так

*pointer1* -> *pointer2*
*pointer1.NextItem=pointer2*

из рассказа han_malign я не совсем понял как это сделать

← →
Anatoly Podgoretsky (2002-10-19 15:28) [12]

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

Лобавление в твоем случае можно сделать так

NewItem.NextItem := ar.NextItem;
ar.NextItem := NewItem;

← →
race1 (2002-10-20 05:36) [13]

А если сделать 2-3-4- и т.д. потока, то быстрее будет работать?

массив Найти похожие ветки