DevProTalk

Forumi IT profesionalaca
web development, web design, e-business, SEO


Idite nazad   DevProTalk > Web development i web aplikacije > Programiranje
Želite da se reklamirate ekskluzivno na ovoj poziciji? Javite se

Programiranje Java, Perl, VB, ASP, .NET, C, C++, Pascal, Delphi Sponzor: VIP izazov 3

Odgovori
 
Alati teme Način prikaza
Staro 03. 02. 2006.   #31
marinowski
Igor Marinović
Expert
 
Avatar marinowski
 
Datum učlanjenja: 09.06.2005
Lokacija: Palić
Poruke: 549
Hvala: 31
39 "Hvala" u 17 poruka
marinowski is on a distinguished road
Pošaljite ICQ poruku za marinowski
Default

Gledao sam još malo ovaj problem. Interesantan je što je postavka jednostavna, i ne trebaju nikakvi dodatni podaci da bi se počeo rešavati.

Slažem se sa bluesmanom da je najvažnije da program radi, pristalica sam pragmatičkog rešavanja problema.

Problem je bio naći funkciju koja dobro "meša" karaktere, drugi problem je brzina, treći memorija. Recimo da mt_rand ili md5 dobro odabiru random karaktere. Brzina je bila ok, ali je 300Mb bilo suviše.

Probao sam par varijanti: ideja je izgenerisati više kodova nego što treba, pa izbaciti duplikate. array_unique funkcija se čini idealna za to, ali troši 300Mb memorije. Nema veze, tu je array_sort, lakše je izbaciti duplikate iz sortiranog niza, džaba. Opet troši suviše memorije.

Sledeća ideja mi se činila zgodnom: držati niz stalno sortiran, i proveravati pomoću binarnog pretraživanja da li je novogenerisani elemenat već u nizu. Ukoliko jeste, zaboraviti ga. Ukoliko nije, ubaciti ga na pravo mesto. array_splice mi se činila prava komanda za to, ništa premeštanje čitavih segmenata niza, samo treba da se ubaci elemenat i to je to. Na žalost, array_splice se itekako usporava kako niz raste, pa je i to bilo neupotrebljivo. Perl se ponašao bolje sa spliceom, ali opet nedovoljno brzo. OK, tu je memorija bila pod kontrolom, sve je bilo u jednom nizu. Binarni search je, po očekivanju, bio munjevit.

Ja za ovakve zadatke obično koristim Perl, nekako mi je zgodnija komandna linija, a ima i dosta little-devil alata u shellu. Recimo ovakav program izgeneriše više od 2 miliona (ne unique!) kodova za manje od 30 sekundi:
Kôd:
#!/usr/bin/perl

use MD5;
use Time::HiRes qw(gettimeofday);

while ($i++ < 2001000) {
        ($s,$ms) = gettimeofday;
        print substr(MD5->hexhash(utime().$s.$ms),5,8)."\n";
}
A kako postići unique? sa sort -u komandom. Sve zajedno traje negde oko 40 sekundi. (pretpostavljam da je sort gutao memoriju)

Sve u svemu, nisam siguran koliko je PHP dobar za baratanje velikim strukturama, ima, čini se, tu mesta za optimizaciju. Svejedno, array_unique i array_splice su korisne komande, možda zatrebaju.
marinowski je offline   Odgovorite uz citat
Staro 04. 02. 2006.   #32
zextra
Boris
Grand Master
 
Avatar zextra
 
Datum učlanjenja: 01.12.2005
Lokacija: Novi Sad
Poruke: 775
Hvala: 5
156 "Hvala" u 2 poruka
zextra is on a distinguished roadzextra is on a distinguished road
Default

Uz malu modifikaciju (0.5 umesto 2 miliona iteracija, ali se md5 hash sece na 4 dela - iako bi moglo na jos vise delova - pa se u jednoj iteraciji dobiju 4 key-a umesto jednog) skripta radi nesto brze. Ukupno zauzece memorije je manje od 30mb (negde oko 25-27) za perl i sort zajedno. Propustanjem unique key-eva kroz "wc -l" dobije se da je broj duplikata uvek manji od 0.025%, sto je verovatno zadovoljavajuce, uz vreme izvrsavanja manje od 15 sekundi (sa sve sortiranjem).

Ja sam uvek pre za Perl kada je iole veca kolicina podataka u pitanju - posebno ako treba nesto da se parsuje

Eve ga i kod ako nekog zanima..
Kôd:
use Digest::MD5 qw/md5_hex/;
use Time::HiRes qw/gettimeofday/;

my $i = 0;
while( $i++ < 500_000 )
{
    my ( $m, $ms ) = gettimeofday;
    my $code = md5_hex( $m / rand( $ms ) );

    printf(
        "%s\n"x4,
        substr( $code,  0, 8 ),
        substr( $code,  8, 8 ),
        substr( $code, 16, 8 ),
        substr( $code, 24, 8 )
    );
}
A rezultat izvrsavanja...
Kôd:
$ time perl rand.pl | sort -u | wc -l
1999556

real    0m14.923s
user    0m14.129s
sys     0m0.460s
__________________
"It’s important to have goals when you pet. Otherwise you’re just rubbing another mammal for no reason." - Scott Adams
zextra je offline   Odgovorite uz citat
Staro 04. 02. 2006.   #33
Petar Marić
Python Ambassador
Master
 
Avatar Petar Marić
 
Datum učlanjenja: 06.06.2005
Lokacija: Novi Sad
Poruke: 602
Hvala: 28
27 "Hvala" u 17 poruka
Petar Marić će postati "faca" uskoro
Pošaljite ICQ poruku za Petar Marić
Lightbulb

OK, na kraju sam i ja napravio rešenje - doduše u MATLAB-u.

generate_unique_codes.m:
Kôd:
function false_hit_chance = generate_unique_codes(number_of_codes, percent_of_extra_codes, out_file)
%Generates random unique 8 character codes
%
%INPUT ARGUMENTS:
%   number_of_codes         - desired number of codes
%   percent_of_extra_codes  - percent of extra generated codes.
%                             A non-zero value might be needed to eliminate nonunique codes
%   out_file                - file to which the codes will be outputed
%OUTPUT:
%   false_hit_chance        - odds of a false hit
%NOTES:
%   The codes themselves are a hexadecimal representation of randomly generated 32 bit integers
%   The odds of a false hit are number_of_codes/2^32

maximum_number_of_codes = 2^32; %do not change this or the code wont work

if number_of_codes > maximum_number_of_codes
    error('ERROR: Unable to generate desired number of codes! Try decrasing the value of number_of_codes')
end
if percent_of_extra_codes < 0
    error('ERROR: percent_of_extra_codes must be a non-negative number! Try increasing the value of percent_of_extra_codes')
end

codes = unique(  randint(1, round( number_of_codes*(1 + percent_of_extra_codes/100) ), maximum_number_of_codes)  );

length_of_generated_codes = length(codes);
if length_of_generated_codes < number_of_codes
    error('ERROR: Failed to generate the desired number of codes! Try increasing the value of percent_of_extra_codes parameter.')
end

codes(number_of_codes+1:length_of_generated_codes) = []; %erase the unwanted codes

fp = fopen(out_file, 'w');
fprintf(fp, '%08x\n', codes);
fclose(fp);

false_hit_chance = number_of_codes/maximum_number_of_codes;
test.m:
Kôd:
out_file = 'out.txt';
test_cases = [ 1e2  0.1
               1e3  0.1
               1e4  0.1
               1e5  0.1
               1e6  0.1
               2e6  0.1 ];


%%%% DO NOT EDIT BELOW THIS LINE %%%%
number_of_tests = size(test_cases, 1);
tmp = sprintf('Starting the test with %d test case(s)...\n', number_of_tests);
disp(tmp)

for i = 1:number_of_tests
    number_of_codes         = test_cases(i, 1);
    percent_of_extra_codes  = test_cases(i, 2);

    tmp = sprintf('TEST %3d: CALLING generate_unique_codes(%d, %g, \"%s\")', i, number_of_codes, percent_of_extra_codes, out_file);
    disp(tmp)
    start_time = clock;
    
    generate_unique_codes(number_of_codes, percent_of_extra_codes, out_file);
    
    stop_time = clock;
    elapsed_time = etime(stop_time, start_time);
    tmp = sprintf('TEST %3d was done in %g second(s).\n', i, elapsed_time);
    disp(tmp)
end

disp('All test cases were successfully completed.')
Rezultati testa:
Kôd:
>> test
Starting the test with 6 test case(s)...

TEST   1: CALLING generate_unique_codes(100, 0.1, "out.txt")
TEST   1 was done in 0.016 second(s).

TEST   2: CALLING generate_unique_codes(1000, 0.1, "out.txt")
TEST   2 was done in 0 second(s).

TEST   3: CALLING generate_unique_codes(10000, 0.1, "out.txt")
TEST   3 was done in 0.031 second(s).

TEST   4: CALLING generate_unique_codes(100000, 0.1, "out.txt")
TEST   4 was done in 0.375 second(s).

TEST   5: CALLING generate_unique_codes(1000000, 0.1, "out.txt")
TEST   5 was done in 3.766 second(s).

TEST   6: CALLING generate_unique_codes(2000000, 0.1, "out.txt")
TEST   6 was done in 7.797 second(s).

All test cases were successfully completed.
>>
Naravno svi kodovi su jedinstveni i generiše se tačno zahtevani broj kodova, tj ako se mogu generisati pri zadatim uslovima.

Šta na kraju da kažem do: The speed of my code sparkels your mind
__________________
Python Ambassador of Serbia
Petar Marić je offline   Odgovorite uz citat
Staro 04. 02. 2006.   #34
marinowski
Igor Marinović
Expert
 
Avatar marinowski
 
Datum učlanjenja: 09.06.2005
Lokacija: Palić
Poruke: 549
Hvala: 31
39 "Hvala" u 17 poruka
marinowski is on a distinguished road
Pošaljite ICQ poruku za marinowski
Default

Zextrino iskoristavanje citavog md5 je pametno, gotovi se rezultati u fileu dobivaju za oko 15 sekundi.

Maricevo resenje stvarno radi munjevito, kod mene zavrsi posao za 3.8s (!), svaka cast. Matlab stvarno lepo mesa brojeve, i unique funkcija mu je munjevita.

Probao sam slicno u Perlu, Matlab kod je u sustini ovo:
Kôd:
for ($i = 0; $i<2002000; $i++) {
        printf("%08x\n",rand(2000000000));
}
gde je 2002000 'nesto vise' od 2 miliona, a 2 milijarde dovoljno veliki broj da se ne pojave duplikati. Rezultat izvrsavanja uz sort -u je bio negde oko 17s.

Right tool for the right job
marinowski je offline   Odgovorite uz citat
Staro 04. 02. 2006.   #35
zextra
Boris
Grand Master
 
Avatar zextra
 
Datum učlanjenja: 01.12.2005
Lokacija: Novi Sad
Poruke: 775
Hvala: 5
156 "Hvala" u 2 poruka
zextra is on a distinguished roadzextra is on a distinguished road
Default

Off Topic: Jbg ako bi to Perl odradio brze od MATLAB-a, mislim da bi s razlogom mogli da se zapitamo cemu zapravo MATLAB sluzi..


Svaka cast na resenju Petre
__________________
"It’s important to have goals when you pet. Otherwise you’re just rubbing another mammal for no reason." - Scott Adams

Poslednja izmena od zextra : 04. 02. 2006. u 11:02.
zextra je offline   Odgovorite uz citat
Staro 04. 02. 2006.   #36
zextra
Boris
Grand Master
 
Avatar zextra
 
Datum učlanjenja: 01.12.2005
Lokacija: Novi Sad
Poruke: 775
Hvala: 5
156 "Hvala" u 2 poruka
zextra is on a distinguished roadzextra is on a distinguished road
Default

Moze i Perl (+ bash) za manje od 10 sec:

Kôd:
use Digest::MD5 qw/md5_hex/;
use Time::HiRes qw/gettimeofday/;

while( $i++ < 80_000 * 1.001 )
{
    my ( $m, $ms ) = gettimeofday;
    my $code = md5_hex( $m . $ms );

    for( $a = 0; $a < 25; $a++ )
    {
        print substr( $code, $a, 8 ), "\n";
    }
}
Manje petljanja - brze izvrsenje...

Kôd:
$ time perl rnd.pl > /dev/null

real    0m2.542s
user    0m2.452s
sys     0m0.032s

$ time perl rnd.pl | sort -u | head -n 2000000 | wc -l
2000000

real    0m9.187s
user    0m8.629s
sys     0m0.320s
Naravno, MATLAB opet odradi posao znatno brze. Pandan MATLAB-ovog resenja radi malo sporije (11 sec prosek), i generise neznatno vise duplikata (0.05% umesto 0.025%).
__________________
"It’s important to have goals when you pet. Otherwise you’re just rubbing another mammal for no reason." - Scott Adams

Poslednja izmena od zextra : 04. 02. 2006. u 11:33.
zextra je offline   Odgovorite uz citat
Staro 04. 02. 2006.   #37
marinowski
Igor Marinović
Expert
 
Avatar marinowski
 
Datum učlanjenja: 09.06.2005
Lokacija: Palić
Poruke: 549
Hvala: 31
39 "Hvala" u 17 poruka
marinowski is on a distinguished road
Pošaljite ICQ poruku za marinowski
Default

Jeste bolje $m . $ms nego $m / $ms, jer konkatenacija oduzima manje procesora nego deljenje ... Medjutim, ovako rezultati opasno lice, ja bas jedan md5() ne bih koristio 25 puta ...
marinowski je offline   Odgovorite uz citat
Staro 04. 02. 2006.   #38
Petar Marić
Python Ambassador
Master
 
Avatar Petar Marić
 
Datum učlanjenja: 06.06.2005
Lokacija: Novi Sad
Poruke: 602
Hvala: 28
27 "Hvala" u 17 poruka
Petar Marić će postati "faca" uskoro
Pošaljite ICQ poruku za Petar Marić
Default

Hvala svima na pohvalama

Samo da napomenem jednu bitnu stvar - onih 0.025% koje Zextra pominje nastaju ako se percent_of_extra_codes postavi na 0 - zato i postoji taj parametar.
Sad kad malo razmislim, mislim da sam bio prilično velikodušan što sam postavio percent_of_extra_codes na 0.1% - skript radi i sa 0.026%. što je savršeno logično. U stvari, potrebno je da percent_of_extra_codes bude samo neznatno veći od procenta očekivanog broja duplih kodova.
__________________
Python Ambassador of Serbia
Petar Marić je offline   Odgovorite uz citat
Staro 04. 02. 2006.   #39
Petar Marić
Python Ambassador
Master
 
Avatar Petar Marić
 
Datum učlanjenja: 06.06.2005
Lokacija: Novi Sad
Poruke: 602
Hvala: 28
27 "Hvala" u 17 poruka
Petar Marić će postati "faca" uskoro
Pošaljite ICQ poruku za Petar Marić
Exclamation

Citat:
Originalno napisao zigor
...
gde je 2002000 'nesto vise' od 2 miliona, a 2 milijarde dovoljno veliki broj da se ne pojave duplikati. Rezultat izvrsavanja uz sort -u je bio negde oko 17s.
...
Ne bi trebao da koristiš opseg od [0..2e9-1] već [0..2^32-1] upravo zato da bi imao uniformnu raspodelu generisanih kodova.
Ovako si odsekao 53.43% mogućih kodova što je najverovatnije razlog zbog kojeg dobijaš dva puta više duplikata.
__________________
Python Ambassador of Serbia
Petar Marić je offline   Odgovorite uz citat
Staro 04. 02. 2006.   #40
zextra
Boris
Grand Master
 
Avatar zextra
 
Datum učlanjenja: 01.12.2005
Lokacija: Novi Sad
Poruke: 775
Hvala: 5
156 "Hvala" u 2 poruka
zextra is on a distinguished roadzextra is on a distinguished road
Default

Omg sa cime se mi zavitlavamo...

@zigor: Slazem se da su dosta slicni kodovi, ali nakon mesanja istih, verovatnoca je nesto veca od 1:80.000 da iz te gomile izvuces dva koda koja su slicna... Doduse, ako se Marfi pita, verovatnoca je tek nesto veca od 1:5 ili tako nekako

@Petar: dobro zapazanje
__________________
"It’s important to have goals when you pet. Otherwise you’re just rubbing another mammal for no reason." - Scott Adams
zextra je offline   Odgovorite uz citat
Odgovori


Alati teme
Način prikaza

Pravila pisanja
Možete ne započinjati nove teme
Možete ne slati odgovore
Možete ne slati priloge
Možete ne izmeniti svoje poruke
vB kôd je Uključen
Smajliji su Uključen
[IMG] kod je Uključen
HTML kôd je Isključen
Pogledajte forum

Slične teme
Tema Početna poruka teme Forum Odgovori Poslednja poruka
random + mysql mega023 PHP 9 09. 03. 2010. 17:08
random select na velikoj tabeli kodi SQL baze podataka - Sponzor: Baze-Podataka.net 14 09. 04. 2008. 13:46
random koji favorizuje kodi Programiranje 16 29. 04. 2007. 22:09
java.util.Random security Ivan Programiranje 0 02. 01. 2007. 19:43
Random image - preraditi za flash... headcutter (X)HTML, JavaScript, DHTML, XML, CSS 4 02. 09. 2005. 23:14


Vreme je GMT +2. Trenutno vreme je 20:57.


Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.
Mišljenja, saveti, izjave, ponude ili druge informacije ili sadržaji nastali na Sajtu su vlasništvo onoga ko ih je kreirao, a ne DevProTalk.com, tako da ne morate da se oslanjate na njih.
Autori poruka su jedini odgovorni za ovakve sadržaje. DevProTalk.com ne garantuje tačnost, kompletnost ili upotrebnu vrednost informacija, stavova, saveta ili datih izjava. Ne postoje uslovi pod kojima bi mi bili odgovorni za štetu ili gubitak koji je posledica bilo čijeg oslanjanja na nepouzdane informacije, ili bilo kakve informacije nastale kroz komunikaciju između registrovanih članova.
Web sajt može sadržavati linkove na druge web sajtove na Internetu ili neke druge sadržaje. Ne kontrolišemo niti podržavamo te druge web sajtove, niti smo pregledali bilo kakve sadržaje na takvim sajtovima. Mi nećemo biti odgovorni za legalnost, tačnost ili prikladnost bilo kog sadržaja, oglasa, proizvoda, usluga ili informacije lociranim na ili distribuiranih kroz druge web sajtove, niti za bilo kakvu štetu nastalu kao posledica takvih informacija. DevProTalk.com drži i čuva druga prava vlasništva na web sajtu. Web sajt sadrže materijale zaštićene copyright-om, zaštitne znakove i druge informacije o pravu vlasništva ili softver. Članovi mogu poslatu informacije zaštićene pravima vlasništva njihovih nosilaca i ona ostaju zaštićena bez obzira da li su oni koji prenose te informacije to naveli ili ne. Osim informacija koje su u javnom vlasništvu ili za koje dobijete dozvolu, nemate pravo da kopirate, modifikujete ili na bilo koji način menjate, objavljujete, prenosite, distribuirate, izvršavate, prikazujete ili prodajte bilo koju informaciju zaštićenu pravima vlasništva. Slanjem informacija ili sadržaja na bilo koji deo DevProTalk.com, Vi automatski dozvoljavate i predstavljate garanciju da imate pravo da dozvolite DevProTalk.com ili članovima DevProTalk.com bespovratnu, kontinualnu, neograničenu, globalnu dozvolu da koriste, kopiraju, izvršavaju, prikazuju i distribuiraju takve informacije i sadržaje i da iz takvih sadžaja koriste bilo koji deo u bilo koje svrhe, kao i pravo i dozvolu da koriste gore navedene sadržaje. Svi zaštitni znakovi (trademarks), logotipi, oznake usluga, firme ili imena proizvoda koji se pominju na ovom web sajtu su vlasništvo kojim raspolažu njihovi vlasnici.