Bu yazıda, basit ama büyük bir hesaplama problemini hızlandırmak için kullanabileceğimiz bazı yöntemlere bakacağız ve bir Python modülünü C ile nasıl yazabileceğimizi göreceğiz.
Kaggle’ın yarışma problemlerinden biri, Noel Baba’nın ziyaret edeceği şehirleri en kısa yol olarak düzenlememizi istiyor. Şehirlerin iki boyutlu koordinatları ve ID numaraları verilmiş. Noel Baba 0 numaralı noktadan yola çıkıyor ve yine 0 numarada yolculuğunu bitiriyor. Soru şu: Öyle bir şehir sırası bulun ki, Noel Baba’nın katedeceği toplam mesafe asgariye insin. Bu optimizasyon probleminin klasik Seyyar Satıcı probleminden farkı şu: Noel Baba’nın her on durağından birinin sıra numarası bir asal sayı değilse, bir sonraki etabın mesafesi %10 fazla olarak hesaplanıyor. Yani ideal en kısa yolda on noktadan birinin asal numaralı bir şehir olması gerekli.
Bu yazıda bu problemi tamamen çözmeyeceğiz, ama çözümü bulmak için elzem olan bir ara problemi didik didik edeceğiz: Belli bir şehir listesi verildiğinde, bu yolculukta katedilecek toplam mesafeyi mümkün olan en hızlı şekilde hesaplayacak kodu yazacağız. Hızlı olması önemli, çünkü en kısa yolu bulacak olan optimizasyon algoritması bu işi binlerce kere tekrarlayacak.
Bu not defterini ve ilgili programları GitHub sayfamızdan indirebilirsiniz.
Veriyi yükleyelim
Veri dosyasını çalışma dizinimin altında data dizinine koydum.
Dikkat: Buradan sonraki dört komut (! ile başlayanlar) işletim sistemi yorumlayıcısına gönderilir. Ben Linux kullanıyorum; sizin işletim sisteminiz farklıysa aynı komutlar bulunmayabilir ve Jupyter hata mesajı verir.
Önce verinin ilk ve son satırlarına bakalım.
!head -n5 data/cities.csv
!tail -n5 data/cities.csv
Şehir ID numaraları 0 ile başlayıp 197768 ile bitiyor. Arada tekrarlanan ID olup olmadığını kontrol edelim.
!cut -f1 -d, data/cities.csv | sort | uniq -d
Komut hiç bir şey çıkarmıyor, demek ki tekrarlanan ID yok. Peki acaba arada atlanan ID var mı? Dosyanın toplam uzunluğuna bakalım:
!wc -l data/cities.csv
Dosyada toplam 197770 satır var. Birinci satır sütun başlıklarını içeriyor, onu çıkarırsak toplam 197769 veri noktası mevcut. Tekrarlanan ID olmadığını da görmüştük, demek ki 0-197768 arası ID’lerin hepsi dosyada mevcut.
Buradan itibaren normal Python koduna dönüyoruz; komutlarımız her işletim sisteminde çalışacaktır.
Dosyayı bir Numpy dizisine yükleyelim.
import numpy as np
şehirler = np.loadtxt("data/cities.csv", delimiter=",",skiprows=1, usecols=(1,2))
şehirler[:5,:]
Bir dizi şehir numarası alıp, katedilen toplam mesafeyi verecek bir fonksiyon yazmalıyız. Ancak, her onuncu adımı atmadan önce durup, bulunduğumuz şehir numarasının asal olup olmadığına bakmalıyız. Bir sonraki adım mesafesi buna bağlı olacak.
toplam = || sonraki_nokta - bu_nokta ||
adımno = 1
noktalar bitmediği sürece tekrarla:
noktaları güncelle
eğer adımno 10'a bölünüyorsa ve nokta numarası asal değilse:
toplam += 1.1 * || sonraki_nokta - bu_nokta ||
değilse:
toplam += || sonraki_nokta - bu_nokta ||
Belli bir şehir numarasının asallığını kontrol için bir fonksiyon çağırabiliriz. Ama bu, çok tekrarlandığında fazla zaman alacak bir işlem. Onun yerine, 0 ile 197768 arasındaki bütün asal sayıları çıkarıp bir listeye yazalım ve verilen sayının bu listede bulunup bulunmadığını soralım. Bilgisayar için listeye bakmak fonksiyon çağırmaktan daha hızlı bir işlemdir.
Asal şehirlerin listesi
Toplam mesafe hesaplarken on adımda bir, bulunduğumuz şehir numarasının asal olup olmadığına bakacağız. Asal sayıları bir listeye yazıp gerektikçe bakmak, her seferinde o sayının asal olup olmadığını hesaplamaktan çok daha kolaydır. O zaman, 0 ile 197768 arasındaki asalları içeren bir liste hazırlayalım.
SymPy pakedi içindeki sieve modülü, Eratosthenes süzgeci yöntemiyle asal sayılar veren bazı fonksiyonlar içeriyor. Bu modüldeki primerange() fonksiyonunu kullanarak bu işi yapabiliriz.
from sympy import sieve
asalşehirler = list(sieve.primerange(0,197769))
Birinci deneme: Toplam mesafe fonksiyonu
Şimdi, verilen bir yol için toplam mesafeyi veren fonksiyonu yazalım. Fonksiyonun girdisi şehir numaralarının bir permütasyonu olacak, ve ilk ve son elemanlar 0 olacak.
def mesafe(i,j):
d = şehirler[i,:] - şehirler[j,:]
return np.sqrt(np.dot(d,d))
def toplam_mesafe(p):
toplam = 0
for adımno in range(1,len(p)):
m = mesafe(p[adımno],p[adımno-1])
if adımno%10==0 and (p[adımno-1] not in asalşehirler):
m = 1.1*m
toplam += m
return toplam
Denemelerimiz için Noel Baba’nın kullanacağı bir yol belirlememiz lazım. Bu aşamada sadece kodu hızlandırmaya çalışıyoruz; herhangi bir optimizasyon uygulamıyoruz. Basitçe, 0’dan başlayarak bütün şehirleri ID sırasıyla takip eden bir yol kullanacağız. Son durak olarak 0 eklemeyi de unutmayalım.
yol = list(range(197769))+[0]
Bu haliyle fonksiyonumuzun ne kadar vakit aldığını %time sihirli komutuyla ölçebiliriz. (Jupyter kullanmıyorsanız aynı işi timeit modülüyle yapabilirsiniz.)
%time toplam_mesafe(yol)
%timeit toplam_mesafe(yol)
Zaman profili çıkarma
İlk algoritmamızla bir tek yolun toplam mesafesini hesaplamak 6 saniyeden fazla alıyor. Bu epeyce yavaş; hızlandırmanın yolunu aramamız lazım. Bunun için de ilk adım fonksiyonun zaman profilini çıkarmak; yani hangi satırda ne kadar vakit harcandığını ölçmek. Bunu line_profiler paketi ile yapabiliriz.
line_profiler sisteminizde kurulu değilse, terminalde
$ pip install line_profiler
veya
$ conda install -c anaconda line_profiler
komutuyla kurabilirsiniz. Anaconda kullanıyorsanız ikincisini tercih edin.
%load_ext line_profiler
%lprun -f toplam_mesafe toplam_mesafe(yol)
Görüyoruz ki zamanın çoğu, şehrin sayısının asal olup olmadığını kontrol etmek için harcanıyor. Öncelikli olarak bu işlemi hızlandırmaya çalışalım.
İkinci deneme: İkiye bölerek arama yapmak
Şehrin sayısının asal olup olmadığına bakarken uzun bir liste içinde bir elemanın var olup olmadığını kontrol ediyoruz. Python, bu kontrolü yaparken elemanları baştan itibaren sırayla tarar; bu da büyük listelerde çok uzun zaman alır.
Eğer elimizde sıralı bir liste varsa (ki asal şehirler listesi öyle), ikiye bölerek arama (binary search) algoritması çok daha hızlı çalışır. Şimdi bunu deneyelim.
Bu algoritma gayet basittir; kendimiz de yazabiliriz. Ama Python’un standart kütüphanesindeki bisect modülü bu işlevi sağlıyor zaten. Mümkün oldukça mevcut kütüphaneleri kullanmak daha iyidir; çünkü bu kütüphanelerdeki kodlar çok kişi tarafından uzun zaman boyunca denenmiş, hataları düzeltilmiş, performansları geliştirilmiştir.
bisect modülünün yardım belgelerinde tarif edildiği şekilde, verilen bir liste içinde bir elemanın olup olmadığını döndüren, içinde() isimli bir fonksiyon yazalım. Birinci denemedeki programımızdaki ilgili satırı da bu fonksiyonu çağıracak şekilde değiştirelim.
import bisect
def mesafe(i,j):
d = şehirler[i,:] - şehirler[j,:]
return np.sqrt(np.dot(d,d))
def içinde(a, x):
i = bisect.bisect_left(a, x)
if i != len(a) and a[i] == x:
return True
else:
return False
def toplam_mesafe(p):
toplam = 0
for adımno in range(1,len(p)):
m = mesafe(p[adımno],p[adımno-1])
if adımno%10 == 0 and not içinde(asalşehirler, p[adımno-1]):
toplam += 1.1*m
else:
toplam += m
return toplam
Tekrar %time sihirli işlemini kullanarak fonksiyonun kullandığı zamanı ölçelim.
%time toplam_mesafe(yol)
Başka hiç bir değişiklik yapmadan, sadece ikili arama algoritması kullanarak süreyi dörtte bire indirdik. lprun ile profilleme yaptığımızda şehrin asallığını belirleme için gereken zamanın çok düştüğünü görüyoruz. Artık darboğaz oluşturmuyor.
%lprun -f toplam_mesafe toplam_mesafe(yol)
Üçüncü deneme: Mesafeyi fonksiyon çağrısı yapmadan hesaplamak
Bir önceki denemede, artık zamanın çoğunun mesafe() fonksiyonuna yapılan çağrıda harcandığını görüyoruz. Bu işlemi hızlandırıp hızlandıramayacağımızı düşünelim. Genel olarak bir fonksiyon çağrısı zaman harcayıcı bir işlemdir. mesafe() fonksiyonda yapılan işlemleri toplam_mesafe() içine taşıyalım ve bir hızlanma olup olmadığını görelim.
def toplam_mesafe(p):
toplam = 0
for adımno in range(1,len(p)):
d = şehirler[p[adımno]] - şehirler[p[adımno-1]]
m = np.sqrt(d[0]**2+d[1]**2)
if adımno%10 == 0 and not içinde(asalşehirler, p[adımno-1]):
toplam += 1.1*m
else:
toplam += m
return toplam
%time toplam_mesafe(yol)
%lprun -f toplam_mesafe toplam_mesafe(yol)
Az miktarda bir hızlanma görüyoruz, ama bu değişiklik önemli bir fark oluşturmadı. Yine zamanın %60’dan fazlası tek bir adımlık mesafeyi hesaplayan işlemlerde harcanıyor. Değiştirmesek de olurdu.
Dördüncü deneme: Numpy ile vektörleştirme
Temel Python işlemleri kullanarak daha fazla hızlandırma sağlayabilecekmişiz gibi görünmüyor. Şimdi bambaşka bir yaklaşım deneyelim: Hızlı sayısal vektör işlemleri için geliştirilmiş NumPy kütüphanesini kullanalım.
Python gibi yüksek seviyeli, yorumlanan dillerde while veya for gibi döngüler çok yavaş işler. Buna karşılık vektörleştirme kullanırsak, yani döngü işlerini dikkatli bir şekilde vektör işlemleri haline getirirsek NumPy bize büyük bir avantaj sağlar. Biz görmeden arka planda yine bir döngü çalışır kuşkusuz, ama bu döngü NumPy kütüphanesinin C ile yazılmış, derlenerek azami derecede hızlı hale getirilmiş kodları içinde çalışır. Python komut yorumlayıcısını yavaşlatan faktörlerden etkilenmez.
def toplam_mesafe(p):
p = np.array(p)
# Şehir çiftleri arasındaki fark vektörlerini hesapla
kaymalar = şehirler[p[1:]] - şehirler[p[:-1]]
# Her fark vektörünün uzunluğunu hesapla
mesafeler = np.linalg.norm(kaymalar, axis=1)
# Turdaki her şehir için (son durak 0 hariç) asalşehirler içinde bulunanlara False, diğerlerine True yaz.
asalmaske = np.isin(p[:-1], asalşehirler, assume_unique=True, invert=True)
# Uzun olması gereken adımlar için True, diğerleri için False yaz.
uzunadımlar = (np.arange(1,len(p)) % 10 == 0) & asalmaske
# On adımdan biri asal şehirde başlamıyorsa mesafeyi %10 artır.
mesafeler[uzunadımlar] *= 1.1
return mesafeler.sum()
Gördüğünüz gibi bu kodda açıkça yazılmış hiç bir döngü yok; bütün döngüler alt seviyede hallediliyor. Bu da ciddi bir hızlanma sağlıyor.
%time toplam_mesafe(yol)
%timeit toplam_mesafe(yol)
Bu sefer performans artışı çok etkileyici; işlemi 60 milisaniyeye indirdik.
%lprun -f toplam_mesafe toplam_mesafe(yol)
Profilden gördüğümüz gibi özellikle kısıtlayıcı bir darboğaz yok. NumPy içindeki hızlı vektör algoritmalarını kullanmak büyük avantaj sağladı.
Bundan daha hızlı olmaz mı? Olur, ama ellerimizi makine yağına ve silikon tozuna bulamamız gerekecek. Bu fonksiyonu C ile yazacağız ve Python’dan çağıracağız.
Beşinci deneme: Python C API’sini kullanmak
Burada toplam_mesafe() fonksiyonunu Python ile değil C ile yazacağız, ama bu fonksiyonun Python içinde kullanılabilmesini sağlayacağız. Bir Python listesi (şehir numaraları) alacak, işleyecek ve sonucu geri verecek.
Python C API’si, bazı kurallara riayet ederek bu işleri yapabileceğimiz bir arayüz sağlıyor bize. Bu geniş API’yi burada ayrıntılarıyla anlatmamız mümkün değil. Bazı örnek kullanımlar ve açıklamalar için Tutorialspoint ve Wikibooks‘a bakabilirsiniz.
Sabit verileri C dizileri olarak kaydet
Kullandığımız şehir koordinatlarının ve asal sayılar listesinin hep aynı olduğuna dikkat edin. Bunları sabit veriler olarak C kaynak koduna eklersek daha fazla performans artışı sağlayabiliriz. Bu amaçla, önce data.c adıyla bir C kaynak dosyası hazırlayacağız. Bu dosyada asal şehirler ile her bir şehrin x ve y koordinatları birer C dizisi (array) olarak kaydedilmiş olacak. Bunu elle yapmak zor, o yüzden bu dosyayı yaratacak özel bir betik hazırlayacağız; aşağıdaki gibi.
# santa2c.py
# CSV dosyasındaki verileri C array olarak içeren bir data.c dosyası yaratır.
import numpy as np
cities = np.loadtxt("data/cities.csv", delimiter=",",skiprows=1, usecols=(1,2))
from sympy import sieve
primeids = sieve.primerange(0,197769)
with open("data.c","w") as f:
# Asal olan şehir numaralarını sıralı bir diziye yaz.
f.write("unsigned int asalsehirler[] = {")
for p in primeids:
f.write( str(p)+"," )
f.write( "};\n" )
# Şehirlerin x koordinatlarını bir diziye yaz.
f.write( "double x[]={"+str(cities[0,0]) )
for x in cities[1:,0]:
f.write( ","+str(x) )
f.write( "};\n" )
# Şehirlerin y koordinatlarını bir diziye yaz.
f.write( "double y[]={"+str(cities[0,1]) )
for y in cities[1:,1]:
f.write( ","+str(y) )
f.write( "};\n" )Bu programı terminalde şu şekilde çalıştırırız:
$ python santa2c.py
ve bu işlemin sonucunda data.c dosyası yaratılmış olur. Şimdi Asıl işi yapan C kodunu nasıl yazacağımızı görelim.
Toplam mesafe: C kodu
Yazacağımız C programı, derlendikten sonra bir Python modülü olarak yüklenecek. Bu programın içinde asıl işi yapan toplam_mesafe() fonksiyonunun yanı sıra, bazı yardımcı fonksiyonlar, ve Python’a bu modülün nasıl kullanılacağını bildiren kodlar bulunacak.
// pysanta.c
#include <Python.h> // Python C API'si için
#include <math.h> // sqrt() için
#include <stdlib.h> // bsearch() için
#define n_asal 17802
// data.c içinde yazılı diziler:
extern double x[];
extern double y[];
extern unsigned int asalsehirler[];Yardımcı fonksiyonlarımızı yazalım: İki şehir arasındaki mesafeyi hesaplayan bir fonksiyon, ve ikili arama için kullanacağımız bsearch() fonksiyonu için gereken karşılaştırma fonksiyonu.
inline double mesafe(long sehir1, long sehir2)
{
double dx, dy;
dx = x[sehir2] - x[sehir1];
dy = y[sehir2] - y[sehir1];
return sqrt(dx*dx+dy*dy);
}
int compareints (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}Python’dan çağıracağımız toplam_mesafe() fonksiyonunu biraz farklı bir şekilde yazmamız gerekiyor. Fonksiyonun giriş parametreleri ve döndürdüğü değer bir Python nesnesi olmalı.
static PyObject* toplam_mesafe(PyObject* self, PyObject* args)
{
PyObject *yol;
long onceki, yeni;
int *item;
double m;
double toplam = 0;Parametreleri toplamak için PyArg_ParseTuple ve benzeri fonksiyonlar kullanışlı bir arayüz oluşturuyorlar. Burada parametre olarak tek bir liste alacağız ve yol değişkenine aktaracağız. Ardından, PyList_Size() ile bu listenin eleman sayısını alabiliriz, PyList_GetItem() ile belirli elemanlarına ulaşabiliriz. Ulaştığımız elemanı tamsayı değerine çevirmek için PyLong_AsLong() fonksiyonunu kullanırız (Python C API’de bütün tamsayılar long tipindedir).
if (!PyArg_ParseTuple(args, "O", &yol))
return NULL;
Py_ssize_t len = PyList_Size(yol);
onceki = PyLong_AsLong(PyList_GetItem(yol, 0));Şimdi yolun her adımındaki mesafeleri toplayalım. On adımda bir asallık şartını kontrol etmeyi unutmayalım.
for (int adim=1; adim<len; adim++) {
yeni = PyLong_AsLong(PyList_GetItem(yol, adim));
m = mesafe(onceki, yeni);
if (adim%10==0) {
// İkili arama ile şehir sayısını asallar arasında ara.
item = (int*) bsearch (&onceki, asalsehirler, n_asal,
sizeof (unsigned int), compareints);
// Asallar arasında bulunmadıysa mesafeyi %10 arttır.
if (item==NULL) m *= 1.1;
}
toplam += m;
onceki = yeni;
}Hesaplama döngümüz bittikten sonra sonuç değerini bir Python nesnesi haline getirerek döndürüyoruz.
return Py_BuildValue("f", toplam);
} // toplam_mesafe sonuProgramın geri kalanı, bu modülle ilgili üst bilgiler içeren veri yapıları ve modülün ilk işlemleri için gereken hazırlık fonksiyonunun tanımından ibaret. Bunlarla ilgili ayrıntıya girmiyorum; daha fazla bilgiyi yukarıda belirttiğim kaynaklarda bulabilirsiniz.
static PyMethodDef SantaMethods[] =
{
{"toplam_mesafe", toplam_mesafe, METH_VARARGS, "Belli bir turun katettiği toplam mesafeyi verir."},
{NULL, NULL, 0, NULL}
};
static struct PyModuleDef Santa_Module = {
PyModuleDef_HEAD_INIT,
"santa", // Python'un gordugu modul ismi.
"Gezgin Santa Problemi modulu.", // modul belgeleme dizesi
-1,
SantaMethods
};
PyMODINIT_FUNC PyInit_santa(void)
{
return PyModule_Create(&Santa_Module);
}Kodları derleyerek Python modülü yarat
Derleme aşamasında C kodu ve Python API’si birleştirilerek bir paylaşılan kütüphane oluşturulur (Unix/Linux’da .so uzantılı, Windows’ta .pyd uzantılı). Bu işlemin ayrıntılarını Python belgelerinde bulabilirsiniz. Sisteminizde bir C derleyicisinin ve Python “header”larının bulunması gerekiyor.
Derleme aşamasında gereken adımları otomatikleştirmek için distutils modülünü kullanmak tavsiye edilir. Bunun için önce aşağıdaki gibi bir setup.py programı hazırlarız:
from distutils.core import setup, Extension
module = Extension('santa', sources = ['data.c','pysanta.c'])
setup (name = 'santa',
version = '1.0',
description = 'Gezgin Santa Problemi',
ext_modules = [module])Özetlersek, şu aşamada elimizde üç tane kaynak kodu dosyası bulunması gerekiyor: setup.py, pysanta.c ve data.c (ki bunu santa2c.py programıyla üretmiştik).
Ardından modülü inşa etmek için terminalde şu komutu veririz:
$ python setup.py build_ext --inplace
Bu işlemden sonra santa modülü derlenmiş bir ikili dosya olarak kullanmaya hazırdır. Şimdi Python’a dönerek alışıldık şekilde import ederek kullanabiliriz.
Derlenmiş modülü Python’la kullan
from santa import toplam_mesafe
Bu yeni versiyonu kullanırken yukarıda kullandığımız şehirler ve asalşehirler listelerine ihtiyacımız kalmıyor, çünkü bu veriler artık santa kaynak kodunun içine gömülü.
Fonksiyonumuzun yeni halinin hızını ölçelim:
%time toplam_mesafe(list(range(197769))+[0])
%timeit toplam_mesafe(list(range(197769))+[0])
Önceki denemelere göre çok daha hızlıyız artık. İlk denememizde ortalama 6.8 saniye süren işlem, şimdi ortalama 16 milisaniye sürüyor; 400 kattan fazla bir hızlanma sağladık. Optimizasyona başlamak için bu kadarı yeterli olacaktır.
Daha iyisini yapamaz mıyız? Mümkün, ama daha yüksek performans için paralel programlama teknikleri kullanmak gerekir. Toplam mesafeyi hesaplamak kolayca dağıtılabilecek bir problemdir. CPU’nuzun dört tane çekirdeği varsa yol listesini dört parçaya ayırabilir ve her bir parçanın uzunluğunu ayrı ayrı hesaplatabilirsiniz. Böyle bir algoritma ile toplam_mesafe() çalışma süresini teorik olarak 4-5 milisaniyeye indirmek mümkün olur. Bunu meraklısına alıştırma olarak bırakıyorum.