Hi,

ich habe ein kleines Problem:




Das ist aus dem mulitserver tut von kevin98. Ihr seht: Es sind mehrere Clients angemeldet. Und ich möchte an den Client mit dem nick "blabal" einen text schicken. Das geht so wie ich´s oben mache auch wunderbar. nur denke ich das das nicht grade sehr elegant/performant ist. vorallem wenn ein paar milionen user angemeldet WÄREN (ich wil´s schon stabil machen).

Gibt es sowas wie:



Hoffe ihr versteht was ich meine...

Hallo Jaffa Keks,

das ist Performant genug.

Gruss

mikeb69

Aber wenn es richtig viele User geben würde?

Immer wenn ein client etwas sendet muss der server erst alle user "durchegen" bis er den entsprechenden "partner client" gefunden hat. und diesem dann den stream schicken. das muss doch besser gehen?

Dann machs mit nem Backgroundworker...

mikeb69 schrieb:

das ist Performant genug.

Daran ist gar nichts laufzeitoptimiert. Eine lineare Liste ist im Bezug auf die Suchgeschwindigkeit eine der schlechtesten Datenstrukturen, die es gibt.

Samus Aran schrieb:

Dann machs mit nem Backgroundworker...

Und vielleicht lagern wir den Rechenvorgang noch in eine Cloud aus, was? Dadurch reduziert sich der Rechenaufwand ganz bestimmt.

Eine einfach Lösung mit spürbarem Effekt ist: Verwende eine Hashtable (in .NET z.B. implementiert durch Dictionary) und verwende als Hashes bzw. Keys die Nicks.
Wenn das funktioniert, solltest du etwas am Hashing-Algorithmus feilen, denn einfach die Nicks zu verwenden, ist nicht besonders schlau. Aber dazu gibt es jede Menge Bücher, z.B. Introduction to Algorithms.

Hallo Renati,

Daran ist gar nichts laufzeitoptimiert. Eine lineare Liste ist im Bezug auf die Suchgeschwindigkeit eine der schlechtesten Datenstrukturen, die es gibt.

aber schnell genug für diesen Fall und diesen User.

Gruss

mikeb69

Warum? Wenn er sich mit Laufzeitoptimierung beschäftigen möchte, sollte man ihm doch zumindest die Chance geben. In diesem Forum wird oft (zu Recht) angeprangert, dass sich Fragesteller keine Gedanken machen, keine Ahnung haben und Copy&Paste Code haben wollen.
Aber wenn dann mal jemand ein Problem selbstständig erkennt, klar formuliert und nach möglichen Lösungswegen ohne erkennbaren Copy&Paste-Gedanken fragt, dann finde ich es falsch, ihn abzudeckeln. Ganz egal, ob Jaffa Keks das nun weiterverfolgen wird oder nicht - aber jede vernünftige Frage verdient eine vernünftige Antwort. Und wenn ihn das nur zu der Erkenntnis bringt, dass man auch beim normalen Programmieren auf elementare Probleme der Informatik stößt...

Hallo Renati,

... aber jede vernünftige Frage verdient eine vernünftige Antwort.

aus meiner Sicht war das eine vernünftige Antwort.

Wie groß ist den der Geschwindigkeitsunterschied zwischen dem was er schon hat und dem was du ihm anbietest ?

Vermutlich vernachlässigbar.

Dann stellt sich mir aber die Frage ob es nicht schlauer wäre den Codestil des Users verbessern zu wollen als
ein paar ms in einem sehr speziellem Fall rauszukitzeln.

In diesem Forum wird oft (zu Recht) angeprangert, dass sich Fragesteller keine Gedanken machen, keine Ahnung haben und Copy&Paste Code haben wollen.
Aber wenn dann mal jemand ein Problem selbstständig erkennt, klar formuliert und nach möglichen Lösungswegen ohne erkennbaren Copy&Paste-Gedanken fragt, dann finde ich es falsch, ihn abzudeckeln.

Ganz meine Meinung.

Gruss

mikeb69

oh sorry ich wollte jetzt keinen Streit zwischen den pro´s hier im Forum entfachen...

Ich habe mir halt überlegt ob es denn nicht anders geht. nehmen wir an es wären 5000000 user online. und ich vergleiche erst bei jedem ob der nick dem meines partners entspricht. und das bei jedem futzi von text. na dann gute nacht. noch dazu soll das projekt sehr perfomant werden.

also bedanke ich mich bei renati! ein buch werd ich mir nicht gleich kaufen aber ich guck mal was man so über "hashtables" findet. vlt. gelingts mir ja. und wenn nicht ist ja auch kein welt untergang.

Wenn wir schon dabei sind. Kann mir einer von euch verraten wie sowas wie teamviewer funktioniert? ich aknn mir nicht vorstellen das das einfach screenshots macht und diese dann überträgt (so läuft mein programm nämlich zurzeit). Die geschwindigkeit ist bei einer 60kbits leitung wie ich sie habe echt ok. aber wie läuft das bei teamviewer. vlt. über direct x ?

mikeb69 schrieb:

Wie groß ist den der Geschwindigkeitsunterschied zwischen dem was er schon hat und dem was du ihm anbietest ?

Eine gute Hashfunktion vorausgesetzt liegt eine Hashtable in O(1), die lineare Liste aber in O(n). Während also die Zugriffszeit bei obiger Implementation linear zur Anzahl der Elemente steigt, ist sie bei der Hashtable konstant und unabhängig von der Anzahl der Elemente.
Beispiel: Während deine lineare Liste zum Finden eines Elements durchschnittlich 1ms*1/2*n benötigt, benötigt meine Hashtable immer 5ms.
Hat deine Liste 1 Element, brauchst du 1ms zum Finden des Elements. Ich 5ms.
Hat deine Liste 1000 Elemente, brauchst du durdchschnittlich eine halbe Sekunde zum Finden eines Elements. Ich 5ms.
Hat deine Liste 1000000 Elemente, brauchst du durchschnittlich 50 Sekunden zum Finden eines Elements. Ich 5ms.
Der Unterschied ist also gewaltig.

@JaffaKeks:
Wir streiten doch nicht, es wird doch keiner ausfallend. Nur ein bisschen scharfkantige Rhetorik.
Wenn du eine Universitätsbibliothek in der Nähe hast, bekommst du dieses oder ein ähnliches Buch dort garantiert. Du kannst dir die entsprechenden Seiten vor Ort kopieren und fertig (gibt's übrigens auch auf deutsch).
Zur Funktionsweise von Teamviewer gibt es hier schon mehrere Themen, kurz gesagt ist es grundsätzlich eine gute Strategie, den Bildschirm in Kacheln aufzuteilen und nur solche zu übertragen, die sich geändert haben. Während ich z.B. diesen Text schreibe, verändert sich ja der Großteil meines Screens nicht, sondern nur dieses Textfeld hier. DirectX ist nur eine Zugriffsschnittstelle auf die Grafikkarte.

AH!

Nochmal danke
Uni Bibliothek gibt es sogar hier. da werd ich morgen mal vorbei gucken. und dann einfach die entsprechenden seiten mit portable netbook scanner einsacannen spart paier.

Zu Teamviewer: Auf sowas mit Kacheln bin ich auch schon gekommen. Wenn ich überprüfen möchte ob sich der Bildinhalt einer Kachel geändert hat... also ich würde das dann so amchen das ich alle pixel des bildes durchgehe und überprüfe ob sie die selbe "farbe" wie vor sagen wir 5ms hatten. wäre das so richtig oder geht das eleganter?

Hier bleibt dir wirklich nicht viel mehr übrig, als die Pixel einzeln zu testen. Du solltest möglichst "rohe" Datenstrukturen verwenden, also hier z.B. ein zweidimensionales Array anstatt zweier geschachtelter Listen. Es ist natürlich möglich, z.B. schachbrettartig jeden 2. Pixel auszulassen und diese immer wechselnd abzufragen, so dass der Vergleich nur halb so lang dauert. Für .NET fällt mir auf Anhieb aber keine Methode ein, Repaint-Events des Systems abzufangen.
Gegebenenfalls (natürlich erst nach intensiver Suche) solltest du diese Frage in ein neues Thema auslagern, damit andere sie bemerken...

P.S.: In diesem Buch sollte auch etwas über Hashtables zu finden sein: Kleinberg, Tardos: Algorithm Design
P.P.S.: Und es gibt Videoaufzeichnungen von einer Vorlesung am MIT: ocw.mit.edu/OcwWeb/Electrical-…JFall-2005/VideoLectures/

Großen Dank renati!

Ich versuchs jetzt erst mal mit der Schachbrett Methode. Danke dir!

Wenn ich nochmal probleme haben sollte komm ich nochmal auf diesen thread/dich zurück!

GROßES DANKE!

Um noch mal auf den "Streit" HashListe vs lineare Liste zurückzukommen ...
( Die besten Bemerkungen von Noobs in diesem Forum - Oder wie man sich als Neuling besser nicht verhält ! )

Um zu beurteilen, was das "beste" ist, muss man erstmal definieren. was denn überhaupt "gut" ist.
Bei jeglicher "Liste" gibt es im Prinzip 4 Parameter um sie zu "bewerten":
1. : Insert - wie lange dauert es, ein Element zur Liste hinzuzufügen
2. : Lookup - wie lange dauert es, ein bestimmtes Element zu finden
3. : Delete - wie lange dauert es, ein Element aus der Liste zu löschen
4. : Speicherverbrauch - wieviel Speicher benötigt jedes Element im Durchschnitt.

Dummerweise lassen sich nicht alle Parameter gleichzeitig optimieren. Heißt: Wenn ich schnell suchen, einfügen und löschen kann (LID), dann brauch ich meist viel Speicher (der gespeicherte Hash ist verhältnissmäßig groß und muss ja auch gespeichert werden). Will ich wenig Speicher verwenden (zb ein Array), dann sind dafür die LID Funktionen langsamer.

Ich muss mich also jedesmal entscheiden, ob ich mehr Wert auf Geschwindigkeit oder mehr Wert auf geringen Speicherverbrauch lege. Außerdem sollte man sich natürlich Gedanken machen, ob die ganzen Überlegungen überhaupt relevant sind - eine Liste mit 5-50 Elementen, die pro Minute nur einmal durchlaufen wird, lohnt kaum eine Optimierung (außer "aufhübschen" mit LINQ )

Beispiel: Während deine lineare Liste zum Finden eines Elements durchschnittlich 1ms*1/2*n benötigt, benötigt meine Hashtable immer 5ms.
Hat deine Liste 1 Element, brauchst du 1ms zum Finden des Elements. Ich 5ms.
Hat deine Liste 1000 Elemente, brauchst du durdchschnittlich eine halbe Sekunde zum Finden eines Elements. Ich 5ms.
Hat deine Liste 1000000 Elemente, brauchst du durchschnittlich 50 Sekunden zum Finden eines Elements. Ich 5ms.
Der Unterschied ist also gewaltig.Beispiel: Während deine lineare Liste zum Finden eines Elements durchschnittlich 1ms*1/2*n benötigt, benötigt meine Hashtable immer 5ms.
Hat deine Liste 1 Element, brauchst du 1ms zum Finden des Elements. Ich 5ms.
Hat deine Liste 1000 Elemente, brauchst du durdchschnittlich eine halbe Sekunde zum Finden eines Elements. Ich 5ms.
Hat deine Liste 1000000 Elemente, brauchst du durchschnittlich 50 Sekunden zum Finden eines Elements. Ich 5ms.
Der Unterschied ist also gewaltig.

Ich grabe diesen Thread jetzt nochmal aus
Mein Informatik Lehrer hat uns erklärt (als wir über Access sprachen) das "Je mehr Inhalte eine Tabelle hätte desto länger dauert es bis ein Datensatz gefunden sei". Stimmt das ? Warum nutz Access nicht sowas geniales wie eine Hashtable ?

weil es auch bei einer Hashtable logischer weise langsamer werden muss, kann mich natürlich auch irren, aber glaube kaum

Jedes Element in einer Hashtable hat einen Schlüssel. Dieser Schlüssel identifiziert das Element eindeutig.
Auf den Schlüssel wird die Hashfunktion angewendet, deren Ergebnis (der Hash) bestimmt die Position des Elements in der Tabelle. Der Hash wird gewöhnlich übrigens nicht gespeichert, da er einzig und allein den Zweck hat, die Position des Elements festzulegen und er sich durch diese implizit ergibt.
Wenn man nun ein Element sucht, dann muss man den Schlüssel kennen. Setzt der Schlüssel sich also aus Vor- und Nachname zusammen, muss man die kennen und findet recht schnell (man kann da wie gesagt unter Idealbedingungen grob mit konstantem Zeitaufwand rechnen) das gesuchte Element.
Hier sitzt aber auch das Problem: Bei einer Datenbank weiß man vorher oft nicht, was genau man will. D.h. man kennt z.B. Vor- und Nachnamen einer Person nicht, sondern nur das Alter. Damit lässt sich eine Hashtable erstmal nicht auf eine Datenbanktabelle anwenden.
Was man aber machen kann, ist einzelne Spalten zu indizieren und davon eine Hashtable anzulegen. Der Primärschlüssel erfüllt solche Anforderungen: Er ist pro Element einzigartig in der Tabelle. Eine einfache Hashfunktion für einen Primärschlüssel wäre zum Beispiel f(x) := x mod 997. Das wird auch durchaus so praktiziert. Ob nun gerade von Access, weiß ich allerdings nicht.

Ein Wort zu den Idealbedingungen: Bei einer Hashtable ist es am besten, wenn man möglichst viel über die Anzahl der Elment weiß. Um bei konstantem Zeitaufwand zu bleiben, muss man Kollisionen (zwei Elemente erhalten den selben Hash) möglichst vermeiden. Das geht durch große Hashtables und gute Hashfunktionen. Große Hashtables benötigen aber mehr Speicher (pro Zeile die Größe einer Speicheradresse). Je stärker also die Anzahl der Elemente in der Hashtable schwankt, desto schlechter ist es für die Geschwindigkeit auf der einen und den Speicherverbrauch auf der anderen Seite.