[]
Yazılımcılara bir algoritma sorusu.
Bir search işlemi için listede kayıtlı milyonlarca isim içinden ilk 3 harfi “mar” olanları herhangi bir veritabanı olmadan daha önce eklenilen isimlerin içinden bulup yazmasını istiyoruz. Basit işlemler için for ile listeyi dönüp if ile kontrol şartı koyup yeni listeyi de konsola yazdırabiliyorken milyonlarca ismin olduğu bir yerde (bu arada illa bir listede tutulma şartı yok) bu search işlemi için kurmamız gereken algoritma nedir?
Sortlardan birini kendine sec alfabetik diz, sonrasi mili saniye zaten.
Liste diziliyse binary search iyidir. Dondurup if'e sokmak yavaslatir.
Liste diziliyse binary search iyidir. Dondurup if'e sokmak yavaslatir.
- divit
(01.06.22 16:29:12)
liste dinamik mi? eklemeler cikartmalar olacak mi? aramalar dinamik mi? sadece mar mi ariyorsunuz yoksa farkli seyler arayacak misiniz? sadece ilk harfleri mi arayacaksiniz? fuzzy arama gerekiyor mu? (m*r mesela veya mar'a benzeyen diger seyler) - bu sorularin cevabina gore hem algoritma hem de ek teknoloji kullanilacaksa ne kullanilacagi degisir.
soruyu sordugun sekliyle, evet listeyi bir kere alfabetik olarak siralarsin sonra binary search ile kolayca bulursun. ama eklemeler olacaksa listeye dogru siraya eklemen gerekir yani eklemeler yavaslar mesela. her yontemin kendine has tradeofflari var.
soruyu sordugun sekliyle, evet listeyi bir kere alfabetik olarak siralarsin sonra binary search ile kolayca bulursun. ama eklemeler olacaksa listeye dogru siraya eklemen gerekir yani eklemeler yavaslar mesela. her yontemin kendine has tradeofflari var.
- robokot
(01.06.22 16:35:13)
sadece java'ya hakim olduğum için ondan konuşacağım;
herhangi bir collection şeklinde geliyor diye düşünüyorum onu stream yaparsın ondan filter ile metodunu daha önceden yazdığın boolean dönen bir metod(yani sadece ilk 3 harfi karşılaştıran) ayrıştırısın, sonra buna forEach yaparsın yazdırırsın
ama bu dediklerim için stream biliyor olmak lazım. for ve if 'e girmek çok amatörce olur ve arkadaşların dediği gibi yavaşlatır.
herhangi bir collection şeklinde geliyor diye düşünüyorum onu stream yaparsın ondan filter ile metodunu daha önceden yazdığın boolean dönen bir metod(yani sadece ilk 3 harfi karşılaştıran) ayrıştırısın, sonra buna forEach yaparsın yazdırırsın
ama bu dediklerim için stream biliyor olmak lazım. for ve if 'e girmek çok amatörce olur ve arkadaşların dediği gibi yavaşlatır.
- high hopes of the sozluk (01.06.22 16:52:17 ~ 16:53:06)
@robokot evet listeye ekleme de yapılacak ama dediğim gibi liste kullanımı şart değil başka bir yapı da olabilir. Keyword olarak da trie kelimesi verilmiş ama ağaç yapısını burada sıralama için mi kullanmaj ile ilgili söyleniyor bilemiyorum.
Aslında sıralı bir sorgulama var aynı bir ismi googleda search eder gibi. “Mar”, “davido” “michae” gibi 3-4-5 sıralı harfle bir sorgu attığımızı düşünebiliriz. Liste dinamik çünkü ekleme durumu da var, sorguyu kendimiz belirliyoruz diyelim ama sadece sonuç yazılıyor ekrana. Mar yazıyoruz ve bize örneğin [maria, margreta, marhinos, ….] geliyor. Ya da davi yazdığımızda [david, davel] geliyor. Ne sorgularsak kaç harf sorgularsak artık.
Burada 1 milyonluk isim listesi mar için en kötü senaryoda 3 milyonluk en iyi senaryoda 1 milyonluk sorgu oluyor ya. Bunu min süreye indirmek.
Aslında sıralı bir sorgulama var aynı bir ismi googleda search eder gibi. “Mar”, “davido” “michae” gibi 3-4-5 sıralı harfle bir sorgu attığımızı düşünebiliriz. Liste dinamik çünkü ekleme durumu da var, sorguyu kendimiz belirliyoruz diyelim ama sadece sonuç yazılıyor ekrana. Mar yazıyoruz ve bize örneğin [maria, margreta, marhinos, ….] geliyor. Ya da davi yazdığımızda [david, davel] geliyor. Ne sorgularsak kaç harf sorgularsak artık.
Burada 1 milyonluk isim listesi mar için en kötü senaryoda 3 milyonluk en iyi senaryoda 1 milyonluk sorgu oluyor ya. Bunu min süreye indirmek.
- filipis (01.06.22 16:54:34 ~ 17:11:01)
- dr doofenshmirtz (01.06.22 18:41:04)
C# için LINQ:
list.Where(x => x.ToLower().StartsWith(“mar”)).ToList();
Size yeni listeyi döndürür.
list.Where(x => x.ToLower().StartsWith(“mar”)).ToList();
Size yeni listeyi döndürür.
- Tisatiaşer (01.06.22 19:53:48)
isin icine milyonlarca kayit giriyorsa bunun icin "trie" veri yapisini kullanmak en hizli cozum.
www.geeksforgeeks.org
medium.com
www.geeksforgeeks.org
medium.com
- emrahday (02.06.22 00:09:23 ~ 00:10:23)
hep ilk 3 harfi arayacaksan bütün kelimelerin ilk 3 harfini hash'leyip bir hash table'a koy. sonra lookup'ların da insert'lerin de O(1)('e yakın) olur :)
niye O(1) olmayabilir? çünkü belki bucket lazım. ama her türlü ağaçtan falan hızlı olur.
edit: sonraki yorumu gördüm, hash table olmuyor 4 harfli de arayacaksan :/
niye O(1) olmayabilir? çünkü belki bucket lazım. ama her türlü ağaçtan falan hızlı olur.
edit: sonraki yorumu gördüm, hash table olmuyor 4 harfli de arayacaksan :/
- plutongezegendegilmi (02.06.22 00:26:39 ~ 00:33:31)
1
