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

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

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

Создание связного списка [D7, Win2k]

Страницы: 1 2 >
polar © (2005-09-09 10:40:00)
Добрый день.
есть такой код:
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 не чистит память. Не понимаю почему.
Спасибо, если кто-то откликнется.

polar (2005-09-09 14:01:00) [1]
Спасибо за дельные советы.

Dilmo (2005-09-09 13:57:00) [2]
можно даже уменьшить размер в 2 раза не думаю что по скорости много проиграешь

Dilmo (2005-09-09 13:56:00) [3]
врядли чего то стоящее найдешь, потому что разработка таких функций очень сильно зависит от области применения.. то есть от твоей конкретной задачи и данных которые в этой задаче вертятся, я бы тебе советовал использовать таблицу с заранее заданным размером.. сам посчитай...
4 байта для Win32 занимает 1 указатель
Таблица размером 100000 записей будет занимать 400кб в памяти, не так уж и много для нынешних компов...

polar (2005-09-09 13:48:00) [4]
согласен. Ищу алгоритмы таких функций. Если есть какие-то ссылки, буду благодарен.

Dilmo (2005-09-09 13:44:00) [5]
хм...досконально не знаю как там у вас все устроено, поэтому предложу пару вариантов, может что подойдет

вариант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:42:00) [6]
Вообще, ситуация такая:

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

polar (2005-09-09 13:39:00) [7]
динамическая таблица для того, что заранее известно только примерное кол-во записей. Здесь важно и память экономить и скорость увеличить

Dilmo (2005-09-09 13:32:00) [8]
В общем перво-наперво необходимо определить что важнее, скорость или память
Если важнее скорость то теория советует размер хэш таблицы делать раза в 2 больше чем размер предполагаемого массива данных, в данном случае размер д.б порядка 100000, взяв такой размер ты уменьшаешь вероятность коллизий но при построении ключа нужно учесть каков размер твоей таблицы чтобы возможные значения по возможности равномерно "размазывались" по всей хэш таблицы, в твоем случае простое суммирование кодов символом может и не хватить если строки короткие, большая часть будет в начале таблицы а в конце почти ничего... в общем прикидывать надо
соотвественно и память отожрется под 100000 записей....

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

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

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

Dilmo (2005-09-09 13:12:00) [10]
Вопрос напрашивается.. ты эти процедуры откуда взял, из книжки ?
Если из книжки, то почему не разобрался как это все работает.

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

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

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

polar (2005-09-09 13:03:00) [11]
> Динамической Хэш таблицы ?

Да

Dilmo (2005-09-09 12:49:00) [12]
чтото не совсем я тебя понял, размер какой таблицы тебе известен ?

Dilmo (2005-09-09 12:48:00) [13]
Динамической Хэш таблицы ?

polar (2005-09-09 12:27:00) [14]
Прошу прощения за занудство.
Как видно этот алгоритм работает, когда заранее известен размер таблицы. Вы не знаете способа для динамической таблицы?

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

polar (2005-09-09 12:20:00) [15]
Спасибо.

Dilmo (2005-09-09 12:12:00) [16]
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 11:49:00) [17]
Тогда как убить указатель на все записи?

Dilmo (2005-09-09 11:47:00) [18]
И еще я бы советовал тебе в связанном списке проверять уникальность ключа, а то может все запутаться

Dilmo (2005-09-09 11:39:00) [19]
1. Вообще не понятен смысл типа TCollisionList
2. На мой взгляд память не будет очищаться полностью
но частично будет. Поясню

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

Digitman (2005-09-09 11:27:00) [20]

> polar (09.09.05 11:24) [2]

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

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

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

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

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

Страницы: 1 2 >

Наверх

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