Apakah setiap algoritma linear waktu merupakan algoritma streaming?

14

Atas pertanyaan tentang penghitungan inversi ini , saya menemukan makalah yang membuktikan batas bawah pada kompleksitas ruang untuk semua algoritma streaming (pasti) . Saya telah mengklaim bahwa batasan ini meluas ke semua algoritma waktu linier. Ini agak berani seperti pada umumnya, algoritma waktu linier dapat melompat-lompat sesuka hati (akses acak) dimana algoritma streaming tidak bisa; harus menyelidiki elemen-elemen secara berurutan. Saya dapat melakukan beberapa lintasan, tetapi hanya terus-menerus banyak (untuk runtime linier).

Karena itu pertanyaan saya:

Dapatkah setiap algoritma linear waktu dinyatakan sebagai algoritma streaming dengan banyak lintasan yang terus-menerus?

Akses acak tampaknya mencegah konstruksi (sederhana) yang membuktikan jawaban positif, tetapi saya belum dapat memberikan contoh balasan.

Bergantung pada model mesin, akses acak bahkan mungkin tidak menjadi masalah, karena runtime. Saya akan tertarik pada jawaban untuk model-model ini:

Mesin turing, input datar
RAM, masukan sebagai array
RAM, masukan sebagai daftar tertaut

algorithms streaming-algorithm simulation lower-bounds Raphael
sumber

seperti yang Anda lihat di jawaban, "algoritma streaming" sering menyiratkan kecil (ruang polylog). tetapi mengingat motivasi Anda, pertanyaan saya pikir harus: bisa setiap algoritma waktu linear yang menggunakan

kata-kata dari ruang kerja dikonversi ke algoritma mengalir yang menggunakan

kata ruang. jadi contoh tandingan akan menjadi masalah yang dapat dipecahkan dengan

ruang dengan akses acak sedangkan algoritma aliran terus-menerus konstan membutuhkan ruang

. belum ada jawaban yang memberikan contoh seperti itu

s

$s$

O (s)

$O(s)$

o (n)

$o(n)$

Ω (n)

$\Omega(n)$

Sasho Nikolov

@SashoNikolov: Sebenarnya, masalah seluruh ruang adalah tangensial. Pertanyaan saya terutama tentang runtime. Jika jawabannya "ya", maka batas bawah (pada kompleksitas ruang) yang dibuktikan dalam makalah akan berlaku untuk semua algoritma linear-waktu. Bahwa batas bawah adalah ruang adalah insidental, tetapi bukan fokus dari pertanyaan itu sendiri.

Raphael

Saya tidak mengerti. Itu sepele untuk membuat algoritma waktu linier menjadi "one pass streaming" dengan ruang tak terbatas. Pertanyaan Anda hanya masuk akal jika dalam bentuk "dapatkah algoritma akses acak waktu linier dibuat streaming aliran konstan sambil mempertahankan ukuran kompleksitas

". Jadi Anda harus memilih ukuran kompleksitas, ya ini tidak masuk akal.

μ

$\mu$

Sasho Nikolov

@ SashoNikolov: Saya tidak tahu bahwa "algoritma streaming" memiliki masalah definisi seperti itu. Mengingat bahwa mereka menunjukkan ruang linier batas bawah untuk algoritma streaming, saya berasumsi bahwa ruang bukan inti dari definisi. Tapi saya kira Anda bisa menerjemahkan yang terikat ke "Tidak ada algoritma streaming ...". Namun, bagaimana dengan definisi ini: "Algoritma streaming adalah algoritma yang diberi input (daftar) satu elemen setiap saat. Untuk setiap elemen baru, ia dapat melakukan perhitungan dalam

. Setelah terus-menerus banyak lintasan seperti itu , harus menampilkan jawaban setelah waktu

. "

o (n)

$o(n)$

o (n)

$o(n)$

Raphael

@SashoNikolov: Itu akan mengecualikan "salin input dan melakukan apa saja" algoritma dari gagasan, tetapi batasi hingga

waktu. Apakah itu sesuai dengan kelas yang biasanya dilambangkan? Jika tidak, saya tidak berpikir "streaming" dapat didefinisikan dari waktu ke waktu atau kompleksitas ruang yang berguna. Ini lebih merupakan strategi, mirip dengan Greedy atau divide & conquer.

o (n^{2})

$o(n^2)$

Raphael

15

Agar algoritma streaming menjadi bermakna, mereka harus bekerja dengan jumlah ruang kerja yang jauh lebih kecil daripada input itu sendiri. Misalnya, jika Anda mengizinkan jumlah ruang kerja yang sama dengan input, maka Anda dapat dengan mudah menyatakan algoritme apa pun sebagai “algoritme streaming satu-pass” yang pertama-tama menyalin input ke ruang kerja dalam satu pass dan kemudian hanya menggunakan karya tersebut ruang.

Saya pikir itu tipikal untuk membatasi ruang kerja paling banyak polylogarithmic dalam ukuran input ketika berbicara tentang algoritma streaming. Berdasarkan asumsi ini, pemilihan median tidak memiliki algoritma streamingpass O (1) oleh hasil Munro dan Paterson [MP80]: algoritma streaming P- pass untuk seleksi median pada elemen N harus disimpan Ω ( N ^{1 / P} ) elemen. Di sisi lain, pemilihan median memiliki algoritma linear-time deterministik yang terkenal [BFPRT73].

[BFPRT73] Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, dan Robert E. Tarjan. Batas waktu untuk seleksi. Jurnal Ilmu Komputer dan Sistem , 7 (4): 448–461, Agustus 1973. DOI: 10.1016 / S0022-0000 (73) 80033-9

[MP80] J. Ian Munro dan Mike S. Paterson. Seleksi dan penyortiran dengan penyimpanan terbatas. Theoretical Computer Science , 12 (3): 315–323, November 1980. DOI: 10.1016 / 0304-3975 (80) 90061-4

Tsuyoshi Ito
sumber

6

Dalam model streaming, Anda hanya diperbolehkan menyimpan data ekstra konstan atau poli-logaritmik saat memindai melalui input. Jika Anda mempertimbangkan algoritma waktu linear
yang mengikuti paradigma divide and conquer , Anda perlu menyimpan lebih banyak informasi dan / atau Anda harus memindai data Anda sebanyak kedalaman rekursi.

Salah satu contoh adalah algoritma DC3 untuk membangun array sufiks teks (diberikan sebagai array dalam model RAM). Untuk membangun susunan sufiks, Anda mengelompokkan karakter ke dalam triplet, sehingga Anda mendapatkan teks dengan karakter super baru . Anda dapat melakukan ini dengan offset , yang menghasilkan tiga teks baru . Menariknya, Anda dapat menghitung array sufiks jika Anda memiliki array sufiks dalam waktu linier. Oleh karena itu kebutuhan algoritma $T$ $0,1,2$ $T_1,T_2,T_3$ $T_1\cdot T_2$

t (n) = t (2 / 3 n) + O (n)

$t(n)= t(2/3 \;n) + O(n)$

waktu. Rekursi ini diselesaikan dengan jelas untuk . Saya tidak melihat bagaimana ini dapat diubah menjadi algoritma streaming. $t(n)=O(n)$

Contoh lain yang terkenal adalah algoritma pemilihan linear-time klasik .

A.Schulz
sumber

Berikut adalah contoh lain yang mungkin. Membangun heap mengambil O (n) dan menggunakan internal heapify () subrutin yang membagi dan menaklukkan.

Massimo Cafaro

tapi ini bukan bukti, kan? Anda hanya mengatakan bahwa simulasi naif tidak akan berhasil. tetapi kadang

Sasho Nikolov

@SashoNikolov: Apa yang saya katakan adalah saya tidak menganggap algoritma DC3 sebagai algoritma streaming, karena itu membutuhkan banyak memori yang bekerja. Mungkin Anda dapat memodifikasi algoritme menjadi algoritme streaming, tetapi hasilnya bukan DC3. Saya belum membahas, apakah ada

streaming algoritma untuk konstruksi array suffix. Ini akan menjadi pertanyaan yang sangat berbeda.

O (n)

$O(n)$

A.Schulz

"Saya tidak melihat bagaimana ini dapat diubah menjadi algoritma streaming" membuat saya yakin Anda mengatakan sesuatu selain "algoritma ini tidak mengalir tanpa modifikasi"

Sasho Nikolov

4

$P$

$R(P)$ $P$
$S(P)$ $P$

$R(P)$ $S(P)$

$n$ $[1, n-1]$ $O(\log n)$ $O(1)$ $\omega(\log n)$

$O(1/\log^2 n)$ $ps = \Omega(\sqrt{n})$ $p$ $s$ $O(\log^2 n)$

Sasho Nikolov
sumber

1

Bahkan dalam definisi paling sederhana dari "algoritma streaming" (sebuah algoritma yang, setelah setiap iterasi tambahan pada sumber, menghasilkan pengetahuan langsung dari potongan tambahan selanjutnya dari hasil), saya dapat memikirkan beberapa algoritma linier yang tidak berperilaku seperti itu. Algoritma Hashing adalah yang besar; FNV-1a linier dengan jumlah byte di sumber, tetapi kami tidak tahu bagian dari hash terakhir sampai sumber penuh telah diproses.

RadixSort alias BucketSort adalah O (N) (secara teknis O (NlogM) di mana M adalah nilai maksimum dalam item N, yang dianggap kecil), dan harus dijalankan secara keseluruhan untuk menjamin bahwa setiap item individual ada di tempat akhirnya.

Untuk menjadi algoritma "streaming", yang paling sederhana, suatu algoritma harus memiliki dua properti berikut, yang keduanya tidak terikat waktu:

Kompleksitas ruang yang lebih baik daripada O (N) (dinyatakan secara ekivalen, seluruh sumber tidak harus diketahui dan seluruh hasil tidak harus disimpan)
Hubungan O / N (I / O) (algoritma menghasilkan sejumlah output yang berbanding lurus dengan inputnya)

Oleh karena itu, kelas utama dari algoritma yang melakukan streaming adalah algoritma yang melakukan "proyeksi" (transformasi tambahan dari satu input ke output X> 0).

KeithS
sumber

O (\log n)

$O(\log n)$

ω (1)

$\omega(1)$

logN juga baik-baik saja; intinya adalah bahwa algoritma seharusnya tidak memerlukan pengetahuan tentang seluruh input atau output sekaligus.

KeithS

Ω (n)

$\Omega(n)$

Apakah setiap algoritma linear waktu merupakan algoritma streaming?

Jawaban: