Thiết kế một thuật toán, tìm từ thường dùng nhất trong sách

Question

Câu hỏi phỏng vấn:

Tìm từ thường dùng nhất trong sách.

Ý tưởng của tôi:

Sử dụng bảng băm, di chuyển và đánh dấu bảng băm.

Nếu kích thước của sách được biết, nếu sử dụng bất kỳ từ nào> 50%, hãy bỏ qua bất kỳ từ mới nào trong quá trình truyền tải sau đây và chỉ đếm các từ cũ. Điều gì sẽ xảy ra nếu kích thước sách không xác định?

Đó là thời gian và không gian O (n) và O (n).

Bất kỳ ý tưởng nào tốt hơn?

Cảm ơn

Answer 1

Thường Heap là cấu trúc dữ liệu mà phù hợp tốt khi chúng ta phải xác định một cái gì đó giống như hầu hết/sử dụng nhất.

Ngay cả Python;s Counter.nlargest được sử dụng cho các mục đích này được triển khai thông qua cấu trúc dữ liệu Heap.

Một Binary Heap dữ liệu cấu trúc có phức tạp sau

CreateHeap - O(1) 
FindMin - O(1) 
deleteMin - O(logn) 
Insert - O(logn) 

Tôi chạy một comparition trên Hash (sử dụng từ điển mặc định trong Python) và Heap (sử dụng Collections.Counter.nlargest trong python) và Hash là fairing hơi tốt hơn so với Heap.

>>> stmt1=""" 
import collections, random 
somedata=[random.randint(1,1000) for i in xrange(1,10000)] 
somehash=collections.defaultdict(int) 
for d in somedata: 
    somehash[d]+=1 
maxkey=0 
for k,v in somehash.items(): 
    if somehash[maxkey] > v: 
     maxkey=k 
""" 
>>> stmt2=""" 
import collections,random 
somedata=[random.randint(1,1000) for i in xrange(1,10000)] 
collections.Counter(somedata).most_common(1) 
""" 
>>> t1=timeit.Timer(stmt=stmt1) 
>>> t2=timeit.Timer(stmt=stmt2) 
>>> print "%.2f usec/pass" % (1000000 * t2.timeit(number=10)/10) 
38168.96 usec/pass 
>>> print "%.2f usec/pass" % (1000000 * t1.timeit(number=10)/10) 
33600.80 usec/pass 

Answer 2

Có một sự tổng quát của Tối ưu hóa của bạn nếu kích thước cuốn sách nổi tiếng và bất kỳ từ nào bạn đã thấy có một số> số còn lại của từ + các cao nhất kế tiếp đếm, từ cao nhất tính hiện tại của bạn là câu trả lời.

Answer 3

Để xác định độ phức tạp, tôi nghĩ bạn cần xem xét hai biến, n = tổng số từ, m = số từ duy nhất. Tôi tưởng tượng sự phức tạp của trường hợp tốt nhất sẽ xuất hiện gần O (n log (m)) cho tốc độ, và O (m) để lưu trữ, giả sử mỗi lần bạn lặp qua từng từ n, và xây dựng và tìm kiếm dựa trên bảng băm hoặc cấu trúc như vậy mà cuối cùng chứa các phần tử m.

Answer 4

Giải pháp của bạn là chính xác, nhanh chóng và có thể là giải pháp tốt nhất/dễ nhất từ ​​quan điểm thực tế.

Các giải pháp của người đăng khác có độ phức tạp về thời gian tồi tệ hơn giải pháp của bạn. Đối với một băm, như bạn đang sử dụng, độ phức tạp thời gian thực sự là O (n). Mỗi chèn là O (1) và có n từ, do đó, giai đoạn chèn chi phí O (n). Lặp lại và tìm số tối đa là O (n). Không gian cũng là O (n) như bạn đã đề cập. Lưu ý rằng bạn sẽ không thể chấm dứt thuật toán của bạn sớm bằng cách sử dụng giải pháp của Chris vì tìm kiếm bảng băm của bạn là tốn kém và không có cách nào để bạn thực hiện điều này trong thời gian O (1) sau mỗi lần chèn.

Heap sẽ tốn nhiều thời gian hơn vì bạn cần duy trì heap trong mỗi lần chèn. Một chèn heap là O (log (n)) và do đó tổng chi phí cho việc chèn sẽ là O (nlog (n)).

Answer 5

Đây thực sự là ví dụ cổ điển về số map reduce.

Ví dụ trong trang wikipedia sẽ cung cấp cho bạn số từ của mỗi từ duy nhất, nhưng bạn có thể dễ dàng thêm bước trong bước giảm theo dõi từ phổ biến nhất hiện tại (với một số loại mutex để xử lý vấn đề tương tranh).

Nếu bạn có một cụm máy phân tán hoặc một máy tính có tính song song cao, điều này sẽ chạy nhanh hơn nhiều so với sử dụng bảng băm.

Answer 6

Nếu bạn đang xử lý sách, bạn biết từ vựng và tần số từ gần đúng. Ngay cả khi bạn không đưa thông tin này lên phía trước, bạn có thể có được ước tính tốt bằng cách quét một mẫu ngẫu nhiên.

Để có câu trả lời chính xác, tôi sẽ sử dụng hàm băm hoàn hảo của các từ phổ biến nhất. Hàm băm hoàn hảo yêu cầu bộ nhớ O (k) và đảm bảo tra cứu O (1) trường hợp xấu nhất nhanh nhất.

Đối với các từ không phổ biến, tôi sẽ sử dụng hàng đợi ưu tiên được triển khai dưới dạng cây heap hoặc cây tự cân bằng. Một bảng băm thông thường cũng có thể là một lựa chọn tốt.