Grid Komşuluk Bulma Sorunu ve Çözümü

GridKomsulukBulmaSorunuVeCozumu.md

Grid Komşuluğu Tablosu

Gridin Yapısı

 9 4
 6 3
 5 8

Sorun

Yukarıdaki yapıda birbiriyle doğrudan komşu olanlar için 6x6 bir matriste karşılık gelen indekse 1, olmayanlar için 0 yazılacak.

  9 4 6 3 5 8 
9 0 1 1 0 0 0 
4 1 0 0 1 0 0 
6 1 0 0 1 1 0 
3 0 1 1 0 0 1 
5 0 0 1 0 0 1 
8 0 0 0 1 1 0 

Çözüm

Bu sorun için iki farklı sürüm yazıldı. Bunlar:

• gridKomsularibulV1
• gridKomsularibulV2

Çözüm koduna buradan ulaşılabilir.

gridKomsularibulV1 Algoritması (İç içe 4 döngülü)

• Matris boyutu kadar döngüde kal.
• Herbir grid elemanı indeksi (sıradaki) için tüm grid elemanlarının indekslerini gez.
• Sıradaki satır indeksi ile bakılan elemanın satır indeksi farkı mutlak(1) ise matriste yatay ve dikey indekse denk gelen hücre değerine 1 yükle.
• Veya sıradaki sütun indeksi ile bakılan elemanın sütun indeksi farkı mutlak(1) ise matriste yatay ve dikey indekse denk gelen hücre değerine 1 yükle.
• Kalan her şey için matriste yatay ve dikey indekse denk gelen hücre değerine 0 yükle.
• Bakılan her eleman için matris yatay indeksini 1 artır.
• Sıradaki her elemana bakıldıktan sonra matris indeksini 1 artır.

gridKomsularibulV2 Algoritması (İç içe 3 döngülü, daha kompakt)

• Gridin satır sayısı kadar dön.
• Gridin herbir sütunü için:
  • Gridin satır ve sütun indeksini Matrisin satır indeksine dönüştür: (matrixstr = a * (GRIDSTR - 1) + b)
  • Matrisin herbir sütunu için:
    • Taranacak grid sütun indeksi (stnind) sona ulaştıysa sıfırla ve taranacak gridin bir sonraki satırına geç; satır indeksini (strind) 1 artır.
    • Satır komşuluğunu yokla. Satır komşuluğu için gereken koşullar:
      • Taranan gridin sütun indeksi ile ana döngünün sütun indeksi aynı ve taranan gridin satır indeksi ile ana döngünün satır indeksi arasındaki fark mutlak(1) olmalı.
    • Sütun komşuluğunu yokla. Sütun komşuluğu için gereken koşullar:
      • Taranan gridin satır indeksi ile ana döngünün satır indeksi aynı ve taranan gridin sütun indeksi ile ana döngünün sütun indeksi arasındaki fark mutlak(1) olmalı.
    • Yoklamaların sonuçlarını XOR (^) işleminden geçirerek matriste hesaplanan indekslere denk gelen yere kaydet.
    • Taranan gridin sonraki sütununa geç (sütun indeksini 1 artır).

Sürümlerin Benchmark Karşılaştırması

Benchmark işlemi doğrudan kod içerisinde olup yalnızca algoritmaların ölçümü yapılmıştır. Benchmark sonuçları donanımdan donanıma ve sistemden (OS) sisteme değişiklik gösterebilir. Hatta aynı sistemde arka arkaya çalıştırılınca herbir çalışma için bile farklı sonuçlar verebilir.

Benchmark ölçmü yalnızca algoritmalara uygulanmış olup ilgisiz yerler hariç tutulmuştur. Kendi sistemimde yaptığım testlerin sonuçları şöyle:

Çözüm sürümü	Benchmark (ns)
gridCozum_v1	1779
gridCozum_v2	1651

Benchmark Testinin Yapıldığı Sistemin Özellikleri

İşletim Sistemi ve Masaüstü

İşletim sistemi: openSUSE Tumbleweed 20240502
KDE Plasma sürümü:* 6.0.4
KDE Frameworks sürümü: 6.1.0
Qt sürümü: 6.7.0
Çekirdek sürümü: 6.8.8-1-default (64 bit)
Grafik platformu: X11

Donanım

İşlemciler: 12 × 11th Gen Intel® Core™ i5-11400H @ 2.70GHz
Bellek: 7,5 GiB RAM
Grafik işlemcisi: Mesa Intel® UHD Graphics
Üretici: ASUSTeK COMPUTER INC.
Ürün adı: ASUS TUF Gaming F15 FX506HF_FX506HF

Çözüm Kodunun Örnek bir Çıktısı

  0 1 
0 9 4 
1 6 3 
2 5 8 

  0 1 2 3 4 5 
0 0 0 0 0 0 0 
1 0 0 0 0 0 0 
2 0 0 0 0 0 0 
3 0 0 0 0 0 0 
4 0 0 0 0 0 0 
5 0 0 0 0 0 0 

Algoritma v1 sonuç:

  0 1 2 3 4 5 
0 0 1 1 0 0 0 
1 1 0 0 1 0 0 
2 1 0 0 1 1 0 
3 0 1 1 0 0 1 
4 0 0 1 0 0 1 
5 0 0 0 1 1 0 

Algoritma v1 sonuçları temizleniyor...

  0 1 2 3 4 5 
0 0 0 0 0 0 0 
1 0 0 0 0 0 0 
2 0 0 0 0 0 0 
3 0 0 0 0 0 0 
4 0 0 0 0 0 0 
5 0 0 0 0 0 0 

V1 Algoritması çalışma süresi (nanosaniye): 1812.000000

V2 Algoritması çalışma süresi (nanosaniye): 1704.000000

Algoritma v2 sonuç:

  0 1 2 3 4 5 
0 0 1 1 0 0 0 
1 1 0 0 1 0 0 
2 1 0 0 1 1 0 
3 0 1 1 0 0 1 
4 0 0 1 0 0 1 
5 0 0 0 1 1 0