Tantangannya adalah untuk memfilter file besar dengan cepat.
- Input: Setiap baris memiliki tiga bilangan bulat positif yang dipisahkan ruang.
Output: Semua jalur input
A
B
,T
yang memenuhi salah satu kriteria berikut.- Ada ada garis masukan lain
C
,D
,U
di manaD = A
dan0 <= T - U < 100
. - Ada ada garis masukan lain
C
,D
,U
di manaB = C
dan0 <= U - T < 100
.
- Ada ada garis masukan lain
Untuk membuat file uji gunakan skrip python berikut yang juga akan digunakan untuk pengujian. Ini akan membuat file 1.3G. Anda tentu saja dapat mengurangi noline untuk pengujian.
import random
nolines = 50000000 # 50 million
for i in xrange(nolines):
print random.randint(0,nolines-1), random.randint(0,nolines-1), random.randint(0,nolines-1)
Aturan Kode tercepat ketika diuji pada file input yang saya buat menggunakan skrip di atas pada komputer saya menang. Batas waktu satu minggu dari waktu entri yang benar pertama.
Mesin Saya Pengaturan waktu akan dijalankan pada mesin saya. Ini adalah instalasi ubuntu RAM 8GB standar pada Prosesor Delapan-Core AMD FX-8350. Ini juga berarti saya harus dapat menjalankan kode Anda.
Beberapa informasi waktu yang relevan
Waktu diperbarui untuk menjalankan yang berikut sebelum setiap tes.
sync && sudo bash -c 'echo 3 > /proc/sys/vm/drop_caches'
time wc test.file
real 0m26.835s
user 0m18.363s
sys 0m0.495s
time sort -n largefile.file > /dev/null
real 1m32.344s
user 2m9.530s
sys 0m6.543s
Status entri
Saya menjalankan baris berikut sebelum setiap tes.
sync && sudo bash -c 'echo 3 > /proc/sys/vm/drop_caches'
- Perl (Menunggu untuk perbaikan bug.)
- Scala 1 menit 37 detik oleh @James_pic. (Menggunakan scala -J-Xmx6g Filterer largefile.file output.txt)
- Jawa . 1 menit 23 detik oleh @Geobits. (Menggunakan java -Xmx6g Filter_26643)
- C . 2 menit 21 detik oleh @ScottLeadley.
- C . 28 detik oleh @James_pic.
- Python + panda . Mungkin ada solusi "groupby" sederhana?
- C . 28 detik oleh @KeithRandall.
Pemenangnya adalah Keith Randall dan James_pic.
Saya tidak tahu waktu lari mereka dan keduanya hampir secepat wc!
1 < n < 2147483647
?Jawaban:
C, ~
74,1 detikRadix sort di T, lalu berjalan melalui array mencari korek api.
Cepat karena ramah cache. Jenis radix masuk akal, dan jalan terakhir sangat. Saya harus memeriksa setiap baris terhadap sekitar 100 lainnya, tetapi semuanya bersebelahan dalam cache.
Ditambahkan: Saya tidak lagi harus memeriksa setiap baris terhadap pemindaian 100 baris lainnya. Tabel kecil jumlah bit urutan rendah b di jendela sudah cukup untuk menghilangkan sebagian besar pemindaian ini.
Sekarang sekitar 1/2 penguraian waktu, 1/3 penyortiran waktu, 1/6 waktu melakukan pencocokan yang sebenarnya.
sumber
filter.c
untuk melakukan hal yang sama, sampai pada pertanyaan dan menemukan ini. +1Scala 2.10 - 0:41
Masalahnya pada dasarnya:
Sebagian besar RDBMS akan melihat bahwa join dari
x.a
toy.b
memiliki kekhususan tertinggi, dan merencanakan ini sebagai hash join.Jadi itu yang akan kita lakukan. Kami membuat hashtabel data aktif
a
, hash gabung dengan tabel yang samab
, dan filter perbedaannyat
.Kompilasi dengan:
Dan jalankan dengan:
Di mesin saya, ini berjalan dalam 2 menit 27.
Namun, mungkin menarik untuk mencoba pendekatan dari jawaban @ Lembik, tetapi dalam bahasa yang lebih cepat. Ini terkait dengan sesuatu seperti gabungan yang bergabung
t
. Di atas kertas, seharusnya lebih lambat, tetapi memiliki lokalitas cache yang lebih baik, yang mungkin mendorongnya ke depan.Memperbarui
Saya telah berhasil mencukur sebagian besar waktu dengan perubahan kecil yang mengejutkan - hash mingler yang lebih baik. Peta hash sangat sensitif terhadap penggumpalan hash, jadi perubahan ini membawanya ke 1:45 di mesin saya.
Sebagian besar waktu dihabiskan membaca data ke dalam array.
Saya ingin tahu mengapa kode membaca data saya jauh lebih lambat daripada @Geobits. Butuh kode saya 70 detik untuk membaca data di - lebih lama dari seluruh program @Geobits, setelah
Thread.start
bug diperbaiki. Saya tergoda untuk mencuri pendekatan @Geobits untuk membaca data, tapi saya tidak yakin bagaimana perasaan para dewa Stack Exchange tentang hal itu.Perbarui 2
Saya telah membuat perbaikan lebih lanjut, kali ini untuk pembaca data. Menggunakan pencocokan pola dan operasi monad di dalam loop merusak kinerja, jadi saya menyederhanakannya. Saya pikir
scala.io.Source
adalah hambatan selanjutnya untuk diatasi.Sekarang jam 1:26 di mesin saya.
Perbarui 3
Singkirkan
probe
dari OpenHashMultiMap. Kode sekarang lebih java-ish, dan berjalan di 1:15.Perbarui 4
Saya sekarang menggunakan FSM untuk mem-parsing input. Jalankan waktu turun ke 0:41
sumber
StringTokenizer
, tetapi ketika saya melakukannya, saya mengurai jutaan string.String.split
saat ini menjadi hambatan, tetapiStringTokenizer
tidak jauh lebih baik sekarang - mengalokasikan dalam lingkaran dalam yang ketat menyakiti GC saya yang sudah tegang. Saya sedang mengerjakan FSM yang tampaknya memiliki janji (sementara benar-benar berlebihan)Java: 1m54s
(Pada i7 saya)
Karena setiap pertandingan akan berada dalam 100
t
dari pasangannya, saya memutuskan untuk memasukkan inputt
. Ada satu ember untuk masing-masing 100, jadi untuk memeriksa nomor, itu hanya perlu memeriksa terhadap +/- 1 ember.Rata-rata, setiap ember hanya berisi 100 entri, sehingga tidak perlu waktu lama untuk memindai beberapa ember untuk masing-masing. Lebih dari separuh waktu dihabiskan untuk membaca dan mengisi, pencocokan hanya membutuhkan waktu sekitar 40 detik.
Catatan: Bergantung pada pengaturan JVM Anda, Anda mungkin perlu menambah ukuran heap. Ini juga mengasumsikan nama file
test.file
. Cukup ubah pada baris 24 jika bukan itu masalahnya.sumber
Thread::run
, bukanThread.start
, jadi semuanya berjalan dimain
utas. DenganThread::start
, waktu berjalan turun dari 1:38 hingga 0:46 di komputer saya.sort
waktu. Saya menumpuk tumpukan hingga 6G, sama seperti milik saya (Anda bilang Anda punya 8G, jadi sepertinya tebakan yang masuk akal).C - 12 detik
Saya memutuskan untuk mengirimkan jawaban Scala saya ke C, untuk melihat berapa banyak lagi kinerja yang bisa saya dapatkan.
Ini kurang lebih pendekatan yang sama (membangun tabel hash terbuka
a
), kecuali bahwa saya melewatkan langkah di mana saya membangun array awal, dan beralih dari tabel hash secara langsung (untuk beberapa alasan saya tidak pernah bisa mendapatkan pendekatan ini untuk tampil di Scala - Saya menduga JVM inlining yang harus disalahkan).Saya tidak peduli dengan benang, karena itu menyakitkan untuk dilakukan dengan mudah.
Kode tersebut adalah:
Kompilasi dengan:
Dan jalankan dengan:
Lokasi file uji dikodekan sebagai "test.file".
Sekali lagi, membaca data menghabiskan sebagian besar waktu (hanya di bawah 9 detik). Pencocokan membutuhkan sisa waktu.
Sekali lagi, akan menarik untuk melihat bagaimana ini bertentangan dengan jawaban Scott Leadley, yang menggunakan bahasa yang sama tetapi strategi yang berbeda. Scott bergabung di T, yang pada prinsipnya berarti ia akan lebih banyak bergabung, tetapi sekali lagi, bergabung dengan T memberikan lokalitas cache yang lebih baik.
sumber
diff <(sort -n James_pic-c.out) <(sort -n James_pic-scala.out)
a
nilai yang diberikan terjadi din
manan >= BUFFER_SIZE + 2
perl, 17m46s pada inti i7 w / 8GB mem
Pertama, kami menggunakan sort -n -k3 untuk mendapatkan bidang yang paling penting secara berurutan, mengambil keuntungan dari paralelisme bawaan pada versi modern sort (1). Kemudian, karena perl sangat terhambat oleh fakta bahwa skalar sederhana mengambil urutan masing-masing 80 byte (50 juta * 3 * 80 terlalu banyak - setidaknya 12GB), kami menghirup output menjadi 50 juta * 12 byte array (12 byte per baris, setiap baris berisi 3 integer yang dapat direpresentasikan sebagai integer 32 bit). Lalu kami melepaskan 8 utas yang masing-masing mencakup (sekitar) 1/8 data (+ beberapa tumpang tindih).
Output tidak disortir:
Saya yakin ini akan menjadi urutan besarnya lebih cepat di C, tapi saya mungkin tidak akan meluangkan waktu untuk melakukannya.
sumber
A = D = 8455767
, tapiU = 50175
,T = 50130
, dan sebagainyaT - U = -45
C # - 30 Detik
Pendekatan yang berbeda dari kebanyakan jika saya membaca dengan benar - saya tidak menggunakan struktur berbasis hash.
Saya cenderung tidak mendapatkan hasil, tidak yakin apakah ini anomali statistik, atau kesalahan dalam alasan saya.Memperbaiki, perbandingan untuk jenis biner cacat.sumber
x.A
akan datangsortedA
, danx.B
akan datang darisortedB
, sedangkan sebenarnya keduanya akan datangsortedB
, dan iniComparer
akan menghasilkan hasil omong kosongA
danB
, ada algoritma yang lebih cepat daripada iterasiA
dan pencarian binerB
yangO(n log(n))
(dan secara efektif tabel hash orang miskin). Anda malah dapat menggabungkan-bergabung dengan dua daftar, yangO(n)
.B
akan didistribusikan secara seragam dalam rentang tertentu, akan menukar pencarian biner untuk pencarian interpolasi, yang mengurangi waktu pencarian dariO(log(n))
menjadiO(log(log(n))
.C
Brutal, brute force, C. jelek di muka Anda. Pada saat do-over saya akan memilih bahasa kompilasi lainnya.
Kompilasi dengan "gcc -m64 -pthreads -O". Diharapkan input pada stdin. Berjalan multi-utas secara default. Gunakan opsi "-s" untuk hanya menggunakan satu utas.
sumber
Saya akhirnya mendapat kesempatan untuk membangun sistem Ubuntu 14.04 fisik yang mirip dengan Lembik dan melakukan post-mortem pada solusi saya untuk puzzle ini. Dalam pilihan saya yang penting:
terhentiadalah tidak bekerja:Daripada membuat Anda bosan dengan parser FSM lain, solusi di bawah ini menggunakan pengganti fgets () dan lokal strtol () [cari s2i ()].
Implementasi referensi di Ruby:
Ini adalah anjing, ~ 50x lebih lambat dari solusi C, tetapi perl sama lambat dan kurang ringkas.
Solusi C:
Kompilasi dengan "gcc -O3 -std = c99 -Wall -m64".
sumber