Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Do Mär 28, 2024 12:54

Foren-Übersicht » Programmierung » Design Challenges
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 7 Beiträge ] 
Autor Nachricht
BeitragVerfasst: Mo Jan 16, 2012 14:32 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2621
Wohnort: Berlin
Programmiersprache: Go, C/C++
Aufgabe
Es wird eine API zur Verfügung gestellt, mit der man 0 bis mehrere Werte in einer Gruppe ablegen kann.
Die logische Verknüpfung der Werte, in einer Gruppe, werden durch den Nutzer, der API bestimmt und nicht durch die API selber.
Ob der Nutzer ein Wert mit einem 0.25ms Intervall in Verbindung bringt oder einfach nur jeden 8 Wert will ist nicht Aufgabe der API.
Diese Gruppen werden von einer Verwaltungs Instanz gehalten.
Die API soll nicht Thread-Safe sein, da dieses die Anzahl der möglichen Resultate und die Komplexität der Challenge unnötig erhöht.
Mit der API können nur Gruppen abgebildet werden, die als Gleitkommazahl darstellbar sind.
Die einzelnen Gruppen sollen durch ein Namen Kennzeichenbar sein, müssen aber nicht Einzigartig sein.

Was zählt als Lösung
Für jede Lösung muss der Sourcecode und ein Beispielcode(wie verwendet man den Code) für jede öffentlich zugreifbare Methode/Property eingereicht werden.
Es dürfen externe Bibliotheken verwendet werden und sollten mit den Bezugsquellen genannt werden.
Ein UML Diagram ist nicht Pflicht hilft aber zum schnelleren Verständnis, der Lösung.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Di Jan 24, 2012 21:41 
Offline
Forenkatze
Benutzeravatar

Registriert: Mi Okt 22, 2003 18:30
Beiträge: 1944
Wohnort: Närnberch
Programmiersprache: Scala, Java, C*
Öh... erster ;) Und ohne weiteren Kommentar mein Lösungsvorschlag, den ich gerade gebastelt habe:
Code:
  1. package profiler
  2.  
  3. // example code
  4. object ProfilerTest extends App {
  5.   Profiler.addBinding("Temperature", Sample(System.nanoTime, 42.0d))
  6.   Profiler.addBinding("Temperature", Sample(System.nanoTime, 40.0d))
  7.   Profiler.addBinding("Memory Usage", Sample(System.nanoTime, 512.0d))
  8.  
  9.   println("Values recorded so far: ")
  10.   println(Profiler.map(entry => "- %s: %s".format(entry._1, entry._2.toList.sortWith(_.timestamp < _.timestamp).mkString(", "))).mkString("\n"))
  11. }
  12.  
  13. // profiler code
  14. import scala.collection.mutable.{HashMap, Set, MultiMap}
  15.  
  16. case class Sample(timestamp: Long, value: Double) {
  17.   override def toString = "%.3f at %dms".format(value, timestamp / 1000000)
  18. }
  19.  
  20. object Profiler extends HashMap[String, Set[Sample]] with MultiMap[String, Sample]

Verwendet wurde Bibliothekstechnisch nur die scala-library.jar von Scala 2.9. Die ist also bei Scala mit dabei. Ich war mal so frei und habe das alles in einer Datei gemacht und Beispielcode von Library-Code durch Comments getrennt.

Ausgabe:
Code:
  1. Values recorded so far:
  2. - Temperature: 40,000 at 1327437292574ms, 42,000 at 1327437292557ms
  3. - Memory Usage: 512,000 at 1327437292574ms


Tante Edith meint:
So ganz ohne Kommentar möchte ich es dann doch nicht dastehen lassen. Hat ja keinen Sinn, wenn niemand den Code versteht :)

Beginnend mit dem Profiler selbst:
Zeile 14 ist das import-Statement. Das sollte jetzt keine all zu großen Überraschungen bereiten. Deswegen sei auch nur kurz darauf eingegangen: Man erkennt hieran, dass mutable collections verwendet werden. Leider hat Scala von Haus aus keine immutable MultiMap dabei und die Aufgabenstellung schrie förmlich danach. Und da Thread-safety nicht verlangt war, sprach direkt nichts gegen die mutable MultiMap.
Zeile 16 ist die Klassendefinition für die Sample-Klasse. War zwar nicht verlangt, ich fand es aber hübscher, wenn so ein vom Profiler aufgezeichnetes Sample etwas gekapselt ist. Diese Art in Scala, Klassen zu deklarieren, sorgt dafür, dass automatisch ein Konstruktor gemacht wird, der die beiden in Klammern angegebenen Parameter initialisiert. Der Compiler generiert ein passendes equals und hashCode. Die Methode toString habe ich überschrieben, damit es in der Ausgabe ein wenig hübscher wird, ist aber auch optional.
Zeile 20 schließlich ist der eigentliche Profiler. Da die gewünschte Funktionalität bereits vollständig in der Standardbibliothek enthalten ist, ist der Profiler erwartungsgemäß etwas knapp. Zeile 20 ist daher einfach nur ein Singleton (dafür dient das object-Keyword). Nennenswert ist da noch das mixin-keyword. Das mixt den MultiMap-Trait in die HashMap hinein und schon hat man eine MultiMap :)

Und nun zum Beispielcode:
Zeile 4 ist quasi die main-Methode, wie man sie aus Java und C* kennt. Nur auf das nötigste reduziert.
Zeile 5-7 fügt dem Profiler Werte hinzu und der Profiler sorgt dafür, dass sie in den passenden benamsten Gruppen landen.
Zeile 10 spuckt die Werte, die der Profiler gespeichert hat, wieder aus. Wer die Zeile auch nach mehrmaligem Lesen nicht so ganz rallt, sei beruhigt. Die macht nämlich eine ganze Menge und ist deswegen so kryptisch. Tatsächlich wird über alle Gruppen iteriert, ihr Name ausgegeben und nach ihrem Namen die einzelnen Messwerte, die nach ihrem Timestamp sortiert werden. Könnte man auch etwas leserlicher schreiben, mir hat der Einzeiler aber gefallen :)

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Di Jan 24, 2012 22:58 
Offline
DGL Member
Benutzeravatar

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java
Eine C++ Lösung mit Macro-Einsatz zur Reduzierung von Allocations und Vermeidung von Stringvergleichen....wir wollen ja schließlich etwas Profilen... ;)

Code:
  1. #include <iostream>
  2. #include <time.h>
  3. #include <vector>
  4. #include <map>
  5. #include <string>
  6.  
  7. using namespace std;
  8.  
  9. class Profiler
  10. {
  11. public:
  12.     static unsigned GetId(string name) {
  13.         map<string,unsigned>::iterator itr = m_names.find(name);
  14.         if (itr != m_names.end()) {
  15.             return itr->second;
  16.         }
  17.         else {
  18.             unsigned id = m_samples.size();
  19.             m_names.insert(make_pair(name, id));
  20.             m_samples.push_back(vector<SSample>());
  21.             return id;
  22.         }
  23.     }
  24.  
  25.     static void Sample(unsigned id, float value) {
  26.         time_t timestamp = time(NULL);
  27.         m_samples[id].push_back(SSample(timestamp, value));
  28.     }
  29.  
  30.     static void Print() {
  31.         map<string,unsigned>::const_iterator
  32.             itr = m_names.begin(),
  33.             end = m_names.end();
  34.         for ( ; itr != end; ++itr) {
  35.             cout << itr->first << "\n";
  36.             const vector<SSample>& samples = m_samples[itr->second];
  37.             for (size_t i=0; i<samples.size(); ++i) {
  38.                 cout << samples[i].timestamp << " => " << samples[i].value << "\n";
  39.             }
  40.             cout << "\n";
  41.         }
  42.     }
  43.  
  44. private:
  45.     struct SSample {
  46.         time_t timestamp;
  47.         float value;
  48.  
  49.         SSample(time_t _timestamp, float _value) : timestamp(_timestamp), value(_value) {}
  50.     };
  51.  
  52.     static map<string,unsigned> m_names;
  53.     static vector<vector<SSample> > m_samples;
  54. };
  55.  
  56. map<string,unsigned> Profiler::m_names;
  57. vector<vector<Profiler::SSample> > Profiler::m_samples;
  58.  
  59.  
  60. #define PROFILE(name, value) \
  61.     { static unsigned profilerLocalID__ = Profiler::GetId(name); Profiler::Sample(profilerLocalID__, value); }
  62.  
  63. int main() {
  64.     PROFILE("Temperature", 34.5f);
  65.     PROFILE("Temperature", 35.5f);
  66.     PROFILE("Memory Usage", 78.0f);
  67.  
  68.     Profiler::Print();
  69.  
  70.     return 0;
  71. }

_________________
Yeah! :mrgreen:


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Di Jan 24, 2012 23:23 
Offline
Forenkatze
Benutzeravatar

Registriert: Mi Okt 22, 2003 18:30
Beiträge: 1944
Wohnort: Närnberch
Programmiersprache: Scala, Java, C*
Coolcat hat geschrieben:
Eine C++ Lösung mit Macro-Einsatz zur Reduzierung von Allocations und Vermeidung von Stringvergleichen....wir wollen ja schließlich etwas Profilen... ;)
Gut, dass mein Code auch keine Stringvergleiche macht. Und Dank der mittlerweile standardmäßig eingeschalteten Escape Analysis sind Allocations auch weitestgehend auf dem Stack und nicht mehr auf dem Heap.

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mi Jan 25, 2012 00:40 
Offline
DGL Member
Benutzeravatar

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java
Zitat:
Gut, dass mein Code auch keine Stringvergleiche macht.

Du benutzt eine HashMap. D.h. es wird zu erst ein Hash berechnet...der Hash gesucht und dann nochmal der String verglichen..könnte ja eine Hashkollision gewesen sein. Gut, ich kenne Scala nicht, vielleicht werden hier kontante Strings speziell behandelt, so dass es letztlich nur ein Pointer-Vergleich ist. In jedem Fall behaupte ich das "direkt an die richtige Stelle schreiben" schneller ist ;)

Was die Allkokation angeht, die HashMap liegt mit Sicherheit auf dem Heap und muss schließlich irgendwie wachsen wenn neue Samples kommen. Wenn ich nach ca. 1min googlen diese Escape Analyisis richtig verstehe optimiert diese nur "Short lived objects", was auch Sinn macht. Die Samples leben aber sicher recht lange.

Dafür ist dein Code natürlich deutlich eleganter :)

_________________
Yeah! :mrgreen:


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mi Jan 25, 2012 01:38 
Offline
Forenkatze
Benutzeravatar

Registriert: Mi Okt 22, 2003 18:30
Beiträge: 1944
Wohnort: Närnberch
Programmiersprache: Scala, Java, C*
Java macht tatsächlich als erstes einen Pointervergleich beim String.equals. Und da die Strings hier konstant sind und im Bytecode alle gleichen Strings nicht nur gleich, sondern auch identisch sind, geht der Vergleich sehr schnell.
Und der Hash der Strings wird, sobald er ein Mal berechnet wurde, gespeichert. Ist also auch sehr schnell vergleichbar. Daher hat der Code quasi keine nennenswerten Stringvergleiche zur Laufzeit.

Das mit den short-lived objects ist richtig. Aber genau das sind ja die, die die Performance üblicherweise herunterziehen.

Ich habe mal eine komplett thread-safe Version gemacht:
Code:
  1. package profiler
  2.  
  3. object ProfilerTest2 extends App {
  4.   var profiler = new ProfilerImmutable
  5.   profiler += ("Temperature", Sample(System.nanoTime, 42))
  6.   profiler += ("Temperature", Sample(System.nanoTime, 43))
  7.   profiler += ("Mem", Sample(System.nanoTime, 25))
  8.  
  9.   println(profiler)
  10. }
  11.  
  12. case class ProfilerImmutable(
  13.   groups: Map[String, List[Sample]] = Map.empty[String, List[Sample]]
  14. ) {
  15.   def + (group: String, sample: Sample) =
  16.     copy(groups = groups + (group -> (sample :: getElseNew(group))))
  17.  
  18.   override def toString =
  19.     "Results: \n" + groups.map(entry => "- " + entry._1 + ": " + entry._2.sortWith(_.timestamp < _.timestamp).mkString(", ")).mkString("\n")
  20.  
  21.   private def getElseNew(group: String) = groups.getOrElse(group, List.empty[Sample])
  22. }
  23.  
  24. case class Sample(timestamp: Long, value: Double) {
  25.   override def toString = "%.3f at %dms".format(value, timestamp / 1000000)
  26. }


Der Code ist komplett immutable (!), daher auch zu 100% threadsafe. Außerdem noch ein bisschen besser gekapselt, so dass der Aufrufer diesmal wirklich leichtes Spiel hat (Zeile 1 - 9). Diese Version gefällt mir fast besser als die erste :) Hat außerdem den Vorteil, dass man den Profiler und die Ergebnisse wild in der Gegend herumreichen kann ohne Angst haben zu müssen, dass irgend ein anderer Teil des Programms daran Dinge verändert.

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mi Jan 25, 2012 17:43 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2621
Wohnort: Berlin
Programmiersprache: Go, C/C++
Code:
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <string>
  5. #include <memory>
  6.  
  7. class SampleGroup:public std::vector<float>
  8. {
  9.     public:
  10.         SampleGroup(const char *Name)
  11.         :Name(Name)
  12.         {
  13.         }
  14.         const char *Name;      
  15. };
  16.  
  17. class Profiler
  18. {
  19.     public:
  20.         typedef std::map<unsigned long long,SampleGroup> ContainerType;
  21.         typedef std::pair<unsigned long long,SampleGroup> ElementType;
  22.  
  23.         static SampleGroup* AddGroup(const char* Name)
  24.         {
  25.             m_Groups.insert(ElementType(unsigned long long(Name),SampleGroup(Name)));
  26.             return &m_Groups.find(unsigned long long(Name))->second;
  27.         }
  28.  
  29.         static SampleGroup* GetGroup(const char* Name)
  30.         {
  31.             SampleGroup* result=0;
  32.             ContainerType::iterator it=m_Groups.find(unsigned long long(Name));
  33.             if (it!=m_Groups.end())
  34.                 result=&it->second;
  35.             return result;
  36.         }
  37.  
  38.         static const ContainerType& Groups()
  39.         {
  40.             return m_Groups;
  41.         }
  42.     protected:
  43.         static ContainerType m_Groups;
  44. };
  45.  
  46. Profiler::ContainerType Profiler::m_Groups;
  47.  
  48. /**
  49.  * Test code
  50.  */
  51.  
  52. int main(int argc, char* argv[])
  53. {
  54.    
  55.     Profiler::AddGroup("DeltaTime")->push_back(0.33f);
  56.     SampleGroup* mem=Profiler::AddGroup("Memory");
  57.     SampleGroup* memTime=Profiler::AddGroup("MemoryTimeStamp");
  58.  
  59.     mem->push_back(0.14f);
  60.     memTime->push_back(0.1f);
  61.  
  62.     const Profiler::ContainerType& grps=Profiler::Groups();
  63.     for (Profiler::ContainerType::const_iterator it=grps.begin();it!=grps.end();++it)
  64.         std::cout<<it->second.Name<<std::endl;
  65.  
  66.     std::cout<<Profiler::GetGroup("DeltaTime")->at(0)<<std::endl;
  67.     std::cout<<mem->at(0)<<"% at "<<memTime->at(0)<<"seconds after start"<<std::endl;  
  68.     return 0;
  69. }


Output
Code:
  1. DeltaTime
  2. Memory
  3. MemoryTimeStamp
  4. 0.33
  5. 0.14% at 0.1seconds after start


edit:
Idee
Es gibt 2 Klassen, SampleGroup und Profiler.
SampleGroup wird von std::vector<float> abgeleitet, da diese intern ein array von floats verwendet und Speicher, für weitere Elemente vor reserviert.
Durch diese Eigenschaften ist das hinzufügen und zugreifen sehr schnell, ausser wenn der reservierte Speicher voll ist und ein neuer reserviert wird, denn dann muss der alte Block kopiert werden. Will man den damit verbundenen Peek vermeiden, dann sollte man auf dequeue zurück greifen und auf gering längere Zeiten, für das hinzufügen von Elementen in kauf nehmen.
Der Konstruktor erwartet ein const char*, weil c++ alle Texte als const char* interpretiert und ich das duplizieren eines ohnehin immer verfügbaren Textes sparen.

Profiler ist eine Klasse mit statischen Membern und Methoden.
Zum lagern der SampleGroup's benutzte ich folgenden Container std::map<unsigned long long,SampleGroup>.
Der Key ist wird eventuell einige verwundern und ist eine Optimierung.
Da eine SampleGroup über ein Namen erreichbar ist und C++ nun mal den Text unter einer einzigartigen Speicheradresse hinterlegt,kann man diesen auch perfekt als Key verwenden. Um sicher zu gehen, dass ich den Pointer fassen kann, nehme ich ein unsigned long long, dass per C++11 Standard jeder Compiler supporten muss. Wenn man also schon zur Compiletime weiß, auf welches Element man zugreifen will, dann kann man dies so prima lösen.
Wenn man erst zur Runtime weiß, welches Objekt man haben will, dann muss man über die Groups Methode sich durch die Objekte hangeln.
Der Zugriff auf Profilerdaten sollte eigentlich keine Zeitkritische Operation sein aber das erweitern schon.

Da bisher nur GCC constexpr aus den neuen Standard beherrscht, hab ich den Pointeransatz gewählt.
Sobald VS2012 den Support bietet, macht es aber Sinn den Pointer-Ansatz durch 2 Hashfunktionen zu ersetzten.
Die erste wäre eine Compiletime Hashfunktion, durch constexpr realisiert und die 2. wäre gleiches nur für Runtime, damit auch string Klassen verwendet werden können.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 7 Beiträge ] 
Foren-Übersicht » Programmierung » Design Challenges


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 5 Gäste


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.069s | 19 Queries | GZIP : On ]