QuickRatio returns an upper bound on ratio() relatively quickly. This isn't defined beyond that it is an upper bound on .Ratio(), and is faster to compute.
()
| 541 | // This isn't defined beyond that it is an upper bound on .Ratio(), and |
| 542 | // is faster to compute. |
| 543 | func (m *SequenceMatcher) QuickRatio() float64 { |
| 544 | // viewing a and b as multisets, set matches to the cardinality |
| 545 | // of their intersection; this counts the number of matches |
| 546 | // without regard to order, so is clearly an upper bound. We do |
| 547 | // so on hashes of the lines themselves, so this might even be |
| 548 | // greater due hash collisions incurring false positives, but |
| 549 | // we don't care because we want an upper bound anyway. |
| 550 | if m.fullBCount == nil { |
| 551 | m.fullBCount = map[lineHash]int{} |
| 552 | for _, s := range m.b { |
| 553 | h := _hash(s) |
| 554 | m.fullBCount[h] = m.fullBCount[h] + 1 |
| 555 | } |
| 556 | } |
| 557 | |
| 558 | // avail[x] is the number of times x appears in 'b' less the |
| 559 | // number of times we've seen it in 'a' so far ... kinda |
| 560 | avail := map[lineHash]int{} |
| 561 | matches := 0 |
| 562 | for _, s := range m.a { |
| 563 | h := _hash(s) |
| 564 | n, ok := avail[h] |
| 565 | if !ok { |
| 566 | n = m.fullBCount[h] |
| 567 | } |
| 568 | avail[h] = n - 1 |
| 569 | if n > 0 { |
| 570 | matches += 1 |
| 571 | } |
| 572 | } |
| 573 | return calculateRatio(matches, len(m.a)+len(m.b)) |
| 574 | } |
| 575 | |
| 576 | // RealQuickRatio returns an upper bound on ratio() very quickly. |
| 577 | // |