Brauch nen kleinen Denkanstoß für Performance

Pretty

@Wutz:
Danke - 50000% Performancegewinn ist für den Anfang ganz prima die comparison-Funktion war zwar für mich etwas knifflig, aber läuft hervorragend.

Wutz

Ja super.
War irgendwie auch zu erwarten. Für deine gezeigte Aufgabenstellung reichen C89 Mittel nebst Dateipersistenz aus, du bleibst dabei immer portabel und bindest dich nicht an irgendwelche Bibliotheken.
Ich hoffe auch, dass du dann auch die Daten sortiert abspeicherst, qsort also nur nach einem insert/update/delete aufrufst und sonst nur noch bsearch verwendest.
Die Struktur selbst sollte auch keine Zeiger sondern die Daten direkt enthalten.

knivil

Pretty schrieb:

@Wutz:
Danke - 50000% Performancegewinn ist für den Anfang ganz prima die comparison-Funktion war zwar für mich etwas knifflig, aber läuft hervorragend.

Wenn man zum Vergleichen Muell nimmt, dann sind "big numbers" ja immer toll.

@wutz: Super gelöst und schön dass mal nicht gleich eine fette Datenbank, Framework, Engine, HA, Cluster etc. gebraucht wird, um mal 30000 Daten zu filtern. Is ja echt nicht wahr, dass einige hier für so etwas eine Datenbank nutzen müssen.

Pretty

Ähnliche Situation, deshalb hier weiter...
Vorweg: Datenbank ist im Moment keine Alternative.
Ich gebe mir dann doch nochmal die Blöße und frage blöd:

Ich habe natürlich diverseste andere Daten in dem Progrämmchen in allen denkbaren Formen.
Bei einer Liste ist meine Suchfunktion noch sehr unperformant.
Dabei sind die Einträge in diesem Strukturarray sortiert nach einem Datumsfeld.
Dieses Feld ist an dieser Stelle nicht für die Suche von Bedeutung, die Sortierung ergibt sich durch Appenden in der "Sammeldatei" / Quelldatei und bsearch ohne passende Sortierung macht ja nicht viel Sinn. Ich vermute einfach mal, dass Hin- und Hersortieren, nur um bsearch verwenden zu können, auch nicht zu intelligent wäre, oder? Soll ich mir eventuell Indizes aufbauen, die ich dann bei jeder Datenänderung aktualisiere?

Wer nichts konstruktives beitragen möchte, möge sich bitte seiner Meinung enthalten.

Wutz

bsearch ohne voriges qsort ist natürlich sinnfrei.

Schreibe dir eine Suche-Funktion, die zunächst mal immer erst qsort und dann bsearch aufruft (haben sinnigerweise ja die gleiche cmp-Funktion) und probiere es aus.
Bei 30000 Datensätzen sollte auch ein vorheriges qsort jeweils nicht viel langsamer werden. Evtl. kannst du dir noch ein Flag gönnen, das die letzte Sortierung speichert und somit beim Funktionsaufruf evtl. 1x qsort spart.

Pretty

Werde ich mal basteln, danke.

Allerdings brauche ich für die Sortierung logischerweise nur Attribute des jeweiligen structs und die Suche macht aktuell Quervergleiche zwischen verschiedenen Datenstrukturen. Oder soll ich dann zur Suche eine entsprechende Suchstruktur befüllen und die verwenden, damit die compare-Funktion für beides geht?

Wutz

Schreibe dir für jede deiner Strukturlisten eine eigene Suchfunktion.
Daten zu kopieren nur um darin zu suchen ist aufwändiger und fehleranfälliger.

Pretty

struct A {
   char a[5];
   char b[5];
   char c[5];
   char y[5];
} sA[99999];
struct B {
   char d[5];
   char b[5];
   char c[5];
} sB[99999];

^ beispielhafte Darstellung...
Ich meinte, dass ich eine bisher noch nicht sortierte Liste sA anhand der gemeinsamen Attribute mit sB nach etwaigen Treffern durchsuchen möchte.
Eine Vergleichsfunktion zum Sortieren von sA nach b, c und y wird mir also zum Suchen von Übereinstimmungen zwischen sA und sB in den Attributen b und c nicht so ohne Weiteres helfen, richtig?
Allerdings wird mir auch die Vergleichsfunktion für die Sortierung von sB (nach c, b und d) keine besseren Dienste leisten, oder?
Ich hätte mir nun einen Zeiger auf ein such-Struct à la sA mit den Suchwerten b und c befüllt und anhand dessen bsearch losgetreten. Keine tolle Idee?

Wutz

Ich habe nicht verstanden, was du meinst.
Woher du die Suchwerte für Liste A herbekommst, also aus Liste B oder sonstwo her, sollte egal sein.

Pretty

struct A {
   char kz[5];
   char firma[5];
   char person[5];
   char datum[5];
} sVorgaenge[99999];   // komplette historie, nur inserts
struct B {
   char firma[5];
   char person[5];
   char blabla[5];
   ...
} sHeutigerTag[99999];   // daraus wird sVorgaenge befuellt

Kurz etwas abstrahierter:
Das Schließsystem des Hochhauses protokolliert 24 Stunden lang in die Liste sHeutigerTag, wer das Gebäude betritt oder verlässt.
Wenn eine Person vorgestern ins Haus und bisher nicht mehr raus ist, wird diese Person seit vorgestern täglich in dieser Liste auftauchen.
Die EDV verarbeitet jeden Morgen die gestrigen Vorgänge und zusammen mit den vergangenen Daten in sVorgaenge ergibt sich gegebenenfalls bezogen auf die Firma, deren Untermenge eine Person immer ist, ein Zuwachs, Verlassen oder ein Erstbetritt des Hauses.
Wenn Person irgendwer (z.B. 7777) aus der Firma kkkk bereits im Gebäude ist und deren Angestellter 5555 kommt hinzu, ergibt sich in sVorgaenge ein entsprechender Satz mit einem Zuwachs für kkkk durch 5555 und dem gestrigen Datum.
Laut sVorgaenge sei Angestellter 7777 ja bereits im Haus, wird aber in sHeutigerTag nicht gefunden. Daraus folgt für heute ein Verlassen-Eintrag für 7777 & kkkk & heute in sVorgaenge.

Die folgenden Schleifen und Suchvorgänge sind haarsträubend und zum Teil redundant. Ich habe mich gerade entschieden, alles etwas zu entwirren. Mal sehen, welchen Ärger mir das dann einbringt... Danke auf jeden Fall für die Unterstützung