| 2504 | } |
| 2505 | |
| 2506 | static int zsetChooseDiffAlgorithm(zsetopsrc *src, long setnum) { |
| 2507 | int j; |
| 2508 | |
| 2509 | /* Select what DIFF algorithm to use. |
| 2510 | * |
| 2511 | * Algorithm 1 is O(N*M + K*log(K)) where N is the size of the |
| 2512 | * first set, M the total number of sets, and K is the size of the |
| 2513 | * result set. |
| 2514 | * |
| 2515 | * Algorithm 2 is O(L + (N-K)log(N)) where L is the total number of elements |
| 2516 | * in all the sets, N is the size of the first set, and K is the size of the |
| 2517 | * result set. |
| 2518 | * |
| 2519 | * We compute what is the best bet with the current input here. */ |
| 2520 | long long algo_one_work = 0; |
| 2521 | long long algo_two_work = 0; |
| 2522 | |
| 2523 | for (j = 0; j < setnum; j++) { |
| 2524 | /* If any other set is equal to the first set, there is nothing to be |
| 2525 | * done, since we would remove all elements anyway. */ |
| 2526 | if (j > 0 && src[0].subject == src[j].subject) { |
| 2527 | return 0; |
| 2528 | } |
| 2529 | |
| 2530 | algo_one_work += zuiLength(&src[0]); |
| 2531 | algo_two_work += zuiLength(&src[j]); |
| 2532 | } |
| 2533 | |
| 2534 | /* Algorithm 1 has better constant times and performs less operations |
| 2535 | * if there are elements in common. Give it some advantage. */ |
| 2536 | algo_one_work /= 2; |
| 2537 | return (algo_one_work <= algo_two_work) ? 1 : 2; |
| 2538 | } |
| 2539 | |
| 2540 | static void zdiff(zsetopsrc *src, long setnum, zset *dstzset, size_t *maxelelen, size_t *totelelen) { |
| 2541 | /* Skip everything if the smallest input is empty. */ |