Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Extras de cont cu semnatura elect...

Ce parere aveti despre ascasa.de ...

Sfat achizitie bmw e92 320d

switch Gigabit POE pentru toate e...
 Triunghi

Relatie, vorbit prin mesaje

Radon!

S-a ocupat Dumnezeu de formarea o...
 Windows 10 Pro - Automatic Repair...

Purici pisica apartament

Romania se afla in top 5 cele mai...

Dividende 2023 declaratia unica A...
 kit placa de baza si procesor pen...

Cum aflu balanta unei adrese cu b...

Sfaturi achitizie PC - Cabinet Av...

Sonerie modulara montata in tablo...
 

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

- - - - -
  • Please log in to reply
36 replies to this topic

#19
Webbbob

Webbbob

    Member

  • Grup: Members
  • Posts: 636
  • Înscris: 22.03.2019

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

cu ce te ajuta sa faci un hash în loc sa le parsezi? sau sa le pui în sorted set fata de soluția de mai sus?
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.

#20
romio79

romio79

    Active Member

  • Grup: Members
  • Posts: 1,655
  • Înscris: 30.03.2005
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 :)

#21
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,106
  • Înscris: 24.02.2007

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

pentru cerința data eu nu m-as complica sa le parsez ci as face un hash(long) pe fiecare linie apoi cele unice stocate într-un SortedSet<T> sa fie look-upurile rapide(binary tree),câteva linii maxim in total.

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:

La ora asta nu stau sa-l fac mai bine, oricum, viteza e limitata de citirea de pe disc.
Evident ca in productie nici nu se pune problema sa parsezi asa ip-uri Posted Image

Prea putina memorie alocata.

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

#22
radu103

radu103

    Guru Member

  • Grup: Senior Members
  • Posts: 12,226
  • Înscris: 15.11.2003

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

... Merge (daca garantezi ca hashul e unic), dar se poate si mai bine & mai usor.
Hash-ul prin definitie este unic, o functie injectiva

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


#23
Webbbob

Webbbob

    Member

  • Grup: Members
  • Posts: 636
  • Înscris: 22.03.2019

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

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 :)
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.

#24
radu103

radu103

    Guru Member

  • Grup: Senior Members
  • Posts: 12,226
  • Înscris: 15.11.2003

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

Nu mai stiu exact structura zip, dar ideal ar fi sa-l procesezi direct pe masura ce descarci arhiva.
Ideal ar sa ajungi la rezultat fara sa te complici inutil si sa adaugi gold-plating care poate sa nu mearga

#25
rex

rex

    Senior Member

  • Grup: Senior Members
  • Posts: 4,619
  • Înscris: 16.06.2004
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

#26
romio79

romio79

    Active Member

  • Grup: Members
  • Posts: 1,655
  • Înscris: 30.03.2005
incape daca te chinui un pic :)

#27
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,106
  • Înscris: 24.02.2007

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

daca incerci sa faci o structura care sa stocheze 4 miliarde inregistrari in memorie o sa crape

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

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

Hash-ul prin definitie este unic, o functie injectiva

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:

ambele le ai deja implementate știi ca merg sigur

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

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

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

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.

#28
tavitu

tavitu

    Minune: HE a început să emită facturile!

  • Grup: Senior Members
  • Posts: 5,598
  • Înscris: 16.02.2009

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

Hash-ul prin definitie este unic, o functie injectiva
Î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:

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.
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.

#29
Webbbob

Webbbob

    Member

  • Grup: Members
  • Posts: 636
  • Înscris: 22.03.2019

 tavitu, on 07 aprilie 2021 - 10:39, 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.


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.
vezi https://github.com/d...ic/SortedSet.cs

#30
_bcristian_

_bcristian_

    Senior Member

  • Grup: Senior Members
  • Posts: 3,527
  • Înscris: 31.12.2006

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

Prea putina memorie alocata.

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

Quote

It is necessary to calculate the number of unique IP addresses in this file, consuming as little memory and time as possible.
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. :D


Quote

A simple text file with IPv4 addresses is given.
Cerinta este sa numeri din fisierul text, nu din arhiva. Deci optimizarea cu citit zipul ca stream nu se incadreaza.

#31
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,293
  • Înscris: 10.08.2005
Pai fisierul vine arhivat, faci cum vrei.

#32
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,106
  • Înscris: 24.02.2007

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

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

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

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

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.

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

#33
_bcristian_

_bcristian_

    Senior Member

  • Grup: Senior Members
  • Posts: 3,527
  • Înscris: 31.12.2006
Da, nu m-am uitat si in sursa, mersi de informatie.

#34
romio79

romio79

    Active Member

  • Grup: Members
  • Posts: 1,655
  • Înscris: 30.03.2005
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.


#35
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,293
  • Înscris: 10.08.2005
https://forum.softpe...i-adrese-ip-v4/

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


#36
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,106
  • Înscris: 24.02.2007

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

La ora asta nu stau sa-l fac mai bine, oricum, viteza e limitata de citirea de pe disc.
Evident ca in productie nici nu se pune problema sa parsezi asa ip-uri Posted Image

Am observat acum un off by 1 error :D

Anunturi

Neurochirurgie minim invazivă Neurochirurgie minim invazivă

"Primum non nocere" este ideea ce a deschis drumul medicinei spre minim invaziv.

Avansul tehnologic extraordinar din ultimele decenii a permis dezvoltarea tuturor domeniilor medicinei. Microscopul operator, neuronavigația, tehnicile anestezice avansate permit intervenții chirurgicale tot mai precise, tot mai sigure. Neurochirurgia minim invazivă, sau prin "gaura cheii", oferă pacienților posibilitatea de a se opera cu riscuri minime, fie ele neurologice, infecțioase, medicale sau estetice.

www.neurohope.ro

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate