Java でのソートされた (メモリマップされた ?) ファイル内の二分探索
https://stackoverflow.com/questions/736556
-
09-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は Perl プログラムを Java に移植するのに苦労しており、やりながら Java を学習しています。元のプログラムの中心的なコンポーネントは、 Perlモジュール それは、バイナリ検索を使用して+500 GBのソートテキストファイルの文字列プレフィックスルックアップを行います（基本的に、ファイルの中央でバイトオフセットに「シーク」、最寄りのNewlineへのバックトラック、検索文字列と「Seek」を比較します。そのバイトオフセットの半分/2倍、見つかるまで繰り返します...）
いくつかのデータベース ソリューションを試してみましたが、このサイズのデータ セットでは検索速度の点でこれに勝るものはありませんでした。そのような機能を実装する既存の Java ライブラリをご存知ですか?それができない場合は、テキスト ファイルのランダム アクセス読み取りを行う慣用的なサンプル コードを教えていただけますか?
あるいは、新しい (?) Java I/O ライブラリには詳しくありませんが、500 GB のテキスト ファイルをメモリ マップして (メモリに余裕のある 64 ビット マシンを使用しています)、バイナリを実行するというオプションはありますか?メモリマップされたバイト配列を検索しますか?この問題や同様の問題について、皆さんの経験を共有していただければ幸いです。
解決
私は 大きい Javaのファン MappedByteBuffers このような状況のために。猛烈な勢いで進んでいます。以下は、バッファをファイルにマップし、中央までシークし、改行文字まで逆方向に検索する、私がまとめたスニペットです。これで十分ですか?
私自身のアプリケーションにも同様のコード（シーク、読み取り、完了するまで繰り返す）があり、ベンチマークされていますjava.io 対するストリーム MappedByteBuffer 運用環境で結果をブログに投稿しました (「java.nio」タグが付いた Geekomatic の投稿 ) 生データ、グラフなどすべてを含みます。
2秒の要約？ 私の MappedByteBufferベースの実装は約 275% 高速になりました。 YMMV。
~2GB を超えるファイルを処理するには、キャストと .position(int pos), の配列に裏付けられたページング アルゴリズムを作成しました。 MappedByteBuffers.MBB は OS の仮想メモリ システムを使用して機能するため、2 ～ 4GB を超えるファイルを処理するには 64 ビット システムで作業する必要があります。
public class StusMagicLargeFileReader {
private static final long PAGE_SIZE = Integer.MAX_VALUE;
private List<MappedByteBuffer> buffers = new ArrayList<MappedByteBuffer>();
private final byte raw[] = new byte[1];
public static void main(String[] args) throws IOException {
File file = new File("/Users/stu/test.txt");
FileChannel fc = (new FileInputStream(file)).getChannel();
StusMagicLargeFileReader buffer = new StusMagicLargeFileReader(fc);
long position = file.length() / 2;
String candidate = buffer.getString(position--);
while (position >=0 && !candidate.equals('\n'))
candidate = buffer.getString(position--);
//have newline position or start of file...do other stuff
}
StusMagicLargeFileReader(FileChannel channel) throws IOException {
long start = 0, length = 0;
for (long index = 0; start + length < channel.size(); index++) {
if ((channel.size() / PAGE_SIZE) == index)
length = (channel.size() - index * PAGE_SIZE) ;
else
length = PAGE_SIZE;
start = index * PAGE_SIZE;
buffers.add(index, channel.map(READ_ONLY, start, length));
}
}
public String getString(long bytePosition) {
int page = (int) (bytePosition / PAGE_SIZE);
int index = (int) (bytePosition % PAGE_SIZE);
raw[0] = buffers.get(page).get(index);
return new String(raw);
}
}
他のヒント
私は同じ問題を抱えています。並べ替えられたファイル内で何らかのプレフィックスで始まるすべての行を検索しようとしています。
これは私が作成したメソッドです。これは主にここにある Python コードの移植です。 http://www.logarithmic.net/pfh/blog/01186620415
テストしましたが、まだ完全にはテストしていません。ただし、メモリマッピングは使用しません。
public static List<String> binarySearch(String filename, String string) {
List<String> result = new ArrayList<String>();
try {
File file = new File(filename);
RandomAccessFile raf = new RandomAccessFile(file, "r");
long low = 0;
long high = file.length();
long p = -1;
while (low < high) {
long mid = (low + high) / 2;
p = mid;
while (p >= 0) {
raf.seek(p);
char c = (char) raf.readByte();
//System.out.println(p + "\t" + c);
if (c == '\n')
break;
p--;
}
if (p < 0)
raf.seek(0);
String line = raf.readLine();
//System.out.println("-- " + mid + " " + line);
if (line.compareTo(string) < 0)
low = mid + 1;
else
high = mid;
}
p = low;
while (p >= 0) {
raf.seek(p);
if (((char) raf.readByte()) == '\n')
break;
p--;
}
if (p < 0)
raf.seek(0);
while (true) {
String line = raf.readLine();
if (line == null || !line.startsWith(string))
break;
result.add(line);
}
raf.close();
} catch (IOException e) {
System.out.println("IOException:");
e.printStackTrace();
}
return result;
}
その機能を備えたライブラリを私は知りません。ただし、Java での外部バイナリ検索の正しいコードは次のようになります。
class ExternalBinarySearch {
final RandomAccessFile file;
final Comparator<String> test; // tests the element given as search parameter with the line. Insert a PrefixComparator here
public ExternalBinarySearch(File f, Comparator<String> test) throws FileNotFoundException {
this.file = new RandomAccessFile(f, "r");
this.test = test;
}
public String search(String element) throws IOException {
long l = file.length();
return search(element, -1, l-1);
}
/**
* Searches the given element in the range [low,high]. The low value of -1 is a special case to denote the beginning of a file.
* In contrast to every other line, a line at the beginning of a file doesn't need a \n directly before the line
*/
private String search(String element, long low, long high) throws IOException {
if(high - low < 1024) {
// search directly
long p = low;
while(p < high) {
String line = nextLine(p);
int r = test.compare(line,element);
if(r > 0) {
return null;
} else if (r < 0) {
p += line.length();
} else {
return line;
}
}
return null;
} else {
long m = low + ((high - low) / 2);
String line = nextLine(m);
int r = test.compare(line, element);
if(r > 0) {
return search(element, low, m);
} else if (r < 0) {
return search(element, m, high);
} else {
return line;
}
}
}
private String nextLine(long low) throws IOException {
if(low == -1) { // Beginning of file
file.seek(0);
} else {
file.seek(low);
}
int bufferLength = 65 * 1024;
byte[] buffer = new byte[bufferLength];
int r = file.read(buffer);
int lineBeginIndex = -1;
// search beginning of line
if(low == -1) { //beginning of file
lineBeginIndex = 0;
} else {
//normal mode
for(int i = 0; i < 1024; i++) {
if(buffer[i] == '\n') {
lineBeginIndex = i + 1;
break;
}
}
}
if(lineBeginIndex == -1) {
// no line begins within next 1024 bytes
return null;
}
int start = lineBeginIndex;
for(int i = start; i < r; i++) {
if(buffer[i] == '\n') {
// Found end of line
return new String(buffer, lineBeginIndex, i - lineBeginIndex + 1);
return line.toString();
}
}
throw new IllegalArgumentException("Line to long");
}
}
ご注意ください：このコードをアドホックに作成しました。コーナーケースは十分にテストされておらず、コードは 64K を超える単一行がないことを前提としています。
また、行の開始位置のオフセットのインデックスを作成するのも良いアイデアだと思います。500 GB のファイルの場合、そのインデックスはインデックス ファイルに保存する必要があります。各ステップで次の行を検索する必要がないため、そのインデックスを使用すると、それほど小さくない定数係数が得られるはずです。
それが質問ではないことはわかっていますが、(Patrica) Trys (ディスク/SSD 上) のようなプレフィックス ツリー データ構造を構築してプレフィックス検索を行うことは良い考えかもしれません。
これは、達成したいことの簡単な例です。おそらく、最初にファイルにインデックスを付けて、各文字列のファイルの位置を追跡するでしょう。文字列は改行（またはキャリッジリターン）で区切られていると仮定します。
RandomAccessFile file = new RandomAccessFile("filename.txt", "r");
List<Long> indexList = new ArrayList();
long pos = 0;
while (file.readLine() != null)
{
Long linePos = new Long(pos);
indexList.add(linePos);
pos = file.getFilePointer();
}
int indexSize = indexList.size();
Long[] indexArray = new Long[indexSize];
indexList.toArray(indexArray);
最後のステップは、多数の検索を実行する際の速度をわずかに向上させるために配列に変換することです。おそらく変換すると思います Long[] に long[] また、上ではそれを示しませんでした。最後に、指定されたインデックス位置から文字列を読み取るコード:
int i; // Initialize this appropriately for your algorithm.
file.seek(indexArray[i]);
String line = file.readLine();
// At this point, line contains the string #i.
500 GB のファイルを扱っている場合は、バイナリ検索よりも高速な検索方法、つまり本質的にハッシュの一種である基数ソートを使用した方がよいでしょう。これを行うための最適な方法は、実際にはデータの分布と検索の種類によって異なりますが、文字列プレフィックスを探している場合には、これを行うための良い方法があるはずです。
整数の基数ソート ソリューションの例を投稿しましたが、同じアイデアを使用できます。基本的にはデータをバケットに分割し、O(1) ルックアップを使用して関連するデータのバケットを取得することでソート時間を短縮します。 。
Option Strict On
Option Explicit On
Module Module1
Private Const MAX_SIZE As Integer = 100000
Private m_input(MAX_SIZE) As Integer
Private m_table(MAX_SIZE) As List(Of Integer)
Private m_randomGen As New Random()
Private m_operations As Integer = 0
Private Sub generateData()
' fill with random numbers between 0 and MAX_SIZE - 1
For i = 0 To MAX_SIZE - 1
m_input(i) = m_randomGen.Next(0, MAX_SIZE - 1)
Next
End Sub
Private Sub sortData()
For i As Integer = 0 To MAX_SIZE - 1
Dim x = m_input(i)
If m_table(x) Is Nothing Then
m_table(x) = New List(Of Integer)
End If
m_table(x).Add(x)
' clearly this is simply going to be MAX_SIZE -1
m_operations = m_operations + 1
Next
End Sub
Private Sub printData(ByVal start As Integer, ByVal finish As Integer)
If start < 0 Or start > MAX_SIZE - 1 Then
Throw New Exception("printData - start out of range")
End If
If finish < 0 Or finish > MAX_SIZE - 1 Then
Throw New Exception("printData - finish out of range")
End If
For i As Integer = start To finish
If m_table(i) IsNot Nothing Then
For Each x In m_table(i)
Console.WriteLine(x)
Next
End If
Next
End Sub
' run the entire sort, but just print out the first 100 for verification purposes
Private Sub test()
m_operations = 0
generateData()
Console.WriteLine("Time started = " & Now.ToString())
sortData()
Console.WriteLine("Time finished = " & Now.ToString & " Number of operations = " & m_operations.ToString())
' print out a random 100 segment from the sorted array
Dim start As Integer = m_randomGen.Next(0, MAX_SIZE - 101)
printData(start, start + 100)
End Sub
Sub Main()
test()
Console.ReadLine()
End Sub
End Module
要旨を掲載します https://gist.github.com/mikee805/c6c2e6a35032a3ab74f643a1d0f8249c
これはスタック オーバーフローといくつかのブログで見つけたものに基づいたかなり完全な例であり、他の人がそれを使用できることを願っています
import static java.nio.file.Files.isWritable;
import static java.nio.file.StandardOpenOption.READ;
import static org.apache.commons.io.FileUtils.forceMkdir;
import static org.apache.commons.io.IOUtils.closeQuietly;
import static org.apache.commons.lang3.StringUtils.isBlank;
import static org.apache.commons.lang3.StringUtils.trimToNull;
import java.io.File;
import java.io.IOException;
import java.nio.Buffer;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.file.Path;
public class FileUtils {
private FileUtils() {
}
private static boolean found(final String candidate, final String prefix) {
return isBlank(candidate) || candidate.startsWith(prefix);
}
private static boolean before(final String candidate, final String prefix) {
return prefix.compareTo(candidate.substring(0, prefix.length())) < 0;
}
public static MappedByteBuffer getMappedByteBuffer(final Path path) {
FileChannel fileChannel = null;
try {
fileChannel = FileChannel.open(path, READ);
return fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, fileChannel.size()).load();
}
catch (Exception e) {
throw new RuntimeException(e);
}
finally {
closeQuietly(fileChannel);
}
}
public static String binarySearch(final String prefix, final MappedByteBuffer buffer) {
if (buffer == null) {
return null;
}
try {
long low = 0;
long high = buffer.limit();
while (low < high) {
int mid = (int) ((low + high) / 2);
final String candidate = getLine(mid, buffer);
if (found(candidate, prefix)) {
return trimToNull(candidate);
}
else if (before(candidate, prefix)) {
high = mid;
}
else {
low = mid + 1;
}
}
}
catch (Exception e) {
throw new RuntimeException(e);
}
return null;
}
private static String getLine(int position, final MappedByteBuffer buffer) {
// search backwards to the find the proceeding new line
// then search forwards again until the next new line
// return the string in between
final StringBuilder stringBuilder = new StringBuilder();
// walk it back
char candidate = (char)buffer.get(position);
while (position > 0 && candidate != '\n') {
candidate = (char)buffer.get(--position);
}
// we either are at the beginning of the file or a new line
if (position == 0) {
// we are at the beginning at the first char
candidate = (char)buffer.get(position);
stringBuilder.append(candidate);
}
// there is/are char(s) after new line / first char
if (isInBuffer(buffer, position)) {
//first char after new line
candidate = (char)buffer.get(++position);
stringBuilder.append(candidate);
//walk it forward
while (isInBuffer(buffer, position) && candidate != ('\n')) {
candidate = (char)buffer.get(++position);
stringBuilder.append(candidate);
}
}
return stringBuilder.toString();
}
private static boolean isInBuffer(final Buffer buffer, int position) {
return position + 1 < buffer.limit();
}
public static File getOrCreateDirectory(final String dirName) {
final File directory = new File(dirName);
try {
forceMkdir(directory);
isWritable(directory.toPath());
}
catch (IOException e) {
throw new RuntimeException(e);
}
return directory;
}
}
私も同様の問題を抱えていたので、このスレッドで提供されている解決策から（Scala）ライブラリを作成しました。
https://github.com/avast/BigMap
巨大なファイルをソートし、このソートされたファイル内でバイナリ検索を行うためのユーティリティが含まれています...
本当にファイルのメモリマッピングを試したい場合は、次の方法を見つけました。 メモリマッピングの使用方法に関するチュートリアル ジャワでニオ。
