Ошибка TList и BinarySearch - PullRequest
Новая
       9

Ошибка TList и BinarySearch

3 голосов
/ 27 ноября 2011

У меня возникли проблемы с TList и BinarySearch. У меня есть такая структура: 

  PDoubleEstr = record
    Double: array [1..2] of Integer;
    Count: Integer;
  end;
  TDoubleEstr = TList<PDoubleEstr>;

и объявить: 

var oDoubleEstr: TDoubleEstr;

Затем, я правильно инициализирую список с помощью этой функции: 

procedure Initialize;
var
  iIndex1, iIndex2: Integer;
  rDoubleEstr: PDoubleEstr;
begin
  oDoubleEstr.Clear;
  for iIndex1 := 1 to 89 do
    for iIndex2 := Succ(iIndex1) to 90 do
    begin
      with rDoubleEstr do
      begin
        Double[1] := iIndex1;
        Double[2] := iIndex2;
        Count := 0;
      end;
      oDoubleEstr.Add(rDoubleEstr);
    end;
end;

Теперь я определю эту процедуру: 

procedure Element(const First: Integer; const Second: Integer; var Value: PDoubleEstr);
begin
  with Value do
  begin
    Double[1] := First;
    Double[2] := Second;
  end; 
end;

тогда в моей основной процедуре: 

procedure Main;
var 
  Value: PDoubleEstr;
  Index: Integer;
  flag: boolean;
begin
  Element(89, 90, Value);
  flag := oDoubleEstr.BinarySearch(Value, Index, TDelegatedComparer<PDoubleEstr>.Construct(Compare));
  Writeln(Flag:5, oDoubleEstr[Index].Double[1]:5, oDoubleEstr[Index].Double[2]:5);  
end;

Получается ошибка. В том смысле, что элементы с индексом «Индекс» не соответствуют элементу, который я набрал. Конечно, oDoubleEstr отсортирован правильно, и не понимаю, где я ошибаюсь. Конструкция сравнения так определена: 

function TDouble.Compare(const Left, Right: PDoubleEstr): Integer;
begin
  Result := Sign(Left.Double[1] - Right.Double[2]);
end;

и я думаю, что ошибка в конструкции, но не понимается как ее решить. В общем, я хочу проверить, существует ли элемент, и если существует, получить индекс. В качестве элемента я имею в виду только поле Double в моем случае. Я пытаюсь объяснить лучше, мой список настолько заполнен: 

 1   2    // element 0
 1   3    
......
 1  90    
......
88  89
88  90
89  90    // element 4004

если я установил Элемент как (89,90), то мне следует повернуть меня в качестве индекса значение: 4004 и значение true, если оно найдено, или значение false в противном случае. Спасибо за помощь.

Ответы [ 2 ]

2 голосов
/ 27 ноября 2011

Я не уверен, что вы пытаетесь сделать, но эта функция Compare недопустима.Функция сравнения должна иметь следующее свойство симметрии: 

Compare(a, b) = -Compare(b, a)

Ваша функция не имеет этого свойства, поскольку вы сравниваете Double[1] с Double[2].

Вы также рискуетеошибка диапазона с вычитанием в вашей функции сравнения.Вместо этого я бы использовал операторы < и >.

Я очень неохотно предлагаю, какой должна быть функция сравнения, потому что я не уверен, какой у вас желаемый критерий упорядочения.Если вы хотите лексикографическое сравнение (т. Е. В алфавитном порядке), то сначала сравните значения Double[1] и, если они равны, выполните второе сравнение значений Double[2].

Однако теперь, когда я посмотрелснова в том, как вы строите список, и теперь, когда я вижу, что вы утверждаете, что этот список отсортирован по построению, становится ясно, какой должна быть функция заказа.Примерно так: 

function CompareInt(const Left, Right: Integer): Integer;
begin
  if Left<Right then begin
    Result := -1
  else if Left>Right then
    Result := 1
  else
    Result := 0;
end;

function Compare(const Left, Right: PDoubleEstr): Integer;
begin
  Result := CompareInt(Left.Double[1], Right.Double[1]);
  if Result=0 then
    Result := CompareInt(Left.Double[2], Right.Double[2]);
end;

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

Кроме того, я думаю, что Double - плохое имя переменной, потому что это также фундаментальный тип.Использование PDoubleEstr для именования записи очень запутанно, потому что обычное использование префикса P - для указателя.

1 голос
/ 27 ноября 2011

Да, Дэвид Хефферман прав. Если вы определите свою функцию сравнения следующим образом, она будет работать: 

function Compare(const Left, Right: PDoubleEstr): Integer;
begin
  Result := Sign(Left.Double[1] - Right.Double[1]);
  if Result=0 then
    Result := Sign(Left.Double[2] - Right.Double[2]);
end;

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

...