Как удалить пустоты в большом массиве ?

← →
Кен (2004-02-16 05:03) [0]

Есть большой массив, элементы которого ссылаются друг на друга. Постепенно часть элементов этого массива становится ненужными и их надо бы удалить, а остальные элементы сдвинуть, чтобы пустот небыло. Но проблема в том, что в этом случае ссылки на сдвинутые элементы собъются, и значит надо их корректировать, а это слишком долго и неудобно. Как можно решить такую проблему ?

← →
dr Tr0jan (2004-02-16 05:12) [1]

Сделать динамический массив. Или использовать множество.

← →
Кен (2004-02-16 05:22) [2]

> dr Tr0jan © (16.02.04 05:12) [1]
> Сделать динамический массив. Или использовать множество.

А какая разница динамический или статический ? Дырки то всё равно и там и там будут.

← →
Verg (2004-02-16 07:21) [3]

Либо корректируй ссылки, либо вместо массивов используй связные списки.

← →
Alex Konshin (2004-02-16 07:50) [4]

Первая идея: хранить в массиве ссылки на элементы (например, можно использовать TList), тогда удаление элемента сводится к удалению элемента в массиве и уничтожению объекта (или освобождению памяти из-под record).
Никакие ссылки править не нужно, так как адреса других элементов не меняются.

Еще идея: использовать другой ключ для доступа к элементу. То есть, не индекс, а, например, его уникальный Id.
Правда, тогда операция доступа к элементу становится более дорогостоящей, но зато никакие ссылки править не надо. Могу порекомендовать свой класс AVLTree как основу для реализации этой идеи.

Тут уж тебе самому решать, какая у тебя задача и какое решение тебе лучше подходит.

← →
Кен (2004-02-17 01:34) [5]

> Alex Konshin © (16.02.04 07:50) [4]

Тогда нужен ещё массив ссылок или id, а это увеличивает размеры. Да и скорость доступа думаю замедлится.
Хочется, чтобы это всё было просто и желательно, чтобы как нибудь само делалось. Есть же, например, команда Sort, которая сортирует, а уж как она сортирует - это её дело. Так же и тут хотелось бы простое решение.

← →
Alex Konshin (2004-02-17 01:37) [6]

Ну так я дал тебе два решения, первое - очень простое.

← →
Alex Konshin (2004-02-17 02:16) [7]

Второе же решение может быть вполне приемлемо.
Что ты понимаешь под временем доступа к элементу в твоей конкретной задаче?
Например, если ты создал массив фамилий сотрудников и потом, используя быстрый доступ через индекс тупо перебираешь фамилии для нахождения нужной, то в итоге ты получаешь очень медленный доступ к конкретному, нужному именно в этот момент, элементу.
Мысль ясна?
А реализации, в которых массивы притянуты за уши, очень нередки и даже типичны для начинающих. А, судя по вопросу, у тебя вполне может быть именно этот случай - неправильная организация данных.

← →
Suntechnic (2004-02-17 06:12) [8]

>Кен ©

То, о чём ты пишешь это извечная проблема "связанный список - вектор". Первый характеризуется оптимальной работой с памятью, второй скоростью доступа. Комбинировать два эти подхода получается (например с использованием хэш-таблиц см. вторую идею Alex Konshin © ), но опять же приходится чем то жертвовать. А так чтобы и то и другое и попроще.... извини, но так в жизни не бывает.

Есть же, например, команда Sort, которая сортирует, а уж как она сортирует - это её дело. Так же и тут хотелось бы простое решение.

И последнее...

Есть же, например, команда Sort, которая сортирует, а уж как она сортирует - это её дело

То, что ты вызываешь одну ф-цию совсем не означает, что она состоит из двух строчек кода.

← →
Кен (2004-02-17 07:02) [9]

> Suntechnic © (17.02.04 06:12) [8]
> То, о чём ты пишешь это извечная проблема "связанный список
> - вектор". Первый характеризуется оптимальной работой с
> памятью, второй скоростью доступа. Комбинировать два эти
> подхода получается (например с использованием хэш-таблиц

Кстати, а как в Дельфи с хэшами ? Хочу такие же как в перле, чтобы не мучится.

> Alex Konshin © (17.02.04 02:16) [7]
> Например, если ты создал массив фамилий сотрудников и потом,
> используя быстрый доступ через индекс тупо перебираешь фамилии
> для нахождения нужной

У меня ничего не перебирается, а всё по ссылкам.

← →
Defunct (2004-02-17 07:22) [10]

> Есть большой массив, элементы которого ссылаются друг на друга.

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

> А какая разница динамический или статический ? Дырки то всё равно и там и там будут.

Зато памяти будет выделяться ровно столько, сколько надо.

← →
Alex Konshin (2004-02-17 08:08) [11]

Кстати, а как в Дельфи с хэшами ? Хочу такие же как в перле, чтобы не мучится.
Такие - не такие, но что-то подобное можно изобразить.
Например, на основе TStringKeyAvlTree это можно сделать:
{$APPTYPE CONSOLE} program AvlSample; uses AVLtrees in "AVLtrees.pas"; type TMapNode = class; TMap = class(TStringKeyAVLtree) private function GetItems( Index: String ) : String; procedure SetItems( Index: String; Value: String ); public constructor Create; reintroduce; property Items[Index:String] : String read GetItems write SetItems; default; end; TMapNode = class(TStringKeyAVLtreeNode) private FValue : String; public property Value : String read FValue write FValue; end; constructor TMap.Create; begin inherited Create(TMapNode); end; function TMap.GetItems( Index: String ) : String; var item : TMapNode; begin item := TMapNode(Find(Index)); if item=Nil then Result := "" else Result := item.FValue; end; procedure TMap.SetItems( Index: String; Value: String ); var item : TMapNode; begin item := TMapNode(Get(Index)); item.FValue := Value; end; var map : TMap; begin map := TMap.Create; map["gdfg"] := "rerte"; map["hklh"] := "bnv"; map["erur"] := "ewq"; map["ghkl"] := "jklhjkg"; map["iopio"] := "qqwwertyt"; WriteLn( map["gdfg"] ); end.

У меня ничего не перебирается, а всё по ссылкам.
Я не телепат, твоей задачи не знаю.
Ну а если все по ссылкам, то массив-то зачем?

Как удалить пустоты в большом массиве ? Найти похожие ветки