Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Care sint cele mai ieftine mortar...

Ferdinand Residence - Sectorul 2

programel Win Movie Maker

Meritau ginerii lui Lot sa moara?
 Ce credeți ca s-ar intampla ...

Instanta amana sistematic pronunț...

se poate folosi alt incarcator US...

Parchet impermeabil + fara praguri
 Despre prima de activare

One Cotroceni

Piese noi pentru reducerea zgomot...

Refuzat la imbarcare din cauza un...
 Alungire => hipertrofie

Care este "rostul" porumb...

La mulți ani @Noua_pe_site&#...

La mulți ani @RODigitalum-me...
 

[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,077
  • Î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,216
  • Î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,216
  • Î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,077
  • Î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,525
  • Î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,290
  • Înscris: 10.08.2005
Pai fisierul vine arhivat, faci cum vrei.

#32
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,077
  • Î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,525
  • Î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,290
  • Î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,077
  • Î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

Chirurgia endoscopică a hipofizei Chirurgia endoscopică a hipofizei

"Standardul de aur" în chirurgia hipofizară îl reprezintă endoscopia transnazală transsfenoidală.

Echipa NeuroHope este antrenată în unul din cele mai mari centre de chirurgie a hipofizei din Europa, Spitalul Foch din Paris, centrul în care a fost introdus pentru prima dată endoscopul în chirurgia transnazală a hipofizei, de către neurochirurgul francez Guiot. Pe lângă tumorile cu origine hipofizară, prin tehnicile endoscopice transnazale pot fi abordate numeroase alte patologii neurochirurgicale.

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