Поиск нескольких списков для пропущенных записей

Question

У меня есть 3 списка, я сделаю их простыми здесь.

список букв
A
B
С

список номеров
1
2 * * +1010 3

Смешанная
А, 1
А, 2
В, 2
В, 3
С, 1
С, 3

Мне нужно знать, чего не хватает:
А, 3
В, 1
С, 2

Список писем насчитывает около 85 записей
а в списке чисел около 500 записей.

В смешанном списке около 75 000 записей.

Я могу использовать запрос к базе данных (mysql 5.0) или Turbo Delphi 2006 для обработки текстовых файлов. Как лучше всего найти то, чего не хватает?

Спасибо
Dave

Answer 1

Перекрестное объединение будет производить каждую комбинацию, если у вас есть оба списка в таблицах SQL:

SELECT
  Letter + ',' + Number AS Combination
FROM
  NumberList,
  LetterList

Используя объединенный результат (возможно, сохраните его во временной таблице), вы можете использовать запрос NOT EXISTS, чтобы найти то, чего не хватает:

SELECT
  Combination
FROM
  AllCombinations AS a
WHERE
  NOT EXISTS 
  (SELECT 1 FROM MyCombitations AS m WHERE m.Combination = a.Combination)

Для этого потребуется таблица MyCombitations, в которой перечислены все комбинации, которые у вас есть, и вы хотите сравнить их с полным списком.

Если вы хотите ускорить процесс, вы должны использовать постоянную таблицу комбинаций и индекс в поле MyCombitations.Combination. Для повторных запросов это определенно желательно.

Answer 2

Нет необходимости создавать дополнительные таблицы. Следующий запрос будет работать так же хорошо:

SELECT c.chr, n.num
FROM chars c, nums n
 WHERE NOT EXISTS (SELECT 1
                     FROM mix m
                    WHERE m.chr = c.chr AND m.num = n.num)

Answer 3

Если вы можете отсортировать данные ( Turbo powers SysTools имеет хорошую процедуру сортировки, которая работает хорошо), то вы можете сделать это в коде довольно быстро с двумя списками ввода и списком вывода. Концепция этого проста:

1. Взять два списка, отсортированных таким же образом
2. Если левая сторона меньше правой, то на правой стороне отсутствует это значение, поэтому добавьте его в свой «отсутствующий список» и увеличьте курсор на левой стороне.
3. Если они равны, то увеличить оба,
4. Если правая сторона меньше левой, то увеличивается только правая сторона (необязательно, добавьте в список «необходимо удалить»).

Этот процесс иногда называют процессом «Старый мастер / Новый мастер» и очень быстр, поскольку вы ходите по обоим спискам только один раз.

Простой пример:

var
  ListL : tStringList; // the left list
  ListR : tSTringList; // the right list
  ListA : tSTringList; // the Add List (should start empty)
  ListD : tStringList; // the Delete list (should start empty)
  iCurL : integer;     // Left Cursor
  iCurR : integer;     // Right Cursor
  iRes  : integer;     // result of compare
begin
  iCurL := 0;
  iCurR := 0;
  ListL := tStringList.create;
  ListR := tSTringList.create;
  ListA := tSTringList.create;
  ListD := tStringList.create;
  InitAndLoadLists(ListL,ListR,ListA,ListD);
  while (iCurL <= ListL.Count-1) and (iCurR <= ListR.Count-1) do
    begin
      iRes := CompareStr(ListL.Strings[iCurL],ListR.Strings[iCurR]);
      if iRes = 0 then
        begin
          inc(iCurL);
          inc(iCurR);
        end;
      if iRes < 0 then
        begin
          ListA.Add(ListL.Strings[iCurL]);
          inc(iCurL);
        end;
      if iRes > 0 then
        begin
          listD.Add(ListR.Strings[iCurR]);
          inc(iCurR);
        end;
    end;
  while (iCurL <= ListL.Count-1) do
    begin
      listA.Add(ListL.Strings[iCurL]);
      inc(iCurL);
    end;
  while (iCurR <= ListR.Count-1) do
    begin
      listD.Add(ListR.Strings[iCurR]);
      inc(iCurR);
    end;
  ShowMessage( 'ADDS' + ^M+^J + ListA.Text);
  ShowMessage( 'DELS' + ^M+^J + ListD.Text);
end;

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

procedure InitAndLoadLists(ListL, ListR, ListA, ListD: TStringList);
begin
  ListL.Add('A,1');
  ListL.Add('B,3');
  ListL.Add('C,2');
  ListR.Add('A,2');
  ListR.Add('B,3');
  ListR.Add('C,4');
end;

Редактировать: Код протестирован в Delphi 2009 и работает правильно.

Answer 4

SELECT letter,number FROM lettersTable l , numbersTable n WHERE
(
    SELECT count(*) 
    FROM 
        (
            SELECT * 
            FROM combinationsTable 
            WHERE l.letter=combinationsTable.letter AND n.number = combinationsTable .number
        ) AS temp
) = 0;

Это зависит от SELECT * ОТ A, B, проверяющего все комбинации (неявное перекрестное соединение).

Answer 5

75.000 это не много. Загрузите список букв и список чисел в два отдельных TStringLists. Создайте динамический массив (индексы будут индексами в этих двух списках строк) с соответствующими измерениями Заполнить его. Загрузите данные и отметьте каждую строку в массиве. Выведите все элементы, которые не были отмечены.

В псевдокоде (не проверено):

var
  i1, i2: integer;
  sl1, sl2: TStringList;
  cross: array of array of boolean;
begin
  // load data into sl1, sl2
  SetLength(cross, sl1.Count, sl2.Count);
  for i1 := 0 to sl1.Count - 1 do
    for i2 := 0 to sl2.Count - 1 do
      cross[i1, i2] := false;
  // for each element in 'combined' list
    // split it into elements s1, s2
    i1 := sl1.IndexOf(s1);
    i2 := sl2.IndexOf(s2);
    if (i1 < 0) or (i2 < 0) then
      // report error
    else
      cross[i1, i2] := true;
  for i1 := 0 to sl1.Count - 1 do
    for i2 := 0 to sl2.Count - 1 do
      if not cross[i1, i2] then
        // output sl1[i1], sl2[i2]
end;