C++ Suche kleinere Datentypen

Das erstemal 12Uhr war es nach 43.200s und die 12. Stunde des Tages war es 3.600s lang bei einer Tageslänge von 86.400s.

Entsprechend:
( Zeitwert - 43.200 ) % 86.400s = x
Wobei x <= 3600 / 86400 geprüft werden müsste um herauszubekommen, ob die Zeit im Bereich 12:00:00 - 12:59:59 liegt.

Probleme die auftreten sind, dass wenn du wirklich alles in Unixtime überführst Schaltsekunden beachten musst. Deswegen klappt diese einfache Lösung auch nicht mit der Unixtime der aktuellen Zeit. An der Stelle lohnt aber sicher ein Blick in die Doku der time.h oder du baust dir eine eigene Lösung die nach dem Prinzip der Unixtime funktioniert aber Schaltsekunden ignoriert (ich gehe davon aus, dass deine Datensätze keine Schaltsekunden gesondert aufzeigen), oder du suchst etwas im Netz, da das Problem sicher schon Andere vor dir hatten.

Weiterhin unschön ist bei diesem fixem Hack, dass x ein Float sein müsste, anstatt das man die ganze Zeit nur schön mit Integern rechnet. Das ist dann eine Optimierungsaufgabe das ganze derart elegant zu gestalten, dass nur Integer herausfallen.

Edit: BOAR Leute, ihr seid zu schnell

-> 20:14:25


So hätte man die Rechnungen ohne Floats.

Aber wieso müsste x denn ein Float sein?
Edit: klar.. 3600 / 86400 ist < 1

Edit²:
( Zeitwert - 43.200 ) % 86.400s = x

Da wird x doch niemals ein float sein?

Edit³:
Ich weiß nicht wieso ich Bit-Operatoren genutzt habe. Piktogramm hat mich mit seinem Float und seiner Rechnung ganz verwirrt. Einfach "normale" Division nehmen, der Compiler macht das beste daraus:

Ach verflixt, eigentlich sollte da statt dem Modulooperator ein Divisionsoperator stehen, damit der TE seinen Kopf selber anstrengen muss. Verflixt!
Als Division wäre wäre x nur als float sinnvoll. Naja wenigsten muss der TE jetzt nachdenken, damit der den Vergleich richtig hinbekommt, da mit dem Modulo der Check auf 3600/86400 nicht mehr klappt.

Diese ganze Diskussion um einen kleineren Zeit-Datentyp ist der falsche weg!
Wenn du sagst du erstellst StatistikEN (Plural!) dann gehe ich mal ganz stark davon aus, dass du deine Datenmenge insgesamt mehr als einmal komplett durchläufst - und das ist ein großer Fehler. Außerdem ist es sicherlich falsch, wenn du dich für Temperaturen interessierst die Daten aber nach Datum sortierst behandelst.
Gib uns mal bitte konkrete Beispiele wie deine Anfragen (=Statistiken) aussehen sollen. Außerdem wäre eine grobe Zahl interessant für uns wie viele Zeitpunkte du Temperaturen hast und am besten natürlich auch ein Ausschnitt wie die Daten aussehen.
Willst du zB Fragen "Wie oft war es unter 12° Grad" und später auch "Wie oft war es über 20 Grad?"?
Dann wäre es zB ein riesen Fortschritt wenn du die Daten nicht nach Datum sondern nach Temperatur sortierst. Sortieren ist fast gleichschnell zu durchlaufen (O(N*log(N)( statt O(N)) aber anschließend ist es nur noch eine O(log(N)) Aufgabe (klick) die beiden Fragen oben zu beantworten da sie nach Temperatur sortiert sind. Bei einer Sortierung nach Datum brauchst du jedes mal O(N) für jede deiner Statistiken.
Spricht etwas dagegen die zeitliche Auflösung deiner Daten zu verringern? Temperatur schwankt ja nicht im Minuten-Takt bzw evtl ist es für deine Auswertung egal? Evtl reicht dir ja eine 'Tages-Durchschnittstemperatur'? Dann könnntest du nämlich VOR der ganzen Analyse erstmal eine drastische Daten-Reduktion durchführen und zB jedem Tag nur noch eine einzige Temperatur zuordnen. Hierfür dann ne Funktion "bildeDurchschnittsTempFürTag" die zB Uhrzeit 10-16 Uhr betrachtet oder ähnliches. Folgende Analysen arbeiten dann nur noch mit der einen Grad-Zahl statt jedesmal einen riesen Datenhaufen mit 1000 Werten pro Tag anzugucken.

Außerdem kann es sehr wohl sinnvoll sein mit Linux time (uint32) zu arbeiten, wenn dir die Auflösung und der Wertebereich ausreicht. Wenn du nämlich einmalig bei irgend einer Statistik-Anfrage einen Zeitraum im Format YYYY-MM-DD angibst für die etwas ermittelt werden soll musst du natürlich nicht ständig jedes Datum im Datensatz von Typ her konvertieren - du könntest stattdessen auch die beiden Termine der Anfrage nach Linuxtime bringen und deine Software auf Basis von uint32 arbeiten lassen.

@kuddlmuddl
In einem anderem Thread wurde dem TE schon um die Ohren gehauen, dass sein Problem so klingt, als könnte man es mit Datenbanken sehr bequem erschlagen

@kuddlmuddl
Wenn er tatsächlich nur ein paar Statistiken durchführen will, dann kann man sie auch beim einmaligen Durchlaufen durch das Array aufstellen und hat so insgesamt nur O(n), was bei großen Datenmengen doch deutlich schneller ist als O(nlogn).

Ansonsten ist es schwierig sich hier weiter Gedanken zu machen, wenn man keine genaueren Informationen hat. Aber das Entpacken der Daten wird wohl absolut null ins Gewicht fallen. Entweder man ist hier Memory-Bound oder es werden noch andere Berechnungen angestellt, von denen hier nicht berichtet wird.

Piktogramm schrieb:

Naja wenigsten muss der TE jetzt nachdenken

Zum Vergrößern anklicken....

Hehe das kann ich sowieso versprechen Ich hab ja erst vor einigen Jahren angefangen mit dem Coden und hab Studiums/Berufsmäßig nie damit zu tun gehabt daher sind so manche Dinge, wie auch Modulo ziemlich faszinierend, ich verstehe rechnerisch wie es funktioniert aber warum es eigentlich funktioniert... naja gut ich bleibe dran, bin immer motiviert Definitiv aber eine schöne Alternative zu struct tm (ich gehe mal davon aus auch schneller, das teste ich noch) und wenn es nur Abweichungen von Schaltsekunden sind, das wäre gar nicht schlimm. Und per Unixzeit wären auch 4 Byte zu machen, sehr schön.

@kuddlmuddl
Daten nach Zeit sortiert und auch mehrfache Durchläufe haben dann schon einen Sinn, zumindest langfristig wird es eine Rolle spielen. Mein Projekt hat mit Thermodynamik und Bauphysik zu tun, das Simulieren nach Zeit (nach Datum sortiert) ist nötig da so auch Phasenverschobene Effekte berücksichtigt werden die nach dem input Sonne kw/m² zeitlich versetzt auftreten können. Eine Auflösung von mind. ca 20 Sekunden ist teilweise schon wichtig (natürlich je nach Usecase zB wenn die Speichermasse sehr gering ist). Die Phasenverschiebung, beeinflusst durch die Speicherkapazität von Elementen soll später neben anderen Parametern auch ausgewertet werden. Im Prinzip kann ich noch gar nicht genau sagen was alles genau ausgewertet wird da die Methodologie sich durch laufende Tests und Ergebnisse auch immer weiterentwickelt. Auf jeden Fall werden noch viele verschiedene Dinge dazu kommen und auch wieder wegfallen. Parallel laufen auch Tests unter Realbedingungen und ich schaue wie gut es korreliert. Wenn die Grundlagensachen gemacht sind kann ich dann auch an Optimierungsdurchläufe denken was ein mehrfaches Durchlaufen mit sich verändernden Parametern bedeutet. Multithreading nicht ausgeschlossen. Das wäre dann ähnlich wie "parametrisches Entwerfen" nur eher spezialisiert auf Physik statt auf geometrische Spielereien. Daher will ich von vornherein alle Datentypen möglichst klein halten und möglichst wenig Performancebremsen.

daemon777 schrieb:

@kuddlmuddl
Wenn er tatsächlich nur ein paar Statistiken durchführen will, dann kann man sie auch beim einmaligen Durchlaufen durch das Array aufstellen und hat so insgesamt nur O(n), was bei großen Datenmengen doch deutlich schneller ist als O(nlogn).
Ansonsten ist es schwierig sich hier weiter Gedanken zu machen, wenn man keine genaueren Informationen hat. Aber das Entpacken der Daten wird wohl absolut null ins Gewicht fallen. Entweder man ist hier Memory-Bound oder es werden noch andere Berechnungen angestellt, von denen hier nicht berichtet wird.

Zum Vergrößern anklicken....

Ja habe mich für Memory-Bound also das komplette Laden in den RAM entschieden (wie es mir überzeugenderweise im anderen Thread geraten wurde), mir ist dann die Performance schon wichtiger und RAM ist inzwischen bezahlbar.

Optimiere dann wenn es notwendig ist, an den Stellen welche nach Messungen(!!!) der Flaschenhals sind und nicht vorher!
Das bisschen was du an RAM für den Datentyp sparen könntest wirst du die mit hoher Wahrscheinlichkeit durch ineffiziente Algorithmen wieder zunichte machen. Du wirst also viel Aufwand für im besten Falle den gleichen Verbrauch/Performance wie mit den Standard Typen erhalten.

@Fonce:
Du bist viel zu spät, das Thema ist durch


@T_55
Du kannst beruhigt sein, solche Sachen wie das Nutzen eines konsistenten Datenformats innerhalb eines Programms wurde bei mir an der Uni nicht gelehrt und von vielen Professoren nicht verlangt. Entsprechend sieht man an solchen Stellen dann auch, wer sich selbstständig mit dem Kram auseinandergesetzt hat und wer nicht.

Wenn er tatsächlich nur ein paar Statistiken durchführen will, dann kann man sie auch beim einmaligen Durchlaufen durch das Array aufstellen und hat so insgesamt nur O(n), was bei großen Datenmengen doch deutlich schneller ist als O(nlogn).

Zum Vergrößern anklicken....

Im Prinzip ja, wobei ich N*logN sehr gleich zu N sehe aber ich fürchte: Er läuft nicht nur einmal für alle Statistiken sondern je Anfrage durch.. das meinte ich ja gerade.

das Simulieren nach Zeit (nach Datum sortiert) ist nötig da so auch Phasenverschobene Effekte berücksichtigt werden die nach dem input Sonne kw/m² zeitlich versetzt auftreten können

Zum Vergrößern anklicken....

Das ist der Punkt: Du musst deine Daten selbstverständlich nach Datum sortiert aufnehmen (was denn sonst? Wunschtemperatur des Experiments zu jedem Zeitpunkt vorgeben? ) Aber du musst deine Anwendung nicht auf nach Datum sortierten Daten arbeiten lassen! Das sage ich ja gerade: Sortier sie beim Programmstart einmal nach Temperatur oder füge sie in eine std::map/set/unordere_map/multiset ein (je nachdem, was genau du für Anfragen stellst) und danach ist jede Anfrage mit winzigen Zeitaufwand beantwortet.

Daher will ich von vornherein alle Datentypen möglichst klein halten und möglichst wenig Performancebremsen.

Zum Vergrößern anklicken....

Was ich schon sagte: Klein ist noch lange nicht der richtige Weg um besonders schnell zu sein. Es ist oft eher das Gegenteil. Redundante/Überflüssige Informationen um die deine Daten angereichert werden (wie zB eine Sortierung der umgeehrten Paare Temp=>Datum) ermöglichen ja gerade schnellere Beantwortung von Fragen als Rohdaten.
Außerdem wie schon gesagt: Performance-Bremse hast du bestimmt nicht bei uint32 unixtime sondern eher durch 'schlechte' Algorithmen.

Ja habe mich für Memory-Bound also das komplette Laden in den RAM entschieden (wie es mir überzeugenderweise im anderen Thread geraten wurde), mir ist dann die Performance schon wichtiger und RAM ist inzwischen bezahlbar.

Zum Vergrößern anklicken....

Wo denn sonst wenn nicht im Ram? Genau genommen sollte ein Ram-Zugriff der Worst case in deinem Programm sein und so selten wie möglich passieren. Schnelle Algorithmen arbeiten natürlich nur im L1-3 Cache.

Und was Fonce auch sagt ist natürlich richtig: Wenigstens ein 'elapsed time in ms' sollte am Ende stehen um überhaupt verschiedene Ansätze zu vergleichen.

Ich kanns nur nochmal anbieten: Nenn mal einige konkrete Anfragen die du an deine Daten formulierst welche lange dauern und ich würde mich nicht wundern, wenn man problemlos um Faktor 1000 schneller werden kann beim Beantworten - und zwar komplett unabhängig von deinem verwendeten DateTime Datentyp.


Nur mal ein anschauliches Beispiel:
Du hast 1milliarde Paare von $date und $temp.
Du fragst oft ähnlich 'Wie oft war Temp < 25', oder auch <24 und ähnliches aber höchstens zB mit 0.1 Auflösung.
Wenn du hierfür vorher alle Daten nur exakt 1x durchläufst und alle Temperatur-Werte auf die maximal nötige Auflösung rundest und danach in einer std::map ablegst wo halt Key der temp-Wert ist und value die Zahl, wie oft diese Temperatur vorkommt dann ist das ein Baum mit 1000 Einträgen, wenn die Temperatur in einem Bereich von +-50° schwankt. Diese 1000 Einträge sind nun alle mit logN findbar und jede deiner Fragen 'Wie oft <25' lässt sich in unter 1ms beantworten - und zwar unabhängig von der Zahl der Messwerte! Also auch für deutlich mehr als 1mrd Messwerte. Erst bei >2^64 Messwerten wirds auf einer 64bit CPU 'langsamer' aber immernoch überhaupt garkein Problem bei so einfachen Fragen.

Egal was du tust - nimm keine std::list, std::map, std::set, std::unordered_map ... . Für kleine Datentypen wie in deinem Fall sind das einfach Katastrophal ineffiziente Datenstrukturen. Da bist du auf einem 64Bit System schnell bei 24 Byte und mehr (2-3 Pointer + Verwaltungskram) Overhead pro Eintrag (bei Visual Studio komm ich - warum auch immer - sogar auf ca 50 Byte overhead by std::set).
Einfach die Daten in einen oder mehrere std::vector packen, bei Bedarf sortieren und ne Binärsuche machen (std::upper/lower_bound).

Was das Sortieren vs durchiterieren angeht würde ich locker mit 1-2 Größenordnungen Unterschied rechnen (hängt natürlich von vielen Faktoren ab). Mal unabhängig von der asymptotischen Komplexität (O(log(N)*N) vs O(N)) ist ein Sortieralgorithmus halt deutlich komplizierter als nur jedes Element mit nem Grenzwert zu vergleichen.

Wenn du wirklich viele Abfragen wie die von Kuddlemuddle genannte hast ann sich also lohnen - muss sich aber nicht.

Ich will nur auf was hinweisen:

http://wiki.c2.com/?RulesOfOptimizationClub

Steht dein Programm schon?
Liefert es für einen Testdatensatz Ergebnisse?
Sind die Ergebnisse richtig?
Ist es dafür zu langsam?
Wie viel sollte es schneller werden?

Aber zurück zum Thema: Wähle das Format so, dass es praktisch ist.
Eure Bitfummelei macht moderne Prozessoren nur wuschig und damit langsam. Dazu ist modulo (NPOT) so was von langsam.

@TE:

Im Prinzip kann ich noch gar nicht genau sagen was alles genau ausgewertet wird da die Methodologie sich durch laufende Tests und Ergebnisse auch immer weiterentwickelt.

Zum Vergrößern anklicken....

Das schreit nach einer flexiblen Lösung (eigene Datumstypen zählen da nicht dazu). Mach es wohlüberlegt flexibel.

Beispiel aus meinem Erfahrungsfundus:

Ich habe mal ein Programm geschrieben, das den kürzesten Weg zwischen zwei Wikipedia-Artikeln findet. Angefangen habe ich, es in einer Datenbank zu schreiben (MySQL, lud mir die Latein-Wikipedia runter, die ist nicht so groß (Testcase, Regel 8.)). War sau langsam, aber kompakt und schnell geschrieben. Dann habe ich einen Profiler genommen und rausgefunden, was langsam war. Und diese Teile habe ich nach C++ portiert. War viel schneller, aber nicht so viel, wie ich gerne hätte. Also den Datensatz etwas geknetet, clevere Lösungen gefunden, um GB einzusparen. Keine Cache-Misses, Prefetching (gibt so ca. 30 %). Das ganze Programm. Am Ende konnte ich den kürzesten Weg zwischen zwei Artikel innerhalb von ca. 1 Sekunde finden, dazu wurde der Datensatz von 3 GB gescannt (deutsche Wiki) und mit MySQL Zusatzinfos geladen (noch mal 5-6 GB).

Und jetzt das wichtige:

Alle Vorüberlegungen wegen Performance waren voll für'n Popo. Die Probleme waren immer wo anders.
Ohne Testcase und Profiler musst du gar nicht anfangen, zu optimieren. So viele Fehler, die durch das Optimieren reingekommen sind... So viele Optimierungen, die alles langsamer gemacht haben (Bitfummelei!).

Und für deinen Fall: Große Datensätze.
In der DB vorhalten und gezielt für die Rechnung die Daten in ein Format exportieren, das für genau diese Rechnung am Besten geeignet ist.

Ich brauch es stundenweise, exportier es stundenweise.
Ich brauch es chronologisch, exportier es chronologisch.
Ich brauch es nach Temperatur sortiert, exportier es nach Temperatur sortiert.
Ich habe Mist gemessen, schmeiße alle Datensätze zwischen 11 und 12 Uhr weg, => DELETE FROM ...
Ich will es auf verschiedenen Rechnern simulieren: Auf die Datenbank via LAN zugreifen und exportieren.
Ich will meine Daten durchsuchen: Durchsuch sie.