Yani her bir işlem basamağında bakılacak sayılar yarı yarıya azaltılır.
1 Beğeni
Evet tabi dizinin sıralı olması gerekiyor. Bu yüzden önce dizi sıralanıp sonra arama işlemi yapılabilir.
1 Beğeni
Ama diziyi siralamak en az n-1 islem? :p
</tasatipkac>
Yapacak bir şey yok o konuda 
Ama veriyi sıralı bir şekilde tutan veri yapısı olursa hiç sıralamaya gerek olmaz bence. Örneğin binary tree. O zaman böyle arama algoritmalarına da gerek olmaz.
Onlara da insert log(n) :) Bol index’li buyuk database’lerin yavaslama sebebi. Yapacak bir sey yok tabi…
Bu arada binary search tree kullaniyosan onun da kendini dengelemesi lazim, yoksa worst case n'e gidiyo. (Bunu bilmiyorduysan; duz binary tree’ye 1’den 100’e kadar sayilari sirayla insert ettigini dusun.)
1 Beğeni
Ben de tam bu konuya çalışıyordum 
Bahsettiğiniz gibi ağaç gittikçe düz bir liste haline gelebilir. Bu yüzden bazı gelişmiş ağaç yapıları var. Örneğin Red-Black Tree, AVL tree, B-Tree
Tekrar merhaba, son birkaç mesajdır bahsedilen daha kısa sürede arama yapmakla alakalı bir soru sormak istiyorum.
Diyelim elimizde aşağıdakine benzer 64338 tane kayıt var.
[1, 'François I, King of France', 'M', 'AA', '12 September 1494 Jul.Cal. (21 Sep 1494 greg.)', '22:00', '2266996.417593', '45n42', '0w20', 'Cognac', 'France', 'https://www.astro.com/astro-databank/François_I,_King_of_France', [('1928', 'Traits : Personality : Ambitious'), ('262', 'Lifestyle : Financial : Wealthy'), ('151', 'Notable : Famous : Royal family')]]
Yukarıdaki listedeki her bir eleman bir veritabanının farklı sütunlarında yer alıyor. Yani toplamda 13 tane sütun var:
adb id, name, gender, rodden rating, date, time, julian date, latitude, longitude, place, country, adb link ve category
Bir kaydın birden fazla kategorisi olabiliyor. Veya farkı kayıtlar aynı kategoride de bulunabiliyor.
Aşağıdaki fonksiyon yardımıyla aynı kategoriye sahip kayıtlar kategori gruplarına dahil ediliyor. Toplamda 793 tane kategori var. Her bir kategorinin bir numarası bir de kategori ismi var. Ama bu numaralar 1, 2, 3, … şeklinde düzenlenmemiş, yani kategori numarası 3000 olan bir kategoriye rastlamak mümkün.
Şimdi, aşağıdaki fonksiyon çalıştığı zaman, benim bilgisayarımda aşağı yukarı 24 saniyede 64338 kaydın hepsi 793 kategoriye dağıtılıyor. Bu dağıtma işlemini de binary search ile daha kısa sürede yapmak mümkün müdür?
def group_categories():
global category_names, all_categories
category_names, all_categories = [], []
for _i_ in category_dict.keys():
_records_ = []
category_groups = {}
category_name = ""
for j_ in database:
for _k in j_[12]:
if _k[0] == f"{_i_}":
_records_.append(j_)
category_name = _k[1]
if category_name is None:
category_name = "No Category Name"
category_groups[(_i_, category_name)] = _records_
if not _records_:
pass
else:
if category_name not in category_names:
category_names.append(category_name)
all_categories.append(category_groups)
category_names = sorted(category_names)
Bu kategorilendirmeyi binary search ile yapamazsınız çünkü binary search bir arama algoritmasıdır. Sıralama algoritmaları daha farklı.
Binary search algoritmasını tam anlatamadım, şöyle bir gif ile daha kolay açıklayabilirim diye düşünüyorum.
Elimizde sıralı olarak bir dizi varsa, dizinin hemen ortasına geçiyoruz. Aradığımız eleman bu ortadaki elemandan büyükse sağ tarafın orta elemanına, küçükse sol tarafın orta elemanına geçiş yapıyoruz. Bu şekilde, daha fazla bölünmeyene kadar veya sayı bulunana kadar devam ediyoruz.
Dolayısıyla sizin kodunuzda arama işlemi olmadığı için, bu algoritmayı kullanmak mümkün değil. Ama kodunuzda kuyruk yapısıyla beraber Thread kullanırsanız, bir nebze hızlandırmak mümkün.
Ek olarak şunu söylemek istiyorum. Sizin elinizdeki verilerin tümü işlenmek zorunda yani, tüm verileri kategorilere ayırmak zorundasınız. Ancak binary search üzerinde, verilerin belli bir kısmını görmezden geliyoruz.
2 Beğeni
Hmm. Peki teşekkür ederim. Daha önce bu örnek için thread kullandım ama sonra kaldırdım. Bir daha denerim.
1 Beğeni
Yavas calisan, binary search’e gecirmek istedigin kisim nerede?
Python’in dictionary’leri hash table olduklari icin cok daha hizlilar bu arada.
Paylastigin bu kod, onem sirasiyla:
- Degisken isimleri olmadigi icin
- (Guzel isimlendirilmis) yardimci fonksiyon kullanmadigi icin
- Siklomatik kompleksitesi cok yuksek oldugu icin (for icinde for icinde for icinde if icinde if)
okunabilir degil. Datayi ve cagiran kodu yazmadigin icin calistirilabilir de degil. Paylasman hic bir ise yaramadi kisacasi; soruyu daha da acmani isteyecegim.
Bu arada, bu kodun tam tersini paylassaydin, yani programin datayi alip bu fonksiyon ile isleyene kadar olan kismini ve bu fonksiyon isini yaptiktan sonraki ciktisini veya ciktinin kullanim seklini paylassaydin, yardimci olabilirdik.
1 Beğeni
Tamam biraz daha açıklayıcı bir şekilde anlatmaya çalışayım.
Kodlar arasında yine bir arama işlemi gerçekleştiriliyor, eğer aranan değer bulunursa dağıtma işlemine geçiliyor. Şöyle bir koşul var. if _k[0] == f"{_i_}" Koşuldaki değişkenler string veri tipinde ancak integer veri tipine dönüştürülebilir. Bu koşul sağlanırsa, koşula uyan kayıtlar yeni listelere aktarılıyor ve bu liste, anahtar değeri kategori numarası ve kategori isminden oluşan bir tuple verisi olan bir sözlüğün değer kısmı haline getiriliyor.
Yani 793 kategorinin her biri için 64338 kaydın tutulduğu liste tekrar tekrar inceleniyor. Ve her bir kayıt birden fazla kategori içerebildiği için, bir kayıttaki kategori sayısı kadar işlem tekrar ediliyor.
Yukarıda bahsettiğim işlem benim bilgisayarımda toplamda yaklaşık 24-25 saniyede gerçekleşiyor. Bu işlem program açılırken bir kez yapılıyor. Yani fonksiyon tanıtılır tanıtılmaz, fonksiyon çağrılmaya başlıyor. Ancak kullanıcı veritabanına kayıt ekleyebildiği için, aynı fonksiyon reload database isimli bir fonksiyon içinde de çağrılıyor. Bu fonksiyon bir düğme ile çağrılabiliyor. Kullanıcı bu amaç için tanımlanmış bir düğmeye bastığı zaman veritabanındaki kayıtlar yeniden kategorilere göre düzenleniyor.
Bu arada kodların tamamını paylaşmak istemedim, ama bakmak isterseniz aşağıdaki adresten programı indirebilirsiniz. Yalnız belirtmek isterim ki, indireceğiniz program hızlı bir şekilde açılacaktır çünkü lisans koşulları yüzünden programın kullandığı veritabanını paylaşamadım. Bu veritabanı xml formatında tutuluyor. Ancak daha sonradan kullanıcıların kayıt ekleyebileceği ikinci bir veritabanı tanımladım. Bu veritabanı db formatında tutuluyor. Her iki veritabanı da birleştiriliyor, kullanıcıya o şekilde veriler gösteriliyor.
Gayet anlasilabilir bir durum. Peki ornek bir database paylasabilir misin? Kayit eklemekte zorlaniyorum:
Exception in Tkinter callback
Traceback (most recent call last):
File "/usr/lib/python3.6/tkinter/__init__.py", line 1705, in __call__
return self.func(*args)
File "TkAstroDb.py", line 3845, in <lambda>
data=None))
File "TkAstroDb.py", line 3689, in get_record_data
_latitude_ = float(entries[6].get())
ValueError: could not convert string to float:
Galiba örnek bir veritabanı vardı ama içinde çok fazla kayıt yoktu diye hatırlıyorum.
Bu arada enlem ve boylam değerlerinin ondalık veri tipinde olması gerekiyor.
Örneğin:
DMS latitude longitude coordinates for Ankara are: 39°55’11.53"N, 32°51’15.37"E.
Decimal latitude and longitude coordinates for Ankara (Turkey): 39.91987, 32.85427
Örnek veritabanını aşağıdaki linkten indirebilirsiniz. xml dosyasını programın olduğu dizine koyarsanız, program o xml dosyasını kullanacaktır. Ama örnek veritabanının içinde fazla kayıt olmadığı için, program 24 saniyeden daha kısa bir sürede açılacaktır.
Sorun burada.
Database bir kere incelenecegine 793 kere inceleniyor.
1 Beğeni
Aynen öyle. Ben de bu durumu nasıl düzeltirim diye düşünüyorum. Tamam yazdığım kod amaca uygun işlemi gerçekleştiriyor ama çok fazla sayıda işlem oluşuyor bu da bekleme süresini uzatıyor.
Database’i bir kere oku, her kaydi ait oldugu kategorilere ekle?
Yani database’i okurken kayıtlar kategorilere yerleştirilsin değil mi? Peki, ama ikinci database’e yeni kayıtlar eklenecek, bu iki veritabanının birleştirilmesi, diğer veritabanındaki kayıtların da kategorilere dağıtılması ve kategorilerin ada göre tekrar sıralanması gerekiyor.
Bunlar bambaska problemler.
Yeni kayit nedir?
Iki database varsa 5 cesit kayit var:
- Ikisinde de olmayan kayitlar
- Ikisinde de olan kayitlar
- A’da olup B’de olmayan kayitlar
- B’de olup A’da olmayan kayitlar
- Ikisinde de olup farkli olan kayitlar
Bunlardan hangileri “yeni kayit” ve hangi sartlarda ne yapmak istiyorsun hic bir fikrim yok tabi ki.
Ayni algoritma. 2 kere calisabilir.
Bu tek fonksiyon.
Istersen yeni baslik ac, orada tartisalim. Bilgi baya dagilmis durumda; iki tane database oldugunu bu mesaja kadar bilmiyordum mesela.
xml veritabanı astrodienst ekibi tarafından hazırlanmış, senelerdir üzerinde çalıştıkları bir veritabanı. Bu veritabanında hiçbir değişiklik yapmıyorum. Sadece onlar tarafından eklenmiş olan kayıtları kullanıyorum. Bu veritabanından 64338 adet kayıt ayıklayabildim.
Ayrıca program, ön-tanımlı olarak boş bir sql veritabanıyla birlikte geliyor. Bu veritabanı kullanıcıların manuel olarak yeni kayıtlar ekleyebilmeleri için programa dahil edildi. Bu veritabanına eklenen kayıtlar düzenle ve sil gibi fonksiyonlar kullanılarak değiştirilebilir ve silinebilir. (Programın ilk sürümlerinde bu sql veritabanı yoktu, sadece astrodienst’in veritabanının kullanıldığı bir programdı. Ancak ilerleyen zamanlarda programı kullanan arkadaşlar programa eklenmesini istedikleri birkaç özellikten bahsettiler. Örneğin kullanıcıların kendilerinin kontrol edebileceği kişisel bir veritabanı olması istendi. Sql veritabanı da bu sebeple programa dahil edilmiş oldu.)
5 çeşit değil, iki çeşit kayıt var. Kayıtlar ya xml veritabanındadır ya da sql veritabanındadır. Yani kullanıcılar zaten xml veritabanında olan bir kaydı sql veritabanına eklememeli.
Bu arada dediğiniz gibi konudan baya uzaklaştık, uygun bir başlık açarım bunun için.