Блог

Главная - Вопросы по программированию - Интерполяционный поиск

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

#delphi #delphi-xe6

#delphi #delphi-xe6

Вопрос:

Как я могу реализовать поиск интерполяции по генриху в 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.

Комментарии:

1. Ну, так что же не так с этим кодом?

2. Я ничего не знаю об универсальных функциях в Delphi, но, вероятно, лучшим способом будет включить параметр универсальной функции — при условии, что Delphi это разрешает, — который принимает Item , массив и два индекса и возвращает интерполированный индекс. Это заменит вычисление M . Если вы не можете сделать это с помощью универсального параметра, вам придется использовать указатель на функцию.

3. @Gene Функция не является универсальной. Он работает с массивами целых чисел

4. @user3764855 Что означают параметры Index и Count ? Они кажутся ненужными.

5. Использовать low (A) и high (A) нет?

Ответ №1:

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

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

должно быть вне тела while cycle

Комментарии:

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

2. Алгоритм не учитывает дубликаты — просто возвращает первое совпадающее значение — первое, второе, последнее, любой дубликат.

Ответ №2:

Полное рабочее решение. Вероятно, можно оптимизировать дальше. Это работает, даже если есть дубликаты, он просто выведет первый индекс, а также будет работать со строками, если вы используете что-то вроде 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;