Индексированный массив ?

← →
Secam (2004-12-25 09:27) [0]

У меня возник такой вопрос:
В языках типа PHP и Perl есть такое понятие, как ХЭШ или индексированный массив. Хотелось бы узнать есть ли какой-то изящный механизм реализации таких массивов в Delphi.
Т.е. требуется создать что-то вроде
type Hash_element=Record key: string; value: string; end; Hash=array of Hash_element;
Хочется иметь возможность быстрого доступа к value каждого элемента, зная его key. При этом не перебирать весь массив
каждый раз.
Подскажите, может компонент есть для этого или может какая-нибудь хитрость, как это всё описать по другому.

← →
VMcL © (2004-12-25 09:31) [1]

TStringList
?

← →
Secam (2004-12-25 09:42) [2]

Не похоже ...
TStringList ведь индексируется по номеру. Конечно можно выбрать по значению строки и понять есть ли значение в списке.
Но TStringList не дает возможности задать такие значения:
hash["key1"]:="value1"; hash["key2"]:="value2"; hash["key3"]:="value3"; writeln(hash["key3"]);
Синтакси "абстрактный" но смысл, я думаю, ясен

← →
Secam (2004-12-25 09:52) [3]

В TStrings я нашел
property Names[const Name: string]: string;
property Values[const Name: string]: string;
Мне кажется это что-то близкое, но как этим воспользоваться для решения моей задачи, пока не понятно ...
Поясните пожалуйста.

← →
Sun bittern © (2004-12-25 10:24) [4]

Secam (25.12.04 09:52) [3]

TValueListEditor построен с использованием TStringList.
Гляньте его исходники + F1.

The following example updates the strings in a list box given the strings contained in another list box. If a string in the source list box has the form Name=Value and the destination list box contains a string with the same Name part, the Value part in the destination list box will be replaced by the source’s value.

procedure MergeStrings(Dest, Source: TStrings);

var
I, DI: Integer;
begin
for I := 0 to Source.Count - 1 do
begin
if Pos ("=", Source[I]) > 1 then
begin
DI := Dest.IndexOfName(Source.Names[I]);
if DI > -1 then Dest[DI] := Source[I];
end;
end;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
MergeStrings(ListBox1.Items,ListBox2.Items);
end;

← →
Yuri-7 (2004-12-25 10:49) [5]

Воспользуйся TSortList (http://i-7.webhost.ru/sortlistr.zip)
Там есть функция поиска по ключу.

← →
Secam (2004-12-25 10:51) [6]

Спасибо,
Я посмотрел этот пример в help"е из этого можно сделать всё что-нужно.
Единственное, что, на мой взгляд, это ужасно медленный и ресурсоемкий способ сделать достаточно простую вещь.

Быстрее наверное будет все-таки перебирать 1 массив.
Сделать структуру, которую я оприсал в сообщении [1]
Перебрать все элементы хэша, сравнить с ключем, если ключ совпадает, то по номеру взять значение.
Потому что вызов Pos ("=", Source[I]) это совершенно лишнее действие, и массив перебирается 2 раза первый:
for I := 0 to Source.Count - 1
второй:
IndexOfName(Source.Names[I]);

Поэтому в качестве решения предлагаю всем, кто будет читать эту ветку, сделать класс с 2-мя массивами переменной длины 1й с ключами и 2й с данными, чтобы совпадали индексы этих массивов и сделать метод,
который будет перебирать все ключи, находить индекс совпадения и выдавать значение из массива значений по индексу. По моему это должно гораздо быстрее работать.
Кстати тогда символ "=" не будет особенным и сможет присутствовать в строках ключей и значений. :)

← →
Secam (2004-12-25 11:08) [7]

Да TSortList сильная штука ...

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

Спасибо.

← →
Cobalt © (2004-12-25 13:53) [8]

Недавно как-то наткнулся на упоминание об SDL - Standart Delphi Library, на Коорлевстве Дельфи, кажется.
И там, вроде как, было до кучи всяких таких вещей...

← →
марсианин © (2004-12-26 03:36) [9]

> Быстрее наверное будет все-таки перебирать 1 массив.

еще быстрее находить значение в отсортированном массиве строк..

← →
Просто Джо © (2004-12-26 03:45) [10]

Еще можно попробовать стандартный THashedStringList - работает достаточно быстро.

← →
марсианин © (2004-12-26 04:03) [11]

использовать стандартый компонент не только быстрее, но и правильнее

← →
Shama_n © (2004-12-26 12:39) [12]

Быстрей чем отсортированный массив [9] + бинарный поиск, наверно не будет работать ничего
Правда если значения массива постоянно меняются то придется сильно усложнять алгоритм или одна только сортировка сожрет все процессорное время

← →
Leonid Troyanovsky © (2004-12-26 14:16) [13]

> Shama_n © (26.12.04 12:39) [12]
> Быстрей чем отсортированный массив [9] + бинарный поиск,
> наверно не будет работать ничего
> Правда если значения массива постоянно меняются то придется
> сильно усложнять алгоритм или одна только сортировка сожрет
> все процессорное время

А зачем его каждый раз сортировать?
Достататочно вставлять значения в нужные места.

--
С уважением, LVT.

← →
Shama_n © (2004-12-26 15:23) [14]

А зачем его каждый раз сортировать? Достататочно вставлять значения в нужные места.

Если вставлять сразу в нужное место то придется сдвигать все значения, с большим индексом, на 1. А если там массив на 1000000 записей? Или может еще какой способ есть?

← →
Yuri-7 (2004-12-26 15:34) [15]

Shama_n © (26.12.04 15:23) [14]
См. Yuri-7 (25.12.04 10:49) [5]

← →
Secam (2004-12-26 15:40) [16]

Я в конечном итоге сделалал через 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;
Работает нормально и поиск есть и вставка быстрая.

← →
_Lucky_ (2004-12-26 15:45) [17]

> марсианин © (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 16:05) [18]

TSortList Это по сути Некое дерево судя по исходнику.
Там смысл в том, что можно создать запись с несколькими полями
и одно из полей сделать ключевым.
Составить функцию которая задает критерий сравнения 2х элементов и на выходе дает результат левее/правее/ или совпадает.
А алгоритм поиска там уже реализован. Данные все передаются через указатели. Решение на мой взгляд хорошее.

PS. Для моей задачи таких наворотов можно и не делать, просто меня заинтересовала эта тема.
Спасибо всем.

← →
Yuri-7 (2004-12-26 21:06) [19]

Ключевыми могут быть сколько угодно полей. Что-то у тебя сложная сортировка получилась.
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 23:15) [20]

А если KEY это строка ?

[16] Secam (26.12.04 15:40)
че-то мне кажется, что при (d1_length<i) i указывает на элемент после последнего.

к тому же проверь, все ли првильно будет работать, если сравнивать 2 строки типа "ABC" и "ABCD"

> Вроде бы индексирование и представляет собой упорядоченность
> значений, разве не так?

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

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

← →
_Lucky_ (2004-12-27 13:40) [22]

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

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

по видимому приведенный пример затрагивает поисковые машины, но описан не совсем корректно.

Напишу и я чего-нибудь

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;

F1 - это значит посмотри в справке, я точного синтаксиса не помню, просто помню, что есть такая ф-ция.

Индексированный массив ? Найти похожие ветки