<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by İ. Başar YARGICI on Medium]]></title>
        <description><![CDATA[Stories by İ. Başar YARGICI on Medium]]></description>
        <link>https://medium.com/@basar_yargici?source=rss-9b837ce44818------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*9yZqVQJ0sJvIVByVy0Pdyg.jpeg</url>
            <title>Stories by İ. Başar YARGICI on Medium</title>
            <link>https://medium.com/@basar_yargici?source=rss-9b837ce44818------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 06:03:01 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@basar_yargici/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Process - Bir Yazılımın İşletim Sisteminde Yaşam Döngüsü]]></title>
            <link>https://medium.com/folksdev/process-bir-yaz%C4%B1l%C4%B1m%C4%B1n-i%CC%87%C5%9Fletim-sisteminde-ya%C5%9Fam-d%C3%B6ng%C3%BCs%C3%BC-1977987d1084?source=rss-9b837ce44818------2</link>
            <guid isPermaLink="false">https://medium.com/p/1977987d1084</guid>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[operating-systems]]></category>
            <category><![CDATA[threads]]></category>
            <category><![CDATA[process]]></category>
            <category><![CDATA[software-engineering]]></category>
            <dc:creator><![CDATA[İ. Başar YARGICI]]></dc:creator>
            <pubDate>Tue, 01 Nov 2022 17:34:11 GMT</pubDate>
            <atom:updated>2022-12-09T08:34:10.181Z</atom:updated>
            <content:encoded><![CDATA[<h3>Process - Bir Yazılımın İşletim Sistemindeki Yaşam Döngüsü</h3><p>İşletim Sistemlerindeki en önemli konseptlerden ve soyutlamalardan birisi <strong>Process </strong>kavramıdır ve bilgisayardaki çalıştırılabilir tüm yazılımlar bir dizi Process’ten oluşmaktadır.</p><p>Process kavramını daha iyi anlayabilmek adına, bilgi sahibi olunması gereken birkaç temel konu bulunmaktadır:</p><ul><li>Günümüz bilgisayarlarının birçoğunun temel aldığı Von Neumann Mimarisi</li><li>İşletim sisteminin varoluşsal sancıları 😄</li></ul><h3>Von Neumann Mimarisi</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/551/1*Ucdv8XfFGbRqhiGdYbVPow.png" /><figcaption>Von Neumann Mimarisinin Şeması</figcaption></figure><p>Von Neumann<strong> </strong>mimarisini incelemek<strong>, </strong>günümüzdeki bilgisayarların çalışma prensibinin temelini anlamak için güzel bir kaynaktır. Bu mimari, veri ve komutları tek bir depolama biriminde bulundurmaktadır. Von Neumann, bir bilgisayarı oluşturan <strong>3 ana bileşenin</strong> olduğunu savunmaktadır:</p><ul><li><strong>Giriş Çıkış Birimleri (Input/Output Devices):</strong> Kullanıcının komut girmesini sağlayan cihazlara <strong>Input Device</strong>, çıktıları gözlemleyebileceği cihazlara ise <strong>Output Device</strong> denmektedir.</li><li><strong>Bellek (Memory):</strong> İşlenecek bilgilerin depolandığı birimdir.</li><li><strong>İşlemci (CPU):</strong> Bellekten ya da giriş biriminden alınan verinin, makine kodu ile birleştirilerek, üzerinde aritmetiksel ve mantıksal işlemlerin yapıldığı birimdir.</li></ul><blockquote><em>🔗 Von Neumann Mimarisinin detaylarına </em><a href="https://en.wikipedia.org/wiki/Von_Neumann_architecture"><strong><em>buradan</em></strong></a><em> ulaşabilirsiniz.</em></blockquote><h4><strong>İşlemciye Komutlarımızı Nasıl İletiyoruz?</strong></h4><p>İşletim sisteminin olmadığı zamanlarda (<a href="https://en.wikipedia.org/wiki/Computer#Digital_computers">ilk bilgisayar dönemlerinde</a>), komutları bilgisayara giren bilim insanları (benim tabirimle işletim insanları😃) bulunmaktaydı. Bu kişiler delikli kart (Punched Card) adı verilen karton parçalarını, programın akışına (Flow) uygun olarak gerekli slotlara takar ve hesaplamalar sonucu cihazdan bir sonuç alırdı.</p><p><em>Punced Card: Üzerinde belirli noktalara açılan (veya açılmayan) delikler sayesinde sayısal bilgi taşıyabilen karton parçaları.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*JBm7ogTKFgogI5R4.jpg" /><figcaption><a href="https://en.wikipedia.org/wiki/Fortran">Fortran</a> programı: Z(1) = Y + W(1), son 8 sütun sıralama (sorting) bilgisi verir</figcaption></figure><p><strong>İşletim Sistemi,</strong> bilgisayarda çalışan <strong>donanım kaynaklarını yöneten</strong> ve çeşitli uygulama yazılımları için <strong>yaygın servisler sağlayan</strong> <strong>yazılımlar bütünüdür</strong>. Aslında İşletim Sisteminin ortaya çıkış nedeni, yavaş, hata yapmaya açık ve verimi düşük olan bu işletim insanlarının yerini almaktır. İşletim Sistemine bir input verildiğinde bu input, CPU’daki hesaplamalar sonucunda bir output olarak istemciye geri verilir. Ek olarak, işletim sistemi, kullanıcıya bu outputu <strong>hız</strong>, <strong>doğruluk ve verim </strong>temelli bir yaklaşımla sunmaktadır.</p><h3>Process</h3><p>Process, <strong>çalışan programın soyutlaması </strong>olarak tanımlanabilir. Processler sayesinde, <strong>tek bir core’a sahip işlemci </strong>üzerinde <strong>sözde (pseudo) concurrency </strong>yakalanabilmektedir.</p><p>Bilgisayarda birçok işlemi aynı anda yapmaya çalışıyoruz. Örneğin, tarayıcı üzerinde gezinirken arkada Müzik çalmasını veya mail geldiğinde bir notification pop-up’ı gösterilmesini bekliyoruz. Elimizde tek core’a sahip bir işlemci olsun. İşlemlerimizin kısa bir süre içerisinde tamamlanabilmesi için bu işlemcinin olabildiğince az kesintili çalıştırılması gerekmektedir. Ama şöyle bir durum var ki işlemci, T anında sadece tek bir işlem gerçekleşeştirebilmektedir. Peki biz nasıl aynı anda birçok uygulamayı çalıştırabiliyoruz? Hadi bir örnek ile bunu pekiştirelim 😄</p><p>Facebook Server’ına bir istek (request) attığımızı düşünelim. Server’ın amacı, olabildiğince hızlı hizmet verebilmektir. Bu sebeple ilk olarak kendi önbelleğinde (Cache) “bu sayfa var mı?” diye kontrol eder. Eğer varsa, cache’deki sayfayı kullanıcıya gönderir (response) ve işlemi sonlandırır. Eğer sayfa cachede yoksa, server, kendi belleğinden sayfayı almak için belleğine bir istekte bulunur. CPU bu süreçte Input/Output (I/O) biriminden yanıt beklediği için <strong>bloklanmış bir şekilde </strong>bekleme durumunda bulunur. Şu anda CPU bekleme durumdayken, başka kullanıcılar tarafından da bu Server’a istekler gelecektir. CPU’nun bu istekleri işlemesi gerekir ki <strong>gecikmeyi (Latency) </strong>olabildiğince az tutsun ve kullanıcılar sistemden gelecek sonucu beklemesin. Bu bekleme süresini azaltmak için <strong>CPU kullanımını (Utilization) olabildiğince arttırmak </strong>gereklidir. CPU kullanımını arttırmak için de <strong>eş zamanlılığı (Concurrency) </strong>elde etmemiz gerekmektedir. <strong>Processler ve</strong> <strong>Threadler</strong>,<strong> </strong>eş zamanlılığı sağlamakta bizlere yardımcı olmaktadır. Eş zamanlılığı, tek bir işlemcide, farklı uygulamaların belirli zaman periyotlarında sıra sıra çalışması ya da iki farklı uygulamanın birbirinden farklı iki işlemcide aynı anda çalışması olarak düşünebilirsiniz.</p><p>Process<strong> </strong>aslında <strong>RAM’e taşınmış, çalışma durumunda olan, program sayacına (Program Counter), yazmaçlara (Register) ve değişkenlere (Variables) sahip olan bir programdır</strong>. Her Process, CPU’nun kendisine ait olduğunu düşünür. Ancak gerçekte şöyle bir işleyiş vardır;</p><ul><li>Örneğin tek core’a sahip bir CPU’nun üzerinde çalıştığımızı ve elimizde birçok processin olduğunu varsayalım</li><li>İlk process CPU’ya geldi. İşlemlerinin bir kısmını CPU’ya yaptırdı ama kullanıcıdan veri almak için I/O controller’a gitmesi gerekti. Böylece CPU bloklanarak boş duruma (Idle) geçti.</li><li>CPU’yu boş durumda bırakmak istemediğimiz için <strong>sözde (Pseudo) paralel </strong>olarak Process 2&#39;yi işleme aldık ve Process 1 gelene kadar ya da CPU’nun idle durumu oluşana kadar Process 2 üzerinde işleme devam ettik.</li><li>Process 2 bittikten sonra Process 1 hala gelmediyse, Process 3 e geçeriz ve aynı işlemi elimizdeki işler bitene kadar devam ettiririz.</li></ul><p>CPU’yu boş durumda bırakmadan, <strong>Process’ler arasında</strong> sürekli <strong>değişim (context switch)</strong> yaptığımız bu yönteme <strong>çoklu programlama (Multiprogramming) </strong>denir.</p><p>Örnekte paralel kelimesinden önce parantez içinde “pseudo” kelimesini kullandım. Pseudo dememizin sebebi, aslında tek core’lu bu örneğimizde T anında birçok işlemin yapılmamasıdır. CPU’da hesaplamalar o kadar <strong>hızlı</strong> yapılıyor ki, bizler bu hesaplamayı <strong>farketmiyor</strong>, aynı anda paralel olarak bu işlerin hesaplandığını düşünüyoruz.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/894/1*tbXtBwtcj-0Ml5acvrkCxg.png" /></figure><p><strong>(a)</strong> 4 farklı programın Multiprogramming ile Memory’deki durumu <br><strong>(b)</strong> Birbirinden bağımsız kendi Flow’una, Program Counter’ına (PC) sahip olan 4 process. Hangi process işlenirse onun PC’ı gerçek PC’ye yerleştirilir<br><strong>(c)</strong> Tek core CPU’da sırasıyla Process’lerin işlenme durumu. Dikkatli bakılırsa T anında sadece tek bir process işleniyor. Pseudo kelimesinin kullanım sebebinin c grafiği ile daha iyi anlaşıldığını umuyorum.</p><p>Analojiler’in teknik eğitimlerde öneminin daha fazla olduğunu düşünüyorum. Yazımda ana kaynak olarak kullandığım ve incelenmesini kesinlikle önerdiğim <strong>Andrew S. TanenBaum ve Herbert Bos tarafından yazılan “Modern Operating Systems”</strong> kitabında bu konu ile ilgili çok beğendiğim bir analoji bulunmakta. Biz Process kavramını <strong>“program in execution”</strong> yani çalışma durumunda RAM’e taşınmış program olarak tanımlıyoruz. Bu analojideki hedeflenen amaç ise program ve Process arasındaki farkın daha iyi anlaşılabilmesidir.</p><h3>Mutfak Meraklısı Bilgisayar Uzmanı Analojisi</h3><p>Kız çocuğu için doğum günü pastası hazırlayan bir adam olduğunu varsayalım ve adına John diyelim. John’un elinde doğum günü pastasını hazırlayabilmek için bir tarif bulunmakta. Tezgahının üzerinde ise ihtiyacı olan her malzeme var; un, yumurta, şeker, vanilya tozu vs. Bu durumda pasta tarifini bir <strong>program</strong>, John’u <strong>CPU</strong> ve malzemeleri de <strong>input data</strong> olarak düşünebiliriz. John’un pasta tarifini okuması, malzemeleri eklemesi ve keki fırına verme süreci yani işin yapılma süreci bir <strong>Process’tir.</strong></p><p>John, kekin 3. malzemesini karışıma eklerken oğlunun içeri koşarak geldiğini ve arı tarafından sokulduğunu söylediğini varsayalım. John, kekin yapım aşamasında hangi adımda kaldığını (3. malzemede kaldığını) deftere <strong>yazdıktan </strong>sonra (Process’in durumu (<strong>state</strong>) böylece kaydedilmiş oldu), doğrudan oğlunun yanına yardımcı olmak için gitti. Arı sokmasını görünce ilk yardım defterini açıp arı sokması ile ilgili talimatları okudu. John yani CPU’muz, birbirinden farklı iki program arasında (kek tarifi ve ilk yardım defteri), <strong>bir process’ten</strong> (kek harcı hazırlamak) daha <strong>öncelikli </strong>bir <strong>process’e</strong> (oğlunun sağlık durumuna bakmak) <strong>geçiş (Switch) yaptı</strong>. İlk yardım tamamlandıktan sonra John, kek harcını hazırlamaya geri dönerek defterine baktıktan sonra (<strong>State kontrolü)</strong> 3. malzemeyi harca ekleyerek<strong> </strong>işini yapmaya devam etti.</p><p>Bu analojide anlatılmak istenen bir diğer nokta da şu ki, <strong>Process;</strong> bir çeşit işlemin olduğu <strong>hareketlilik</strong>tir. <strong>Program </strong>ise kağıda yazılmış bir <strong>komut listesi</strong>dir.</p><p>Process Scheduler tarafından hangi processin seçileceği ise <strong>Scheduling Algoritmalarına </strong>dayanmaktadır. Scheduling Algoritmaları ile birlikte tek core’a sahip bir <strong>CPU’yu paylaşımlı olarak</strong> kullanabiliyoruz. Bu algoritmaları da sonraki yazılarımda incelemeyi planlıyorum 🚀</p><h3>İşletim Sistemi Bir Process’i Nasıl Başlatır?</h3><p>İşletim Sistemi, Process’i 4 farklı şekilde başlatabilir:</p><ol><li><strong>Sistem’in Başlatılması (System Initialization)</strong>: <br>Bir bilgisayarı açtığımız zaman, birçok Process İşletim Sistemi tarafından başlatılır. Bu processlerden bazıları Foreground Process olarak tanımlanırken bazıları da Background Process olarak isimlendirilmektedir. <br>Kullanıcının etkileşime girdiği processler , <strong>Foreground Process</strong> olarak isimlendirilir. Kullanıcı etkileşimi ile alakasız olan ama belirli bir amaç uğruna sistem tarafından başlatılmış olan processler ise <strong>Background Process</strong> olarak isimlendirilir. <br>Örneğin; sistemde çalışmayan bir uygulamaya tıklayarak run etmemiz sonucu etkileşim sağlanacak ekranı göstermek için işletim sistemi bir Foreground Process başlatmış olur. Background Process’lere ise Mail Receiver örnek olarak verilebilir. Yani mail geldiği an bekleme durumundan çalışma durumuna geçerek işlevini yerine getirir. <br>Ek olarak Background’da çalışan, belli tetiklemeler sonucu aktif olan Process’ler, <strong>Daemon </strong>olarak isimlendirilmektedir.</li><li><strong>Çalışan Process’in Sistemden Yeni Process Başlatma İsteği</strong>:<br>Running State’e sahip bir process, yaptığı işi daha verimli yapabilmesi için sistemden yeni process başlatma isteğinde bulunabilir. Bu istek sonucunda da sistem yeni bir process başlatır.</li><li><strong>Kullanıcı İsteği</strong>: <br>Kullanıcının komut girmesi sonucunda veya bir uygulamayı çalıştırmak amacıyla iconuna iki kez tıklanması sonucu yeni bir process başlatılabilir.</li><li><strong>Batch Başlatılması</strong>: <br>Belirli bir zamanda yapılması gereken işleri <strong>Batch Job</strong> olarak isimlendirmekteyiz. İşletim Sistemi de bu işi yapabilmek için bir process başlatır.</li></ol><h3>Peki İşletim Sistemi Bir Process’i Nasıl Sonlandırır?</h3><p>Bir Process’i sonlandırmak (Terminate) için 4 farklı senaryo vardır:</p><ol><li><strong>Normal Sonlandırma (İstem sonucu — Voluntary)</strong>: <br>Process’lerin “işim bitti” çağrısı yapması sonucunda ya da kullanıcının uygulamayı kapat iconuna tıklaması sonucu oluşan senaryodur.</li><li><strong>Error Sonucu Sonlandırma</strong> <strong>(İstem sonucu — Voluntary):</strong> <br>Process’in bir <strong>Fatal Error</strong> bulması sonucunda oluşan durumdur. Kullanıcı, bu hata ile ilgili bir pop up gösterilmesi sonucu bilgilendirilirip, kullanıcının tekrar işlem yapması istenebilir ya da doğrudan process sonlandırılabilir.</li><li><strong>Fatal Error Sonucu Sonlandırma (İstem dışı — Involuntary):</strong> <br>Process’te bir bug olması (Örneğin yanlış hafıza adresini hedefleyerek işlem yapmaya çalışmak ya da bir sayıyı 0&#39;a bölmeye çalışmak) sonucu process’in sonlandırıldığı senaryodur.</li><li><strong>Başka Process Tarafından Sonlandırma (İstem dışı — Involuntary):<br></strong>Process başka bir Process’i ve onun başlattığı tüm Process’leri sonlandırabilir. Bu işlemin yapılabilmesi için, sonlandıracak (Killer) process’in, sonlanacak (Killee) Process’ten daha yüksek bir yetkiye sahip olması gerekmektedir.</li></ol><h3><strong>Process Durumları (States)</strong></h3><p>Bir Process’in, içinde bulunabileceği <strong>3 durum</strong> vardır:</p><ol><li><strong>Ready</strong></li><li><strong>Running</strong></li><li><strong>Blocked</strong></li></ol><p>Scheduler’in planlaması sonucu bir Process, işini tamamlayana kadar bu üç state arasında gidip gelir.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/311/1*ce0kiHicQ7tFZLdUg_0xjQ.png" /><figcaption>Process’in Stateler Arası Geçiş Temsili</figcaption></figure><p>Grafikteki bu geçişler sırasıyla aşağıdaki gibidir:</p><p>1. İşletim Sisteminin, process’in o an devam edemeyeceği (Örneğin I/O’dan bir veri beklemesi) sonucu yapılan geçiştir.</p><p>2 ve 3. Process Scheduler tarafından hangi processin çalışacağının seçilmesi sonucu gerçekleşen geçişlerdir.</p><p>4. Block’lanan process’in çalışmaya hazır olması durumunda (Örneğin I/O’dan bir veri gelmesi) gerçekleşen geçiştir.</p><p>Umuyorum ki bu yazı sizlere bir fayda sağlamıştır 😄 Bana ulaşmak için aşağıdaki linkleri kullanabilirsiniz:</p><ul><li><a href="https://twitter.com/basar_yargici">Twitter</a></li><li><a href="https://www.linkedin.com/in/ibrahimbasaryargici/">Linkedin</a></li><li><a href="https://github.com/basarYargici">Github</a></li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgiphy.com%2Fembed%2Fl0EwYB32fj4VZxMpa%2Ftwitter%2Fiframe&amp;display_name=Giphy&amp;url=https%3A%2F%2Fgiphy.com%2Fgifs%2Freactionseditor-mothers-day-l0EwYB32fj4VZxMpa&amp;image=https%3A%2F%2Fmedia1.giphy.com%2Fmedia%2Fl0EwYB32fj4VZxMpa%2Fgiphy.gif%3Fcid%3D790b7611a02db44da3d1c55c6d9195d56e7f0f62d7a49956%26rid%3Dgiphy.gif%26ct%3Dg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=giphy" width="435" height="244" frameborder="0" scrolling="no"><a href="https://medium.com/media/855267796c10091978556f55bccc430e/href">https://medium.com/media/855267796c10091978556f55bccc430e/href</a></iframe><p>Yazımda Faydalandığım Kaynaklar:</p><ul><li><a href="https://tr.wikipedia.org/wiki/Delikli_kart">https://tr.wikipedia.org/wiki/Delikli_kart</a></li><li><a href="https://en.wikipedia.org/wiki/Operating_system">https://en.wikipedia.org/wiki/Operating_system</a></li><li><a href="https://en.wikipedia.org/wiki/Von_Neumann_architecture">https://en.wikipedia.org/wiki/Von_Neumann_architecture</a></li><li>Modern Operating Systems Fourth Edition by Andrew S. TanenBaum and Herbert Bos</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1977987d1084" width="1" height="1" alt=""><hr><p><a href="https://medium.com/folksdev/process-bir-yaz%C4%B1l%C4%B1m%C4%B1n-i%CC%87%C5%9Fletim-sisteminde-ya%C5%9Fam-d%C3%B6ng%C3%BCs%C3%BC-1977987d1084">Process - Bir Yazılımın İşletim Sisteminde Yaşam Döngüsü</a> was originally published in <a href="https://medium.com/folksdev">folksdev</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Myers Difference Algorithm]]></title>
            <link>https://medium.com/folksdev/myers-difference-algorithm-d9150b2c3d94?source=rss-9b837ce44818------2</link>
            <guid isPermaLink="false">https://medium.com/p/d9150b2c3d94</guid>
            <category><![CDATA[myers]]></category>
            <category><![CDATA[android]]></category>
            <category><![CDATA[diff-algorithm]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[software-development]]></category>
            <dc:creator><![CDATA[İ. Başar YARGICI]]></dc:creator>
            <pubDate>Mon, 19 Sep 2022 12:35:03 GMT</pubDate>
            <atom:updated>2022-09-19T13:01:08.936Z</atom:updated>
            <content:encoded><![CDATA[<p>Versiyon Kontrol Sistemi, üzerinde değişiklik yaptığımız dosyadaki farklılıkları nasıl bu kadar hızlı ve doğru fark ediyor? Google, bir Android uygulamasında liste üzerinde güncelleme işlemi yapıldığında listenin tamamının bildirilmesinin neden verimsiz olduğunu düşünüyor?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/850/1*R23LI1PdHqCBREYDzUGRMA.png" /><figcaption>Versiyon Kontrol Sistemi’nden Bir Diff Örneği</figcaption></figure><p>Bu ve benzeri sorular eminim ki birçoğumuzda merak uyandırıyor. Ben de bu merak ile çıktığım yolda Google tarafından önerilen yöntemin kaynak kodunda (source code) Myers Difference Algorithm’ın olduğunu gördüm ve bu konu üzerinde araştırmalar yapmaya başladım. Bu yazımda sizlere Myers Difference Algorithm’ın ne olduğunu aktarırken, bu algoritmanın hangi temellere dayandığı ve nerelerde kullanıldığı ile ilgili bilgiler de vereceğim.</p><p>Eugene W. Myers tarafından geliştirilen bu <strong>greedy</strong> diff algoritması, “<a href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.4.6927&amp;rep=rep1&amp;type=pdf">An O(ND) Difference Algorithm and Its Variations</a>” isimli makale ile 1986 yılında yayımlandı.</p><p>Bilgisayar bilimlerinde, iki içeriğin karşılaştırılması sonucunda anlamlı bir fark ve benzerlik çıktısı veren algoritmaları “<strong>diff</strong>” algoritmaları olarak isimlendirmekteyiz. Çoğunlukla diff algoritmaları, iki farklı versiyonu olan aynı dosyanın karşılaştırılması sırasında karşımıza çıkmaktadır.</p><h4>Bu Algoritmanın Amacı Nedir?</h4><p>Myers Diff Algorithm (MDA), iki dizi arasında <strong>en uzun ortak alt diziyi </strong>(longest common subsequence<strong>)</strong> ya da en uzun ortak alt diziye <strong>ulaşan yolu </strong>(shortest edit script)<strong> </strong>bulmayı hedefleyen bir algoritmadır.</p><h4>En Uzun Ortak Alt Dizi (LCS) Nedir?</h4><p>İki dizinin ortak alt dizisi, her iki dizide de aynı sırada görünen öğelerin dizisidir. Örneğin “XYAZ” ve “XZOH” kümelerini karşılaştırdığımız zaman, iki uzunluğa sahip LCS’nin “XZ” olduğunu göreceğiz. “ABC” ve “ACB” örneklerini karşılaştırdığımızda ise birbirinden farklı iki uzunluklu alt küme bulacağız: “AB” ve “AC”. Bu durumda algoritma bulduğu ilk alt kümeyi dönecektir.</p><h4>Peki LCS’yi Nasıl Bulabiliriz?</h4><p>MDA, LCS/SES problemini bulmak için Edit Graph dediğimiz, koordinat sistemine benzetebileceğimiz bir grafiği kullanıyor. Kullanılacak dizilerin doğru konumlandırılıp ilk dizinin elemanı ile ikinci dizinin elemanının bir araya geleceği; N’nin ilk dizinin, M’nin ise ikinci dizinin boyu olduğu varsayıldığı NxM bir graph elde edilir. <strong>Amacımız ise (0,0) noktasından (N,M) noktasına olabildiğince az hareket ile ulaşmaktır.</strong> Bu algoritmanın örnek ile daha iyi açıklanabileceğini düşündüğüm için, konuyu örnek üzerinden pekiştirmeye çalışacağız.</p><p>Karşılaştırmak istediğimiz ve aralarındaki farkları bulmak istediğimiz iki dizi tanımlayalım. X dizisi eski, Y dizisi ise yeni<strong> </strong>versiyonumuz olsun:</p><ul><li>X = “ABDEF”</li><li>Y = “BDAE”</li></ul><p>Bu durumda dizi boyutları:</p><ul><li>N = X.size = 5</li><li>M = Y.size = 4</li></ul><p>Edit Graph üzerinde yatay, dikey ve çapraz hareket edebiliriz. Amacımızın hareket ederek Y dizisini elde etmek olduğunu unutmayalım. Hareket ederken bilmemiz gereken 3 kural var:</p><ul><li><strong>Yatay (Horizontal) </strong>hareket, sonuç dizisinden <strong>sil </strong>anlamına gelir. Örneğin; aşağıdaki grafikte (0,0)’dan (1,0) noktasına hareket edersek, sonuç dizisinden ‘A’ harfini silmiş oluruz.</li><li><strong>Dikey (Vertical) </strong>hareket, sonuç dizisine <strong>ekle </strong>anlamına gelir. Örneğin; aşağıdaki grafikte (0,0)’dan (0,1) noktasına hareket edersek, sonuç dizisine ‘B’ harfini eklemiş oluruz.</li><li><strong>Çapraz (Diagonal) </strong>hareket ise bir <strong>değişiklik olmadığı</strong> anlamına gelir. Çapraz yol ile karşılaşıldığında hareketi sonlandırmadan çapraz yol bitene kadar devam etmeliyiz. Örneğin; (0,0) noktasından (1,0) noktasına ilerle dediğimiz zaman (1,0) ile (3,2) arasındaki çapraz yol bitmediği için tek hareket ile (3,2) noktasına gelmiş oluyoruz. Burada unutmamamız gereken önemli nokta şu ki çapraz yolları hareket olarak saymıyoruz. Yani (0,0) noktasından (3,2) noktasına üç hareket ile değil de bir hareket ile erişmiş oluyoruz.</li></ul><p>Edit Graph üzerinde yapacağımız işlemler şu şekilde olacaktır:</p><ul><li>Eski diziyi (X) üst tarafa, yeni diziyi (Y) sol tarafa koy.</li><li>MxN boyutunda bir tablo oluştur.</li><li>İki dizinin de her bir elemanının eşleneceği kutuları çiz.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/621/1*5Meymmm8lAPUJev11RQQxA.png" /><figcaption>Edit Graph Başlangıç Şekli</figcaption></figure><ul><li>İki dizide aynı elemanlara denk gelen kutulara çapraz hareket edilebilecek bir yol aç.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/610/1*Ap084DDZIpaP2T_FWBH2iA.png" /><figcaption>Çapraz Hareket Yolları</figcaption></figure><ul><li>Bu adımlardan sonra tekrarlı bir şekilde (0,0) noktasından (5,4) noktasına erişmeye çalışacağız.</li><li>Dikey, yatay ve çapraz hareket yapabileceğimiz bu sistemde (0,0) noktasından harekete başlayınca ulaşabileceğimiz en uzak noktalar şu şekildedir:<br>* (0,1) noktasına 1 dikey hareket ile ulaşabiliriz.<br>* (1,0) noktasına ise 1 yatay hareket ile ulaşabiliriz. Buna ek olarak (1,0) noktasından sonra, hiçbir değişiklik yapma anlamına gelen çapraz çizgiler ile karşılaşmamız sonucunda, hareketimize devam etmemiz gerekir. Önce (2,1) noktasına, sonrasında (3,2) noktasına erişiriz.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/671/1*d4mSoCKKN0TgQSerj3REpA.png" /><figcaption>Birinci Hareket</figcaption></figure><ul><li>Böylece ilk hareketimizden sonra yeni bir hareketi başlatacak iki farklı başlangıç noktamız oluyor: (0,1) ve (3,2).<br>(0,1) noktasından yatay hareket ile (1,1) noktasına, dikey hareket ile öncelikle (0,2) noktasına, ardından (1,3) noktasına erişebiliriz.<br>(3,2) noktasından yatay hareket ile (4,2) noktasına, dikey hareket ile öncelikle (3,3) noktasına, ardından (4,4) noktasına erişebiliriz.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/687/1*GbaZTAR9fp6toIOHS1zi5w.png" /><figcaption>İkinci Hareket</figcaption></figure><ul><li>Yukarıdaki işlemi tekrarlayıp (4,4) noktasından bir yatay hareket yapıldığında (5,4) noktasına, yani amaçladığımız noktaya erişmiş oluruz.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/727/1*-5NXBNOXuWPmD7zEloaNhw.png" /><figcaption>Üçüncü Hareket</figcaption></figure><p>Böylece X dizisinden Y dizisine ulaşan <strong>en az hareket sayısına sahip yolu </strong>(path) bulmuş oluyoruz. Aynı zamanda başlangıç noktasından bitiş noktasına kadar bu yolu takip ettiğimizde, eski diziden <strong>hangi karakterlerin silindiğini </strong>(yatay hareket), <strong>değişmeyen karakterleri </strong>(çapraz hareket) ve <strong>yeni diziye eklenen karakterleri </strong>(dikey hareket) görebiliriz.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/727/1*QQU2qJtXd1w8dnK6-VwhGQ.png" /><figcaption>En Az Hareket İle Son Noktaya Ulaşabileceğimiz Yol</figcaption></figure><p>Bu hareketleri en basit hali ile açıklamak gerekirse:</p><ul><li>Eski diziden A harfini <strong>çıkar</strong></li><li>B ve D harflerine dokunma</li><li>A harfini <strong>ekle</strong></li><li>E harfine dokunma</li><li>Eski diziden F harfini <strong>çıkar</strong></li></ul><p>Hareket olarak sadece <strong>ekleme </strong>ve <strong>çıkarma </strong>işlemlerini saydığımız için toplam üç hareket ile eski diziden yeni dizinin nasıl elde edildiğini görmüş oluyoruz.</p><p>Bu örneği Versiyon Kontrol Sisteminden alışık olduğunuz bir görsel ile incelemek istersek:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/487/1*5Zs_GVkPvvq1MG7BlhPwdg.png" /><figcaption>İki Dizi Arasındaki Fark</figcaption></figure><p>Yukarıdaki örneğin karmaşıklığının artmaması için algoritmanın orijinal halinde bulunan D-path ve K-line dediğimiz iki farklı kavramdan örnekte bahsetmedim. Bu iki kavram en kısa yolun doğru bir şekilde bulunmasında bizlere yardımcı olmaktadır.</p><p>K-line aslında sadece iki kural içeren ve en kısa yolun bulunmasına yardımcı olan bir çapraz çizgidir:<br>- Bir noktadaki K’nın değerini hesaplamak istiyorsak x-y değerine bakmalıyız (K = x — y).<br>- Yeni bir hareket yapmayı planlıyorsak, hareketin başarılı bir şekilde tamamlanması için ulaşacağımız noktadaki K değerine bakmamız gerekir. Bu noktaya kadar oluşturduğumuz yolda en az |K| adet harekete (ekleme ya da silme) sahipsek hareketi yapabiliriz. Eğer hareket sayımız |K|’dan az ise hareketi yapamayız.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/922/1*Hj-MHebrA405ZgAyBLH5CA.png" /><figcaption>Örneğimizdeki K-Line’lar</figcaption></figure><p>D-path ise (0,0) noktasından başlayan, D sayısınca <strong>çapraz olmayan yol</strong> ile oluşturulmuş yoldur.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/891/1*iS2O_mpE4qQm0eu8GWEGNg.png" /><figcaption>D-Path’ler</figcaption></figure><p>Örneğimizde (0,0) noktasından yapılabilecek ilk hareketin ulaşabileceği noktaların (0,1) ve (3,2) olduğunu düşünerek D = 1 için çizgimizi çekiyoruz. Bu işlemi tekrar ederek diğer D-path’lere de ulaşabiliriz.</p><p>Myers Algoritması ile ilgili kod örnekleri ve interaktif görselleştirme araçlarının yanında detaylı analiz içeren <a href="https://blog.robertelder.org/diff-algorithm/#myers-paper">Robert Elder’ın bloğunu</a> okumanızı ve grafikler üzerinde oynama yapmanızı şiddetle tavsiye ederim.</p><p>Detaya inmek isteyenler için önerilerim:<br> — <a href="https://en.wikipedia.org/wiki/Longest_common_subsequence_problem">Longest common subsequence problem<br></a> — <a href="https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/">The Myers diff algorithm</a> by James Coglan<br> — <a href="http://raywenderlich.github.io/swift-algorithm-club/Myers%20Difference%20Algorithm/">Myers Difference Algorithm</a> by Raywenderlich<br> — <a href="https://epxx.co/artigos/diff_en.html">Diff algorithms</a> by Elvis Pfützenreuter<br> — <a href="https://www.codeproject.com/Articles/42279/Investigating-Myers-diff-algorithm-Part-1-of-2">Investigating Myers’ diff algorithm</a> by Nicholas Butler<br>— Video severler için Türkçe örnek çözüm videosu: <a href="https://www.youtube.com/watch?v=KaablZTnrKI">LCS Algoritması - Longest Common Subsequences</a><br> — Video severler için Dynamic Programming kullanılarak LCS mantığını anlatan bir video: <a href="https://www.youtube.com/watch?v=ASoaQq66foQ">Longest Common Subsequence (2 Strings) — Dynamic Programming &amp; Competing Subproblems</a></p><p>Umuyorum ki ilk Medium yazımı beğenmişssinizdir :) Bana ulaşmak için aşağıdaki linkleri kullanabilirsiniz:</p><ul><li><a href="https://twitter.com/basar_yargici">Twitter</a></li><li><a href="https://www.linkedin.com/in/ibrahimbasaryargici/">Linkedin</a></li><li><a href="https://github.com/basarYargici">Github</a></li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgiphy.com%2Fembed%2Fe7QQ9Kawb0OTJkTM1w%2Ftwitter%2Fiframe&amp;display_name=Giphy&amp;url=https%3A%2F%2Fgiphy.com%2Fgifs%2Ftheitcrowd-funny-crowd-e7QQ9Kawb0OTJkTM1w&amp;image=https%3A%2F%2Fmedia0.giphy.com%2Fmedia%2Fe7QQ9Kawb0OTJkTM1w%2F200.gif%3Fcid%3D790b7611cd78b7870138f5d4f0fd4146202edc0cfcff6389%26rid%3D200.gif%26ct%3Dg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=giphy" width="435" height="238" frameborder="0" scrolling="no"><a href="https://medium.com/media/4154ca4e7a91fad57b03b6890d62afde/href">https://medium.com/media/4154ca4e7a91fad57b03b6890d62afde/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d9150b2c3d94" width="1" height="1" alt=""><hr><p><a href="https://medium.com/folksdev/myers-difference-algorithm-d9150b2c3d94">Myers Difference Algorithm</a> was originally published in <a href="https://medium.com/folksdev">folksdev</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>