Cấu trúc dữ liệu nhanh hơn để tìm kiếm chuỗi

Question

Tôi có mã này xác định xem một từ (bỏ qua trường hợp) có được bao gồm trong tệp văn bản wordList hay không. Tuy nhiên, tệp văn bản wordList có thể có 65000 dòng + + và chỉ cần tìm kiếm một từ bằng cách thực hiện của tôi dưới đây mất gần một phút. Bạn có thể nghĩ đến việc triển khai tốt hơn không?

Cảm ơn!

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

public class WordSearch 
{ 
    LinkedList<String> lxx; 
    FileReader fxx; 
    BufferedReader bxx; 

    public WordSearch(String wordlist) 
     throws IOException 
    { 
     fxx = new FileReader(wordlist); 
     bxx = new BufferedReader(fxx); 
     lxx = new LinkedList<String>(); 
     String word; 

     while ((word = bxx.readLine()) != null) 
      { 
      lxx.add(word); 
     } 

     bxx.close(); 
    } 

    public boolean inTheList (String theWord) 
    { 
     for(int i =0 ; i < lxx.size(); i++) 
      { 
      if (theWord.compareToIgnoreCase(lxx.get(i)) == 0) 
        { 
       return true; 
      } 
     } 

     return false; 
    } 
} 

Answer 1

Sử dụng HashSet mà bạn đặt phiên bản chữ thường của mỗi từ. Kiểm tra nếu một số HashSet chứa một chuỗi được chỉ định, tính trung bình, hoạt động liên tục (đọc: cực kỳ nhanh).

Answer 2

Vì bạn đang tìm kiếm, bạn có thể cân nhắc việc sắp xếp danh sách trước khi tìm kiếm; thì bạn có thể thực hiện tìm kiếm nhị phân nhanh hơn nhiều so với tìm kiếm tuyến tính. Điều đó có thể giúp nếu bạn thực hiện nhiều tìm kiếm trên cùng một danh sách, nếu không, hình phạt bạn trả để sắp xếp danh sách sẽ không đáng để tìm kiếm chỉ một lần.

Ngoài ra, thực hiện tìm kiếm tuyến tính trên danh sách được liên kết bằng cách sử dụng "lxx.get (i)" đang yêu cầu sự cố. LinkedList.get() là O (n). Bạn có thể sử dụng một Iterator (cách dễ dàng: for (String s: lxx)) hoặc chuyển sang kiểu danh sách có thời gian truy cập O (1), chẳng hạn như ArrayList.

Answer 3

Mỗi tìm kiếm qua l trong một hoạt động O (n), vì vậy điều này sẽ nhận được khá tốn kém khi bạn có hàng ngàn từ. Thay vào đó, sử dụng một HashSet:

Set<String> lxx; 

... 

lxx = new HashSet<String>(); 
while ((word = bxx.readLine()) != null) { 
     lxx.add(word.toLowerCase()); 
} 
bxx.close(); 

và sau đó sử dụng lxx.contains(theWord.toLowerCase()) để kiểm tra xem từ đó có trong tập tin. Mỗi tra cứu trong HashSet là một hoạt động O (1), vì vậy thời gian cần thiết là (gần như) độc lập với kích thước tệp của bạn.

Answer 4

Trước hết, không khai báo biến của bạn trở thành một LinkedList, tuyên bố nó là một danh sách (các phần của mã không quan tâm đến danh sách xóa:

public class WordSearch 
{ 
    List<String> lxx; 

    public WordSearch(String wordlist) 
     throws IOException 
    { 
     lxx = new LinkedList<String>(); 
    } 
} 

Tiếp theo không gọi được trên danh sách, sử dụng một get LinkedList sẽ rất chậm thay vì sử dụng một iterator ... tốt hơn nhưng sử dụng stype mới cho vòng lặp trong đó sử dụng một iterator cho bạn:.

public boolean inTheList (String theWord) 
    { 
     for(String word : lxx) 
     { 
      if (theWord.compareToIgnoreCase(word) == 0) 
      { 
       return true; 
      } 
     } 

     return false; 
    } 

Tiếp theo thay đổi LinkedList mới đến một ArrayList mới :

lxx = new ArrayList();

Mã này phải nhanh hơn, nhưng bạn vẫn có thể làm tốt hơn.

Vì bạn không quan tâm đến các từ trùng lặp, hãy sử dụng Đặt thay vì Danh sách và sử dụng một HashSet thay vì một ArrayList.

Làm như vậy sẽ tăng tốc độ chương trình đáng kể.

Mã ban đầu của bạn, sử dụng LinkedList với get phải bắt đầu lại ở đầu danh sách mỗi khi tìm kiếm từ tiếp theo trong danh sách. Sử dụng Iterator (thông qua kiểu vòng lặp mới cho mỗi vòng lặp) sẽ dừng điều đó xảy ra.

Sử dụng LinkedList có nghĩa là mỗi lần bạn phải chuyển sang từ tiếp theo trong danh sách có tra cứu liên quan, ArrayList không có phí trên đó.

Sử dụng HashSet (có thể) sử dụng cấu trúc cây có tra cứu rất nhanh.

Answer 5

Đây là triển khai của tôi, tìm kiếm dưới 50 mili giây.

Trước tiên, bạn phải tải tệp và giữ cho tệp được sắp xếp trong bộ nhớ.

Bạn có thể tải nó theo bất kỳ cách nào bạn muốn, nhưng nếu bạn tải nó theo khối lớn sẽ dễ dàng hơn.

đầu vào của tôi đã là byte into python book (tải về phiên bản tập tin duy nhất HTML) và Java language specification (tải về html và tạo ra một tập tin duy nhất trong số tất cả các trang html)

Để tạo danh sách vào một tập tin lớn tôi đã sử dụng chương trình tương tự này (xem mã nhận xét).

Khi tôi có một tập tin lớn với khoảng 300k từ, tôi chạy chương trình với sản lượng này:

C:\Users\oreyes\langs\java\search>dir singlelineInput.txt 
El volumen de la unidad C no tiene etiqueta. 
El número de serie del volumen es: 22A8-203B 

Directorio de C:\Users\oreyes\langs\java\search 

04/03/2011 09:37 p.m.   3,898,345 singlelineInput.txt 
       1 archivos  3,898,345 bytes 

C:\Users\oreyes\langs\java\search>javac WordSearch.java 

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "great" 
Loaded 377381 words in 2844 ms 
true 
in 31 ms 

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "great" 
Loaded 377381 words in 2812 ms 
true 
in 31 ms 

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "awesome" 
Loaded 377381 words in 2813 ms 
false 
in 47 ms 

C:\Users\oreyes\langs\java\search>gvim singlelineInput.txt 

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "during" 
Loaded 377381 words in 2813 ms 
true 
in 15 ms 

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "specification" 
Loaded 377381 words in 2875 ms 
true 
in 47 ms 

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "<href" 
Loaded 377381 words in 2844 ms 
false 
in 47 ms 

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "<br>" 
Loaded 377381 words in 2829 ms 
true 
in 15 ms 

Luôn dưới 50 ms.

Dưới đây là các mã:

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

    class WordSearch { 
     String inputFile; 
     List<String> words; 
     public WordSearch(String file) { 
      inputFile = file; 
     } 
     public void initialize() throws IOException { 
      long start = System.currentTimeMillis(); 
      File file = new File(inputFile); 
      ByteArrayOutputStream baos = new ByteArrayOutputStream((int) file.length()); 
      FileInputStream in = new FileInputStream(file); 
      copyLarge(in, baos, (int)file.length()); 

      Scanner scanner = new Scanner(new ByteArrayInputStream( baos.toByteArray())); 
      words = new LinkedList<String>(); 
      while(scanner.hasNextLine()) { 
       String l = scanner.nextLine().trim(); 
       //for(String s : l.split("\\s+")){ 
       //System.out.println(s); 
       words.add(l.toLowerCase()); 
       //} 
      } 

      Collections.sort(words); 
      for(String s : words) { 
       //System.out.println(s); 
      } 
      System.out.println("Loaded " + words.size() + " words in "+ (System.currentTimeMillis() - start) + " ms" ); 
     } 

     public boolean contains(String aWord) { 
      return words.contains(aWord.toLowerCase()); 
     } 
     // taken from: http://stackoverflow.com/questions/326390/how-to-create-a-java-string-from-the-contents-of-a-file/326413#326413 
     public static long copyLarge(InputStream input, OutputStream output, int size) 
       throws IOException { 
      byte[] buffer = new byte[size];// something biggie 
      long count = 0; 
      int n = 0; 
      while (-1 != (n = input.read(buffer))) { 
       output.write(buffer, 0, n); 
       count += n; 
      } 
      return count; 
     } 
     public static void main(String ... args) throws IOException { 
      WordSearch ws = new WordSearch(args[0]); 
      ws.initialize(); 
      long start = System.currentTimeMillis(); 
      System.out.println(ws.contains(args[1])); 
      System.out.println("in "+ (System.currentTimeMillis() - start) +" ms "); 

     } 
    } 

Phần cứng là để có được một mẫu đầu vào: P

Answer 6

Đoán những gì, sử dụng lợi nhuận HashMap trong thời gian không:

Dưới đây là phiên bản sửa đổi và nó luôn luôn kết thúc trong 0 ms.

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

    class WordSearch { 
     String inputFile; 
     //List<String> words; 
     Set<String> words; 
     public WordSearch(String file) { 
      inputFile = file; 
     } 
     public void initialize() throws IOException { 
      long start = System.currentTimeMillis(); 
      File file = new File(inputFile); 
      ByteArrayOutputStream baos = new ByteArrayOutputStream((int) file.length()); 
      FileInputStream in = new FileInputStream(file); 
      copyLarge(in, baos, (int)file.length()); 

      Scanner scanner = new Scanner(new ByteArrayInputStream( baos.toByteArray())); 
      words = new HashSet<String>(); 
      while(scanner.hasNextLine()) { 
       String l = scanner.nextLine().trim(); 
       //for(String s : l.split("\\s+")){ 
       //System.out.println(s); 
       words.add(l.toLowerCase()); 
       //} 
      } 

      //Collections.sort(words); 
      for(String s : words) { 
       System.out.println(s); 
      } 
      System.out.println("Loaded " + words.size() + " words in "+ (System.currentTimeMillis() - start) + " ms" ); 
     } 

     public boolean contains(String aWord) { 
      return words.contains(aWord.toLowerCase()); 
     } 

     public static long copyLarge(InputStream input, OutputStream output, int size) 
       throws IOException { 
      byte[] buffer = new byte[size];// something biggie 
      long count = 0; 
      int n = 0; 
      while (-1 != (n = input.read(buffer))) { 
       output.write(buffer, 0, n); 
       count += n; 
      } 
      return count; 
     } 
     public static void main(String ... args) throws IOException { 
      WordSearch ws = new WordSearch(args[0]); 
      ws.initialize(); 
      long start = System.currentTimeMillis(); 
      System.out.println(ws.contains(args[1])); 
      System.out.println("in "+ (System.currentTimeMillis() - start) +" ms "); 

     } 
    } 

Bây giờ tôi biết chắc chắn :)

Answer 7

hai gợi ý: Cả hai cấu trúc dữ liệu cung cấp cho bạn một hiệu suất tốt hơn.

1. Biểu đồ từ tuần hoàn được chỉ định (DAWG)
2. Cấu trúc dữ liệu từ điển. n-tree