What is the fastest algorithm for intersection of two sorted lists? -


say there 2 sorted lists: , b.

the number of entries in , b can vary. (they can small/huge. can similar each other/significantly different).

what known fastest algorithm functionality?

can 1 give me idea or reference?

assume a has m elements , b has n elements, m ≥ n. information theoretically, best can is

   (m + n)! lg -------- = n lg (m/n) + o(n)     m!  n!

comparisons, since in order verify empty intersection, have perform sorted merge. can within constant factor of bound iterating through b , keeping "cursor" in a indicating position @ recent element of b should inserted maintain sorted order. use exponential search advance cursor, total cost on order of

lg x_1 + lg x_2 + ... + lg x_n,

where x_1 + x_2 + ... + x_n = m + n integer partition of m. sum o(n lg (m/n)) concavity of lg.


Comments

Post a Comment

Popular posts from this blog

php - trouble displaying mysqli database results in correct order -

i have table in database stores events , date expire. want display events on website display current events first expired events after? i have tried following sql $sql = "select noticeid, notice, noticedesc, noticeimg, noticedate, expirydate tbl_notices group noticeid ,expired order expirydate asc"; but returns expired results first due expirydate being ordered asc in query. my tbl_notice structure looks this noticeid => int(4) notice => varchar(100) noticedesc => text noticedate => timestamp noticeimg => varchar(40) expirydate => datetime expired => int(1) 0 current or 1 expired my php code is $sql = "select noticeid, notice, noticedesc, noticeimg, noticedate, expirydate tbl_notices group noticeid ,expired order expirydate asc"; $result = mysqli_query($conn,$sql); if ($result->num_rows > 0) { // output data of each row while($row = $result->fetch_assoc()) { ...
Read more

sql server - Cannot query correctly (MSSQL - PHP - JSON) -

i have little problem on project. , turns out query result returns nothing when value of first name or last name has 'ñ' in it. here's code config.php: <?php ini_set('mssql.charset', 'utf-8'); header('content-type: text/html; charset=utf-8'); $servername = "192.168.1.21"; /* ip add of db server */ $connection = array("database" => "db", "uid" => "?", "pwd" => "***"); $conn = sqlsrv_connect($servername, $connection); if(!$conn){ echo "connection not established."; die(print_r(sqlsrv_errors(), true)); } ?> myquery: $idnumber = $_post["idnum"]; $response = array(); $query2 = "select clname, cfname, cmname, cqualifier student cidno = '$idnumber'"; try{ $stmt2 = sqlsrv_query($conn, $query2); } catch(pdoexeption $ex){ $response["success"] = 0; $response["message"] = "d...
Read more

depending on nth recurrence of job in control M -

we have need in control m follows. have 2 daily jobs in control m job , job b. job has recurrence count of 5 per day , job b needs depend on 3rd occurrence of job a. how can achieved in control m configuration? thanks.. use runcount variable below. do below job a do not add out condition in out condition tab in steps tab: on(stmt=*, code=runcount=3) addcondtion specify condition name ex: a-ok for job b do below. specify in condition below. a-ok let me know if u need complete structure
Read more