Pertanyaan Deretan dengan jarak paling panjang yang sama


Saya memiliki satu juta bilangan bulat dalam urutan terurut dan saya ingin menemukan kelanjutan terpanjang di mana perbedaan antara pasangan yang berurutan adalah sama. Sebagai contoh

1, 4, 5, 7, 8, 12

memiliki kelanjutan

   4,       8, 12

Metode naif saya serakah dan hanya memeriksa seberapa jauh Anda dapat memperpanjang kelanjutan dari setiap poin. Ini membutuhkan O(n²) waktu per titik tampaknya.

Apakah ada cara yang lebih cepat untuk mengatasi masalah ini?

Memperbarui. Saya akan menguji kode yang diberikan dalam jawaban sesegera mungkin (terima kasih). Namun sudah jelas bahwa menggunakan memori n ^ 2 tidak akan berfungsi. Sejauh ini tidak ada kode yang mengakhiri dengan input sebagai [random.randint(0,100000) for r in xrange(200000)] .

Pengaturan waktu.  Saya diuji dengan data input berikut pada sistem 32 bit saya.

a= [random.randint(0,10000) for r in xrange(20000)] 
a.sort()
  • Metode pemrograman dinamis ZelluX menggunakan 1.6G RAM dan membutuhkan waktu 2 menit dan 14 detik. Dengan pypy hanya butuh 9 detik! Namun crash dengan kesalahan memori pada input besar.
  • Metode waktu O (nd) dari Armin memakan waktu 9 detik dengan pypy tetapi hanya 20MB RAM. Tentu saja ini akan jauh lebih buruk jika jaraknya jauh lebih besar. Penggunaan memori yang rendah berarti saya juga bisa mengujinya dengan = [random.randint (0,100000) untuk r di xrange (200000)] tetapi tidak selesai dalam beberapa menit saya berikan dengan pypy.

Untuk bisa menguji metode Kluev, aku mengulanginya

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

untuk membuat daftar panjang kasar 20000. Semua timing dengan pypy

  • ZelluX, 9 detik
  • Kluev, 20 detik
  • Armin, 52 detik

Tampaknya jika metode ZelluX dapat dibuat ruang linier maka akan menjadi pemenang yang jelas.


76
2017-08-10 07:59


asal


Jawaban:


Memperbarui: Algoritma pertama yang dijelaskan di sini sudah usang Jawaban kedua Armin Rigo, yang jauh lebih sederhana dan lebih efisien. Tetapi kedua metode ini memiliki satu kelemahan. Mereka membutuhkan berjam-jam untuk menemukan hasil untuk satu juta bilangan bulat. Jadi saya mencoba dua varian lainnya (lihat bagian kedua dari jawaban ini) di mana kisaran bilangan bulat input dianggap terbatas. Keterbatasan semacam itu memungkinkan algoritme yang lebih cepat. Saya juga mencoba mengoptimalkan kode Armin Rigo. Lihat hasil pembandingan saya di bagian akhir.


Berikut ini adalah gagasan algoritma menggunakan O (N) memori. Kompleksitas waktu adalah O (N2 log N), tetapi dapat diturunkan ke O (N2).

Algoritma menggunakan struktur data berikut:

  1. prev: array indeks menunjuk ke elemen sebelumnya dari subsequence (mungkin tidak lengkap).
  2. hash: hashmap dengan key = perbedaan antara pasangan berturut-turut di subsequence dan value = dua hashmaps lainnya. Untuk hashmaps lainnya: key = index awal / akhir dari subsequence, value = pair of (subsequence length, ending / starting index dari subsequence).
  3. pq: antrean prioritas untuk semua nilai "perbedaan" yang mungkin untuk kejadian yang disimpan di prev dan hash.

Algoritma:

  1. Inisialisasi prev dengan indeks i-1. Memperbarui hash dan pq untuk mendaftarkan semua (tidak lengkap) kejadian yang ditemukan pada langkah ini dan "perbedaan" mereka.
  2. Dapatkan (dan hapus) "perbedaan" terkecil dari pq. Dapatkan rekaman terkait dari hash dan pindai salah satu peta hash tingkat kedua. Pada saat ini semua kesimpulan dengan "perbedaan" telah lengkap. Jika peta hash tingkat kedua berisi panjang subsequence lebih baik daripada yang ditemukan sejauh ini, perbarui hasil terbaik.
  3. Di dalam array prev: untuk setiap elemen dari setiap urutan yang ditemukan pada langkah # 2, indeks pengurangan dan pembaruan hash dan mungkin pq. Saat memperbarui hash, kita bisa melakukan salah satu operasi berikut: menambahkan subsequence baru dengan panjang 1, atau menumbuhkan beberapa subsequence yang ada dengan 1, atau menggabungkan dua subsequences yang ada.
  4. Hapus catatan peta hash yang ditemukan pada langkah # 2.
  5. Lanjutkan dari langkah # 2 saat pq tidak kosong.

Algoritma ini memperbarui elemen O (N) dari prev O (N) kali masing-masing. Dan setiap pembaruan ini mungkin perlu menambahkan "perbedaan" baru pq. Semua ini berarti kompleksitas waktu O (N2 log N) jika kita menggunakan implementasi tumpukan sederhana untuk pq. Untuk menguranginya menjadi O (N2) kita mungkin menggunakan implementasi antrian prioritas lanjutan. Beberapa kemungkinan tercantum di halaman ini: Antrian Prioritas.

Lihat kode Python yang sesuai Ideone. Kode ini tidak mengizinkan elemen duplikat dalam daftar. Adalah mungkin untuk memperbaikinya, tetapi itu akan menjadi optimasi yang baik pula untuk menghapus duplikat (dan untuk menemukan subsequence terpanjang di luar duplikat secara terpisah).

Dan kode yang sama setelah sedikit optimasi. Pencarian di sini dihentikan segera setelah panjang subsequence dikalikan dengan kemungkinan terjadinya "perbedaan" melebihi kisaran daftar sumber.


Kode Armin Rigo sederhana dan cukup efisien. Namun dalam beberapa kasus, ini melakukan beberapa perhitungan tambahan yang dapat dihindari. Pencarian dapat dihentikan segera setelah panjang subsequence dikalikan dengan kemungkinan kelanjutan "perbedaan" melebihi rentang daftar sumber:

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]))

Jika rentang bilangan bulat dalam data sumber (M) kecil, algoritma sederhana dimungkinkan dengan O (M2) waktu dan ruang 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]))

Ini mirip dengan metode pertama oleh Armin Rigo, tetapi tidak menggunakan struktur data dinamis. Saya kira sumber data tidak memiliki duplikat. Dan (untuk menjaga kode sederhana) saya juga mengira bahwa nilai input minimum tidak negatif dan mendekati nol.


Algoritma sebelumnya dapat ditingkatkan jika alih-alih array boolean, kami menggunakan struktur data bitset dan operasi bitwise untuk memproses data secara paralel. Kode yang ditunjukkan di bawah ini mengimplementasikan bitset sebagai integer Python built-in. Ini memiliki asumsi yang sama: tidak ada duplikat, nilai input minimum tidak negatif dan mendekati nol. Kompleksitas waktu adalah O (M2 * Log L) di mana L adalah panjang optimal subsequence, kompleksitas ruang adalah 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

Tolok ukur:

Data masukan (sekitar 100000 bilangan bulat) dihasilkan dengan cara ini:

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

Dan untuk algoritma tercepat saya juga menggunakan data berikut (sekitar 1000000 bilangan bulat):

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

Semua hasil menunjukkan waktu dalam detik:

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



Kami dapat memiliki solusi O(n*m) dalam waktu dengan kebutuhan memori yang sangat sedikit, dengan mengadaptasi milik Anda. Sini nadalah jumlah item dalam urutan input angka yang diberikan, dan m adalah kisarannya, yaitu jumlah tertinggi dikurangi yang terendah.

Memanggil A urutan semua nomor input (dan menggunakan precomputed set() untuk menjawab secara konstan pertanyaan "apakah nomor ini di A?"). Panggil d itu langkah dari subsequence yang kita cari (perbedaan antara dua nomor dari subsequence ini). Untuk setiap nilai d yang mungkin, lakukan pemindaian linier berikut atas semua nomor input: untuk setiap angka n dari A dalam urutan yang meningkat, jika nomornya belum terlihat, lihat ke depan dalam A untuk panjang urutan dimulai pada n dengan langkah d. Kemudian tandai semua item dalam urutan seperti yang telah dilihat, sehingga kita menghindari pencarian lagi dari mereka, untuk hal yang sama d. Karena itu, kerumitannya adil O(n) untuk setiap nilai 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'

Pembaruan:

  • Solusi ini mungkin cukup baik jika Anda hanya tertarik pada nilai d yang relatif kecil; misalnya, jika mendapatkan hasil terbaik untuk d <= 1000 akan cukup baik. Lalu kompleksitasnya turun O(n*1000). Ini membuat algoritme mendekati, tetapi sebenarnya dapat dijalankan n=1000000. (Diukur pada 400-500 detik dengan CPython, 80-90 detik dengan PyPy, dengan subset acak angka antara 0 dan 10'000'000.)

  • Jika Anda masih ingin mencari seluruh jajaran, dan jika kasus umum adalah urutan panjang, perbaikan yang penting adalah berhenti segera setelah d terlalu besar untuk urutan yang lebih panjang untuk ditemukan.


19
2017-08-10 10:40



PEMBARUAN: Saya menemukan kertas pada masalah ini, Anda dapat mengunduhnya sini.

Berikut ini adalah solusi berdasarkan pemrograman dinamis. Ini membutuhkan O (n ^ 2) kompleksitas waktu dan O (n ^ 2) kompleksitas ruang, dan tidak menggunakan hashing.

Kami menganggap semua nomor disimpan dalam larik a dalam urutan menaik, dan n menghemat panjangnya. Array 2D l[i][j] mendefinisikan panjang terpanjang sama spasi berakhir dengan a[i] dan a[j], dan l[j][k] = l[i][j] + 1 jika a[j] - a[i] = a[k] - a[j] (saya <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



Algoritma

  • Main loop melintasi daftar
  • Jika nomor ditemukan dalam daftar precalculate, maka itu milik semua urutan yang ada di daftar itu, hitung ulang semua urutan dengan hitungan + 1
  • Hapus semua yang dikalkulasi untuk elemen saat ini
  • Hitung ulang urutan baru di mana elemen pertama berasal dari rentang 0 hingga saat ini, dan kedua adalah elemen arus dari traversal (sebenarnya, bukan dari 0 hingga saat ini, kita dapat menggunakan fakta bahwa elemen baru tidak boleh lebih dari max (a) dan baru daftar harus memiliki kemungkinan untuk menjadi lebih lama yang sudah ditemukan satu)

Jadi untuk daftar [1, 2, 4, 5, 7] output akan menjadi (itu sedikit berantakan, coba kode sendiri dan lihat)

  • indeks 0, elemen 1:
    • jika 1 di precalc? Tidak - jangan lakukan apa-apa
    • Tidak melakukan apapun
  • indeks 1, elemen 2:
    • jika 2 di precalc? Tidak - jangan lakukan apa-apa
    • periksa apakah 3 = 1 + (2 - 1) * 2 di set kami? Tidak - jangan lakukan apa-apa
  • indeks 2, elemen 4:
    • jika 4 di precalc? Tidak - jangan lakukan apa-apa
      • periksa apakah 6 = 2 + (4 - 2) * 2 di set kami? Tidak
      • periksa apakah 7 = 1 + (4 - 1) * 2 di set kami? Ya - tambahkan elemen baru {7: {3: {'count': 2, 'start': 1}}}  7 - elemen dari daftar, 3 adalah langkah.
  • indeks 3, elemen 5:
    • jika 5 di precalc? Tidak - jangan lakukan apa-apa
      • jangan periksa 4 karena 6 = 4 + (5 - 4) * 2 kurang dari elemen yang dihitung 7
      • periksa apakah 8 = 2 + (5 - 2) * 2 di set kami? Tidak
      • memeriksa 10 = 2 + (5 - 1) * 2 - lebih dari max (a) == 7
  • indeks 4, elemen 7:
    • jika 7 di precalc? Ya - taruh hasilnya
      • jangan periksa 5 karena 9 = 5 + (7 - 5) * 2 lebih dari max (a) == 7

result = (3, {'count': 3, 'start': 1}) # langkah 3, hitungan 3, mulai 1, ubah menjadi urutan

Kompleksitas

Seharusnya tidak lebih dari O (N ^ 2), dan saya pikir itu kurang karena penghentian sebelumnya mencari sekuens baru, saya akan mencoba untuk memberikan analisis rinci nanti

Kode

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



Inilah jawaban lain, bekerja tepat waktu O(n^2) dan tanpa persyaratan memori penting selain mengubah daftar menjadi satu set.

Ide ini cukup naif: seperti poster asli, itu serakah dan hanya memeriksa seberapa jauh Anda dapat memperpanjang kelanjutan dari masing-masing pasangan poin - namun, periksa dulu bahwa kita berada di mulai dari sebuah subsequence. Dengan kata lain, dari poin a dan b Anda memeriksa seberapa jauh Anda dapat memperpanjang ke b + (b-a), b + 2*(b-a), ... tapi hanya jika a - (b-a) belum di set semua poin. Jika ya, maka Anda sudah melihat subsequence yang sama.

Triknya adalah meyakinkan diri kita bahwa optimasi sederhana ini cukup untuk menurunkan kompleksitas O(n^2) dari aslinya O(n^3). Itu yang tersisa sebagai latihan bagi pembaca :-) Waktunya bersaing dengan yang lain O(n^2) solusi di sini.

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



Solusimu adalah O(N^3) sekarang (Anda berkata O(N^2) per index). Ini dia O(N^2) waktu dan O(N^2) solusi memori.

Ide

Jika kita tahu kelanjutan yang melewati indeks i[0],i[1],i[2],i[3] kita tidak boleh mencoba lanjutan yang dimulai dengan i[1] dan i[2] atau i[2] dan i[3]

Perhatikan saya mengedit kode itu untuk membuatnya lebih mudah menggunakannya a diurutkan tetapi tidak akan berfungsi untuk elemen yang sama. Anda dapat memeriksa jumlah jumlah maksimum elemen yang sama dalam O(N) dengan mudah

Pseudocode

Saya mencari hanya untuk panjang maksimal tetapi itu tidak mengubah apa pun

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)

Pemikiran tentang penggunaan memori

O(n^2) waktu adalah sangat lambat untuk 10.00000 elemen. Tetapi jika Anda akan menjalankan kode ini pada sejumlah elemen seperti itu, masalah terbesarnya adalah penggunaan memori.
Apa yang bisa dilakukan untuk menguranginya?

  • Ubah susunan boolean ke bitfields untuk menyimpan lebih banyak boolean per bit.
  • Buat setiap boolean array lebih pendek karena kami hanya menggunakan usedPairs[i][j] jika i < j

Beberapa heuristik:

  • Simpan hanya pasangan indeks yang digunakan. (Konflik dengan ide pertama)
  • Hapus Pairs bekas yang tidak akan pernah digunakan lebih banyak (untuk itu i,j yang sudah dipilih dalam lingkaran)

2
2017-08-10 09:20



Ini adalah 2 sen saya.

Jika Anda memiliki daftar yang disebut input:

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

Anda dapat membangun struktur data yang untuk masing-masing poin ini (tidak termasuk yang pertama), akan memberi tahu Anda seberapa jauh titik itu dari siapa pun dari pendahulunya:

[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

Sekarang Anda memiliki kolom, Anda dapat mempertimbangkan i-th item input (yang mana input[i]) dan setiap angka n di kolomnya.

Angka-angka yang termasuk dalam serangkaian angka berjarak sama yang termasuk input[i], adalah mereka yang memilikinya n * j dalam i-th posisi kolom mereka, di mana j adalah jumlah kecocokan yang sudah ditemukan saat memindahkan kolom dari kiri ke kanan, ditambah k-th pendahulu dari input[i], dimana k adalah indeks n di kolom input[i].

Contoh: jika kita mempertimbangkan i = 1, input[i] = 4, n = 3, kemudian, kita dapat mengidentifikasi urutan yang memahami 4 (input[i]), 7 (karena memiliki 3 dalam posisi 1 kolomnya) dan 1, karena k adalah 0, jadi kami mengambil pendahulunya pertama i.

Kemungkinan implementasi (maaf jika kode tidak menggunakan notasi yang sama dengan penjelasan):

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

Yang terpanjang:

print max(sequences, key=len)

1
2017-08-10 21:46



Lintasi susunan, simpan catatan hasil optimal dan tabel dengan

(1) indeks - perbedaan elemen dalam urutan,
(2) menghitung - jumlah elemen dalam urutan sejauh ini, dan
(3) elemen yang direkam terakhir.

Untuk setiap elemen array lihat perbedaan dari masing-masing elemen array sebelumnya; jika elemen tersebut terakhir dalam urutan yang diindeks dalam tabel, sesuaikan urutan tersebut dalam tabel, dan perbarui urutan terbaik jika berlaku, jika tidak memulai urutan baru, kecuali jika maksimum saat ini lebih besar dari panjang kemungkinan urutan.

Memindai mundur kita dapat menghentikan pemindaian kita ketika d lebih besar dari bagian tengah rentang larik; atau ketika arus maksimal lebih besar dari panjang urutan yang mungkin, untuk d lebih besar dari perbedaan indeks terbesar. Urutan di mana s[j] lebih besar dari elemen terakhir dalam urutan dihapus.

Saya mengubah kode saya dari JavaScript ke Python (kode python pertama saya):

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



Ini adalah kasus khusus untuk masalah yang lebih umum yang dijelaskan di sini: Temukan pola panjang dimana K = 1 dan diperbaiki. Ini didemostrasikan di sana yang dapat diselesaikan dalam O (N ^ 2). Runnig implementasi saya dari algoritma C yang diusulkan di sana dibutuhkan 3 detik untuk menemukan solusi untuk N = 20000 dan M = 28000 dalam mesin 32-bit saya.


0
2018-02-25 04:12



Metode serakah
1. Hanya satu urutan keputusan yang dihasilkan.
2. Banyak jumlah keputusan yang dihasilkan. Pemrograman dinamis 1. Ini tidak menjamin untuk memberikan solusi optimal selalu.
2. Ini pasti memberikan solusi optimal.


0