Suche in mehreren Listen nach fehlenden Einträgen

Question

Ich habe 3 Listen, die ich hier kurz zusammenfassen möchte.

Liste der Buchstaben
A
B
C

Nummernliste
1
2
3

Gemischt
A,1
A,2
B,2
B,3
C,1
C,3

Ich muss wissen, was noch fehlt:
A,3
B,1
C,2

Die Liste der Buchstaben umfasst etwa 85 Einträge
und die Liste der Nummern hat etwa 500 Einträge.

Die gemischte Liste umfasst etwa 75.000 Einträge.

Ich kann entweder eine Datenbankabfrage (mysql 5.0) oder Turbo Delphi 2006 verwenden, um Textdateien zu verarbeiten. Was wäre der beste Weg, um herauszufinden, was fehlt?

Danke,
Dave

Answer 1

Eine Kreuzverknüpfung würde alle möglichen Kombinationen ergeben, da Sie beide Listen in SQL-Tabellen haben:

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

Mit dem kombinierten Ergebnis (eventuell in einer temporären Tabelle speichern) können Sie mit einer NOT EXISTS-Abfrage herausfinden, was fehlt:

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

Dies würde eine Tabelle erfordern MyCombitations die alle Kombinationen auflistet, die Sie tatsächlich haben und die Sie mit der vollständigen Liste abgleichen möchten.

Wenn Sie die Dinge beschleunigen wollen, sollten Sie eine permanente Tabelle mit Kombinationen und einen Index auf der MyCombitations.Combination Feld. Bei wiederholten Abfragen ist dies durchaus ratsam.

Answer 2

Es ist nicht nötig, zusätzliche Tabellen zu erstellen. Die folgende Abfrage würde genauso gut funktionieren:

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

75.000 ist nicht viel. Laden Sie die Liste der Buchstaben und die Liste der Zahlen in zwei separate TStringLists. Erstellen Sie ein dynamisches Array (Indizes wären Indizes in diesen beiden Stringlisten) mit den entsprechenden Abmessungen. Füllen Sie es auf. Laden Sie die Daten und markieren Sie jede Zeile im Array. Geben Sie alle Elemente aus, die nicht markiert wurden.

In Pseudocode (ungetestet):

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;

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;

Dies beruht darauf, dass SELECT * FROM A,B alle Kombinationen testet (implizites Cross-Join).

Answer 5

Wenn Sie die Daten sortieren können ( Turbo versorgt SysTools hat eine gute Sortierroutine, die gut funktioniert), dann können Sie dies in Code ziemlich schnell mit zwei Eingabelisten und einer Ausgabeliste tun. Das Konzept dahinter ist einfach:

1. Man nehme zwei Listen, die auf die gleiche Weise sortiert sind
2. Wenn die linke Seite kleiner als die rechte Seite ist, dann fehlt der rechten Seite dieser Wert, also fügen Sie ihn zu Ihrer "Fehlenden Liste" hinzu und erhöhen Sie den Cursor für die linke Seite.
3. Wenn sie gleich sind, dann werden beide erhöht,
4. Wenn die rechte Seite kleiner als die linke Seite ist, dann wird nur die rechte Seite erhöht (optional zur Liste "muss gelöscht werden" hinzufügen).

Dieser Prozess wird manchmal auch als "Old Master/New Master"-Prozess bezeichnet und ist extrem schnell, da Sie beide Listen nur einmal durchlaufen.

Einfaches Beispiel:

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;

Der folgende Code wurde von mir zum Testen verwendet. Dies ist nur ein Beispiel, aber in einer realen Situation würde ich meine Schlüssel so aufbauen, dass sie richtig sortieren, Zahlen richtig auffüllen und gegebenenfalls Groß- und Kleinschreibung erzwingen. Wenn Sie die Turbo-Power-Sortierroutinen verwenden, können Sie ZWEI Sortierungen anstelle von zwei Listen verwenden, aber der Endeffekt ist derselbe.

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;

Edit : Der Code wurde in Delphi 2009 getestet und verhält sich korrekt.