擅长:python、mysql、java
<p>这就是求一组集合的最小值的问题。这个问题的定义和算法看起来很幼稚:</p>
<pre><code>set(s for s in sets if not any(other < s for other in sets))
</code></pre>
<p>有一些次二次算法可以做到这一点(例如<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.4283" rel="nofollow noreferrer">this</a>),但是考虑到N是10000,实现的效率可能更重要。最佳方法在很大程度上取决于输入数据的分布。考虑到输入集是自然语言短语,它们大多不同,redtuna建议的方法应该可以很好地工作。下面是该算法的python实现。在</p>
^{pr2}$
<p>这仍然是二次方的,但是在我的机器上,对于一组包含50%最小值的10k短语,它的运行时间为350ms,单词来自指数分布。在</p>