2

次の形式の 1.7G ファイルがあります。

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

基本的に、Stringはキーで、Longはハッシュマップの値です。アプリケーションで何かを実行する前に初期化することに関心があります。

私の現在のコードは次のとおりです。

  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);
                }

これは完了するのに約 12 分かかります。これを行うためのより良い方法があると確信しているので、助けや指針をいただければ幸いです。

ありがとう

EJP 提案のように更新しますか?

EJP さん、あなたの提案に感謝します。これがあなたの意図したものであることを願っています。これが間違っている場合は修正してください

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();
      }
    }
4

2 に答える 2

4

  1. FileInputStream をラップした BufferedInputStream をラップした DataInputStream を使用します。

  2. 繰り返しごとに少なくとも 4 つのシステム コールを呼び出し、長さと現在のサイズをチェックし、文字列と長さを取得するための読み取り回数を誰が知っているかを実行する代わりに、EOFException が発生するまで readUTF() と readLong() を呼び出すだけです。

于 2012-12-11T11:59:18.027 に答える
2

その場で使用できるようにファイルを作成します。つまり、この方法でロードしません。可変長のレコードがあるため、各レコードの位置の配列を作成し、キーを順番に配置して、データのバイナリ検索を実行できます。(または、カスタム ハッシュ テーブルを使用できます) 次に、データ オブジェクトに変換されるのではなく、データが実際にファイルに格納されているという事実を隠すメソッドでこれをラップできます。

これをすべて行うと、「ロード」フェーズが冗長になり、それほど多くのオブジェクトを作成する必要がなくなります。

これは長い例ですが、うまくいけば何が可能かを示しています。

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;
    }
}

2 GB の生データを生成し、100 万回のルックアップを実行します。ロードとルックアップがほとんどヒープを使用しないように記述されています。( << 1MB )

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

ハッシュ テーブル ルックアップを使用すると、O(ln N) ではなく O(1) であるため、ルックアップごとに高速になりますが、実装がより複雑になります。

于 2012-12-11T12:09:16.923 に答える