O(lg N) - Ali Çehreli

Varsayımlar
D programlama dilindeki
resmileştirilmiş varsayımlar
Ali Çehreli
DConf 2014
http://ddili.org
1 / 26
[OT] Walter Bright'ın sunumu ile ilgili ek yansı
toString üye işlevinin sink yüklemesini yeğleyin:
YAVAŞ:
string toString() const
{
return format("%s", a);
}
Çirkin olduğundan anlaşılabileceği gibi, HIZLI:
void toString(void delegate(const(char)[]) sink) const
{
formattedWrite(sink, "%s", a);
}
Reklam: Bu konuda daha fazla bilgi için,
http://ddili.org/ders/d/kapamalar.html
http://ddili.org
2 / 26
Bu sunumu düşündüren nedenler
1. assumeSorted ("sıralanmış olduğunu varsay") hem ilginçtir hem
de hız açısından önemlidir
2. phobos/std klasöründe "assume" (varsay) sözcüğü
grep'lendiğinde başka olanaklar da bulunur
3. Oysa, yazılım hataları nedeniyle oluşan bazı felaketlerin
kaynağının varsayımlar olduğu bilinir
◦ Yanan roketler
◦ Yanlış sonuç üreten parçacık hızlandırıcıları
◦ Batan savaş gemileri
◦ Kullanılamayan ambülans sistemleri
◦ vs.
Kaynak: "The Role and Impact of Assumptions in Software
Development, Maintenance and Evolution", Meir M Lehman
http://ddili.org
3 / 26
Bu sunumun asıl nedeni
Bu sunum olmasa DConf 2014 ancak
%97 tamamlanmış olurdu.
http://ddili.org
4 / 26
Varsayımlar tehlikelidir
"Assumptions are dangerous things to make, and like all dangerous
things to make -- bombs, for instance, or strawberry shortcake -- if you
make even the tiniest mistake you can find yourself in terrible
trouble." ― Lemony Snicket, The Austere Academy
"Asla varsayma." ― Anonim
http://ddili.org
5 / 26
Varsayımlar heryerde bulunur
• Programdan istenenler konusunda
• Tasarım kararları konusunda
• Programın çalıştığı ortam hakkında (örneğin, internete bağlı olma
konusunda)
• Kodun davranışı konusunda (işlev çağıranlar, işlevler, vs.)
• Kütüphane arayüzleri konusunda
Bir varsayım:
readf(" %s", &a);
writeln(a);
Aynı varsayımın denetlenmesi:
import std.exception : enforce;
uint adet = readf(" %s", &a);
enforce(adet == 1, "Okunamadı");
http://ddili.org
6 / 26
Varsayımlar denetlenmelidir
(olabiliyorsa, hata düzeneği yoluyla)
assert
(denetim başarısız olduğunda Error atar)
• in bloklarında
• out bloklarında
• invariant bloklarında
• unittest bloklarında
• Uygun olan başka her durumda
enforce
(denetim başarısız olduğunda Exception atar)
• İşlevi çağıranı denetlerken
• Çağrılmış olan işlevi denetlerken
• Uygun olan başka her durumda
http://ddili.org
7 / 26
Resmileştirilmiş
varsayım örnekleri
http://ddili.org
8 / 26
Konu: Normalde kullanılan,
sırayla aramadır (linear search)
Sıralanmamış olan giriş aralıklarını da kabul ettiklerinden
std.algorithm içindeki arama işlevleri sırayla arama algoritmasını
kullanırlar (O(N)):
import std.algorithm;
int[] arr = [ /* ... */ ];
arr.find
(/*
arr.findSplit
(/*
arr.findAdjacent(/*
arr.canFind
(/*
// etc.
http://ddili.org
...
...
...
...
*/);
*/);
*/);
*/);
//
//
//
//
//
O(N)
O(N)
O(N)
O(N)
O(N)
9 / 26
O(lg N) karmaşıklık için SortedRange
std.algorithm içindeki sıralama işlevleri std.range.SortedRange
nesneleri döndürürler. SortedRange O(lg N) karmaşıklıkta işleyen
arama algoritmaları sunar (ikili arama (binary search)):
auto sıralı = arr.sort();
// (schwartzSort, completeSort, veya makeIndex de olur)
import std.range;
sıralı.contains (/*
sıralı.lowerBound(/*
sıralı.equalRange(/*
sıralı.upperBound(/*
sıralı.trisect
(/*
...
...
...
...
...
*/);
*/);
*/);
*/);
*/);
//
//
//
//
//
O(lg
O(lg
O(lg
O(lg
O(lg
N)
N)
N)
N)
N)
Zincirleme de kullanılır (UFCS):
foo
.bar
.sort
.contains(42);
// O(lg N)
Hediyesi: debug derlemelerinde rasgele elemanları karşılaştırarak
sırası bozuk eleman olup olmadığını anlamaya çalışır. Bu denemelerin
sayısı algoritmik karmaşıklığı bozacak kadar fazla değildir.
http://ddili.org
10 / 26
Sıralanmış olan hangisi?
auto arr = [ /* ... */ ];
auto sıralı = arr.sort();
Aslında ikisi de sıralanmıştır:
• arr 'ın elemanları sıralanmıştır
• sıralı , arr 'ı sıralanmış bir aralık olarak sunar
Ancak, O(lg N) karmaşıklığı sağlayan sıralanmış olma bilgisi yalnızca
sıralı 'da bulunur:
arr.canFind(5);
sıralı.contains(5);
// O(N)
// O(lg N)
Dolayısıyla, bunu yapmayın:
arr.sort();
// ...
arr.canFind(5);
http://ddili.org
// Dönüş değerini gözardı ediyor
// Gereksizce O(N)
11 / 26
Sorun: Aralık zaten sıralı olabilir
import std.range;
void main()
{
auto arr = iota(5)
.map!(a => a * 2);
assert(arr.equal([0, 2, 4, 6, 8]));
}
http://ddili.org
// açıkça sıralı
// Ama ne yazık ki SortedRange değil:
auto sonuç = arr.trisect(6);
// ← derleme HATASI
12 / 26
Çözüm: assumeSorted
("sıralanmış olduğunu varsay")
import std.range;
void main()
{
auto arr = iota(5)
.map!(a => a * 2)
.assumeSorted;
assert(arr.equal([ 0, 2, 4, 6, 8 ]));
}
// Bu sefer bir SortedRange.
auto sonuç = arr.trisect(6);
// O(lg N)
trisect() 'in ürettiği sonuç:
assert(result[0].equal([ 0, 2, 4 ]));
assert(result[1].equal([ 6 ]));
assert(result[2].equal([ 8 ]));
Not: Arama sırasında atılan adımları belirleyen enum 'u da incelemek
isteyebilirsiniz:
// From std.range:
enum SearchPolicy {
linear, trot, gallop, binarySearch, trotBackwards, gallopBackwards
}
http://ddili.org
13 / 26
Konu: Örtüşen dilimlerden yalnızca birisinin
kapasitesi vardır
int[] a = new int[8];
int[] b = a[0 .. $/2];
int[] c = b[0 .. $/2];
Yukarıdaki kod çalışma zamanına (druntime) ait olan bir dizi ve onun
elemanlarına erişim sağlayan üç dilim üretir:
0
1
2
3
4
5
6
7
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
ek kapasite
|
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|<------------- a ------------->|
|<----- b ----->|
|<- c ->|
Eleman ezmek yasaktır; ek kapasiteyi yalnızca a kullanabilir:
assert(a.capacity != 0);
assert(b.capacity == 0);
assert(c.capacity == 0);
a ~= 42;
b ~= 43;
c ~= 44;
http://ddili.org
// örneğin, 15
// hızlıdır; ek kapasiteyi kullanır
// yeni bellek ayırır ve elemanları oraya kopyalar
// yeni bellek ayırır ve elemanları oraya kopyalar
14 / 26
Sorun: Kapasiteyi kaybetmek fazla kolaydır
int[] makeArray()
{
int[] geçici = new int[8];
// ...
}
int[] sonuç = geçici[0 .. $/2];
return sonuç;
// kapasite 'geçici' ile birlikte kaybedilir
void main()
{
int[] a = makeArray();
}
http://ddili.org
assert(a.capacity == 0);
// Üzücü. :(
15 / 26
Çözüm: assumeSafeAppend
("eklemenin güvenli olduğunu varsay")
int[] makeArray()
{
int[] geçici = new int[8];
// ...
}
int[] result = geçici[0 .. $/2];
return result.assumeSafeAppend; // kapasite 'sonuç'a aktarılır
void main()
{
int[] a = makeArray();
}
assert(a.capacity != 0);
// Yaşasın! :)
Not: std.array.array 'in ürettiği dilimin durumu:
import std.range : iota;
import std.array : array;
auto arr = iota(10).array;
// belleği GC.malloc ile ayırır
assert(arr.capacity == 0);
// Üzücü. :(
monarch_dodra'nın söylediğine göre, bu durum yeni eklenen druntime
işlevi _d_newarrayU() ile yakında çözülecek.
http://ddili.org
16 / 26
Konu: Değişebilen verinin değişmez olarak
kullanılamaması
Tür sistemi iş başında:
void değişmezVeriGerektiren(immutable(int)[] arr)
{
// ...
}
void main()
{
int[] arr;
arr ~= 42;
değişmezVeriGerektiren(arr);
}
// ← derleme HATASI
Oysa, arr 'ın elemanlarının bir daha hiç değişmeyeceklerinin
bilindiğini düşünün. Öyleyse, immutable olarak geçirilmesinde bir
sakınca olmamalıdır.
http://ddili.org
17 / 26
Yetersiz çözümler: Kopyalama veya tür dönüşümü
Kopyalamak yavaştır:
import std.conv : to;
değişmezVeriGerektiren(arr.to!(immutable(int)[])); // kopyalar! :(
Tür dönüşümü denetlenemez:
değişmezVeriGerektiren(cast(immutable(int)[])arr);
arr[0] = 43;
http://ddili.org
// Değişmezlik garantisi ihlal edilmiştir! :(
18 / 26
Çözümler: assumeUnique
("tek olduğunu varsay") ve pure
import std.exception : assumeUnique;
immutable(int)[] imm = arr.assumeUnique;
değişmezVeriGerektiren(imm);
arr[0] = 43;
// 'arr' null olur
// Çalışma zamanı hatası. Yaşasın! :)
// (Aslında tam çözüm değildir çünkü elemanlar başka referanslar
// yoluyla yine de değiştirebilirler.)
Daha iyi çözüm: tek olduğunu varsaymak yerine, "tek olarak üretmek".
pure işlevlerin dönüş değerleri otomatik olarak immutable 'a dönüşür:
int[] diziÜret() pure
{
int[] arr;
arr ~= 42;
return arr;
}
değişmezVeriGerektiren(diziÜret());
http://ddili.org
19 / 26
Konu: nothrow olarak tanımlanmış olan bir işlevin
hata atabilen bir işlevi çağıramaması
void bar(int i)
{
import std.exception : enforce;
enforce(i < 10);
}
// hata atabilir
// ...
void foo() nothrow
{
bar(7);
// ← derleme HATASI
}
Ancak, bar(7) çağrısının hata atmayacağı açıktır.
http://ddili.org
20 / 26
Sorun: Hatayı her durumda tek tek susturmak
külfetlidir
void foo() nothrow
{
try {
bar(7);
} catch (Exception) {
// Susturduk ama şimdi ne olacak?
}
}
// ...
Peki ya bar(7) kod değişiklikleri sonucunda hata atmaya başlasa? O
yüzden aşağıdaki güvenlidir:
class VarsayımHatası : Error
{
this(string mesaj) { super(mesaj); }
}
void foo() nothrow
{
try {
bar(7);
} catch (Exception) {
throw new VarsayımHatası("Şaşırtıcı: Hata atıldı!");
}
}
http://ddili.org
// ...
21 / 26
Çözüm: assumeWontThrow
("hata atmayacağını varsay")
void foo() nothrow
{
import std.exception : assumeWontThrow;
assumeWontThrow(bar(7));
}
// ...
Not: assumeWontThrow UFCS kullanımında yanıltıcıdır.
bar(7).assumeWontThrow;
// İşlem sırası ne?
bar(7) , assumeWontThrow 'dan önce işletilmez çünkü
assumeWontThrow 'un parametresi lazy (tembel olarak işletilen) bir
ifadedir.
http://ddili.org
22 / 26
Konu: pure bir işlevin saf olmayan bir işlevi
çağıramaması
void bar()
{
// ...
}
void foo() pure
{
bar();
// ← derleme HATASI
}
Ancak, bar() işlemleri açısından aslında saf olduğu halde çeşitli
nedenlerle pure olarak tanımlanmamış olabilir.
http://ddili.org
23 / 26
Sorun: Bir işlev tür dönüşümü ile nasıl pure olarak
kullanılabilir?
void foo() pure
{
auto barPure = cast(pure)bar;
barPure();
}
http://ddili.org
// ← derleme HATASI
24 / 26
Çözüm: assumePure
("saf olduğunu varsay")
void foo() pure
{
auto barPure = assumePure(&bar);
barPure();
}
Aşağıdaki işlevi std.traits.SetFunctionAttributes işlevinin
olasılıkla David Nadlinger tarafından yazılmış olan açıklamalarından
kopyalıyorum:
import std.traits;
auto assumePure(T)(T t)
if (isFunctionPointer!T || isDelegate!T)
{
enum attrs = functionAttributes!T | FunctionAttribute.pure_;
return cast(SetFunctionAttributes!(T, functionLinkage!T, attrs))t;
}
http://ddili.org
25 / 26
Özet
Phobos'taki resmileştirilmiş varsayımlar:
• assumeSorted , O(lg N) karmaşıklıkta arama sunar
• assumeSafeAppend , dilimin kapasitesini aktarır
• assumeUnique , immutable 'a yarı-güvenli tür dönüşümü sağlar
• assumeWontThrow , nothrow 'un hata atanı çağırmasını sağlar
• assumePure , pure 'un saf olmayanı çağırmasını sağlar
Ek olarak, Dmitry Olshansky tarafından yazılmış olan std.uni
modülündeki özel bir işlev:
• assumeSize ("genişlik varsay") dönüş değerinin belirtilen sayıdaki
bite sığacağını varsayar
http://ddili.org
26 / 26