Ist denn überhaupt schon irgendwas implementiert?
Ist denn überhaupt schon einmal gemessen worden wie lange es dauert?
Ist denn überhaupt festgelegt, wie lange es überhaupt dauern darf?
Einfache In-Memory-Lösung in Java, benötigt ca. 70 ms um in 1.000.000 Einträge nach 6 Merkmalen zu durchsuchen.
import java.util.List;
import java.util.Random;
import java.util.logging.Level;
import java.util.logging.Logger;
/**
*
* @author ionutbaiu
*/
public class Search {
public static void main(String[] args) {
Logger log = Logger.getLogger("Search");
log.info("Start Application");
class Item {
int a, b, c, d, e, f;
public Item(int a, int b, int c, int d, int e, int f) {
this.a = a;
this.b = b;
this.c = c;
this.d = d;
this.e = e;
this.f = f;
}
@Override
public String toString() {
return "Item{" + "a=" + a + ", b=" + b + ", c=" + c + ", d=" + d + ", e=" + e + ", f=" + f + '}';
}
}
log.info("Building List");
Random random = new Random(0);
List<Item> list = new LinkedList<>();
for (int i = 0; i < 1_000_000; i++) {
list.add(new Item(random.nextInt(), random.nextInt(), random.nextInt(), random.nextInt(), random.nextInt(), random.nextInt()));
}
log.log(Level.INFO, "List has #{0} items", list.size());
log.log(Level.INFO, "Starting Search {0}", System.currentTimeMillis());
list.stream().filter((item) -> item.a == 1 && item.b == 2 && item.c == 3 && item.d == 1 && item.e == 2 && item.f == 3).forEach(System.out::println);
log.log(Level.INFO, "Search done! {0}", System.currentTimeMillis());
}
}```
Hashing bringt meines Wissens nach Hauptsächlich etwas um die existenz eines Eintrags auszuschliessen.
Primitives Beispiel:
``` public static void main(String[] args) {
System.out.println("Searching for 7, Binary"+Integer.toBinaryString(7));
int hashA = createHash(1,9,5);
int hashB = createHash(5,10);
int hashC = createHash(1,5,7,9);
System.out.println("Can A contain 7 "+canContain(7, hashA));
System.out.println("Can B contain 7 "+canContain(7, hashB));
System.out.println("Can C contain 7 "+canContain(7, hashC));
System.out.println("Can A contain 17 "+canContain(17, hashA));
System.out.println("Can B contain 19 "+canContain(19, hashB));
System.out.println("Can C contain 23 "+canContain(23, hashC));
}
private static int createHash(int...items) {
for(int item: items) {
System.out.println(item+": "+Integer.toBinaryString(item));
}
int hash = 0;
for(int item: items) {
hash |= item;
}
System.out.println("Hash is "+Integer.toBinaryString(hash));
return hash;
}
private static boolean canContain(int searched, int hash) {
boolean canContain = ((hash & searched) == searched);
return canContain;
}```
Gesucht wird die 7, Binär ausgedrückt 0111.
Aus den Daten, also einer Spalte in der Datenbank, wird ein Hashwert gebildet, durch ein Binäres-Oder aller Elemente.
Wenn die 7 nun enthalten sein muss. dann müssen auch alle Binären-Einsen der Sieben im Hash gesetzt sein.
Ist dies nicht, der Fall, dann braucht man auch nicht alle Zahlen durchsuchen und man kann zurückgeben, dass die 7 nicht vorhanden ist.
Wenn im Hash alle 3 Einsen vorhanden sind, dann muss man dennoch den ganzen Datensatz durchgehen um Sicherzustellen ob die 7 Tatsächlich vorhanden ist.
Oder man zieht eine beliebige Anzahl anderer Hashwerte zu Rate. (z.B. Maximum,Minimum in der Spalte)
Probleme gibt es allerdings wenn oft gelöscht wird. Zudem ist die Art und Anzahl der Daten entscheidend gute Hashfunktionen zu finden.
Allerdings sollten solche Dinge von einer guten Datenbank bereits abgedeckt sein, weshalb der Sinn und Zweck dies selbst zu implementieren eher akademischer Natur ist.
