Пересечение списка - PullRequest
Новая
       9

Пересечение списка

1 голос
/ 23 мая 2011

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

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)?

Ответы [ 3 ]

3 голосов
/ 23 мая 2011

Вот функция, которая должна делать то, что вы хотите. Я определил 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;
1 голос
/ 24 мая 2011

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

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

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

0 голосов
/ 23 мая 2011

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

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

...