Блог

Я хочу вычислить список «пересечение». Проблема в том:

 L1 = [1, 0, 2, 3, 1 , 3, 0, 5]
L2 = [3, 5]
  

Тогда результатом будет

 L3 = [0, 0, 0, 1, 0, 1, 0, 1]
  

Затем я преобразую этот результат в байт. В этом случае будет 21 в десятичном формате.

Я хочу создать на delphi, и мне нужно, чтобы это делалось эффективно. Есть ли способ решить эту проблему лучше, чем O (m * n)?

Вот функция, которая должна делать то, что вы хотите. Я определил L2 как набор вместо массива, поскольку вы сказали, что все ваши значения будут помещаться в Byte . Его сложность равна O (n); проверка принадлежности к множеству выполняется в постоянное время. Но поскольку результат должен умещаться в байт, длина L1 должна быть ограничена 8, поэтому сложность этой функции на самом деле равна O (1).

 function ArrayMembersInSet(const L1: array of Byte; const L2: set of Byte): Byte;
var
  i: Integer;
  b: Byte;
begin
  Assert(Length(L1) <= 8,
    'List is to long to fit in result');
  Result := 0;
  for i := 0 to High(L1) do begin
    b := L1[i];
    if b in L2 then
      Result := Result or (1 shl (7 - i));
  end;
end;
  

Ответ Роба будет работать для этого конкретного случая. Для более общего случая, когда необходимо сравнить два списка, вы можете сделать это за O (m n) времени, если оба списка отсортированы. (Или O (n log n) время, если вам нужно сначала отсортировать их, но это все равно намного быстрее, чем O (m * n).)

Базовый алгоритм сравнения списков выглядит следующим образом:

 procedure ListCompare(list1, list2: TWhateverList; [Add extra params here]);
var
  i, j: integer;
begin
  i := 0;
  j := 0;
  while (i < list1.Count) and (j < list2.Count) do
  begin
    if list1[i] < list2[j] then
    begin
      //handle this appropriately
      inc(i);
    end
    else if list1[i] > list2[j] then
    begin
      //handle this appropriately
      inc(j);
    end
    else //both elements are equal
    begin
      //handle this appropriately
      inc(i);
      inc(j);
    end;
  end;

  //optional cleanup, if needed:
  while (i < list1.Count) do
  begin
    //handle this appropriately
    inc(i);
  end;
  while (j < list2.Count) do
  begin
    //handle this appropriately
    inc(j);
  end;
end;
  

Это можно настроить для целого ряда задач, включая пересечение списков, изменив места «обрабатывать это соответствующим образом», и гарантированно не будет выполняться больше шагов, чем указано в обоих списках вместе взятых. Для пересечения списков, пусть регистр equals добавит значение к некоторым выводам, а два других ничего не сделают, кроме увеличения количества счетчиков, и вы можете отказаться от необязательной очистки.

Один из способов использования этого алгоритма — превратить дополнительные параметры вверху в указатели на функции и передать в подпрограммы, которые будут обрабатывать соответствующие случаи, или nil, чтобы ничего не делать. (Просто убедитесь, что вы проверяете наличие nil перед их вызовом, если вы идете по этому маршруту!) Таким образом, вам нужно будет написать базовый код только один раз.

Ну, несмотря ни на что, вам нужно будет посетить каждый элемент в каждом списке, сравнивая значения. Вложенный цикл выполнил бы это за O (n ^ 2), и преобразование должно быть просто локальной работой.

РЕДАКТИРОВАТЬ: я заметил, что вы хотите лучшую среду выполнения, чем O (n * m).