| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Индексированный массив ?
Secam © (2004-12-25 09:27:00)У меня возник такой вопрос:
В языках типа PHP и Perl есть такое понятие, как ХЭШ или индексированный массив. Хотелось бы узнать есть ли какой-то изящный механизм реализации таких массивов в Delphi.
Т.е. требуется создать что-то вроде
type Hash_element=Record
key: string;
value: string;
end;
Hash=array of Hash_element;
Хочется иметь возможность быстрого доступа к value каждого элемента, зная его key. При этом не перебирать весь массив
каждый раз.
Подскажите, может компонент есть для этого или может какая-нибудь хитрость, как это всё описать по другому.
TUser (2004-12-27 13:54:00) [1]F1 - это значит посмотри в справке, я точного синтаксиса не помню, просто помню, что есть такая ф-ция.
TUser (2004-12-27 13:53:00) [2]Напишу и я чего-нибудь
TDelphiHash = class
private
FKeys: THashedStringList;
FValues: TStringList;
FCaseSensitive: boolean;
public
constructor Create;
destructor Destroy; override;
procedure Add(Key, Value: string);
function Get(Key: string; var Value: string): integer;
procedure MakeHash;
property CaseSensetive: booleab read FCaseSensitive write FCaseSensitive;
end;
...
constructor TDelphiHash.Create;
begin
FKeys:=THashedStringList.Create;
FValues:=TStringList.Create;
FCaseSensitive:=false;
end;
destructor Destroy; override;
begin
FKeys.Free; FValues.Free;
end;
procedure Add(Key, Value: string);
var i:integer;
begin
i:=Get(Key,Value);
if i = 0 then begin
FKeys.Add(Key);
FValues.Add(Key);
end else FValues[i]:=Value;
end;
function Get(Key: string; var Value: string): integer;
var f:boolean;
function IsEq(S1, S2: string): boolean;
begin
if FCaseSensitive then
result:=S1=S2
else result:=AnsiCompareString(S1,S2); // F1
end;
begin
result:=0; f:=true;
while f and (result < FKeys.Count) do
if IsEq(FKeys[result],Key) then
f:=false
else
inc (result);
if f then
result:=0
else begin
Value:=FValues[result];
inc (result);
end;
end;
procedure MakeHash;
end;
_Lucky_ (2004-12-27 13:40:00) [3]
> как частный вариант..
> например, массив строк можно не сортировать, а составить
> массив с индексами строк, и этот уже этот массив (из чисел)
> сортировать, переставлять. а вообще, лучше почитай литературку.
и смысл есть массив не сортированных строк и к нему прицеплен сортированный массив индексов, при поиске по строкам скорости не прибавиться.
вообще получается, что индексирован именно массив чисел, а не массив строк.
взять БД там индекс как раз и создается для ускорения поиска а для этого он сортируется, поэтому поиск по индексированным полям всегда намного быстрее.
по видимому приведенный пример затрагивает поисковые машины, но описан не совсем корректно.
марсианин (2004-12-27 00:04:00) [4][16] Secam (26.12.04 15:40)
че-то мне кажется, что при(d1_length<i)i указывает на элемент после последнего.
к тому же проверь, все ли првильно будет работать, если сравнивать 2 строки типа "ABC" и "ABCD"
> Вроде бы индексирование и представляет собой упорядоченность
> значений, разве не так?
как частный вариант..
например, массив строк можно не сортировать, а составить массив с индексами строк, и этот уже этот массив (из чисел) сортировать, переставлять. а вообще, лучше почитай литературку.
короче тут куча вариантов, как это сделать.. ведь не обязательно пихать все данные в массив, есть еще и связанный список, деревья всякие..
Secam (2004-12-26 23:15:00) [5]А если KEY это строка ?
Yuri-7 (2004-12-26 21:06:00) [6]Ключевыми могут быть сколько угодно полей. Что-то у тебя сложная сортировка получилась.
function Sort_str(i1,i2: Pointer): integer;
var
d1,d2: ^THTTP_Header;
begin
d1:=i1; d2:=i2;
if d1^.key > d2^.key then Result:=1
else
if d1^.key < d2^.key then Result:=-1
else Result:=0;
end;
Secam (2004-12-26 16:05:00) [7]TSortList Это по сути Некое дерево судя по исходнику.
Там смысл в том, что можно создать запись с несколькими полями
и одно из полей сделать ключевым.
Составить функцию которая задает критерий сравнения 2х элементов и на выходе дает результат левее/правее/ или совпадает.
А алгоритм поиска там уже реализован. Данные все передаются через указатели. Решение на мой взгляд хорошее.
PS. Для моей задачи таких наворотов можно и не делать, просто меня заинтересовала эта тема.
Спасибо всем.
_Lucky_ (2004-12-26 15:45:00) [8]
> марсианин © (26.12.04 03:36) [9]
>
> > Быстрее наверное будет все-таки перебирать 1 массив.
>
>
> еще быстрее находить значение в отсортированном массиве
> строк..
Вроде бы индексирование и представляет собой упорядоченность значений, разве не так? А вопрос был именно про реализацию индексированного массива.
> Shama_n © (26.12.04 15:23) [14]
> А зачем его каждый раз сортировать?
> Достататочно вставлять значения в нужные места.
>
> Если вставлять сразу в нужное место то придется сдвигать
> все значения, с большим индексом, на 1. А если там массив
> на 1000000 записей? Или может еще какой способ есть?
а вообще имеет смысл делать массив в 1000000? быть может у товарища который задал вопрос, для решения задачи требуется всего лишь 10? Ну конечно как универсальное средств надо реализовать это все так чтобы переделывать не пришлось, поэтому выход 1 динамика.
А для ускорения поиска дерево, даже в бинарном дереве поиск будет идти быстрее чем где-то еще - тут уж в любом случае все перебирать не прийдется, хотя агроритм будет довольно тяжелый в реализации, ну раз уж это кому-то надо, то значит пусть берет и реализует, а для начала лучше задуматься, а нужно ли это вообще? быть может действительно хватит массива в 10 элементов?
возможно предложение с деревом покажеться странным, но обычно пишу на сях а там компонентов нет (CBuilder в расчет не береться).
Secam (2004-12-26 15:40:00) [9]Я в конечном итоге сделалал через TSortList
с такой вот процедурой сортировки:
function Sort_str(i1,i2: Pointer): integer;
var
d1,d2: ^THTTP_Header;
i,d1_length,d2_length:integer;
begin
d1:=i1; d2:=i2;
i:=1;
d1_length:=length(d1^.key);
d2_length:=length(d2^.key);
while ((i<=d1_length) and (i<=d2_length) and (d1^.key[i]=d2^.key[i])) do inc(i);
if ((d1_length<i) or (ord(d1^.key[i]) < ord(d2^.key[i]))) then Result:=-1;
if ((d2_length<i) or (ord(d1^.key[i]) > ord(d2^.key[i]))) then Result:=1;
if ((d1_length<i) and (d2_length<i)) then Result:=0;
end;
А в качестве элемента использовал
THTTP_Header=record
key : string;
value : string;
end;
Работает нормально и поиск есть и вставка быстрая.
Yuri-7 (2004-12-26 15:34:00) [10]Shama_n © (26.12.04 15:23) [14]
См. Yuri-7 (25.12.04 10:49) [5]
Shama_n (2004-12-26 15:23:00) [11]
А зачем его каждый раз сортировать?
Достататочно вставлять значения в нужные места.
Если вставлять сразу в нужное место то придется сдвигать все значения, с большим индексом, на 1. А если там массив на 1000000 записей? Или может еще какой способ есть?
Leonid Troyanovsky (2004-12-26 14:16:00) [12]
> Shama_n © (26.12.04 12:39) [12]
> Быстрей чем отсортированный массив [9] + бинарный поиск,
> наверно не будет работать ничего
> Правда если значения массива постоянно меняются то придется
> сильно усложнять алгоритм или одна только сортировка сожрет
> все процессорное время
А зачем его каждый раз сортировать?
Достататочно вставлять значения в нужные места.
--
С уважением, LVT.
Shama_n (2004-12-26 12:39:00) [13]Быстрей чем отсортированный массив [9] + бинарный поиск, наверно не будет работать ничего
Правда если значения массива постоянно меняются то придется сильно усложнять алгоритм или одна только сортировка сожрет все процессорное время
марсианин (2004-12-26 04:03:00) [14]использовать стандартый компонент не только быстрее, но и правильнее
Просто Джо (2004-12-26 03:45:00) [15]Еще можно попробовать стандартный THashedStringList- работает достаточно быстро.
марсианин (2004-12-26 03:36:00) [16]
> Быстрее наверное будет все-таки перебирать 1 массив.
еще быстрее находить значение в отсортированном массиве строк..
Cobalt (2004-12-25 13:53:00) [17]Недавно как-то наткнулся на упоминание об SDL - Standart Delphi Library, на Коорлевстве Дельфи, кажется.
И там, вроде как, было до кучи всяких таких вещей...
Secam (2004-12-25 11:08:00) [18]Да TSortList сильная штука ...
Не знаю правда, удастся ли искать по текстовому ключу, но надо попробовать.
Спасибо.
Secam (2004-12-25 10:51:00) [19]Спасибо,
Я посмотрел этот пример в help'е из этого можно сделать всё что-нужно.
Единственное, что, на мой взгляд, это ужасно медленный и ресурсоемкий способ сделать достаточно простую вещь.
Быстрее наверное будет все-таки перебирать 1 массив.
Сделать структуру, которую я оприсал в сообщении [1]
Перебрать все элементы хэша, сравнить с ключем, если ключ совпадает, то по номеру взять значение.
Потому что вызов Pos ('=', Source[I]) это совершенно лишнее действие, и массив перебирается 2 раза первый:
for I := 0 to Source.Count - 1
второй:
IndexOfName(Source.Names[I]);
Поэтому в качестве решения предлагаю всем, кто будет читать эту ветку, сделать класс с 2-мя массивами переменной длины 1й с ключами и 2й с данными, чтобы совпадали индексы этих массивов и сделать метод,
который будет перебирать все ключи, находить индекс совпадения и выдавать значение из массива значений по индексу. По моему это должно гораздо быстрее работать.
Кстати тогда символ "=" не будет особенным и сможет присутствовать в строках ключей и значений. :)
Yuri-7 (2004-12-25 10:49:00) [20]Воспользуйся TSortList ( http://i-7.webhost.ru/sortlistr.zip)
Там есть функция поиска по ключу.
| |
Страницы: 