İkili Aramayla Sınır Bulmak: İlk Eşleşme ve Aralık Sayımı

Sıralı bir listede belirli bir sayının bulunup bulunmadığını öğrenmek, arama problemlerinin yalnızca başlangıcıdır. Aynı sayı birkaç kez geçiyorsa ilk konumu nasıl bulunur? Belirli iki değer arasında kaç kayıt vardır? Bu yazıda ikili aramayı, tek bir eşleşme arayan işlem yerine iki bölge arasındaki sınırı bulan bir algoritma olarak kuracağız. Python’ın bisect belgeleri de işlemleri doğrudan eşitlik aramak yerine ekleme konumu bulmak üzerinden tanımlar.

1. Önce sonucun anlamını belirleyin

Örnek listemiz [2, 4, 4, 4, 7, 9] olsun. Hedefimiz 4 olduğunda herhangi bir eşleşmenin konumunu döndürmek yeterli değildir: 1, 2 ve 3 indisleri aynı değeri gösterir. Bunun yerine şu soruyu soralım: Hedeften küçük olmayan ilk eleman hangi konumdadır? Bu örnekte yanıt 1 olur. Hedef 5 olduğunda ise yanıt 4 olur; çünkü o konumda bulunan 7, yeni değerin önüne geçemeyeceği ilk elemandır.

Bu konuma sol sınır diyeceğiz. Solundaki bütün değerler hedeften küçüktür; sağındaki bütün değerler hedefe eşit veya büyüktür. Hedef bütün elemanlardan büyükse sonuç listenin uzunluğudur. Dolayısıyla dönen sayı her zaman okunabilecek bir elemanın indisi değildir. Bu sözleşme, resmi bisect_left açıklamasıyla örtüşür.

2. Arama aralığını yarı açık tutun

Aşağıdaki özgün öğretici uygulamada aday konumları [lo, hi) aralığıyla izleyeceğiz. Sol uç dahil, sağ uç hariçtir. Başlangıçta lo = 0 ve hi = len(a) seçilir. Böylece boş liste için de ayrı bir dal yazmak gerekmez. Döngü boyunca henüz karar vermediğimiz elemanlar bu aralıktadır.

def sol_sinir(a, hedef):
    lo, hi = 0, len(a)

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < hedef:
            lo = mid + 1
        else:
            hi = mid

    return lo

sayilar = [2, 4, 4, 4, 7, 9]
assert sol_sinir(sayilar, 4) == 1
assert sol_sinir(sayilar, 5) == 4
assert sol_sinir(sayilar, 10) == 6
assert sol_sinir([], 4) == 0

Ortadaki eleman hedeften küçükse onu ve solundaki bütün elemanları eleriz. Çünkü sıralı listede bunların hiçbiri aranan sınır olamaz. Bu yüzden sol ucu mid + 1 yaparız. Diğer durumda ortadaki eleman hâlâ cevap olabilir; sağ ucu mid yaparak onu sınır adayı olarak koruruz. Aynı karar yapısı CPython’ın bisect_left uygulamasında da görülebilir.

3. Bir örneği elle yürütün

Altı elemanlı örneğimizde hedef yine 4 olsun. Başlangıç aralığı [0, 6) olur. Aşağıdaki tablo, kodun değerleri nasıl daralttığını gösteren elle çıkarılmış bir izdir; performans ölçümü değildir.

lo hi mid Ortadaki değer Karar
0 6 3 4 hi = 3
0 3 1 4 hi = 1
0 1 0 2 lo = 1

Son durumda iki uç da 1 olur. Artık incelenecek eleman kalmamıştır ve sınır belirlenmiştir. Dikkat edilmesi gereken nokta, eşitlik görüldüğünde hemen dönmememizdir. İlk 4 değerini bulmak için solda başka bir eşleşme olup olmadığını araştırmaya devam ederiz.

4. Neden doğru sonuç verir?

Doğruluk gerekçesini üç parçaya ayırabiliriz. Başlangıçta sol tarafta elenmiş eleman yoktur; sağ tarafta da henüz bir kısıtlama yapılmamıştır. Her adımda, elenen sol bölümde yalnızca hedeften küçük değerler, sağ bölümde ise yalnızca hedefe eşit veya büyük değerler bulunduğunu koruruz. Bu, döngünün değişmezidir.

Ayrıca her turda aralık kesin olarak küçülür: ya sol uç ortanın ilerisine gider ya da sağ uç ortaya çekilir. Sonunda uçlar birleşir. Birleşme noktasının solundaki hiçbir eleman cevaba uygun değildir; sağındaki bütün elemanlar koşulu sağlar. Bu nedenle birleşme noktası aradığımız ilk konumdur. Bu gerekçe, yukarıdaki kod ve sıralılık varsayımı üzerinden yapılan çıkarımdır.

5. Eşleşme kontrolünden aralık sayımına geçin

Sol sınırın bulunması, hedefin listede bulunduğu anlamına gelmez. Örneğin 5 için dönen konumda 7 vardır. Kesin eşleşme gerekiyorsa önce sonucun liste uzunluğundan küçük olduğunu, ardından o konumdaki değerin hedefe eşit olduğunu kontrol edin. Python belgelerindeki sıralı listede arama örnekleri de bu iki kontrolü birlikte kullanır.

Şimdi sağ sınırı tanımlayalım: hedeften kesin olarak büyük ilk elemanın konumu. Sol sınır eşitlerin önünde, sağ sınır eşitlerin arkasında kalır. Bu iki konumun farkı, tekrar sayısını verir. Aynı fikirle kapalı bir değer aralığındaki elemanları da sayabiliriz. Sınırların standart kütüphanedeki karşılıkları bisect_left ve bisect_right işlevleridir; davranışları resmi belgede tanımlanır.

from bisect import bisect_left, bisect_right


def aralik_sayisi(a, alt, ust):
    if alt > ust:
        return 0
    return bisect_right(a, ust) - bisect_left(a, alt)


sayilar = [2, 4, 4, 4, 7, 9]
assert bisect_right(sayilar, 4) - bisect_left(sayilar, 4) == 3
assert aralik_sayisi(sayilar, 4, 7) == 4
assert aralik_sayisi(sayilar, 5, 6) == 0
assert aralik_sayisi(sayilar, 9, 2) == 0

6. Maliyeti ve kullanım sınırını ayırın

Bu kodda her tur aday aralığını yaklaşık yarıya indirir. İndisle erişimin ve karşılaştırmanın sabit zaman aldığı varsayımıyla sol sınır araması O(log n) zaman, yalnızca birkaç indis tuttuğu için O(1) ek alan kullanır. İki sınır arayan sayım da aynı asimptotik maliyettedir. Bunlar koddan türetilen sınırlardır; CPython kaynağındaki daralan aralıklı döngüler aynı analizi izlemeyi mümkün kılar.

Ancak konumu bulmakla listeye eleman eklemek aynı işlem değildir. Resmi performans notları, listeye sıralı eklemede O(n) ekleme maliyetinin logaritmik aramaya baskın geldiğini belirtir. Bu yüzden çok sayıda ekleme yapılan bir iş yükünü yalnızca arama karmaşıklığıyla değerlendirmeyin.

Temel kullanım sınırı sıralılıktır. Örneğin [4, 2, 7] girdisinde yukarıdaki eleme gerekçesi geçersizdir. Arama sırasında listeyi değiştirmeyin; karşılaştırmaların tutarlı olmasını sağlayın. Alıştırma olarak tek elemanlı, tüm değerleri eşit ve hedefi hiç içermeyen listeler için beklenen sınırları önce kâğıt üzerinde çıkarın. Amaç döngüyü ezberlemek değil, her adımda hangi bölgenin neden elendiğini açıklayabilmektir.

Kaynaklar

Loading

Facebooktwitterredditpinterestlinkedinmail

Python ve SQLite ile Hatalı Kaydı Atlayıp İşleme Devam Etmek

Bir dosyadan ürün listesi aktardığınızı düşünün. Yüz kayıt içindeki tek bir yinelenen ürün kodu yüzünden bütün aktarımı iptal etmek istemiyorsunuz. Ancak her başarılı kaydı ayrı ayrı onaylamak da istediğiniz davranış değil: aktarımın sonunda beklenmeyen bir hata çıkarsa o ana kadar yapılan değişiklikleri birlikte geri alabilmelisiniz. Bu dersin hedefi, bu iki ihtiyacı aynı örnekte karşılamak.

SQLite’ın savepoint mekanizması, işlem içinde geri dönebileceğiniz adlandırılmış noktalar oluşturur. Böylece belirli bir kayıt için yapılan değişiklikleri geri alırken önceki kayıtları işlem içinde tutabilirsiniz. İç noktayı kaldırmak, dış işlem sürerken değişiklikleri bağımsız olarak kalıcılaştırmaz. Bu ayrım SQLite savepoint belgesinde açıklanır.

1. Önce hata politikasını belirleyin

Örneğimizde her ürünün benzersiz bir kodu ve bir adı olacak. Aynı kod ikinci kez geldiğinde o satırı reddedeceğiz. Bunun dışındaki beklenmeyen hataları ise aktarımın tamamını durduracak sorunlar olarak ele alacağız. Burada asıl karar, hangi hatanın beklenen bir veri sorunu, hangisinin işleme devam etmeyi tehlikeli kılan bir durum olduğudur.

Bu politika her projeye uygun değildir. Örneğin aynı siparişin başlık ve kalemlerini aktarıyorsanız tek kalemin atlanması eksik bir sipariş oluşturabilir. Geri alma sınırını dosyadaki satır sayısına göre değil, uygulamanın anlamlı iş birimine göre seçin. Bu derste her ürün kaydını bağımsız kabul ediyoruz.

2. İşlem yönetimini açıkça seçin

Örnek, autocommit=False parametresi nedeniyle Python 3.12 veya üstünü gerektirir. Bu ayarda bağlantının bağlam yöneticisi normal çıkışta işlemi onaylar, dışarı taşan istisnada geri alır. Bağlantıyı kapatmak ise ayrıca gerekir. Parametre ve bağlam yöneticisinin davranışı Python sqlite3 belgelerinde tanımlanır.

Ders boyunca dış işlemin sahibi with con: bloğu olacak. Döngü içindeki kod yalnızca kendi savepoint sınırını yönetecek. Böylece kodu okurken iki ayrı soruyu takip edebiliriz: Bu satır kabul edildi mi? Aktarımın bütünü onaylandı mı? Bunlar aynı karar değildir.

3. Çalıştırılabilir aktarımı yazın

Aşağıdaki kodu aktarim.py adıyla kaydedip python aktarim.py komutuyla çalıştırabilirsiniz. Örnek bellek içi veritabanı kullanır; amacı kalıcı dosya üretmek değil, geri alma sınırlarını görünür kılmaktır. Kullanılan bağlantı ve parametre bağlama API’leri resmî Python başvurusunda bulunur.

import sqlite3


def aktar(con, kayitlar):
    kabul = 0
    reddedilen = []

    with con:  # Dış işlem: tamamını onayla veya geri al.
        for sira, (kod, ad) in enumerate(kayitlar, start=1):
            con.execute("SAVEPOINT satir")
            try:
                con.execute(
                    "INSERT INTO urun (kod, ad) VALUES (?, ?)",
                    (kod, ad),
                )
            except sqlite3.IntegrityError:
                con.execute("ROLLBACK TO satir")
                reddedilen.append(sira)
            else:
                kabul += 1
            finally:
                con.execute("RELEASE satir")

    return kabul, reddedilen


con = sqlite3.connect(":memory:", autocommit=False)
try:
    con.execute("""
        CREATE TABLE urun (
            kod TEXT PRIMARY KEY NOT NULL,
            ad TEXT NOT NULL
        )
    """)
    con.commit()  # Tablo kurulumunu aktarım işleminden ayır.

    kayitlar = [
        ("K-01", "Klavye"),
        ("F-01", "Fare"),
        ("K-01", "Yinelenen klavye"),
        ("E-01", "Ekran"),
    ]

    kabul, reddedilen = aktar(con, kayitlar)
    print("Kabul:", kabul)
    print("Reddedilen satırlar:", reddedilen)
    print(con.execute(
        "SELECT kod, ad FROM urun ORDER BY kod"
    ).fetchall())
finally:
    con.close()

Kod akışından beklenen sonuç üç kabul ve üçüncü satırın reddedilmesidir. Son sorguda E-01, F-01 ve K-01 kodlu ürünler görünmelidir; K-01 ürününün adı ilk kayıttaki gibi kalmalıdır. Bu, çalıştırılarak elde edilmiş bir ölçüm değil, editörün yerel ortamda doğrulayabileceği beklenen davranıştır.

4. Geri alma ile noktayı kaldırmayı ayırın

Döngünün başında oluşturulan satir noktası, o kaydın sınırını belirler. Ekleme başarılıysa nokta kaldırılır. Benzersizlik ihlalinde önce ROLLBACK TO satir çalışır, ardından nokta kaldırılır. Bunun nedeni, ROLLBACK TO komutunun hedef savepoint’i kendiliğinden silmemesidir. SQLite’ın tanımladığı kurallar bu iki komutu ayrı görevler olarak ele alır.

Üçüncü kayıt reddedildiğinde önceki iki kayıt henüz dış işlemin parçasıdır. Dördüncü kayıt da eklendikten sonra blok normal tamamlanırsa aktarım onaylanır. Başka bir istisna blok dışına çıkarsa bu örneğin hedeflediği davranış, başarılı eklemeleri de birlikte geri almaktır. Böylece “satır reddedildi” ile “aktarım başarısız oldu” durumlarını ayrı raporlayabiliriz.

Örnekte yalnızca IntegrityError beklenen kayıt hatası kabul edilir. Tabloya yeni kısıtlar eklerseniz bu hata sınıfının artık farklı ret nedenlerini kapsayabileceğini hesaba katın. Üretim sürümünde satır numarasının yanında anlaşılır ret nedeni de tutmayı planlayın; bütün sorunları “yinelenen kod” diye etiketlemeyin.

5. Küçük değişikliklerle davranışı sınayın

  • Yinelenen kodu benzersiz yapın; dört kaydın kabul edilmesini bekleyin.
  • İlk ve son kaydı aynı kodla deneyin; yalnızca sonuncunun reddedildiğini kontrol edin.
  • Döngü içinde ikinci kayıttan sonra geçici bir RuntimeError üretin. İstisnayı çağıran tarafta yakalayıp tablonun boş kaldığını doğrulayın.
  • Boş liste gönderin; kabul sayısının sıfır, ret listesinin boş olmasını bekleyin.

Testleri birbirinden bağımsız, yeni veritabanlarıyla kurun. Aksi hâlde önceki denemenin kayıtları sonraki denemede benzersizlik hatası oluşturabilir ve yanlış sonuca varabilirsiniz. Özellikle hata senaryosunda yalnızca istisnanın oluştuğunu değil, geride hangi kayıtların kaldığını da denetleyin.

6. Karmaşıklık ve kullanım sınırı

Bu örneğin Python katmanı, n kayıt için döngüyü n kez yürütür; dolayısıyla veritabanı işlemleri hariç kontrol akışı O(n) zaman alır. Reddedilen r satırın numarasını tuttuğumuz için ek Python belleği O(r), en kötü durumda O(n) olur. Bu değerlendirme SQL çalıştırma, indeks bakımı ve işlem günlüklerinin maliyetini kapsamaz; bütün aktarımın süresini yalnızca O(n) diye sunmak yanıltıcı olur.

Savepoint kullanmak eşzamanlı yazma kapasitesini artıran bir yöntem değildir. SQLite aynı anda tek yazma işlemine izin verir; büyük bir aktarım diğer yazarları bekletebilir. Bu sınır SQLite işlem belgesinde belirtilir. Aktarımı parçalara bölmeyi düşünürseniz bunun tüm dosyayı tek seferde geri alma hedefini değiştireceğini de değerlendirin.

Son olarak bu ders, veritabanı değişikliklerini yönetir; e-posta gönderme veya dış serviste işlem oluşturma gibi adımlar örneğin kapsamı dışındadır. İlk uygulamanızda akışı yalnızca kayıt ekleme ve sonuç raporlama ile sınırlayın. Sonra iş kurallarınızı genişletirken hangi adımın hangi hata durumunda geri alınacağını açıkça yazın.

Kaynaklar

Loading

Facebooktwitterredditpinterestlinkedinmail

Beklenmeyen Yalnızlık

unexpected_loneliness

Hayatım boyunca yalnız kalmayı sevdiğimi düşünürdüm.
Şimdi fark ediyorum ki aslında yalnız kalmayı değil, yalnız kalmayı tercih etmeyi seviyorum.

İnsanın kendisiyle yalnız kalması; iç kavgasını verip güçlenmesi demek bana göre.
Tabii bu, kararı siz verdiğiniz sürece.

Şimdilerde yüzüme çarpan yalnızlık ise benim tercihim değil.
Sanırım bu yüzden bu kadar can yakıyor.

Hayatınızda kimseyi kırmamaya çalışıyorsunuz.
Elinizden gelenin en iyisini yapıyorsunuz.
Ama günün sonunda, kimsenin hayatına dokunamamış olma hissi kalıyor geriye.
İşte bu, insanın içini sessizce oyan bir yalnızlık.

Çözüm mü?
Açıkçası bilmiyorum.

Ya bu duruma alışacağım ve buna “çözüm” diyeceğim,
ya da hayatımı yeniden yalnızlığı bilinçli olarak seçen adam moduna alacağım.

Çünkü bir şeyi seçmenin getirdiği sorumlulukla,
onun size dayatılması arasında derin bir fark var.

Aksiyon alma zamanı geldi…
hatta geçiyor bile.

Ne demiş ünlü düşünür Sagopa:
“Ben bana kendim için lazımım.” 🙂

Kalın sağlıcakla,

Loading

Facebooktwitterredditpinterestlinkedinmail

Makine Öğrenmesinin Matematiği – 1 – Giriş

Motivasyon

Makine öğrenmesi, veriden otomatik olarak değerli bilgiler çıkaran algoritmalar tasarlamayla ilgilenir. Burada dikkat edilmesi gereken en önemli kelime “otomatik” tir; yani makine öğrenmesi, birçok farklı veri kümesine uygulanabilen ve anlamlı sonuçlar üreten genel amaçlı yöntemlerle ilgilenir. Makine öğrenmesinin temelinde yer alan üç ana kavram vardır: veri, model ve öğrenme.

Makine öğrenmesi doğası gereği veri odaklıdır; bu nedenle veri, makine öğrenmesinin merkezinde yer alır. Makine öğrenmesinin amacı, belirli bir alana özgü uzmanlığa fazla ihtiyaç duymadan, veriden değerli örüntüleri (pattern) çıkarmak için genel amaçlı yöntemler tasarlamaktır.

Örneğin, geniş bir doküman koleksiyonuna (örneğin, birçok kütüphanedeki kitaplar) sahip olduğumuzu düşünelim. Makine öğrenmesi yöntemleri, bu dokümanlarda yaygın olarak paylaşılan konuları otomatik olarak belirlemek için kullanılabilir.

Bu hedefe ulaşmak için, genellikle veriyi üreten sürece benzer şekilde modellenen yapılar tasarlarız. Örneğin, bir regresyon probleminde model, girdi değerlerini gerçek sayılarla ifade edilen çıktılara eşleyen bir fonksiyon tanımlar.

Mitchell’in (1997) ifadesini yorumlayarak söyleyecek olursak:
Eğer bir model, veriyi dikkate aldıktan sonra belirli bir görevdeki performansını artırıyorsa, o modelin veriden öğrendiği söylenebilir.

Burada Tom Mitchell’ın ifadesini kitabı okumayanlar için iyice detaylandıralım:

Tom Mitchell, makine öğrenmesi alanında önemli bir araştırmacıdır ve 1997’de yazdığı “Machine Learning” adlı kitabında makine öğrenmesini şu şekilde tanımlamıştır:

“Bir bilgisayar programı, belirli bir görev T üzerinde, performans ölçütü P’ye göre, deneyim E’den öğrenerek performansını artırıyorsa, o zaman programın T’yi öğrenerek geliştirdiği söylenir.”

Bu tanımın açılımını şöyle düşünebiliriz:

  • T (Görev – Task): Modelin gerçekleştirmesi gereken iş. Örneğin, bir e-postanın spam olup olmadığını belirleme, görüntüdeki nesneleri tanıma veya bir borsa tahmini yapma.
  • P (Performans Ölçütü – Performance Measure): Modelin başarısını ölçen kriter. Örneğin, bir sınıflandırma modelinde doğruluk oranı, bir regresyon modelinde hata metriği gibi.
  • E (Deneyim – Experience): Modelin eğitim verisinden elde ettiği bilgi. Yani geçmiş verilere dayalı öğrenme süreci.

Bu tanıma göre bir model, veriden öğrenmiş sayılabilmesi için belirli bir görevde (T), performans ölçütüne (P) göre, deneyim kazandıkça (E) daha iyi hale gelmelidir.

Örneğin:

  • Bir e-posta sınıflandırma modeli, spam ve normal e-postaları ayırmak için tasarlanmış olsun (T).
  • Modelin başarısı, doğru tahmin oranı ile ölçülüyor olsun (P).
  • Eğer model, daha fazla e-posta örneği ile eğitildikçe spam tespitinde daha başarılı hale geliyorsa (E), o zaman model gerçekten “öğreniyor” demektir.

Buradaki temel amaç, henüz karşılaşmadığımız veriler üzerinde de iyi genelleme yapabilen modeller bulmaktır, çünkü gelecekte ilgileneceğimiz veriler bunlar olabilir. Öğrenme, modelin parametrelerini optimize ederek verideki desenleri ve yapıları otomatik olarak bulmanın bir yolu olarak düşünülebilir.

Makine öğrenmesi birçok başarı hikayesine sahip olsa da ve zengin, esnek makine öğrenmesi sistemlerini tasarlayıp eğitmek için yazılımlar kolayca erişilebilir durumda olsa da, makine öğrenmesinin matematiksel temellerinin anlaşılmasının son derece önemli olduğuna inanıyoruz.

Bu temel prensipleri kavramak, şu konularda bize büyük avantaj sağlar:

  • Yeni makine öğrenmesi çözümleri geliştirmek,
  • Mevcut yaklaşımları anlamak ve hata ayıklamak,
  • Kullandığımız yöntemlerin temel varsayımlarını ve sınırlamalarını öğrenmek.

Özetle, makine öğrenmesini sadece uygulamalı bir araç olarak görmek yerine, altında yatan matematiksel prensipleri öğrenmek, daha sağlam ve bilinçli çözümler üretmemizi sağlar.

Bu yazıda neden matematiksel altyapıya odaklıyoruz kısmını anlatmaya çalıştım, bir sonraki yazıda görüşmek üzere.

İyi kodlamalar.

Loading

Facebooktwitterredditpinterestlinkedinmail

Kod yazmak anlamaktır.