İleri Seviye Listeler Sorusu

Herkese iyi forumlar arkadaşlar. İnternette bir soruyla karşılaştım (ingilizce) ve buraya atıp sizlere sormak istedim.

Yazılı olarak soru :

Supose that initially we had two identical (all elements are same) lists consisting of unique integers, sorted increasingly. Let’s call these lists as list_a and list_b. Someone randomly deleted
an element from list_b and appended an element to the end that is greater than the last element
of list_b. Then, the two elements of the two lists will be same upto the index that is deleted and
for the rest of indices the two lists will have unequal elements in the same indices. For example,
consider the two lists below:
[1, 6, 8, 9, 14, 16, 19, 21, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49, 53]
#list _a
[1, 6, 8, 9, 14, 16, 19, 21, 23, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49]
#list _b

list_a[i] = list_b[i] for, $i=0,. . . ,7 $ and list_a[i] is different form list_b[i] for all i ≥ 8.
Starting from 0, the first index that two lists have different value is called divergence index. The
divergence index for this example is 8.
Write a recursive method that finds the divergence index of two lists in O(log n) complexity using
bi-section.
Notes: Remember how we solved the “guess what number I have in my mind” game in the class.
Answers with for-loops that traverse through the all elements from the beginning to end (or, from
the end to the beginning etc.) are not valid.


def div_index(a, b):
    # ... This is where you will write your code
    # ... call somewhere div_index ...
    # ...
    pass



# Run the test case:
list_a = [1, 6, 8, 9, 14, 16, 19, 21, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47,␣
, →49, 53]
list_b = [1, 6, 8, 9, 14, 16, 19, 21, 23, 26, 31, 34, 35, 37, 38, 41, 42, 44,␣
, →47, 49]
div_index(list_a, list_b)
# You should get 8

Fotoğraf olarak soru :

Yardımcı olmaya çalışan arkadaşlara şimdiden teşekkürler.

Şöyle bir algoritma izledim…

Kodlar:

def dev_index(a: list, b: list):

    def inner(x: list, y: list):
        midpoint = int(len(x) / 2)
        if x[:midpoint] != y[:midpoint]:
            return inner(x[:midpoint], y[:midpoint])
        else:
            if len(x) == 1:
                return x[0]
            else:
                return inner(x[midpoint:], y[midpoint:])

    return a.index(inner(a, b))

Test:

list_a = [
    1, 6, 8, 9, 14, 16, 19, 21, 26, 31, 34, 
    35, 37, 38, 41, 42, 44, 47, 49, 53
]

list_b = [
    1, 6, 8, 9, 14, 16, 19, 21, 23, 26, 31, 
    34, 35, 37, 38, 41, 42, 44, 47, 49
]

print(dev_index(list_a, list_b))

Sonuç:

8

Açıklama:

Bozulmanın başladığı değeri bulmak için bi-section (listeleri ikiye bölme işlemi) yapılacak. Yani öz-yinelemenin her adımında listeler ikiye bölünecek ve listelerin ilk yarılarının birbirlerine eşit olup olmadıkları karşılaştırılacak. Duruma göre listelerin ya sıfırıncı indisten ortasına kadar, ya da ortasından sonuna kadar olan kısımları fonksiyonun yeni parametreleri olacak. Listelerin elemanları yarı yarıya azaltılırsa, en sonunda zaten tek bir değer kalır. O değer de farklılaşmanın başladığı değer olur.

3 Beğeni

Çok az ve öz kodla çözüme ulaşmışsınız . Teşekkür ederim

Bunlar lineer zamanda calisan yardimci fonksiyonlar malesef, odevin ruhuna uygun degil.

Base case’in tek eleman karsilastirma olmasi lazim. Divergence’i buldugumuz anda da indeksini bilmemiz mumkun aslinda, bil– bunu challenge olarak birakayim.

3 Beğeni

Aşağıdaki gibi bir fonksiyon da sonucu bulur ama aşağıdaki fonksiyonda bi-section yok, yani çok büyük listelerde zaman problemi oluşacak (Aşağıdaki fonksiyon lineer zamana göre işlem yapıyor.). İlk paylaştığım fonksiyonla daha az adımlarla sonuca ulaşıyorken, aşağıdaki fonksiyonla sonuca ulaşmak için daha çok adım atmamız gerekiyor.

Üstelik üçüncü bir parametre de vermemiz gerekiyor.

def dev_index(a: list, b: list, count: int = 0):
    if a[0] == b[0]:
        return dev_index(a[1:] + [a[0]], b[1:] + [b[0]], count=count + 1)
    else:
        return count

Başka nasıl bir yol izleyebiliriz diye düşünüyorum. :thinking:

1 Beğeni

Fonksiyon nasıl aynı anda hem O(n) yani lineer zamana göre işlem yapacak hem de bi-section olacak diye düşünüyorum. Henüz bir çözüm bulamadım. :frowning:

@aib’in dikkat çektiği yerleri düzeltirsek şöyle bir şey yazabiliriz:

list_a = [1, 6, 8, 9, 14, 16, 19, 21, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49, 53]
list_b = [1, 6, 8, 9, 14, 16, 19, 21, 23, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49]

f = lambda m, k, l, i: (f(m[l:], k[l:], (len(m)-l)//2, l + i) if m[l-1] == k[l-1] else f(m[:l], k[:l], l//2, i)) if len(m) > 1 else i+l
dev_index = lambda l, k: f(l, k, len(l)//2, 0)

print(dev_index(list_a, list_b))

len fonksiyonu list örnekleri üzerinde sabit, ama list örnekleri üzerinde dilimleme yapmak lineer (kaynak). Dilimleme işlemi için memoryview ve array.array kullanılırsa sabit bir zaman karmaşıklığı elde edilir diye tahmin ediyorum.

2 Beğeni

Aa bak bu güzelmiş. Benim aklıma gelmedi. :blush:

2 Beğeni

Hatta memoryview kullanmadan şöyle bir şey yapabiliriz:

class Sublist():
    def __init__(self, l):
        self.list = l
        self.start = 0
        self.finish = len(l)

    def upto(self, finish):
        self.finish = self.start + finish
        return self

    def startfrom(self, start):
        self.start += start
        return self

    def __getitem__(self, index: int):
        i = self.start + index
        if not i < self.finish: # bu kodda gerek yok ama genel olarak böyle bir durumda hata verilmesi lazım
            raise IndexError()
        return self.list[i]

    def __len__(self):
        return self.finish - self.start 

list_a = [1, 6, 8, 9, 14, 16, 19, 21, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49, 53]
list_b = [1, 6, 8, 9, 14, 16, 19, 21, 23, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49]

f = lambda m, k, l, i: (f(m.startfrom(l), k.startfrom(l), (len(m)-l)//2, l + i) if m[l-1] == k[l-1] else f(m.upto(l), k.upto(l), l//2, i)) if len(m) > 1 else i+l
dev_index = lambda l, k: f(Sublist(l), Sublist(k), len(l)//2, 0)

print(dev_index(list_a, list_b))
2 Beğeni

Hmm, yani listenin hafızada yer kaplamamasını sağlıyor bu. Tam anlamıyla olmasa da bir generator gibi davranıyor. Generator nesnesinin len özelliğine sahip olanı hatta. :slight_smile:

Amaç hafıza kullanımını azaltmak değil, listelerin dilimlenmesi lineer zaman alıyor ama bu şekilde sabit zaman almış oluyor.

Maalesef listelerin dilimlenmesinin sabit olması ifadesini pek anlamadım. Dinamik olunca nasıl oluyor, sabit olunca nasıl oluyor?

O(1) demek istemiştim, constant diye geçiyor.

O(1) -> sabit
O(n) -> lineer

1 Beğeni

Daha iyi anlamak için soruyorum m.startfrom(l) bir O(1)'mi olmuş oluyor? Buna karşılık m[l:] ifadesi ise bir O(n) mi?

Bu arada şöyle bir deney yapınca aslında farkı daha rahat görebiliyoruz.

list_a = [*range(1000000)]
list_b = [*range(1000000)]
list_a[99990] = "a"

Son yazdığınız kodların çalışma süresi 0.00010783800007629907 saniye. Oysa ilk paylaştığınız kodların çalışma süresi 0.031673476999912964 saniye.

Evet. Çünkü yaptığı şey belli, döngü falan kullanmıyor. Hep aynı işlemi yapıyor.

Evet, hatta tam olarak O(len(m) - l). Çünkü dilimlemenin döndüreceği listenin uzunluğu arttıkça dilimleme işlemi daha çok zaman alıyor ve bu ikisi doğru orantılı.

Bu bize algoritmanın zaman karmaşıklığı (time complexity) ile alakalı birbilgi vermiyor, bir algoritmanın zaman karmaşıklığı hakkında fikir sahibi olmak için o algoritmayı farklı parametreler ile denememiz lazım. Ayrıca O(1) bir algoritma O(n) bir algoritmadan daha hızlı da olabilir.

Orayı anlamadım.

1 Beğeni

Bende soruda verilen list_a ve list_b için Sublist sınıfını kullanan kod, liste dilimleme kullanan koddan 4 kat yavaş çalışıyor mesela.

Şu kodu çalıştırıp çıktısını inceleyebilirsiniz, time complexity’nin etkisini listelerin uzunluğu artınca daha iyi anlıyoruz:

from timeit import default_timer as timer

class Sublist():
    def __init__(self, l):
        self.list = l
        self.start = 0
        self.finish = len(l)

    def upto(self, finish):
        self.finish = self.start + finish
        return self

    def startfrom(self, start):
        self.start += start
        return self

    def __getitem__(self, index: int):
        i = self.start + index
        if not i < self.finish: # bu kodda gerek yok ama genel olarak böyle bir durumda hata verilmesi lazım
            raise IndexError()
        return self.list[i]

    def __len__(self):
        return self.finish - self.start 


def ölç(f, n=100000):
    "Bir işlemi aldığı ortalama zaman."
    t = timer()
    f(n)
    return (timer() - t) / n

def logn(n):
    f = lambda m, k, l, i: (f(m.startfrom(l), k.startfrom(l), (len(m)-l)//2, l + i) if m[l-1] == k[l-1] else f(m.upto(l), k.upto(l), l//2, i)) if len(m) > 1 else i+l
    dev_index = lambda l, k: f(Sublist(l), Sublist(k), len(l)//2, 0)

    for _ in range(n):
        dev_index(list_a, list_b)   

def lineer(n):
    f = lambda m, k, l, i: (f(m[l:], k[l:], (len(m)-l)//2, l + i) if m[l-1] == k[l-1] else f(m[:l], k[:l], l//2, i)) if len(m) > 1 else i+l
    dev_index = lambda l, k: f(l, k, len(l)//2, 0)

    for _ in range(n):
        dev_index(list_a, list_b)

repeat = 100

import random
list_a = sorted(random.sample(range(1000000), 1000))
list_b = list_a.copy()
list_a.pop(random.randrange(0, len(list_a)))
list_a.append(list_a[-1] + random.randint(1, 100))

a=ölç(lineer, repeat)
print("lineer:", a)
b=ölç(logn, repeat)
print("logn:", b)

list_a = sorted(random.sample(range(1000000), 100000))
list_b = list_a.copy()
list_a.pop(random.randrange(0, len(list_a)))
list_a.append(list_a[-1] + random.randint(1, 100))

c=ölç(lineer, repeat)
print("lineer:", c)
d=ölç(logn, repeat)
print("logn:", d)

print("lineerdeki artış:", c/a)
print("logndeki artış:", d/b)

Anladım. Güzel bir yaklaşım bu.

Yok zaten O(1), O(n)'den daha hızlı sonuç verdiğini göstermek için bu örneği paylaştım.

Liste büyüdükçe aradaki farkı daha bariz bir şekilde görebiliyoruz diye böyle bir örnek yaptım. O paylaştığım sonuçlar da bu örnekle alakalı. Yani O(1)'in işlem süresi 0.00010783800007629907 saniye sürerken, O(n)'in işlem süresi 0.031673476999912964 saniye sürdü.

1 Beğeni

Standart recursive cozumumuz:

def find_divergence_index(list1, list2, start, end):
    if start == end - 1:
        if list1[start] == list2[start]:
            return None
        else:
            return start

    mid = (start + end) // 2

    dileft  = find_divergence_index(list1, list2, start, mid)
    diright = find_divergence_index(list1, list2, mid, end)

    if dileft is not None:
        return dileft
    else:
        return diright

a = [1, 6, 8, 9, 14, 16, 19, 21, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49, 53]
b = [1, 6, 8, 9, 14, 16, 19, 21, 23, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49]
di = find_divergence_index(a, b, 0, len(a))
print(di)

Lineer zamanda calisiyor ve standart loop’a karsi avantaji yok, karmasiklik dezavantaji var.

Fakat yapilabilecek ilk optimizasyon koddan bile anlasiliyor: dileft None degil ise diright'i hesaplamaya gerek yok:

def find_divergence_index(list1, list2, start, end):
    if start == end - 1:
        if list1[start] == list2[start]:
            return None
        else:
            return start

    mid = (start + end) // 2

    dileft  = find_divergence_index(list1, list2, start, mid)

    if dileft is not None:
        return dileft
    else:
        diright = find_divergence_index(list1, list2, mid, end)
        return diright

a = [1, 6, 8, 9, 14, 16, 19, 21, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49, 53]
b = [1, 6, 8, 9, 14, 16, 19, 21, 23, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49]
di = find_divergence_index(a, b, 0, len(a))
print(di)

Bir sonraki optimizasyon problem bilgimize dayaniyor: Ilk elemanlari farkli listeler farkli, son elemanlari ayni listeler ayni:

def find_divergence_index(list1, list2, start, end):
    if list1[start] != list2[start]:
        return start

    if list1[end - 1] == list2[end - 1]:
        return None

    if start == end - 1:
        if list1[start] == list2[start]:
            return None
        else:
            return start

    mid = (start + end) // 2

    dileft  = find_divergence_index(list1, list2, start, mid)

    if dileft is not None:
        return dileft
    else:
        diright = find_divergence_index(list1, list2, mid, end)
        return diright

a = [1, 6, 8, 9, 14, 16, 19, 21, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49, 53]
b = [1, 6, 8, 9, 14, 16, 19, 21, 23, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49]
di = find_divergence_index(a, b, 0, len(a))
print(di)

En kisa veya hiz/uzunluk-optimize kod olmayabilir fakat standart recursive cozumden 2 adimda geldigimiz icin basit.

Bu basit cozumu yazarken fark ediyoruz: mid bi tarafin start'i, digerinin end'i. O zaman sol/sag cagirip start/end'i kontrol etmektense mid'e bakip ona gore sola veya saga gidebiliriz:

def find_divergence_index(list1, list2, start, end):
    if start == end - 1:
        return start

    mid = (start + end) // 2

    if list1[mid] != list2[mid]:
        dileft  = find_divergence_index(list1, list2, start, mid + 1)
        return dileft
    else:
        diright = find_divergence_index(list1, list2, mid + 1, end)
        return diright

a = [1, 6, 8, 9, 14, 16, 19, 21, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49, 53]
b = [1, 6, 8, 9, 14, 16, 19, 21, 23, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49]
di = find_divergence_index(a, b, 0, len(a))
print(di)

(Yarilari bir saga kaydirdik cunku kontrol ettigimiz mid'in oncelikli olan sol tarafa denk gelmesini istiyoruz. Sola denk gelirse ilk divergence indexi yerine son non-divergence indexini buluyoruz. Off-by-1.)

2 Beğeni

Implementasyon detayi.

Algoritma bazinda konustugumuzda ikisi de ayni islem oldugu icin kompleksiteleri ayni.

Calisma suresi olcmekte buyuk sikintilar var, dogrusu matematiksel analiz.

Zaten input arttikca surelerin hangi hizda arttigina bakmak lazim, O notasyonunun olctugu sey o:


O(1) algoritmalar cogunlukla O(n) algoritmalardan daha hizli sonuc veriyor ama her zaman degil.