Sortierte DatenListe am schnellsten durchlaufen

[Dit_]

Hallo follgendes Problem

ich habe eine DatenListe.
Auszug:

...
212789184 212789191 PRI
212792264 212792271 USA
212792272 212792279 PRI
212792280 212792287 USA
212792288 212792319 PRI
212792320 212793199 USA
212793200 212793207 VIR
212793208 212793215 PRI
212793216 212794783 USA
212794784 212794791 VIR
212794792 212794799 USA
212794800 212794815 VIR
212794816 212794879 USA
...

Insgesamt sind es ca 103000 zeilen(!).

Wie man sieht es sind die s.g. IP Blocks. Die Liste ist aufsteigend sortiert.

Ich bekomme eine IP Adresse und rechen IP Code aus. zB aus IP "a.b.c.d" bekomme ich IP code 212794820. Jetzt laufe ich die Liste durch und pruefe Zeile für Zeile
ob mein IP Code zwischen den ersten und zweiten Zahl liegt, wenn ja, dann bekomme ich als Ergebnis der LänderCode.



In diesem Beispiel liegt 212794820 zwischen 212794816 und 212794879 . Ergebnis also USA (letzte Zeile aus dem Auszug. siehe oben)


Problem:
Wie gesagt, es sind über 103000 Zeilen und die Liste ist in einer Datei file.log gespeichert. Zugriff also über FileReader/BufferedReader. Um eine Ip Adresse zu bearbeiten brauche ich bis zu 900 ms, besonders lange dauert das wenn die Liste fast bis zum Ende bearbeitet werden muss.

Frage also, wie kann ich das am schnellsten erledigen? Das ist wichtig da ich eine UserListe in einer JTable habe und diese wird mit allen UserInformationen alle 1 bis 2 sekunden aktualisiert. d.h. bei
20 User wird das zu lange dauern bis alle IPs bestimmt sind.

Ich dachte ich mache mal ein String[][][] feld und dann mit Bisektionssuche nach passendem Block suchen... aber bevor ich das mache frage lieber nach

public String getCountryByIp(String ip) {
		long c = getIPCode(ip);
		FileReader fileReader = null;
		String a = "";
		String[] b;
		long x;
		long y;
		try {
			fileReader = new FileReader("src/file/ipcodes.log"); // 500 - 1000 ms
			BufferedReader reader = new BufferedReader(fileReader);

			a = reader.readLine();
			while (a != null) {
				b = a.split(" ");
				x = Long.parseLong(b[0]);
				y = Long.parseLong(b[1]);
				if (c >= x && c <= y) {
					return b[2];
				}
				a = reader.readLine();
			}

		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
		
		return "Not found...";
	}

P.S.
So rechne ich IP Code aus.

202.186.13.14
A = 202
B = 186
C = 13
D = 14

16777216*A + 65536*B + 256*C + D
also
16777216*202 + 65536*186 + 256*13 + 14 = 3401190670

Danke schon mal.

 

[LoR]

Versuchs mal damit:

public class IPBlock implements Comparable<IPBlock> {

    private long minIP;
    private long maxIP;
    private String country;

    public IPBlock(long minIP) {
        this(minIP, 0, null);
    }

    public IPBlock(long minIP, long maxIP, String country) {
        this.minIP = minIP;
        this.maxIP = maxIP;
        this.country = country;
    }

    public String getCountry() {
        return country;
    }

    public void setCountry(String country) {
        this.country = country;
    }

    public long getMinIP() {
        return minIP;
    }

    public void setMinIP(long minIP) {
        this.minIP = minIP;
    }

    public long getMaxIP() {
        return maxIP;
    }

    public void setMaxIP(long maxIP) {
        this.maxIP = maxIP;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final IPBlock other = (IPBlock) obj;
        if (this.minIP != other.minIP) {
            return false;
        }
        return true;
    }

    @Override
    public int hashCode() {
        return (int) (this.minIP ^ (this.minIP >>> 32));
    }

    public int compareTo(IPBlock o) {
        if (this.minIP < o.minIP) {
            return -1;
        } else if (this.minIP > o.minIP) {
            return +1;
        }
        return 0;
    }

    @Override
    public String toString() {
        return this.country;
    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;

public class Main {

    public static void main(String[] args) {
        //Eindeutigkeit garantieren
        SortedSet<IPBlock> set = new TreeSet<IPBlock>();

        //Beispieldaten einfügen
        set.add(new IPBlock(212789184, 212789191, "PRI"));
        set.add(new IPBlock(212792264, 212792271, "USA"));
        set.add(new IPBlock(212792272, 212792279, "PRI"));
        set.add(new IPBlock(212792280, 212792287, "USA"));
        set.add(new IPBlock(212792288, 212792319, "PRI"));
        set.add(new IPBlock(212792320, 212793199, "USA"));
        set.add(new IPBlock(212793200, 212793207, "VIR"));
        set.add(new IPBlock(212793208, 212793215, "PRI"));
        set.add(new IPBlock(212793216, 212794783, "USA"));
        set.add(new IPBlock(212794784, 212794791, "VIR"));
        set.add(new IPBlock(212794792, 212794799, "USA"));
        set.add(new IPBlock(212794800, 212794815, "VIR"));
        set.add(new IPBlock(212794816, 212794879, "USA"));

        List<IPBlock> searchlist = new ArrayList<IPBlock>(set);

        //Testen wir das ganze mal :)
        System.out.println(searchIPBlock(searchlist, 212794820));
    }

    /**
     * Suchfunktion
     *
     * @param searchlist
     * @param searchip
     * @return IPBlock, ansonsten null
     */
    private static IPBlock searchIPBlock(List<IPBlock> searchlist, int searchip) {
        int index = Collections.binarySearch(searchlist, new IPBlock(searchip));
        index = index >= 0 ? index : (-(index) - 2);
        IPBlock block = index >= 0 && index < searchlist.size() ? searchlist.get(index) : null;
        return block != null && searchip <= block.getMaxIP() ? block : null;
    }
}

Das sollte relativ effizient sein. Kannst ja mal testen wie schnell das ganze jetzt ist

Gruß

//EDIT max. IP eingefügt

 

[JohannisderKaeufer]

Angenommen du möchtest das ganze für 20 Datensätze machen.

Dann liest du dein Dokument momentan 20 mal ein. Das ist sehr ungünstig.

Übergib doch gleich eine Liste mit den 20 Datensätzen. Lies das Dokument 1 mal ein und überprüfe jede Zeile auf die 20 Datensätze. und gib eine map zurück.

getCountrys for ips{List<String> liste}{
file einlesen
Map result = new Map()
while(file.nochNichtAmEnde){
     zeile einlesen
     for(String ip:liste){
        if(ip == zeile){
            map.put(ip, land)
            liste.remove(ip)
            if(liste.isEmpty()){
                 return map;
            }
            
        }
     }
}
return map;
}

Statt einem String[][][] kann man auch ein Objekt erstellen

class IPBereich{
Long anfang
Long ende
String land
}

Das könnte man einmal in eine Liste einlesen, sofern genügend Speicher vorhanden ist und dann mit einer Binären Suche rangehen.

Eine weitere Alternative wäre das ganze in einen Baum zu packen.

class IPTREE{
Long anfang
Long ende
String land
IPTREE kleinerAlsAnfang
IPTREE groesserAlsEnde
}

Die Schwierigkeit hierbei besteht, dann darin einen möglichst ausgeglichenen Baum zu bekommen.


Zu guter letzt würde ich noch das Caching empfehlen
Es ist ja meist so, daß sich ips nicht im Sekundentakt ändern und die Länder bleiben auch die selben, sofern nicht exzessiv mit proxys gearbeitet wird.
Also wie wäre es einen Cache anzulegen.
Eine Map bei der ein Userobjekt der Key ist und dort ein Objekt vom Typ IPBereich liegt.
Wenn aktualisiert wird wird zuerst im Cache geschaut ob der User drin ist, dann ob die Ip immer noch im selben IPBereich liegt. Erst wenn eins davon fehlschlägt in der Datei nachschauen.

 

[Marco13]

Hab' die anderen Antworten jetzt nicht gelesen, aber bei "sortierte Liste durchsuchen" kam mit auch spontan die "Bisektionssuche" bzw. Collections (Java Platform SE 6) in den Sinn. Andere Datenstrukturen sind natürlich eine "grobgranualarere" Verbesserung - ob die für die passt, musst du wissen...

 

[FArt]

Ein einfacher Weg: nutze eine InMemory-Datenbank, z.B. HSQLDB. Die einzige Tabelle ist schnell angelegt (Datei einlesen, einzelne Datensätze schreiben) und jede weitere Suche ist ein schneller (und einfacher) Select...

 

[faetzminator]

Wenn du die Daten nicht in ein Set schmeissen willst oder kannst (z.B. wegen der Datenmenge), kannst du auf die Binary Search Binäre Suche ? Wikipedia zurückgreifen.

 

[Janus]

Was lange dauert ist das Einlesen der Datei. In nur 100k Zeilen nach etwas im Speicher zu suchen sollte mit fast jeder Methode schnell genug sein.

Um deine Methode zu beschleunigen musst du das ständige Einlesen der vollständigen Datei wegrationalisieren. Wenn du sicher sein kannst, dass die Datei klein genug bleibt, lies sie nur ein, wenn sie sich ändert und halte sie ansonsten im Speicher.
Solltest du nicht sicher sein können, ob die Datei vollständig in den Speicher passt, ist es häufig ein günstiger Ansatz, die eine große Datei in mehrere kleine zu zerlegen, die jeweils bestimmte Blöcke enthalten. Wenn du etwas suchst, kannst du also die Suche auf eine einzige, kleinere Datei beschränken.

 

[faetzminator]

Dir ist es egal, ob die Funktion eine max. Laufzeit von [c]O(log n)[/c], [c]O(n)[/c] oder vielleicht sogar [c]O(n^2)[/c] hat? Mal abgesehen davon, dass in [c]java.util.Arrays[/c] bereits eine solche Suche angeboten wird, es muss nur noch schnell ein Comparator geschrieben werden: http://java.sun.com/javase/6/docs/api/java/util/Arrays.html#binarySearch%28T[],%20T,%20java.util.Comparator%29

 

[Janus]

Dir ist es egal, ob die Funktion eine max. Laufzeit von [c]O(log n)[/c], [c]O(n)[/c] oder vielleicht sogar [c]O(n^2)[/c] hat?

Eine Laufzeit größer O(n) für das Suchen in einer Liste erscheint mir doch etwas weit hergeholt.

 

[faetzminator]

Eine Laufzeit größer O(n) für das Suchen in einer Liste erscheint mir doch etwas weit hergeholt.

Natürlich, ist in dem Fall auszuschliessen. Dann hätten wir die "normale Methodik" mit [c]O(n)[/c]. Aber warum diese implementieren, wenn uns Java mit etwa gleich viel eigenem Code das ganze in [c]O(log n)[/c] erledigen kann ?

 

[Landei]

Würde sich hier nicht ein TreeSet (oder vielleicht TreeMap) anbieten? Ein TreeSet ist immer geordnet, und Elemente werden mittels binärer Suche lokalisiert.

 

[Ebenius]

Schneller und einfacher als mit Arrays.binarySearch(...) wird's wohl nicht werden, oder?

Ebenius

 

[Marco13]

Eine Laufzeit größer O(n) für das Suchen in einer Liste erscheint mir doch etwas weit hergeholt.

Nicht unbedingt, wenn man das Pessimierungsprinzip Schleifenmultiplikation beherzigt. Schön beschrieben ist das z.B. im Abschnitt 1.2.3, Seiten 9 und 10 von http://www.ru-eschweilerhof.de/cs/fb17/algodat/skript.pdf

 

[Janus]

Nicht unbedingt, wenn man das Pessimierungsprinzip Schleifenmultiplikation beherzigt. Schön beschrieben ist das z.B. im Abschnitt 1.2.3, Seiten 9 und 10 von http://www.ru-eschweilerhof.de/cs/fb17/algodat/skript.pdf

Ich kann dir auch Bubblesort implementieren und nebenbei eine Gaswolke simulieren, aber was sollte mir das bringen? Sachlich bleiben.

 

[ThreadPool]

Eine Laufzeit größer O(n) für das Suchen in einer Liste erscheint mir doch etwas weit hergeholt.

Dafür brauchst du nur eine echte verkette Liste. [1]


[1] ArrayList ist keine verkette Liste, es ist ein einfaches Array das sich nach aussen verhält wie eine Liste.

 

[faetzminator]

Dafür brauchst du nur eine echte verkette Liste. [1]

Da wäre Wort Case ebenfalls [c]O(n)[/c]. Da wäre der Vorgang einfach

x = erstes element
für element x != null 
    wenn element = gesuchtes
        abbruch
    x = nächstes element

 

[braindamage]

Hi, hab nicht den ganzen text nicht! durchgelesen aber die interpolationssuche ist echt schnell.
du müsste deine daten in einem array halten.
schaumal hier, ist mit besipiel
Interpolationssuche ? Wikipedia

läuft in O(log log n) => log log 100 000 <= 10 schritten, habs net gerechnet denk auch <=5

 

[Ebenius]

Okay, um nochmal auf den Themeneröffner einzugehen: Wenn die Liste tatsächlich nicht im Speicher sein darf, dann würde ich ein Binärformat mit fester Länge verwenden und mit NIO drauf zugreifen. Notfalls mit DataInputStream.

Wenn's Text bleiben soll/muss: Mach doch einfach 256 Dateien und leg Deine Infos im Cluster (nach Class A getrennt) ab.

Die Konvertierung der Blöcke in einen Integer liest sich so übrigens besser:

final int i = a << 24 | b << 16 | c << 8 | d;

Darüber hinaus: String.split() ist recht langsam. Um 100.000 mal den String [c]abcdefghi jklmnop USA[/c] mit [c]split(" ")[/c] aufzuteilen braucht mein System rund 1.2 Sekunden. Für indexOf und substring braucht's nur <100ms.

    final String s = "abcdefghi jklmnop USA";
    System.out.println(new Date() + " Splitting...");
    long t = System.currentTimeMillis();
    for (int i = 0; i < 100000; i++) {
      final int splitAt1 = s.indexOf(' ');
      final int splitAt2 = s.indexOf(' ', splitAt1 + 1);
      final String sub1 = s.substring(0, splitAt1);
      final String sub2 = s.substring(splitAt1 + 1, splitAt2);
      sub1.toString();
      sub2.toString();
    }
    System.out.println("Split1 took "
          + (System.currentTimeMillis() - t)
          + "ms");
    System.out.println(new Date() + " Splitting...");

    t = System.currentTimeMillis();
    for (int i = 0; i < 100000; i++) {
      s.split(" ").toString();
    }
    System.out.println("Split2 took "
          + (System.currentTimeMillis() - t)
          + "ms");

Thu Jan 14 18:06:39 CET 2010 Splitting...
Split1 took 86ms
Thu Jan 14 18:06:39 CET 2010 Splitting...
Split2 took 1296ms

HTH, Ebenius

 

[braindamage]

warum darf die liste nciht im spiecher sein? sein doch nur 400kb + vielleicht nochmal max 800kb...

 

[Dit_]

Danke euch allen!
Ich muss jetzt wohl alle vorgeschlagenen Methoden ausprobieren.
Meine Datei mit IPBlocks ist 2,5 mb groß. Was genau meint ihr mit Daten im Speicher halten ?

 

[LoR]

Danke euch allen!
Ich muss jetzt wohl alle vorgeschlagenen Methoden ausprobieren.
Meine Datei mit IPBlocks ist 2,5 mb groß. Was genau meint ihr mit Daten im Speicher halten ?

Naja statt bei jeder Anfrage die IPBlocks Datei einzulesen könntest du die Datei einmal einlesen und dann auf diesen Daten arbeiten. Darauf zielen hier auch so gut wie alle Antworten ab. Vermutlich ändert sich die Datei ja auch nicht ständig oder?

Wenn nein, dann kannst du es so machen (ist im Prinzip genau das gleiche was ich schon zuvor gepostet habe):

public class IPBlock implements Comparable<IPBlock> {

    private long minIP;
    private long maxIP;
    private String country;

    public IPBlock(long minIP) {
        this(minIP, 0, null);
    }

    public IPBlock(long minIP, long maxIP, String country) {
        this.minIP = minIP;
        this.maxIP = maxIP;
        this.country = country;
    }

    public String getCountry() {
        return country;
    }

    public void setCountry(String country) {
        this.country = country;
    }

    public long getMinIP() {
        return minIP;
    }

    public void setMinIP(long minIP) {
        this.minIP = minIP;
    }

    public long getMaxIP() {
        return maxIP;
    }

    public void setMaxIP(long maxIP) {
        this.maxIP = maxIP;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final IPBlock other = (IPBlock) obj;
        if (this.minIP != other.minIP) {
            return false;
        }
        return true;
    }

    @Override
    public int hashCode() {
        return (int) (this.minIP ^ (this.minIP >>> 32));
    }

    public int compareTo(IPBlock o) {
        if (this.minIP < o.minIP) {
            return -1;
        } else if (this.minIP > o.minIP) {
            return +1;
        }
        return 0;
    }

    @Override
    public String toString() {
        return this.country;
    }
}

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws Exception {
        List<IPBlock> searchlist = readIPBlocks("C:/ipblocks.txt");
        System.out.println(searchIPBlock(searchlist, 212794820));
    }

    private static List<IPBlock> readIPBlocks(String filename) throws IOException {
        List<IPBlock> blocklist = new LinkedList<IPBlock>();
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new FileReader(filename));
            String line;
            while ((line = reader.readLine()) != null) {
                String[] str = line.split(" ");
                long minIP = Long.parseLong(str[0]);
                long maxIP = Long.parseLong(str[1]);
                String country = str[2];
                IPBlock block = new IPBlock(minIP, maxIP, country);
                blocklist.add(block);
            }
        } finally {
            if (reader != null) {
                reader.close();
            }
        }
        Collections.sort(blocklist);
        return blocklist;
    }

    /**
     * Suchfunktion
     *
     * @param searchlist
     * @param searchip
     * @return IPBlock, ansonsten null
     */
    private static IPBlock searchIPBlock(List<IPBlock> searchlist, int searchip) {
        int index = Collections.binarySearch(searchlist, new IPBlock(searchip));
        index = index >= 0 ? index : (-(index) - 2);
        IPBlock block = index >= 0 && index < searchlist.size() ? searchlist.get(index) : null;
        return block != null && searchip <= block.getMaxIP() ? block : null;
    }
}