Làm cách nào để tối ưu hóa các phép toán trên các bộ boolean lớn (75.000 mục) bằng Python?

Question

Có tập lệnh này có tên là svnmerge.py mà tôi đang cố gắng tinh chỉnh và tối ưu hóa một chút. Tôi hoàn toàn mới với Python mặc dù, vì vậy nó không phải dễ dàng.

Sự cố hiện tại dường như liên quan đến một lớp có tên là RevisionSet trong tập lệnh. Về bản chất những gì nó làm là tạo ra một hashtable lớn (?) Của các giá trị boolean nguyên-key. Trong trường hợp xấu nhất - một cho mỗi lần sửa đổi trong kho SVN của chúng tôi, gần 75.000 bây giờ.

Sau đó, nó thực hiện các hoạt động được đặt trên các mảng lớn như vậy - cộng, trừ, giao lộ, v.v. Việc triển khai thực hiện là việc thực hiện O (n) đơn giản nhất, trong đó, tự nhiên, khá chậm trên các tập lớn như vậy. Toàn bộ cấu trúc dữ liệu có thể được tối ưu hóa bởi vì có các khoảng thời gian dài của các giá trị liên tục. Ví dụ: tất cả các khóa từ 1 đến 74.000 có thể chứa true. Ngoài ra kịch bản được viết cho Python 2.2, đó là một phiên bản khá cũ và chúng tôi đang sử dụng 2,6 anyway, do đó, có thể có một cái gì đó để đạt được điều đó quá.

Tôi có thể tự mình cố gắng cùng nhau, nhưng sẽ rất khó và mất nhiều thời gian - chưa kể rằng nó có thể đã được triển khai ở đâu đó. Mặc dù tôi muốn trải nghiệm học tập, kết quả là quan trọng hơn ngay bây giờ. Những gì bạn sẽ đề nghị tôi làm gì?

Answer 1

Bạn có thể thử làm điều đó với một chút thay vì trăn trơn. Tôi thấy nó là rất nhanh cho các hoạt động như thế này.

Ví dụ:

# Create 1000000 numbers between 0 and 1000, takes 21ms 
x = numpy.random.randint(0, 1000, 1000000) 

# Get all items that are larger than 500, takes 2.58ms 
y = x > 500 

# Add 10 to those items, takes 26.1ms 
x[y] += 10 

Kể từ đó là với rất nhiều hàng, tôi nghĩ rằng 75000 không phải là một vấn đề hoặc :)

Answer 2

Ví dụ, tất cả các phím từ 1 đến 74.000 chứa true

Tại sao không hoạt động trên tập con? Chỉ 74001 đến cuối.

Cắt xén 74/75 dữ liệu của bạn dễ dàng hơn nhiều so với việc cố gắng viết một thuật toán thông minh hơn O (n).

Answer 3

Bạn nên viết lại RevisionSet để có tập hợp các bản chỉnh sửa. Tôi nghĩ rằng các đại diện nội bộ cho một phiên bản nên là một số nguyên và phạm vi sửa đổi nên được tạo ra khi cần thiết.

Không có lý do thuyết phục nào để sử dụng mã hỗ trợ python 2.3 trở xuống.

Answer 4

Chỉ là một ý nghĩ. Tôi đã từng làm điều này bằng cách sử dụng mã hóa chạy trong thao tác hình ảnh nhị phân. Tức là, lưu trữ từng bộ như một dãy số: số bit tắt, số bit trên, số bit tắt, v.v.

Sau đó, bạn có thể thực hiện tất cả các thao tác boolean trên chúng dưới dạng trang trí trên một kết hợp đơn giản thuật toán.

Answer 5

Đây là sự thay thế nhanh cho RevisionSet đặt thành bộ. Nó sẽ nhanh hơn nhiều. Tôi đã không kiểm tra đầy đủ nó, nhưng nó đã làm việc với tất cả các bài kiểm tra mà tôi đã làm. Chắc chắn có những cách khác để tăng tốc mọi thứ, nhưng tôi nghĩ rằng điều này thực sự hữu ích vì nó thực sự khai thác nhanh các bộ thay vì làm các vòng lặp trong Python mà mã gốc đang hoạt động trong các chức năng như __sub__ và __and__. Vấn đề duy nhất với nó là iterator không được sắp xếp.Bạn có thể phải thay đổi một chút mã để giải thích điều này. Tôi chắc chắn có những cách khác để cải thiện điều này, nhưng hy vọng nó sẽ cho bạn một khởi đầu tốt.

class RevisionSet(set): 
    """ 
    A set of revisions, held in dictionary form for easy manipulation. If we 
    were to rewrite this script for Python 2.3+, we would subclass this from 
    set (or UserSet). As this class does not include branch 
    information, it's assumed that one instance will be used per 
    branch. 
    """ 
    def __init__(self, parm): 
     """Constructs a RevisionSet from a string in property form, or from 
     a dictionary whose keys are the revisions. Raises ValueError if the 
     input string is invalid.""" 


     revision_range_split_re = re.compile('[-:]') 

     if isinstance(parm, set): 
      print "1" 
      self.update(parm.copy()) 
     elif isinstance(parm, list): 
      self.update(set(parm)) 
     else: 
      parm = parm.strip() 
      if parm: 
       for R in parm.split(","): 
        rev_or_revs = re.split(revision_range_split_re, R) 
        if len(rev_or_revs) == 1: 
         self.add(int(rev_or_revs[0])) 
        elif len(rev_or_revs) == 2: 
         self.update(set(range(int(rev_or_revs[0]), 
             int(rev_or_revs[1])+1))) 
        else: 
         raise ValueError, 'Ill formatted revision range: ' + R 

    def sorted(self): 
     return sorted(self) 

    def normalized(self): 
     """Returns a normalized version of the revision set, which is an 
     ordered list of couples (start,end), with the minimum number of 
     intervals.""" 
     revnums = sorted(self) 
     revnums.reverse() 
     ret = [] 
     while revnums: 
      s = e = revnums.pop() 
      while revnums and revnums[-1] in (e, e+1): 
       e = revnums.pop() 
      ret.append((s, e)) 
     return ret 

    def __str__(self): 
     """Convert the revision set to a string, using its normalized form.""" 
     L = [] 
     for s,e in self.normalized(): 
      if s == e: 
       L.append(str(s)) 
      else: 
       L.append(str(s) + "-" + str(e)) 
     return ",".join(L) 

Addition: Bằng cách này, tôi so sánh làm công đoàn, các nút giao thông và subtractions của RevisionSet gốc và RevisionSet của tôi ở trên, và các mã trên là từ 3x đến 7X nhanh hơn đối với những người hoạt động khi hoạt động trên hai Các bản sửa đổi có 75.000 phần tử. Tôi biết rằng những người khác đang nói rằng đó là cách để đi, nhưng nếu bạn không có kinh nghiệm với Python, như bình luận của bạn chỉ ra, thì bạn có thể không muốn đi tuyến đường đó vì nó sẽ liên quan đến nhiều thay đổi hơn. Tôi khuyên bạn nên thử mã của tôi, xem nó có hoạt động không và nếu có, hãy xem nó có đủ nhanh cho bạn hay không. Nếu nó không phải là, sau đó tôi sẽ cố gắng profiling để xem những gì cần phải được cải thiện. Chỉ sau đó tôi sẽ xem xét sử dụng numpy (đó là một gói tuyệt vời mà tôi sử dụng khá thường xuyên).