Создание связного списка

← →
polar (2005-09-09 10:40) [0]

Добрый день.
есть такой код:
PCollisionList = ^TCell;
TCollisionList = PCollisionList;

TCell = record
Key, Data: string;
Next: PCollisionList;
end;

THashTable = array of TCollisionList;
TDataList = array of string;

procedure CreateHashTable(aHashSize: longint; var aHashTable: THashTable);
procedure ClearHashTable(var aHashTable: THashTable);
function HashFunction(aKey: string; var aHashTable: THashTable): longint;
procedure HashInsert(aKey, aData: string; var aHashTable: THashTable);
function HashSearch(aKey: string; var aDataList: TDataList; var aHashTable: THashTable): boolean;

procedure CreateHashTable(aHashSize: longint; var aHashTable: THashTable);
begin
try
SetLength(aHashTable, 0);
SetLength(aHashTable, aHashSize);
except on e: Exception do begin
SetLength(aHashTable, 0);
e.Message := "CreateHashTable: " + e.Message;
raise;
end; end;
end;

procedure ClearHashTable(var aHashTable: THashTable);
var tmpI: integer;
begin
try
for tmpI := 0 to Length(aHashTable)-1 do begin
if assigned(aHashTable[tmpI]) then begin
Dispose(aHashTable[tmpI]);
end;
end;
SetLength(aHashTable, 0);
except on e: Exception do begin
SetLength(aHashTable, 0);
e.Message := "ClearHashTable: " + e.Message;
raise;
end; end;
end;

function HashFunction(aKey: string; var aHashTable: THashTable): longint;
var tmpI: integer;
begin
try
result := 0;
for tmpI := 1 to Length(aKey) do result := result + Integer(aKey[tmpI]);
result := result mod Length(aHashTable);
except on e: Exception do begin
e.Message := "HashFunction: " + e.Message;
raise;
end; end;
end;

procedure HashInsert(aKey, aData: string; var aHashTable: THashTable);
var tmpIndex: longint;
tmpPCollisionList: PCollisionList;
begin
tmpIndex := HashFunction(aKey, aHashTable);
New(tmpPCollisionList);
try
tmpPCollisionList^.Key := aKey;
tmpPCollisionList^.Data := aData;
tmpPCollisionList^.Next := aHashTable[tmpIndex];
aHashTable[tmpIndex] := tmpPCollisionList;
except on e: Exception do begin
Dispose(tmpPCollisionList);
e.Message := "HashFunction: " + e.Message;
raise;
end; end;
end;

function HashSearch(aKey: string; var aDataList: TDataList; var aHashTable: THashTable): boolean;
var tmpPCollisionList: PCollisionList;
tmpExpectedIndex: longint;
begin
tmpExpectedIndex := HashFunction(aKey, aHashTable);
tmpPCollisionList := aHashTable[tmpExpectedIndex];
SetLength(aDataList, 0);
result := false;

while (tmpPCollisionList <> nil) do begin
if tmpPCollisionList^.Key = aKey then begin
result := true;
SetLength(aDataList, Length(aDataList) + 1);
aDataList[High(aDataList)] := tmpPCollisionList^.Data;
end;
tmpPCollisionList := tmpPCollisionList^.Next;
end
end;

При этом всё хорошо, но процедура ClearHashTable не чистит память. Не понимаю почему.
Спасибо, если кто-то откликнется.

← →
Digitman © (2005-09-09 11:10) [1]

как думаешь - отладчик встроенный зачем существует в Делфи ?

← →
polar (2005-09-09 11:24) [2]

Дело не использовании отладчика. Я что-то не освобождаю в ClearHashTable. Не вижу что. В отладчике этого не видно.

← →
Digitman © (2005-09-09 11:27) [3]

> polar (09.09.05 11:24) [2]

> Дело не использовании отладчика

как раз в нем и дело

> В отладчике этого не видно

а что там, в отладчике, тебе вообще видно ?

на то и отладчик, чтобы видеть все что можно видеть в ран-тайм вообще

← →
Dilmo (2005-09-09 11:39) [4]

1. Вообще не понятен смысл типа TCollisionList
2. На мой взгляд память не будет очищаться полностью
но частично будет. Поясню

Когда исполняется вот этот кусок кода
if assigned(aHashTable[tmpI]) then begin
Dispose(aHashTable[tmpI]);
end;
У тебя убивается указатель только на 1 запись то есть тот, который на данный момент хранится в массиве, все остальные записи имеющие одниковое значение Хэш функции остаются в памяти
При достаточно большом значении HashSize относительно кол-ва элементов данных, кол-во коллизий будет близко к 0 и поэтому память будет очищаться нормально, в противном случае, чем больше коллизий, тем больше неочищенной памяти, надеюсь понятно объяснил

← →
Dilmo (2005-09-09 11:47) [5]

И еще я бы советовал тебе в связанном списке проверять уникальность ключа, а то может все запутаться

← →
polar (2005-09-09 11:49) [6]

Тогда как убить указатель на все записи?

← →
Dilmo (2005-09-09 12:12) [7]

procedure KillList(startValue: PCollisionList);
var
currentItem: PCollisionList;
nextItem: PCollisionList;
begin
currentItem := startValue;
nextItem := startValue.Next;
while nextItem <> nil do begin
Dispose(currentItem);
currentItem := nextItem;
nextItem := currentItem.Next;
end;
Dispose(currentItem);
end;

procedure ClearHashTable(var aHashTable: THashTable);
var
tmpI: integer;
begin
try
for tmpI := 0 to Length(aHashTable)-1 do begin
if assigned(aHashTable[tmpI]) then begin
KillList(aHashTable[tmpI]);
end;
end;
SetLength(aHashTable, 0);
except on e: Exception do begin
SetLength(aHashTable, 0);
e.Message := "ClearHashTable: " + e.Message;
raise;
end; end;
end;

Примерно так..думаю должно работать

← →
polar (2005-09-09 12:20) [8]

Спасибо.

← →
polar (2005-09-09 12:27) [9]

Прошу прощения за занудство.
Как видно этот алгоритм работает, когда заранее известен размер таблицы. Вы не знаете способа для динамической таблицы?

Заранее спасибо.

← →
Dilmo (2005-09-09 12:48) [10]

Динамической Хэш таблицы ?

← →
Dilmo (2005-09-09 12:49) [11]

чтото не совсем я тебя понял, размер какой таблицы тебе известен ?

← →
polar (2005-09-09 13:03) [12]

> Динамической Хэш таблицы ?

Да

← →
Dilmo (2005-09-09 13:12) [13]

Вопрос напрашивается.. ты эти процедуры откуда взял, из книжки ?
Если из книжки, то почему не разобрался как это все работает.

Подозреваю что под заранее известным размером
размером Хэш таблицы ты имеешь в виду что при создании этой таблицы ты указываешь ей размер.

И еще 2 вопроса:
1. Зачем ты используешь ХЭШ
2. Зачем тебе динамическая таблица

Чего ты вообще хочешь добиться ?

← →
polar (2005-09-09 13:17) [14]

Задача состоит в следующем:
— организовать связный список для хранения большого числа (порядка 10000 — 50000) записей, объект списка имеет несколько полей разного типа. От DataSet пришлось отказаться по причине его малой скорости.
— реализовать наиболее быстрый поиск по этому списку (равенство записей по нескольким полям).

← →
Dilmo (2005-09-09 13:32) [15]

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

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

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

← →
polar (2005-09-09 13:39) [16]

динамическая таблица для того, что заранее известно только примерное кол-во записей. Здесь важно и память экономить и скорость увеличить

← →
polar (2005-09-09 13:42) [17]

Вообще, ситуация такая:

есть grid на форме, в зависимости от выбранного режима grid должен перестраиваться, поэтому есть параллельный полный список данных, на основе которого происходит перестраивание. Таких grid"ов 3 на форме и если записей более 1000 получается медленно.

← →
Dilmo (2005-09-09 13:44) [18]

хм...досконально не знаю как там у вас все устроено, поэтому предложу пару вариантов, может что подойдет

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

вариант2: если 1й не проходит, то тогда можно конечно и динамическую длину сделать, но в таком случае тебе придется вот эту процедуру переделать

function HashFunction(aKey: string; var aHashTable: THashTable): longint;
var tmpI: integer;
begin
try
result := 0;
for tmpI := 1 to Length(aKey) do result := result + Integer(aKey[tmpI]);
result := result mod Length(aHashTable);
except on e: Exception do begin
e.Message := "HashFunction: " + e.Message;
raise;
end; end;
end;

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

← →
polar (2005-09-09 13:48) [19]

согласен. Ищу алгоритмы таких функций. Если есть какие-то ссылки, буду благодарен.

← →
Dilmo (2005-09-09 13:56) [20]

врядли чего то стоящее найдешь, потому что разработка таких функций очень сильно зависит от области применения.. то есть от твоей конкретной задачи и данных которые в этой задаче вертятся, я бы тебе советовал использовать таблицу с заранее заданным размером.. сам посчитай...
4 байта для Win32 занимает 1 указатель
Таблица размером 100000 записей будет занимать 400кб в памяти, не так уж и много для нынешних компов...

← →
Dilmo (2005-09-09 13:57) [21]

можно даже уменьшить размер в 2 раза не думаю что по скорости много проиграешь

← →
polar (2005-09-09 14:01) [22]

Спасибо за дельные советы.

Создание связного списка Найти похожие ветки