Röportaj bir soru

Dört milyar tamsayılar ile giriş dosya vermiş, dosyasında olmayan bir tam sayı üretmek için bir algoritma sağlar. 1GB bellek varsayalım. Eğer bellek sadece 10 MiB varsa ne yapacağınızı takip edin.

Benim analizi:

Dosya boyutu 4 * 10⁹* 4 = 16 bayt GiB.

Harici sıralama yapabiliriz, böylece tam sayı aralığı daha iyi tanıyoruz. Benim sorum sıralanmış büyük tamsayı kümeleri eksik tamsayı ortaya çıkarmanın en iyi yolu nedir?

Benim anlayış(tüm cevapları okuduktan sonra):

32-bit tamsayı bahsediyoruz varsayarak. = 4*2^32 10⁹farklı tamsayılar.

Durum 1: 1 GiB = 1 * 10⁹bayt = 8 milyar bayt bit/ * 8 bit bellek. Eğer biraz farklı bir tamsayı temsil eden kullanırsak yeterli. çözüm: bilmiyoruz tür gerekir. Uygulama:

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i  ){
        for(int j =0; j<radix; j  ){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix j);
        }
    }
}

Durum 2: 10 MB hafıza = 10 * 10⁶* 8 bit = 80 milyon bit

Solution: For all possible 16-bit prefixes, there are 2^16 number of
integers = 65536, we need 2^16 * 4 * 8 = 2 million bits. We need build
65536 buckets. For each bucket, we need 4 bytes holding all possibilities because
 the worst case is all the 4 billion integers belong to the same bucket.

Step 1: Build the counter of each bucket through the first pass through the file.
Step 2: Scan the buckets, find the first one who has less than 65536 hit.
Step 3: Build new buckets whose high 16-bit prefixes are we found in step2
through second pass of the file
Step 4: Scan the buckets built in step3, find the first bucket which doesnt
have a hit.

The code is very similar to above one.

Sonuç: Biz dosya da artırarak bellek azaltın.

Bir açıklama için geç gelenler: Bu soru, sordu, değil ki bu tam olarak bir tamsayı değil içerdiği dosya -- en azından bu insanların çoğu yorumlar. Yorum iplik birçok yorumgörevin bu değişim hakkında ama. Ne yazık ki Açıklama Butanıttıyorum iplik sonra, yazarı tarafından silindi, şimdi her şeyi yanlış anladığım için artık cevap gibi görünüyor. Çok kafa karıştırıcı. Özür dilerim.

"Tamsayı" 32 bit demektir . varsayarak : Sahip 10 MB alan daha senin için yeterli sayı kaç sayı vardır giriş dosyası ile herhangi bir 16-bit önek için mümkün olan tüm 16-bit önekleri bir geçer giriş dosyası. Kova en az bir tane az 2^16 kez daha vurmak zorunda kalacak. İkinci bir geçiş mümkün numaralarını olacağını kova zaten kullanılıyor bulmak için elimden geleni yaparım.

Eğer birden fazla 32 bit anlamına gelir, ama yine de sınırlı boyutta: Yukarıda, (imzalı veya imzasız; senin seçimin) 32-bit aralığının dışında düşme meydana tüm giriş numaralarını görmezden.

"Tamsayı" matematik tam sayı . anlamına geliyorsa ..: Giriş ile bir kez okuyun ve takip edinen büyük sayışimdiye kadar gördüğüm en uzun süresi. İşiniz bittiğinde, çıkışmaksimum artı birbir tane daha var haneli rastgele bir sayı. (Dosya sayıları 10'dan fazla) tam olarak temsil etmesi gereken bir bignum olabilir, ama eğer bir giriş dosyası ise, o zaman en azından gösterebiliruzunluğubunun içine sığan bir şey).