Jump to content
php.lv forumi

Vienādās vērtības masīvos


Dzint
 Share

Recommended Posts

Šādi glabājot masīva vērtības, vienādo vērtību atrašana notiek proporcionāli O(n^2).

 

Ja datu daudzums ir liels, tad tos labāk vajadzētu glabāt associatīvā masīvā

 

$arrayAssoc1 = Array(2 => true, 4=>true, 6=>true, 1=>true);
$arrayAssoc2 = Array(5=>true, 4=>true, 7=>true, 8=>true, 1=>true, 3=>true);

function ArrayOverlap($array1, $array2) {
               $arrayKeys = array_keys($array1);
               $resultArray = Array();
               foreach($arrayKeys as $key) {
                   if(isset($array2[$key])) $resultArray[] = $key;
               }
               return $resultArray;
           }

 

Izmantojot associatīvus masīvus vienādo elementu atrašana notiek O(n) laikā

Link to comment
Share on other sites

Izmantojot associatīvus masīvus vienādo elementu atrašana notiek O(n) laikā

Tā jau gluži nebūs, jo PHP masīva elementi neglabājas tāpat kā c++ masīvā - pēc kārtas atmiņas gabalā ar noteiktu bufera izmēru, bet gan, ja nemaldos, hash-tabulā, kur piekļuves laiks pagtvaļīgam elementam vidēji būs lielāks (no O(1) līdz O(n), vidēji ap O(log2(n)) ).

 

Glabājot masīvā šādā veidā array(6,7,3,1,2) var darīt tā:

sakārto - O(n*log2(n))

iet cauri masīvam izmantojot norādītājus uz masīva elementu un izmantojot next, current funckijas. Iet cauri tā, lai abiem masīviem norādītājs būtu pie vienādām vērtībām, šādā veidā mēs varam atlasīt tos elementus, kuri nepārklājas. - O(n)

Kopā O(n*log2(n))

 

Pēc tava varianta ar foreach iet cauri visam 1. masīvam ar foreach, laiks ir O(n)

Bet ciklā jāpiekļūst patvaļīgam 2. masīva elementam - O(log2(n)).

Kopā tie paši O(n*log2(n));

Link to comment
Share on other sites

Haštabulas piekļūšanas laiks galīgi nav O(log2(n)). Tas ir bināra sakārtoa koka piekļūšanas laiks.

Labai haštabulai piekļūšanas laiks ir amortizēts O(1).

 

Man ir stipra aizdoma, ka gandrīz vienmēr ArrayOverlap veids (+ vēl pāriešana uz to) būs ātrāks nekā quicksort kārtošana un iešana cauri ar next/current. Izņemot protams ļoti mazus masīvus, vai retus pataloģiskus heša kolīziju gadījumus.

Link to comment
Share on other sites

Haštabulas piekļūšanas laiks galīgi nav O(log2(n)). Tas ir bināra sakārtoa koka piekļūšanas laiks.

Labai haštabulai piekļūšanas laiks ir amortizēts O(1).

 

Haštabulai piekļūšanas laika O(1) būs tikai tad, ja ierakstu skaits būs mazāks kā hashtabulas izmēri un pie tam neviens ieraksts neradīs vienādas hash vērtības. Taču sliktākais laiks, ja visas ierakstu vērtības radījušas vienādas hash vērtības, ir O(n). Tāpēc pie lieliem masīviem nevar pieņemt, ka hāstabulas piekļuves laiks būs O(1). Tā kā pastāv ļoti daudz dažādas nianses, kā veidot haštabulu, tad tās vidējais statistiskais piekļuves laiks ir tuvojās dažādām funkcijām - O(log2(n)), O(sqrt(n)), O(ln(n)), atkarībā no šīm niansēm un attiecības starp ierakstu daudzumu un haštabulas izmēriem.

 

Man ir stipra aizdoma, ka gandrīz vienmēr ArrayOverlap veids (+ vēl pāriešana uz to) būs ātrāks nekā quicksort kārtošana un iešana cauri ar next/current. Izņemot protams ļoti mazus masīvus, vai retus pataloģiskus heša kolīziju gadījumus.

 

To mēs varam uzzināt, tikai notestējot, bet piekrītu, ka ArrayOverlap metode varētu būt visātrākā no šeit apskatītajām.

Edited by codez
Link to comment
Share on other sites

Haštabulai piekļūšanas laika O(1) būs tikai tad

Es jau nesaku, ka tai ir O(1), es saku, ka tai ir amortizēts O(1). Tā ir liela atšķirība.

 

Tā pat, kā std::vector push_back metodes laiks arī ir amortizēts O(1).

Link to comment
Share on other sites

Amoritzētais laiks ir laiks, ko veic n secīgas operācijas dalīts ar n.

 

Piemēram, ja mums ir n elementu masīvs (atmiņas buferis), tad, lai ievietotu pa vidu jaunu elementu, pārējie elementi jāpabīda uz priekšu, kas sliktākajā gadījumā sastāda O(n). Tagad, ja mums ir jāieliek n elementi, tad mums ir jāpabīda pārējie elementi tikai vienreiz un kopējais laiks ir O(n), bet amoritzētais O(n)/n=O(1).

 

Taču patvaļīgu elementu piekļuve n izvēlētu elementu gadījumā haštabulai tik un tā katram elementam aizņems laiku O(f(n)), kur f ir kaut kāda funkcija kas tiecas uz sqrt(n), ln(n) vai ko citu, kas atkarīgs no haštabulas īpašībām. Un rezultātā n elementiem mēs piekļūsim laikā O(f(n)*n), bet amoreitzētais laiks būs O(f(n)*n)/n=O(f(n)).

Savukārt sliktākajā gadījumā piekļuve haštabulas elementam ir O(n), bet n patvaļīgu elementu piekļuves būs O(n^2), kas veidos amortizēto laiku O(n^2)/n=O(n).

 

Vienīgi gadījumā, ja mums ir n secīgu elementu piekļuve, tad n elementu piekļuves laiks būs O(n) un tad amortizētais laiks būs O(n)/n=O(1), bet ArrayOverlap piedāvātajā variantā nav n secīgu elementu piekļuve.

Link to comment
Share on other sites

kur f ir kaut kāda funkcija kas tiecas uz sqrt(n), ln(n)

Pierādi :)

 

Es gan neesmu dzirdējis, ka amortizēta sarežģītība definējas ar "secīgu elementu piekļuvi".

Amortizetā sarežģītībā veic n operācijas (nevis n elementus pēc kārtas), un ņem sarežģītāko laiku, un dala to ar operāciju skaitu (n). Ja heštabulai elementu atrast sarežģītākais ir O(n) laikā (bet pārējie ir tuvu vai precīzi O(1)), tad tās amortizētā sarežģītība ir O(n)/n = O(1).

 

Tāpat kā ar std::vector push_back'u, kurš, pie masīva pārpildīšanās, reizina savu izmēru ar 2.

Ja es likšu tajā elementus no 1..10, tad masīvs iespējams resaizosies līdz pat 4 reizēm. Taču amortizētā sarežģītība joprojām būs O(1), nevis O(log(sqrt(figzin(n))).

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

×
×
  • Create New...