Интерполяционный поиск

Как я могу реализовать общий интерполяционный поиск в Delphi? Я пытался перенести его из Википедии. Однако он возвращает неправильный результат.

function Search(var A: TArray<Integer>; const Index, Count, Item: Integer): Integer;
var
  L, H, M: Integer;
begin
  L := Index;
  H := Count;
  Result := -1;
  while (A[L] <= Item) and (A[H] >= Item)  do
  begin
    M := L + ((Item - A[L]) * (H - L)) div (A[H] - A[L]);
    if A[M] < Item then
      L := M + 1
    else if A[M] > Item then
      H := M - 1
    else
      Exit(M);

    if A[L] = Item then
      Exit(L)
    else
      Exit(-1);
  end;
end;

var
  A: TArray<Integer>;
  I: Integer;
begin
  A := TArray<Integer>.Create(1, 2, 3, 4, 5, 7, 7, 7, 7);
  I := Search(A, 0, High(A), 5); // Returns -1;
  ReadLn;
end.

delphi delphi-xe6
person user3764855    schedule 06.07.2014    source источник
comment
Так что же не так с этим кодом?   -  person TLama    schedule 06.07.2014
comment
Я ничего не знаю о дженериках в Delphi, но лучший способ, вероятно, включить параметр универсальной функции - при условии, что Delphi это позволяет - который принимает Item, массив и два индекса и возвращает интерполированный индекс. Это заменит вычисление M. Если вы не можете сделать это с помощью универсального параметра, вам придется использовать указатель на функцию.   -  person Gene    schedule 06.07.2014
comment
@Gene Функция не является универсальной. Работает с массивами целых чисел.   -  person David Heffernan    schedule 06.07.2014
comment
@ user3764855 Что означают параметры Index и Count? Они кажутся ненужными.   -  person David Heffernan    schedule 06.07.2014
comment
Использовать низкий (A) и высокий (A) нет?   -  person David Heffernan    schedule 06.07.2014
comment
Вы спросили, как сделать общую функцию. Я говорю вам сделать его общим, включив общий параметр функции, который выполняет интерполяцию. Некоторые языки (например, Ада) позволят вам это сделать. Я не знаю, будет ли Delphi.   -  person Gene    schedule 06.07.2014
comment
@Джин, я понимаю тебя. Мой ответ на один из недавних вопросов спрашивающего показывает, как сделать это общим способом. Возможно, спрашивающему просто нужно снова прочитать этот ответ.   -  person David Heffernan    schedule 06.07.2014
comment
В любом случае, сделать его универсальным сложно. Алгоритм не имеет большого смысла вдали от реальной линии.   -  person David Heffernan    schedule 06.07.2014
comment
Алгоритм подходит для значений на реальной линии   -  person David Heffernan    schedule 07.07.2014
comment
На самом деле не сложно написать этот материал. Однако это будет не намного быстрее, чем деление пополам.   -  person David Heffernan    schedule 07.07.2014
comment
@DavidHeffernan Я понял это. Красивое решение.   -  person user3764855    schedule 07.07.2014

Ответы (2)


arrow_upward
4
arrow_downward

Этот фрагмент кода:

  if A[L] = Item then
      Exit(L)
    else
      Exit(-1);

должен быть вне тела цикла while

person MBo    schedule 06.07.2014
comment
Кажется, что алгоритм возвращает первый, если нет дубликатов, и последний, если есть дубликаты. - person user3764855; 06.07.2014
comment
Алгоритм не учитывает дубликаты - просто возвращает первое совпадающее значение - первое, второе, последнее, любой дубликат. - person MBo; 06.07.2014

arrow_upward
0
arrow_downward

Полноценное рабочее решение. Может наверное оптимизировать дальше. Он работает, даже если есть дубликаты, он просто выведет первый индекс, а также будет работать со строками, если вы используете что-то вроде LevenshteinDistance.

type
    TCompare<T> = reference to function(const L, R: T): Integer;
    TArrayManager<T> = record
        class function InterpolationSearch(var A: TArray<T>; const Index, Count: Integer; const Item: T; const Distance, Compare: TCompare<T>): Integer; static;
    end;

class function TArrayManager<T>.InterpolationSearch(var A: TArray<T>; const Index, Count: Integer; const Item: T; const Distance, Compare: TCompare<T>): Integer;
var
  L, H, M, C: integer;
begin
  L := Index;
  H := Count;
  Result := -1;
  while L <= H do
  begin
    if L = H then
      M := L
    else
    begin
      M := L + (Distance(Item, A[L]) * (H - L)) div Distance(A[H], A[L]);
      if M < L then
        M := L
      else if M > H then
        M := H;
    end;
    C := Compare(A[M], Item);
    if C < 0 then
      L := M + 1
    else
    begin
      H := M - 1;
      if C = 0 then
      Result := M;
    end;
  end;
end;
person user3764855    schedule 07.07.2014