Array ve Hashing Pattern'leri: Two Pointers, Sliding Window, Prefix Sum ve Frequency Map

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 ve Microsoft.Extensions.TimeProvider.Testing 10.11.0 ile yazılmış testlerle doğrulanmıştır; ölçümler BenchmarkDotNet 0.15.8 ile alınmıştır.

Önce Tahmin Et

Bookstore'un pazarlama ekibi "iki kitabı birlikte al, toplam tam 60 TL olsun, kargo bedava" kampanyası istiyor. Katalogdaki fiyatlardan toplamı tam 60 olan iki kitabı bulan bir method gerekiyor. İlk akla gelen çözüm her kitabı diğer her kitapla denemek.

Katalogda 1.000 kitap varken bu çözüm 0,14 ms civarında sürüyor. Katalog 100.000 kitaba çıkınca ne kadar sürer: 30 ms mi, 3 saniye mi? Aynı işi bir Dictionary ile yapan versiyon 100.000 kitapta ne kadar sürer?

Two Sum: O(n²)'den O(n)'e

Bu yazıdaki bütün pattern'lerin ortak fikri aynı: iç içe döngünün yaptığı tekrar eden işi bir kez yap ve sonucu hatırla. En temiz örneği two sum.

namespace Algorithms.Patterns;

public static class TwoSum
{
    // O(n^2): her çift
    public static (int, int)? BruteForce(int[] prices, int target)
    {
        for (int i = 0; i < prices.Length; i++)
            for (int j = i + 1; j < prices.Length; j++)
                if (prices[i] + prices[j] == target) return (i, j);
        return null;
    }

    // O(n): gördüklerini hatırla, "tamamlayıcısını gördüm mü?" diye sor
    public static (int, int)? WithDictionary(int[] prices, int target)
    {
        Dictionary<int, int> seenAt = new(prices.Length);
        for (int i = 0; i < prices.Length; i++)
        {
            if (seenAt.TryGetValue(target - prices[i], out int j)) return (j, i);
            seenAt.TryAdd(prices[i], i); // tekrar eden değerlerde ilk index'i tut
        }
        return null;
    }

    // sıralı input: two pointers, O(n) ve ek bellek yok
    public static (int, int)? SortedTwoPointers(int[] sorted, int target)
    {
        int left = 0, right = sorted.Length - 1;
        while (left < right)
        {
            int sum = sorted[left] + sorted[right];
            if (sum == target) return (left, right);
            if (sum < target) left++;   // daha büyük toplam lazım: bunu ancak left'i ilerletmek yapar
            else right--;               // daha küçük toplam lazım
        }
        return null;
    }
}

Brute force her fiyat için "bununla toplamı 60 eden bir fiyat var mı?" sorusunu bütün listeyi gezerek cevaplıyor. Dictionary versiyonu aynı soruyu her adımda soruyor ama cevabı O(1)'de alıyor: o ana kadar görülen fiyatları bir hash table'da tutuyor. Fiyat 12 ise aradığı 48; 48 daha önce görüldüyse çift bulundu. Bedeli O(n) ek bellek. Two pointers versiyonu sıralı bir input'ta ek bellek kullanmadan aynı işi yapıyor; birazdan ona döneceğiz.

Dikkat isteyen tek ayrıntı tekrar eden değerler. Hedef 60 ve listede tek bir 30 varsa, 30'un kendisiyle eşleşmemesi gerekiyor. Tamamlayıcıyı aramak, mevcut fiyatı eklemekten önce yapıldığı için bu kendiliğinden doğru çalışıyor:

[Fact]
public void TwoSum_DuplicateValues_UsesTwoDifferentIndexes()
{
    Assert.Equal((0, 2), TwoSum.WithDictionary([30, 10, 30], 60));
    Assert.Null(TwoSum.WithDictionary([30, 10], 60));
}

Benchmark en kötü durumu ölçüyor: eşleşen tek çift listenin son iki elemanı, yani iki versiyon da sonuna kadar gitmek zorunda.

[GlobalSetup]
public void Setup()
{
    // 10'dan büyük, birbirinden farklı çift fiyatlar; eşleşen tek çift son iki eleman (ikisi için de en kötü durum)
    _prices = [.. Enumerable.Range(0, N).Select(i => 10 + i * 2)];
    _prices[^2] = 1;
    _prices[^1] = 3;
    _target = 4;
}

BenchmarkDotNet v0.15.8, macOS 27.0.1 (26A434) [Darwin 27.0.0]
Apple M5, 1 CPU, 10 logical and 10 physical cores
.NET SDK 10.0.402
  [Host] : .NET 10.0.13 (10.0.13, 10.0.1326.50504), Arm64 RyuJIT armv8.0-a

| Method     | N      | Mean             | Ratio | Allocated |
|----------- |------- |-----------------:|------:|----------:|
| BruteForce | 1000   |       135.716 us |  1.00 |         - |
| Dictionary | 1000   |         3.287 us |  0.02 |   22192 B |
|            |        |                  |       |           |
| BruteForce | 10000  |    12,393.128 us | 1.000 |         - |
| Dictionary | 10000  |        35.698 us | 0.003 |  202226 B |
|            |        |                  |       |           |
| BruteForce | 100000 | 1,691,487.141 us | 1.001 |         - |
| Dictionary | 100000 |       323.704 us | 0.000 | 2172963 B |

Açılıştaki soruya dönelim. 1.000 kitapta brute force 0,14 ms; 100.000 kitapta 1,69 saniye. Veri 100 kat büyüdü, süre yaklaşık 12.500 kat büyüdü: n² büyümenin ta kendisi (beklenen 10.000 kat, üstüne büyük array'in cache'e sığmamasının etkisi). Dictionary versiyonu aynı veride 3,3 µs'den 324 µs'ye çıkıyor, yani veriyle doğru orantılı; 100.000 kitapta brute force'tan 5.000 kattan fazla hızlı. Bedeli "Allocated" sütununda: 100.000 fiyat için 2,1 MB'lık bir Dictionary. Ölçüm makinede başka işler çalışırken alındı; oranlara bak. İç içe döngüleri böyle tek bir geçişe indirmenin genel tekniği Big-O ve Complexity serisinin "Koddan Time Complexity Çıkarmak" yazısında.

Frequency Map ve Gruplama

Two sum'daki "gördüklerini hatırla" fikrinin en yaygın hâli saymak. Hangi türden kaç kitap satıldı, hangi müşteri kaç sipariş verdi, hangi kelime kaç kez arandı? Elle yazılan versiyon ile .NET 9'da gelen CountBy:

public static Dictionary<string, int> CountByHand(IEnumerable<string> genres)
{
    Dictionary<string, int> counts = [];
    foreach (string genre in genres)
        counts[genre] = counts.GetValueOrDefault(genre) + 1;
    return counts;
}

[Fact]
public void FrequencyMap_ByHand_MatchesCountBy()
{
    string[] genres = ["sci-fi", "classic", "sci-fi", "poetry", "sci-fi", "classic"];

    Dictionary<string, int> byHand = FrequencyMap.CountByHand(genres);
    Dictionary<string, int> byLinq = genres.CountBy(g => g).ToDictionary();

    Assert.Equal(byLinq, byHand);
    Assert.Equal(3, byHand["sci-fi"]);
}

CountBy ve AggregateBy, eskiden GroupBy(...).Select(g => (g.Key, g.Count())) ile yapılan işi her grup için ara bir list oluşturmadan yapıyor; ayrıntılar LINQ (Language Integrated Query) serisinin "LINQ ve .NET 9: CountBy, AggregateBy ve Index" yazısında. Elle yazılan döngü de aynı mantığı izliyor; ikisi de O(n) zaman ve farklı key sayısı kadar bellek.

Frequency map'in bir adım ötesi, key'i akıllıca seçerek gruplamak. Aynı harflerden oluşan kelimeleri (anagram'ları) bulmak için her kelimenin harflerini sıralayıp key yapmak yetiyor: "dune" ve "nude" ikisi de "denu" key'ine düşüyor.

// anagram grupları: aynı harfler, herhangi bir sıra -> aynı sıralı key
public static List<List<string>> GroupAnagrams(IEnumerable<string> words)
{
    Dictionary<string, List<string>> groups = [];
    foreach (string word in words)
    {
        char[] letters = word.ToCharArray();
        Array.Sort(letters);
        string key = new(letters);
        if (!groups.TryGetValue(key, out List<string>? group))
            groups[key] = group = [];
        group.Add(word);
    }
    return [.. groups.Values];
}

Gerçek hayatta aynı fikir "normalize edilmiş key" olarak karşına çıkıyor: büyük/küçük harf ve boşluklardan arındırılmış e-posta adresleri, tirelerden temizlenmiş ISBN'ler (International Standard Book Number), aynı adresi farklı yazan müşteri kayıtları. Doğru key'i bulduğunda gruplama tek bir Dictionary geçişi.

Two Pointers

Input sıralıysa hash table'a bile gerek kalmıyor. SortedTwoPointers bir pointer'ı en küçük, diğerini en büyük fiyata koyuyor. Toplam hedeften küçükse toplamı büyütmenin tek yolu soldakini ilerletmek; büyükse sağdakini geri çekmek. Her adımda bir pointer hareket ediyor ve pointer'lar buluşunca iş bitiyor: en fazla n adım, O(1) ek bellek.

Neden hiçbir çifti kaçırmadığının sezgisi şu: toplam hedeften küçükken soldaki fiyatı atıyoruz, çünkü o fiyat en büyük fiyatla bile hedefe ulaşamıyor; başka hiçbir fiyatla da ulaşamaz. Her adım, cevap olamayacağı kanıtlanmış bir fiyatı eliyor.

Aynı iki pointer fikri, sıralı bir array'deki tekrarları ek bellek kullanmadan silmeye de yarıyor. Bir pointer okuyor, diğeri bir sonraki benzersiz değerin yazılacağı yeri gösteriyor:

// sıralı bir array'deki tekrarları yerinde siler, yeni uzunluğu döner
public static int Dedupe(int[] sorted)
{
    if (sorted.Length == 0) return 0;
    int write = 1;
    for (int read = 1; read < sorted.Length; read++)
    {
        if (sorted[read] != sorted[write - 1])
            sorted[write++] = sorted[read];
    }
    return write;
}

[Fact]
public void Dedupe_SortedArray_KeepsFirstOfEachValue()
{
    int[] ids = [1, 1, 2, 3, 3, 3, 7];

    int length = TwoPointers.Dedupe(ids);

    Assert.Equal([1, 2, 3, 7], ids[..length]);
}

Okuma ve yazma pointer'ı, serinin ikinci yazısındaki RemoveAll alıştırmasının da çözümü: her element en fazla bir kez kopyalanıyor, yani O(n).

Sliding Window

Sliding window, ardışık bir aralık (pencere) üzerinde bir değer hesaplayıp pencereyi her adımda kaydırırken baştan hesaplamak yerine yalnızca giren ve çıkan element'i hesaba katmak. İki türü var. Sabit genişlikli pencerede "art arda 7 günün en yüksek satış toplamı" gibi bir soru soruluyor:

// art arda k günün en iyi toplamı: sabit pencere, yeni günü ekle, eskisini çıkar
public static long MaxSumOfK(int[] dailySales, int k)
{
    long window = 0;
    for (int i = 0; i < k; i++) window += dailySales[i];
    long best = window;
    for (int i = k; i < dailySales.Length; i++)
    {
        window += dailySales[i] - dailySales[i - k];
        best = Math.Max(best, window);
    }
    return best;
}

Değişken genişlikli pencerede ise bir koşul bozulana kadar pencere sağdan büyüyor, koşul bozulunca soldan küçülüyor. "Tekrar eden karakter içermeyen en uzun substring" klasik örneği:

// tekrar eden karakter içermeyen en uzun substring'in uzunluğu
public static int LongestUnique(string text)
{
    Dictionary<char, int> lastSeen = [];
    int best = 0, start = 0;
    for (int end = 0; end < text.Length; end++)
    {
        // pencere içinde bir tekrar: start'ı önceki konumunun bir sağına atla
        if (lastSeen.TryGetValue(text[end], out int previous) && previous >= start)
            start = previous + 1;
        lastSeen[text[end]] = end;
        best = Math.Max(best, end - start + 1);
    }
    return best;
}

[Theory]
[InlineData("abcabcbb", 3)]
[InlineData("bbbb", 1)]
[InlineData("", 0)]
[InlineData("abba", 2)]
public void LongestUnique_ReturnsLength(string text, int expected) =>
    Assert.Equal(expected, SlidingWindow.LongestUnique(text));

"abba" testi tam o previous >= start kontrolü için. İkinci b görüldüğünde start 2'ye atlıyor. Sonra a geliyor; a'nın son görüldüğü yer index 0 ama bu artık pencerenin dışında. Kontrol olmasa start geriye, 1'e giderdi ve sonuç yanlışlıkla 3 çıkardı.

Bookstore'daki gerçek bir sliding window: arama API'sine (Application Programming Interface) bir istemciden son 60 saniyede en fazla N istek kabul etmek. Kabul edilen isteklerin zamanlarını bir queue'da tutuyoruz; her yeni istekte pencereden çıkmış zamanları baştan atıyoruz:

// sliding log: herhangi bir "window" uzunluğundaki sürede en fazla "limit" isteğe izin verir
public sealed class SlidingWindowRateLimiter(int limit, TimeSpan window, TimeProvider clock)
{
    private readonly Queue<DateTimeOffset> _accepted = new();

    public bool TryAcquire()
    {
        DateTimeOffset now = clock.GetUtcNow();
        // pencereden çıkan zamanları at: pencere (now - window, now] aralığı
        while (_accepted.Count > 0 && _accepted.Peek() <= now - window)
            _accepted.Dequeue();
        if (_accepted.Count >= limit) return false;
        _accepted.Enqueue(now);
        return true;
    }
}

Zamanı test edebilmek için DateTime.UtcNow yerine TimeProvider alıyoruz; testte FakeTimeProvider ile saati elle ilerletiyoruz. Pencere sınırının tam neresi olduğu (59. saniye reddedilmeli, 60. kabul edilmeli) bir off-by-one sorusu ve testte açıkça yazılı:

[Fact]
public void RateLimiter_AtMostLimitPerWindow()
{
    FakeTimeProvider clock = new(new DateTimeOffset(2026, 11, 8, 10, 0, 0, TimeSpan.Zero));
    SlidingWindowRateLimiter limiter = new(limit: 3, TimeSpan.FromSeconds(60), clock);

    bool[] first = [limiter.TryAcquire(), limiter.TryAcquire(), limiter.TryAcquire(), limiter.TryAcquire()];
    clock.Advance(TimeSpan.FromSeconds(59));
    bool at59 = limiter.TryAcquire();
    clock.Advance(TimeSpan.FromSeconds(1));
    bool at60 = limiter.TryAcquire();

    Assert.Equal([true, true, true, false], first);
    Assert.False(at59);
    Assert.True(at60);
}

Production'da bunu kendin yazmana gerek yok: System.Threading.RateLimiting'deki SlidingWindowRateLimiter ve ASP.NET Core'un rate limiting middleware'i aynı fikri, pencereyi segment'lere bölerek daha az bellekle uyguluyor. Bizim sliding log versiyonumuz kesin ama limit kadar timestamp tutuyor; segment'li versiyon yaklaşık ama sabit bellekli.

Prefix Sum

Bookstore'un satış raporu ekranı "şu tarihten şu tarihe toplam satış" sorusunu gün içinde binlerce kez soruyor. Her sorguda aralığı toplamak O(aralık uzunluğu). Prefix sum bunu tek bir çıkarmaya indiriyor: prefix[i] ilk i günün toplamı ise, [from, to] aralığının toplamı prefix[to + 1] - prefix[from].

public sealed class PrefixSum
{
    private readonly long[] _prefix; // _prefix[i] = ilk i günün toplamı; _prefix[0] = 0

    public PrefixSum(int[] values)
    {
        _prefix = new long[values.Length + 1];
        for (int i = 0; i < values.Length; i++) _prefix[i + 1] = _prefix[i] + values[i];
    }

    // values[from..to] (iki uç dahil) toplamı, O(1)
    public long RangeSum(int from, int to) => _prefix[to + 1] - _prefix[from];
}

Array'in bir eleman uzun olması ve _prefix[0] = 0 seçimi bilinçli: "ilk 0 günün toplamı" tanımı sayesinde aralık baştan başlasa da formül değişmiyor, özel durum yok. Toplamlar long, çünkü bir yılın günlük satışlarını int'te toplamak taşabilir. Kurulum O(n), her sorgu O(1).

Prefix sum'ın hash table ile birleştiği yer, en güzel örneklerden biri: "toplamı tam k olan kaç ardışık aralık var?" Değerler negatif olabildiğinde (iadeler) sliding window çalışmaz, çünkü pencereyi büyütmek toplamı her zaman artırmaz. Ama [i, j] aralığının toplamı prefix[j] - prefix[i] olduğuna göre, j'de biten ve toplamı k olan aralık sayısı, daha önce görülmüş ve değeri prefix[j] - k olan prefix sayısına eşit:

// toplamı tam k olan kaç ardışık aralık var (değerler negatif olabilir, ör. iadeler)
public static int CountEqualTo(int[] values, int k)
{
    Dictionary<long, int> prefixCounts = new() { [0] = 1 }; // boş prefix
    long prefix = 0;
    int count = 0;
    foreach (int value in values)
    {
        prefix += value;
        // burada biten bir aralığın toplamı k ise, daha önceki bir prefix prefix - k'ye eşittir
        count += prefixCounts.GetValueOrDefault(prefix - k);
        prefixCounts[prefix] = prefixCounts.GetValueOrDefault(prefix) + 1;
    }
    return count;
}

[Theory]
[InlineData(new[] { 1, 1, 1 }, 2, 2)]
[InlineData(new[] { 3, 4, 7, -2, 2, 1, 4, 2 }, 7, 6)]
[InlineData(new[] { 5 }, 5, 1)]
public void SubarraySum_CountsRanges(int[] values, int k, int expected) =>
    Assert.Equal(expected, SubarraySum.CountEqualTo(values, k));

{ [0] = 1 } başlangıç kaydı bu yazının en çok unutulan satırı. Array'in en başından başlayan aralıkları sayabilmek için "hiç eleman almamış" prefix'in, yani 0'ın, bir kez görülmüş olması gerekiyor. Üçüncü test tam bunu yakalıyor: tek elemanlı [5] array'inde k=5 için cevap 1. Başlangıç kaydı olmasa 0 çıkardı.

$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.ArrayPatternTests
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (573ms)

Test run summary: Passed!
  total: 15
  failed: 0
  succeeded: 15

Hangi Pattern Ne Zaman?

Tablodaki her satırın arkasında aynı soru var: iç içe döngü neyi tekrar tekrar hesaplıyor ve bunu bir kez hesaplayıp nerede saklayabilirim? Cevap bazen bir hash table, bazen iki index, bazen bir prefix array'i.

Üretimde Dikkat

O(n) bellek, O(n²) zamandan her zaman iyi değil. 100 milyon satırlık bir log dosyasında two sum yapan bir Dictionary gigabaytlarca bellek ister; o noktada veriyi sıralayıp two pointers ile ek bellek kullanmadan çözmek ya da işi veritabanına (bir JOIN ya da GROUP BY) bırakmak daha doğru. Zaman ve bellek arasındaki bu takas Big-O ve Complexity serisinin "Space Complexity" yazısında.

Prefix sum'ı veri değişmeyecekse kullan. Gün içinde geçmiş günlerin satışı değişiyorsa (iadeler, düzeltmeler), her değişiklik sonraki bütün prefix'leri bozar ve yeniden kurmak O(n). Sık güncellenen veride aralık toplamı için Fenwick tree ya da segment tree gibi yapılar her iki işlemi de O(log n)'de yapıyor.

Rate limiter'ı tek bir process'in belleğinde tutmak, birden fazla instance'ta her instance'ın kendi limitini uygulaması demek. Dağıtık bir limit gerekiyorsa sayaç Redis gibi paylaşılan bir yerde durmalı; bu konu System Design serisinin "Rate Limiting Tasarımı: Token Bucket, Sliding Window ve Distributed Rate Limiter" yazısında.

Sık Düşülen Tuzaklar

Pencere sınırlarında off-by-one. Bir pencerenin [start, end] mi yoksa [start, end) mi olduğunu kodun başında karar verip bir yoruma yaz; uzunluğu end - start + 1 mi end - start mi hesaplayacağın buna bağlı. Rate limiter testindeki 59. ve 60. saniye gibi sınır değerlerini her zaman test et.

Prefix map'e başlangıç kaydını unutmak. { [0] = 1 } olmadan array'in başından başlayan aralıklar sayılmaz ve hata yalnızca bazı input'larda görünür.

Two sum'da sırayı ters çevirmek. Mevcut fiyatı dictionary'ye ekleyip sonra tamamlayıcısını aramak, 30 + 30 = 60 gibi bir durumda aynı elemanı kendisiyle eşleştirir.

Toplamları int'te tutmak. Prefix sum ve pencere toplamları hızla büyür; long kullan ya da kritik yerlerde checked ile taşmayı yakala.

Küçük Bir Deneme

★☆☆ SortedTwoPointers'ı, toplamı tam hedef olan bütün çiftleri dönecek şekilde değiştir. Tekrar eden fiyatlar varken aynı çifti iki kez dönmemek için ne yapman gerekiyor?

★★☆ "En fazla k farklı türden kitap içeren en uzun ardışık satış dizisi"ni bulan bir sliding window yaz. Penceredeki türleri bir frequency map'te tut; sayı sıfıra düşen türü map'ten silmeyi unutma.

★★★ PrefixSum'ı iki boyuta genişlet: raf × gün grid'inde herhangi bir dikdörtgenin toplamını O(1)'de veren bir PrefixSum2D yaz. İpucu: prefix[r + 1, c + 1] = grid[r, c] + prefix[r, c + 1] + prefix[r + 1, c] - prefix[r, c].

Two pointers'ın sıralı input istediğini gördük. Bir sonraki yazıda sıralamanın kendisine geçiyoruz: insertion sort'un neden hâlâ değerli olduğu, merge sort ve sorting'in en çok gözden kaçan özelliği olan stability. Array.Sort'un eşit element'lerin sırasını korumadığı gerçek bir bug ile.