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

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

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

массив [D5]

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

race1 (2002-10-20 05:36:00) [1]
А если сделать 2-3-4- и т.д. потока, то быстрее будет работать?

Anatoly Podgoretsky (2002-10-19 15:28:00) [2]
Вооьще лучше прочитать что нибудь про организацию разных списков, хотя не велика наука и самому разработать теорию.

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

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

race1 (2002-10-19 12:16:00) [3]
спасибо всем за ответы, я решил поступить как посоветовал han_malign, но у меня появился вопрос - я создал новый поинтер, и теперь предыдущиму поинтеру мне нужно NextItem сделать текущий созданный поинтер, т.е. так

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

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

MBo (2002-10-18 18:51:00) [4]
>han_malign
>Толик
Перечитал вопрос ;) Вы правы про дин. массив

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

MBo (2002-10-18 17:52:00) [6]
>сам является динамическим массивом
Все может быть. Может, автор расшифрует

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

MegaVolt (2002-10-18 17:35:00) [8]
Толик: Tlist масив указателей и их перемещение идёт гораздо быстрее чем просто перемещение массива целиком особенно большого!!! В этом и есть выигрыш. Примененять массив или двунаправленный список зависит от задачи: какая операция чаще всего встречается ту структуру и нужно применять.

MBo (2002-10-18 17:32:00) [9]
>Толик
Вероятно, получится. В TList хранится указатель на данные, и в subj-вом случае (как я его понял) нужно будет сдвигать в SizeOf(бооольшой элемент)/SizeOf(Pointer) меньше данных.

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

han_malign (2002-10-18 16:35:00) [11]
Азы структур данных:
если элементы массива не сортированы то оптимален связный список, если сортирован то ИМХО двоичное дерево
Ну, что такое двоичное дерево, я думаю объяснять не нужно.
Связный список(не помню на каком курсе, но напомнить стоит)
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 - массивный, для больших элементов - избыточность данных минимальна.

MegaVolt (2002-10-18 16:26:00) [12]
однозначно :) TList!!! или если есть желание можно самому сделать динамический двунаправленный список смотря что больше подходит для работы.
Список позволит быстренько перемещатся вперёд назад и удалять вставлять элементы очень быстро. Однако перемещение на нужный элемент потребует перебора по очереди.
TList наоборот позволяет быстро получать доступ но при удалении элемента из середины он сдвигает все остальны что занимает время хотя и минимальное

MBo (2002-10-18 15:56:00) [13]
TList!!!

Наверх

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