Accélération de la lecture des fichiers

Question

J'ai un fichier de 1,7G avec le format suivant :

String Long String Long String Long String Long ... etc

Essentiellement, Chaîne de caractères est une clé et Long est une valeur dans un hashmap que je souhaite initialiser avant d'exécuter quoi que ce soit d'autre dans mon application.

Mon code actuel est :

  RandomAccessFile raf=new RandomAccessFile("/home/map.dat","r");
                raf.seek(0);
                while(raf.getFilePointer()!=raf.length()){
                        String name=raf.readUTF();
                        long offset=raf.readLong();
                        map.put(name,offset);
                }

Cela prend environ 12 minutes et je suis sûr qu'il y a de meilleures façons de faire, donc j'apprécierais toute aide ou indication.

merci

---

Mise à jour comme dans la suggestion de l'EJP ?

EJP : merci pour votre suggestion et j'espère que c'est ce que vous vouliez dire. Corrigez-moi si c'est faux

DataInputStream dis=null;
    try{
     dis=new DataInputStream(new BufferedInputStream(new FileInputStream("/home/map.dat")));
     while(true){
       String name=dis.readUTF();
       long offset=dis.readLong();
       map.put(name, offset);
     }
    }catch (EOFException eofe){
      try{
        dis.close();
      }catch (IOException ioe){
        ioe.printStackTrace();
      }
    }

Answer 1

1. Utilisez un DataInputStream enveloppé d'un BufferedInputStream enveloppé d'un FileInputStream.

2. Au lieu d'effectuer au moins quatre appels système par itération, de vérifier la longueur et la taille actuelle et d'effectuer qui sait combien de lectures pour obtenir la chaîne et le long, il suffit d'appeler readUTF() et readLong() jusqu'à ce que vous obteniez une EOFException.

Answer 2

Je construirais le fichier de manière à ce qu'il puisse être utilisé à la place, c'est-à-dire sans chargement de cette manière. Comme vous avez des enregistrements de longueur variable, vous pouvez construire un tableau de l'emplacement de chaque enregistrement, puis placer la clé dans l'ordre afin de pouvoir effectuer une recherche binaire des données. (Ou vous pouvez utiliser une table de hachage personnalisée) Vous pouvez ensuite envelopper cela avec une méthode qui cache le fait que les données sont en fait stockées dans un fichier au lieu d'être transformées en objets de données.

Si vous faites tout cela, la phase de "chargement" devient superflue et vous n'aurez pas besoin de créer autant d'objets.

---

Il s'agit d'un long exemple mais qui, espérons-le, montre ce qui est possible.

import vanilla.java.chronicle.Chronicle;
import vanilla.java.chronicle.Excerpt;
import vanilla.java.chronicle.impl.IndexedChronicle;
import vanilla.java.chronicle.tools.ChronicleTest;

import java.io.IOException;
import java.util.*;

public class Main {
    static final String TMP = System.getProperty("java.io.tmpdir");

    public static void main(String... args) throws IOException {
        String baseName = TMP + "/test";
        String[] keys = generateAndSave(baseName, 100 * 1000 * 1000);

        long start = System.nanoTime();
        SavedSortedMap map = new SavedSortedMap(baseName);
        for (int i = 0; i < keys.length / 100; i++) {
            long l = map.lookup(keys[i]);
//            System.out.println(keys[i] + ": " + l);
        }
        map.close();
        long time = System.nanoTime() - start;

        System.out.printf("Load of %,d records and lookup of %,d keys took %.3f seconds%n",
                keys.length, keys.length / 100, time / 1e9);
    }

    static SortedMap<String, Long> generateMap(int keys) {
        SortedMap<String, Long> ret = new TreeMap<>();
        while (ret.size() < keys) {
            long n = ret.size();
            String key = Long.toString(n);
            while (key.length() < 9)
                key = '0' + key;
            ret.put(key, n);
        }
        return ret;
    }

    static void saveData(SortedMap<String, Long> map, String baseName) throws IOException {
        Chronicle chronicle = new IndexedChronicle(baseName);
        Excerpt excerpt = chronicle.createExcerpt();
        for (Map.Entry<String, Long> entry : map.entrySet()) {
            excerpt.startExcerpt(2 + entry.getKey().length() + 8);
            excerpt.writeUTF(entry.getKey());
            excerpt.writeLong(entry.getValue());
            excerpt.finish();
        }
        chronicle.close();
    }

    static class SavedSortedMap {
        final Chronicle chronicle;
        final Excerpt excerpt;
        final String midKey;
        final long size;

        SavedSortedMap(String baseName) throws IOException {
            chronicle = new IndexedChronicle(baseName);
            excerpt = chronicle.createExcerpt();
            size = chronicle.size();
            excerpt.index(size / 2);
            midKey = excerpt.readUTF();
        }

        // find exact match or take the value after.
        public long lookup(CharSequence key) {
            if (compareTo(key, midKey) < 0)
                return lookup0(0, size / 2, key);
            return lookup0(size / 2, size, key);
        }

        private final StringBuilder tmp = new StringBuilder();

        private long lookup0(long from, long to, CharSequence key) {
            long mid = (from + to) >>> 1;
            excerpt.index(mid);
            tmp.setLength(0);
            excerpt.readUTF(tmp);
            if (to - from <= 1)
                return excerpt.readLong();
            int cmp = compareTo(key, tmp);
            if (cmp < 0)
                return lookup0(from, mid, key);
            if (cmp > 0)
                return lookup0(mid, to, key);
            return excerpt.readLong();
        }

        public static int compareTo(CharSequence a, CharSequence b) {
            int lim = Math.min(a.length(), b.length());
            for (int k = 0; k < lim; k++) {
                char c1 = a.charAt(k);
                char c2 = b.charAt(k);
                if (c1 != c2)
                    return c1 - c2;
            }
            return a.length() - b.length();
        }

        public void close() {
            chronicle.close();
        }
    }

    private static String[] generateAndSave(String baseName, int keyCount) throws IOException {
        SortedMap<String, Long> map = generateMap(keyCount);
        saveData(map, baseName);
        ChronicleTest.deleteOnExit(baseName);

        String[] keys = map.keySet().toArray(new String[map.size()]);
        Collections.shuffle(Arrays.asList(keys));
        return keys;
    }
}

génère 2 Go de données brutes et effectue un million de recherches. Il est écrit de telle manière que le chargement et la recherche utilisent très peu de heap. ( << 1 MB )

ls -l /tmp/test*
-rw-rw---- 1 peter peter 2013265920 Dec 11 13:23 /tmp/test.data
-rw-rw---- 1 peter peter  805306368 Dec 11 13:23 /tmp/test.index

/tmp/test created.
/tmp/test, size=100000000
Load of 100,000,000 records and lookup of 1,000,000 keys took 10.945 seconds

L'utilisation d'une table de hachage serait plus rapide par consultation car elle est O(1) au lieu de O(ln N), mais plus complexe à mettre en œuvre.