Динамические списки vs TList

Duncon · 03 май 2007, 10:12

А я говорю про метод класса TList к примеру, зачем городить если есть готовое?

SergeyS · 03 май 2007, 10:42

&quot писал(а):А я говорю про метод класса TList к примеру, зачем городить если есть готовое?

Да это похоже нужно для выполнения образовательной программы по языку Паскаль. Alex_Burn-то где-то учится, а обучение подобным вещам на уроках программирования на Паскале первое дело (сразу после темы массивы

).

Вообще-то такие вещи нужно знать, хотя бы для расширения кругозора

Duncon · 03 май 2007, 19:51

ну незнаю, если бы подобное делал создал бы класс списка и в нем бы хранил записи, но не ссылки внутри записей - это неудобно + скорее всего плохо отразится на производительности..

SergeyS · 04 май 2007, 04:33

&quot писал(а):создал бы класс списка и в нем бы хранил записи

Данная штука появилась, когда об ООП только начали говорить (если не раньше)

&quot писал(а):это неудобно + скорее всего плохо отразится на производительности..

А вот это ты зря. Пример: у тебя есть TList размером в несколько миллионов записей, тебе нужно добавить где-то в начале один элемент, для этого ты будешь использовать функцию move для перемещения части списка на один элемент, а затем присвоишь освободившемуся месту нужный тебе указатель; итого ты скопируешь как минимум несколько мегабайт памяти. В случае работы со списками, тебе достаточно переприсвоить от одного до двух указателей (next или prev) и вуаля список увеличился на один элемент.
Данный способ очень хорош для организации сильно меняющихся последовательностей данных

Duncon · 04 май 2007, 11:14

Ну если поползать по TList, то можно увидеть что меняются только индексы, но не двигаются сами записи... Хотя действительно (next или prev) довольно удобно, но при этом чтобы добраться до энного элемента придется пройтись по всем записям ни есть гуд...

Код: Выделить всё

procedure TList.Insert(Index: Integer; Item: Pointer);
begin
  if (Index < 0) or (Index > FCount) then
    Error(@SListIndexError, Index);
  if FCount = FCapacity then
    Grow;
  if Index < FCount then
    System.Move(FList^[Index], FList^[Index + 1],
      (FCount - Index) * SizeOf(Pointer));
  FList^[Index] := Item;
  Inc(FCount);
  if Item <> nil then
    Notify(Item, lnAdded);
end;

procedure TList.Move(CurIndex, NewIndex: Integer);
var
  Item: Pointer;
begin
  if CurIndex <> NewIndex then
  begin
    if (NewIndex < 0) or (NewIndex >= FCount) then
      Error(@SListIndexError, NewIndex);
    Item := Get(CurIndex);
    FList^[CurIndex] := nil;
    Delete(CurIndex);
    Insert(NewIndex, nil);
    FList^[NewIndex] := Item;
  end;
end;

BBB · 04 май 2007, 11:38

Duncon писал(а):Ну если поползать по TList, то можно увидеть что меняются только индексы, но не двигаются сами записи...

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

Хотя действительно (next или prev) довольно удобно, но при этом чтобы добраться до энного элемента придется пройтись по всем записям ни есть гуд...

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

somewhere · 04 май 2007, 12:00

Duncon, по-любому где-то есть Table, где ставиться соответствие между индексом и поинтером на объект. В этом случае найти энный элемент не составит труда. Иначе чтобы получить, например, последний элемент действительно нужно будет бегать по оперативке. Не думаю, что в TList это так, хотя ради эксперимента можно посмотреть.

&quot писал(а):К минусам твоего класса, наверное, надо еще отнести и то, что при интерсивном наполнении списка надо будет, помимо создания самих записей, периодически расширять (через переаллокейт динамической памяти, видимо) массив

FCapacity - обычно меняется не на 1-цу и не на два, а несколько сотен записей. Переаллокейт вызывается не особо часто - уж можно и потерпеть десятку тысяч тактов.

Duncon · 04 май 2007, 17:15

BBB собственно этот пример есть кусок класса TList, (неужели ни разу не заглядывал).
..по-любому где-то есть Table..
В примере с (next или prev) ее нет..
Вернулись к городить огород, есть замечательный класс Tlist в котором можно замечательно хранить записи....

Naeel Maqsudov · 07 май 2007, 00:51

Динамические списки позволяют представлять структуры данных с последовательным доступом. Динамические списки могут быть односвязными, двусвязными, циклическими. Следующая инкарнация динамических списков - это деревья. Все эти структуры отлично заточены под огромное количество прикладных задач. Очень рекомендую по этому поводу книгу Дональда Кнута "Искусство программирования". Том 1.
Там есть удивительно изящные алгоритмы. Например, с помощью взаимно-пересекающихся списков, составленных из коэффициентов полиномов, фантастически просто (на асемблере!) там решается задача сложения многочленов. Очень красивый и очень компактный алгоритм!

TList - к динамическим спискам не имеет отношения - это просто-напросто динамический массив указателей. А следовательно, это регулярная структура прямого доступа.

Итак, позвольте подытожить.

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

За сим давайте остановимся, пока это окончательно не переросло в тривиальный флейм.