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

[Dzint]

Ir divi masīvi array(2,4,6,1) un array (5,4,7,8,1,3). Nepieciešams izveidot jaunu masīvu tikai ar tām vērtībām kas abos masīvos ir vienādas. Šai gadījuma newArray(4,1).

[webi]

for ($i=0; $i<count($array1); $i++)
{
if (in_array($array1[$i], $array2)) $array3 = $array1[$i];
}

[bubu]

$array3 = array_intersect($array1, $array2);

[Dzint]

$array3 = array_intersect($array1, $array2);

 

Paldies, tā jau domāju ka ir kāda gatava php funkcija

[spainis]

Šā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ā

[codez]

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));

[bubu]

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.

[codez]

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 August 18, 2010 by codez

[bubu]

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

[codez]

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.

[bubu]

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