Datenbankauswertung (Kombinationshäufigkeit)

BoMbY · 31.07.2006

Hallo,

ich stehe hier vor einem kleinen Problem mit einer Auswertung. Ich werde das Problem im folgenden einmal vereinfacht darstellen:

Wir haben eine Tabelle, in welcher die Komponenten von gefertigten Rechnern stehen, welche in etwa wie folgt aussehen könnte:

Code:

Rechner-Seriennummer; Materialnummer-Komponente;
                      0000001;                              1000001;
                      0000001;                              1000002;
                      0000001;                              1000003;
                      0000001;                              1000004;
                      0000001;                              1000005;
                      0000002;                              1000001;
                      0000002;                              1001002;
                      0000002;                              1002003;
                      0000002;                              1003004;
                      0000002;                              1004005;

Diese Tabelle enthält jetzt aber einige hundertausend Rechner mit jeweils etwa 20-25 Komponenten.

Was ich jetzt haben möchte, ist die Häufigkeit von allen möglichen und eindeutigen Kombinationen von Materialnummern in den einzelnen Rechnern. Also z.B. wie oft wurde das Material '1004005' mit '1000001' verbaut, oder die Materialien '1000001', '1001002', '1002003', '1003004' und '1004005' in Kombination - also wirklich alle Kombinationen ...

Ein Grundsätzlicher Algorithmus ist klar:
1. Ich lese die Komponenten eines Rechners
2. Ich bilde alle möglichen und eindeutigen Kombinationen
3. Ich merke mir diese Kombinationen in meiner Ergebnisstabelle
4. Wieder zu 1 mit dem nächsten Rechner

Das Problem dabei ist aber die beinnahe unendliche Laufzeit, denn wie man sich vorstellen kann, gibt es verdammt viele Mögliche Kombinationen (und man kann viele eigentlich ausschließen weil sie z.B. doppelt sind).

Die Frage ist also: Kennt jemand einen optimierten Ansatz um so eine Auswertung zu beschleunigen, oder muss man die Anzahl der Kombinationen einfach beschränken (also z.B. nur alle Fünfer-Kombinationen?

Dank und Gruß,
BoMbY

Edit: Also um es vieleicht nochmal auf den Punkt zu bringen: Das Problem ist die Ermittlung der möglichen Kombinationen. Der derzeitige Ansatz diese zu bekommen, ist rekursiv, und wie Ihr Euch vorstellen könnt, ist das bei entsprechend vielen Komponenten einfach viel zu tief, als dass das noch ein Rechner mitmachen würde.
.
.
Edit:
Okay, ich habe jetzt mal eine kleine C#-Version von der Methode gebastelt, von der ich denke, dass sie schon ziehmlich optimiert läuft, und keine doppelten (und hoffentlich alle möglichen) Ergebnisse liefern sollte:

PHP:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static string[] data = { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"/*, "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z" */};

        static void Main(string[] args)
        {
            ArrayList res = new ArrayList();
            doit(res);

            foreach (string line in res)
            {
                Console.WriteLine(line);
            }

            Console.WriteLine();
            Console.WriteLine("Count: " + res.Count);
            Console.ReadLine();
        }

        static void next(ArrayList res, string current, int from, int to, int depth, int max_depth)
        {
            for (int i = from; i < to; i++)
            {
                if (depth == max_depth)
                {
                    res.Add(current + data[i]);
                }
                else
                {
                    next(res, current + data[i], i + 1, to, depth + 1, max_depth);
                }
            }
        }

        static void doit(ArrayList res)
        {
            for (int i = 2; i <= data.Length; i++)
            {
                for (int j = 0; j < data.Length; j++)
                {
                    next(res, data[j], j + 1, data.Length, 2, i);
                }
            }
        }
    }
}

Sieht da jemand noch Optimierungspotential?

Datenbankauswertung (Kombinationshäufigkeit)

BoMbY

Grand Admiral Special

Ähnliche Themen