Listedeki yinelemeleri engellemenin hızlı yolları C> içinde <>

C # programım belirli bir düzenden rastgele dizeler oluşturur. Bu dizeler bir listede saklanır. Hiçbir kopyaya izin verilmediğinden, bu şekilde yapıyorum:

List myList = new List();
for (int i = 0; i < total; i++) {
  string random_string = GetRandomString(pattern);
  if (!myList.Contains(random_string)) myList.Add(random_string);
}

Tahmin edebileceğiniz gibi bu yüzlerce giriş için iyi sonuç verir. Ancak birkaç milyon karakter üretecek durumla karşı karşıyayım. Ve eklenen her dizede kopyaları kontrol etmek yavaşlar ve yavaşlar.

Yinelemeleri önlemek için daha hızlı yollar var mı?

21
@Jonesy: Belirli bir veri kümesi için test edilmeye değer bir şey gibi görünüyor. Daha hızlı olduğu ortaya çıkarsa, kişi bu performans optimizasyonunu koda eklediği şaşırtmaya karşı (bu durumda çok fazla olmayan) tartmaktadır.
katma yazar David, kaynak
hepsini eklemek de daha hızlı olur mu, sonra kopyaları kontrol etmek için Distinct() tuşunu kullanın, ardından kaldırılan numarayı geri ekleyin.
katma yazar Jonesopolis, kaynak
Sadece ilgisiz, bunları tam olarak ne için kullanıyorsun?
katma yazar musefan, kaynak
@Servy: Yeterince adil, muhtemelen doğru, kesinlikle yine de mantıklı geliyor
katma yazar musefan, kaynak
@Servy: Çatışmanın ne kadar muhtemel olduğuna bağlı. Program ilk önce Listeyi DB'den yüklemek zorundaysa, kabul edilebilir bir takas olabilir.
katma yazar musefan, kaynak
Listenizi bir veritabanında tutmaya devam ediyorsanız, alanı benzersiz kılmayı da deneyebilirsiniz ve sonra INSERT başarısız olursa farklı bir tane deneyebilirsiniz - dikkate alınması gereken bir şey
katma yazar musefan, kaynak
@Servy Ne yazık ki hayır. Bu tür özel bir şeydir, bu yüzden GUID'ler yardımcı olmaz.
katma yazar Robert Strauch, kaynak
@musefan Dokümanlar için seri numaraları üretmek için bunlara ihtiyacım var.
katma yazar Robert Strauch, kaynak
@musefan Sadece dizenin zaten var olduğunu bulmak için bütün bir DB turu gezisi yapmak sorun olurdu.
katma yazar Servy, kaynak
@musefan Bir öğenin zaten DB'de bulunup bulunmadığını belirlemek için tek bir DB sorgusu yapmak bile, bir öğenin bellekte bir karmaşa olup olmadığını görmek için milyonlarca kontrol olmasa bile yüz binden uzun sürecek. Bu sorunu çözmek için bir DB kullanmak kolayca birkaç bin kez yavaşlama olabilir.
katma yazar Servy, kaynak
@Robert Her belge için bir GUID kullanabilir misiniz?
katma yazar Servy, kaynak
yinelenenlerden kaçınmak için set kullanın
katma yazar Jayram Singh, kaynak
@David HashSet 'nin başlangıçta daha az bellek etkisi olması ve daha sonra tamamen yinelemeye gerek olmaması nedeniyle daha hızlı olacağı teorik argümanını büyük olasılıkla yapardım. Her bir öğeyi kontrol etmenin maliyeti hala mevcuttur, ancak bu veri yapısı bunun için optimize edilmiştir.
katma yazar Adam Houldsworth, kaynak

7 cevap

Bir öğenin olup olmadığını, yani HashSet olup olmadığını çok daha verimli bir şekilde belirleyebilecek bir veri yapısı kullanın. Bir öğenin, kümedeki öğe sayısına bakılmaksızın sabit zamanda sette olup olmadığını belirleyebilir.

gerçekten öğelerin yerine List içindeki öğelere ihtiyacınız varsa veya sonuçtaki listedeki öğelerin oluşturuldukları sıraya göre olmasını istiyorsanız hem liste hem de karma değer; HashSet 'de şu anda mevcut değilse, öğeyi her iki koleksiyona da ekleyerek.

35
katma
Tamam, bu yüzden bir HashSet kullandım ve hızdaki artış çok büyük. Ancak yeni bir sorunum var. Karma setinde belirli miktarda girişe ihtiyacım var. Sorumu yaptığım gibi döngü için kullanırsam, 2.000.000 döngüden sonra durur. Yinelemeler karma kümesinde yok, ancak yinelenen bir hit varsa, karma küme 2.000.000 giriş içermiyor. Bundan nasıl kaçınabilirim? if (myList.Count <2000000) myList.Add (random_string); bunu önler ancak yine de biraz yavaş olur.
katma yazar Robert Strauch, kaynak
@Robert yerine (int i = 0; i yerine, yalnızca (<0; Veya, gerçekten i 'ye ihtiyacınız yoksa, o zaman sadece iken (set.Count .
katma yazar Servy, kaynak
Görünüşe göre HasSet için öğe bulma O (1) 'dir, yani eğer bu maddeyi bulursanız = ortak listeye ekleyin.
katma yazar user2545071, kaynak

Don't use List<>. Use Dictionary<> or HashSet<> instead!

9
katma
Bir HashSet kullanarak, Listede olduğu gibi nesneye erişemez ve değiştiremezsiniz.
katma yazar ppumkin, kaynak

En kolay yol bunu kullanmaktır:

myList = myList.Distinct().ToList();

Bu, listenin bir kez oluşturulmasını ve ardından yeni bir liste oluşturulmasını gerektirse de. Daha iyi bir yol, jeneratörünüzü zamanından önce yapmak olabilir:

public IEnumerable GetRandomStrings(int total, string pattern)
{
    for (int i = 0; i < total; i++) 
    {
        yield return GetRandomString(pattern);
    }
}

...

myList = GetRandomStrings(total, pattern).Distinct().ToList();

Elbette, öğelere dizine göre erişmeniz gerekmiyorsa, ToList öğesini bırakarak ve yalnızca bir IEnumerable kullanarak verimi daha da artırabilirsiniz.

5
katma
Bir listede birkaç milyon dizeyi kaldırmak için .Distinct tuşunun kullanılması, IMO'nun verimli geldiğini göstermez.
katma yazar Darren Davies, kaynak
Ayrıca, sonuçta gereksinim duyduğunuz sayıda dize varsa, GetRandomStrings 'ın sonsuz uzun bir sekans oluşturması ve sonra sınırlandırmak için Take kullanması mantıklı olabilir. İstenilen boyut Ardından, oluşturulan dizelerin sayısını veya benzersiz Ayrı öğesinden önce veya sonra Al öğesini koyabilirsiniz. > oluşturulan dizeler.
katma yazar Servy, kaynak
@ p.s.w.g Ben sadece bir yerel olarak ayarlayıp sonra fırlatıp atmak için GetRandomStrings yönteminizin, verim anlamına geldiğini düşünüyorum.
katma yazar Servy, kaynak
@DarrenDavies Dahili olarak, Distinct , diğerleri önerdiği gibi HashSet kullanır. Tek verimsiz kısmı önce listeyi oluşturuyor, sonra cevabımın ikinci bölümünde değindiğim farklı kullanarak.
katma yazar p.s.w.g, kaynak
@ Servis Evet, teşekkürler.
katma yazar p.s.w.g, kaynak
@Servy Başlangıçta böyle uygulamıştım, ancak sonsuz jeneratörler tehlikeli olabilir ve biraz dikkatle kullanılması gerekiyor.
katma yazar p.s.w.g, kaynak

You could use a HashSet if order is not important:

HashSet myHashSet = new HashSet();
for (int i = 0; i < total; i++) 
{
   string random_string = GetRandomString(pattern);
   myHashSet.Add(random_string);
}

HashSet sınıfı, yüksek performanslı küme işlemleri sağlar. Küme, yinelenen öğeler içermeyen ve öğeleri belirli bir sıraya sahip olmayan bir koleksiyondur.

MSDN

Veya sırası önemliyse, SortedSet (yalnızca .net 4.5)

5
katma
Hashed nesnesini o zaman nasıl alabilirim? HashSet'in bir GET'i de yok. Kendini uygulamak da çok etkili değil.
katma yazar ppumkin, kaynak
Sorted< set> öğelerinin sıralandığını unutmayın. Sipariş edilen bir set gerekliyse (yani, eleman siparişi korunur) OrderedDictionary daha iyi bir seçim olacaktır. Dezavantajı, genel olmamasıdır.
katma yazar Olivier Jacot-Descombes, kaynak

iyi bir yol değil, çabuk düzeltmek, Tüm listede yinelenen bir giriş olup olmadığını kontrol etmek için bir bool almak

bool containsKey;
string newKey;

    public void addKey(string newKey){

         foreach(string key in MyKeys){
           if(key == newKey){
             containsKey = true;
          }
         }

      if(!containsKey){
       MyKeys.add(newKey);
     }else{
       containsKey = false;
     }

    }
1
katma

Bir Hashtable, bir öğenin bir listeden olup olmadığını kontrol etmenin daha hızlı bir yolu olabilir.

0
katma
Anahtar/değer ilişkisine sahip değil, sadece bir dizi ip, bu yüzden bir harita değil bir sete ihtiyacı var. Ayrıca, HashTable genel değil; gerçekten bir harita yapısına ihtiyacınız varsa bunun yerine genel Sözlük kullanıyor olmalısınız. Eski bir kodda bir HashTable kullanmamalısınız.
katma yazar Servy, kaynak

Denedin mi:

myList = myList.Distinct()
0
katma