Hallo,

ich arbeite an einem Konzept für eine App, die einen Sweep-Algorithmus verwendet, um in einem zeitrkitischen Umfeld effizient Elemente auszuwählen. Ich kann sicherstellen, dass die Elemente im Hinblick auf eine ihrer Eigenschaften aufsteigend sortiert sind - das hilft (bzw. ist eigentlich Voraussetzung) beim Sweep-Verfahren, allerdings kann es trotzdem sein, dass die weitere Verarbeitung zur Identifikation des oder der gesuchten Elemente noch immer eine größere Grundgesamtheit aufweist. Erschwerend kommt hinzu, dass die Identifikation des bzw. der gesuchten Elemente nicht einfach mittels größer/kleiner funktioniert, sondern durch Berechnungen, die etwas komplexere Trigonometische Funktionen enthalten (also z.B. auch Sinus/Cosinus usw.) - und davon dann in, sagen wir, 1/2 Sekunde vielleicht bis zu 100 und das auch u.U. immer wieder.

Soviel vorweg, damit Ihr es Einordnen könnt, jetzt meine Frage: Wie "halte" ich am günstigsten die Daten in diesem zeitkritischen (!!) Umfeld?

Idee 1 ist, ein Array mit Dictionaries aufzubauen und dann den Sweep zunächst über arrayFilteredByPredicate abzubilden (wie gesagt, die Elemente sind soritert). Weiterverarbeitung dann mit der Ergebnismenge ... Die Daten werden als plist im Documents-Verzeichnis gespeichert und von dort geladen, ansonsten aber im Speicher gehalten. Vorteil könnte sein, dass ich keinen CoreDate-Overhead habe (??), Nachteil, dass das Ganze etwas groß und "teuer" wird. 10.000 Elemente können durchaus dabei rum kommen.

Idee 2 ist, CoreData zu verwenden. Vorteil wäre sicher die optimierte Datenhandling, Nachteil (??) aber der besagte CoreData-Overhead, falls es ihn überhaupt gibt. CD würde mir auch an anderer Stelle helfen, das ist aber erstmal egal.

Ich suche also nach der im Hinblick auf die Verarbeitungsgeschwindigkeit besten Variante und bin durchaus willens, architektonische Eleganz dafür dranzugeben.

Ja, ich/wir werden schon sehen, dass wir das Optimum aus der Berechnung herausquetschen. Dass wir mit Lookups arbeiten könnten ist eine Idee. Ein Teil der Berechnungen wie z.B. Normalen usw. werden vorbereitet.

Mir geht es in erster Linie um die Datenhaltung - CoreData oder "inline"? - auch weil ich nicht unbedingt das RAM zumüllen möchte. Zeitoptimierung steht an erster Stelle. Nur muss ich im Hinterkopf behalten, dass es eine ganze Menge Daten geben wird.

Naja, die Algorithmen sind auf dem Papier fertig - also in der Theorie. Ich muss das nicht zwingend in High-Level Objective-C lösen, sondern werde sicher einiges auch mit Memory Operations und Pointer-Verschiebungen machen können (oder wie auch immer), denn die für die Berechnung relevanten Daten sind in ihrer Länge eigentlich statisch.

Im Grunde geht es - vereinfacht und vergesst mal kurz den cos/sin-Kram - um ein Netz von Geraden, die zwischen Punkten aufgespannt werden. Objekte wären zunächst einmal diese Geraden mit ihren Koordinaten. Es ist wirklich fast wie ein Spinnennetz. Die Geraden haben Start- und Endpunkte. Ich haben eine Gerade (Start- und Endpunkt) und möchte ermitteln, welche Gerade(n) geschnitten werden. Dazu identifiziere ich in einem ersten Schritt zunächst mittels Sweep-Algorithmus die in Frage kommenden Geraden (x-Richtung), sortiere das Ergebnis um (y-Richtung), zweiter Sweep-Durchlauf, dann Berechnen.

Im Grunde berechne ich, welche Straße in einer Stadt wie Hamburg gerade von einem Bus überquert wird Naja, hinkt ein wenig, ich weiß, aber kommt schon hin. Stellt es Euch als besonders großes Spiel vor (was es auch nicht ist).