Evet, opCmp o tür için şüphe götürmez bir sıralama kararı bulunduğunda mantıklı oluyor. Örneğin bir kesirli sayı türünün değerine göre sıralanması mantıklı. Dediğiniz gibi, Kitap gibi bir türde ise sıralamanın nasıl olacağı duruma göre değişir. Örneğin, bazen yazar ismine göre sıralamak gerekir.
sort() diziyi zaten sıralıyor. O yüzden .array çağırmadan doğrudan kullanılabilir.
SortedRange dönüyor olmasının yararı, SortedRange'in üye işlevlerinin bu durumdan yararlanıp çok daha hızlı olabilen ikili arama algoritmasını kullanıyor olmaları. (SortedRange yalnızca RandomAccessRange'lerle kullanılabiliyor.) SortedRange'den yararlanan işlevlerden en doğal olanı std.algorithm.find'dır: Gelen aralık bir SortedRange olduğunda O(log(N)) karmaşıklığındaki SortedRange.equalRange'i çağırır:
import std.stdio;
import std.range;
import std.algorithm;
import std.datetime.stopwatch;
import std.string;
enum elemanAdedi = 1_000_000;
enum ölçümAdedi = 1_000;
const static int arananSayı;
static this() {
// Sırayla aramada ortalama süre tutsun diye ortalarda bir değer arayalım
import std.random;
enum hataPayı = 1000;
static assert(elemanAdedi > hataPayı);
const ek = uniform(-(hataPayı / 2), (hataPayı / 2));
arananSayı = (elemanAdedi / 2) + ek;
writefln("Aranan sayı: %s", arananSayı);
}
auto std_algorithm_find_ile(R)(R sayılar) {
// std.algorithm.find aralık hakkında bir varsayımda bulunamayacağından olan
// sırayla aramak zorundadır. Karmaşıklık (complexity) genelde O(N)'dir.
// Ancak, R'nin bir SortedRange olduğunu bildiğinde o da s.equalRange'i
// çağırır.
auto sonuç = find(sayılar, arananSayı);
assert(!sonuç.empty);
return sonuç.front;
}
auto SortedRange_equalRange_ile(R)(R sayılar) {
// SortedRange sıralı olduğunu bildiğinden ikili aramayı
// uygular. Karmaşıklık: O(log(N))
auto sonuç = sayılar.equalRange(arananSayı);
assert(!sonuç.empty && sonuç.front == arananSayı);
return sonuç.front;
}
void main() {
auto dizi = iota(elemanAdedi).array;
auto s = sort(dizi);
const ölçümler = benchmark!(() => std_algorithm_find_ile(dizi),
() => std_algorithm_find_ile(s),
() => SortedRange_equalRange_ile(s))
(ölçümAdedi);
writefln("std.algorithm.find ile dizi : %s", ölçümler[0]);
writefln("std.algorithm.find ile SortedRange: %s", ölçümler[1]);
writefln("SortedRange.equalRange ile : %s", ölçümler[2]);
}
SortedRange yöntemi du deneyde binlerce kat hızlı çıkıyor:
'
Aranan sayı: 500061
std.algorithm.find ile dizi : 936 ms, 530 μs, and 2 hnsecs
std.algorithm.find ile SortedRange: 123 μs and 9 hnsecs
SortedRange.equalRange ile : 129 μs and 5 hnsecs
'
Çok önemli olarak, find'ın yavaş kaldığı durumda dizinin kendisini gönderdiğimize dikkat edin. Sıralanmış olan bir aralık üzerinde arama yapmak gerektiğinde SortedRange'i kullanmak şart.
SortedRange.equalRange bir aralık döndürür. Boş olmadığından emin olup .front'unu kullanmak gerekiyor. equalRange'in yararı, birden fazla sayı bulunduğunda hepsine eriştiriyor olması. (Aşağıdaki örnekte birden fazla sayı kullanacağım.)
Aslında bu örnekte bir enayilik var: iota() ile üretilen sayılar yaşamlarına sıralı olarak başlayacaklarından sort()'u çağırmak gereksiz olmalı. Böyle durumlar için "sıralı olduğunu varsay" anlamında assumeSorted var. Bize güvenip SortedRange'i döndürür:
// auto s = sort(dizi);
auto s = dizi.assumeSorted;
Böylece sırama işleminden bile kurtulmuş oluruz.
equalRange'in kullanımını gösteren bir örnek:
import std.stdio;
import std.range;
import std.random;
import std.algorithm;
auto diziOluştur() {
// Basit olsun diye "emirli" (imperative) yöntem kullanıyorum
int[] sonuç;
foreach (_; 0 .. 30) {
sonuç ~= uniform(0, 10);
}
return sonuç;
}
void main() {
auto dizi = diziOluştur();
auto s = sort(dizi);
enum arananSayı = 7;
writeln("Dizi: %s", s);
writefln("Dizideki %s değerli bütün elemanlar:", arananSayı);
foreach (eleman; s.equalRange(arananSayı)) {
writeln(eleman);
}
}
Verilen aralığın SortedRange olduğundan bundan yararlanmak isteyen işlev yazmak istediğimizde std.traits'ten yararlanabiliriz:
import std.stdio;
import std.range;
import std.algorithm;
void foo(R)(R aralık) {
import std.traits;
static if (isInstanceOf!(SortedRange, R)) {
writeln("Güzel, SortedRange");
} else {
writeln("SortedRange değil");
}
}
void main() {
auto dizi = [ 3, 1, 2 ];
auto s = sort(dizi);
foo(s);
foo(dizi);
}
Ali
--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]
Permalink
Reply