Bölüm 5: Polinomlar ve Seyrek Matrisler

5.1Polinom soyut veri tipi

Polinom, lise matematiğinden tanıdık bir nesnedir. Bilgisayarda da sık karşımıza çıkar: hata denetim kodları, şifreleme, eğri uydurma ve sayısal integral polinomlarla çalışır. Bu nesneyi bir programda kullanmak için önce onunla yapılacak işlemleri, sonra bu işlemleri hızlı yapan bellek düzenini belirlemek gerekir. Birinci adım bir soyut veri tipi (abstract data type, ADT) tanımıdır. Soyut veri tipi, bir veri türünün değerlerini ve bu değerler üzerindeki işlemleri anlatır, ama bellekte nasıl tutulacağını söylemez. Bellek düzeni ikinci adımda, gerçeklemede seçilir.

5.1.1Polinom, terim ve derece

Tanımdaki küme bakışı önemlidir. A(x) = 3x²⁰ + 2x⁵ + 4 polinomu {⟨20, 3⟩, ⟨5, 2⟩, ⟨0, 4⟩} kümesidir. Sıfır katsayılı terimler kümeye girmez: x¹⁹'dan x⁶'ya kadar bütün terimlerin katsayısı sıfırdır ve hiçbiri yazılmaz. Polinomun derecesi 20'dir. Sabit terim 4 = 4x⁰ olduğundan üssü 0'dır. Hiç terimi olmayan polinom sıfır polinomudur; boş kümeye karşılık gelir.

Aynı üssün iki kez geçmemesi kuralı, toplama ve çarpma kodlarının da temel koşuludur. 2x³ + 5x³ gibi bir yazım kümeye uygun değildir; bu iki terim tek bir 7x³ terimine indirgenmelidir. Çarpım kodunun en çok uğraştığı iş bu indirgemedir.

5.1.2İşlemler

Horowitz ve arkadaşlarının ders kitabı, polinom soyut veri tipini Tablo 5.1'deki işlemlerle tanımlar. İşlemlerin adları kitaptaki İngilizce adlardır; anlamları Türkçe verilmiştir.

Bu liste, polinomla yapılacak her işi kapsar. Add ve Mult öteki işlemlerle yazılabilir. Toplama, iki polinomun en büyük üslerini LeadExp ile karşılaştırıp uygun terimi Attach ile sonuca ekleyerek ilerler. Çarpma, birinci polinomun her terimi için SingleMult çağırıp ara sonuçları toplar. Soyut veri tipinin yararı burada görülür. Toplama algoritması, polinomun bellekte dizi mi bağlı liste mi olduğunu bilmeden yazılabilir. Gerçeklemeyi değiştiren programcı yalnız bu işlemleri yeniden yazar.

5.1.3Toplama ve çarpma kuralları

Toplamada aynı üslü terimlerin katsayıları toplanır:

A(x) + B(x) = Σ (a_i + b_i) · xⁱ

Bir üs yalnız bir polinomda varsa, öteki polinomun o üsteki katsayısı 0 sayılır ve terim olduğu gibi sonuca geçer. İki katsayının toplamı 0 ise terim sonuçtan düşer. Örneğin (4x³ + 2x² + 5) + (3x³ − 2x² + x) = 7x³ + x + 5'tir; x² terimleri birbirini götürür.

Çarpmada her terim öteki polinomun her terimiyle çarpılır. İki terimin çarpımında üsler toplanır, katsayılar çarpılır: a_ixⁱ · b_jx^j = a_ib_j x^i+j.

A(x) · B(x) = Σ_i ( a_ixⁱ · Σ_j b_jx^j )

n terimli bir polinom m terimli bir polinomla çarpılınca n · m çarpım oluşur. Bu çarpımların bazılarının üssü aynı çıkabilir. (x + 1)(x − 1) çarpımında dört terim oluşur: x², −x, x ve −1. Ortadaki iki terimin üssü 1'dir; toplamları 0 olduğundan ikisi de kaybolur ve sonuç x² − 1 olur. Çarpım kodunun asıl zorluğu, aynı üslü terimleri bulup birleştirmek ve sıfırlananları atmaktır.

5.2Polinomu dizide tutmak

C'de polinomu tutmanın en kolay yolu bir dizidir. Ama dizinin neyi tutacağı konusunda iki farklı seçim vardır: her üs için bir hücre ayırmak ya da yalnız var olan terimleri yazmak. Bu iki seçim, aynı polinom için çok farklı bellek ve zaman maliyetleri doğurur.

5.2.1Birinci yöntem: katsayı dizisi

Birinci yöntem bütün katsayıları üsse göre dizinlenmiş bir dizide tutar. coef[i], xⁱ'nin katsayısıdır:

#define MAX_DEGREE 101   /* azami derece + 1 */
typedef struct {
  int degree;               /* en büyük üs */
  float coef[MAX_DEGREE];   /* coef[i]: x^i katsayısı */
} polynomial;
polynomial P;

MAX_DEGREE makrosu en büyük derecenin bir fazlasıdır; 101 hücreli dizi 0'dan 100'e kadar üsleri tutar. Yapının degree alanı, katsayısı sıfırdan farklı en büyük üssü saklar. Bu alan sayesinde derece her istendiğinde dizi sondan taranmaz. Yapı tanımı typedef ile polynomial adını alır; polynomial P; satırı bu türden bir değişken bildirir.

Bu gösterimde işlemler çok basittir. Coef(p, e) doğrudan p.coef[e]'dir ve O(1) sürer. LeadExp(p), p.degree'dir. Toplama, iki dizinin aynı indisli hücrelerini toplar. Bu notta katsayı dizisiyle toplamayı gösteren kısa bir fonksiyon yazılmıştır:

/* katsayı dizisiyle toplama: d = a + b */
void dizi_topla(const polynomial *a, const polynomial *b,
                polynomial *d) {
  int i, n = a->degree > b->degree ? a->degree : b->degree;
  for (i = 0; i <= n; i++) {
    float x = i <= a->degree ? a->coef[i] : 0;
    float y = i <= b->degree ? b->coef[i] : 0;
    d->coef[i] = x + y;
  }
  d->degree = n;
  while (d->degree > 0 && d->coef[d->degree] == 0)
    d->degree--;                /* baştaki sıfırları at */
}

Fonksiyon iki polinomun büyük derecesine kadar döner. Bir polinomun derecesi aşılmışsa o polinomun katsayısı 0 alınır. Toplamın derecesi önce n kabul edilir; sonra baştaki sıfırlar atılır. (2x³ + 1) + (−2x³ + x + 4) toplamında x³ katsayısı 0 çıkar ve son döngü dereceyi 3'ten 1'e indirir; sonuç x + 5'tir. Zaman maliyeti iki polinomun derecesinin büyüğüyle orantılıdır: O(max(deg A, deg B)).

Sorun bellektedir. Katsayısı 0 olan terimler de tutulur. P(x) = 5x¹⁰⁰ polinomunun tek terimi vardır, ama dizi 101 hücre ayırır ve coef[0..99] hücrelerinin hepsi 0'dır (Şekil 5.1). Bir float 4 bayt olduğundan bu yapı, degree alanıyla birlikte 408 bayt kaplar. Anlamlı bilgi yalnız iki sayıdır: üs 100 ve katsayı 5. Toplama da aynı israfı zamana taşır: iki tek terimli polinomu toplamak için 101 hücre dolaşılır.

Katsayı dizisinin bir sınırı daha vardır. Derece MAX_DEGREE − 1'i aşamaz. x¹⁰⁰⁰ terimli bir polinom için dizi bin bir hücreli olmalıdır; bu durumda bütün polinomlar, tek terimli olsalar bile, dört kilobayt yer kaplar. Seyrek polinom, yani terimlerinin çoğunun katsayısı 0 olan polinom için bu yöntem uygun değildir. Katsayıların çoğu doluysa, örneğin x⁴ + 3x³ − x² + 2x + 7 gibi bir polinomda, katsayı dizisi hem sade hem hızlıdır.

5.2.2İkinci yöntem: terim dizisi

İkinci yöntem yalnız sıfırdan farklı terimleri saklar. Her terim bir katsayı ve bir üs çiftidir. Bütün polinomların terimleri tek bir ortak dizide durur:

#define MAX_TERMS 101   /* azami terim sayısı */
typedef struct {
  float coef;            /* katsayı */
  int expon;             /* üs */
} polynomial;
polynomial P[MAX_TERMS]; /* tüm polinomlar burada */
int avail = 0;           /* ilk boş konum */

Yapının adı yine polynomial'dır, ama artık tek bir terimi temsil eder: coef katsayıyı, expon üssü tutar. P dizisi programdaki bütün polinomların terimlerini barındırır. avail değişkeni dizideki ilk boş konumu gösterir; yeni bir terim her zaman P[avail]'e yazılır ve avail bir artar.

Bir polinom, P içinde ardışık bir aralıktır. Polinomu bulmak için iki indis yeter: ilk teriminin indisi start ve son teriminin indisi finish. Terimler büyük üsten küçüğe sıralı tutulur. Bu sıra, toplama algoritmasının hızlı çalışmasının anahtarıdır. Şekil 5.2, A(x) = 3x²⁰ + 2x⁵ + 4 ve B(x) = x⁵ + 10x³ + 3x² + 1 polinomlarının ortak dizideki yerini gösterir.

Bu gösterimde 5x¹⁰⁰ polinomu tek bir hücre kaplar: ⟨5, 100⟩. Bir terim float katsayı ile int üsten oluşur ve 8 bayttır. Katsayı dizisinin 408 baytı yerine 8 bayt yeter. Derecenin bir üst sınırı da kalmaz; üs int'e sığdığı sürece her değeri alabilir. Sınırlı olan, bütün polinomların toplam terim sayısıdır: MAX_TERMS = 101.

Sıralı terimlerin değerini bir benzetme açıklar. Alfabetik sıralı iki öğrenci listesini tek bir sıralı listeye dönüştürmek için iki listenin başından aynı anda yürümek yeter. Her adımda iki başın önce geleni yeni listeye yazılır. Listeler sırasız olsaydı her isim için öteki listenin tamamını taramak gerekirdi. Bu iki işaretçili yürüyüşe birleştirme (merge) denir. Dersin hocası da aynı noktayı vurgular: birleştirme mantığı, sıralı yapılar üzerinde daha etkin algoritmalar üretmeyi sağlar. Polinom toplamanın tamamı bu fikre dayanır.

5.2.3İki gösterimin karşılaştırması

Hangi gösterimin daha iyi olduğu polinomun yapısına bağlıdır. Tablo 5.2, iki gösterimi bellek ve temel işlemler açısından karşılaştırır. Tabloda d derece, t sıfırdan farklı terim sayısıdır.

Terim dizisinde Coef yavaşlar, çünkü istenen üs dizide aranmalıdır. Ama polinom işlemlerinin çoğu, tek tek katsayıları sorgulamak yerine terimleri sırayla dolaşır. Toplama ve çarpma böyle işlemlerdir ve terim dizisinde terim sayısıyla orantılı zaman alır. 3x²⁰ + 2x⁵ + 4 polinomunun katsayı dizisi 21 hücre dolaşılarak toplanır; terim dizisinde 3 terim yeter.

5.3Polinom toplama: padd

Terim dizisi gösteriminde iki polinomu toplayan fonksiyonun adı padd'dir (polynomial add). Fonksiyon P[sa..fa]'daki A ile P[sb..fb]'deki B'yi toplar ve sonucu avail'den başlayarak P'nin boş kısmına yazar.

5.3.1İki işaretçiyle birleştirme

İki polinomun terimleri büyük üsten küçüğe sıralıdır. sa ve sb indisleri iki polinomun henüz işlenmemiş ilk terimini gösterir; Bunlara işaretçi denir. C işaretçisi değil, dizi indisidirler. Her adımda iki işaretçinin gösterdiği terimlerin üsleri karşılaştırılır. Üç durum vardır:

• Üsler eşit. Katsayılar toplanır. Toplam sıfırdan farklıysa sonuca bu üsle eklenir; sıfırsa terim kaybolur. İki işaretçi de bir ilerler.
• A'nın üssü büyük. A'daki bu üsse sahip bir terim B'de yoktur. B'nin kalan terimlerinin hepsi B'nin şu anki teriminden küçük üslüdür, şu anki terim de A'nınkinden küçüktür. Öyleyse bu üs B'nin hiçbir yerinde geçmez. A'nın terimi olduğu gibi sonuca eklenir ve yalnız A'nın işaretçisi ilerler.
• B'nin üssü büyük. Durum simetriktir: B'nin terimi eklenir, yalnız B'nin işaretçisi ilerler.

Polinomlardan birinin terimleri bitince döngü durur. Öteki polinomda kalan terimlerin üsleri, sonuca yazılmış bütün terimlerden küçüktür; bu terimler olduğu gibi sonuca kopyalanır.

İkinci durumun gerekçesi algoritmanın doğruluğunun özüdür ve yalnız sıralılık sayesinde geçerlidir. Terimler sırasız olsaydı, A'nın bir teriminin B'de karşılığı olup olmadığını anlamak için B'nin tamamını taramak gerekirdi. Sıralı dizide B'nin şu anki terimi bu soruya tek başına cevap verir.

5.3.2COMPARE ve attach

padd iki yardımcı kullanır. Birincisi üç yönlü karşılaştırma yapan bir makro, ikincisi sonuca terim ekleyen bir fonksiyondur:

#define COMPARE(x, y) \
  ((x) < (y) ? -1 : (y) < (x) ? 1 : 0)

void attach(float coef, int expon) {
  if (avail >= MAX_TERMS) {
    fprintf(stderr, "Dizi tasmasi!\n"); exit(1);
  }
  P[avail].coef = coef;
  P[avail++].expon = expon;
}
#define EK(k) attach(P[k].coef, P[k].expon)

COMPARE(x, y), x < y ise −1, x > y ise 1, eşitse 0 verir. İç içe iki koşul işleciyle yazılmıştır. Makro parametreleri her geçişte parantez içindedir, çünkü önişlemci makroyu metin olarak yerine koyar. COMPARE(a + 1, b) gibi bir çağrıda parantezler, işleç önceliğinin ifadeyi yanlış gruplamasını önler. Sonucun üç değerli olması, padd'in switch ile yazılmasını sağlar.

attach, bir terimi P[avail]'e yazar ve avail'i bir artırır. Yazmadan önce dizinin dolup dolmadığını denetler; doluysa standart hata akışına bir ileti yazıp programı sonlandırır. Bu denetim olmasaydı P[101]'e yazılırdı. Dizinin sınırı dışına yazmak C'de tanımsız davranıştır: komşu değişkenler bozulabilir ya da program çökebilir. P[avail++].expon = expon; satırı son ek artırma işlecini kullanır: önce P[avail]'in üssü yazılır, sonra avail artar.

EK(k) makrosu, P[k] terimini olduğu gibi sonuca kopyalamanın kısa yazımıdır. EK(sb), önişlemciden sonra attach(P[sb].coef, P[sb].expon) olur.

5.3.3padd() kodu

void padd(int sa,int fa,int sb,int fb,int*sd,int*fd){
  float c; *sd = avail;               /* D'nin başı */
  while (sa <= fa && sb <= fb)
    switch (COMPARE(P[sa].expon, P[sb].expon)) {
    case -1: EK(sb); sb++; break;     /* B büyük */
    case  1: EK(sa); sa++; break;     /* A büyük */
    case  0: c = P[sa].coef + P[sb].coef;
      if (c) attach(c, P[sa].expon); /* 0: ekleme */
      sa++; sb++;
    }
  for (; sa <= fa; sa++) EK(sa);      /* A'da kalan */
  for (; sb <= fb; sb++) EK(sb);      /* B'de kalan */
  *fd = avail - 1;
}

Fonksiyon altı parametre alır. İlk dördü girdi aralıklarıdır: A P[sa..fa]'da, B P[sb..fb]'de durur. Son ikisi çıktıdır: sd ve fd, sonucun başlangıç ve bitiş indislerinin yazılacağı değişkenlerin adresleridir. C'de bir fonksiyon tek değer döndürebilir. İki değer döndürmek için çağıran taraf iki değişkenin adresini verir; fonksiyon bu adreslere yazar. *sd = avail; ifadesi, çağıranın değişkenine avail'in o anki değerini koyar.

Kodun yapısı şöyledir:

1. 2. satır: Sonucun ilk terimi P[avail]'e yazılacağından *sd şimdiden belirlenir.
2. 3–10. satırlar: İki polinomda da terim kaldıkça döngü döner. switch, üslerin karşılaştırma sonucuna göre üç daldan birini seçer. case -1, B'nin üssü büyük olduğunda B'nin terimini ekler. case 1, A'nınkini ekler. case 0, katsayıları toplar; toplam 0 değilse attach çağrılır. if (c) koşulu c != 0 anlamındadır.
3. 11–12. satırlar: Döngü bitince iki polinomdan en çok birinde terim kalmıştır. İki for döngüsünden yalnız biri iş yapar; öteki koşulu baştan yanlış bulur.
4. 13. satır: Son eklenen terim P[avail − 1]'dedir; *fd bu indisi alır.

case 0 dalının sonunda break yoktur. Bu dal switch'in son dalı olduğundan kontrol zaten switch'in sonuna düşer; bir sonraki dala geçiş olmaz. Yine de son dala da break yazmak iyi bir alışkanlıktır: sonradan altına yeni bir dal eklenirse kod istemeden o dala akmaz.

5.3.4Kod izleme: A + B

A(x) = 4x³ + 2x² + 5 polinomu P[0..2]'de, B(x) = 3x³ − 2x² + x polinomu P[3..5]'te durur ve avail = 6'dır (Şekil 5.3). padd(0, 2, 3, 5, &sd, &fd) çağrısı Tablo 5.3'teki gibi ilerler.

Tabloda sa ve sb sütunları adımın başındaki değerleri, avail sütunu adımın sonundaki değeri gösterir. İlk iki turda üsler eşittir. Birincide katsayılar toplanıp 7x³ yazılır. İkincide 2x² ile −2x² birbirini götürür; c sıfır olduğu için attach çağrılmaz ve avail değişmez. Üçüncü turda A'nın kalan terimi 5x⁰, B'nin kalan terimi x¹'dir. COMPARE(0, 1) = −1 olduğu için B'nin terimi eklenir. Bu adımdan sonra B biter ve döngü koşulu yanlış olur. A'da kalan 5, ilk for döngüsüyle kopyalanır.

Sonuç D(x) = 7x³ + x + 5'tir ve P[6..8] aralığındadır: sd = 6, fd = 8. Program bu girdiyle çalıştırıldığında attach üç kez çağrılır ve avail 9 olur. Girdi polinomları yerinde kalır; padd onları değiştirmez.

5.3.5Karmaşıklık

En iyi durum, bütün üslerin ortak olduğu durumdur (n = m). Her tur case 0 dalına girer ve iki işaretçi birlikte ilerler; döngü n tur döner. Bu durumda maliyet Ω(n)'dir; n = m olduğundan bu da Θ(n + m) ile aynı derecedir. En kötü durum hiç ortak üs olmamasıdır. O zaman her terim ayrı ayrı yazılır ve n + m attach yapılır. On terimli iki polinomun toplamı bu yüzden en çok 20 attach çağrısı yapar. Bu sayı programla da doğrulanmıştır. Üsleri tek sayı olan on terimli bir polinom, üsleri çift sayı olan on terimli bir polinomla toplanınca 20 çağrı sayılır. İki eş polinom toplanınca 10 çağrı sayılır.

Terimler sırasız tutulsaydı ne olurdu? A'nın her terimi için B'de aynı üslü terim aranmalı, bulunamazsa terim sonuca uygun yere yerleştirilmeliydi. Arama terim başına O(m) sürer ve n terim için O(nm) eder. Sonucu sıralı tutmak için araya ekleme yapılırsa her ekleme dizideki terimleri kaydırır; bu da toplamda O((n + m)²) düzeyine çıkar. Hocanın deyişiyle, istenen O(n + m) ise ve daha iyisi yapılabiliyorsa ne âlâ. Ama girdinin her terimine en az bir kez bakmak gerektiğinden toplama için n + m'den hızlı bir algoritma olamaz; padd en iyi derecededir.

5.3.6Ortak dizinin bedeli

Ortak P dizisi basit bir bellek yöneticisidir: avail yalnız ileri gider. Her padd çağrısı sonucunu dizinin sonuna ekler. Bir ara sonuçla işi biten polinomun terimleri dizide kalır ve yerleri geri kazanılmaz. Uzun bir hesapta dizi bu artıklarla dolar ve attach “Dizi tasmasi!” iletisiyle programı durdurur, oysa dizideki canlı polinomların toplam boyu küçük olabilir.

Bu sorunun iki çözümü vardır. Birincisi sıkıştırmadır (compaction). Dizi dolunca hâlâ kullanılan polinomlar dizinin başına doğru kaydırılır ve başlangıç ile bitiş indisleri güncellenir. Sıkıştırma, canlı terim sayısıyla orantılı zaman alır ve bütün polinomların indislerini değiştirdiği için dikkatli yazılmalıdır. İkinci çözüm, polinomu bağlı listeyle tutmaktır. Her terim kendi düğümünde durur; işi biten düğüm free ile hemen geri verilir.

5.4Dizi gösterimiyle çarpım ve çok polinomlu işlemler

padd iki polinomu toplar. Çarpım, çok sayıda polinomun toplamı ve çarpımı da aynı dizi gösterimiyle yazılabilir. Sunumda ödev olarak verilen bu üç sorunun çözümleri aşağıda ayrıntılı olarak verilir.

5.4.1pmult(): tek terimle çarpıp toplamak

Çarpma kuralı bir algoritma önerir. A'nın her a_ix^e_i terimi için B, bu tek terimle çarpılır (SingleMult). Ortaya çıkan m terimli polinom ara sonuca padd ile eklenir. B'nin terimleri sıralı olduğundan tek terimle çarpım da sıralı bir polinom verir: her üse aynı e_i eklenir ve sıra bozulmaz. Bu notta ödevin çözümü olarak yazılan fonksiyon şöyledir:

/* A = P[sa..fa], B = P[sb..fb]; çarpım P[*sd..*fd] */
void pmult(int sa, int fa, int sb, int fb,
           int *sd, int *fd) {
  int i, j, ss = avail, sf = avail - 1;  /* boş ara sonuç */
  int ts, tf, ys, yf;
  for (i = sa; i <= fa; i++) {
    ts = avail;                      /* B · a_i x^e_i */
    for (j = sb; j <= fb; j++)
      attach(P[i].coef * P[j].coef,
             P[i].expon + P[j].expon);
    tf = avail - 1;
    padd(ss, sf, ts, tf, &ys, &yf);  /* ara sonuca ekle */
    ss = ys;  sf = yf;
  }
  *sd = ss;  *fd = sf;
}

Ara sonuç P[ss..sf]'dir. Başta boştur: sf = ss − 1 olduğu için aralıkta terim yoktur. Dış döngünün her turunda ts ile tf arasına B · a_ix^e_i yazılır. Sonra padd eski ara sonuçla bu geçici polinomu toplar ve yeni ara sonucu dizinin sonuna koyar. İlk turda ara sonuç boş olduğundan padd'in ana döngüsü hiç dönmez ve geçici polinom olduğu gibi kopyalanır.

Zaman analizi için A'da n, B'de m terim olsun. i. turda geçici polinom m terimlidir ve O(m) zamanda yazılır. Ara sonucun boyu en çok i · m'dir, çünkü şimdiye kadar i · m çarpım üretilmiştir. padd bu turda O(im + m) zaman alır. Bütün turların toplamı:

Σ_i=1ⁿ O(im + m) = O(m · n(n + 1)/2 + nm) = O(n²m)

Sunumdaki O(n · (nm + m)) = O(n²m) yazımı, ara sonucu her turda en büyük boyuyla, yani nm ile sınırlayarak aynı sonuca ulaşır. Sonuç simetrik değildir: n'nin karesi, m'nin birinci kuvveti vardır. Küçük polinom dış döngüye alınırsa maliyet O(min(n, m)² · max(n, m)) olur. 2 terimli bir polinom 100 terimli bir polinomla çarpılsın. İki terimli olanı dışa almak yaklaşık 2² · 100 = 400 birimlik iş yapar; tersi 100² · 2 = 20.000 birim.

Bellek maliyeti daha da kötüdür. Her tur m geçici terim ve en çok im yeni ara sonuç terimi yazar ve bunların hiçbiri geri verilmez. Toplam tüketim de O(n²m)'dir. Ortak dizinin bu bedeli, uzun hesaplarda sıkıştırmayı ya da bağlı listeyi zorunlu kılar. Programda (3x²⁰ + 2x⁵ + 4)(x⁵ + 10x³ + 3x² + 1) çarpımı 11 terimli doğru sonucu verir, ama avail 7'den 42'ye çıkar: 35 konumun yalnız 11'i sonuçtur.

5.4.2n polinomu toplamak

Çok sayıda polinomla çalışan bir program, her polinomun yerini iki tabloda tutabilir. start[k], k. polinomun P içindeki ilk teriminin, finish[k] son teriminin indisidir. n polinomu toplamanın en kolay yolu art arda padd çağırmaktır: önce ilk ikisi toplanır, sonra sonuca üçüncüsü eklenir ve böyle sürer.

Bütün polinomlardaki toplam terim sayısı N olsun. Art arda toplamada ara sonuç büyür ve her padd onu baştan dolaşır. En kötü durumda ilk polinomun terimleri n − 1 kez kopyalanır. Toplam maliyet O(n · N)'dir. Örneğin her biri 100 terimli 100 polinom, ortak üsleri yoksa, yaklaşık 100 · 10.000 / 2 = 500.000 terim kopyalaması gerektirir.

Daha iyi bir yol, n polinomun hepsini aynı anda birleştirmektir. Her polinom için bir işaretçi tutulur. Her adımda n işaretçinin gösterdiği terimler arasından en büyük üslü olanı seçilir; aynı üslü olanlar toplanır. En büyüğü n terim arasından düz arayarak bulmak her adımda O(n) sürer ve toplam O(n · N) eder; bir kazanç yoktur. En büyük üssü öncelikli kuyruk (priority queue) ile, örneğin bir heap ile seçmek her adımı O(log n)'ye indirir. Toplam maliyet O(N log n) olur. Aynı sonuç, polinomları bir turnuva ağacı gibi ikişer ikişer toplayarak da elde edilir. Her turda polinom sayısı yarıya iner ve her tur toplam O(N) iş yapar ve ⌈log₂ n⌉ tur vardır.

5.4.3n polinomu çarpmak

Çarpımda ara sonuçlar hızla büyür. n polinom soldan sağa çarpılırsa, P₁P₂ çarpımı P₃ ile, sonuç P₄ ile çarpılır ve böyle sürer. Her adımda büyük bir ara sonuç küçük bir polinomla çarpılır. pmult'un maliyeti dış döngüdeki polinomun terim sayısının karesiyle büyüdüğü için büyük ara sonuç her zaman iç döngüye alınmalıdır.

İkişer ikişer, ağaç biçiminde çarpmak boyutları dengeler. Önce P₁P₂, P₃P₄, … çarpılır; sonra bu çarpımlar ikişer ikişer çarpılır. Her düzeyde çarpılan polinomlar benzer boydadır. Ara sonuçları tutmak için aynı start/finish tabloları kullanılabilir; ama dizi gösteriminde artıklar hızla biriktiğinden bağlı liste daha uygun bir seçimdir.

5.5Bağlı liste ile polinom

Dizi gösteriminin iki zayıf noktası vardır: toplam terim sayısının önceden bilinmesi gerekir ve işi biten terimlerin yeri geri kazanılmaz. Bağlı liste ikisini de çözer. Her terim, malloc ile ayrılan bir düğümde durur. Düğümler birbirine işaretçilerle bağlanır ve terim sayısı programın çalışması sırasında serbestçe büyüyüp küçülür. Bir terim artık gerekmediğinde düğümü free ile sisteme geri verilir.

5.5.1Düğüm yapısı

typedef struct pol_oge *pol_gosterge;
typedef struct pol_oge {
  int katsayi;
  int us;
  pol_gosterge bag;
} pol_oge;

İlk satır, struct pol_oge türüne işaret eden bir işaretçi türünü pol_gosterge adıyla tanımlar. Bu satır yapının tanımından önce gelir. C buna izin verir, çünkü bir yapıya işaretçi bildirmek için yapının içeriğini bilmek gerekmez; adın bir yapı olduğunu bilmek yeter. Ardından gelen tanım düğümün üç alanını verir: katsayi, us ve listedeki sonraki düğümün adresini tutan bag. Yapı kendine işaret eden bir alan içerdiği için kendine dönüşlü yapı (self-referential structure) adını alır. Bu gösterimde katsayılar tam sayıdır.

Liste, terimleri yine üsse göre azalan sırada tutar ve yalnız sıfırdan farklı terimleri içerir. Listenin ilk düğümünün adresi bir pol_gosterge değişkeninde saklanır; son düğümün bag alanı NULL'dır. Şekil 5.5, a = 3x¹⁴ + 2x⁸ + 1 polinomunun listesini gösterir.

Bir düğüm, 64 bitlik bir sistemde 16 bayt kaplar: iki int için 8 bayt, işaretçi için 8 bayt. Terim dizisindeki 8 baytlık terime göre iki kat yer tutar; bağın bedeli budur. Buna karşılık düğümler bellekte ardışık olmak zorunda değildir ve ortak bir dizinin sınırı yoktur. Polinomun terim sayısı ancak sistemin belleği bittiğinde sınırlanır.

Listenin iki önemli kazancı vardır. Birincisi, araya ekleme ve silme yalnız birkaç işaretçinin değişmesiyle, O(1) zamanda yapılır; elbette yeri bulunduktan sonra. Dizide araya ekleme, sonraki bütün terimleri bir konum kaydırmayı gerektirirdi. İkincisi, toplama yine birleştirmedir: iki listenin başından aynı anda yürünür ve padd'deki üç durum aynen uygulanır. Bağlı listeyle toplama da O(n + m) zamanda çalışır. Tek fark, sonuç düğümlerinin malloc ile ayrılması ve iş bitince free ile geri verilmesidir.

5.5.2YeniTerimEkle() ve SonrakiTerimiSil()

Çarpım kodu iki yardımcıya dayanır. Birincisi yeni bir terim düğümü oluşturur ve isteğe bağlı olarak verilen bir düğümün peşine bağlar:

/* terim oluştur; Onceki varsa peşine ekle */
pol_gosterge YeniTerimEkle(int Us, int Katsayi,
                           pol_gosterge Onceki) {
  pol_gosterge p = malloc(sizeof *p);
  if (!p) { printf("Bellek yetmiyor!\n"); exit(1); }
  p->us = Us;  p->katsayi = Katsayi;
  if (Onceki) {              /* araya ya da sona */
    p->bag = Onceki->bag;    /* önce yeni düğüm */
    Onceki->bag = p;         /* sonra önceki */
  } else p->bag = NULL;      /* tek başına */
  return p;
}

malloc(sizeof *p), p'nin gösterdiği türün, yani pol_oge'nin boyu kadar bellek ayırır. sizeof(pol_oge) yazmak da doğrudur; ama sizeof *p biçimi, p'nin türü değişirse kendiliğinden doğru kalır. malloc bellek bulamazsa NULL döndürür. Kod bu durumu hemen denetler ve programı bir iletiyle sonlandırır. Denetim yapılmasaydı bir sonraki satır NULL işaretçisinin gösterdiği yere yazmaya çalışırdı; bu tanımsız davranıştır ve çoğu sistemde program çöker.

Düğümün alanları doldurulduktan sonra iki durum ayrılır. Onceki verilmişse yeni düğüm onun peşine bağlanır. Sıra önemlidir: önce yeni düğümün bağı Onceki'nin eski sonrakine yöneltilir, sonra Onceki'nin bağı yeni düğüme. İki satır yer değiştirseydi Onceki->bag önce yeni düğüme yazılırdı; eski sonraki düğümün adresi kaybolur ve listenin geri kalanı erişilemez hâle gelirdi. Onceki NULL ise yeni düğüm tek başına bir liste olur; bağı NULL'dır. Fonksiyon her durumda yeni düğümün adresini döndürür.

İkinci yardımcı, verilen düğümden sonraki düğümü siler:

/* Onceki'den sonrakini sil */
void SonrakiTerimiSil(
        pol_gosterge Onceki) {
  pol_gosterge Silinecek =
        Onceki->bag;
  if (!Silinecek) return;
  Onceki->bag =
        Silinecek->bag;
  free(Silinecek);
}

Silinecek düğümün adresi önce Silinecek değişkeninde saklanır. Sonra Onceki'nin bağı, silinecek düğümün sonrakine yöneltilir; böylece düğüm listeden çıkar. En son düğümün belleği free ile geri verilir. Adres saklanmadan bağ güncellenseydi düğüme bir daha ulaşılamaz ve belleği hiçbir zaman geri verilemezdi. Böyle kaybolan belleğe bellek sızıntısı (memory leak) denir. Hocanın ifadesiyle, bellekteki kalıntı temizlenmelidir. Ters sıra da yanlıştır: önce free(Onceki->bag) çağrılıp sonra Onceki->bag = Onceki->bag->bag yazılırsa, serbest bırakılmış bir düğümün alanı okunur. Geri verilmiş belleği gösteren bu işaretçiye sarkan işaretçi (dangling pointer) denir ve onu kullanmak tanımsız davranıştır.

Fonksiyon, silinecek düğüm yoksa (Onceki son düğümse) hiçbir şey yapmadan döner. Fonksiyonun ilk düğümü silemediğine dikkat edilmelidir: silme her zaman bir önceki düğüm üzerinden yapılır. Çarpım kodu bu kısıtla yaşayabilir, çünkü çarpım listesinin ilk terimi hiçbir zaman silinmez.

5.5.3PolCarp() ve yerlestir()

İki polinomun çarpımında A'nın her terimi B'nin her terimiyle çarpılır. Üretilen her çarpım, sıralı sonuç listesindeki yerine konur. Aynı üslü bir terim zaten varsa katsayı güncellenir; güncellenen katsayı 0 olursa terim silinir. İç döngünün bu gövdesi okunaklılık için ayrı bir fonksiyona alınmıştır:

pol_gosterge yerlestir(pol_gosterge r,
                       int us, int kat) {
  while (r->bag && r->bag->us > us) r = r->bag;
  if (!r->bag || r->bag->us < us)
    YeniTerimEkle(us, kat, r);         /* yeni üs */
  else if ((r->bag->katsayi += kat) == 0)
    SonrakiTerimiSil(r);               /* 0 oldu */
  return r;
}

yerlestir, r düğümünden başlayıp yeni terimin yerini arar. Varsayım şudur: r'nin üssü yeni terimin üssünden büyüktür, yani yeni terim r'den sonra bir yere gelecektir. while döngüsü, sonraki düğümün üssü yeni üsten büyük olduğu sürece ilerler. Döngü bittiğinde r, yeni terimden önce gelecek son düğümdür. Üç durum kalır:

• r'den sonra düğüm yoksa (!r->bag) ya da sonraki düğümün üssü yeni üsten küçükse, bu üs listede yoktur. YeniTerimEkle(us, kat, r) yeni düğümü r'nin peşine bağlar.
• Sonraki düğümün üssü yeni üsse eşitse katsayıya kat eklenir. (r->bag->katsayi += kat) == 0 ifadesi önce toplamayı yapar, sonra sonucu 0 ile karşılaştırır.
• Toplam 0 olduysa SonrakiTerimiSil(r) bu düğümü siler.

Fonksiyon r'yi döndürür. Bu dönüş değeri bir sonraki aramanın başlangıcıdır. B'nin terimleri azalan sırada geldiği için aynı p ile üretilen çarpımlar da azalan sıradadır. Bir sonraki çarpım, listede öncekinin yerinden sonra gelir; aramayı listenin başından yeniden başlatmaya gerek yoktur.

Çarpım fonksiyonunun kendisi şöyledir:

pol_gosterge PolCarp(pol_gosterge pBas,
                     pol_gosterge qBas) {
  pol_gosterge p, q, r = NULL, bas = NULL, rBas=NULL;
  for (p = pBas; p; p = p->bag) {
    r = bas;               /* aramaya buradan başla */
    for (q = qBas; q; q = q->bag) {
      int us = p->us + q->us;
      int kat = p->katsayi * q->katsayi;
      if (rBas) r = yerlestir(r, us, kat);
      else rBas=r=bas=YeniTerimEkle(us, kat, NULL);
      if (q == qBas) bas = r;  /* sonraki p için */
    }
  }
  return rBas;
}

pBas ve qBas, iki polinomun listelerinin başıdır. rBas, sonuç listesinin başını tutar; fonksiyon sonunda onu döndürür. r, iç döngüde sonuç listesinde dolaşan konumdur. bas ise bir sonraki p için aramanın başlayacağı düğümdür.

bas değişkeni bir gözleme dayanır. p ile B'nin ilk terimi qBas'ın çarpımı, p'nin üretebileceği en büyük üslü terimdir. Sıradaki p' terimi p'den küçük üslüdür. p''nin bütün çarpımları, p'nin qBas ile çarpımından küçük üslü olur ve listede onun önüne düşemez. Öyleyse p' için arama, p · qBas çarpımının yerleştiği yerden başlayabilir. Kodda bu, q == qBas iken dönen r'nin bas'a kaydedilmesiyle yapılır. Dış döngünün her turu r = bas ile başlar.

Sonuç listesi boşken (rBas == NULL) yerlestir çağrılamaz, çünkü r geçerli bir düğüm değildir. Bu durumda ilk çarpım YeniTerimEkle(us, kat, NULL) ile tek başına bir düğüm olur ve rBas, r ve bas bu düğüme yöneltilir. rBas=r=bas=… zincirleme atamasında atama işleci sağdan sola çalışır: önce bas, sonra r, en son rBas değeri alır.

Listenin ilk düğümü A'nın ilk terimiyle B'nin ilk teriminin çarpımıdır. Bu terimin üssü bütün çarpımların en büyüğüdür ve tek olarak elde edilir: başka hiçbir terim çifti aynı üssü veremez. Bu yüzden ilk düğüm hiçbir zaman güncellenmez ve silinmez; SonrakiTerimiSil'in ilk düğümü silememesi bir sorun yaratmaz. Aynı nedenle bir aramanın başlangıcı olan r düğümünün üssü her zaman yeni terimin üssünden büyüktür ve yerlestir'in varsayımı korunur.

5.5.4Kod izleme: (x + 1)(x − 1)

A = x + 1 ve B = x − 1 listeleri ikişer düğümlüdür. Düğümler (katsayı, üs) çifti olarak yazılır: A = (1, 1) → (1, 0), B = (1, 1) → (−1, 0). Beklenen sonuç x² − 1'dir. Tablo 5.4, dört çarpımın her birini izler. Tabloda &(1, 2), katsayısı 1 ve üssü 2 olan düğümün adresidir.

Birinci adımda liste boştur ve ilk düğüm doğrudan oluşturulur. İkinci adımda yerlestir, r = &(1, 2)'den başlar. Sonraki düğüm olmadığı için döngü hiç dönmez ve −x düğümü x²'nin peşine eklenir (Şekil 5.6a). Fonksiyon yeni düğümü değil, onun öncülünü döndürür; r yine &(1, 2)'dir.

Üçüncü adım çarpımın ilginç anıdır. Dış döngü p = 1'e geçer ve r = bas ile başlar. Bu örnekte bas listenin ilk düğümüdür; daha uzun polinomlarda arama listenin ortasından başlayabilir. Yeni çarpım 1 · x = x'tir. Sonraki düğüm −x'in üssü de 1'dir. Katsayılar toplanır: −1 + 1 = 0. Terim sıfırlandığı için SonrakiTerimiSil(r) onu listeden çıkarır ve belleğini geri verir (Şekil 5.6b). Dördüncü adımda 1 · (−1) = −1 sabit terimi listenin sonuna eklenir.

Sonuç x² − 1'dir. n · m = 4 çarpım yapılmış, aynı üslü −x ile +x birleşip silinmiştir. Fonksiyon rBas'ı döndürür. Program, sonuçla işi bitince listenin bütün düğümlerini tek tek free ile geri vermelidir; girdiler için de aynısı geçerlidir. Test sürücüsünde bunu yapan kısa bir döngü vardır: sıradaki düğümün adresi saklanır, şu anki düğüm serbest bırakılır ve saklanan adrese geçilir.

5.5.5Karmaşıklık ve ölçüm

A'da n, B'de m terim olsun. Çarpım sayısı tam nm'dir. Her çarpımın kendi işi sabittir (bir toplama, bir çarpma, en çok bir malloc ya da free). Asıl maliyet yerlestir'in while döngüsündeki yürüyüştür.

Bir p terimi için iç döngü, bas'tan başlayıp listede yalnız ileri gider. yerlestir her çağrıda kaldığı yerden sürer, geri dönmez. Bu yüzden bir p için toplam yürüyüş, listenin bas'tan sonraki uzunluğunu geçemez. Sonuç listesi en çok nm düğümlüdür. Bir p'nin maliyeti O(m + nm), bütün p'lerin maliyeti O(n²m)'dir. Bu sınır pmult'unkiyle aynıdır, ama bağlı listede ara sonuçlar için ek bellek harcanmaz: sonuç listesi en çok nm düğümlüdür ve sıfırlanan düğümler hemen geri verilir.

Sınırın gerçekten erişilip erişilmediği terimlerin üslerine bağlıdır. Bunu görmek için yerlestir'in döngüsüne bir sayaç eklenmiş ve n = m terimli iki polinom iki farklı dizilimle çarpılmıştır. İki durumda da sonuç nm farklı üslü terimden oluşur:

• Seyrek A, sık B. A'nın üsleri (n − 1)m, …, m, 0; B'ninkiler m − 1, …, 0. Her p'nin çarpımları bir blok oluşturur ve bir sonraki p'nin bloğu tamamen onun arkasına gelir.
• Sık A, seyrek B. A'nın üsleri n − 1, …, 0; B'ninkiler (m − 1)n, …, n, 0. Her p'nin çarpımları, öncekilerin arasına serpiştirilir.

İlk dizilimde adım sayısı n iki katına çıkınca dört katına çıkar; yaklaşık 2nm'dir, yani O(nm). bas burada işini yapar: her p araması bir önceki bloğun başından başlar ve liste yalnız bir kez dolaşılır. İkinci dizilimde adım sayısı sekiz katına çıkar ve n²m/2'ye neredeyse eşittir. Her p, eklediği terimler önceki terimlerin arasına dağıldığı için listenin büyük kısmını yeniden dolaşır. Bu, O(n²m) sınırının gerçekten erişilebildiğini gösterir. En kötü durum maliyeti Θ(n²m)'dir.

Ölçümden çıkan pratik ders şudur: n ile m farklıysa küçük polinom dış döngüye alınmalıdır. Dış döngü terim sayısının karesi maliyete girdiği için 2 terimli bir polinomu dışa almak, 100 terimliyi dışa almaktan yaklaşık elli kat ucuzdur.

Kodun doğruluğu da sınanmıştır. Rastgele üretilen 20.000 polinom çiftinin PolCarp sonucu, katsayıları bir dizide toplayan kaba kuvvet çarpımıyla karşılaştırılmıştır. Her sonuç listesinin azalan üslü, sıfır katsayısız ve kaba kuvvet sonucuyla aynı olduğu görülmüştür.

5.5.6Problemin öteki çözümleri

İki polinomu çarpmanın tek yolu PolCarp değildir. Tablo 5.6, sunumda listelenen yöntemleri karmaşıklıklarıyla verir. A'da n, B'de m terim vardır.

Birinci yöntem nm çarpımı sırasız bir listeye yazar, sonra listeyi sıralar ve komşu aynı üsleri birleştirir. Sıralama basit bir karesel algoritmayla, örneğin eklemeli sıralamayla yapılırsa (nm)² = n²m² karşılaştırma gerekir. İkinci yöntem her çarpım için sonucu baştan tarar; sonuç nm terime kadar büyüyebildiği için yine O(n²m²) eder. Üçüncü yöntem pmult'un liste sürümüdür; PolCarp da bas sayesinde bu sınıra iner.

Beşinci yöntem birleştirmeli sıralamanın (merge sort) birleştirme aşamasına benzer. n liste, her biri m terimli olarak üretilir. Sonra ikişer ikişer birleştirilir: n liste n/2'ye, n/2 liste n/4'e iner. Her düzeyde toplam en çok nm terim işlenir ve ⌈lg n⌉ düzey vardır. Toplam maliyet O(nm lg n)'dir. Küçük polinomun terimleriyle liste kurmak, logaritmanın içine küçük sayıyı koyar.

Yedinci yöntem sonucu katsayı dizisinde biriktirir: her çarpımın katsayısı d[us]'ye eklenir. Çarpımın kendisi O(nm) sürer ve son derece basittir. Ama dizinin boyu üslerin büyüklüğüne bağlıdır. x^1000000 içeren iki seyrek polinom için iki milyon hücreli bir dizi gerekir. Sonuç dizisini terim listesine çevirmek de bütün diziyi taramayı ister. Dersin hocası bu fikre kısa ve sert bir cevap verir: n. indisin n. üssü tuttuğu bir dizi asla. Seyrek veri için tasarlanan bir yapının içine seyrek olmayan bir dizi koymak, yapının bütün kazancını geri verir. Bu notun test programı yedinci yöntemi yalnız doğruluk denetimi için, küçük üslerle kullanmıştır.

5.6Seyrek matris

Polinomdaki sorun, iki boyutlu yapılarda daha büyük ölçekte karşımıza çıkar. Bir şehrin yol ağını tutan komşuluk matrisi, bir sosyal ağdaki arkadaşlık ilişkileri ya da bir mühendislik benzetimindeki denklem sistemi, binlerce satır ve sütunlu matrislerdir. Bu matrislerin öğelerinin büyük çoğunluğu sıfırdır: her kavşak birkaç kavşağa bağlanır, her kişinin arkadaş sayısı toplam nüfusun yanında küçüktür.

5.6.1Tanım

Şekil 5.7'deki 6 × 6 matrisin 36 hücresinden yalnız 8'i doludur. Bu notun seyrek matris örneklerinin çoğu bu matristen türetilir. Matris C'de iki boyutlu bir diziyle, int a[6][6] olarak tutulabilir. Bu dizi, 8 anlamlı sayı için 36 hücre ayırır. 1000 × 1000 boyutlu ve her satırında yalnız beş dolu öğe bulunan bir matris, dört baytlık tam sayılarla 4 MB tutar; dolu öğeler ise toplam 5.000 tanedir.

Bellek israfı tek sorun değildir. İki boyutlu dizide transpoz, toplama ve çarpma gibi işlemler bütün hücreleri dolaşır. 1000 × 1000 matrisin transpozu bir milyon hücre kopyalar; oysa yalnız 5.000 öğenin yeri değişir. Seyrek matris gösterimlerinin amacı, hem belleği hem de işlem süresini dolu öğe sayısına bağlamaktır.

5.6.2Üçlü gösterim

Her dolu öğe üç bilgiyle tam olarak belirlenir: satırı, sütunu ve değeri. Bu üç bilgiyi bir yapıda toplamak, terim dizisindeki ⟨üs, katsayı⟩ çiftinin iki boyutlu karşılığıdır.

#define MAX_TERMS 101
#define MAX_COL 50   /* azami sütun */
typedef struct {
  int row, col, value;   /* satır, sütun, değer */
} term;
term M[MAX_TERMS];

term yapısının üç int alanı vardır ve yapı 12 bayt kaplar. M[0] başlıktır: M[0].row satır sayısını, M[0].col sütun sayısını, M[0].value dolu öğe sayısını tutar. Dolu öğeler M[1]'den M[M[0].value]'ya kadar dizilir. MAX_COL, transpoz fonksiyonlarındaki yardımcı dizilerin boyudur; matrisin sütun sayısı bu değeri aşamaz. Başlığın da aynı türden bir üçlü olarak tutulması küçük bir hiledir: ayrı bir başlık yapısı gerekmez ve matris tek bir diziyle fonksiyonlara geçirilir.

Sıra koşulu, satır öncelikli düzenin (row-major order) üçlülere uygulanmasıdır. İki boyutlu dizi bellekte satır satır durur; üçlü tablo da dolu öğeleri aynı sırayla okur. Şekil 5.8'de 0. satırın üç öğesi (sütun 0, 3, 5) önce gelir, sonra 1. satırın iki öğesi (sütun 1, 2) gelir. 3. satırda dolu öğe olmadığı için tabloda 3 satır numaralı üçlü yoktur. Bu sıra sayesinde bir satırın öğeleri tabloda ardışık durur ve bir satırı okumak, tablonun bir aralığını okumaktır.

Horowitz'in kitabı seyrek matris soyut veri tipini dört işlemle tanımlar: Create(max_row, max_col) boş bir matris kurar, Transpose(a) transpozu verir, Add(a, b) ve Multiply(a, b) toplamı ve çarpımı verir. Üçlü gösterim bu işlemlerin yalnız biridir; bağlı liste ve sıkıştırılmış satır gösterimi gibi başka gerçeklemeler de vardır.

5.6.3Üçlü gösterim ne zaman kazandırır?

İki boyutlu dizi rows · cols tam sayı tutar. Üçlü gösterim, başlık dahil t + 1 üçlü, yani 3(t + 1) tam sayı tutar. Üçlü gösterimin daha az yer kaplaması için

3(t + 1) < rows · cols, yani t < rows · cols / 3 − 1

olmalıdır. Kabaca, matrisin üçte birinden azı doluysa üçlü gösterim kazandırır. Üçte biri dolu olduğunda iki gösterimin bellek maliyeti yaklaşık eşittir; daha doluysa üçlü gösterim daha çok yer tutar ve tercih edilmez.

Bu hesap yalnız belleği karşılaştırır. Zaman açısından tablo farklıdır: üçlü gösterimde bir öğeye a[i][j] gibi doğrudan ulaşılamaz. (i, j) öğesini okumak için tablo aranmalıdır. Sıralılık sayesinde ikili arama O(log t)'de bulur, ama yine de O(1) değildir. Seyrek gösterim, tek tek öğe okumaktan çok bütün dolu öğeleri dolaşan işlemler için uygundur. Transpoz ve çarpım böyle işlemlerdir.

5.7Transpoz alma

Transpoz, matris işlemlerinin en basitlerinden biridir ve seyrek gösterimin hem gücünü hem tuzağını iyi gösterir.

5.7.1Transpoz ve sıra sorunu

İki boyutlu dizide transpoz iki iç içe döngüdür: t[j][i] = m[i][j]. Üçlü gösterimde ilk akla gelen, her üçlünün row ve col alanlarını yer değiştirmektir. Bu, öğelerin doğru konumunu verir, ama sırayı bozar. Şekil 5.7'deki matriste M[1] = (0, 0, 15), M[2] = (0, 3, 22), M[3] = (0, 5, −15)'tir. Alanlar değiştirilince (0, 0, 15), (3, 0, 22), (5, 0, −15) elde edilir. Bunların ardından gelen M[4] = (1, 1, 11), (1, 1, 11) olur. Sonuç tablosu 0, 3, 5, 1, … diye ilerler ve artık satır sırasında değildir. Satır sırasına güvenen bütün algoritmalar, örneğin çarpım ve ikili arama, bu tabloyla yanlış çalışır.

Sırayı düzeltmenin iki kaba yolu vardır. Alanlar değiştirilir ve tablo sonradan sıralanır; ya da her üçlü, sonuç tablosunda doğru yere araya eklenir ve sonraki üçlüler bir konum kaydırılır. İkisi de pahalıdır. Dersin hocası bunu şöyle söyler: kaydırma, taşıma kullanılıyorsa veri yapısının hakkı verilmiyor demektir. Daha iyi bir çözüm, transpozun tanımından çıkar. Transpozun satırları M'nin sütunlarıdır. Öyleyse M sütun sütun taranırsa, transpozun satırları sırayla üretilir.

5.7.2transpose(): sütun sütun tarama

void transpose(term M[], term T[]) {
  int n = M[0].value, i, j, cur;
  T[0].row = M[0].col;  T[0].col = M[0].row;
  T[0].value = n;
  if (n > 0) {
    cur = 1;                       /* T'de sıradaki */
    for (i = 0; i < M[0].col; i++)     /* her sütun */
      for (j = 1; j <= n; j++)         /* her terim */
        if (M[j].col == i) {
          T[cur].row = M[j].col; T[cur].col = M[j].row;
          T[cur].value = M[j].value;  cur++;
        }
  }
}

Fonksiyon önce başlığı yazar: transpozun satır sayısı M'nin sütun sayısı, sütun sayısı M'nin satır sayısıdır. Dolu öğe sayısı değişmez. Matris boş değilse iç içe iki döngü çalışır. Dış döngü M'nin her sütunu i için bir tur döner. İç döngü M'nin bütün üçlülerini tarar ve sütunu i olanları T'ye yazar. cur, T'de sıradaki boş konumdur.

Sonucun neden sıralı çıktığı iki gözleme dayanır. Birincisi, dış döngü sütunları artan sırada dolaştığı için T'ye önce M'nin 0. sütununun öğeleri, sonra 1. sütununun öğeleri yazılır. Bunlar T'nin 0. ve 1. satırlarıdır; satır sırası sağlanır. İkincisi, aynı sütundaki öğeler M'de satır sırasıyla durduğu için iç döngü onları satır sırasıyla bulur. T'de bu satır numaraları sütun numarası olur; aynı satır içinde sütun sırası da sağlanır.

İç döngünün j = 1'den başladığına dikkat edilmelidir. j = 0'dan başlasaydı başlık M[0] da taranırdı. M[0].col sütun sayısıdır ve hiçbir i değerine eşit olmaz, çünkü i en çok sütun sayısının bir eksiğine çıkar. Sonuç bu yüzden bozulmazdı, ama her sütun için gereksiz bir karşılaştırma yapılırdı. Doğrusu j = 1'dir.

5.7.3Kod izleme ve analiz

İzleme için küçük bir matris kullanılır: 3 × 4 boyutlu ve dört dolu öğeli M. Dolu öğeler M[1] = (0, 0, 7), M[2] = (0, 3, 3), M[3] = (1, 1, 4) ve M[4] = (2, 0, 2)'dir. Üçlülerin sütunları sırasıyla 0, 3, 1, 0'dır.

Dış döngü dört tur, iç döngü her turda dört adım döner: 4 · 4 = 16 karşılaştırma yapılır. Bunların yalnız dördü eşleşir; on ikisi boşa gider. 2. sütunda hiç dolu öğe yoktur, ama yine de bütün üçlüler taranır. Sonuç T satır sırasına göre kendiliğinden sıralıdır: (0, 0, 7), (0, 2, 2), (1, 1, 4), (3, 0, 3).

Fonksiyon Şekil 5.7'deki 6 × 6 matrise de uygulanmıştır. Sonuç tablosu (0, 0, 15), (0, 4, 91), (1, 1, 11), (2, 1, 3), (2, 5, 28), (3, 0, 22), (3, 2, −6), (5, 0, −15)'tir (Şekil 5.12). Burada 6 · 8 = 48 karşılaştırma yapılır.

Karmaşıklık iç içe döngülerden okunur. Dış döngü cols, iç döngü terms kez döner; iç gövde sabit iş yapar. Zaman O(cols · terms)'dir. Bu maliyet, matrisin ne kadar seyrek olduğuna bağlıdır. Matris doluysa terms = rows · cols olur ve maliyet O(cols² · rows)'a çıkar. İki boyutlu dizide transpoz O(rows · cols) sürer. Dolu matriste transpose bir cols çarpanı kadar daha yavaştır.

Yani üçlü gösterim bellekten kazandırırken zamandan kaybettirmiştir. Bu takas ancak terms ≪ rows · cols olduğunda anlamlıdır. Sorunun kaynağı açıktır: aynı M dizisi her sütun için baştan sona yeniden taranır. Her terimin T'de nereye gideceği önceden bilinseydi, M bir kez taranır ve her terim doğrudan yerine konurdu. Örneğin transpozun 0. satırında 2, 1. satırında 3 öğe olacağı bilinsin. 0. satır T[1]'den, 1. satır T[3]'ten, 2. satır T[6]'dan başlar. Hızlı transpoz bu bilgiyi önceden hesaplar.

5.7.4fast_transpose(): önce say, sonra yerleştir

void fast_transpose(term M[], term T[]) {
  int i, j, nc = M[0].col, nt = M[0].value;
  int row_terms[MAX_COL], start_pos[MAX_COL];
  T[0].row = nc;  T[0].col = M[0].row;  T[0].value = nt;
  if (nt <= 0) return;                    /* boş matris */
  for (i = 0; i < nc; i++) row_terms[i] = 0;
  for (i = 1; i <= nt; i++) row_terms[M[i].col]++;
  start_pos[0] = 1;
  for (i = 1; i < nc; i++)
    start_pos[i] = start_pos[i-1] + row_terms[i-1];
  for (i = 1; i <= nt; i++) {
    j = start_pos[M[i].col]++;       /* yerini al, artır */
    T[j].row = M[i].col;  T[j].col = M[i].row;
    T[j].value = M[i].value;
  }
}

Fonksiyon iki yardımcı dizi kullanır. row_terms[i], transpozun i. satırındaki, yani M'nin i. sütunundaki öğe sayısıdır. start_pos[i], transpozun i. satırının T'deki ilk konumudur. Kodun dört döngüsü vardır:

1. row_terms sıfırlanır. C'de yerel diziler ilk değer almaz; içlerindeki değer belirsizdir. Sıfırlama atlanırsa sayaçlar rastgele değerlerden başlar.
2. Sayma. M'nin her üçlüsü için kendi sütununun sayacı bir artar: row_terms[M[i].col]++.
3. Başlangıç konumları. 0. satır T[1]'den başlar. Her satır, bir önceki satırın başlangıcına önceki satırın öğe sayısı eklenerek bulunur: start_pos[i] = start_pos[i-1] + row_terms[i-1]. Bu bir önek toplamıdır (prefix sum): start_pos[i], 1 ile 0'dan i − 1'e kadar bütün sayaçların toplamıdır.
4. Yerleştirme. M baştan sona bir kez taranır. Her üçlü, kendi sütununun start_pos değerinin gösterdiği yere yazılır ve bu değer bir artar. Aynı sütundan gelen sonraki üçlü bir sonraki konuma düşer.

Dördüncü döngünün j = start_pos[M[i].col]++; satırı yoğun bir ifadedir. Önce M[i].col okunur; bu, dizinin indisidir. Son ek ++ işleci önce start_pos[M[i].col]'un eski değerini j'ye verir, sonra diziyi bir artırır. Ön ek ++start_pos[M[i].col] yazılsaydı önce artırma yapılır ve j bir fazla olurdu: ilk üçlü T[2]'ye yazılır, son üçlü dizinin dışına taşardı. Hocanın uyarısı bu satır içindir: programcı, program yazdığı dilin işleç önceliklerini iyi bilmelidir. Burada köşeli parantez ve . işleçleri, son ek ++'dan önce uygulanır; artırılan, M[i].col değil, start_pos dizisinin o hücresidir.

Üçlülerin sırası neden korunur? M satır sırasıyla tarandığı için aynı sütundaki öğeler satır sırasıyla gelir. Her biri kendi satırının bir sonraki boş konumuna yazılır. Transpozun her satırında öğeler M'deki satır numaralarına, yani transpozdaki sütun numaralarına göre artan sıradadır. Satırların kendi sırası da start_pos değerlerinin artan olmasından gelir.

5.7.5Kod izleme: iki aşama

Aynı 3 × 4 matris kullanılır. Birinci aşama sayar ve başlangıç konumlarını bulur (Tablo 5.8).

Son adımdaki eşitlik dikkat çeker: start_pos[2] ile start_pos[3] ikisi de 4'tür. 2. sütunda hiç öğe olmadığı için transpozun 2. satırı boştur ve 3. satır, 2. satırın başlayacağı yerden başlar. Boş bir satır, ardışık iki eşit başlangıç konumu olarak görünür.

İkinci aşama M'yi bir kez tarar (Tablo 5.9).

Üçlüler T'ye sırasız yazılır: önce T[1], sonra T[4], T[3] ve T[2]. Ama her biri doğru yere gider ve sonunda T, transpose'un ürettiği tabloyla aynıdır. Aşama bittiğinde start_pos[i], i. satırın son öğesinden sonraki konumu gösterir; yani start_pos[i] artık i + 1. satırın başıdır. 2. sütun boş olduğu için start_pos[2] hiç değişmemiştir.

6 × 6 örnek matriste birinci aşama row_terms = [2, 1, 2, 2, 0, 1] ve start_pos = [1, 3, 4, 6, 8, 8] üretir. 4. sütun boş olduğu için start_pos[4] ile start_pos[5] eşittir. Bu değerler programla doğrulanmıştır.

5.7.6Analiz, tek dizili sürüm ve ölçüm

fast_transpose'un dört döngüsü sırasıyla cols, terms, cols − 1 ve terms tur döner. Hiçbiri iç içe değildir. Döngü dışındaki sabit sayıda işlemle birlikte toplam iş

2 · terms + 2 · cols + sabit = O(cols + terms)

olur. Dolu matriste terms = rows · cols olduğundan maliyet O(rows · cols)'tur: iki boyutlu dizideki transpozla aynı derece. Seyrek matriste maliyet dolu öğe sayısıyla orantılıdır. Bedeli, cols boyunda iki yardımcı dizidir: O(cols) ek bellek.

Hızlı transpoz tek bir yardımcı diziyle de yazılabilir. Hocanın sorusu bunu hatırlatır: hızlı transpoz tek bellekle olur denmişti ya, işte bu o. Sayma bittikten sonra sayaçlara bir daha gerek yoktur; aynı dizi yerinde başlangıç konumlarına çevrilir:

/* row_terms'ü yerinde start_pos'a çevir */
for (i = 0, pos = 1; i < nc; i++) {
  int c = cnt[i];      /* bu sütundaki terim sayısı */
  cnt[i] = pos;        /* artık başlangıç konumu */
  pos += c;
}
for (i = 1; i <= nt; i++) {
  j = cnt[M[i].col]++;
  T[j].row = M[i].col;  T[j].col = M[i].row;
  T[j].value = M[i].value;
}

Bu kodda cnt, önce row_terms gibi sayılmış dizidir. İlk döngü her sayacı okur, yerine o satırın başlangıç konumunu yazar ve pos'u sayaç kadar ilerletir. Sayacın eski değeri c yerel değişkeninde saklanmazsa, üzerine yazılan değer okunur ve pos yanlış artar. İkinci döngü önceki sürümün yerleştirme döngüsüyle aynıdır. Bu biçim, bu notun test programında tam bir fonksiyon olarak derlenmiş ve iki yardımcı dizili sürümle aynı sonucu verdiği görülmüştür.

Tek dizili sürüm, sayarak sıralamanın (counting sort) ta kendisidir. Sayarak sıralama, küçük bir aralıktan anahtar alan öğeleri sıralar: önce her anahtardan kaç tane olduğunu sayar, önek toplamıyla her anahtarın başlangıç konumunu bulur, sonra öğeleri sırayla yerlerine koyar. Hızlı transpozda anahtar sütun numarasıdır. Aynı anahtarlı öğelerin girdideki göreli sırası korunduğu için sıralama kararlıdır ve satır sırası bozulmaz.

Aradaki fark büyük matrislerde çarpıcıdır. Tablo 5.10, sunumdaki iki fonksiyonun yalnız MAX_TERMS ve MAX_COL sabitleri büyütülerek -O2 ile derlenmiş sürümlerinin ölçümünü verir. Her satırda on dolu öğe vardır. Süreler makineye göre değişir; önemli olan büyüme oranıdır.

Boyut iki katına çıkınca hem sütun sayısı hem dolu öğe sayısı iki katına çıkar. transpose'un süresi cols · t ile orantılı olduğu için yaklaşık dört katına çıkar: 4, 14, 60, 254. fast_transpose'un süresi cols + t ile orantılıdır ve yaklaşık iki katına çıkar. En büyük matriste iki yöntem arasında yedi yüz kata yakın fark vardır. Küçük süreler ölçüm duyarlılığının sınırına yakındır; bu yüzden hızlı transpoz elli kez çalıştırılıp ortalama alınmıştır.

5.8Seyrek matris çarpımı

Matris çarpımı, seyrek gösterimin en çok işe yaradığı ve en dikkatli yazılması gereken işlemdir. Bu kesimdeki kod, Horowitz'in mmult programının sade bir uyarlamasıdır.

5.8.1Satır çarpı sütun

A matrisi m × n, B matrisi n × p boyutlu olsun. Çarpımları D = A · B, m × p boyutludur ve her öğesi

d_ij = Σ_k=0ⁿ⁻¹ a_ik · b_kj

formülüyle bulunur. A'nın i. satırı ile B'nin j. sütunu öğe öğe çarpılıp toplanır. Seyrek matrislerde bu toplamın çoğu terimi sıfırdır. a_ik · b_kj çarpımı ancak iki öğe de doluysa sıfırdan farklıdır. Öyleyse yalnız aynı k değerinde dolu olan öğe çiftleri çarpılmalıdır.

İki seyrek matrisin çarpımı seyrek olmak zorunda değildir. Şekil 5.15'deki iki matrisin her birinde dokuz hücreden üçü doludur, ama çarpımlarının dokuz hücresinin hepsi doludur. A'nın bütün satırları 0. sütunda, B'nin bütün dolu öğeleri 0. satırdadır; her (i, j) çifti k = 0'da buluşur.

Üçlü gösterimde A'nın i. satırı ardışık durur. Ama B'nin j. sütunu tabloya dağılmıştır: her satırdan en çok bir öğe, tablonun farklı yerlerinde. Bir sütunu toplamak için bütün tabloyu taramak gerekir. Çözüm, önce B'nin transpozunu almaktır. fast_transpose ile elde edilen B^T'de B'nin sütunları ardışık satırlar olur. Sonra A'nın her satırı ile B^T'nin her satırı, col alanına göre birleştirilerek çarpılır. A'nın i. satırındaki bir öğenin sütunu k'dır; B^T'nin j. satırındaki bir öğenin sütunu da B'deki satırı, yani yine k'dır. İki satırın aynı col değerli öğeleri çarpılacak çiftlerdir.

Transpozu alınan matrisin hangisi olduğu önemlidir. “Önce ilk matrisin transpozu alınır” demek yanlıştır. Horowitz'in mmult'unda ve mantık olarak transpozu alınan ikinci matris, B'dir. A'nın satırları zaten ardışıktır; sorun B'nin sütunlarındadır.

5.8.2Yardımcılar: son(), carp(), sakla()

Çarpım üç küçük yardımcıyla yazılır. İlk ikisi şunlardır:

/* s'deki terimin satırının bittiği yer */
int son(term t[], int s) {
  int e = s;
  while (e <= t[0].value &&
         t[e].row == t[s].row) e++;
  return e;
}
/* a[x..ex) satırı · b[y..ey) satırı */
int carp(term a[], int x, int ex,
         term b[], int y, int ey) {
  int sum = 0;
  while (x < ex && y < ey)
    if (a[x].col < b[y].col) x++;
    else if (a[x].col > b[y].col) y++;
    else sum += a[x++].value * b[y++].value;
  return sum;
}

son(t, s), t[s]'deki üçlüyle aynı satırda olan üçlülerin bittiği yeri bulur. e, s'den başlar ve satır numarası değişene ya da tablo bitene kadar ilerler. Döndürülen e, satırın son öğesinden bir sonraki indistir. Satır, yarı açık [s, e) aralığıdır: s dahil, e hariç. Bu yazım C'deki dizi döngülerinin alışılmış biçimidir; boş aralık s = e olarak görünür ve aralığın boyu e − s'dir. Koşuldaki sıra önemlidir: e <= t[0].value önce sınanır. && işleci kısa devre yaptığı için tablonun sonunu geçen bir e ile t[e] hiç okunmaz.

carp, a'nın [x, ex) satırı ile b'nin [y, ey) satırının nokta çarpımını hesaplar. Bu, padd gibi iki işaretçili bir birleştirmedir. İki satırın öğeleri sütuna göre sıralıdır. Sütunlar farklıysa küçük olan işaretçi ilerler, çünkü o sütunun öteki satırda eşi yoktur. Sütunlar eşitse iki değer çarpılıp toplama eklenir ve iki işaretçi de ilerler. Döngü, satırlardan biri bitince durur; kalan öğelerin eşi olamaz. Maliyet iki satırın öğe sayılarının toplamıyla orantılıdır.

Üçüncü yardımcı sonucu yazar:

void sakla(term d[], int *nd,
      int r, int c, int s) {
  if (s == 0) return;
  if (++*nd >= MAX_TERMS) {
    fprintf(stderr, "Cok terim\n");
    exit(1);
  }
  d[*nd].row = r;
  d[*nd].col = c;
  d[*nd].value = s;
}

sakla, toplam 0 ise hiçbir şey yazmaz; sıfır öğeler seyrek tabloya girmez. Değilse sayaç önce artırılır, sonra üçlü yazılır. ++*nd ifadesinde önek ++ ve * aynı öncelikte ve sağdan sola bağlanır: ++(*nd) anlamına gelir. Önce nd'nin gösterdiği sayaç bir artar, sonra yeni değer sınırla karşılaştırılır. Sonucun MAX_TERMS'ı aşması bir hata durumudur. Çarpımın seyrek kalacağının bir garantisi olmadığı için bu denetim süs değildir.

5.8.3smult() ve kod izleme

void smult(term a[], term bt[], term d[]) {
  int ra, ea, rb, eb, nd = 0;
  for (ra = 1; ra <= a[0].value; ra = ea) {
    ea = son(a, ra);           /* A satırı [ra,ea) */
    for (rb = 1; rb <= bt[0].value; rb = eb) {
      eb = son(bt, rb);        /* B sütunu [rb,eb) */
      sakla(d, &nd, a[ra].row, bt[rb].row,
            carp(a, ra, ea, bt, rb, eb));
    }
  }
  d[0].row = a[0].row;  d[0].col = bt[0].row;
  d[0].value = nd;
}

Fonksiyon A'yı ve B'nin transpozu bt'yi alır. Dış döngü A'nın satırlarını dolaşır: ra satırın ilk üçlüsü, ea = son(a, ra) satırın sonudur. Bir sonraki tur ra = ea ile başlar, yani bir sonraki satırdan. İç döngü aynı biçimde bt'nin satırlarını, yani B'nin sütunlarını dolaşır. Her satır çifti için carp nokta çarpımı hesaplar ve sakla sıfır değilse sonuca yazar. Sonuç üçlüsünün satırı a[ra].row, sütunu bt[rb].row'dur: B^T'nin satır numarası B'nin sütun numarasıdır.

Sonuç üçlüleri kendiliğinden doğru sıradadır. Dış döngü A'nın satırlarını, iç döngü B'nin sütunlarını artan sırada dolaşır. Bu, satır öncelikli sıranın ta kendisidir. Başlık en sona yazılır, çünkü dolu öğe sayısı ancak döngüler bitince bilinir. Boş satırlar ve boş sütunlar hiç ziyaret edilmez; döngüler yalnız tabloda bulunan satırları dolaşır.

İzleme için A = [[1, 0, 2], [0, 3, 0]] (2 × 3) ve B = [[4, 0], [0, 5], [6, 0]] (3 × 2) kullanılır. Tablolar şöyledir: a = (2, 3, 3) | (0, 0, 1), (0, 2, 2), (1, 1, 3). B'nin transpozu 2 × 3'tür: bt = (2, 3, 3) | (0, 0, 4), (0, 2, 6), (1, 1, 5).

Birinci adımda carp, A'nın 0. satırının sütunları {0, 2} ile B'nin 0. sütununun satırları {0, 2}'yi birleştirir. İki eşleşme vardır: k = 0'da 1 · 4, k = 2'de 2 · 6. Toplam 16'dır. İkinci adımda A'nın sütunları {0, 2}, B'nin 1. sütununun satırları {1}'dir; ortak değer yoktur ve toplam 0 olduğu için hiçbir şey yazılmaz. Sonuç D = [[16, 0], [0, 15]]'tir.

Kodun doğruluğu küçük örneklerin ötesinde de sınanmıştır. Test programı, boyutları 1 ile 6 arasında rastgele seçilen ve yaklaşık dörtte biri dolu 3.000 matris çifti üretmiştir. Her çiftin fast_transpose + smult sonucu, üç iç içe döngüyle hesaplanan klasik çarpımla aynı çıkmıştır. Aynı testte transpose, fast_transpose ve tek dizili sürüm de her matriste aynı transpozu vermiştir. Şekil 5.15'deki örnek, çarpımın dokuz öğeli dolu bir tablo ürettiğini gösterir.

5.8.4Karmaşıklık

A'nın dolu öğe sayısı t_A, B'ninki t_B olsun. Maliyet üç parçadan oluşur:

• Transpoz. fast_transpose(B): O(cols_B + t_B).
• B^T'nin gezilmesi. A'nın her satırı için bt baştan sona dolaşılır; son çağrıları ve carp'ın bt tarafındaki adımları her satır için toplam O(t_B) eder. A'nın en çok rows_A satırı için: Σ_i t_B = rows_A · t_B.
• A satırlarının gezilmesi. Her (i, j) çifti için carp, A'nın i. satırını da dolaşır. j en çok cols_B değer alır; her j için A'nın satırları toplam t_A öğedir: Σ_j t_A = cols_B · t_A.

Transpozun O(cols_B + t_B) maliyeti bu toplamın içinde kalır. Klasik çarpım O(rows_A · cols_A · cols_B) sürer: üç iç içe döngü. Matrisler doluysa t_A = rows_A · cols_A ve t_B = cols_A · cols_B olur ve seyrek sürüm de O(rows_A · cols_A · cols_B) düzeyine çıkar. Derece aynıdır, ama sabit daha büyüktür: her öğe için üç alan okunur, karşılaştırmalar yapılır.

Seyrek sürüm, t_A ve t_B matris boyutlarının küçük bir kesri olduğunda değer. Örneğin 1000 × 1000 boyutlu iki matrisin her satırında beş dolu öğe olsun: t_A = t_B = 5000. Klasik çarpım 10⁹ çarpma yapar. Seyrek çarpımın sınırı 1000 · 5000 + 1000 · 5000 = 10⁷'dir; yüz kat daha azdır. Sonuç D'nin seyrek olacağı ise garanti değildir. Şekil 5.15'deki gibi dolu bir sonuç MAX_TERMS'ı aşabilir; sakla'daki denetim bu yüzden vardır.

5.9Öteki gösterimler

Üçlü gösterim öğretici ve basittir, ama tek seçenek değildir. Bilimsel hesapta en çok kullanılan biçim sıkıştırılmış satır gösterimidir. Sık ekleme ve silme gereken uygulamalarda ise bağlı gösterim öne çıkar.

5.9.1Sıkıştırılmış satır gösterimi (CSR)

Üçlü gösterimde her öğenin satır numarası ayrı ayrı yazılır. Aynı satırdaki öğeler ardışık durduğu için bu bilgi gereksiz yere tekrarlanır. CSR, satır numaralarını atıp her satırın nerede başladığını tutar. i. satırın öğeleri val[row_ptr[i] .. row_ptr[i+1] − 1] aralığındadır; aralığın boyu row_ptr[i+1] − row_ptr[i]'dir.

6 × 6 örnekte row_ptr = [0, 3, 5, 6, 6, 7, 8]'dir. 0. satır val[0..2]'dir: 15, 22, −15. 3. satırda öğe yoktur; row_ptr[3] = row_ptr[4] = 6. Bellek: val 8, col_ind 8, row_ptr 7 tam sayı, toplam 23. Üçlü gösterim 27 tam sayı tutuyordu. Fark büyük matrislerde belirginleşir: üçlüler 3t, CSR 2t + rows + 1 tam sayı tutar.

CSR'nin en önemli kullanımı matris-vektör çarpımıdır: y = M · x. Yinelemeli denklem çözücüleri bu işlemi binlerce kez yapar.

/* y = M * x  (matris-vektör çarpımı) */
for (i = 0; i < rows; i++) {
  y[i] = 0;
  for (k = row_ptr[i]; k < row_ptr[i+1]; k++)
    y[i] += val[k] * x[col_ind[k]];
}

Dış döngü satırları dolaşır. İç döngü i. satırın dolu öğelerini dolaşır: her öğenin değeri, vektörün aynı sütundaki öğesiyle çarpılıp y[i]'ye eklenir. x[col_ind[k]] ifadesi dolaylı erişimdir: önce sütun numarası okunur, sonra vektörün o konumu. Dış döngü rows, iç döngüler toplamda t tur döner. Maliyet O(rows + t)'dir. Örnek matris x = (1, 2, 3, 4, 5, 6) ile çarpılınca y = (13, 31, −24, 0, 91, 84) çıkar; ilk öğe 15 · 1 + 22 · 4 − 15 · 6 = 13'tür.

row_ptr, fast_transpose'taki start_pos ile aynı fikirdir: her satırın başlangıç konumu, önceki satırların öğe sayılarının önek toplamıdır. Üçlü tablodan CSR kurmak da sayarak yapılır: her satırın öğeleri sayılır, önek toplamı alınır. Sütun öncelikli eşi CSC'dir (compressed sparse column): satırlar yerine sütunlar sıkıştırılır. Bir matrisin CSR gösterimi, transpozunun CSC gösterimiyle aynı dizilerdir.

5.9.2Bağlı seyrek matris

Üçlü dizi ve CSR, sabit bir matris için çok iyidir, ama matris değiştikçe zorlanır. Bir öğe eklemek ya da silmek, sıralı diziyi kaydırmayı gerektirir ve O(t) sürer. Üçlü dizinin MAX_TERMS sınırı da vardır.

Bağlı gösterimde her dolu öğe bir düğümdür. Düğüm satırı, sütunu, değeri ve iki bağ tutar: aynı satırdaki sonraki öğeye ve aynı sütundaki sonraki öğeye. Aynı satırdaki düğümler bir dairesel bağlı liste (circular linked list) oluşturur; aynı sütundakiler de öyle. Her satırın ve her sütunun bir başlık düğümü (header node) vardır. Başlık düğümleri de kendi aralarında bağlıdır ve bütün matris tek bir giriş noktasından dolaşılabilir. Horowitz bu yapıyı kitabının bağlı listeler bölümünde ayrıntılı olarak kurar.

Bu gösterimin kazancı esnekliktir. Yeri bulunduktan sonra bir öğe eklemek ya da silmek birkaç bağ değişikliğiyle, O(1) zamanda yapılır. Hem satıra hem sütuna göre gezinmek kolaydır: bir satırı ya da bir sütunu dolaşmak, ilgili dairesel listeyi dolaşmaktır. Bu yüzden çarpımda transpoza gerek kalmaz. Bedeli, öğe başına iki işaretçilik ek bellektir; 64 bitlik bir sistemde üç tam sayının 12 baytına 16 bayt daha eklenir.

Seyrek matrisin bağlı gerçeklemesi, bağlı listelerin doğrudan bir uygulamasıdır. Bir düğümü iki listeye birden bağlamak, ekleme ve silmede iki listenin bağlarını tutarlı güncellemek ve bütün düğümleri sızıntısız serbest bırakmak, bağlı liste becerisinin iyi bir sınavıdır. Dersin hocası bu çalışmanın her öğrencinin kendi emeği olması gerektiğini özellikle vurgular: iki ödev kâğıdı üst üste konup ışığa tutulduğunda aynı görünmemelidir.

5.10Karmaşıklık özeti

Tablo 5.12, bu notta incelenen işlemlerin maliyetlerini bir arada verir.

Tablonun ortak bir dersi vardır. Bütün hızlı algoritmalar sıralılığa ve birleştirmeye dayanır: padd iki sıralı terim dizisini, carp iki sıralı satırı, fast_transpose ise sayarak sıralamayla sıralı bir tablo üretir. Seyrek gösterimin bellek kazancı ancak bu sıra korunursa zaman kazancına dönüşür.

5.11Sık yapılan hatalar

Bu notun kodlarında en sık rastlanan hatalar şunlardır:

1. Terimleri sırasız tutup padd'i yine de iki işaretçiyle yazmak. Birleştirme yalnız sıralı girdide doğrudur. Sırasız girdide aynı üslü iki terim birbirini hiç görmeyebilir ve sonuçta iki ayrı terim olarak kalır.
2. Toplamı 0 olan terimi sonuca eklemek ya da listeden silmemek. padd'deki if (c) denetimi ve yerlestir'deki SonrakiTerimiSil çağrısı bu yüzden vardır. Silinen düğümün belleği free ile geri verilmelidir.
3. attach'ta float katsayıyı int parametreyle kırpmak; avail taşmasını denetlememek. Kırpma derleyici uyarısı olmadan olur. Taşma denetimi olmadan dizinin sonundan sonrası bozulur.
4. Transpozda yalnız row ve col alanlarını değiştirip sıralamayı unutmak; M[0] başlığını terim sanmak. Sırasız transpoz, çarpım gibi sıraya dayanan işlemleri bozar. Döngüler 1'den başlamalıdır.
5. start_pos[M[i].col]++ ifadesinde ön ek ile son ek farkını karıştırmak. Son ek, eski değeri kullanıp sonra artırır; ön ek kullanılırsa her üçlü bir konum kayar ve sonuncusu tablonun dışına yazılır.
6. Seyrek çarpımda A'nın transpozunu almak; sonucun seyrek kalacağını varsaymak. Transpozu alınacak matris B'dir. Sonuç dolu olabilir; sonuç tablosunun sınırı denetlenmelidir.
7. Bağlı listede silme sırasını karıştırmak. Düğümün adresi saklanmadan bağ güncellenirse bellek sızar; bağ güncellenmeden düğüm serbest bırakılırsa sarkan işaretçi kalır.
8. Yerel sayaç dizilerini sıfırlamamak. row_terms gibi yerel diziler C'de belirsiz değerle başlar; sayma döngüsünden önce sıfırlanmalıdır.

5.12Özet

• Gösterim önemlidir. Katsayı dizisi dolu ve düşük dereceli polinomda basit ve hızlıdır, ama seyrek polinomda belleği ve zamanı sıfırlara harcar. Terim dizisi yalnız sıfırdan farklı terimleri, büyük üsten küçüğe sıralı olarak tutar.
• Sıralılık ve birleştirme. padd, sıralı iki terim dizisini iki işaretçiyle yürüyerek Θ(n + m) zamanda toplar. Toplamı 0 olan terim sonuca yazılmaz. Ortak P dizisinde artıkların yeri geri kazanılmaz; sıkıştırma ya da bağlı liste gerekir.
• Dizi gösterimiyle çarpım. pmult, her terimle tek terimli çarpım yapıp sonucu padd ile ekler: O(n²m). Küçük polinom dış döngüye alınmalıdır. Çok sayıda polinom öncelikli kuyrukla ya da ikişer ikişer birleştirilir.
• Bağlı liste. Terim sayısı bilinmiyorsa esnektir. PolCarp çarpımları sıralı listeye yerleştirir, aynı üsleri birleştirir, sıfırlananları siler ve belleğini geri verir. bas değişkeni aramayı kısaltır; en kötü durum yine Θ(n²m)'dir.
• Üçlüler. Seyrek matris ⟨satır, sütun, değer⟩ üçlüleri ve M[0] başlığıyla tutulur. Üçlüler satır, sonra sütun sırasındadır. Gösterim 3(t + 1) < rows · cols iken, kabaca matrisin üçte birinden azı doluyken kazançlıdır.
• Transpoz. Alanları değiştirmek sırayı bozar. transpose sütun sütun tarayarak O(cols · t), fast_transpose önce sayıp sonra yerleştirerek O(cols + t) zamanda çalışır. Hızlı transpoz, sütun numarasını anahtar alan sayarak sıralamadır.
• Çarpım. Önce B'nin transpozu alınır; sonra A'nın her satırı B^T'nin her satırıyla birleştirilerek çarpılır: O(cols_B · t_A + rows_A · t_B). Sonucun seyrek kalacağı garanti değildir.
• Öteki gösterimler. CSR, satır numaraları yerine satır başlangıçlarını tutar ve matris-vektör çarpımını O(rows + t)'de yapar; row_ptr, start_pos ile aynı önek toplamı fikridir. Bağlı seyrek matris, ekleme ve silmeyi O(1)'e indirir, ama öğe başına iki işaretçi harcar.

5.13Kavram listesi

• polinom polynomial
• soyut veri tipi abstract data type
• birleştirme merge
• öncelikli kuyruk priority queue
• bellek sızıntısı memory leak
• sarkan işaretçi dangling pointer
• seyrek matris sparse matrix
• üçlü triple
• satır öncelikli düzen row-major order
• transpoz transpose
• hızlı transpoz fast transpose
• sayarak sıralama counting sort
• anahtar key
• sıkıştırılmış satır gösterimi compressed sparse row
• dairesel bağlı liste circular linked list
• başlık düğümü header node

5.14Kendini Dene

1. A = 5x⁶ − 2x³ + 4 ve B = 2x⁶ + 2x³ + x − 4 için padd'in ana döngüsü kaç tur döner, kaç attach yapılır ve sonuç nedir?

   Cevap

   Döngü dört tur döner: (6, 6) eşit, 5 + 2 = 7 yazılır; (3, 3) eşit, −2 + 2 = 0 yazılmaz; (0, 1) B büyük, x yazılır; (0, 0) eşit, 4 − 4 = 0 yazılmaz. İki polinom da aynı anda biter. İki attach yapılır ve sonuç 7x⁶ + x'tir.

2. avail = 5 iken A = x² + 1 ile B = x² + x + 1, pmult ile çarpılıyor. Sonuç nedir ve iş bitince avail kaç olur? Kullanılan konumların kaçı sonucu tutar?

   Cevap

   Sonuç x⁴ + x³ + 2x² + x + 1'dir (5 terim). Birinci turda 3 geçici terim yazılır ve padd onları boş ara sonuca kopyalar (3 terim daha). İkinci turda 3 geçici terim ve 5 terimlik yeni ara sonuç yazılır. Toplam 3 + 3 + 3 + 5 = 14 konum kullanılır; avail 19 olur. 14 konumun yalnız 5'i sonuçtur.

3. (x² + x)(x − 1) çarpımında PolCarp hangi terimi siler? Sonuç nedir?

   Cevap

   p = x² turunda x³ ve −x² eklenir. p = x turunda x · x = +x² gelir; katsayı −1 + 1 = 0 olur ve x² düğümü silinir. Son çarpım −x sona eklenir. Sonuç x³ − x'tir.

4. PolCarp'ta sonuç listesinin ilk düğümü neden hiçbir zaman silinmez? Bu özellik hangi yardımcının kısıtını zararsız kılar?

   Cevap

   İlk düğüm, iki polinomun en büyük üslü terimlerinin çarpımıdır. Üssü öteki bütün çarpımlardan büyüktür ve başka hiçbir terim çifti aynı üssü üretemez; katsayısı hiç güncellenmez ve 0 olamaz. SonrakiTerimiSil yalnız verilen düğümden sonrakini silebilir, ilk düğümü silemez. İlk düğüm silinmediği için bu kısıt sorun yaratmaz.

5. 100 × 100 bir matriste üçlü gösterim, iki boyutlu diziden en çok kaç dolu öğeye kadar daha az yer kaplar?

   Cevap

   Koşul 3(t + 1) < 10.000'dir. t = 3332'de üçlüler 3 · 3333 = 9999 tam sayı tutar ve daha küçüktür; t = 3333'te 10.002 tam sayı tutar. Sınır t ≤ 3332'dir, yani matrisin yaklaşık üçte biri.

6. 4 × 5 boyutlu bir matrisin dolu öğeleri (0, 2, 1), (1, 0, 3), (1, 2, −1), (2, 4, 6), (3, 2, 2)'dir. fast_transpose'un row_terms ve start_pos dizileri nedir? Transpozun üçlüleri hangi sırayla yazılır? transpose kaç karşılaştırma yapar?

   Cevap

   Sütunlar 2, 0, 2, 4, 2'dir: row_terms = [1, 0, 3, 0, 1], start_pos = [1, 2, 2, 5, 5]. Transpoz (0, 1, 3), (2, 0, 1), (2, 1, −1), (2, 3, 2), (4, 2, 6)'dır. 1. ve 3. satırlar boştur; bu yüzden start_pos[1] = start_pos[2] ve start_pos[3] = start_pos[4]. transpose, 5 · 5 = 25 karşılaştırma yapar.

7. Aynı 4 × 5 matrisin CSR gösteriminde row_ptr nedir? Üç dizi toplam kaç tam sayı tutar?

   Cevap

   row_ptr = [0, 1, 3, 4, 5]'tir: 0. satırda bir, 1. satırda iki, 2. ve 3. satırlarda birer öğe vardır. val ve col_ind beşer, row_ptr beş tam sayı tutar: toplam 15. Üçlü gösterim 3 · 6 = 18 tam sayı tutardı.

8. fast_transpose'ta j = start_pos[M[i].col]++; yerine j = ++start_pos[M[i].col]; yazılırsa 3 × 4 izleme matrisinde ne olur?

   Cevap

   Ön ek önce artırır, sonra yeni değeri verir. İlk üçlü (0, 0, 7) T[1] yerine T[2]'ye yazılır. Her üçlü kendi doğru yerinin bir ilerisine gider ve son üçlü (2, 0, 2) T[3]'e, (0, 3, 3) ise T[5]'e düşer. T[1] boş kalır. T[5], dört dolu öğeli tablonun son geçerli konumu T[4]'ün ötesindedir; dizi tam beş üçlülük ayrılmış olsaydı sınır aşılırdı.

9. 1000 × 1000 boyutlu iki matrisin her birinde 3.000 dolu öğe var. Seyrek çarpımın işlem sınırı nedir? Klasik çarpımın çarpma sayısının kaçta biridir?

   Cevap

   Seyrek çarpımın sınırı cols_B · t_A + rows_A · t_B = 1000 · 3000 + 1000 · 3000 = 6 · 10⁶'dır. Klasik çarpım 1000³ = 10⁹ çarpma yapar. Seyrek yöntem yaklaşık 167 kat daha az iş yapar.

5.15İleri okuma

• E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C (2. baskı), Kesim 2.4–2.5 ve 4.4, 4.7: bu notun padd, transpose, fast_transpose ve mmult kodlarının kaynağıdır; bağlı polinomu ve dairesel listelerle kurulan bağlı seyrek matrisi ayrıntılı verir.
• Y. Saad, Iterative Methods for Sparse Linear Systems (2. baskı), Kesim 3.4: CSR, CSC ve öteki seyrek depolama biçimlerini, bilimsel hesaptaki kullanımlarıyla birlikte anlatır.
• T. H. Cormen ve diğerleri, Introduction to Algorithms (3. baskı), Kesim 8.2: hızlı transpozun dayandığı sayarak sıralamayı, kararlılığını ve doğrusal zaman analizini verir.

5.16Kaynaklar

1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, Silicon Press, 2008 (Kesim 2.4–2.5: polinom ve seyrek matris; 4.4 ve 4.7: bağlı polinom ve seyrek matris).
2. Y. Saad, Iterative Methods for Sparse Linear Systems, 2. baskı, SIAM, 2003 (Kesim 3.4: CSR/CSC biçimleri).
3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3. baskı, MIT Press, 2009 (Kesim 8.2: sayarak sıralama).

İlgili sayfalar: Bölüm 5 sunumu · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.