Heiner KückerRange-Map |
|
Home Java-Seite Bit Packed Array ASM Improved heterogene Map, HMap Constraint Code Generator JSP WorkFlow PageFlow FlowControl Page Flow Engine Web Flow Engine Control_and_Command JSP_Spreadsheet Code-Generator für Option-Either-Stil in Java verbesserter Comparator Fluent-Interface Code-Generator auf Basis einer Grammatik Visitor mit Multidispatch for-Schleife mit yield-return Kognitions-Maschine semantisches Netz Domain Parser Codegenerator_für hierarchische Datenstrukturen Expression_Engine Formula_Parser Thread Preprocessor State Transition Engine AspectJ Java_Explorer DBF_Library Kalender_Applet SetGetGen BeanSetGet CheckPackage LineNumbers GradDms Excel-Export StringTokenizer JspDoc JspCheck JSP-Schulung Java Server Pages Struts Ascii-Tabellen- Layouter Ascii-Baum- Layouter Ascii-Art-Fluss- Diagramm- Parser AsciiArt AssignmentMatrix Layouter StringSerial Silbentrennung JDBC_Schlüssel- Generierung bidirektional/ unidirektional gelinkte Liste Java_Sitemap Generator XmlBuilder RangeMap StringFormatter VersionSafe XCopy JTextField CommandLine- ParamReader Bitmap-Grafik MultiMarkable- Buffered- InputStream JavaCache JdomUtil CollectionUtil XML Really Pull Parser Log-Filter Remote-Protokoll Sudoku-Generator Delegation statt Mehrfachvererbung Disjunct Interval Set WebCam_Demo Weiterentwicklung_Java Alaska-XBase++-Seite Projekte Philosophien Techniken Konzepte Sudoku Kontakt / Impressum Links SiteMap Letzte Aktualisierung: 20.08.2005 |
Range-Map
Die RangeMap ist eine performanceoptimierte Datenstruktur zum
Zuordnen eines Wertes zu einem Band/Bereich von Werten
(Nummernband). Die JDK-TreeMap sorgt für das Ausbalancieren des Baumes beim Einfügen und für das performante Suchen beim Abfragen der Range-Map. Gegeben sei folgendes Problem: Es gibt konkrete Nummern (Gerätenummer) die jeweils zu einem Nummernband (Nummernbereich von bis) gehören. Es werden clusterweise wechselnd Geräte hergestellt, die jeweils ein zusammengehörendes Band von laufenden Nummern bekommen. An die Applikation werden demzufolge wechselnd Anfragen zu bestimmten konkreten Nummern gestellt, für die ermittelt werden muss, zu welchem Bereich sie gehören. Die Nummernbänder überlappen sich nicht. Es sollte nicht vorkommen, dass kein Treffer gefunden wird. Es ergibt sich folgende Datenstruktur in der Datenbank: ITEM_FROM NUMBER ITEM_TO NUMBER ITEM_TYP NUMBER Ich will also anhand der Geräte-Nummer die Artikel-Nummer (Geräte-Typ) herausbekommen. Das alles soll ziemlich performant sein. Von der Datenbank hole ich den passenden Datensatz per SELECT ... WHERE ITEM_FROM <= ? AND ITEM_TO >= ? Ein WHERE IN ... hilft mir hier nicht. Ich weiss nicht, ob mir hier ein Index auf der DB hilft. Beim Clipper gab es einen SET SOFTSEEK ON - Schalterder steuerte, dass beim Index-Lookup der nächst passende Treffer ermittelt wurde. Zwischen der Businesslogik und der DB-Schicht liegt natürlich ein Cache. Normalerweise arbeitet ein Cache mit einer Key-Value-Kombination, also HashMap. Das klappt in diesem Fall nicht, da das Prinzip des Hashes auf einer möglichst weiten Spreizung konkreter Werte im Wertebereich beruht. Also brauche ich eine RangeMap.
Also ich habe eine Struktur mit einem Key von bis und einem Value in. Ich dachte mir nun, nehme ich eine TreeMap. Die Suche erfolgt binär und nicht linear (was ziemlich langsam wäre). Der Baum wird von der JDK-Klasse balanciert, Klasse. Nur muss ich die Methoden compareTo und equals so ummodeln, dass beim Einfügen in die Map (put) nach der Range sortiert wird. Beim get muss aber nach Range und Wert verglichen werden. Nun wollte ich aber die JDK-Klasse nicht aufdröseln oder neu implementieren. Deshalb gibt es eine abstrakte Hilfs-Klasse RangeOrPoint, die entweder eine Range (Bereich) oder ein Point (konkreter Wert) sein kann und in compareTo und equals per instanceof entscheidet, wie der Vergleich ausgeht: equals liefert true, wenn Key in Range. compareTo liefert 0, wenn Key in Range. -1, wenn Key kleiner als Range from. 1, wenn Key grösser als Range to. Im herunterladbaren Zip-File RangeMap.zip findet sich eine Implementation oben beschriebener Lösung. Aufgrund des Feedbacks von der News-Group de.comp.lang.java habe ich die Implementierung so geändert, dass die Unterscheidung um welche konkrete Klasse, Range oder Point, es sich handelt, nicht über instanceof ermittelt wird, sondern jeweils unterschiedliche compareTo-Methoden in den jeweiligen Klassen implementiert sind.
Noch zu tun: Lösung zum Verhindern überlappender Ranges
Siehe hierzu auch den Thread auf der News-Group de.comp.lang.java zu diesem Thema. Download der Quelldateien RangeMap.zip
Achtung: Erweiterungen und Fixes stelle ich ohne Historie
und ohne Ankündigung hier bereit. Lizenzbedingungen:
Die Programme, Quelltexte und Dokumentationen können ohne
irgendwelche Bedingungen kostenlos verwendet werden. |