Java kullanarak büyük bir tam sayı dizisinden çoğaltmaları kaldırma

Question

Java kullanarak çok büyük bir tam sayı dizisinden çoğaltılmış değerleri kaldırmak için herhangi bir zamanı etkili bir yoldan biliyor musunuz? Dizinin boyutu, oturum açmış olan kullanıcıya bağlıdır, ancak bazı yinelenen öğelerle her zaman 1500000 sıralanmamış değerleri aşacaktır. Bir List dönüştürerek çalıştı

100000 ila 9999999 Her tamsayı bir dizi içerir, ama benim sunucuda yığın (ISS bunu kısıtladı) veri bu miktarı izin vermez. Ve bir for döngüsü içinde düzenli bir döngü için hesaplamak için 5 dakika alır.

yineleme olmadan dizinin boyutu benim veritabanında depolar biridir.

Yardım memnuniyetle karşılanacaktır!

i listeye öğe ekleyerek başlayın

Answer 1

Belki bir küme kullanabilirdiniz? Java'nın BitSet'in ne kadar verimli olduğunu bilmiyorum. Ancak 9999999 olası değer sadece 9999999/8 = 1250000 byte = 1Mb'nin üzerine çıkacaktır. Değer dizisini yürüttüğünüzde, karşılık gelen biti true olarak ayarlayın. Ardından, bit setinin üzerinde yürüyebilir ve bir bit'i true olarak ayarlandığında, karşılık gelen değeri çıkartabilirsiniz.

1Mb bir işlemci önbelleğinde uyacak, böylece Bu bit uygulamaya bağlı oldukça verimli olabilir.

Bu, aynı zamanda da verileri sıralama yan etkiye sahiptir. Bu veri girişi üzerinden tek bir geçiş gerektirdiği

ve ... Bu bir O (n) algoritması, küme işlemleri de O'dur (1) ve çıkış geçiş (böyle bir dizi-bazlı grubu için) Ayrıca m (m) benzersiz değerlerin sayısıdır ve tanım olarak < = n olmalıdır.

Answer 2

Ben listede yer alan tüm değerleri saklamak bir HashSet yapacak, önce. Ardından, hashset'in eklemek istediğiniz değeri içermemesi için kontrol edin.

Answer 3

Set<Integer> set = new HashSet<Integer>(); 
Collections.addAll(set, array); 

Eğer Integer[] yerine int[] dizisi ihtiyaç sadece olacaktır.

Answer 4

Önce dizi sıralama deneyebilirsiniz:

int arr[] = yourarray; 
Arrays.sort(arr); 
// then iterate arr and remove duplicates 

Answer 5

Belki veriler üzerinde geçerken bir avuç yapabiliriz? Örneğin, verilerin üzerinden on geçiş yaptıysanız ve yukarıdaki önerilerden birini, verilerin daha küçük bir alt kümesine uyguladıysanız (örneğin, mod modunu geçtiğinde # == 0). Böylece:

for (int i = 0 to 9) { 
    set = new Set() 
    for (each entry in the data set) { 
    if (entry % i == 0) { 
     set.add(entry) 
    } 
    } 
    output set 
} 

bellek için zaman (daha az hafıza/daha fazla zaman ve bunun tersi için geçiş sayısını arttırmak) kapalı ticaret Bu şekilde.

Answer 6

Belki de işin yapılacağı nesneler yerine ilkel ile çalışan bir karma kümesi iş yapar mı?ücretsiz uygulamalar (havn't önce onları kullanılan ama belki çalışır) vardır: eminseniz

int[] newArray = new TIntHashSet(yourArray).toArray(); 

Answer 7

int[] a; 
Arrays.sort(a); 
int j = 0; 
for (int i = 1; i < a.length; ++i) { 
    if (a[i] != a[j]) { 
    ++j; 
    a[j] = a[i]; 
    } 
} 
// now store the elements from 0 to j (inclusive - i think) 

Answer 8

: gibi

http://trove4j.sourceforge.net/

http://trove4j.sourceforge.net/javadocs/gnu/trove/TIntHashSet.html

sonra bakar mısın tamsayıları (her zaman sıfırdan daha ve 1000 veya 10000 daha az örn) resonable küçük değerlere sahip olduğunu, böyle bir hile deneyebilirsiniz:

final int MAX = 100; 
    int[] arrayWithRepeats = {99, 0, 10, 99, 0, 11, 99}; 

    //we are counting here integers with the same value 
    int [] arrayOfValues = new int[MAX+1]; 
    int countOfUniqueIntegers = 0; 
    for(int i : arrayWithRepeats) { 
     if(arrayOfValues[i] == 0) { 
      countOfUniqueIntegers++; 
     } 
     arrayOfValues[i]++; 
    } 

    // you can use arrayOfValues (smaller) or convert it 
    // to table of unique values (more usable) 

    int[] arrayOfUniqueValues = new int[countOfUniqueIntegers]; 
    int index = 0; 
    for(int i = 0; i<arrayOfValues.length; i++) { 
     if(arrayOfValues[i] != 0) { 
      arrayOfUniqueValues[index] = i; 
      index++; 
     } 
    } 

    //and now arrayOfUniqueValues is even sorted 
    System.out.println(Arrays.toString(arrayOfUniqueValues)); 

Çıkış: [0, 10, 11, 99]

Answer 9

diske dizi bilgileri ve sort | uniq | wc -l <infile.txt kapalı çatal ve çıkış yakalayabilecek gerçekten umutsuz. Bellek hala çok sıkıymışsa veya tamsayıların alan alanı daha büyükse, bu gerekli olacaktır. Ben (! O bile unix çalışıyorsa) bu sevmiyorum ama benim açımdan görevi başarmak için birçok yolu vardır olmasıdır.

Bir başka gözlem, minimum değer 100,000 olmasıdır. Böylece, 100.000 değerini, 9.999.999'un maksimum değerinden çıkararak, alanın alanını azaltarak, bir miktar bellek tasarrufu sağlayabileceğiz. Belki de 100k/8 bit fıstık şeylerin şemasında, ama aslında bunu yapmakta serbesttir.