Kaybolan veri tipinin izini sürmek

 (hillelwayne.com)
2 puan yazan GN⁺ 2024-03-05 | 1 yorum | WhatsApp'ta paylaş
  • Grafikler; bağımlılıklar, web bağlantıları, model checker durum uzayları ve ilişkisel veritabanlarındaki foreign key’ler gibi yazılımın her yerinde bulunuyor, ancak ana akım programlama dillerinde yerleşik tip ya da standart kütüphane desteği neredeyse yok
  • Yerleşik bir grafik tipi tasarlamanın zor olmasının ilk nedeni; yönlü/yönsüz, basit/multi, hypergraph gibi çok sayıda grafik türü bulunması ve belirli özelliklerin algoritma seçimini ile performansı büyük ölçüde değiştirmesi
  • Edge list, adjacency list, adjacency matrix ve referans veren struct’lar gibi temsil biçimlerinin bellek kullanımı ve sorgulama performansı farklı olduğundan, tek bir genel amaçlı temsilin tüm kullanım senaryolarını karşılaması zor
  • Grafik algoritmaları uygulanması zor ve çoğu zaman büyük girdilerde çalıştırılıyor; bu yüzden Nosey Parker ve Gecode örneklerinde olduğu gibi probleme özel temsil ve dolaşım, genel amaçlı kütüphanelerden daha önemli hale gelebiliyor
  • Grafiklerin standart kütüphanelerde nadir olmasının nedeni; tip, temsil, algoritma ve performans arasındaki trade-off’ların yanı sıra bakım yükünün büyük olması, ayrıca üçüncü taraf kütüphanelerin de sınırlı ya da yavaş olabilmesi

Grafikler yaygın, ama dil desteği zayıf

  • Grafikler düğümler ve kenarlardan oluşur; hem düğümler hem de kenarlar veri taşıyabilir
  • Yazılım mühendisliğinde grafikler birçok biçimde ortaya çıkar
    • Paket bağımlılıkları ve modül import’ları bir yönlü grafik oluşturur
    • İnternet, web sayfaları arasındaki bağlantı grafiğidir
    • Model checker’lar tüm olası yapılandırmaların durum uzayını tarar; burada düğümler durumları, kenarlar ise geçerli geçişleri temsil eder
    • İlişkisel veritabanları; kayıtları düğüm, foreign key’leri kenar olarak görülebilir
    • Grafikler; linked list, binary tree ve hash table’ın genellemesi olarak görülebilir
  • İş mantığında da makale atıf ilişkileri, ulaşım ağı rotaları ve sosyal ağ bağlantıları gibi grafikler sıkça görülür
  • Grafiklere sık ihtiyaç duyulsa da, ana akım dillerin çoğu grafikleri yerleşik tip olarak sunmaz ve bunları standart kütüphaneye dahil edenler de azdır
  • Birçok ekosistemde sağlam üçüncü taraf grafik kütüphaneleri de eksik olduğundan, çoğu durumda geliştiricilerin kendilerinin uygulaması gerekir

Grafik tipi tasarımında fazla sayıda seçenek var

  • Yönlü ve yönsüz grafiklerin dışında da birçok grafik varyantı vardır
    • İki düğüm arasında en fazla bir kenara izin veren basit grafikler ve birden fazla kenara izin veren multigraph’lar
    • Tek bir kenarın 3 veya daha fazla düğümü bağladığı hypergraph’lar
    • Kenarların başka kenarları işaretleyebildiği ubergraph’lar
  • Her varyant ek tasarım kararlarını da beraberinde getirir
    • Kenarlara da ID verilip verilmeyeceği, yoksa yalnızca düğümlere mi verileceği belirlenmelidir
    • Düğüm ve kenarlarda hangi verilerin tutulacağına da karar verilmelidir
  • Tüm grafikleri “yönlü hyper-uber-multigraph” gibi genel bir tiple sunup kullanıcıların bunu kısıtlamasına izin vermek mümkün, ancak hemen iki sorun ortaya çıkar
    • Sonucun tek bir değer mi yoksa bir liste mi olduğu gibi arayüz değişir
    • Grafiklerin özel yapısal özelliklerinden yararlanılamazsa algoritma performansı düşer
  • Örneğin maximum weight matching, grafiğin bipartite olduğu biliniyorsa daha hızlı bir algoritma kullanabilir; ancak genel grafiklerde daha yavaş ve daha genel bir algoritma gerekir
  • Belirli bir problem P, grafik G ve algoritmalar A·B·C olduğunda, hangi algoritmanın çalıştırılacağını seçme şeklinde bir algoritma dispatch problemi de ortaya çıkar
  • Kusursuz bir grafik kütüphanesi birçok grafik türünü desteklemelidir; ancak bu durumda kullanıcıların gerçekten istediği algoritmaları uygulamak için daha az zaman kalır
  • Grafik algoritmalarını uygulamak zordur
    • Python’un yaratıcısının yazdığı find_shortest_path algoritması daha sonra beş kez düzeltildi
    • Nicole, incelediği tüm PageRank uygulamalarının hatalı olduğunu söylüyor
    • NetworkX yaklaşık 500 grafik algoritması sunuyor ve yalnızca algoritma kodu bile neredeyse 60.000 satır tutuyor
    • Python standart kütüphanesinin tamamı yaklaşık 300 paket ve 600.000 satırdan az koddan oluşuyor
  • Standart kütüphane bakımcılarının hangi grafik tiplerini, hangi topolojik özel durumları ve hangi algoritmaları dahil edeceğine karar vermesi gerektiğinden, bakım yükü büyüktür
  • Python “batteries included” yaklaşımıyla bilinse de, PEP 594 ile 20 standart kütüphane modülünü kaldırma yönünde ilerliyor

Grafik temsili için de tek bir doğru seçim yok

  • En basit yönlü grafiği düşünsek bile, iç temsil için birden fazla seçenek vardır
    • Edge list: [[a, b], [b, c], [c, a], [c, b]]
    • Adjacency list: [[b], [c], [a, b]]
    • Adjacency matrix: [0 1 0; 0 0 1; 1 1 0]
    • Birbirine referans veren struct kümeleri
  • Temsil biçimine göre işlemlerin performansı değişir
    • 100 düğüm ve 200 kenarlı bir grafiği adjacency matrix ile temsil ederseniz, 100×100’lük matriste 200 tane 1 ve 9.800 tane 0 bulunur
    • Aynı grafiği edge list ile temsil ederseniz, yalnızca 200 düğüm çifti gerekir
    • Dil ve optimizasyon düzeyine bağlı olarak bellek farkı 20 katı aşabilir
  • Tersine, 100 düğüm ve 8.000 kenarlı bir grafikte 0 ile 93 numaralı düğüm arasındaki kenarı arıyorsanız sonuç farklı olur
    • Adjacency matrix ile graph[0][93] üzerinden O(1) erişim mümkündür
    • Edge list ise 8.000 kenarın taranmasını gerektirdiğinden O(|edge|) zaman alır
  • Az kenarlı grafikler sparse graph, neredeyse tüm kenarların bulunduğu grafikler dense graph olarak adlandırılır
  • Dış veriden grafik oluşturan bir program başlangıçta sparse graph üretirken zamanla dense graph haline gelebilir; bu yüzden iç temsil için “her zaman iyi” bir seçim yoktur
  • Düğüm verisi, kenar verisi ve farklı türde düğüm ve kenarları desteklemek, uygulama karmaşıklığını daha da artırır
  • Üçüncü taraf kütüphaneler genelde iki yönden birini seçer
    • Tüm kullanım senaryolarını kapsayan zengin tek bir tip sunar ama verimlilikten ödün verir
    • Temsil biçimine göre ayrı grafik tipleri sunar ve düğüm/kenar verisi yönetimini kullanıcıya bırakır

NetworkX ve Petgraph’ın gösterdiği trade-off’lar

  • NetworkX, düğümlere ve kenarlara keyfi veri eklenebilmesi için grafikleri dict of dict of dict yapısında saklar
  • Başka temsillere dönüştürme işlevleri sunar, ancak doğrudan o temsiller üzerinde çalışma yaklaşımını sunmaz
  • Rust ekosisteminin önde gelen grafik kütüphanesi Petgraph, graph, graphmap, matrix_graph gibi kullanım senaryosuna özel tipler sağlar
  • Bradford, git deposunun tüm geçmişinde secret arayan güvenlik aracı Nosey Parker içinde Petgraph kullanıyor
    • Benchmark grafiği CPython; 250.000 commit ve 1.300.000 object içeriyor
    • Her commit düğümünde yalnızca birkaç kenar bulunduğundan adjacency list seçildi
  • Birden fazla temsili desteklemek, algoritma ekleme maliyetini yükseltir
    • Her temsil için ayrı algoritma yazılırsa bakım yükü 3 ila 4 kat artar
    • Polimorfik tipler üzerindeki genel soyutlamalarla yazılırsa performans düşer
  • Görüşülen kişilerden biri, elde yazılmış bir grafik algoritmasının genel amaçlı bir algoritmadan 20 kattan fazla hızlı olabileceğini tahmin ediyor

Performans kısıtları, grafik kütüphanelerinin temel sorunu

  • Grafik algoritmaları arasında NP-complete ya da daha da zor çok sayıda problem bulunur
    • Karp’ın 21 canonical NP-complete probleminden 14’ü grafik problemidir
  • Grafik problemleri çok büyük girdiler üzerinde çalıştırılabildiğinden, temsil biçimi ve uygulama ayrıntıları işin yapılabilir olup olmayacağını belirler
  • Bradford, Nosey Parker’da her commit için dosya sistemi snapshot’ını yeniden oluşturmak adına object graph üzerinde dolaşmak zorundaydı
    • Petgraph’ın sunduğu dört grafik walker, bu kullanım senaryosuna uygun şekilde genişletilemiyordu
    • Bunun üzerine anlık olarak “semi-novel” bir graph traversal algorithm tasarladı ve bellek kullanımını binde bire indirdi
  • Zayenz, tümünü ele almanın imkânsız olduğu kadar büyük bir grafiğe örnek olarak 15 puzzle’ı veriyor
    • Çözüm arama, durum uzayında A* search çalıştırılarak yapılıyor
    • Durum uzayında 20 trilyondan fazla durum var
    • Tüm düğümleri üretmek, daha baştan başarısız olmak anlamına geliyor
  • Zayenz’in dahil olduğu Gecode constraint solver’a grafik ekleme araştırma projesinde de, genel amaçlı grafik tipi probleme özel temsil seçimiyle rekabet edemedi
  • Grafik veritabanları da karmaşık grafik algoritmaları çalıştırmak için tasarlanmış olsa da performans sorunları sürüyor
    • Nicole’e göre dolaşım sırasında derinlik sınırı konmazsa tüm grafik ziyaret edilmiş oluyor
    • “Üç adım dışarı çık, yol varsa bul” gibi derinlik aramaları bile çok fazla veriyi ziyaret ediyor
  • Nicole, grafik sorgu performansı danışmanlığında çoğunlukla grafik veritabanından ayrılma amaçlı migration projeleri yürütüyor
    • Bir projede yalnızca tek bir hesaplamayı olduğu gibi bırakıp geri kalan her şeyi MapReduce süreci olarak yeniden yazdılar
    • Anlaması daha zor hale geldi ama en azından gece boyunca gerçekten tamamlanabilir oldu

Neden standart kütüphanelerde grafikler nadir

  • Geniş kapsamlı grafik desteğinin nadir olmasının birkaç nedeni üst üste biniyor
    • Çok sayıda grafik türü var
    • Her grafik türü için birçok temsil biçimi var
    • Çok sayıda grafik algoritması var
    • Algoritma performansı temsil ve uygulama ayrıntılarına hassas
    • İnsanlar çok büyük grafikler üzerinde çok pahalı algoritmalar çalıştırıyor
  • Dil standart kütüphaneleri, çok sayıda tasarım kararı, trade-off ve bakım yükünü üstlenmek zorunda kalıyor
  • Programcıların üçüncü taraf grafik kütüphanelerinden kaçınmasının da nedenleri var
    • Kütüphane fazla sınırlı olabilir
    • Genel amaçlı kütüphane performans gereksinimlerini karşılamayabilir
  • Grafikler sistem analizi için faydalı olsa da, uygulama aşamasında veri temsili ve algoritma seçimini doğrudan kontrol etmek çoğu zaman gerekiyor

Ek: Grafik tipi sunan diller ve ilgili araçlar

  • Graph query language (GQL), grafik veritabanlarında SQL’in karşılığı olan rolü üstlenir
    • Yaygın olarak kullanılan tek bir standart yoktur; öne çıkan örnekler SPARQL ve Neo4j’nin Cypher
    • Buradaki GQL, geliştirilmekte olan GQL standart diliyle karıştırılmamalıdır
  • GraphQL bir graph query language değildir; adı Facebook Graph Search ile olan bağlantısından gelir
  • GQL ile SQL arasındaki temel fark, ilişkilerin yani “join”lerin birinci sınıf varlıklar olmasıdır
    • Film ve insan veri kümesinde SQL, “oynadı”, “yönetti”, “yapımcılığını üstlendi” ilişkilerini ayrı many-to-many tablolarla ifade eder
    • SPARQL’de ilişkiler kenar olduğu için “Y filminde herhangi bir rolde yer alan kişiler ve o roller” kolayca sorgulanabilir
  • GQL; kenar ters çevirme, bileşim ve transitive closure gibi kenar işlemlerini de destekleyebilir
    • SPARQL, yol uzunluğu ya da yol üzerindeki hesaplamaları, örneğin iki oyuncuyu bağlayan film zincirini toplama gibi işlemleri desteklemez
    • Bunu destekleyen bir GQL çok daha karmaşık hale gelir
  • Biçimsel belirtim dili Alloy, relation veri tipi üzerinde kullanışlı grafik dolaşım primitive’lerine sahip olduğundan grafik temsilleriyle uğraşmayı genel amaçlı programlama dillerine göre daha kolaylaştırır
    • Ancak bu primitive’ler etiketli kenarlara dayanır ve başka grafik temsillerine uymayabilir
  • Python, 2020’de graphlib’i ekledi
    • TopologicalSorter dışında yöntem yoktur
    • Grafik yalnızca düğüm dict’i olarak alınır
    • a -> b grafiği, {b: [a]} gibi ters yönde bir dict ile ifade edilir
  • 2023 itibarıyla CPython içinde graphlib kullanılmıyor
    • GitHub’da graphlib referansı içeren dosya sayısı 900’ün altında
    • Aynı yıl eklenen zoneinfo ise 6.000’den fazla dosyada geçiyor
    • def topological_sort( ifadesi 4.000 dosyada yer alıyor
    • Elle yazılmış topological sort uygulamaları çoğu zaman graphlib’den farklı grafik temsilleri kullandığı için dönüştürmeleri zor oluyor
  • Standart kütüphanede grafik tipi bulunan diğer örnekler arasında Erlang ve SWI-Prolog var
  • “Her şey grafiktir” yaklaşımını benimseyen programlama dilleri de var
    • Örnek olarak GP2 ve Grape verilebilir
    • Bunlar bugün hâlâ oldukça akademik bir alanda kalıyor
  • Mathematica, MATLAB ve Maple gibi matematik yazılım dilleri de bir şekilde grafik kütüphaneleri barındırıyor
  • 18 Mart 2024 güncellemesiyle, yazıya gelen bazı yorumlar ayrı bir sayfada toplandı

İlgili okumalar

1 yorum

 
GN⁺ 2024-03-05
Hacker News yorumları

  • Graphviz'in, başka projelerin kullanmadığı kendine ait bir temel grafik kütüphanesi var; bunun hem artıları hem eksileri vardı
    Bu deneyimden hareketle biz de tipik bir ikinci sistem sendromu yaşadık. Modüler, tip güvenli ve verimli bir grafik kütüphanesi yapmak istedik, ama sonuçta bu muhtemelen “iyi, hızlı, ucuz — ikisini seç” sözünün bir varyasyonuydu
    Modüler derken, grafik algoritması kütüphaneleri paketlerinin birbirinden bağımsız geliştirilebilmesini ve derlenebilmesini kastediyorduk; tip güvenli derken de “düğümde color özelliği yok” gibi çalışma zamanı hataları yerine programlama hatalarını derleme sırasında, en geç de bağlama aşamasında yakalamak istiyorduk
    Verimli derken de grafik özelliklerine erişim maliyetinin C struct alanı erişimi kadar ucuz olmasını kastediyorduk; yanımızda harici hash table taşımak ya da bolca string dönüşümü yapmak istemiyorduk
    Bu hedeflerin bedeline değip değmediği, hatta anlamlı olup olmadığı tartışılabilir; ama o zaman istediğimiz buydu. Laboratuvarda ünlü C++ yaratıcıları vardı ve C++'a bir şans daha vermeyi düşünüyorduk
    Önce stajyer olan, sonra birlikte çalışmayı sürdüren Gordon Woodhull çok yetenekli bir programcıydı ve template C++ ile böyle bir grafik kütüphanesi gerçekleştirmesi yazdı. Kaynak kodu da https://www.dynagraph.org/ adresinde duruyor
    Geri kalanımız bu kodun nasıl çalıştığını gerçekten anlayıp anlayamayacağımızdan emin olamadığımız için ünlü C++ mucitleriyle code review yaptık; sayısız kod ekranı ve sessizlikten sonra varılan sonuç “muhtemelen çalışır” oldu. O anda artık karmaşıklık uçurumunun ötesine geçmiş olabileceğimizi anladık
    Derleme zamanı template hataları, tek bir hatanın tüm ekranı kaplayıp yalnızca C++ mucitlerinin sevebileceği ayrıntılar saçmasına yol açıyordu. Hata bizdeydi; Gordon ise ilerlemeyi sürdürdü ve dinamik grafik yerleşimini Microsoft OLE üzerinde bile çalışır hale getirdi
    Geriye dönüp bakınca bu biraz bizim kendi Project Xanadu'muzmuş; biz orada kaybolurken Gephi(Java), NetworkX ve NetworKit(Python) gibi şeyler çıktı. Graphviz'in bazı bölümlerini yazan parlak yazılım mühendisi John Ellson, ana akım çalışmayı yeniden canlandırdı

    • Graphviz dot sözdizimi NetworkX ile parse edilip pahalı araç çalıştırma planları yapılabiliyor; grafik yapısı sayesinde de otomatik paralelleştirme mümkün oluyor

  • Grafiklerle çok çalışmış biri olarak, “programlama dillerinde neden yerleşik bir grafik veri tipi yok?” sorusunu sayısız kez duydum
    Artık sadece “bunu iyi yapmak gerçekten zor” demek yerine, bu yazı gibi daha derin analizlere işaret edebiliyor olmak hoşuma gidiyor

    • Bu sorunun biraz komik yanı, çoğu kişinin dillerin büyük kısmında ağaç veri yapısı bile olmadığını gözden kaçırması
      Çoğu dilin yapısal tip olarak sunduğu şeyler temelde statik dizi, dinamik dizi ve bağlı listeyle sınırlı. İkili arama ağacı ya da hash table gibi şeyler, alttaki yapının bazı yeteneklerini gizleyen anlamsal soyutlamalar; saf yapısal gösterimler değiller
    • Grafikler, gereksinimlere göre gösterim biçimi büyük ölçüde değişen geniş bir veri yapısı alanı olduğu için, bunları alan/donanım değil, doğrudan problem alanı düzeyinde gerçekleştirmek daha mantıklı diye düşünürdüm
      Yazıdaki “uygulama seçenekleri çok fazla” kısmı da aynı şeyi söylüyor. Sonra Petgraph [0]'ı görünce ilk kez genel amaçlı bir grafik kütüphanesine gerçekten baktım ve oldukça ilginç buldum; ama yine de grafikleri alan düzeyinde gerçekleştirmeyi sürdürdüm
      [0] https://github.com/petgraph/petgraph
    • Ters bir deneyim de yaşadım. Tcl'de ilk grafik işimi yaparken standart kütüphanede grafik algoritmaları olmayacağını varsaydım, ama meğer varmış; böylece tekerleği yeniden icat etmek zorunda kalmadım
      https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tclli...
    • “Bunu iyi yapmak gerçekten zor”dan da önemli olan şey, çok sayıda trade-off bulunması
      Neredeyse bütün diller hash map sağlar; belirli durumlarda bunu elle gerçekleştirerek daha hızlısını yapabilirsiniz ama varsayılan uygulama genellikle yeterince iyi çalışır. Grafiklerde bunu yapmak zordur; mümkünse belki birden fazla grafik tipi sunmak bile gerekir
      Ek olarak, Java'nın HashMap'i, diğer çoğu dilden farklı olarak yük faktörünün ayarlanabilmesi bakımından biraz sıra dışıdır
    • Belki çok safça bir düşünce ama pointer'ların fiilen yerel grafik tipi olduğunu düşünüyorum
      İnsanların gerçekten istediği şey grafik tipinin kendisi değil, grafiği dolaşmaya yarayan araçlar gibi görünüyor

  • Grafiklerin bir veri yapısı ya da veri tipinden çok bir soyutlama olduğunu düşünüyorum
    Temelde bir grafiği tanımlamak için gereken tek şey köşe kümesi v \in V ile Neighbors(v) fonksiyonudur ve çoğu temel grafik algoritması için gerçekten bu kadarı yeterlidir
    Geri kalanı örneğe özgü kısıtlardır. A->B'nin B->A anlamına gelip gelmediği, düğüm kümesinin belli kısıtlar altında bölünüp bölünemeyeceği, renk ya da etiket bulunup bulunmadığı gibi şeylerdir
    Daha da genelleştirirseniz hipergraph'a kadar çıkabilirsiniz; bu durumda bir köşe kümesiyle köşe kümelerinin kümesi yeterli olur. İlgi alanına göre sayısız biçimde temsil edilebilir ve sıradan grafik bunun sadece özel bir durumudur
    Veritabanı açısından bakıldığında bu, bir sorgu optimizasyonu ve indeksleme problemi olarak da görülebilir. Grafiğe hangi soruları sormak istediğinize bağlı olarak, daha iyi yanıt verecek temsil biçimi değişir. Nasıl ki “tablo” soyutlamasının tek bir gösterim biçimi yoksa, “grafik” de tek bir biçimle sınırlı değildir

    • Grafiklerin her yerde olmasının nedeni, bu kadar soyut olmaları
      Saf sayılarla aynı soyutlama düzeyindeler. Yararlı “sayısal” kütüphaneler olduğu gibi yararlı “grafiksel” kütüphaneler de olabilir; ama “sayı” kütüphanesi ya da “grafik” kütüphanesi pek olmaz. Böyle kavramlar bir API üretmek için fazla soyuttur
    • Köşe kümesi ve Neighbors(v) bile aslında oldukça kısıtlayıcıdır. Çünkü aynı komşuya giden çoklu kenarlara izin vermez
    • Eğer hipergraph bir köşe kümesi ile köşe kümelerinin kümesiyse, bu biraz dosya sistemi gibi de geliyor
      Dosyalar köşeler, dizinler ise iç içe geçebilen köşe kümeleri oluyor

  • İki temel engel var
    Basit ve küçük grafik problemlerinde, vektörlerin vektöründen oluşan bir komşuluk listesini doğrudan yazmak zaten yeterince kolay; karmaşık ve devasa grafik problemlerinde ise performans almak için grafik uygulamasını çözülmek istenen problemin ayrıntılarına göre özel olarak üretmek gerekiyor
    Bu yüzden hangi dil desteğinin yardımcı olacağı pek net görünmüyor. Kodu analiz edip komşuluk listesi, matris, 3 boyutlu dizi vb. arasından hangisinin en iyi olduğuna karar veren aşırı akıllı bir derleyici yoksa iş zor. Böyle optimizasyonları derleyicilerde bir süre daha görmek zor olacak
    Bu, Stroustrup'un gözlemlediği olgunun bir başka örneği. Vektör gibi küçük şeylerle işletim sistemi gibi büyük şeylerde kod paylaşımını iyi yapıyoruz, ama orta ölçekli problemleri iyi paylaşamıyoruz

    • Küçük şeyleri de gerçekten çok iyi paylaşıyoruz demek zor. Çünkü her programlama dilinin kendi vektör implementasyonu var
      Tek bir dil ekosistemi içinde vektör API'si küçük olduğu için paylaşım kolaymış gibi görünüyor. İşletim sistemlerinde de API, iç karmaşıklığa kıyasla görece küçük; sayısal hesaplama kütüphanelerinde de durum benzer, bu yüzden paylaşım iyi çalışıyor
      Buna karşılık karmaşık veri yapılarında olduğu gibi daha fazla özelleştirme istedikçe API karmaşıklaşıyor ve paylaşım zorlaşıyor. Sonuçta paylaşılabilirlik, paylaşılan şeyin yüzey alanına, yani API'nin göreli büyüklüğüne bağlı gibi görünüyor
    • Soyut grafik tiplerine karşı yazılmış algoritmalara bakıp belirli bir algoritmaya uygun şekilde implementasyonu doldurarak optimize etme işi, kod özelleştirme LLM'leri için oldukça uygun bir alan gibi görünüyor

  • Electric Clojure, Clojure'un kendi s-ifadelerini graf yazım sözdizimi olarak kullanıyor ve makrolarla reaktif istemci/sunucu sistemlerinin veri akışını somutlaştırıyor
    Burada kullanım örneği full-stack kullanıcı arayüzleri ama fikir genellenebilir. https://github.com/hyperfiddle/electric kurucusuyum
    “Graf tipleri nereye kayboldu?” sorusunun cevabı bence şu: graf yazım DSL'sinin kapsamı, kontrol akışını ve soyutlamayı ifade etmesi gerekir; bunu yapınca da aslında değerlendirme modelinden bağımsız bir programlama diliyle izomorfik hale gelir. Python ve TypeScript'te araya tam teşekküllü bir programlama dili sıkıştırmak oldukça zor
    “Four problems preventing visual flowchart programming from expressing web applications” başlıklı blog yazısına da bakmaya değer
    https://www.dustingetz.com/#/page/four%20problems%20preventi...

  • Bu yazı esas olarak “programlama dilleri neden graf algoritmalarını daha iyi desteklemiyor?” sorusuna yanıt veriyor ve genel grafik desteğinden çok “büyük veri” grafik işlemeye odaklanıyor gibi görünüyor
    Grafik desteğine genel olarak bakınca “neden OGM(Object Graph Mapper), ORM kadar popüler değil?” ve “neden JSON yaygınken RDF ya da diğer düşük seviyeli grafik serileştirme biçimleri değil?” gibi daha geniş sorular da buna dahil
    Sonuçta tarihsel nedenlerin ağırlığı büyük diye düşünüyorum. RDF biraz fazla erken çıktı, düzgün biçimde evrilemedi ve korkunç bir akademik standart ile implementasyon ekosistemi biriktirdi. Buna bir de grafiklerin implementasyon ve öğrenme eğrisi açısından doğası gereği biraz daha karmaşık olması eklenince, birçok geliştirici için iyi ölçeklenmiyor
    Yazının “Graph Querying Language” bölümüne fazla ağırlık vermezdim. Bazı kısımlar, Neo4J ya da SPARQL'i coşkuyla kullanan birinin gerçek ürün geliştirmeden yazdığı pazarlama metni gibi duruyor
    “Tüm GQL ile SQL arasındaki temel fark, join yani ilişkilerin birinci sınıf varlık olmasıdır” deniyor ama SQL'de de join birinci sınıf bir varlıktır. Hatta JOIN diye bir anahtar sözcük bile var
    Grafik sorgu dillerinin daha alt katmanına, yani sorgu planlarına indiğinizde SQL tabanlı sorgulardan anlamlı bir fark pek kalmıyor. GQL[0] standardizasyonunun SQL uzantısı olarak ilerlemesi de bunun kanıtı
    SPARQL, tam yol dolaşımı gerektiğinde kolay; ama web uygulaması arka ucunda yapılacak biraz daha karmaşık işlere girince, bağlanmamış değerlerle join yapmak gibi tüm sonuç kümesini yanlışlıkla yok eden tuzaklara hızla çarpıyorsunuz
    [0]: https://en.wikipedia.org/wiki/Graph_Query_Language

    • Kendi anahtar sözcüğünün olması aslında bir şeyin birinci sınıf nesne olmadığının güçlü bir kanıtı sayılabilir
      Örneğin Haskell'deki type class'lar birinci sınıf değildir; çoğu programlama dilinde kontrol akışı da birinci sınıf değildir
    • JOIN, özellikle RECURSIVE sorgulardaki join, graf veritabanlarının merkezindedir ve SQL ilişkisel veritabanları da bunu genel olarak iyi işler
      Sadece sözdizimsel bir kısayol yoktur; grafik sorgu dilleri de özünde bu kısayolları eklemeye odaklanır

  • Grafik çizim araçları da epey hayal kırıklığı yaratıyor. Küçük grafiklerde iyi çalışıyorlar ama düğüm sayısı 500 civarını geçince çıktı tamamen anlaşılmaz hale geliyor ya da okunması çok zorlaşıyor
    Grafiği hiyerarşik yapıda otomatik düzenleme ve keşfetmeye uygun bir arayüz sunma konusunda yetersizler. Etrafımızdaki her şeyi bir ölçüde hiyerarşik yapı olarak görmeye alışkın olduğumuzu düşünürsek, genel amaçlı bir grafik veri türü oluştururken de aynı tür sorunların çözülmesi gerekiyor gibi görünüyor
    Bu tür şeylerin derleyici düzeyinde uygulanması ve genel amaçlı grafik algoritmalarının üretilen yapı hiyerarşisine uyum sağlaması gerekebilir. Buna bir ispat denetleyicisi eklenip belirli alt grafiklerin her zaman belirli bir yapıya sahip olduğu doğrulanabilirse, ilgili prosedür statik olarak üretilebilir; geri kalan üst düzey grafik içinse çalışma zamanında dinamik olarak üretilebilir
    Dolayısıyla genel amaçlı grafik çizimi sorununu çözen kişi, bu sorunu uygulayacak yetenek veya içgörüye de sahip olacaktır

    • Grafik çizimi zordur
      Daha fazla seçenek ve kontrol sunan, Graphviz benzeri genel amaçlı grafik çizim kütüphaneleri
      https://eclipse.dev/elk/
      Kiel University'de ELK geliştirme ekibinin yürüttüğü deney
      https://github.com/kieler/KLighD
      Kieler proje vikisi
      https://rtsys.informatik.uni-kiel.de/confluence/display/KIEL...
      Kısıt tabanlı grafik çizim kütüphanesi
      https://www.adaptagrams.org/
      JavaScript uygulaması
      https://ialab.it.monash.edu/webcola/
      İlginç bir kaynak: HOLA: Human-like Orthogonal Network Layout
      https://ialab.it.monash.edu/~dwyer/papers/hola2015.pdf
      Confluent Graphs demosu kenarları daha okunabilir hale getiriyor
      https://www.aviz.fr/~bbach/confluentgraphs/
      Stress-Minimizing Orthogonal Layout of Data Flow Diagrams with Ports
      https://arxiv.org/pdf/1408.4626.pdf
      Improved Optimal and Approximate Power Graph Compression for Clearer Visualisation of Dense Graphs
      https://arxiv.org/pdf/1311.6996v1.pdf
    • Bazı algoritmalar bu sorunu daha iyi ele alıyor, ancak genel durumda “grafiğin iyi bir diyagramını oluşturmak” zekâ-tam bir probleme yakın
      Yapısal olarak aynı grafik bile, iki kişinin verinin farklı yönlerini vurgulamak istemesi nedeniyle tamamen farklı biçimde görselleştirilebilir. Bu, “genel amaçlı grafik algoritması” ve “genel amaçlı grafik veri yapısı” sorununa da benziyor
      Grafikler kod ve veri arasındaki sınırda yer alır. Örneğin her programın bir çağrı grafiği vardır; dolayısıyla bir bakıma “genel amaçlı grafik algoritması” doğrudan hesaplamanın kendisidir
    • İdeal olanlar çoğunlukla ağaç gibi görünür, ama gerçek dünyanın yapıları iyi düzenlenmiş olsalar bile genellikle yönlü çevrimsiz grafiktir
      Düğüm sayısı birkaç onu geçtiğinde bile bunu düzlemsel hale getirmek ya da kesişmeleri azaltıp ilişkili düğümleri iyi gruplayarak neredeyse düzlemsel görünmesini sağlamak genelde zordur
    • Asıl büyük sorunun, her şeyin hiyerarşik olduğuna dair yanılsamaya alışmış olmamız olduğunu düşünüyorum
      Gerçekte neredeyse hiç hiyerarşik olmayan şeyleri grafik çiziminin uzlaştırması gerekiyor ve nereden sonrasının hiyerarşi sayılacağını matematiksel olarak katı biçimde belirlemek zor. Altta yatan grafik yapısı hakkında bağlantılılık, çevrim içerip içermeme, seyreklik gibi varsayımları ne kadar azaltırsanız bu sorun o kadar kötüleşir
      Pratikte grafiklerle etkileşen bir UI yaparken genellikle bir veya iki katmanlı meta hiyerarşi belirlenir ya da zorlanır; böylece kümeleme yapılabilir, hairball düğümlerin yerleşimi bozma etkisi azaltılır ve düğüm sayısı düşürülerek render performansı da iyileştirilebilir. Yerleşim için fCOSE kullanılabilir; Cytoscape.js uygulaması da vardır
    • Sinir ağı çizimlerine bakınca, büyük ölçekli grafik görselleştirmenin ne kadar bütünüyle anlaşılması güç hale geldiği açıkça görülüyor

  • Temel gözlem olan “uygulama seçeneği çok fazla” ifadesinin tamamen doğru olduğunu düşünmüyorum
    Aslında bir kütüphane uygun tüm grafik gösterimlerini uygulayabilir, her gösterim için performansı en iyi algoritmaları sunabilir ve gösterimler arasında dönüşüm sağlayabilir. Bu dönüşümler gösterim sayısıyla orantılıdır ve hem uygulaması hem kullanımı basit olduğundan, bakımcılar ve kullanıcılar için oldukça makul bir yüktür
    Buna ek olarak standart kütüphane veri türleri ve deyimlerinden içe/dışa aktarma dönüşümleri de sağlanabilir. Bellek ve dönüşüm maliyeti ucuzdur; kullanım durumlarının %99’unda veri dönüşüm ek yükü hem RAM hem de CPU açısından muhtemelen göz ardı edilebilir
    Bu arada “Google’da çalışmanın acı gerçeği, sonuçta protobuf’u bir yerden başka bir yere taşımaktan ibaret olmasıdır” sözü de aklıma geliyor
    https://news.ycombinator.com/item?id=20132880

    • Bu yapılırsa devasa bir kütüphane olur gibi geliyor ve kendi işimde kullanacağımdan emin değilim. Grafikleri çok kullanıyorum ama deneyimim yazarın görüştüğü insanlara benziyor
      Sonuçta grafiği hep yeniden uyguluyoruz. Performans önemli ve gördüğüm hazır grafik kütüphaneleri veri kümemizdeki düzenlilikten yararlanamıyordu. Örneğin biz append-only DAG kullanıyoruz ve neredeyse tüm düğümlerin yalnızca en son eklenen öğeyi işaret eden tek bir kenarı var; bu yüzden dahili olarak run-length encoding mümkün
      İhtiyacımız olan sorguları destekleyen genel amaçlı bir grafik kütüphanesi de görmedim. Özellikle büyük eksiklerden biri subgraph diff fonksiyonu
      Üstelik özel uygulama o kadar da fazla iş değil. Grafikleri yeniden uygulamak B-tree’den çok daha kolay ve basit bir uygulama birkaç düzine satırda yazılabilir. Desteklenen algoritmaları da içeren yüksek derecede optimize edilmiş bizim kütüphanemiz bile birkaç yüz satır civarında
      Veriyi standart bir biçimde dışa aktarmanın bir yolu olsa hoş olurdu ama bizim kullanım durumumuzda bir kütüphane eklemek çözmekten çok sorun çıkaracak gibi duruyor

  • Aklıma sık sık gelen eksik uygulama grafikler için Excel
    Tablolu veriler için Excel gibi, RAM’e sığacak kadar veriyi yani bir bilgisayar gerektiren ama veri merkezi gerektirmeyen ölçekteki işleri ele alan, birçok algoritma ve görselleştirmeyi “yeterince iyi” düzeyde uygulayan ve programlama bilgisi olmadan kullanılabilen bir araç
    Yazıda dendiği gibi gerçek dünyadaki birçok sorun grafik sorunuysa, neden bu sorunları çözebilecek araçlara yalnızca programcılar sahip olsun

    • Bence yazı sonuca fazla hızlı varıyor. Gereksinim ekledikçe başka birçok sorunu da istediğiniz kadar karmaşık ve zor hale getirebilirsiniz
      Yine de çoğu kullanım durumuna yeterince uyan veri yapıları ve standart kütüphaneler vardır; özellikle uç gereksinimler varsa özel çözüm yapılır
      Yazı grafiklerin çoğu zaman çok büyük olduğunu söylüyor ama grafik algoritmalarıyla gerçekten uğraşan insanlara sorarsanız böyle deneyimler yaşamanız doğaldır. Programcıların ve kullanıcıların çoğu muhtemelen gerçekten çok küçük grafiklerle uğraşır
    • Bence bu tür sorunları grafik olarak modelleyen sadece programcılar ve matematikçiler
      Sıradan kullanıcıların rastgele gerçek dünya sorunlarında grafik gördüğünü sanmıyorum. Büyük şirketlerde çalışırken öğrendiğim şey, yeterince uğraşırsanız her şeyin bir Excel tablosuna dönüşebileceği oldu
    • Tam olarak istenen şey bu değil ama https://gephi.org/ birçok grafik görselleştirme algoritmasını uyguluyor
      https://strlen.com/treesheets/ ise ağaç verileri için Excel’e daha yakın
    • Yazı, “birçok gerçek dünya sorunu grafik sorunudur” iddiasını yeterince desteklemiyor
      Örneğin internetin grafik olarak modellenebileceğini söylüyor ama bu doğru olsa bile bunun ne işe yaradığı belirsiz. İnternet birçok şekilde temsil edilebilir ve grafik olarak temsil etmenin genel olarak faydalı mühendislik sonuçları doğurduğu açık değil
      Faydalı bilgi elde etmek için ideal temsilin, rastgele girdileri tutarlı çıktılara eşleyen bir kara kutu matris kodlama fonksiyonu yani bir sinir ağı olduğunu söylemek de benzer derecede ikna edici olurdu
      Google gibi yerlerde bu milyarlarca dolarlık bir fikir olabilir ama internetin tamamı birçok insan için bir grafik sorunu değil ve onu grafik olarak ifade etmek çok şeyi çözmüyor
      Gerçek dünya sorunlarını kâğıt üzerinde grafikle çözen insan azdır. Tablolar sürekli kullanılır. Grafikler yaygındır ama grafik sorunları yaygın değildir
    • Bence buradaki kilit nokta VR
      Diğer yorumlarda da grafik görselleştirmenin zor olduğu söylenmişti ama 3D arayüzler çok daha fazla alan sunuyor. VR patlaması başladığında “VR’ın Excel’i ne olacak?” diye düşünmüştüm; Microsoft’un cevabı “3D uzayda yüzen 2D elektronik tablolar” olmuştu. Bana saçma geliyor. Bence cevap grafikler
      Bunu birlikte keşfetmek isteyen varsa kullanıcı adım at gmail.com adresine yazabilir

  • Grafik türleri aslında epey uzun zamandır vardı
    Erlang’da https://www.erlang.org/doc/man/digraph.html ve https://www.erlang.org/doc/man/digraph_utils var; küme kuramı temelli işler yapmak istiyorsanız https://www.erlang.org/doc/man/sofs.html da mevcut

    • Yazının sonunda Erlang’a kısaca değiniliyor
      “Grafik türüne sahip diğer iki dil olarak Erlang ve SWI-Prolog’u buldum. İkisini de çok iyi bilmediğim için ne zaman eklendiklerini söyleyemem ama Erlang’da en azından 2008’den önce vardı. Erlang çekirdek dil komitesinden birine ulaştım ama yanıt alamadım” deniyor
    • Elixir için de oldukça iyi bir grafik kütüphanesi var: https://hexdocs.pm/libgraph/api-reference.html
      Bunu görev sırasını belirlemek için dependency resolution işinde kullanmıştım
    • Bunun farklı durumlarda ne kadar esnek olduğu ve performansının ne kadar iyi olduğu ilgimi çekiyor