Tempo complessità / MySQL analisi delle prestazioni

Question

Impostazione (MySQL):

create table inRelation(
    party1 integer unsigned NOT NULL,
    party2 integer unsigned NOT NULL,
    unique (party1,party2)
);

insert into inRelation(party1,party2) values(1,2),(1,3),(2,3),(1,4),(2,5),(3,5),(1,6),(1,7),(2,7),(5,7);

mysql> select * from inRelation a
    -> join inRelation b on a.party2=b.party1
    -> join inRelation c on b.party2=c.party1
    -> where a.party1=1 and c.party2=7;
+--------+--------+--------+--------+--------+--------+
| party1 | party2 | party1 | party2 | party1 | party2 |
+--------+--------+--------+--------+--------+--------+
|      1 |      2 |      2 |      5 |      5 |      7 |
|      1 |      3 |      3 |      5 |      5 |      7 |
+--------+--------+--------+--------+--------+--------+
2 rows in set (0.00 sec)

mysql> explain select * from inRelation a
    -> join inRelation b on a.party2=b.party1
    -> join inRelation c on b.party2=c.party1
    -> where a.party1=1 and c.party2=7;
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+
| id | select_type | table | type   | possible_keys | key    | key_len | ref                 | rows | Extra       |
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+
|  1 | SIMPLE      | b     | index  | party1        | party1 | 8       | NULL                |   10 | Using index |
|  1 | SIMPLE      | a     | eq_ref | party1        | party1 | 8       | const,news.b.party1 |    1 | Using index |
|  1 | SIMPLE      | c     | eq_ref | party1        | party1 | 8       | news.b.party2,const |    1 | Using index |
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+

Questa è una soluzione BFS per il mio precedente post:

Sfida, come implementare un algoritmo per sei grado di separazione?

Ma qual è la complessità di esso? Supponiamo che ci siano record totalmente n.

Answer 1

Supponendo che non ci sono N vertici e spigoli E. Per ogni tavolo ci può essere un join tra ogni coppia di vertici e bisogno di controllare tutti i vertici per l'uguaglianza. Così peggiore performance caso sarà O (| V | + | E |)

Aggiornamento: Se state pensando di Mysql, ci sono molte cose che riguardano la complessità, se si dispone di indice di chiave primaria sul campo, verrà utilizzato indice B-tree. Se il suo sarà utilizzato un normale indice di non clustered, indice di hash. Ci sono costi differenti per ognuna di queste strutture di dati.

Dalla tua altra domanda, vedo questo è le vostre esigenze 1. Calcolare il percorso da UserX a Usery 2. Per UserX, calcolare tutti gli utenti che non è più di 3 passi.

Per il primo, cosa migliore è quello di applicare djikstra algoritmo e costruire una tabella in Java e quindi aggiornare nella tabella. Si noti che, l'aggiunta di ogni nuovo nodo, ha bisogno di lavorazione completa.

Altro soluzione a questo sarà usare SQL ricorsiva introdotto in SQL 1999 standard per creare una vista contenente il percorso da UserX a Usery. Fatemi sapere se avete bisogno di alcuni riferimenti per le query ricorsive.

Per la seconda, la query che hai scritto funziona perfettamente.