Tôi đã chơi ở nơi làm việc với một số lượng dữ liệu rất lớn, thường là hàng tỷ nguyên tố, tất cả được duy trì trong đám mây memcached và định kỳ chuyển vào tệp và đối với một trong các tác vụ của tôi, tôi đang cố gắng đếm cardinality của bộ này.Làm thế nào để bạn đếm số lượng thẻ dữ liệu rất lớn một cách hiệu quả bằng Python?
Đối với một số ngữ cảnh, mỗi mục chứa IP và một số thuộc tính khác xác định một người và được mã hóa trong base64, kích thước mục là 20 byte. Giảm kích thước của một mục bằng cách loại bỏ một số trường không phải là một khả năng.
Đây là cái gì mà giả lập bộ dữ liệu của tôi như là một phiên bản trong bộ nhớ (nhờ this post cho thế hệ string):
import base64, os
dataset_size = 10000000000 # that's 10 billion, be careful if you run it !
big_dataset = [base64.b64encode(os.urandom(10)) for i in range(dataset_size)]
tiếp cận đầu tiên của tôi là sử dụng một HashSet như thế này:
uniques = set(big_dataset)
print "Cardinality: %d" % len(uniques)
Trong khi lý thuyết này hoạt động tốt trên một tập dữ liệu nhỏ, như bạn có thể đoán có một trục trặc:
- Tôi không thể đưa ra giả định về tính duy nhất của dữ liệu của mình. Tôi có thể có 50% số liệu của mình là duy nhất hoặc tôi cũng có thể có 100%. Điều này được tạo tự động theo các khoảng thời gian đều đặn và thay đổi tùy thuộc vào nhiều yếu tố (ví dụ trong ngày ví dụ)
- Kích thước tập hợp trong 10 tỷ. Mỗi mục được mã hóa trong cơ sở 64 là 20 byte, trung bình 10 tỷ trung bình là vài trăm gigabyte. Thật không may, tôi không có quyền truy cập vào một máy có nhiều RAM!
Tôi đã thực hiện bài tập ở nhà và tìm thấy một số tài liệu nghiên cứu hay một số thư viện ít người biết đến, nhưng một phần của mục đích là hiểu cách tiếp cận nào hoạt động và tại sao.
Vì vậy, tôi đang gọi cho bạn Người dùng Python, bạn có biết bất kỳ thuật toán nào có thể giúp tôi ước tính số lượng thẻ hiệu quả không? Bởi sự phức tạp, tôi có nghĩa là tôi không quan tâm nhiều đến việc chạy phức tạp thời gian, nhưng tôi tập trung hơn vào sự phức tạp của không gian. Tôi không ngại hy sinh một chút chính xác nếu nó tăng hiệu suất rất nhiều (vì vậy tôi không nhất thiết phải biết chính xác số lượng đơn lẻ, ngay cả khi điều đó là lý tưởng, nhưng có lẽ không phải là cách tiếp cận khả thi). Tôi sẽ nói lên đến 5% sẽ được chấp nhận. Tôi đang tìm một cái gì đó đặc biệt trong Python cho dự án này.
Cảm ơn bạn đã trợ giúp bạn có thể cung cấp! Như một số người đã lưu ý, tôi có thể sử dụng Hadoop/MR, nhưng đối với các dự án cụ thể này, chúng tôi không muốn đi theo hướng MR và muốn khám phá các thuật toán để thực hiện điều này trên một máy duy nhất một cách hiệu quả, vì điều này có thể được áp dụng cho một vài dự án khác nhau.
Chỉ cần một gợi ý, nhưng điều này có vẻ như cái gì đó có thể tốt cho khuôn khổ Bản đồ-Giảm - yếu tố bản đồ trong dữ liệu của bạn xuống để đếm trong một cuốn từ điển hoặc một cái gì đó . Đối với điều này, bạn có thể sử dụng [MRJob] (https://github.com/Yelp/mrjob), khung công tác Map-Reduce của Python được tạo bởi Yelp. Chạy nó tại Amazon EC2 với MRJob cũng có thể là một ý tưởng tốt cho bạn. Tôi đã sử dụng nó cho số lượng tần số từ trong corpra lớn trước đây. Tôi đoán nó phụ thuộc chính xác vào cách bạn sẽ phân tích các phần tử dữ liệu riêng lẻ. – ely
Cảm ơn gợi ý, vâng tôi đã nghĩ về MR (tôi đang sử dụng nó rất nhiều trong các dự án khác), nhưng đối với vấn đề cụ thể này, MR/Hadoop không phải là một lựa chọn, chúng tôi muốn xem xét các thuật toán làm điều này trong một máy đơn như là một phần của một bằng chứng về khái niệm. –
Nếu độ chính xác 100% không quan trọng, có lẽ một bộ lọc nở sẽ cho bạn 5% lỗi phù hợp với bộ nhớ? Nếu không, và một máy duy nhất là cần thiết, bạn có thể chỉ cần sử dụng một số cơ sở dữ liệu nosql đơn giản với các khóa duy nhất, lưu trữ trên đĩa và loại bỏ các bản sao. nó sẽ chậm, nhưng nó sẽ làm việc với bất kỳ số lượng ram bạn có. Bạn vẫn có thể song song công việc chèn thực tế. –