Get best of the week

wc ke D: 712 karakter tanpa cabang tunggal

Setelah membaca " Beat With a 80-Line Program di Haskell," yang saya temukan di Hacker News , saya memutuskan bahwa D mungkin lebih baik. Dan saya menulis wc di D.

Note.per. Saya sarankan menerjemahkan artikel di atas0xd34df00d, tetapi ia lebih suka untuk membuat berdasarkan "Winning With Twenty Lines of Haskell: Writing Your Wc" . Dan sekarang artikel itu berlipat ganda seperti pengulangan "koin dicetak."

Program


Terdiri dari satu file - 34 baris dan 712 karakter.

Kode sumber
import std.stdio : writefln, File;
import std.algorithm : map, fold, splitter;
import std.range : walkLength;
import std.typecons : Yes;
import std.uni : byCodePoint;

struct Line {
	size_t chars;
	size_t words;
}

struct Output {
	size_t lines;
	size_t words;
	size_t chars;
}

Output combine(Output a, Line b) pure nothrow {
	return Output(a.lines + 1, a.words + b.words, a.chars + b.chars);
}

Line toLine(char[] l) pure {
	return Line(l.byCodePoint.walkLength, l.splitter.walkLength);
}

void main(string[] args) {
	auto f = File(args[1]);
	Output o = f
		.byLine(Yes.keepTerminator)
		.map!(l => toLine(l))
		.fold!(combine)(Output(0, 0, 0));

	writefln!"%u %u %u %s"(o.lines, o.words, o.chars, args[1]);
}


Tentu saja, ia menggunakan Phobos, pustaka D standar , tetapi mengapa tidak? Phobos indah, dan dilengkapi dengan setiap kompiler D. Program itu sendiri tidak mengandung pernyataan if. Dan dalam implementasi wc di Haskell, beberapa jika digunakan. Program D, selain yang utama, berisi tiga fungsi lebih kecil. Saya bisa dengan mudah meletakkan semua fungsionalitas dalam satu rantai rentang, tetapi mungkin melebihi 80 karakter per baris. Ini adalah prinsip dasar gaya kode.

Performa


Apakah wc pada D lebih cepat dari coreutils wc? Tidak, tapi butuh 15 menit untuk menulis versi saya (saya harus mencari walkLength karena saya lupa nama fungsinya).
file datagarisbytecoreutilsHaskellD
app.d469063,5 ms ± 1,9 ms39,6 ms ± 7,8 ms8,9 ms ± 2,1 ms
big.txt86264rb4,7 ms ± 2,0 ms39,6 ms ± 7,8 ms9,8 ms ± 2,1 ms
vbig.txt1,7 jt96 jt658.6ms ± 24.5ms226,4 ms ± 29,5 ms1,102 s ± 0,022 s
vbig2.txt12.1M671M4,4 s ± 0,058 dtk1,1 s ± 0,039 dtk7,4 s ± 0,085 dtk

Penyimpanan:
file datacoreutilsHaskellD
app.d2052K7228K7708K
big.txt2112K7512K7616K
vbig.txt2288K42620K7712K
vbig2.txt2360K50860K7736K
Apakah Haskell lebih cepat? Untuk file besar, tentu saja, tetapi menggunakan multithreading. Untuk file kecil, GNU coreutils masih menang. Pada tahap ini, versi saya kemungkinan besar dibatasi oleh IO, dan bagaimanapun, ini cukup cepat.

Saya tidak akan berdebat bahwa satu bahasa lebih cepat dari yang lain. Jika Anda menghabiskan waktu mengoptimalkan patokan mikro, kemungkinan besar Anda akan menang. Namun tidak dalam kehidupan nyata. Tapi saya akan berpendapat bahwa pemrograman fungsional dalam D hampir menyusul dengan FP di Haskell.

Sedikit tentang rentang dalam D


range adalah abstraksi yang dapat diulang tanpa menyentuh koleksi yang mendasarinya (jika ada). Secara teknis, range dapat berupa struktur atau kelas yang mengimplementasikan satu atau lebih interface Range. Bentuk paling sederhana, InputRange, membutuhkan fungsi

void popFront();

dan dua anggota atau properti

T front;
bool empty;

T adalah jenis elemen generik yang berkisar berulang.

Rentang D adalah tipe spesifik. Ketika rentang jatuh ke pernyataan foreach, kompiler melakukan modifikasi kecil.

foreach (e; range) { ... }

berubah menjadi

for (auto __r = range; !__r.empty; __r.popFront()) {
    auto e = __r.front;
    ...
}

auto e = menghitung jenis dan setara dengan T e =.
Dengan mengingat hal ini, mudah untuk membuat rentang yang dapat digunakan oleh foreach.

struct Iota {
	int front;
	int end;

	@property bool empty() const {
		return this.front == this.end;
	}

	void popFront() {
		++this.front;
	}
}

unittest {
	import std.stdio;
	foreach(it; Iota(0, 10)) {
		writeln(it);
	}
}

Iota adalah contoh rentang yang sangat sederhana. Berfungsi sebagai generator, tanpa memiliki koleksi yang mendasarinya. Ia beralih melalui bilangan bulat dari awal hingga selesai dengan penambahan satu. Cuplikan ini mengungkapkan sedikit sintaks D.

@property bool empty() const {

Atribut @ property memungkinkan Anda untuk menggunakan fungsi kosong dengan cara yang sama seperti variabel anggota (memanggil fungsi tanpa tanda kurung). Atribut const di bagian akhir berarti bahwa kita tidak mengubah data instance yang kita sebut kosong . Uji unit bawaan mencetak angka dari 0 hingga 10.

Fitur kecil lainnya adalah tidak adanya konstruktor eksplisit. Struktur Iota memiliki dua variabel int anggota. Dalam pernyataan pendahuluan dalam pengujian, kami membuat instance Iota seolah-olah memiliki konstruktor yang menerima dua int. Ini adalah struktur literal. Ketika kompiler D melihat ini, tetapi struktur tidak memiliki konstruktor yang sesuai, maka sesuai dengan urutan deklarasi variabel - anggota struktur akan ditugaskan int.

Hubungan antara ketiga anggota itu sederhana. Jika kosong salah, depan dijamin untuk mengembalikan elemen baru setelah iterasi setelah memanggil popFront. Setelah memanggil popFront, nilai kosong dapat berubah. Jika ini benar, itu berarti bahwa tidak ada lagi elemen untuk beralih dan panggilan lebih lanjut ke depan tidak valid. Menurut dokumentasi InputRange :

  • depan dapat dihitung dengan benar jika dan hanya jika pengembalian kosong atau akan kembali salah.
  • front dapat dikomputasi beberapa kali tanpa memanggil popFront atau memutasi rentang atau data yang mendasarinya, dan memberikan hasil yang sama untuk setiap perhitungan.

Menggunakan ekspresi foreach, atau loop, tidak terlalu fungsional. Misalkan kita ingin memfilter semua angka ganjil untuk Iota. Kita bisa menempatkan if di dalam blok foreach, tapi itu hanya akan memperburuknya. Akan lebih baik jika kita memiliki rentang yang menerima rentang dan predikat yang memutuskan apakah suatu elemen cocok atau tidak.

struct Filter {
	Iota input;
	bool function(int) predicate;

	this(Iota input, bool function(int) predicate) {
		this.input = input;
		this.predicate = predicate;
		this.testAndIterate();
	}

	void testAndIterate() {
		while(!this.input.empty
				&& !this.predicate(this.input.front))
		{
			this.input.popFront();
		}
	}

	void popFront() {
		this.input.popFront();
		this.testAndIterate();
	}

	@property int front() {
		return this.input.front;
	}

	@property bool empty() const {
		return this.input.empty;
	}
}

bool isEven(int a) {
	return a % 2 == 0;
}

unittest {
	foreach(it; Filter(Iota(0,10), &isEven)) {
		writeln(it);
	}
}

Filter sekali lagi sangat sederhana: Iota dan pointer fungsi diperlukan. Saat membuat Filter, kami memanggil testAndIterate, yang mengambil elemen dari Iota sampai kosong atau predikat mengembalikan false. Idenya adalah bahwa predikat memutuskan apa yang harus disaring dan apa yang harus pergi. Properti depan dan kosong hanya diterjemahkan ke Iota. Satu-satunya hal yang benar-benar melakukan pekerjaan adalah popFront. Ini mengembalikan item saat ini dan memanggil testAndIterate. Itu saja. Ini adalah implementasi filter.

Tentu saja, testAndIterate memiliki loop sementara, tetapi menulis ulang menggunakan rekursi, menurut saya, sangat bodoh. Apa yang membuat D hebat adalah bahwa Anda dapat menggunakan metode yang tepat untuk setiap tugas. Pemrograman fungsional itu baik, dan sering memamerkan, tetapi terkadang tidak. Jika sedikit assembler inline diperlukan atau lebih menyenangkan, gunakan.

Filter Panggilan masih tidak terlihat bagus. Dengan asumsi Anda terbiasa membaca dari kiri ke kanan, Filter muncul sebelum Iota, bahkan jika itu berjalan setelah Iota. D tidak memberikan pernyataan pipa, tetapi menggunakan Unified Function Call Syntax (UFCS). Jika suatu ekspresi dapat secara implisit dikonversi ke parameter pertama dari suatu fungsi, maka fungsi tersebut dapat dipanggil seolah-olah itu adalah fungsi anggota dari ekspresi ini. Ini cukup rumit, saya mengerti. Contoh akan membantu:

string foo(string a) {
	return a ~ "World";
}

unittest {
	string a = foo("Hello ");
	string b = "Hello ".foo();
	assert(a == b);
}

Contoh di atas menunjukkan dua panggilan ke fungsi foo. Seperti yang dinyatakan secara tidak langsung, kedua panggilan itu setara. Apa artinya ini untuk contoh Filter Iota kami? UFCS memungkinkan kami menulis ulang unit test seperti ini:

unittest {
	foreach(it; Iota(1,10).Filter(&isEven)) {
		writeln(it);
	}
}

Implementasi peta / transformasi untuk jangkauan sekarang harus dapat diakses oleh setiap pembaca. Tentu saja, filter dapat dibuat lebih abstrak menggunakan templat, tetapi ini hanya detail, tidak ada yang secara konsep baru.

Tentu saja, ada berbagai jenis rentang, misalnya, dua arah. Tebak peluang apa yang memberi Anda ini. Kiat cepat: ada dua primitif baru dalam rentang dua arah yang disebut kembali dan popBack. Ada jenis rentang lain, tetapi setelah Anda memahami rentang input yang ditunjukkan di atas dua kali, Anda hampir semua mengenalinya.

PS Hanya untuk kejelasan, jangan menerapkan filter, peta, atau lipatan Anda sendiri; perpustakaan standar Phobos D memiliki semua yang Anda butuhkan. Mengambil lihat di std.algorithm dan std.range .

tentang Penulis


Robert Schadeck meraih gelar master dalam ilmu komputer dari University of Oldenburg. Tesis masternya berjudul "DMCD - Distributed Multithreaded D Compiler dengan Caching", di mana ia bekerja untuk menciptakan D-compiler dari awal. Dia adalah seorang mahasiswa pascasarjana dalam ilmu komputer pada 2012-2018. di Universitas Oldenburg. Disertasi doktoralnya berfokus pada sistem kuorum bersama dengan grafik. Sejak 2018, ia senang menggunakan D dalam pekerjaan sehari-harinya, bekerja untuk Symmetry Investments.

Tentang Investasi Simetri


Symmetry Investments adalah perusahaan investasi global dengan kantor di Hong Kong, Singapura dan London. Kami telah melakukan bisnis sejak 2014 setelah berhasil memisahkan diri dari hedge fund utama New York.

Di Symmetry, kami berusaha untuk mengambil risiko yang wajar untuk menciptakan nilai bagi pelanggan, mitra, dan karyawan kami. Kami mendapat manfaat dari kemampuan kami untuk menghasilkan kontrak win-win - dalam arti luas. Menang-Menang adalah prinsip dasar etika dan strategis kami. Dengan menghasilkan opsi menang-menang, kita dapat menciptakan solusi unik yang menggabungkan perspektif yang biasanya dianggap tidak kompatibel atau berlawanan, dan mencakup semua yang terbaik yang dapat ditawarkan masing-masing pihak. Kami mengintegrasikan kembali arbitrase pendapatan tetap dengan strategi makro global. Kami menemukan dan mengembangkan teknologi yang berfokus pada potensi integrasi manusia-mesin. Kami menciptakan sistem di mana mesin melakukan yang terbaik, mendukung orang di dalamnyasehingga mereka melakukan yang terbaik. Kami menciptakan meritokrasi berdasarkan kolaborasi: budaya di mana kontribusi individu melayani tujuan pribadi dan kolektif - dan dihargai sesuai dengan itu. Kami menghargai rasa kepemilikan dan semangat kerja sama tim, realisasi diri, dan komunitas.

Orang-orang Symmetry Investments telah menjadi anggota aktif Komunitas D sejak 2014. Kami mensponsori pengembangan proyek excel-d, dpp, autowrap, libmir dan lainnya. Kami meluncurkan Symmetry Autumn of Code pada tahun 2018 dan menjadi tuan rumah DConf 2019 di London.

Perkiraan. Karena penerjemah, seperti biasa, mabuk, saya tidak dapat menjamin keakuratan beberapa istilah manusia, dan saya tidak mengerti apa pun di bagian terakhir. Jadi kirim koreksi dalam komunikasi pribadi.

More articles:


All Articles