Cách tốt nhất để lưu trữ và truy cập 120.000 từ trong java

Question

Tôi đang lập trình một ứng dụng java đọc các tệp văn bản nghiêm ngặt (.txt). Các tệp này có thể chứa tối đa 120.000 từ.

Ứng dụng cần lưu trữ tất cả +120.000 từ. Nó cần phải đặt tên chúng là word_1, word_2, v.v. Và nó cũng cần truy cập những từ này để thực hiện các phương thức khác nhau trên chúng.

Tất cả các phương pháp đều liên quan đến Chuỗi. Ví dụ, một phương thức sẽ được gọi để nói có bao nhiêu chữ cái trong word_80. Một phương pháp khác sẽ được gọi để nói những chữ cái cụ thể trong word_2200.

Ngoài ra, một số phương pháp sẽ so sánh hai từ. Ví dụ, một phương thức sẽ được gọi để so sánh word_80 với word_2200 và cần trả lại có nhiều chữ cái hơn. Một phương thức khác sẽ được gọi để so sánh word_80 với word_2200 và cần phải trả về những chữ cái cụ thể nào cả hai từ chia sẻ.

Câu hỏi của tôi là: Vì tôi đang làm việc gần như độc quyền với Strings, cách tốt nhất để lưu trữ những từ này trong một ArrayList lớn? Một số ArrayLists nhỏ? Hoặc tôi nên sử dụng một trong nhiều khả năng lưu trữ khác, như Vectors, HashSets, LinkedLists?

Hai mối quan tâm chính của tôi là 1.) tốc độ truy cập và 2.) có số lượng phương pháp được tạo sẵn nhất có thể tùy ý sử dụng.

Cảm ơn sự giúp đỡ của bạn trước !!

---

Wow! Cảm ơn tất cả mọi người đã cung cấp phản hồi nhanh như vậy cho câu hỏi của tôi. Tất cả các đề xuất của bạn đã giúp tôi vô cùng. Tôi đang suy nghĩ và xem xét tất cả các tùy chọn được cung cấp trong phản hồi của bạn.

Hãy tha thứ cho tôi vì bất kỳ sự mờ nhạt nào; và để tôi giải quyết các câu hỏi của bạn:

1. Q) Tiếng Anh?
   A) Các tệp văn bản thực ra là các sách được viết bằng tiếng Anh. Sự xuất hiện của một từ trong ngôn ngữ thứ hai sẽ hiếm - nhưng không phải là không thể. Tôi sẽ đặt phần trăm từ không phải tiếng Anh vào các tệp văn bản tại .0001%

2. Q) Bài tập về nhà?
   A) Tôi đang mỉm cười nhìn vào từ ngữ của câu hỏi của tôi ngay bây giờ. Có, nó giống như một bài tập ở trường. Nhưng không, nó không phải là bài tập về nhà.

3. Q) Bản sao?
   A) Có. Và có thể cứ năm từ hoặc nhiều từ, xem xét các liên từ, bài viết, v.v.

4. Q) Truy cập?
   A) Cả hai ngẫu nhiên và tuần tự. Chắc chắn có thể một phương pháp sẽ định vị một từ ngẫu nhiên. Cũng có thể một phương pháp sẽ tìm kiếm một từ phù hợp giữa word_1 và word_120000 theo tuần tự. Điều này dẫn đến câu hỏi cuối cùng…

5. Q) Lặp lại toàn bộ danh sách?
   A) Có.

Ngoài ra, tôi dự định phát triển chương trình này để thực hiện nhiều phương pháp khác về từ. Tôi xin lỗi lần nữa vì sự mờ nhạt của tôi. (Chi tiết làm nên một thế giới khác biệt, phải không?)

Chúc mừng!

Answer 1

Sử dụng Hashtable? Điều này sẽ cung cấp cho bạn tốc độ tra cứu tốt nhất của bạn.

Answer 2

Tôi sẽ lưu trữ chúng trong một ArrayList lớn và lo lắng về (có thể không cần thiết) tối ưu hóa sau này.

Vốn đã lười biếng, tôi không nghĩ rằng nên tối ưu hóa trừ khi có nhu cầu chứng minh. Nếu không, bạn chỉ lãng phí công sức mà có thể được chi tiêu tốt hơn ở nơi khác. Trên thực tế, nếu bạn có thể đặt giới hạn trên cho số từ của mình và bạn không cần bất kỳ hoạt động Danh sách ưa thích nào, tôi sẽ chọn một mảng đối tượng chuỗi (nguyên gốc) bình thường có số nguyên giữ số thực tế. Điều này có khả năng nhanh hơn phương pháp dựa trên lớp học.

Điều này mang đến cho bạn tốc độ lớn nhất trong việc truy cập các phần tử riêng lẻ trong khi vẫn duy trì khả năng thực hiện tất cả thao tác chuỗi tuyệt vời đó.

Lưu ý rằng tôi chưa đánh giá các mảng gốc so với ArrayLists. Chúng có thể nhanh như các mảng bản địa, vì vậy bạn nên tự mình kiểm tra nếu bạn ít tin tưởng vào khả năng của mình hơn là :-).

Nếu họ làm hóa ra là nhanh (hoặc thậm chí đóng), các lợi ích bổ sung (khả năng mở rộng, cho một) có thể đủ để biện minh cho việc sử dụng của chúng.

Answer 3

Nếu bạn sẽ truy cập các chuỗi này theo tuần tự, LinkedList sẽ là lựa chọn tốt nhất.

Để truy cập ngẫu nhiên, ArrayLists có giao diện sử dụng bộ nhớ/truy cập bộ nhớ tốt đẹp.

Answer 4

Chỉ cần xác nhận giả thuyết khách, có một chuẩn mực rất ngây thơ

public static void main(String[] args) 
{ 
    int size = 120000; 
    String[] arr = new String[size]; 
    ArrayList al = new ArrayList(size); 
    for (int i = 0; i < size; i++) 
    { 
     String put = Integer.toHexString(i).toString(); 
     // System.out.print(put + " "); 
     al.add(put); 
     arr[i] = put; 
    } 

    Random rand = new Random(); 
    Date start = new Date(); 
    for (int i = 0; i < 10000000; i++) 
    { 
     int get = rand.nextInt(size); 
     String fetch = arr[get]; 

    } 
    Date end = new Date(); 
    long diff = end.getTime() - start.getTime(); 
    System.out.println("array access took " + diff + " ms"); 

    start = new Date(); 
    for (int i = 0; i < 10000000; i++) 
    { 
     int get = rand.nextInt(size); 
     String fetch = (String) al.get(get); 

    } 
    end = new Date(); 
    diff = end.getTime() - start.getTime(); 
    System.out.println("array list access took " + diff + " ms"); 
} 

và đầu ra:
truy cập mảng mất 578 ms
mảng danh sách truy cập mất 907 ms

chạy nó một vài lần thời gian thực tế dường như thay đổi một số, nhưng nói chung truy cập mảng nhanh hơn từ 200 đến 400 ms, hơn 10.000.000 lần lặp.

Answer 5

ArrayList/Vector nếu vấn đề trật tự (có vẻ như, vì bạn đang gọi các từ "word_xxx") hoặc HashTable/HashMap nếu không.

Tôi sẽ để lại cách tìm hiểu lý do bạn muốn sử dụng ArrayList vs. a Vector hoặc HashTable vs. HashMap cho bạn vì tôi có nghi ngờ lén lút đây là bài tập về nhà của bạn. Kiểm tra Javadocs.

Bạn sẽ không nhận được bất kỳ phương pháp nào giúp bạn như bạn đã yêu cầu trong các ví dụ ở trên từ lớp Khung bộ sưu tập của bạn, vì không ai trong số họ thực hiện phép so sánh Chuỗi. Trừ khi bạn chỉ muốn đặt hàng chúng theo thứ tự bảng chữ cái hoặc thứ gì đó, trong trường hợp đó bạn sẽ sử dụng một trong các triển khai Tree trong khung Collections.

Answer 6

Tôi không hiểu tại sao có quá nhiều người cho rằng Arraylist, hoặc tương tự, vì bạn không đề cập đến việc phải lặp lại toàn bộ danh sách. Hơn nữa, có vẻ như bạn muốn truy cập chúng dưới dạng cặp khóa/giá trị ("word_348" = "pedantic").

Để truy cập nhanh nhất, tôi sẽ sử dụng TreeMap, sẽ thực hiện tìm kiếm nhị phân để tìm khóa của bạn. Nhược điểm duy nhất của nó là nó không đồng bộ, nhưng đó không phải là một vấn đề cho ứng dụng của bạn.

http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html

Answer 7

Phụ thuộc vào vấn đề là gì - tốc độ hoặc bộ nhớ.

Nếu đó là bộ nhớ, giải pháp tối thiểu là viết hàm getWord (n) quét toàn bộ tệp mỗi khi nó chạy và trích xuất từ ​​n.

Hiện tại - đó không phải là giải pháp tốt. Một giải pháp tốt hơn là quyết định lượng bộ nhớ bạn muốn sử dụng: cho phép nói 1000 mục. Quét tệp cho các từ một lần khi ứng dụng bắt đầu và lưu trữ một loạt các dấu trang chứa số từ và vị trí trong tệp chứa vị trí - làm điều này theo cách sao cho các dấu trang được nhiều khoảng cách đều nhau qua tập tin.

Sau đó, mở tệp để truy cập ngẫu nhiên. Hàm getWord (n) bây giờ nhìn vào dấu trang để tìm từ lớn nhất # < = n (hãy sử dụng tìm kiếm nhị phân), tìm cách đến vị trí được chỉ định và quét tệp, đếm các từ để tìm từ được yêu cầu.

Một giải pháp thậm chí nhanh hơn, sử dụng nhiều hơn memnory, là xây dựng một số loại bộ nhớ cache cho các khối - trên cơ sở đó getWord() yêu cầu thường đi qua trong cụm. Bạn có thể sắp xếp mọi thứ để nếu ai đó yêu cầu từ # X và không có dấu trang thì bạn tìm kiếm và đặt vào dấu trang, lưu bộ nhớ bằng cách hợp nhất bất kỳ dấu trang nào ít được sử dụng gần đây nhất.

Và cứ tiếp tục như vậy. Nó phụ thuộc, thực sự, về những gì vấn đề là - trên những loại mô hình của retreival có khả năng.

Answer 8

Làm thế nào về một cây radix hoặc Patricia trie?

http://en.wikipedia.org/wiki/Radix_tree

Answer 9

mất của tôi:

Đối với một chương trình phi luồng, một ArrayList là luôn nhanh nhất và đơn giản nhất.

Đối với một chương trình ren, một java.util.concurrent.ConcurrentHashMap < Integer, String > hoặc java.util.concurrent.ConcurrentSkipListMap < Integer, String > là tuyệt vời. Có lẽ sau này bạn muốn cho phép các luồng để tạo ra nhiều truy vấn đối với điều khổng lồ này cùng một lúc.

Answer 10

Lợi thế duy nhất của danh sách được liên kết trên danh sách mảng hoặc mảng sẽ là nếu có chèn và xóa ở các vị trí tùy ý. Tôi không nghĩ đây là trường hợp ở đây: Bạn đọc trong tài liệu và xây dựng danh sách theo thứ tự.

Tôi nghĩ rằng khi áp phích ban đầu nói về việc tìm kiếm "word_2200", anh ta chỉ đơn giản là từ thứ 2200 trong tài liệu và không có nhãn tùy ý được liên kết với từng từ. Nếu vậy, thì tất cả những gì anh ta cần được lập chỉ mục truy cập vào tất cả các từ. Do đó, một mảng hoặc danh sách mảng. Nếu có một cái gì đó phức tạp hơn, nếu một từ có thể được dán nhãn "word_2200" và từ tiếp theo được dán nhãn "foobar_42" hoặc một số như vậy, thì có, anh ta sẽ cần một cấu trúc phức tạp hơn.

Xin chào, bạn có muốn cung cấp cho chúng tôi một gợi ý TẠI SAO bạn muốn thực hiện điều này không? Tôi khó có thể nhớ lần cuối cùng tôi tự nhủ, "Này, tôi tự hỏi liệu từ 1,237 trong tài liệu này tôi đang đọc dài hơn hay ngắn hơn từ 842?"

Answer 11

Nếu bạn đang di chuyển nhanh cũng như kích thước nhỏ gọn, hãy sử dụng DAWG (Biểu đồ từ tuần hoàn định hướng). Cấu trúc dữ liệu này có ý tưởng về một trie và cải thiện nó bằng cách tìm và tính toán các hậu tố phổ biến cũng như tiền tố chung.

http://en.wikipedia.org/wiki/Directed_acyclic_word_graph