Хитрый, медленный l oop in Python

Question

У меня есть следующий Python код:

import json
import numpy as np

def generate(n, file, emax):
    data = {'n': n}
    adj = np.empty(n, dtype='object')

    for v in np.arange(n):
        erand = np.random.randint(1, emax + 1)
        adj[v] = {'v': int(v), 'e': np.random.choice(n, erand, replace=False).tolist()}

    # ndarrays are not JSON serializable
    data['adj'] = adj.tolist()

    with open(file, 'w') as graph:
        json.dump(data, graph, indent=2)

, который НЕВЕРОЯТНО медленный для n больше 10 ^ 4. Я пробовал много вещей, чтобы сделать это быстрее, включая np.apply_over_axis и что нет, но я не смог получить рабочую версию. Вовлеченные структуры также затрудняют работу с кодом.

Мне кажется, что это одна из тех проблем, где решение будет мгновенным, но мне не хватает опыта Python, чтобы туда добраться.

Если это что-то поможет, я по сути хочу создать случайные графы и предпочел бы не использовать ничего, кроме чистого Python и NumPy.

Пример вывода:

{
  "n": 10,
  "adj": [
    {
      "v": 0,
      "e": [
        0,
        7,
        5,
        6
      ]
    },
    {
      "v": 1,
      "e": [
        5,
        4,
        6,
        2
      ]
    },
    {
      "v": 2,
      "e": [
        8,
        5,
        4,
        2,
        3
      ]
    },
    {
      "v": 3,
      "e": [
        4,
        8
      ]
    },
    {
      "v": 4,
      "e": [
        8,
        4
      ]
    },
    {
      "v": 5,
      "e": [
        3
      ]
    },
    {
      "v": 6,
      "e": [
        9,
        2
      ]
    },
    {
      "v": 7,
      "e": [
        9
      ]
    },
    {
      "v": 8,
      "e": [
        7
      ]
    },
    {
      "v": 9,
      "e": [
        4,
        2,
        9,
        6,
        3
      ]
    }
  ]
}

Редактировать: в исходном посте я сказал, что мне нужны связанные графики. Это было ошибкой с моей стороны - я просто хотел гарантировать, что каждая вершина связана хотя бы с одной другой.

Answer 1

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

from json import dump
from random import randint, sample


def generate(n, path, density):
    '''Generates JSON files representing random directed graphs, where all vertices are connected to at least one other.

    Keyword arguments:
    n: number of vertices.
    path: path to JSON file.
    density: maximum number of edges of any vertex.'''
    data = {'n': n, 'm': 0}
    adj = [{'v': v} for v in range(n)]

    for v in range(n):
        adj[v]['e'] = sample(range(n), randint(1, density))
        while v in adj[v]['e']:
            adj[v]['e'] = sample(range(n), randint(1, density))
        data['m'] += len(adj[v]['e'])

    data['adj'] = adj

    with open(path, 'w') as graph:
        dump(data, graph, indent=2)

Я хочу написать while l oop по-другому, но это кажется работать хорошо.

(редактирование: исправлено для ребер типа (x, x))

Answer 2

Я полагаю, что использованная мной логика c создаст рандомизированные графики, которые вы ищете, если я не включил все требования, пожалуйста, дайте мне знать, и я удалю этот пост. Обратите внимание, что я не включил код для создания файла, так как проблема производительности, я думаю, связана со стоимостью использования функций np.random.

Исходная функция:

def generate(n=100, file='', emax=10):
data = {'n': n}
adj = np.empty(n, dtype='object')

for v in np.arange(n):
    erand = np.random.randint(1, emax + 1)
    adj[v] = {'v': int(v), 'e': np.random.choice(n, erand, replace=False).tolist()}

# ndarrays are not JSON serializable
data['adj'] = adj.tolist()
return data

Быстрее Функция :

def randGraph(n=100, file='', emax=10):
    data = {'n': n}
    nd = np.arange(n)
    masks = np.array(np.hstack((np.random.randint(0, 2, (n,emax)), np.zeros((n, n-emax)))), dtype=np.bool)
    for i in np.arange(n):
        np.random.shuffle(masks[i])
    data['adj'] = [{'v':i, 'e': nd[masks[i]].tolist()} for i in np.arange(n)] 
    return data

Более быстрые функции с джитом Нумбы:

from numba import jit
@jit   
def randGraphJIT(n=100, file='', emax=10):
    data = {'n': n}
    nd = np.arange(n)
    masks = np.array(np.hstack((np.random.randint(0, 2, (n,emax)), np.zeros((n, n-emax)))), dtype=np.bool)
    for i in np.arange(n):
        np.random.shuffle(masks[i])
    data['adj'] = [{'v':i, 'e': nd[masks[i]].tolist()} for i in np.arange(n)] 
    return data

Результаты:

%timeit generate()
2.17 ms ± 76.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit randGraph()
663 µs ± 777 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit randGraphJIT()
284 µs ± 46.5 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

Для непоследовательных графиков:

def randGraphNonSeqential(n=100, file='', emax=10):
    data = {'n': n}
    nd = np.arange(n)
    nds = np.tile(nd, (n,1))
    masks = np.array(np.hstack((np.random.randint(0, 2, (n,emax)), np.zeros((n, n-emax)))), dtype=np.bool)
    for i in np.arange(n):
        np.random.shuffle(nds[i])        
        np.random.shuffle(masks[i])

    data['adj'] = [{'v':i, 'e': nds[i][masks[i]].tolist()} for i in np.arange(n)] 
    return data

@jit
def randGraphNonSeqentialJIT(n=100, file='', emax=10):
    data = {'n': n}
    nd = np.arange(n)
    nds = np.tile(nd, (n,1))
    masks = np.array(np.hstack((np.random.randint(0, 2, (n,emax)), np.zeros((n, n-emax)))), dtype=np.bool)
    for i in np.arange(n):
        np.random.shuffle(nds[i])        
        np.random.shuffle(masks[i])

    data['adj'] = [{'v':i, 'e': nds[i][masks[i]].tolist()} for i in np.arange(n)] 
    return data

Только незначительное улучшение без JIT:

%timeit randGraphNonSeqential()
1.18 ms ± 6.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

все еще довольно хорошее улучшение с JIT:

%timeit randGraphNonSeqentialJIT()
380 µs ± 363 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)