OSMのデータ構造[1]は分かりやすい。しかし、lineデータや polygonデータのノード(頂点)データは ノード番号であって、座標値ではない。
狭い範囲の地図データであれば、node の座標値をメモリ上で管理できるが、 日本地図とか世界地図ではノード数が多すぎて、数GBのメモリには載りきれない。
５年ほど使ってきたプログラムでは、日本全体のノード座標値データを複数のブロックに分けて、 圧縮してメモリに載せている。一部のブロックだけをキャッシュとして、解凍している。
最終的にはこの方法を継続して使用することになるかも知れないが、できれば、 もっとシンプルな方法でノードの座標値を管理したい。
ファイル読み込みにより多少パフォーマンスが悪くなってもよい。 ノードID、経度、緯度を単純なバイナリ配列(ノードID順)とする。 ノードID の上位何ビットかを ブロックID として、ブロック別のファイルとする。
ノードIDは 8バイトであるが、ブロックID を使えば、ファイル上は 4バイトでよい。 ノード当たり、4+4+4 = 12 バイトとなる。
japan.osm のノード数を 250M と見込んだ場合、3GB となる。 これだけならばメモリに載る大きさであるが、wayデータにも大きなメモリが必要となるため、 node で使うメモリは 1～2 GBとするため、 大半はファイル上に置き、一部をキャッシュとして、メモリに置く。
座標値データの探索はバイナリサーチを使う。 Java の場合、Arrays.binarySearchメソッドを使えば、プログラムは極めて簡単で済む。
探索の引数は osm_id であるが、連続番号など、近い番号が続くケースが多いため、 前回と近いときは、バイナリサーチは使わず、前回の位置から順次探索する方が速い。
完成後は OSMParser とする予定であるが、完成までは Parser とする。
Parserは基本的には OSM XMLファイルの全行をパースする。 属性については無視するものが多いが、処理上のロスは小さいと考え、まずは SAX APIを使ってみる。
処理時間がかかりすぎるようであれば、自前のパーサに置き換える。
最初は node セクションの処理だけのため、プログラムは次のようになる。
japan.osm の空読み時間は 9分 となった。自前プログラムとしなくても大丈夫であろう。 因みに、現在の OSMParserの実行時間は全体では 38分であり、 特に、wayオブジェクトの処理に時間がかかっている。
public class Parser extends DefaultHandler {
@Override
public void startElement (String namespaceURI, String localName, String qName, Attributes atts ) {
if ("node".equals(qName)) { // nodeオブジェクトの処理
// System.out.println( "id=" + atts.getValue("id") );
// System.out.println( "lon=" + atts.getValue("lon") );
// System.out.println( "lat=" + atts.getValue("lat") );
} else if ("way".equals(qName)) {
// パース終了
}
}
public static void main( String[] args ) throws Exception {
long start = System.currentTimeMillis();
String src = args.length >= 1 ? args[0] : "c:/osm/japan.osm";
SAXParserFactory factory = SAXParserFactory.newInstance();
SAXParser parser = factory.newSAXParser();
Parser handler = new Parser();
parser.parse(Paths.get(src).toFile(), handler);
System.out.printf("実行時間: %.2f分\n", (System.currentTimeMillis()-start)/60000.0);
}
}
c:\gisa>java -Dfile.encoding=UTF-8 -Xmx5000m OSMParser japan.osm norm 最大Node Id = 10,231,804,665 最大Way Id = 1,118,748,330 最大Rel Id = 14,958,014 minPolys = 3 maxPolys = 358 空読み時間 = 4.08分 nodeパース時間 = 4.93分 wayパース時間 = 27.50分 relation処理時間 = 1.14分 Tagコード変換時間 = 0.00分 レコード書き込み時間 = 13.03分 OSMParser実行時間 = 37.73分 レコード数 34607040/34607040, 最大レコード長 4390116B(4287.2KB), ファイルサイズ 3810.2MB maxOuter: 548708(85F64), maxInner: 4793(12B9)
まず、ID と極座標を取り出し、整数化する。実行時間は 9.33分となった。
final double E7 = 10000000.0;
public void startElement(String uri, String localName, String qName, Attributes atts) throws SAXException {
if ("node".equals(qName)) { // nodeオブジェクトの処理
long id = Long.parseLong(atts.getValue("id"));
int lon = (int)(Double.parseDouble(atts.getValue("lon")) * E7);
int lat = (int)(Double.parseDouble(atts.getValue("lat")) * E7);
} else if ("way".equals(qName)) {
// パース終了
}
}
ブロック毎に sub id、lon、lat を出力するようにした。実行時間は 11.2分となった。 ブロック数は 605、総ファイルサイズは 2.54GB となった。
import java.io.*;
import java.nio.file.Paths;
import javax.xml.parsers.*;
import org.xml.sax.*;
import org.xml.sax.helpers.DefaultHandler;
public class Parser extends DefaultHandler {
final double E7 = 10000000.0;
final int BlockBits = 24; // Block番号 id >> BlockBits
final int BlockSize = 5000000;
int currBlock = -1;
int lastBlock = -1;
int cntNodes = 0;
int maxNodes = 0;
int[] sids = new int[BlockSize];
int[] lons = new int[BlockSize];
int[] lats = new int[BlockSize];
public void startElement(String uri, String localName, String qName, Attributes atts) throws SAXException {
if ("node".equals(qName)) { // nodeオブジェクトの処理
long id = Long.parseLong(atts.getValue("id"));
int blockNumber = (int)(id >> BlockBits);
if (blockNumber != currBlock) { // 新しいブロックが始まった
if (lastBlock >= 0) { // 前のブロックをファイルに書き込む
String path = "c:/osm/sidlonlats/" + lastBlock + ".dat";
try (DataOutputStream dos = new DataOutputStream(
new BufferedOutputStream(new FileOutputStream(path)))) {
for (int i = 0; i < cntNodes; i++) {
dos.writeInt(sids[i]);
dos.writeInt(lons[i]);
dos.writeInt(lats[i]);
}
} catch (Exception e) {
e.printStackTrace();
}
if (cntNodes > maxNodes) maxNodes = cntNodes;
System.out.printf("%d %d/%d\n", lastBlock, cntNodes, maxNodes);
cntNodes = 0;
}
lastBlock = currBlock;
currBlock = blockNumber;
}
sids[cntNodes] = (int)(id & ((1<= 1 ? args[0] : "c:/osm/japan.osm";
SAXParserFactory factory = SAXParserFactory.newInstance();
SAXParser parser = factory.newSAXParser();
Parser handler = new Parser();
parser.parse(Paths.get(src).toFile(), handler);
System.out.printf("実行時間: %.2f分\n", (System.currentTimeMillis()-start)/60000.0);
}
}
最終的には nodeセクションでは nodeの座標値データの出力だけではなく、タグをパースして、 ポイントレコードを出力するが、その前にパフォーマンスの見通しを付けるために、 wayセクションの処理を行う。
次に、ノード座標値の取り出しだけを行った。ノード座標値データは一部だけをメモリに置き、 必要に応じてスワップする仕組みにしているが、今のところ、全てをメモリに置かないと、 スワップに時間がかかり過ぎる。
kanto.osm および japan.osm に対する実行時間を下に示す。
前半の時間が長いのは、ファイルへの書き込みとファイルからの読み込みに時間がかかるためである。
ファイル管理を全面的にやめれば、プログラムはもっと簡単になり、実行時間も短縮する。 現在にOSMの日本地図データでは 5GB の主メモリが使える場合は問題はないが、 もっと大きなデータを扱う場合には、何らかの方法でデータサイズを縮小しないとメモリ不足になる。
スワップによるパフォーマンス劣化はこれほど大きいとは思わなかった。 どこかに不備があるかも知れない。
c:\gisa>java -Dfile.encoding=UTF-8 -Xmx5000m Parser c:/osm/kanto.osm 100万 189950106 1.69分 200万 385886896 1.82分 300万 558946275 1.92分 400万 725347405 2.02分 500万 849865383 2.11分 600万 1012313038 2.21分 実行時間: 2.30分 c:\gisa>java -Dfile.encoding=UTF-8 -Xmx5000m Parser 100万 109558932 8.48分 200万 118896760 8.68分 300万 129656349 8.87分 400万 151799302 9.10分 500万 176647489 9.29分 600万 199159815 9.46分 700万 237257311 9.64分 800万 297680074 9.76分 900万 361676392 9.89分 1000万 389144232 10.00分 1100万 420773372 10.11分 1200万 449643588 10.22分 1300万 483282560 10.32分 1400万 523962051 10.43分 1500万 554035212 10.53分 1600万 577758689 10.63分 1700万 603957342 10.73分 1800万 625593406 10.83分 1900万 665255659 10.93分 2000万 704605019 11.04分 2100万 733490874 11.13分 2200万 756457716 11.23分 2300万 790622198 11.34分 2400万 829932859 11.44分 2500万 881160441 11.54分 2600万 930982044 11.64分 2700万 974634995 11.74分 2800万 1006947494 11.84分 2900万 1041709924 11.93分 3000万 1081645714 12.03分 3100万 1117508196 12.13分 実行時間: 12.17分
// javac Parser.java OSMLib.java Tag.java
// java -Dfile.encoding=UTF-8 -Xmx5000m Parser c:/osm/japan.osm
import java.io.*;
import java.nio.file.*;
import java.util.*;
import javax.xml.parsers.*;
import org.xml.sax.*;
import org.xml.sax.helpers.DefaultHandler;
class NodeCache<K,V> extends LinkedHashMap<K,V> {
protected int limit = 700;
public NodeCache() {
super(501, 0.75F, true); // true: LRU, false: FIFO
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > limit;
}
}
class NodeBlock {
final static int BlockBits = 24; // Block番号 id >> BlockBits
final static int BlockSize = 5000000;
static NodeCache<Integer,NodeBlock> cacheNodes = new NodeCache<>();
int[] sids;
long[] lonlats;
int sidLast = -1, ixLast = -1, blkLast = -1;
public NodeBlock(int size) {
sids = new int[size];
lonlats = new long[size];
}
static int getBlockNumber(long id) { return (int)(id >> BlockBits); }
static int getSubId(long id) { return (int)(id & ((long)(1<<BlockBits) - 1)); }
static long getLonLat(long id) {
int blockNumber = getBlockNumber(id);
int sid = getSubId(id); // sub id
NodeBlock blk = cacheNodes.get(blockNumber);
if (blk == null) {
blk = load(blockNumber);
if (blk == null) {
System.out.printf("no file: blockNumber=%d\n", blockNumber);
return Long.MIN_VALUE; // エラー
}
cacheNodes.put(blockNumber, blk);
}
if (Math.abs(sid - blk.sidLast) < 10 && blk.blkLast == blockNumber) {
if (sid > blk.sidLast) {
for (int ix = blk.ixLast; blk.sids[ix] <= sid; ix++) {
if (blk.sids[ix] == sid) {
blk.sidLast = sid;
blk.ixLast = ix;
blk.blkLast = blockNumber;
return blk.lonlats[ix];
}
}
} else if (sid < blk.sidLast) {
for (int ix = blk.ixLast; blk.sids[ix] >= sid; ix--) {
if (blk.sids[ix] == sid) {
blk.sidLast = sid;
blk.ixLast = ix;
blk.blkLast = blockNumber;
return blk.lonlats[ix];
}
}
}
}
int ix = Arrays.binarySearch(blk.sids, sid);
if (ix >= 0) {
blk.sidLast = sid;
blk.ixLast = ix;
blk.blkLast = blockNumber;
} else {
System.out.printf("no! id=%x blk=%x sid=%x\n", id, blockNumber, sid);
}
return ix >= 0 ? blk.lonlats[ix] : Long.MIN_VALUE;
}
static long fileSize(String path) {
try { return Files.size(Paths.get(path)); }
catch (Exception e) { e.printStackTrace(); return 0; }
}
static NodeBlock load(int block_id) {
String path = Parser.dirSidLonLat + block_id + ".dat";
int num_nodes = (int)(fileSize(path)/12);
if (num_nodes == 0) return null;
NodeBlock blk = new NodeBlock(num_nodes);
try (DataInputStream dis = new DataInputStream(
new BufferedInputStream(new FileInputStream(path)))) {
for (int i = 0; i < num_nodes; i++) {
blk.sids[i] = dis.readInt();
blk.lonlats[i] = dis.readLong();
}
} catch (Exception e) {
e.printStackTrace();
return null;
}
return blk;
}
}
public class Parser extends DefaultHandler {
final double E7 = 10000000.0;
final static String dirSidLonLat = "c:/osm/sidlonlats/";
static long start = System.currentTimeMillis();
int currBlock=-1;
int cntNodes=0, maxNodes=0;
boolean fNodeSection = false;
boolean fWaySection = false;
int cntWay = 0;
int[] sids = new int[NodeBlock.BlockSize]; // ノード座標値のパースで使用
long[] lonlats = new long[NodeBlock.BlockSize];
public void startElement(String uri, String localName, String qName, Attributes atts) throws SAXException {
if (!fWaySection && "node".equals(qName)) {
if (!fNodeSection) fNodeSection = true;
procNode(atts); // nodeオブジェクトの処理
} else if ("way".equals(qName)) {
long id = Long.parseLong(atts.getValue("id"));
if (fNodeSection) {
fNodeSection = false; // nodeセクションは終わった
procNodeEnd(); // nodeセクションの後処理
}
if (!fWaySection) {
fWaySection = true;
}
if (++cntWay % 1000000 == 0) {
System.out.printf("%d万 %d %.2f分\n", cntWay/10000, id,
(System.currentTimeMillis() - start)/60000.0);
}
} else if (fWaySection && "nd".equals(qName)) {
long nid = Long.parseLong(atts.getValue("ref"));
long lonlat = NodeBlock.getLonLat(nid);
//System.out.printf("%d %d %d %d\n",
// NodeBlock.getBlockNumber(nid), nid, lonlat>>32, lonlat&0xffffffffL);
}
}
void writeNodeBlock(int blockNumber, int[] sids, long[] lonlats, int num_nodes) {
String path = dirSidLonLat + blockNumber + ".dat";
try (DataOutputStream dos = new DataOutputStream(
new BufferedOutputStream(new FileOutputStream(path)))) {
for (int i = 0; i < num_nodes; i++) {
dos.writeInt(sids[i]);
dos.writeLong(lonlats[i]);
}
} catch (Exception e) {
e.printStackTrace();
}
}
void procNode(Attributes atts) {
long id = Long.parseLong(atts.getValue("id"));
int blockNumber = NodeBlock.getBlockNumber(id);
if (blockNumber != currBlock) { // 新しいブロックが始まった
if (currBlock >= 0) { // 前のブロックをファイルに書き込む
writeNodeBlock(currBlock, sids, lonlats, cntNodes);
if (cntNodes > maxNodes) maxNodes = cntNodes;
cntNodes = 0;
}
currBlock = blockNumber;
}
sids[cntNodes] = NodeBlock.getSubId(id);
int lon = (int)(Double.parseDouble(atts.getValue("lon")) * E7);
int lat = (int)(Double.parseDouble(atts.getValue("lat")) * E7);
lonlats[cntNodes++] = (((long)lon)<<32) + (lat&0xffffffffL);
}
void procNodeEnd() {
writeNodeBlock(currBlock, sids, lonlats, cntNodes);
}
public static void main( String[] args ) throws Exception {
long start = System.currentTimeMillis();
String src = args.length >= 1 ? args[0] : "c:/osm/japan.osm";
SAXParserFactory factory = SAXParserFactory.newInstance();
SAXParser parser = factory.newSAXParser();
Parser handler = new Parser();
parser.parse(Paths.get(src).toFile(), handler);
System.out.printf("実行時間: %.2f分\n", (System.currentTimeMillis()-start)/60000.0);
}
}
スワップが起きる状態では予想以上に時間がかかる。wayセクションの処理をスワップが少なるように、 複数パスで行うなど、何らかの工夫が必要である。
ブロック内の検索はハッシュは要らないことが分かった。