[Provocare] I.P.-uri unice intr-un fisier 120GB

romio79, on 06 aprilie 2021 - 23:58, said:

pai depinde unde te afli când îți vine o cerința de genu asta, dacă ești la școală și ai timp la greu sa o pilesti sau ești la patron/client unde trebuie sa fie gata ieri.

pai care ar fi diferenta daca parsezi ip-ul in loc de un hah sau utilizezi de exemplu un set normal fata de un sorted set? nu inteleg la ce te ajuta daca trebuia sa fie gata ieri

Webbbob, on 06 aprilie 2021 - 23:36, said:

Ciudata combinatia de hash + binary tree. Merge (daca garantezi ca hashul e unic), dar se poate si mai bine & mai usor.

_bcristian_, on 06 aprilie 2021 - 23:10, said:

Prea putina memorie alocata.

PS: Vezi ca .NET iti ofera un mod mai usor de a enumera liniile din fisier.

dani.user, on 07 aprilie 2021 - 09:59, said:

Hash-ul prin definitie este unic, o functie injectiva

Edited by radu103, 07 April 2021 - 10:07.

romio79, on 07 aprilie 2021 - 09:53, said:

sorted setu in spate e un binary tree lookupul e mai rapid decât un set normal, apoi xxHash e posibil sa fie cam pe acolo cu parsareaa. ambele le ai deja implementate știi ca merg sigur, termini mai repede tasku cu o siguranță mai mare pe implementare și mai repede decât dacă îți faci parsarea tu și calculezi indexu tu. în real life nu ai timp sa reinventezi roata, supunei tu clientului ca ii mai întârzii proiectu sa faci tu de la 0,vezi ce zice. da după cum ziceam și tu nu ai înțeles la scoala/facultate/concurs da e mișto sa ne jucam de-a algoritmu da în real life majoritatea timpului se reutilizeaza lucruri gata făcute sa iasă proiectu cât mai rpd sa ne luam salariile.

dani.user, on 07 aprilie 2021 - 09:31, said:

Ideal ar sa ajungi la rezultat fara sa te complici inutil si sa adaugi gold-plating care poate sa nu mearga

la 20 GB fisier dezarhivat in 120 GB fisier text nici nu sughita prea tare sistemul. o sa dureze vreo 5-10 min pana il dezarhiveaza dar nu va crapa sistemul
am servere de test ce comprima loguri de 50 GB in fiecare zi.

ideea e ca incarcarea datelor din fisierul de 120 GB sa se poata face fara sa scrape sistemul, apoi rezultatul sa poata fi iar stocat fara sa crape sistemul ptr ca teoretic sunt 2^32 ip-uri, adica 4,294,967,296 valori posibilie. daca incerci sa faci o structura care sa stocheze 4 miliarde inregistrari in memorie o sa crape

incape daca te chinui un pic

rex, on 07 aprilie 2021 - 10:17, said:

Inregistrarile respective sunt 0 sau 1 in cazul asta, deci incap in vreo 500 MB memorie.

radu103, on 07 aprilie 2021 - 10:07, said:

Hashul generic accepta intrari oricat de mari si scoate iesiri de o dimesiune fixa. Nu e nici unic nici injectiv.

Webbbob, on 07 aprilie 2021 - 10:08, said:

Si alte structuri de date ai deja implementate in JDK/.NET/STL/etc.

radu103, on 07 aprilie 2021 - 10:08, said:

Nu te complici. Nu impui citirea dintr-un fisier text, citesti de pe standard input si atunci nu-ti mai pasa daca datele vin dintr-un fisier, dintr-o arhiva, de pe net sau poate-s chiar generate pe loc de un program de test.

radu103, on 07 aprilie 2021 - 10:07, said:

În teorie, dar nu în lumea reală. în lumea reală aveam o infinitate de șiruri de caractere posibile, dar de exemplu în Java hash-ul poate reprezenta maxim 2^32.

Webbbob, on 07 aprilie 2021 - 10:08, said:

Mă îndoiesc. Binary tree înseamnă O(log(n)), set înseamnă O(1). Dacă n este suficient de mic și implementarea binary tree are constante suficient de mici, iar implementarea set are constate suficient de mari, atunci da, posibil să fie mai rapid să cauți în binary tree decât în set.

tavitu, on 07 aprilie 2021 - 10:39, said:

vezi https://github.com/d...ic/SortedSet.cs

dani.user, on 07 aprilie 2021 - 09:59, said:

Quote

Nu inteleg ce vrei sa spui cu prea putina memorie? Pai asta e cerinta.

Daca te referi la File.ReadLines, problema e ca nu poti sa-i specifici optiunile de la modul de deschidere a fisierului, in special parcurgerea secventiala.

Mai e chestia evidenta ca citirea si prelucrarea ar trebui sa fie facute in paralel, dar sincer sa fiu mi-e cam lene.

Quote

Cerinta este sa numeri din fisierul text, nu din arhiva. Deci optimizarea cu citit zipul ca stream nu se incadreaza.

Pai fisierul vine arhivat, faci cum vrei.

_bcristian_, on 07 aprilie 2021 - 11:57, said:

Am citit aiurea, ca ai declara array de uint dar defapt era de ulong.

_bcristian_, on 07 aprilie 2021 - 11:57, said:

O specifica ei https://referencesou...amreader.cs,240

Da, nu m-am uitat si in sursa, mersi de informatie.

sa postez si eu o implementare, probabil mai putin eficienta ca cea de mai sus ca viteza, dar am zis sa fie ceva diferit asa ca am incercat sa folosesc un fisier mapat in ram. ca sa mearga close-ul corect trebuie java >= 9

public class MemoryFile implements Closeable {
private static final int MAPPING_SIZE = 1 << 30;
private final RandomAccessFile raf;
private final List<MappedByteBuffer> mappings = new ArrayList<>();
private long maxSize;
private int elemSize = 1;
private String fileName;
public MemoryFile(String filename, long elements) throws IOException {
this.fileName = filename;
this.raf = new RandomAccessFile(filename, "rw");
this.maxSize = elements;
try {
long size = elemSize * elements;
for (long offset = 0; offset < size; offset += MAPPING_SIZE) {
long size2 = Math.min(size - offset, MAPPING_SIZE);
mappings.add(raf.getChannel().map(FileChannel.MapMode.READ_WRITE, offset, size2));
}
} catch (IOException e) {
raf.close();
throw e;
}
}

public byte get(long index) {
assert index >= 0 && index < maxSize;
long p = index * elemSize;
int mapN = (int) (p / MAPPING_SIZE);
int offN = (int) (p % MAPPING_SIZE);
return mappings.get(mapN).get(offN);
}
public void set(long index, byte b) {
	 assert index >= 0 && index < maxSize;
	 long p = index * elemSize;
	 int mapN = (int) (p / MAPPING_SIZE);
	 int offN = (int) (p % MAPPING_SIZE);
	 mappings.get(mapN).put(offN, b);
}

public void close() throws IOException {
	 try {
	 Class<?> unsafeClass = Class.forName("sun.misc.Unsafe");
	 Field unsafeField = unsafeClass.getDeclaredField("theUnsafe");
	 unsafeField.setAccessible(true);
	 Object unsafe = unsafeField.get(null);
	 Method invokeCleaner = unsafeClass.getMethod("invokeCleaner", ByteBuffer.class);
	 for (MappedByteBuffer buffer : mappings) {
	 invokeCleaner.invoke(unsafe, buffer);
	 }
	 raf.close();
	 new File(fileName).delete();
	 } catch (Exception e) {
	 throw new RuntimeException(e);
	 }
}
public static void main(String[] args) throws IOException {
	 long start = System.currentTimeMillis();
	 long count = 0;
	 long maxValue = 1l << 32;
	 try (MemoryFile stuff = new MemoryFile("test.txt", 1L << 32)) {
	 String zipFile = "ip_addresses.zip";
	 long lineRead = 0;
	 try (ZipFile zf = new ZipFile(zipFile)) {
	 ZipEntry ze = (ZipEntry) zf.entries().nextElement();
	 try (BufferedReader br = new BufferedReader(new InputStreamReader(zf.getInputStream(ze), StandardCharsets.UTF_8))) {
	 for (String line = null; (line = br.readLine()) != null;) {
		 lineRead++;
		 if (lineRead % 10_000_000 == 0) {
		 System.out.println("A citit= " + lineRead + ",unice pana acum=" + count);
		 }
		 long adress = Integer.toUnsignedLong(ByteBuffer.wrap(InetAddress.getByName(line).getAddress()).getInt());
		 if (stuff.get(adress) == 0) {
		 count++;
		 stuff.set(adress, (byte) 1);
		 }
		 if (count == maxValue) {
		 break;
		 }
	 }
	 }
	 }
	 System.out.println("Total linii citite " + lineRead + ", unice=" + count);
	 }
	 System.out.println("A durat " + (System.currentTimeMillis() - start));
}
}

LE implementarea mea citeste direct zip-ul
la mine pe laptop a rulat in 26 de minute si a gasit unice 1000000000 si linii citite a raportat 8000000000

Edited by romio79, 07 April 2021 - 14:17.

https://forum.softpe...i-adrese-ip-v4/

Edited by MarianG, 07 April 2021 - 17:22.

_bcristian_, on 06 aprilie 2021 - 23:10, said:

Am observat acum un off by 1 error