Количество элементов в наборе Python

Question

У меня есть список набранных телефонных номеров (nums_dialed). У меня также есть набор телефонных номеров, которые являются номером в офисе клиента (client_nums) Как мне эффективно выяснить, сколько раз я звонил конкретному клиенту (всего)

Например:

>>>nums_dialed=[1,2,2,3,3]
>>>client_nums=set([2,3])
>>>???
total=4

Проблема в том, что у меня большой набор данных: len (client_nums) ~ 10 ^ 5; и len (nums_dialed) ~ 10 ^ 3.

Answer 1

у какого клиента есть 10^5 номера в его офисе? Вы работаете на всю телефонную компанию?

В любом случае:

print sum(1 for num in nums_dialed if num in client_nums)

Это даст вам как можно быстрее номер.

---

Если вы хотите сделать это для нескольких клиентов, используя один и тот же список nums_dialed, вы можете сначала кэшировать данные по каждому номеру:

nums_dialed_dict = collections.defaultdict(int)
for num in nums_dialed:
    nums_dialed_dict[num] += 1

Затем просто суммируйте единицы для каждого клиента:

sum(nums_dialed_dict[num] for num in this_client_nums)

Это было бы намного быстрее, чем повторять весь список чисел снова для каждого клиента.

Answer 2

Использование коллекций. Счетчик из Python 2.7:

dialed_count = collections.Counter(nums_dialed)
count = sum(dialed_count[t] for t in client_nums)

Answer 3

>>> client_nums = set([2, 3])
>>> nums_dialed = [1, 2, 2, 3, 3]
>>> count = 0
>>> for num in nums_dialed:
...   if num in client_nums:
...     count += 1
... 
>>> count
4
>>> 

Должно быть достаточно эффективным даже для больших чисел, которые вы цитируете.

Answer 4

Это очень популярный способ сделать несколько комбинаций отсортированных списков за один проход:

nums_dialed = [1, 2, 2, 3, 3]
client_nums = [2,3]

nums_dialed.sort()
client_nums.sort()

c = 0
i = iter(nums_dialed)
j = iter(client_nums)
try:
    a = i.next()
    b = j.next()
    while True:
        if a < b:
            a = i.next()
            continue
        if a > b:
            b = j.next()
            continue
        # a == b
        c += 1
        a = i.next() # next dialed
except StopIteration:
    pass

print c

Поскольку "set" - неупорядоченная коллекция (не знаю, почему она использует хэши, а не двоичное дерево или отсортированный список), и использовать ее там будет нечестно. Вы можете реализовать собственный «set» через «bisect», если вам нравятся списки или что-то более сложное, что создаст упорядоченный итератор.