जावा

Question

में एक क्रमबद्ध (मेमोरी-मैप किए गए?) फ़ाइल में बाइनरी खोज, मैं जावा पर एक पर्ल प्रोग्राम पोर्ट करने और जावा जाने के दौरान सीखने के लिए संघर्ष कर रहा हूं। मूल कार्यक्रम का एक केंद्रीय घटक Perl module है जो बाइनरी खोज (अनिवार्य रूप से, फ़ाइल के बीच में एक बाइट ऑफसेट के लिए "तलाश", निकटतम न्यूलाइन पर बैकट्रैक, तुलना करने के लिए +500 जीबी क्रमबद्ध टेक्स्ट फ़ाइल में स्ट्रिंग उपसर्ग लुकअप करता है, तुलना करें खोज स्ट्रिंग के साथ लाइन उपसर्ग, बाइट ऑफसेट के आधे/दोगुने के लिए "तलाश करें", मिलने तक दोहराएं ...)

मैंने कई डेटाबेस समाधानों के साथ प्रयोग किया है लेकिन पाया है कि डेटा सेट के साथ सरासर लुकअप गति में कुछ भी नहीं है यह आकार क्या आप किसी भी मौजूदा जावा लाइब्रेरी के बारे में जानते हैं जो ऐसी कार्यक्षमता लागू करता है? यह विफल हो रहा है, क्या आप मुझे कुछ बेवकूफ उदाहरण कोड पर इंगित कर सकते हैं जो पाठ फ़ाइलों में यादृच्छिक पहुंच पढ़ता है?

वैकल्पिक रूप से, मैं नए (?) जावा I/O पुस्तकालयों से परिचित नहीं हूं, लेकिन यह 500 जीबी टेक्स्ट फ़ाइल को स्मृति-मानचित्र करने का विकल्प होगा (मैं 64-बिट मशीन पर स्मृति के साथ स्मृति के साथ हूं) और स्मृति-मैप किए गए बाइट सरणी पर बाइनरी खोज करें? मुझे इस तरह की और इसी तरह की समस्याओं के बारे में साझा करने के लिए आपके अनुभवों को सुनने में बहुत दिलचस्पी होगी।

Answer 1

मैं इस तरह की स्थितियों के लिए जावा के MappedByteBuffers के बड़ा प्रशंसक हूँ। यह तेजी से चमक रहा है। नीचे एक स्निपेट है जिसे मैंने आपके लिए एक साथ रखा है जो फ़ाइल में बफर को मानचित्र करता है, बीच की तलाश करता है, और फिर पीछे की ओर एक न्यूलाइन चरित्र की खोज करता है। यह आपको जाने के लिए पर्याप्त होना चाहिए?

मैं, इसी तरह के कोड (, तलाश पढ़ा है, किया जब तक दोहराएँ) मेरे अपने आवेदन में एक उत्पादन वातावरण में MappedByteBuffer के खिलाफ java.io धाराओं बेंचमार्क और मेरे ब्लॉग (Geekomatic posts tagged 'java.nio') कच्चे डेटा, रेखांकन और सभी के साथ पर परिणाम था।

दो सेकंड सारांश? मेरा MappedByteBuffer-आधारित कार्यान्वयन लगभग 275% तेज था। वाईएमएमवी।

~ 2 जीबी से बड़ी फ़ाइलों के लिए काम करने के लिए, जो कास्ट और .position(int pos) की वजह से एक समस्या है, मैंने MappedByteBuffer एस की एक सरणी द्वारा समर्थित पेजिंग एल्गोरिदम तैयार किया है। 2-4 जीबी से बड़ी फ़ाइलों के साथ काम करने के लिए आपको 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); 
    } 
} 

Answer 2

यह एक सरल उदाहरण है जिसे आप प्राप्त करना चाहते हैं। मैं शायद प्रत्येक स्ट्रिंग के लिए फ़ाइल स्थिति का ट्रैक रखते हुए फ़ाइल को पहले इंडेक्स करता हूं। मैं तार नई-पंक्तियों (या कैरिएज रिटर्न) से अलग कर रहे हैं संभालने हूँ:

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. 

Answer 3

आप वास्तव में फ़ाइल मानचित्रण स्मृति की कोशिश करना चाहते हैं, तो मैं जावा NIO में एक tutorial on how to use memory mapping पाया।

Answer 4

मुझे उस कार्यक्षमता के बारे में पता नहीं है जिसमें कार्यक्षमता है।

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 जीबी फ़ाइल के लिए, उस इंडेक्स को इंडेक्स फाइल में संग्रहित किया जाना चाहिए। आपको उस सूचकांक के साथ एक बहुत ही कम स्थिर कारक प्राप्त करना चाहिए क्योंकि प्रत्येक चरण में अगली पंक्ति की खोज करने की आवश्यकता नहीं है।

मुझे पता है कि यह सवाल नहीं था, लेकिन उपसर्ग पेड़ डेटा संरचना जैसे (पेट्रीका) प्रयास (डिस्क/एसएसडी पर) का निर्माण करना उपसर्ग खोज करना एक अच्छा विचार हो सकता है।

Answer 5

मुझे एक ही समस्या है। मैं सभी लाइनों को खोजने की कोशिश कर रहा हूं जो एक क्रमबद्ध फ़ाइल में कुछ उपसर्ग के साथ शुरू होते हैं। 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; 
} 

Answer 6

आप एक 500GB फ़ाइल के साथ काम कर रहे हैं, तो आप द्विआधारी खोज की तुलना में एक तेजी से देखने विधि का उपयोग कर सकते हैं। ऐसा करने के लिए सबसे अच्छी विधि वास्तव में आपके डेटा वितरण और लुकअप के प्रकारों पर निर्भर करती है, लेकिन यदि आप स्ट्रिंग उपसर्ग की तलाश में हैं तो ऐसा करने का एक अच्छा तरीका होना चाहिए।

मैंने पूर्णांक के लिए एक रेडिक्स सॉर्ट समाधान का एक उदाहरण पोस्ट किया है, लेकिन आप समान विचार का उपयोग कर सकते हैं - मूल रूप से डेटा को बाल्टी में विभाजित करके सॉर्ट टाइम काटने के लिए, फिर बाल्टी को पुनः प्राप्त करने के लिए ओ (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 

Answer 7

मैं इसी तरह की समस्या थी, तो मैं बनाया (स्काला) इस सूत्र में प्रदान की समाधान से पुस्तकालय:

https://github.com/avast/BigMap

यह इस क्रमबद्ध फ़ाइल में भारी फ़ाइल और द्विआधारी खोज छँटाई के लिए उपयोगिता में शामिल है। ..

Answer 8

मैं एक सार 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; 
    } 
}