Итеративно подсчитывать элементы в списке и хранить кол-во в словаре

Question

У меня есть часть кода, которая проходит через набор узлов и подсчитывает длину пути, соединяющую данный узел друг с другом в моей сети. Для каждого узла мой код возвращает мне список, b, содержащий целочисленные значения, дающие мне длину пути для каждого возможного соединения. Я хочу подсчитать количество вхождений заданных длин пути, чтобы создать гистограмму.

local_path_length_hist = {} 
for ver in vertices: 
    dist = gt.shortest_distance(g, source=g.vertex(ver)) 
    a = dist.a 
    #Delete some erroneous entries 
    b = a[a!=2147483647] 
    for dist in b: 
     if dist in local_path_length_hist: 
      local_path_length_hist[dist]+=1 
     else: 
      local_path_length_hist[dist]=1 

Это, по-видимому, очень грубое кодирование в отношении обновления словаря. Есть ли лучший способ сделать это? Каков наиболее эффективный способ создания этой гистограммы?

Answer 1

С gt.shortest_distance возвращает ndarray, numpy математика быстро:

max_dist = len(vertices) - 1 
hist_length = max_dist + 2 
no_path_dist = max_dist + 1 
hist = np.zeros(hist_length) 
for ver in vertices: 
    dist = gt.shortest_distance(g, source=g.vertex(ver)) 
    hist += np.bincount(dist.a.clip(max=no_path_dist)) 

Я использую метод ndarrayclip в бункер на 2147483647 значения, возвращаемые gt.shortest_distance на последней позиции hist. Без использования clip, hist'ssize должно быть 2147483647 + 1 на 64-битном Python, или bincount создаст ValueError на 32-битном Python. Таким образом, последняя позиция hist будет содержать количество всех непустых; вы можете игнорировать это значение в анализе гистограммы.

---

Как ниже тайминги указывают, используя numpy математику, чтобы получить гистограмму хорошо более чем на порядок величины быстрее, чем при использовании либо defaultdicts или counters (Python 3.4):

# vertices  numpy defaultdict counter 
    9000  0.83639 38.48990  33.56569 
    25000  8.57003 314.24265 262.76025 
    50000  26.46427 1303.50843 1111.93898 

Мой компьютер слишком медленный тест с 9 * (10**6) вершинами, но относительные тайминги кажутся довольно согласованными для различного количества вершин (как и следовало ожидать).

---

код синхронизации:

from collections import defaultdict, Counter 
import numpy as np 
from random import randint, choice 
from timeit import repeat 

# construct distance ndarray such that: 
# a) 1/3 of values represent no path 
# b) 2/3 of values are a random integer value [0, (num_vertices - 1)] 
num_vertices = 50000 
no_path_length = 2147483647 
distances = [] 
for _ in range(num_vertices): 
    rand_dist = randint(0,(num_vertices-1)) 
    distances.append(choice((no_path_length, rand_dist, rand_dist))) 
dist_a = np.array(distances) 

def use_numpy_math(): 
    max_dist = num_vertices - 1 
    hist_length = max_dist + 2 
    no_path_dist = max_dist + 1 
    hist = np.zeros(hist_length, dtype=np.int) 
    for _ in range(num_vertices): 
     hist += np.bincount(dist_a.clip(max=no_path_dist)) 

def use_default_dict(): 
    d = defaultdict(int) 
    for _ in range(num_vertices): 
     for dist in dist_a: 
      d[dist] += 1 

def use_counter(): 
    hist = Counter() 
    for _ in range(num_vertices): 
     hist.update(dist_a) 

t1 = min(repeat(stmt='use_numpy_math()', setup='from __main__ import use_numpy_math', 
       repeat=3, number=1)) 
t2 = min(repeat(stmt='use_default_dict()', setup='from __main__ import use_default_dict', 
       repeat= 3, number=1)) 
t3 = min(repeat(stmt='use_counter()', setup='from __main__ import use_counter', 
       repeat= 3, number=1)) 

print('%0.5f, %0.5f. %0.5f' % (t1, t2, t3)) 

Answer 2

Проверка того, что элемент существует в dict, в действительности не требуется. Вы можете использовать только collections.defaultdict. Его инициализация принимает вызываемый объект (например, функцию), который будет вызываться, если вы хотите получить доступ (или присвоить что-то) элементу, который не существует для генерации значения (т. Е. Функция, которая генерирует значение по умолчанию). Для вашего случая это может быть только int. То есть

import collections 
local_path_length_hist = collections.defaultdict(int) 
# you could say collections.defaultdict(lambda : 0) instead 
for ver in vertices: 
    dist = gt.shortest_distance(g, source=g.vertex(ver)) 
    a = dist.a 
    #Delete some erroneous entries 
    b = a[a!=2147483647] 
    for dist in b: 
     local_path_length_hist[dist] += 1 

Вы можете повернуть последние две строки в одном подобном, но на самом деле нет смысла.

Answer 3

Я думаю, вы можете обойти этот код полностью. Ваш вопрос помечен graph-tool. Взгляните на этот раздел своей документации: graph_tool.stats.vertex_hist.

Выдержка из документации, связанной:

graph_tool.stats.vertex_hist(g, deg, bins=[0, 1], float_count=True)
Return the vertex histogram of the given degree type or property.

Parameters:
g : Graph  Graph to be used.
deg : string or PropertyMap
 Degree or property to be used for the histogram. It can be either “in”, “out” or “total”, for in-,
 out-, or total degree of the vertices. It can also be a vertex property map.
bins : list of bins (optional, default: [0, 1])
 List of bins to be used for the histogram. The values given represent the edges of the bins
 (i.e. lower and upper bounds). If the list contains two values, this will be used to automatically
 create an appropriate bin range, with a constant width given by the second value, and starting
 from the first value.
float_count : bool (optional, default: True)
 If True, the counts in each histogram bin will be returned as floats. If False, they will be
 returned as integers.

Returns: counts : ndarray
 The bin counts.
bins : ndarray
 The bin edges.

Это будет возвращать края, сгруппированных как гистограммы в качестве ndarray. Затем вы можете просто получить длину столбцов ndarray, чтобы получить ваши счета для генерации гистограммы.

Answer 4

В модуле collections есть утилита, называемая Counter. Это даже чище, чем при использовании defaultdict(int)

from collections import Counter 
hist = Counter() 
for ver in vertices: 
    dist = gt.shortest_distance(g, source=g.vertex(ver)) 
    a = dist.a 
    #Delete some erroneous entries 
    b = a[a!=2147483647] 
    hist.update(b)