Lập lịch Shift hiệu quả trong Python

Question

Tôi hiện đang làm việc để thực hiện một số mô phỏng lập kế hoạch thay đổi cho một công ty mô hình thuế. Công ty hoạt động 350 xe taxi, và tất cả đều được sử dụng vào bất kỳ ngày nào. Mỗi người lái xe làm việc 5 ca mỗi 12 giờ và mỗi ngày có bốn ca làm việc chồng chéo nhau. Có ca từ 3: 00-15: 00, 15: 00-3: 00, 16: 00-4: 00 và 4: 00-16: 00. Tôi đã phát triển nó trong Python ban đầu, bởi vì sự cần thiết phải phát triển nhanh chóng nó, và tôi nghĩ rằng hiệu suất sẽ được chấp nhận. Các thông số ban đầu chỉ yêu cầu hai ca một ngày (3: 00-15: 00, và 15: 00-3: 00), và trong khi hiệu suất là không lớn, nó đã đủ tốt cho việc sử dụng của tôi. Nó có thể lập lịch trình hàng tuần cho các trình điều khiển trong khoảng 8 phút, sử dụng thuật toán brute force đơn giản (đánh giá tất cả các hoán đổi tiềm năng để xem liệu tình hình có thể được cải thiện không.)

Với bốn thay đổi chồng chéo, hiệu suất hoàn toàn vô cùng. Phải mất hơn một giờ để thực hiện một lịch trình hàng tuần. Tôi đã thực hiện một số hồ sơ bằng cách sử dụng cProfile, và có vẻ như thủ phạm chính là hai phương pháp. Một là một phương pháp để xác định nếu có một xung đột khi đặt một trình điều khiển trong một sự thay đổi. Nó đảm bảo rằng họ không phục vụ trong một sự thay đổi trong cùng một ngày, hoặc phục vụ trong những thay đổi trước hoặc sau. Chỉ với hai ca một ngày, điều này thật dễ dàng. Một cách đơn giản là phải xác định xem người lái xe đã được lên kế hoạch để làm việc trong ca làm việc trực tiếp trước hoặc sau đó. Với bốn thay đổi chồng chéo, điều này đã trở nên phức tạp hơn. Thủ phạm thứ hai là phương pháp xác định liệu ca làm việc là ca ngày hay đêm. Một lần nữa, với hai thay đổi ban đầu, điều này dễ dàng như xác định nếu số ca là chẵn hoặc lẻ, với số ca thay đổi bắt đầu bằng 0. Lần dịch đầu tiên (shift 0) được chỉ định là ca đêm, ngày tiếp theo là ngày và Vv và vv. Bây giờ hai người đầu tiên là đêm, hai người tiếp theo là, vv Những phương pháp này gọi nhau, vì vậy tôi sẽ đặt cơ thể của họ bên dưới.

def conflict_exists(shift, driver, shift_data): 
    next_type = get_stype((shift+1) % 28) 
    my_type = get_stype(shift) 

    nudge = abs(next_type - my_type) 

    if driver in shift_data[shift-2-nudge] or driver in shift_data[shift-1-nudge] or driver in shift_data[(shift+1-(nudge*2)) % 28] or driver in shift_data[(shift+2-nudge) % 28] or driver in shift_data[(shift+3-nudge) % 28]: 
     return True 
    else: 
     return False 

Lưu ý rằng get_stype trả về kiểu thay đổi, với 0 cho biết đó là ca đêm và 1 cho biết đó là ca làm việc trong ngày.

Để xác định loại chuyển đổi, tôi đang sử dụng phương pháp này:

def get_stype(k): 
    if (k/4.0) % 1.0 < 0.5: 
     return 0 
    else: 
     return 1 

Và đây là kết quả có liên quan từ cProfile:

 ncalls tottime percall cumtime percall 
    57662556 19.717 0.000 19.717 0.000 sim8.py:241(get_stype) 
    28065503 55.650 0.000 77.591 0.000 sim8.py:247(in_conflict) 

Có ai có bất kỳ sagely lời khuyên hoặc lời khuyên về làm thế nào tôi có thể đi về việc cải thiện hiệu suất của kịch bản này? Mọi sự trợ giúp sẽ rất được trân trọng!

Chúc mừng,

Tim

EDIT: Xin lỗi, tôi phải làm rõ rằng các dữ liệu từ mỗi ca được lưu giữ như là một tập ví dụ: shift_data [k] là loại tập dữ liệu.

EDIT 2:

Thêm vòng lặp chính, theo yêu cầu dưới đây, cùng với các phương pháp khác gọi. Đó là một chút lộn xộn, và tôi xin lỗi vì điều đó.

def optimize_schedule(shift_data, driver_shifts, recheck): 
    skip = set() 

    if len(recheck) == 0: 
     first_run = True 
     recheck = [] 
     for i in xrange(28): 
      recheck.append(set()) 
    else: 
     first_run = False 

    for i in xrange(28): 

     if (first_run): 
      targets = shift_data[i] 
     else: 
      targets = recheck[i] 

     for j in targets: 
      o_score = eval_score = opt_eval_at_coord(shift_data, driver_shifts, i, j) 

      my_type = get_stype(i) 
      s_type_fwd = get_stype((i+1) % 28) 

      if (my_type == s_type_fwd): 
       search_direction = (i + 2) % 28 
       end_direction = i 
      else: 
       search_direction = (i + 1) % 28 
       end_direction = (i - 1) % 28 

      while True: 
       if (end_direction == search_direction): 
        break 
       for k in shift_data[search_direction]: 

        coord = search_direction * 10000 + k 

        if coord in skip: 
         continue 

        if k in shift_data[i] or j in shift_data[search_direction]: 
         continue 

        if in_conflict(search_direction, j, shift_data) or in_conflict(i, k, shift_data): 
         continue 

        node_a_prev_score = o_score 
        node_b_prev_score = opt_eval_at_coord(shift_data, driver_shifts, search_direction, k) 

        if (node_a_prev_score == 1) and (node_b_prev_score == 1): 
         continue 

        a_type = my_type 
        b_type = get_stype(search_direction) 

        if (node_a_prev_score == 1): 
         if (driver_shifts[j]['type'] == 'any') and (a_type != b_type): 
          test_eval = 2 
         else: 
          continue 
        elif (node_b_prev_score == 1): 
         if (driver_shifts[k]['type'] == 'any') and (a_type != b_type): 
          test_eval = 2 
         else: 
          test_eval = 0 
        else: 
         if (a_type == b_type): 
          test_eval = 0 
         else: 
          test_eval = 2 

        print 'eval_score: %f' % test_eval 

        if (test_eval > eval_score): 

         cand_coords = [search_direction, k] 
         eval_score = test_eval 
         if (test_eval == 2.0): 
          break 
       else: 
        search_direction = (search_direction + 1) % 28 
        continue 

       break 

      if (eval_score > o_score): 
       print 'doing a swap: ', 
       print cand_coords, 

       shift_data[i].remove(j) 
       shift_data[i].add(cand_coords[1]) 

       shift_data[cand_coords[0]].add(j) 
       shift_data[cand_coords[0]].remove(cand_coords[1]) 

       if j in recheck[i]: 
        recheck[i].remove(j) 

       if cand_coords[1] in recheck[cand_coords[0]]:    
        recheck[cand_coords[0]].remove(cand_coords[1]) 

       recheck[cand_coords[0]].add(j) 
       recheck[i].add(cand_coords[1]) 

      else: 
       coord = i * 10000 + j 
       skip.add(coord) 

    if first_run: 
     shift_data = optimize_schedule(shift_data, driver_shifts, recheck) 

    return shift_data 



def opt_eval_at_coord(shift_data, driver_shifts, i, j): 
    node = j 
    if in_conflict(i, node, shift_data): 
     return float('-inf') 
    else: 
     s_type = get_stype(i) 

     d_pref = driver_shifts[node]['type'] 

     if (s_type == 0 and d_pref == 'night') or (s_type == 1 and d_pref == 'day') or (d_pref == 'any'): 
      return 1 
     else: 
      return 0 

Answer 1

Không có gì mà rõ ràng sẽ làm chậm các chức năng này xuống là, và thực sự họ không chậm. Họ chỉ được gọi rất nhiều. Bạn nói rằng bạn đang sử dụng thuật toán brute force - bạn có thể viết một thuật toán không thử mọi kết hợp có thể không? Hoặc là có một cách hiệu quả hơn để làm điều đó, giống như lưu trữ dữ liệu bằng trình điều khiển chứ không phải bằng ca?

Tất nhiên, nếu bạn cần speedups ngay lập tức, nó có thể được hưởng lợi từ chạy trong một thông dịch viên như PyPy, hoặc sử dụng Cython để chuyển đổi phần quan trọng đối với C.

Answer 2

Tôi không nghĩ vấn đề của bạn là thời gian cần để chạy hai chức năng đó. Lưu ý rằng giá trị percall cho các chức năng là 0.000. Điều này có nghĩa là mỗi lần hàm được gọi, nó mất ít hơn 1 mili giây.

Tôi nghĩ rằng vấn đề của bạn là số lần các hàm được gọi. Một cuộc gọi hàm trong python là tốn kém. Ví dụ, gọi một hàm không có gì là 57,662,556 lần mất 7.15 giây trên máy của tôi:

>>> from timeit import Timer 
>>> t = Timer("t()", setup="def t(): pass") 
>>> t.timeit(57662556) 
7.159075975418091 

Một điều tôi muốn tò mò là biến số shift_data. Các danh sách giá trị hoặc dicts?

driver in shift_data[shift-2-nudge] 

Các in sẽ mất thời gian O(N) nếu đó là một danh sách nhưng O(1) thời gian nếu đó là một dict.

EDIT: Kể từ khi giá trị shift_data là bộ, mà nên sử dụng tốt

Answer 3

Hmm. Thú vị và vui vẻ tìm kiếm vấn đề. Tôi sẽ phải nhìn vào nó nhiều hơn. Bây giờ, tôi có điều này để cung cấp: Tại sao bạn giới thiệu phao nổi? Tôi sẽ làm get_stype() như sau:

def get_stype(k): 
    if k % 4 < 2: 
     return 0 
    return 1 

Nó không phải là một tăng tốc lớn, nhưng nó nhanh hơn (và đơn giản hơn). Ngoài ra, bạn không phải làm mod 28 bất cứ khi nào bạn đang cho ăn get_stype, bởi vì nó đã được chăm sóc bởi mod 4 trong get_stype.

Nếu có những cải tiến đáng kể, chúng sẽ có dạng thuật toán tốt hơn. (Tôi không nói rằng thuật toán của bạn là xấu, hoặc rằng có bất kỳ một tốt hơn.Tôi đã không thực sự dành đủ thời gian nhìn vào nó.Nhưng nếu không có một thuật toán tốt hơn để được tìm thấy, sau đó thêm đáng kể tăng tốc độ sẽ phải đến từ việc sử dụng PyPy, Cython, Shed Skin hoặc viết lại bằng một ngôn ngữ khác (nhanh hơn) hoàn toàn.)

Answer 4

Có vẻ như tôi trao đổi giữa hai ca ngày hoặc giữa hai ca đêm sẽ không bao giờ giúp đỡ. Nó sẽ không thay đổi các trình điều khiển như thế nào như những thay đổi và nó sẽ không thay đổi cách những thay đổi xung đột với những thay đổi khác. Vì vậy, tôi nghĩ bạn sẽ chỉ có thể lên kế hoạch cho hai ca thay đổi ban đầu, ban ngày và ban đêm, và chỉ sau đó chia các trình điều khiển được giao vào ca làm hai ca thực tế.