python-O(n)列表减法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python-O(n)列表减法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1191字，纯文字阅读大概需要2分钟。

内容图文

working on an AoC puzzle时,我发现我想减去列表(保留顺序)：

def bag_sub(list_big, sublist):
    result = list_big[:]
    for n in sublist:
        result.remove(n)
    return result

我不喜欢list.remove调用(本身就是O(n))包含在循环中的方式,这似乎效率很低.所以我尝试重写它以避免这种情况：

def bag_sub(list_big, sublist):
    c = Counter(sublist)
    result = []
    for k in list_big:
        if k in c:
            c -= Counter({k: 1})
        else:
            result.append(k)
    return result

>现在是O(n),还是Counter .__ isub__用法仍然搞砸了？
>这种方法要求元素必须是可散列的,这是原始元素没有的限制.是否有O(n)解决方案可避免产生此额外限制？ Python是否有比collections.Counter更好的“袋”数据类型？

您可以假设子列表的长度是list_big的一半.

解决方法:

Is this now O(n), or does the Counter.__isub__ usage still screw things up?

这是预期的情况O(n),除了Counter .__ isub__丢弃非正值时,它会遍历每个键.您最好还是以“通常”的方式从键值中减去1并检查c [k]而不是c中的k. (对于不在c中的k,c [k]为0,因此您不需要进行检查.)

if c[k]:
    c[k] -= 1
else:
    result.append(k)

Is there an O(n) solution which avoids creating this additional restriction?

仅当输入已排序时,在这种情况下,mergesort合并的标准变体才能执行此操作.

Does Python have any better “bag” datatype than collections.Counter?

collections.Counter是Python的包.

内容总结

以上是互联网集市为您收集整理的python-O(n)列表减法全部内容，希望文章能够帮你解决python-O(n)列表减法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端