Câu hỏi Các chuỗi dài nhất đều nhau


Tôi có một triệu số nguyên theo thứ tự sắp xếp và tôi muốn tìm chuỗi dài nhất mà sự khác biệt giữa các cặp liên tiếp bằng nhau. Ví dụ

1, 4, 5, 7, 8, 12

có một chuỗi

   4,       8, 12

Phương pháp ngây thơ của tôi là tham lam và chỉ kiểm tra như thế nào đến nay bạn có thể mở rộng một subsequence từ mỗi điểm. Điều này có O(n²) thời gian cho mỗi điểm có vẻ như.

Có cách nào nhanh hơn để giải quyết vấn đề này không?

Cập nhật. Tôi sẽ kiểm tra mã được đưa ra trong các câu trả lời càng sớm càng tốt (cảm ơn bạn). Tuy nhiên rõ ràng là việc sử dụng bộ nhớ n ^ 2 sẽ không hoạt động. Cho đến nay không có mã nào kết thúc với đầu vào [random.randint(0,100000) for r in xrange(200000)] .

Thời gian.  Tôi đã thử nghiệm với dữ liệu đầu vào sau đây trên hệ thống 32 bit của mình.

a= [random.randint(0,10000) for r in xrange(20000)] 
a.sort()
  • Phương pháp lập trình động của ZelluX sử dụng 1,6G RAM và mất 2 phút và 14 giây. Với pypy nó chỉ mất 9 giây! Tuy nhiên nó bị treo với một lỗi bộ nhớ trên đầu vào lớn.
  • Phương pháp thời gian O (nd) của Armin mất 9 giây với pypy nhưng chỉ có 20MB RAM. Tất nhiên điều này sẽ tồi tệ hơn nhiều nếu phạm vi lớn hơn nhiều. Việc sử dụng bộ nhớ thấp có nghĩa là tôi cũng có thể thử nghiệm nó với a = [random.randint (0,100000) cho r trong xrange (200000)] nhưng nó không kết thúc trong vài phút tôi đã cho nó với pypy.

Để có thể kiểm tra phương pháp của Kluev tôi reran với

a= [random.randint(0,40000) for r in xrange(28000)] 
a = list(set(a))
a.sort()

để tạo danh sách độ dài gần 20000. Tất cả timings với pypy

  • ZelluX, 9 giây
  • Kluev, 20 giây
  • Armin, 52 giây

Dường như nếu phương pháp ZelluX có thể được tạo ra không gian tuyến tính thì nó sẽ là người chiến thắng rõ ràng.


76
2017-08-10 07:59


gốc


Bạn nghĩ điều này được thực hiện nhanh như thế nào? - Mitch Wheat
Tôi không hiểu tất cả các downvotes, và đặc biệt không phải là các phiếu bầu (off-topic, phù hợp hơn cho Siêu người dùng? Nghiêm túc?). Đó là một vấn đề thú vị mà tôi cũng muốn thấy câu trả lời. Vì vậy, +1 từ tôi. - Tim Pietzcker
@ user2179021: Bạn có thể cải thiện câu hỏi của mình bằng cách bao gồm mã bạn đã có. Điều đó dường như làm dịu đi một số người dùng SO quan trọng hơn. Đừng lo lắng về các downvotes cho bây giờ. - Tim Pietzcker
@TimPietzcker Tôi ở cùng bạn ở đây, tôi đã thấy nhiều câu hỏi tồi tệ hơn, tôi nghĩ nó tốt ở đây - Roman Pekar
Trong ví dụ, điều quyết định rằng 4, 8, 12 là đầu ra chính xác trên 1, 4, 7 đó là một chuỗi dài không kém? - Vulcan


Các câu trả lời:


Cập nhật: Thuật toán đầu tiên được mô tả ở đây bị lỗi thời bởi Câu trả lời thứ hai của Armin Rigo, đơn giản và hiệu quả hơn nhiều. Nhưng cả hai phương pháp này đều có một bất lợi. Họ cần nhiều giờ để tìm ra kết quả cho một triệu số nguyên. Vì vậy, tôi đã thử hai biến thể khác (xem phần thứ hai của câu trả lời này), nơi phạm vi của số nguyên đầu vào được giả định là bị giới hạn. Giới hạn này cho phép các thuật toán nhanh hơn nhiều. Ngoài ra tôi đã cố gắng tối ưu hóa mã của Armin Rigo. Xem kết quả điểm chuẩn của tôi ở cuối.


Đây là một ý tưởng về thuật toán sử dụng bộ nhớ O (N). Độ phức tạp thời gian là O (N2 log N), nhưng có thể giảm xuống O (N2).

Thuật toán sử dụng các cấu trúc dữ liệu sau:

  1. prev: mảng các chỉ mục trỏ đến phần tử trước đó (có thể chưa hoàn thành).
  2. hash: hashmap với khóa = sự khác biệt giữa các cặp liên tiếp trong chuỗi và giá trị = hai hashmaps khác. Đối với các hashmaps khác: key = bắt đầu / kết thúc chỉ số của các subsequence, value = pair (chiều dài sau đó, kết thúc / bắt đầu chỉ số của các subsequence).
  3. pq: hàng đợi ưu tiên cho tất cả các giá trị "khác biệt" có thể có cho các chuỗi được lưu trữ trong prev và hash.

Thuật toán:

  1. Khởi tạo prev với các chỉ mục i-1. Cập nhật hash và pq để đăng ký tất cả (không đầy đủ) sau đó được tìm thấy trên bước này và "sự khác biệt" của chúng.
  2. Nhận (và loại bỏ) "sự khác biệt" nhỏ nhất từ pq. Nhận hồ sơ tương ứng từ hash và quét một trong các bản đồ băm cấp hai. Tại thời điểm này tất cả các chuỗi với "sự khác biệt" được cho là hoàn tất. Nếu bản đồ băm cấp thứ hai chứa độ dài của chuỗi tốt hơn so với tìm thấy cho đến thời điểm này, hãy cập nhật kết quả tốt nhất.
  3. Trong mảng prev: cho mỗi phần tử của bất kỳ chuỗi nào được tìm thấy trên bước # 2, chỉ mục giảm và cập nhật hash và có thể pq. Trong khi cập nhật hash, chúng tôi có thể thực hiện một trong các hoạt động sau: thêm một chuỗi mới có độ dài 1 hoặc tăng một số chuỗi hiện tại lên 1 hoặc kết hợp hai chuỗi hiện có.
  4. Xóa bản ghi băm bản đồ được tìm thấy ở bước # 2.
  5. Tiếp tục từ bước # 2 trong khi pq không có sản phẩm nào.

Thuật toán này cập nhật các phần tử O (N) của prev O (N) lần mỗi. Và mỗi bản cập nhật này có thể yêu cầu thêm "sự khác biệt" mới vào pq. Tất cả điều này có nghĩa là độ phức tạp thời gian của O (N2 log N) nếu chúng ta sử dụng thực hiện heap đơn giản cho pq. Để giảm nó thành O (N2) chúng tôi có thể sử dụng các triển khai hàng đợi ưu tiên nâng cao hơn. Một số khả năng được liệt kê trên trang này: Hàng đợi ưu tiên.

Xem mã Python tương ứng trên Ideone. Mã này không cho phép các phần tử trùng lặp trong danh sách. Có thể khắc phục điều này, nhưng nó sẽ là một tối ưu hóa tốt để loại bỏ các bản sao (và để tìm ra các chuỗi dài nhất ngoài các bản sao riêng biệt).

cùng một mã sau một tối ưu hóa nhỏ. Ở đây tìm kiếm được chấm dứt ngay sau khi chiều dài sau đó nhân với "sự khác biệt" sau đó có thể vượt quá phạm vi danh sách nguồn.


Mã của Armin Rigo rất đơn giản và khá hiệu quả. Nhưng trong một số trường hợp, có một số tính toán bổ sung có thể tránh được. Tìm kiếm có thể bị chấm dứt ngay sau khi chiều dài sau đó nhân với số "chênh lệch" sau đó có thể vượt quá phạm vi danh sách nguồn:

def findLESS(A):
  Aset = set(A)
  lmax = 2
  d = 1
  minStep = 0

  while (lmax - 1) * minStep <= A[-1] - A[0]:
    minStep = A[-1] - A[0] + 1
    for j, b in enumerate(A):
      if j+d < len(A):
        a = A[j+d]
        step = a - b
        minStep = min(minStep, step)
        if a + step in Aset and b - step not in Aset:
          c = a + step
          count = 3
          while c + step in Aset:
            c += step
            count += 1
          if count > lmax:
            lmax = count
    d += 1

  return lmax

print(findLESS([1, 4, 5, 7, 8, 12]))

Nếu phạm vi của các số nguyên trong dữ liệu nguồn (M) là nhỏ, một thuật toán đơn giản là có thể với O (M2) thời gian và không gian O (M):

def findLESS(src):
  r = [False for i in range(src[-1]+1)]
  for x in src:
    r[x] = True

  d = 1
  best = 1

  while best * d < len(r):
    for s in range(d):
      l = 0

      for i in range(s, len(r), d):
        if r[i]:
          l += 1
          best = max(best, l)
        else:
          l = 0

    d += 1

  return best


print(findLESS([1, 4, 5, 7, 8, 12]))

Nó tương tự như phương pháp đầu tiên của Armin Rigo, nhưng nó không sử dụng bất kỳ cấu trúc dữ liệu động nào. Tôi cho rằng dữ liệu nguồn không có bản sao. Và (để giữ mã đơn giản), tôi cũng giả sử rằng giá trị đầu vào tối thiểu là không âm và gần bằng không.


Thuật toán trước có thể được cải thiện nếu thay vì mảng boolean chúng ta sử dụng cấu trúc dữ liệu bitet và các hoạt động bitwise để xử lý dữ liệu song song. Mã được hiển thị dưới đây thực hiện bitet như một số nguyên Python dựng sẵn. Nó có cùng các giả định: không có bản sao, giá trị đầu vào tối thiểu là không âm và gần bằng không. Độ phức tạp thời gian là O (M2 * log L) trong đó L là độ dài của dãy tối ưu, độ phức tạp của không gian là O (M):

def findLESS(src):
  r = 0
  for x in src:
    r |= 1 << x

  d = 1
  best = 1

  while best * d < src[-1] + 1:
    c = best
    rr = r

    while c & (c-1):
      cc = c & -c
      rr &= rr >> (cc * d)
      c &= c-1

    while c != 1:
      c = c >> 1
      rr &= rr >> (c * d)

    rr &= rr >> d

    while rr:
      rr &= rr >> d
      best += 1

    d += 1

  return best

Điểm chuẩn:

Dữ liệu đầu vào (khoảng 100000 số nguyên) được tạo theo cách này:

random.seed(42)
s = sorted(list(set([random.randint(0,200000) for r in xrange(140000)])))

Và đối với các thuật toán nhanh nhất, tôi cũng sử dụng dữ liệu sau (khoảng 1000000 số nguyên):

s = sorted(list(set([random.randint(0,2000000) for r in xrange(1400000)])))

Tất cả kết quả hiển thị thời gian tính bằng giây:

Size:                         100000   1000000
Second answer by Armin Rigo:     634         ?
By Armin Rigo, optimized:         64     >5000
O(M^2) algorithm:                 53      2940
O(M^2*L) algorithm:                7       711

11
2017-08-11 10:08



Tôi phải thừa nhận tôi không hiểu giải pháp này. Bạn có thể cung cấp một số mã không? - eleanora
@ user2179021: Không chắc chắn nó sẽ giúp. Đó là khá nhiều mã. Không dễ viết. Quá phức tạp để hiểu. Tôi vẫn hy vọng có thể lấy ý tưởng từ mô tả ngắn này. Có lẽ bạn có câu hỏi về một số bước cụ thể? - Evgeny Kluev
Ngay cả bước 1 cũng sẽ hữu ích. Chúng ta đặt cái gì trước, tiếp theo, băm và pq để ở bước đầu tiên bằng cách sử dụng ví dụ 1, 4, 5, 7, 8, 12 trong câu hỏi? - eleanora
@ user2179021: prev là [Nil, 0,1,2,3,4]. next là [1,2,3,4,5, Nil]. pq sẽ chứa tất cả các chênh lệch liền kề: 1,2,3,4. Mỗi chuỗi có chiều dài 1. Giá trị này cùng với các vị trí bắt đầu / kết thúc được lưu trữ trong hash: {1: ({1: 1,3: 1}, {2: 1,4: 1}), 2: ({2: 1}, {3: 1}), 3: ({0: 1} , {1: 1}), 4: ({4: 1}, {5: 1})}. - Evgeny Kluev
@EvgenyKluev Cách tiếp cận của bạn ở đây là tốt hơn trong ít nhất ba cách :) 1. Giải pháp của bạn được song song để làm cho nó thực sự nhanh chóng. 2. Độ phức tạp thời gian là rõ ràng và không phụ thuộc vào kích thước của các con số. Tôi không chắc chắn 100 phần trăm độ phức tạp thời gian của giải pháp được đề xuất cho câu hỏi được liên kết. 3. Nếu bạn có một số ý tưởng về phạm vi khả năng của 'd', các giải pháp của bạn thậm chí còn nhanh hơn. - eleanora


Chúng ta có thể có một giải pháp O(n*m) kịp thời với rất ít nhu cầu bộ nhớ, bằng cách thích ứng với bộ nhớ của bạn. Đây nlà số lượng các mục trong chuỗi đầu vào đã cho, và m là phạm vi, nghĩa là số cao nhất trừ số thấp nhất.

Gọi Một dãy của tất cả các số đầu vào (và sử dụng một precomputed set() để trả lời trong thời gian không đổi, câu hỏi "là số này trong A?"). Gọi d bậc thang của các subsequence chúng tôi đang tìm kiếm (sự khác biệt giữa hai con số của subsequence này). Đối với mọi giá trị có thể có của d, thực hiện quét tuyến tính sau trên tất cả các số đầu vào: cho mỗi số n từ A theo thứ tự tăng dần, nếu số chưa được nhìn thấy, hãy xem A trong khoảng thời gian bắt đầu từ n bằng một bước d. Sau đó đánh dấu tất cả các mục trong chuỗi đó như đã thấy, để chúng tôi tránh tìm kiếm lại từ chúng, cho cùng một d. Bởi vì điều này, sự phức tạp chỉ là O(n) cho mọi giá trị của d.

A = [1, 4, 5, 7, 8, 12]    # in sorted order
Aset = set(A)

for d in range(1, 12):
    already_seen = set()
    for a in A:
        if a not in already_seen:
            b = a
            count = 1
            while b + d in Aset:
                b += d
                count += 1
                already_seen.add(b)
            print "found %d items in %d .. %d" % (count, a, b)
            # collect here the largest 'count'

Cập nhật:

  • Giải pháp này có thể đủ tốt nếu bạn chỉ quan tâm đến các giá trị của d tương đối nhỏ; ví dụ: nếu nhận được kết quả tốt nhất cho d <= 1000 sẽ đủ tốt. Sau đó, sự phức tạp đi xuống O(n*1000). Điều này làm cho thuật toán xấp xỉ, nhưng thực sự chạy được cho n=1000000. (Đo tại 400-500 giây với CPython, 80-90 giây với PyPy, với một tập con ngẫu nhiên các số từ 0 đến 10'000'000.)

  • Nếu bạn vẫn muốn tìm kiếm toàn bộ phạm vi và nếu trường hợp phổ biến là các chuỗi dài tồn tại, thì cải tiến đáng chú ý là dừng ngay khi d quá lớn để tìm thấy chuỗi dài hơn.


19
2017-08-10 10:40



Giải pháp này có thể đủ tốt nếu bạn chỉ quan tâm đến các giá trị của d tương đối nhỏ; ví dụ, nếu nhận được kết quả tốt nhất cho d <= 1000 là đủ tốt. Sau đó, sự phức tạp đi xuống O(n*1000), có thể chạy trong chưa đầy một phút cho n = 1000000 (thử cũng PyPy). - Armin Rigo
Ý tưởng hay nếu phạm vi rất hạn chế - RiaD
Nhưng nếu d <= 1000 rằng bạn có thể chỉ cần loại bỏ các bản sao, bạn sẽ có tối đa 1000 phần tử và giải quyết nó trong O (1000 ^ 2) mà sẽ làm việc vài giây ở hầu hết tôi brlieve. - RiaD
Không, nếu A có một triệu con số nằm trong khoảng từ 0 đến 10'000'000 thì m = 10'000'000. Nhưng nếu chúng ta hạn chế bản thân d <= 1000 chúng tôi đang tìm kiếm các chuỗi trong toàn bộ A có tối đa 1000 bước. - Armin Rigo
Ah, tôi hiểu ý bạn là gì - RiaD


CẬP NHẬT: Tôi đã tìm thấy một bài báo về vấn đề này, bạn có thể tải xuống đây.

Đây là giải pháp dựa trên lập trình động. Nó đòi hỏi độ phức tạp thời gian O (n ^ 2) và độ phức tạp không gian O (n ^ 2), và không sử dụng băm.

Chúng tôi giả định tất cả các số được lưu trong mảng a theo thứ tự tăng dần và n tiết kiệm chiều dài của nó. Mảng 2D l[i][j] xác định độ dài của các chuỗi có khoảng cách bằng nhau dài nhất kết thúc bằng a[i] và a[j]l[j][k] = l[i][j] + 1 nếu a[j] - - a[i] = a[k] - - a[j] (i <j <k).

lmax = 2
l = [[2 for i in xrange(n)] for j in xrange(n)]
for mid in xrange(n - 1):
    prev = mid - 1
    succ = mid + 1
    while (prev >= 0 and succ < n):
        if a[prev] + a[succ] < a[mid] * 2:
            succ += 1
        elif a[prev] + a[succ] > a[mid] * 2:
            prev -= 1
        else:
            l[mid][succ] = l[prev][mid] + 1
            lmax = max(lmax, l[mid][succ])
            prev -= 1
            succ += 1

print lmax

12
2017-08-11 16:34



Đó là tốt đẹp và sạch sẽ. Nó có thể được thực hiện để chạy trong không gian tuyến tính? - eleanora
Làm thế nào để bạn in ra một subsequence tối ưu từ mã của bạn? - eleanora
@ user2179021 Dòng lmax = max (lmax, l [mid] [succ]) cập nhật lmax, và nếu bạn muốn có một chuỗi tối ưu, bạn có thể lưu chuỗi này ở đây. - ZelluX
Bạn có nghĩ rằng nó có thể được thực hiện không gian tuyến tính? - eleanora
@ user2179021 Tôi không thể hiểu được. Nhưng tôi đã tìm thấy một giải pháp chạy nhanh hơn trong một số trường hợp. Vui lòng xem liên kết trong câu trả lời được cập nhật. - ZelluX


Thuật toán

  • Vòng lặp chính duyệt qua danh sách
  • Nếu số được tìm thấy trong danh sách precalculate, thì nó thuộc về tất cả các chuỗi nằm trong danh sách đó, tính toán lại tất cả các chuỗi với số lượng + 1
  • Xóa tất cả được tính toán trước cho phần tử hiện tại
  • Tính toán lại các chuỗi mới trong đó phần tử đầu tiên nằm trong khoảng từ 0 đến hiện tại và phần tử thứ hai là phần tử hiện tại của quá trình truyền tải (thực tế, không phải từ 0 đến hiện tại, chúng tôi có thể sử dụng thực tế là phần tử mới không được lớn hơn (a) và mới danh sách nên có khả năng để trở nên dài hơn mà đã tìm thấy một)

Vì vậy, cho danh sách [1, 2, 4, 5, 7] đầu ra sẽ là (đó là một chút lộn xộn, hãy thử mã cho mình và xem)

  • mục lục 0, thành phần 1:
    • nếu 1 trong precalc? Không - không làm gì cả
    • Không làm gì cả
  • mục lục 1, thành phần 2:
    • nếu 2 trong precalc? Không - không làm gì cả
    • kiểm tra xem 3 = 1 + (2 - - 1) * 2 trong bộ của chúng tôi? Không - không làm gì cả
  • mục lục 2, thành phần 4:
    • nếu 4 trong precalc? Không - không làm gì cả
      • kiểm tra nếu 6 = 2 + (4 - - 2) * 2 trong bộ của chúng tôi? Không
      • kiểm tra nếu 7 = 1 + (4 - - 1) * 2 trong bộ của chúng tôi? Có - thêm phần tử mới {7: {3: {'count': 2, 'start': 1}}}  7 - yếu tố của danh sách, 3 là bước.
  • mục lục 3, thành phần 5:
    • nếu 5 trong precalc? Không - không làm gì cả
      • không kiểm tra 4 bởi vì 6 = 4 + (5 - - 4) * 2 ít hơn phần tử được tính 7
      • kiểm tra nếu số 8 = 2 + (5 - - 2) * 2 trong bộ của chúng tôi? Không
      • kiểm tra 10 = 2 + (5 - - 1) * 2 - lớn hơn max (a) == 7
  • mục lục 4, thành phần 7:
    • nếu 7 trong precalc? Có - đưa nó vào kết quả
      • không kiểm tra 5 bởi vì 9 = 5 + (7 - - 5) * 2 lớn hơn max (a) == 7

result = (3, {'count': 3, 'start': 1}) # bước 3, đếm 3, bắt đầu 1, biến nó thành chuỗi

Độ phức tạp

Nó không nên nhiều hơn O (N ^ 2), và tôi nghĩ rằng nó ít hơn vì kết thúc sớm hơn của việc tìm kiếm các trình tự mới, tôi sẽ cố gắng cung cấp phân tích chi tiết sau

Mã số

def add_precalc(precalc, start, step, count, res, N):
    if step == 0: return True
    if start + step * res[1]["count"] > N: return False

    x = start + step * count
    if x > N or x < 0: return False

    if precalc[x] is None: return True

    if step not in precalc[x]:
        precalc[x][step] = {"start":start, "count":count}

    return True

def work(a):
    precalc = [None] * (max(a) + 1)
    for x in a: precalc[x] = {}
    N, m = max(a), 0
    ind = {x:i for i, x in enumerate(a)}

    res = (0, {"start":0, "count":0})
    for i, x in enumerate(a):
        for el in precalc[x].iteritems():
            el[1]["count"] += 1
            if el[1]["count"] > res[1]["count"]: res = el
            add_precalc(precalc, el[1]["start"], el[0], el[1]["count"], res, N)
            t = el[1]["start"] + el[0] * el[1]["count"]
            if t in ind and ind[t] > m:
                m = ind[t]
        precalc[x] = None

        for y in a[i - m - 1::-1]:
            if not add_precalc(precalc, y, x - y, 2, res, N): break

    return [x * res[0] + res[1]["start"] for x in range(res[1]["count"])]

3
2017-08-10 09:28



nó tìm kiếm sự khác biệt xuất hiện hầu hết thời gian, phải không? nó sẽ tìm thấy rất nhiều 1 trong "1 2 5 6 100 101 1000 1001 1e5 1e5 + 2 1e5 + 4", trong khi câu trả lời tốt nhất là với diff = 2? - RiaD
vâng, có vẻ như bạn đúng, phải kiểm tra nó .. - Roman Pekar
ideone.com/4CSyTW - RiaD
đã thay đổi mã - ideone.com/3pODoO. Cảm ơn bạn đã tìm lỗi! - Roman Pekar
Trong tương lai, tôi khuyên bạn không nên xóa và đăng lại câu trả lời nếu nó vô tình được gắn nhãn là Community Wiki. Chúng ta có thể dễ dàng đảo ngược tình trạng đó, như tôi đã làm ở đây. - Brad Larson♦


Đây là một câu trả lời khác, làm việc đúng lúc O(n^2) và không có bất kỳ yêu cầu bộ nhớ đáng chú ý nào ngoài việc chuyển danh sách thành một bộ.

Ý tưởng khá ngây thơ: giống như poster gốc, nó tham lam và chỉ kiểm tra xem bạn có thể mở rộng một chuỗi từ mỗi cặp điểm như thế nào --- tuy nhiên, kiểm tra trước rằng chúng ta đang ở khởi đầu của một chuỗi. Nói cách khác, từ điểm a và b bạn kiểm tra xem bạn có thể mở rộng đến mức nào b + (b-a), b + 2*(b-a), ... nhưng chỉ khi a - (b-a) chưa có trong tập hợp tất cả các điểm. Nếu có, thì bạn đã thấy cùng một chuỗi.

Bí quyết là thuyết phục bản thân rằng việc tối ưu hóa đơn giản này là đủ để giảm độ phức tạp xuống O(n^2) từ bản gốc O(n^3). Đó là trái như một tập thể dục cho người đọc :-) Thời gian là cạnh tranh với người khác O(n^2) giải pháp ở đây.

A = [1, 4, 5, 7, 8, 12]    # in sorted order
Aset = set(A)

lmax = 2
for j, b in enumerate(A):
    for i in range(j):
        a = A[i]
        step = b - a
        if b + step in Aset and a - step not in Aset:
            c = b + step
            count = 3
            while c + step in Aset:
                c += step
                count += 1
            #print "found %d items in %d .. %d" % (count, a, c)
            if count > lmax:
                lmax = count

print lmax

3
2017-08-15 06:25





Giải pháp của bạn là O(N^3) bây giờ (bạn nói O(N^2) per index). Đây rồi O(N^2) thời gian và O(N^2) giải pháp bộ nhớ.

Ý kiến

Nếu chúng ta biết hậu tố đi qua các chỉ số i[0],i[1],i[2],i[3] chúng ta không nên thử bắt đầu với i[1] và i[2] hoặc là i[2] và i[3]

Lưu ý rằng tôi đã chỉnh sửa mã đó để làm cho nó dễ dàng hơn một chút khi sử dụng a được sắp xếp nhưng nó sẽ không hoạt động với các phần tử bằng nhau. Bạn có thể kiểm tra số lượng tối đa các phần tử bằng nhau trong O(N) dễ dàng

Mã giả

Tôi chỉ tìm kiếm chiều dài tối đa nhưng điều đó không thay đổi bất cứ điều gì

whereInA = {}
for i in range(n):
   whereInA[a[i]] = i; // It doesn't matter which of same elements it points to

boolean usedPairs[n][n];

for i in range(n):
    for j in range(i + 1, n):
       if usedPair[i][j]:
          continue; // do not do anything. It was in one of prev sequences.

    usedPair[i][j] = true;

    //here quite stupid solution:
    diff = a[j] - a[i];
    if diff == 0:
       continue; // we can't work with that
    lastIndex = j
    currentLen = 2
    while whereInA contains index a[lastIndex] + diff :
        nextIndex = whereInA[a[lastIndex] + diff]
        usedPair[lastIndex][nextIndex] = true
        ++currentLen
        lastIndex = nextIndex

    // you may store all indicies here
    maxLen = max(maxLen, currentLen)

Suy nghĩ về cách sử dụng bộ nhớ

O(n^2) thời gian là rất chậm cho 1000000 yếu tố. Nhưng nếu bạn sẽ chạy mã này trên số lượng yếu tố như vậy thì vấn đề lớn nhất sẽ là sử dụng bộ nhớ.
Có thể làm gì để giảm nó?

  • Thay đổi mảng boolean thành bitfields để lưu trữ nhiều boolean hơn cho mỗi bit.
  • Làm cho mỗi mảng boolean tiếp theo ngắn hơn vì chúng tôi chỉ sử dụng usedPairs[i][j] nếu i < j

Vài phỏng đoán:

  • Chỉ lưu trữ các cặp chỉ thị đã sử dụng. (Mâu thuẫn với ý tưởng đầu tiên)
  • Hủy bỏ các cặp đã sử dụng mà sẽ không bao giờ được sử dụng nhiều hơn nữa i,j đã được chọn trong vòng lặp)

2
2017-08-10 09:20



nlà một triệu, vì vậy boolean usedPairs[n][n] sẽ cần ít nhất một terabit bộ nhớ. - Michael Butscher
Ồ, không nhận thấy những ràng buộc chính xác và không nghĩ về trí nhớ. (btw nó có thể chia cho 2, bởi vì chúng tôi chỉ sử dụng usedPairs[i][j] cho tôi <j) - RiaD
@MichaelButscher, mọi cách O(n^2) cho số 1000000 là rất chậm. - RiaD
Có, và tôi có cảm giác nó không thể được thực hiện nhanh hơn (nhưng không thể chứng minh điều đó). - Michael Butscher
@MichaelButscher, có lẽ chúng ta bằng cách nào đó có thể sử dụng nó được sắp xếp. - RiaD


Đây là 2 xu của tôi.

Nếu bạn có một danh sách được gọi là đầu vào:

input = [1, 4, 5, 7, 8, 12]

Bạn có thể xây dựng một cấu trúc dữ liệu cho mỗi một trong những điểm này (không bao gồm điểm đầu tiên), sẽ cho bạn biết điểm đó từ bất kỳ ai trong số những người tiền nhiệm của nó là bao xa:

[1, 4, 5, 7, 8, 12]
 x  3  4  6  7  11   # distance from point i to point 0
 x  x  1  3  4   8   # distance from point i to point 1
 x  x  x  2  3   7   # distance from point i to point 2
 x  x  x  x  1   5   # distance from point i to point 3
 x  x  x  x  x   4   # distance from point i to point 4

Bây giờ bạn có các cột, bạn có thể xem xét i-th mục đầu vào (là input[i]) và mỗi số n trong cột của nó.

Các con số thuộc về một loạt các con số cách nhau bao gồm input[i], là những người có n * j bên trong i-th vị trí của cột của họ, nơi j là số lượng các kết quả phù hợp đã được tìm thấy khi di chuyển các cột từ trái sang phải, cộng với k-th người tiền nhiệm của input[i], Ở đâu k là chỉ số của n trong cột của input[i].

Ví dụ: nếu chúng ta xem xét i = 1, input[i] = 4, n = 3, sau đó, chúng tôi có thể xác định chuỗi hiểu 4 (input[i]), 7 (bởi vì nó có 3 ở vị trí 1 cột của nó) và 1, bởi vì k là 0, vì vậy chúng tôi lấy người tiền nhiệm đầu tiên của i.

Có thể thực hiện (xin lỗi nếu mã không sử dụng cùng một ký hiệu như giải thích):

def build_columns(l):
    columns = {}
    for x in l[1:]:
        col = []
        for y in l[:l.index(x)]:
            col.append(x - y)
        columns[x] = col
    return columns

def algo(input, columns):
    seqs = []
    for index1, number in enumerate(input[1:]):
        index1 += 1 #first item was sliced
        for index2, distance in enumerate(columns[number]):
            seq = []
            seq.append(input[index2]) # k-th pred
            seq.append(number)
            matches = 1
            for successor in input[index1 + 1 :]:
                column = columns[successor]
                if column[index1] == distance * matches:
                    matches += 1
                    seq.append(successor)
            if (len(seq) > 2):
                seqs.append(seq)
    return seqs

Dài nhất:

print max(sequences, key=len)

1
2017-08-10 21:46



bạn đã thử cái này trên 100000 điểm chưa? - Roman Pekar
Thuật toán của bạn đã hoạt động 2 giây trên 300 điểm, thuật toán của tôi đã hoạt động 0,03 giây. Tôi đã thử của bạn trên 5000 nhưng nó đã quá dài: (làm việc của tôi 18 giây trên 5000, vì vậy nó vẫn không có cách nào chúng ta có thể làm điều này cho 1000000 nhanh - Roman Pekar
@RomanPekar vì nó rõ ràng Θ (N ^ 3) là giải pháp của OP - RiaD
có, nhưng có thể chúng tôi đang thiếu một số điểm và có thể làm điều đó một cách thẳng thắn :) hoặc NlogN ít nhất .... - Roman Pekar


Di chuyển mảng, lưu bản ghi kết quả tối ưu và bảng

(1) chỉ số - sự khác biệt phần tử trong chuỗi,
(2) đếm - số phần tử trong chuỗi cho đến thời điểm này, và
(3) phần tử được ghi cuối cùng.

Đối với mỗi phần tử mảng, hãy xem sự khác biệt của từng phần tử mảng trước đó; nếu phần tử đó cuối cùng trong một chuỗi được lập chỉ mục trong bảng, hãy điều chỉnh trình tự đó trong bảng và cập nhật trình tự tốt nhất nếu có, nếu không thì bắt đầu một chuỗi mới, trừ khi giá trị lớn nhất hiện tại lớn hơn độ dài của chuỗi có thể.

Quét ngược, chúng ta có thể ngừng quét khi d lớn hơn giữa phạm vi của mảng; hoặc khi giá trị lớn nhất hiện tại lớn hơn độ dài của chuỗi có thể, đối với d lớn hơn chênh lệch được lập chỉ mục lớn nhất. Chuỗi nơi s[j] lớn hơn phần tử cuối cùng trong chuỗi sẽ bị xóa.

Tôi đã chuyển đổi mã của mình từ JavaScript sang Python (mã python đầu tiên của tôi):

import random
import timeit
import sys

#s = [1,4,5,7,8,12]
#s = [2, 6, 7, 10, 13, 14, 17, 18, 21, 22, 23, 25, 28, 32, 39, 40, 41, 44, 45, 46, 49, 50, 51, 52, 53, 63, 66, 67, 68, 69, 71, 72, 74, 75, 76, 79, 80, 82, 86, 95, 97, 101, 110, 111, 112, 114, 115, 120, 124, 125, 129, 131, 132, 136, 137, 138, 139, 140, 144, 145, 147, 151, 153, 157, 159, 161, 163, 165, 169, 172, 173, 175, 178, 179, 182, 185, 186, 188, 195]
#s = [0, 6, 7, 10, 11, 12, 16, 18, 19]

m = [random.randint(1,40000) for r in xrange(20000)]
s = list(set(m))
s.sort()

lenS = len(s)
halfRange = (s[lenS-1] - s[0]) // 2

while s[lenS-1] - s[lenS-2] > halfRange:
    s.pop()
    lenS -= 1
    halfRange = (s[lenS-1] - s[0]) // 2

while s[1] - s[0] > halfRange:
    s.pop(0)
    lenS -=1
    halfRange = (s[lenS-1] - s[0]) // 2

n = lenS

largest = (s[n-1] - s[0]) // 2
#largest = 1000 #set the maximum size of d searched

maxS = s[n-1]
maxD = 0
maxSeq = 0
hCount = [None]*(largest + 1)
hLast = [None]*(largest + 1)
best = {}

start = timeit.default_timer()

for i in range(1,n):

    sys.stdout.write(repr(i)+"\r")

    for j in range(i-1,-1,-1):
        d = s[i] - s[j]
        numLeft = n - i
        if d != 0:
            maxPossible = (maxS - s[i]) // d + 2
        else:
            maxPossible = numLeft + 2
        ok = numLeft + 2 > maxSeq and maxPossible > maxSeq

        if d > largest or (d > maxD and not ok):
            break

        if hLast[d] != None:
            found = False
            for k in range (len(hLast[d])-1,-1,-1):
                tmpLast = hLast[d][k]
                if tmpLast == j:
                    found = True
                    hLast[d][k] = i
                    hCount[d][k] += 1
                    tmpCount = hCount[d][k]
                    if tmpCount > maxSeq:
                        maxSeq = tmpCount
                        best = {'len': tmpCount, 'd': d, 'last': i}
                elif s[tmpLast] < s[j]:
                    del hLast[d][k]
                    del hCount[d][k]
            if not found and ok:
                hLast[d].append(i)
                hCount[d].append(2)
        elif ok:
            if d > maxD: 
                maxD = d
            hLast[d] = [i]
            hCount[d] = [2]


end = timeit.default_timer()
seconds = (end - start)

#print (hCount)
#print (hLast)
print(best)
print(seconds)

0
2017-08-20 15:27



vì vậy bạn vẫn cần bộ nhớ O (N ^ 2) - Roman Pekar
@RomanPekar Cảm ơn bạn đã bình luận của bạn. Điều gì về tối ưu hóa bổ sung mà chấm dứt việc quét lùi lại sớm? - גלעד ברקן
bạn có mã không - Roman Pekar
@ RomanPeckar không, chỉ cần suy nghĩ về các thuật toán; tôi cũng không biết Python. - גלעד ברקן
@RomanPeckar đã thêm ví dụ jsfiddle vào câu trả lời của tôi. jsfiddle.net/groovy/b6zkR - גלעד ברקן


Đây là một trường hợp cụ thể cho vấn đề chung chung hơn được mô tả ở đây: Khám phá các mẫu dài trong đó K = 1 và được cố định. Nó được demostrated ở đó nó có thể được giải quyết trong O (N ^ 2). Runnig thực hiện của tôi về thuật toán C đề xuất ở đó phải mất 3 giây để tìm giải pháp cho N = 20000 và M = 28000 trong máy 32bit của tôi.


0
2018-02-25 04:12





Phương pháp tham lam
1. Chỉ một chuỗi quyết định được tạo ra.
2. Nhiều quyết định được tạo ra. Lập trình năng động 1. Nó không đảm bảo để cung cấp cho một giải pháp tối ưu luôn.
2. Nó chắc chắn đưa ra một giải pháp tối ưu.


0