schnelle datenstruktur...

[ruutaiokwu]

hallo zusammen,

bin gerade daran, eine crud (create, read, update, delete)-abstraktion mithilfe von dao's (data access object's) und dto's (data table objects) zu machen.

nun habe ich im dao-interface u.a folgenden methodenkopf definiert

public List<DTOMarkerInterface> read()


meine frage: wie kann ich die geschwindigkeit für den service layer (dort wo aus den crud-operationen konkrete anwendungfälle werden) verbessern? z. zt. verwende ich als interface die List und als konkrete datenstruktur die klasse ArrayList. und ich kann mir vorstellen, dass dies nicht gerade der effizienteste weg ist. (arbeitet ja intern mit arrays...)

hätte jmd. von euch eine idee, wie man die geschwindigkeit verbessern könnte?

- die klasse Queue verwenden?
- hashmap's verwenden? evtl. WeakHashMap wenn diese schneller ist als die "normale" HashMap? kann aber ein problem geben, denn die daten sortiert sein müssen... ist aber (noch) nicht der fall.

welche ansätze verwendet Hibernate? kennst sich jemand dessen innenleben aus?

grüsse,
jan

 

[Gelöschtes Mitglied 5909]

also an list bzw arraylist wirds nicht liegen. ich tippe mal drauf, dass du die service methoden ganz oft aufrust. wie wäre es denn dass du da dann einen cache baust?

 

[ruutaiokwu]

...ja, die methode wird halt so oft wie nötig aufgerufen; zur zeit befindet sich nur 1 method im service layer:

insertOrUpdate(EIDBean aEIDBean)


kurz erklärt: ich muss textfiles abholen, welche immer x zeilen haben. eine zeile davon ist der key, der primärschlüssel. diese fülle ich ab in eine tabelle, welche x felder hat. wenn der key bereits exisiert, veranlasst die insertOrUpdate(EIDBean aEIDBean)-methode auf der service layer ebene, ein sql update (auf DAO-ebene) zu machen, andernfalls ein sql insert.

für jedes file, das abgearbeitet wird, wird die funktion public List<DTOMarkerInterface> read() 1x aufgerufen, welche ein SELECT * from TABELLE macht. und anschliessend wird im service layer über die von public List<DTOMarkerInterface> read() zurückgegebe liste iteriert, und geprüft ob bereits ein key existiert. je nachdem folgt dann, wie bereits erwähnt, ein sql insert oder update...

dass eine solche abstraktion immer langsamer ist als die herkömmliche methode, ist mir klar. ist aber sehr greifbar, durch diese vollständig objektorientierte methode wird der zusammenhang zwischen betriebswirtschaftlichem und technischem richtig klar...

nun stellt sich die frage was man daran noch optimieren könnte? wie ich das mit dem caching realisieren sollte, ist mir nicht ganz klar? glaube da kann man doch ohnehin nichts cachen...?


grüsse,
jan

 

[Marco13]

Du brauchts eine DGH, am besten mit einem D7-Baum, und einem SH4-Hash als RTFM-Accessor.

:joke:

Ohne wirklich verstanden zu haben, was du da vorhast:

... über die von public List<DTOMarkerInterface> read() zurückgegebe liste iteriert, und geprüft ob bereits ein key existiert.

"Prüfen ob was bestimmtes drin ist" geht mit einer Map natürlich schneller, wenn man den Key hat (O(1) gegenüber O(n) bei einer List). HashMap vs. WeakHashMap macht da keinen Unterschied. Fall du mit "sortiert" meinst, dass die zurückgegebene Map die Elemente in einer bestimmten Reihenfolge enthält (nämlich der, in der sie eingefügt wurden) kannst du eine LinkedHashSet als Implementierung verwenden. Falls "echt" nach dem Schlüssel sortiert werden soll, wäre eine TreeMap angebracht.

 

[ruutaiokwu]

"Du brauchts eine DGH, am besten mit einem D7-Baum, und einem SH4-Hash als RTFM-Accessor."

alles bereits hinter mir...;-)


nein, spass bei seite und besten dank für deinen tipp, mit der LinkedHashSet. allerdings bin ich bei der folgenden aussage anderer meinung: "Falls "echt" nach dem Schlüssel sortiert werden soll, wäre eine TreeMap angebracht" ...ich würde eher der dao-funktion read() 2 strings als argument verpassen, die, falls sie nicht null oder "" sind, ein " ORDER BY field ASC" resp. " ORDER BY field DESC" an das sql SELECT-kommando hinten anhängen. also read (String sortBy, String order)...

was hälst du von der klasse Queue in diesem fall? was hälst du grundsätzlich für schneller, List oder Queue?

schlussendlich brauche ich keinen direkten zugriff über einen index oder key, jedoch müssen, wie du richtig erkannt hast, die einträge in der gleichen reihenfolge sein wie beim einfügen.


gruss, jan

 

[Marco13]

Die Frage, ob da wo bei welcher Anfrage nun bei einem SELECT was hinzugefügt werden muss (oder so) liegt hinter meinem Horizont, darauf bezog sich mein erster Satz. Ich habe nur ein paar Datenstrukturen und ihre Eigenschaften erwähnt. Eine List und einen Queue sind sehr ähnlich (so ähnlich, dass LinkedList sowohl eine List als auch eine Queue ist). Wenn die zurückgegebene Struktur nicht mehr verändert (also nicht, wie eine Queue, von vorne her "aufgefressen") wird, sondern nur drüberiteriert wird, besteht eigentlich kein Grund, da nicht eine (ggf. sogar immutable) List zurückzugeben.
Jetzt wieder eine Aussage, die du wegen Mangelnden Verständnisses der Materie meinerseits selbst bewerten musst:
FALLS bei dem Drüberiterieren aber nur etwas gesucht wird, was genausogut der key für eine Map sein könnte, dann wäre der direkte Zugriff mit diesem Key über eine Map natürlich schneller.

 

[bygones]

ich stell mal wieder die berühmte Frage:

du hast nachgemessen, dass das was du nun verwendest nicht performant ist, das genau das die Stelle ist die dir Probleme bereitet ?
oder vermutest du es und denkst "oh da muss ich schonmal schnell was besseres machen" ?

Diskussion bzgl dieser Thematik -> Forensuche....

PS:

und ich kann mir vorstellen, dass dies nicht gerade der effizienteste weg ist. (arbeitet ja intern mit arrays...)

allein das bestätigt mich jdf dass es sich hierbei nur um eine performanceeinbusse handelt...

 

[LoR]

hallo zusammen,

bin gerade daran, eine crud (create, read, update, delete)-abstraktion mithilfe von dao's (data access object's) und dto's (data table objects) zu machen.

nun habe ich im dao-interface u.a folgenden methodenkopf definiert

public List<DTOMarkerInterface> read()


meine frage: wie kann ich die geschwindigkeit für den service layer (dort wo aus den crud-operationen konkrete anwendungfälle werden) verbessern? z. zt. verwende ich als interface die List und als konkrete datenstruktur die klasse ArrayList. und ich kann mir vorstellen, dass dies nicht gerade der effizienteste weg ist. (arbeitet ja intern mit arrays...)

hätte jmd. von euch eine idee, wie man die geschwindigkeit verbessern könnte?

- die klasse Queue verwenden?
- hashmap's verwenden? evtl. WeakHashMap wenn diese schneller ist als die "normale" HashMap? kann aber ein problem geben, denn die daten sortiert sein müssen... ist aber (noch) nicht der fall.

welche ansätze verwendet Hibernate? kennst sich jemand dessen innenleben aus?

grüsse,
jan

Ich verstehe absolut nicht wie man sich mit Designfragen beschäftigen kann aber nicht mal die Grundlagen verstanden hat. Scheint aber mittlerweile immer häufiger vorzukommen :noe:.

 

[ruutaiokwu]

@LoR: was produktives kannst du nicht beisteuern?

 

[LoR]

@LoR: was produktives kannst du nicht beisteuern?

Selbstverständlich z.B. Galileo Computing :: Java ist auch eine Insel (8. Auflage) – 12 Datenstrukturen und Algorithmen. Sobald du dich mit den entsprechenden Datenstrukturen beschäftigt hast werden sich deine gestellten Fragen wie von selbst in Luft auflösen .

 

[Gelöschtes Mitglied 5909]

also nochmal:

1. du lädst immer alle daten um herauszufinden ob ein datensatz existiert?
2. dann iterierst du über alle datensätze bis du den einen gefunden hast
3. und jetzt fragst du ob das iterieren die performance kostet? :bloed:

Also dazu fällt mir nicht mehr viel ein.

Aber nunja, ich will mal nicht so sein.

Lade doch nur den einen, wenn er da ist ist er da -> update, wenn nicht, dann nicht -> insert
Verwende ein Cache!

 

[ruutaiokwu]

"1. du lädst immer alle daten um herauszufinden ob ein datensatz existiert?"

bisher richtig...


"2. dann iterierst du über alle datensätze bis du den einen gefunden hast"

bisher auch richtig... immerhin hatte die schleife ein "break" drin, stell dir vor...;-)


"3. und jetzt fragst du ob das iterieren die performance kostet?"

ich frage das nicht, sondern stelle es fest. und frage nach verbesserungsvorschlägen und tipps.


nun habe ich die problematik mit einem sql count gelöst, das mit 0 bzw. 1 zurückgibt. bei 0 folgt ein insert, bei 1 ein update.... das verstösst aber meiner meinung nach gegen das crud-konzept.

infos dazu hier: CRUD ? Wikipedia

nun aber nochmals zurück zu der crud (create, read (bzw. read), update, delete)-thematik: wenn ich etwas auf diese 4 grundoperationen zerlegen möchte, wird's wohl so oder so langsam. gut, ich meine man könnte natürlich z.b. für irgendwelche sql joins entsprechede beans anfertigen... aber dann ist das ganze nicht mehr 1:1... auch join's würden gegen das crud-konzept verstossen, meiner meinung nach...

was die suche betrifft wäre es evtl. doch angebracht map's zu verwenden, aber NUR die TreeMap, welche auch sortiert werden kann. (z.b. nach primary key...) dann könnte man auch direkt darauf zugreifen...

weiss jemand welche konzepte hibernate oder ibatis verfolgen?

 

[Murray]

Dein Performanceproblem dürfte das Laden aller Datensätze sein; normalerweise ist eine Datenbank selbst schon ganz gut in der Lage, herauszufinden, ob ein bestimmter Datensatz existiert.

Die Art und Weise, wie Du dann das Resultat iterierst, wird die Performance nicht wesentlich bestimmen - zumindest wirst Du mit Optimierungen in diesem Bereich niemals soviel herausholen können wie beim Verzicht auf die Laderei alle Objekte.

Ohne mit der Theorie besonders vertraut zu sein: wo verbietet CRUD denn, beim Laden eine Bedingung anzugeben? Selbst in dem von Dir zitierten Wikipedia-Artikel wird das gemacht.

 

[ruutaiokwu]

hallo zusammen,

bezügl queue vs. list:

habe die sache jetzt praktisch testen können, mit den vorgängen SCHREIBEN sowie ALLES auslesen sind gewisse queues schneller sind als eine ArrayList. (~ 10%)

lists kann man durch queues ersetzen, wenn folgende bedingungen erfüllt sind:




a.) wenn man eine iteration darüber macht, von alpha bis omega, also ALLES ausliest (es sei denn man setzt ein abbruchkriterium z.b. über einen counter, dann kann man auch bei einer queue nur einen teil auslesen... na ja...)

sowie

b.) die liste nach der iterations-schleife NIE mehr braucht. (DAS IST EIN MUSS, die queue "frisst" sich ja selbst auf...)


aber vorsicht: nicht alle queue-implementierungen wird schneller. da muss man schon die richtige haben.


noch was @LoR: "...aber nicht mal die Grundlagen verstanden hat."

was verstehst du unter grundlagen? ist komplexitätstheorie für dich eine grundlage? dann hast du aber einen verdammt hohen massstab! (worauf du aber eigentlich stolz sein kannst, wenn das für dich zum 1x1 gehört ;-)) bei uns in der schweiz ist das ein thema (theor. informatik) für eine hochschule (z.b. eidg. techn. hochschule oder eine universität)

wohl kaum aber bei einer fachhochschule, die machen lieber oo-sachen und uml bis zum abwinken und so zeugs...

klar ist es tatsache, dass die programmierer, welche wirklich anspruchsvolle algorithmen (z.b. trading-algorithmen bei hedge-funds, investmentbanken oder im bereich ki/neuronale netzwerke) entwickeln, meist aus einer mathematischen perspektive entwickeln, oder gar mathematiker sind...

(hand auf's herz: ich gehöre auch nicht zu dieser "elite"...)

der durchschnitts-fh-software-ingenieur (bei uns in der schweiz kann man sich im techn. bereich als fh-abgänger ingenieur nennen) ist kaum (näher) mit komplexitätstheorie vertraut...


gruss, jan