HackerRank: ACM团队

Question

我为这个来自黑客等级的问题做了一个解决方案：

您将获得参加ACM世界总决赛的N人名单.他们中的每一个人要么对某个话题很熟悉，要么就不熟悉。找出一个2人团队所能知道的最多的话题数。并找出有多少团队可以知道最大数量的主题。注:假设a、b和c是三个不同的人，则(a，b)和(b，c)被计算为两个不同的团队。输入格式第一行包含两个整数，N和M，用一个空格分隔，其中N表示人数，M表示主题数。N条线跟着。每一行包含一个长度为M的二进制字符串，如果ith行的jth字符为1，那么ith person就知道jth主题；否则，他就不知道这个主题。

我的代码被认为太慢了(我认为我有10秒的时间，当N和M都是500时，下面的代码需要超过20秒)：

import random
import itertools
import time

# n number of people
# m number of topics

n = 500
m = 500

"""
binary_string(n) and random_list(n_people, n_topic) just help
to generate test cases, irrelevant otherwise.
"""

def binary_string(n):
    my_string = "".join(str(random.randint(0, 1)) for _ in range(n))
    return my_string    

def random_list(n_people, n_topic):
    my_list = [binary_string(n_topic) for _ in range(n_people)]
    return my_list    

"""
the essential part is item_value(e1, e2)
and find_couples(comb_list)
"""


def item_value(e1, e2):
    c = bin(int(e1, 2) | int(e2, 2))
    return sum(int(i) for i in c[2:])


def find_couples(comb_list):
    max_value = 0
    counter = 0      

    for pair in itertools.combinations(comb_list, 2):
        value = item_value(pair[0], pair[1])
        if value == max_value:
            counter += 1
        elif value > max_value:
            max_value = value
            counter = 1

    print(max_value)
    print(counter)
    return    

topic = random_list(n, m)

print(topic)    

start = time.time()
find_couples(topic)
end = time.time()
print(end - start)

1. 在上述算法的上下文中，以何种方式可以使其更有效？
2. 有更好的算法吗？

Answer 1

您在item_value中花费了大量时间，将数字转换为二进制字符串，返回到int，以得到和。使用str.count来获取字符串中的1s数就更方便了。这为您节省了很多类型转换，以及对带有生成器的sum的调用。

def item_value(e1, e2):
    c = bin(int(e1, 2) | int(e2, 2))
    return c[2:].count('1')

我的结果导致从58.9秒减少到0.91秒。

Answer 2

如果您甚至需要添加评论：

# n number of people

只需将n重命名为NUMBER_OF_PEOPLE，更喜欢有意义的名称而不是注释，评论可能会过时，因为它们没有自动检查。