Permalink
Reply
Daha önce InputRange olarak kullanılabilen bir deneme yazmıştım:
http://ddili.org/forum/post/3045
Şimdi bunun tersini yapmak istiyorum: InputRange ile çalışan (bir anlamda onu gerektiren) bir algoritma yazmak...
Örnek algoritma bulmak zor. :/ Aklıma gelen yine garip oldu: asıl elemanlar nasıl olursa olsun, her elemanın belirli sayıda tekrarlandığı bir dizi döndürmek isteyelim.
Örneğin giriş [ 0, 1, 1, 1, 2, 0 ] olsa ve her elemanın iki kere tekrarlanması istense, çıkış şöyle olsun: [ 0, 0, 1, 1, 2, 2, 0, 0 ]. Aynı değer daha sonradan tekrar görülebilir; amaç, yan yana belirli sayıda tekrarlanmış olmaları. Ayrıca baştan 3 kere tekrarlanan 1'in de artık nasıl iki kere tekrarlandığına dikkat edin.
(Sonradan ek: Bu ilginç bir hikaye oldu; çünkü sonunda algoritma yazmaktan vazgeçtim ve InputRange'den dönüşüm sağlayan yeni bir InputRange'de karar kıldım.)
Bu algoritmayı belirli bir veri yapısı üzerinde çalışacak şekilde yazabiliriz. Örneğin şimdilik int türüne bağlı kalırsak, parametresini dizi olarak belirleyebiliriz:
import std.stdio;
/* Elemanların hepsinin de 'tekrarSayısı' kadar tekrarlanmış olduğu bir dizi
* döndürür */
int[] denkTekrarlı(const(int)[] elemanlar, int tekrarSayısı)
{
int[] sonuç;
for (int i; i != elemanlar.length; ++i) {
if ((sonuç.length == 0) || (elemanlar[i] != sonuç[$ - 1])) {
foreach (tekrar; 0 .. tekrarSayısı) {
sonuç ~= elemanlar[i];
}
}
}
return sonuç;
}
void main()
{
int[] sayılar = [ 0, 1, 1, 1, 2, 0 ];
writeln(denkTekrarlı(sayılar, 2));
}
Çıktısı istediğimiz gibi olur:
'[0, 0, 1, 1, 2, 2, 0, 0]'
(Not: Dıştaki for yerine foreach de kullanabiliriz; aralıklar üzerine konuşabilmek için şimdilik for kullanıyorum; daha aşağıda değiştireceğim.)
Ama algoritmada 'elemanlar.length' ve 'elemanlar[ i ]' demiş olduğumuz için kendimizi gereksiz yere dizilerle (veya length ve [] işlecini tanımlayan başka türlerle) kısıtlamış oluyoruz.
Oysa algoritmamız aslında bağlı listelerle bile çalışabilecek bir algoritmadır: başından sonuna kadar ilerlemek dışında bir erişim gerektirmiyor. Yani dizilerin bir özelliği olan indeksle rasgele erişime aslında ihtiyacımız yok.
Biraz dikkatli düşünürsek, algoritmamızın gerektirdiği şeyin bir "giriş aralığı" olduğunu görürüz. Andrei Alexandrescu'nun aralıkları yaymada kullandığı tutar taraf da budur: algortimalar belirli veri yapılarına değil, veriye belirli şekillerde erişime bağlıdırlar. O yüzden "aralıklar iyidir, erişiciler kötüdür". (Ben o makalesini çevirmemiş miydim? Hayır, çevirmemişim. :( Elim aralıklara iyice alışınca çeviririm.)
Bu algoritmayı InputRange ile çalışacak şekilde çok kolay olarak değiştirebiliriz:
-
'i != elemanlar.length' koşulu yerine '!elemanlar.empty'
-
'++i' yerine 'elemanlar.popFront()'; çünkü zaten asıl algoritmada da baştaki elemanları geride bırakıyoruz; onlarla işimiz bitiyor
-
'elemanlar[ i ]' yerine 'elemanlar.front'; çünkü aralık daraldıkça baştaki eleman hep şimdiki eleman olur
import std.range;
int[] denkTekrarlı(Aralık)(Aralık elemanlar, int tekrarSayısı)
if (isInputRange!Aralık)
{
int[] sonuç;
for (int i; !elemanlar.empty; elemanlar.popFront) {
if ((sonuç.length == 0) || (elemanlar.front != sonuç[$ - 1])) {
foreach (tekrar; 0 .. tekrarSayısı) {
sonuç ~= elemanlar.front;
}
}
}
return sonuç;
}
Baştan bilerek yapmadığımı da şimdi yapacağım ve artık for yerine foreach kullanacağım:
int[] denkTekrarlı(Aralık)(Aralık elemanlar, int tekrarSayısı)
if (isInputRange!Aralık)
{
int[] sonuç;
foreach (eleman; elemanlar) {
if ((sonuç.length == 0) || (eleman != sonuç[$ - 1])) {
foreach (tekrar; 0 .. tekrarSayısı) {
sonuç ~= eleman;
}
}
}
return sonuç;
}
O işlevde gereksiz başka bir kısıtlama daha var: herhangi türde bir InputRange alabildiği halde dönüş türü olarak açıkça int[] yazıyor. OutputRange konusunda çok kısaca bahsettiğim ElementType'tan yararlanırsak, Aralık ne türden olursa olsun, o aralığın eleman türünde bir dizi döndürebiliriz:
ElementType!Aralık[] denkTekrarlı(Aralık)(Aralık elemanlar, int tekrarSayısı)
if (isInputRange!Aralık)
{
ElementType!Aralık[] sonuç;
foreach (eleman; elemanlar) {
if ((sonuç.length == 0) || (eleman != sonuç[$ - 1])) {
foreach (tekrar; 0 .. tekrarSayısı) {
sonuç ~= eleman;
}
}
}
return sonuç;
}
Artık çok daha kullanışlıdır çünkü örneğin bir string dizisiyle bile çalışabilir:
writeln(denkTekrarlı([ "ali", "veli", "veli" ], 4));
Çıktısı:
'[ali, ali, ali, ali, veli, veli, veli, veli]'
Bir işimiz daha kaldı: Elemanlardan oluşan bir dizi döndürmek yerine, ürettiğimiz sonuçları 'put' ile yerleştirebileceğimiz bir çıkış aralığı kullanabiliriz. Böylece bu algoritmayı kullananlar istedikleri giriş aralığını istedikleri çıkış aralığına bağlayabilirler.
Kullanıcıların o çıkış aralığını da parametre olarak geçirmeleri gerekir:
import std.stdio;
import std.range;
void denkTekrarlı(Aralık, Çıkış)(Aralık elemanlar,
Çıkış çıkış,
int tekrarSayısı)
if (isInputRange!Aralık)
{
ElementType!Aralık sonEklenen;
foreach (i, eleman; elemanlar) {
if ((i == 0) || (eleman != sonEklenen)) {
foreach (tekrar; 0 .. tekrarSayısı) {
çıkış.put(eleman);
}
sonEklenen = eleman;
}
}
}
void main()
{
int[] sayılar = [ 0, 1, 1, 1, 2, 0 ];
int[] sonuç;
denkTekrarlı(sayılar, appender(&sonuç), 2);
writeln("sonuç: ", sonuç);
string[] sonuç2;
denkTekrarlı([ "ali", "veli", "veli" ], appender(&sonuç2), 4);
writeln("sonuç2: ", sonuç2);
}
O programda 'appender' diye bir işlev kullandım. appender, kendisine verilen dizinin sonuna eleman ekleyen bir OutputRange gibi çalışır.
Doğrusu, şablon kısıtlamalarına Çıkış'ın bir OutputRange olması gerektiğini de eklemek isterdim ama derleme hatasına neden oluyor:
void denkTekrarlı(Aralık, Çıkış)(Aralık elemanlar,
Çıkış çıkış,
int tekrarSayısı)
if (isInputRange!Aralık &&
isOutputRange!Çıkış) // <--- DERLEME HATASI
Ama o hatanın benden kaynaklandığını sanmıyorum. (?)
Çıktılar yine istediğimiz gibi:
'sonuç: [0, 0, 1, 1, 2, 2, 0, 0]
sonuç2: [ali, ali, ali, ali, veli, veli, veli, veli]
'
Daha bitmedi... :D Ulaştığımız sonucun neler getirdiğine bir bakalım...
Ama devam etmeden önce, std.range'deki 'take' işlevini hatırlatacağım: take, belirli bir aralıktan belirli sayıda eleman çeken Take isminde bir aralık döndürür. Yani 'take' bir işlevdir, 'Take' bir aralıktır. take, Take döndürür; biz de o Take'i bir InputRange gibi kullanabiliriz.
İşin güzeli, bu işlem tembel bir şekilde gerçekleştirilir. Biz bu aralığı ancak gerektikçe, front ve popFront işlevleri ile kullanabiliriz. Aşağıdaki writeln da öyle yapıyor:
int[] sonuç;
denkTekrarlı([ 0, 1, 1, 1, 2, 0 ], appender(&sonuç), 2);
writeln(take(sonuç, 3));
take, sonuç'un baş tarafındaki 3 elemanı üretir ve program şu çıktıyı verir:
'[0, 0, 1]'
Özetlersek: Başlangıçta elimizde [ 0, 1, 1, 1, 2, 0 ] dizisi var. O diziyi denkTekrarlı'ya vererek sonuçta [0, 0, 1, 1, 2, 2, 0, 0] üretiyoruz. Ondan sonra, o sonucu take'e vererek en baştaki 3 elemanı elde ediyoruz.
Ne kadar yararlı olsa da bunun iki sakıncası var:
-
(bu çok önemli değil) 'sonuç' ismindeki diziyi yalnızca take'e göndermek için oluşturuyoruz; belki de bir daha kullanmayacağımız halde sırf parametre olabilsin diye tanımlamak zorunda kalıyoruz
-
çok daha önemli olarak, yazmış olduğumuz denkTekrarlı, hevesli bir algoritmadır: kendisine verilen bütün aralığı sonuna kadar kullanır. Bu, bu küçük örnekte hiç de sorun değildir. Ama asıl aralıkta çok fazla sayıda eleman bulunduğunu düşünün... Hatta, asıl aralığın sonsuz olduğunu düşünün! Algoritmamızı o şekilde tanımlasak, program sonsuz bir aralıkla karşılaştığında bilgisayarın belleğini tüketerek çökerdi.
Bu yüzden, take'ten ders almalıyız ve belki de tembel şekilde işleyen bir InputRange döndürmeliyiz. Yeni yazacağımız InputRange, asıl aralığı ancak gerektikçe kullanacak:
/**
* Bu sınıf, kendisine verilen aralıktaki elemanların belirtilen sayıda art
* arda tekrarlandığı bir giriş aralığıdır.
*
* Örneğin aralık olarak
*
* [ 0, 1, 1, 1, 2, 0 ] ve tekrar sayısı olarak 3
*
* verildiğinde, kendisi şu elemanları üreten bir giriş aralığı (InputRange)
* olarak işler:
*
* [ 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0 ]
*/
class DenkTekrarlayan(Aralık)
if (isInputRange!Aralık)
{
Aralık asılAralık;
int tekrarSayısı;
int sayaç;
/* Tekrar sayısı kere bunu döndüreceğiz */
ElementType!Aralık şimdikiEleman;
this(Aralık asılAralık, int tekrarSayısı)
{
this.asılAralık = asılAralık;
this.tekrarSayısı = tekrarSayısı;
this.sayaç = 0;
if (!asılAralık.empty) {
şimdikiEleman = this.asılAralık.front;
}
}
@property bool empty() const
{
return asılAralık.empty;
}
@property ElementType!Aralık front() const
{
return şimdikiEleman;
}
void popFront()
{
++sayaç;
if (sayaç == tekrarSayısı) {
/* Tekrarlarımızı tamamladık; asıl aralıktaki bir sonraki elemana
* geçmemiz gerekiyor */
while (!asılAralık.empty && (asılAralık.front == şimdikiEleman)) {
asılAralık.popFront();
}
if (!asılAralık.empty) {
şimdikiEleman = asılAralık.front;
}
sayaç = 0;
}
}
}
denkTekrarlı diye bir işlev yerine DenkTekrarlayan diye bir sınıf yazmış olduk. Bu sınıfın aralığı ilerletme kavramı popFront işlevinde hallediliyor.
Aslında denkTekrarlı işlevimizden de vazgeçmiş değiliz. Ona güzel bir görev vereceğiz: onun görevi, DenkTekrarlayan'ı doğru şablon parametresiyle oluşturmak ve kullanıcı kodunun yazımını temiz bırakmaktır:
DenkTekrarlayan!Aralık denkTekrarlı(Aralık)(Aralık elemanlar,
int tekrarSayısı)
if (isInputRange!Aralık)
{
return new DenkTekrarlayan!Aralık(elemanlar, tekrarSayısı);
}
Böylece 'new'ün çağrılması ve şablon parametresinin DenkTekrarlayan!Aralık diye açıkça belirtilmesi bu işlevin içine gizlenmiş olur.
Hatırlarsanız, işlev şablon parametrelerinin türleri işlevin kullanımından otomatik olarak çıkarsanabilir. Böyle bir olanak sınıf şablonlarında yoktur. denkTekrarlı, kolayca DenkTekrarlayan nesneleri oluşturmaya yarar (Bu, C++'da da yararlanılan bir yöntemdir):
writeln(denkTekrarlı([ 0, 1, 1, 1, 2, 0 ], 2));
Çıktısı öncekilerle aynı:
'[0, 0, 1, 1, 2, 2, 0, 0]'
Nasıl çalıştığına bakalım:
-
denkTekrarlı'ya bir aralık ve tekrar sayısı veriyoruz
-
denkTekrarlı, onları kullanarak bir DenkTekrarlayan nesnesi oluşturuyor ve hemen döndürüyor; önemli olarak, kendisi bundan başka iş yapmıyor
-
writeln, aralıkları tanıdığı için kendisine verilen DenkTekrarlayan nesnesini bir InputRange gibi art arda kullanarak değerleri elde ediyor ve çıkışa yazdırıyor
Bu durumun öncekinden farkına dikkat edin: denkTekrarlı artık tembel, çünkü kendisi yalnızca bir nesne döndürmektedir; DenkTekrarlayan nesnesi de tembel, çünkü kendisi hemen iş yapmamaktadır, işini popFront çağrıldıkça halletmektedir.
Bunun sonucunda lego parçaları gibi Phobos'un algoritmalarına takılabilen bir olanak edinmiş oluyoruz. Örnek:
writeln(take(denkTekrarlı([ 0, 1, 1, 1, 2, 0 ], 2), 3));
O kodun anlamı: verilen aralıktaki her elemanı 2 kere tekrarla, ve oluşan aralığın başındaki 3 elemanı al. Çıktısı:
'[0, 0, 1]'
Lego parçası gibi olabilmesi için take ile denkTekrarlı'nın sırasını değiştirebilmeliyiz:
writeln(denkTekrarlı(take([ 3, 1, 4, 1, 5 ], 4), 5));
Anlamı: verilen aralığın başındaki 4 elemanı al ve onların her birisini 5 kere tekrarlayan bir aralık üret. Çıktısı:
'[3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1]'
Lezzetli, değil mi? :)
Tembel olmasının getirdiği bir yarar, artık bu aralığı sonu gelmeyen aralıklarla da kullanabilmektir. Hiç sonu gelmeyen çok basit bir aralığımız olsun:
class SonsuzaKadarSayan
{
int sayaç;
static immutable bool empty = false;
@property int front() const
{
return sayaç;
}
void popFront()
{
++sayaç;
}
}
Bu InputRange'in empty niteliğinin bir işlev olmadığına, ama derleme zamanında bilinen bir sabit olduğuna dikkat edin. Phobos öyle tanımları da kabul ediyor; önemli olan, 'empty'nin değeridir... Yanına bir de yukarıdaki gibi bir kolaylık işlevi ekleyelim:
SonsuzaKadarSayan sonsuzSayaç()
{
return new SonsuzaKadarSayan;
}
Önemli olan, o giriş akımının 'empty'sinin hep 'false' değerinde olması, yani bu aralığın sonunun bulunmamasıdır. İsterseniz deneyin: :)
foreach (i; sonsuzSayaç()) {
write(i, ' ');
}
Çıktısı hiç durmaz:
'0 1 2 3 4 5 6 7 8 9 10 11 12 13 ... (sonsuza kadar) ...'
Buna rağmen, tanımladığımız DenkTekrarlayan'ı böyle bir aralıkla bile kullanabiliriz:
writeln(take(denkTekrarlı(sonsuzSayaç, 4), 10));
Anlamı: sonsuz sayacın ürettiği elemanları art arda 4 kere olacak şekilde tekrarla, ve onların başındaki 10 elemanı al. Çıktısı:
'[0, 0, 0, 0, 1, 1, 1, 1, 2, 2]'
Yaşasın tembellik! :p
Programın son hali:
import std.stdio;
import std.range;
/**
* Bu sınıf, kendisine verilen aralıktaki elemanların belirtilen sayıda art
* arda tekrarlandığı bir giriş aralığı döndürür.
*
* Örneğin aralık olarak
*
* [ 0, 1, 1, 1, 2, 0 ] ve tekrar sayısı olarak 3
*
* verildiğinde, kendisi şu elemanları üreten bir giriş aralığı (InputRange)
* olarak işler:
*
* [ 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0 ]
*/
class DenkTekrarlayan(Aralık)
if (isInputRange!Aralık)
{
Aralık asılAralık;
int tekrarSayısı;
int sayaç;
/* Tekrar sayısı kere bunu döndüreceğiz */
ElementType!Aralık şimdikiEleman;
this(Aralık asılAralık, int tekrarSayısı)
{
this.asılAralık = asılAralık;
this.tekrarSayısı = tekrarSayısı;
this.sayaç = 0;
if (!asılAralık.empty) {
şimdikiEleman = this.asılAralık.front;
}
}
@property bool empty() const
{
return asılAralık.empty;
}
@property ElementType!Aralık front() const
{
return şimdikiEleman;
}
void popFront()
{
++sayaç;
if (sayaç == tekrarSayısı) {
/* Tekrarlarımızı tamamladık; asıl aralıktaki bir sonraki elemana
* geçmemiz gerekiyor */
while (!asılAralık.empty && (asılAralık.front == şimdikiEleman)) {
asılAralık.popFront();
}
if (!asılAralık.empty) {
şimdikiEleman = asılAralık.front;
}
sayaç = 0;
}
}
}
/* Bir kolaylık işlevi */
DenkTekrarlayan!Aralık denkTekrarlı(Aralık)(Aralık elemanlar, int tekrarSayısı)
if (isInputRange!Aralık)
{
return new DenkTekrarlayan!Aralık(elemanlar, tekrarSayısı);
}
/**
* Artan değerler üreten ve hiç sonu gelmeyen bir giriş aralığı
*/
class SonsuzaKadarSayan
{
int sayaç;
static immutable bool empty = false;
@property int front() const
{
return sayaç;
}
void popFront()
{
++sayaç;
}
}
/* Bir kolaylık işlevi */
SonsuzaKadarSayan sonsuzSayaç()
{
return new SonsuzaKadarSayan;
}
void main()
{
writeln(`"Elemanları ikişer kere tekrarla"`);
writeln(denkTekrarlı([ 0, 1, 1, 1, 2, 0 ], 2));
writeln(`"Elemanları ikişer kere tekrarla, ve baştaki üç tanesini seç"`);
writeln(take(denkTekrarlı([ 0, 1, 1, 1, 2, 0 ], 2), 3));
writeln(`"Baştaki dört tanesini seç, ve beşer kere tekrarla"`);
writeln(denkTekrarlı(take([ 3, 1, 4, 1, 5 ], 4), 5));
writeln(`"Sonsuza kadar artan değerler üret, her birisini dörder kere`
` tekrarla, ve baştaki on tanesini seç"`);
writeln(take(denkTekrarlı(sonsuzSayaç, 4), 10));
}
Çıktısı:
'"Elemanları ikişer kere tekrarla"
[0, 0, 1, 1, 2, 2, 0, 0]
"Elemanları ikişer kere tekrarla, ve baştaki üç tanesini seç"
[0, 0, 1]
"Baştaki dört tanesini seç, ve beşer kere tekrarla"
[3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1]
"Sonsuza kadar artan değerler üret, her birisini dörder kere tekrarla, ve baştaki on tanesini seç"
[0, 0, 0, 0, 1, 1, 1, 1, 2, 2]
'
Devamı gelecek... :p
Ali
--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]