Skip to content

Instantly share code, notes, and snippets.

@kozmotronik

kozmotronik/gridKomsulukCozum.c

Last active May 5, 2024 15:33
Show Gist options
  • Save kozmotronik/fa8bdc032b6b77a30a79bb068a95f3f0 to your computer and use it in GitHub Desktop.
Save kozmotronik/fa8bdc032b6b77a30a79bb068a95f3f0 to your computer and use it in GitHub Desktop.
Download ZIP
Grid Komşuluk Bulma Çözümü - https://youtu.be/sL471VjO3JU?si=jEe5BDqxN5hO4_PV videosundaki mülakat sorusu için iki çözüm.
Raw
gridKomsulukCozum.c
/**
* \file gridKomsulukCozum.c
* \author kozmotronik (İsmail Sahillioğlu)
*
* https://youtu.be/sL471VjO3JU?si=jEe5BDqxN5hO4_PV adresindeki videoda sorulan bir mülakat
* sorusuna C dili ile yazdığım 2 farklı çözüm.
*
* 1. Çözüm gridKomsulariBulV1
* Bu çözümde 4 adet iç içe çalışan döngü ile grid tablosunun satır ve sütün genişliklerine
* göre indekslerin birbirleriyle ilişkisi yoklanarak komşuluklar tespit edilmektedir.
*
* 2. Çözüm gridKomsulariBulV2
* Bu çözümde ise iç içe döngü sayısı üçe düşürülürek işlemin zaman kompleksliğinin azaltılması
* amaçlanmış ancak bu; grid ve matrix tabloları arasında indeks dönüşümlerinin artmasına
* dolayısıyla da daha fazla hesaplama ile sonuçlanmıştır.
*
* Ancak bundan daha iyi çözümler üretebilecek arkadaşlar olduğunu düşünüyorum. Başka çözümleri de
* görmeyi çok isterim doğrusu.
*
***************************************************************************************************
*
* BENCHMARKING
* Benchmarking işlemi doğrudan kod içerisinde olup yalnızca algoritmaların ölçümü yapılmıştır.
* Benchmarking 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.
* Kendi sistemimde yaptığım testlerin sonuçları şöyle:
*
* Algoritma | Benchmark (nanosaniye)
* ---------------------------------------------
* gridKomsulariBulV1 | 1779
* ---------------------------------------------
* gridKomsulariBulV2 | 1651
*
*
* Bu kodun çalıştırıldığı sistem özellikleri:
* -------------------------------------------------------------------------------------------------
* İş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
*
* İş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
*/
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define GRIDSTR 3
#define GRIDSTN 2
#define MATRIXBOYUT 6
int grid[][GRIDSTN] = { {9,4}, {6,3}, {5,8} };
int matrix[MATRIXBOYUT][MATRIXBOYUT];
void matrixYazdir(int *matrix, int satirSayisi, int sutunSayisi) {
putchar('\n');
for (int str = 0; str < satirSayisi; str++) {
if(str == 0) {
for(int s = 0; s < sutunSayisi; s++) {
if(s == 0) printf(" ");
printf("%d ", s);
}
putchar('\n'); // Alt satıra geç
}
for (int stn = 0; stn < sutunSayisi; stn++) {
if(stn == 0) {
printf("%d ", str);
}
printf("%d ", *( matrix + str*sutunSayisi + stn));
}
putchar('\n'); // Bu satır bitti, alt satıra geç
}
}
void gridKomsulariBulV1() {
int matrixDikeyIndex = 0;
do {
for (int i = 0; i < GRIDSTR; i++) {
for (int j = 0; j < GRIDSTN; j++) {
int matrixYatayIndex = 0;
for(int k = 0; k < GRIDSTR; k++) {
for(int l = 0; l < GRIDSTN; l++) {
int strFark = abs(k - i);
int stnFark = abs(l - j);
if(k == i && stnFark == 1) {
matrix[matrixDikeyIndex][matrixYatayIndex] = 1;
}
else if(l == j && strFark == 1) {
matrix[matrixDikeyIndex][matrixYatayIndex] = 1;
}
else {
matrix[matrixDikeyIndex][matrixYatayIndex] = 0;
}
++matrixYatayIndex;
}
}
matrixDikeyIndex++;
}
}
} while(matrixDikeyIndex < MATRIXBOYUT);
}
void gridKomsulariBulV2() {
for(int a = 0; a < GRIDSTR; a++) {
for(int b = 0; b < GRIDSTN; b++) {
// Grid satır ve sütun indeksinden matrix satır indeksini hesapla.
int matrixstr = a * (GRIDSTR - 1) + b;
int strind = 0; // Grid satır indeksi
int stnind = 0; // Grid sütun indeksi
for(int c = 0; c < MATRIXBOYUT; c++) {
if(stnind >= GRIDSTN) {
stnind = 0;
strind++;
}
int satirKomsu = stnind == b && abs(strind - a) == 1;
int sutunKomsu = strind == a && abs(stnind - b) == 1;
matrix[matrixstr][c] = satirKomsu ^ sutunKomsu;
stnind++;
}
}
}
}
int main(void) {
// Matrix tablosunu temizle
memset(matrix, 0, sizeof(matrix[0][0]) * MATRIXBOYUT * MATRIXBOYUT);
matrixYazdir(grid[0], GRIDSTR, GRIDSTN); // Grid tablosunu yazdır
matrixYazdir(matrix[0], MATRIXBOYUT, MATRIXBOYUT); // Matrix tablosunun başlangıç durumunu yazdır
// Benchmarking
struct timespec bas, son;
if(clock_gettime(CLOCK_REALTIME, &bas) == -1) {
fprintf(stderr, "clock_gettime %d kodu ile hata verdi\n",errno);
exit(EXIT_FAILURE);
}
// Benchmarking
gridKomsulariBulV1();
// Benchmarking
if(clock_gettime(CLOCK_REALTIME, &son) == -1){
fprintf(stderr, "clock_gettime %d kodu ile hata verdi\n",errno);
exit(EXIT_FAILURE);
}
double gecenv1 = (double) (son.tv_nsec -bas.tv_nsec);
// Benchmarking
puts("\nAlgoritma v1 sonuç:");
matrixYazdir(matrix[0], MATRIXBOYUT, MATRIXBOYUT);
// Sonraki algoritma için matrix tablosunu yeniden temizle
puts("\nAlgoritma v1 sonuçları temizleniyor...");
memset(matrix, 0, sizeof(matrix[0][0]) * MATRIXBOYUT * MATRIXBOYUT);
matrixYazdir(matrix[0], MATRIXBOYUT, MATRIXBOYUT); // Matrix tablosunun başlangıç durumunu yazdır
// Benchmarking
if(clock_gettime(CLOCK_REALTIME, &bas) == -1) {
fprintf(stderr, "clock_gettime %d kodu ile hata verdi\n",errno);
exit(EXIT_FAILURE);
}
// Benchmarking
gridKomsulariBulV2();
// Benchmarking
if(clock_gettime(CLOCK_REALTIME, &son) == -1){
fprintf(stderr, "clock_gettime %d kodu ile hata verdi\n",errno);
exit(EXIT_FAILURE);
}
double gecenv2 = (double) (son.tv_nsec -bas.tv_nsec);
// Benchmarking
printf("\nV1 Algoritması çalışma süresi (nanosaniye): %f\n",gecenv1);
printf("\nV2 Algoritması çalışma süresi (nanosaniye): %f\n",gecenv2);
puts("\nAlgoritma v2 sonuç:");
matrixYazdir(matrix[0], MATRIXBOYUT, MATRIXBOYUT);
exit(EXIT_SUCCESS);
}
// Beklenen çıktı
//
// 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment