Todos los Pares - Familia de Funciones

Las siguientes funciones funcionan en todas las combinaciones de pares de vértices

Versiones anteriores de esta página

Rendimiento

Las siguientes pruebas:
  • computadora que no sea servidor
  • con unidad de procesamiento central AMD 64
  • memoria 4G
  • trusty
  • postgreSQL versión 9.3

Datos

Se usaron los siguientes datos

BBOX="-122.8,45.4,-122.5,45.6"
wget --progress=dot:mega -O "sampledata.osm" "https://www.overpass-api.de/api/xapi?*[bbox=][@meta]"

El procesamiento de datos se llevó a cabo con osm2pgrouting-alpha

createdb portland
psql -c "create extension postgis" portland
psql -c "create extension pgrouting" portland
osm2pgrouting -f sampledata.osm -d portland -s 0

Resultados

Prueba:Uno

Esta prueba no se hace con cuadro delimitador. La densidad del gráfico que se pasa es extremadamente baja. Para cada <SIZE> se ejecutaron 30 pruebas para obtener el medio. La consulta probada es:

SELECT count(*) FROM pgr_floydWarshall(
   'SELECT gid as id, source, target, cost, reverse_cost FROM ways where id <=  <SIZE>');

SELECT count(*) FROM pgr_johnson(
   'SELECT gid as id, source, target, cost, reverse_cost FROM ways where id <=  <SIZE>');

Los resultados de la prueba son:

TAMAÑO:es el número de aristas entradas
ARISTAS:es el numero de registros en la consulta
DENSIDAD:es la densidad de los datos \(\dfrac{E}{V \times (V-1)}\).
REGISTROS DEVUELTOS:
 es el número de registros devueltos por las consultas.
Floyd-Warshall:es el tiempo promedio de ejecución en segundos de pgr_floydWarshall.
Johnson:es el tiempo promedio de ejecución en segundos de pgr_johnson.
TAMAÑO ARISTAS DENSIDAD REGISTROS DEVUELTOS Floyd-Warshall Johnson
500 500 0.18E-7 1346 0.14 0.13
1000 1000 0.36E-7 2655 0.23 0.18
1500 1500 0.55E-7 4110 0.37 0.34
2000 2000 0.73E-7 5676 0.56 0.37
2500 2500 0.89E-7 7177 0.84 0.51
3000 3000 1.07E-7 8778 1.28 0.68
3500 3500 1.24E-7 10526 2.08 0.95
4000 4000 1.41E-7 12484 3.16 1.24
4500 4500 1.58E-7 14354 4.49 1.47
5000 5000 1.76E-7 16503 6.05 1.78
5500 5500 1.93E-7 18623 7.53 2.03
6000 6000 2.11E-7 20710 8.47 2.37
6500 6500 2.28E-7 22752 9.99 2.68
7000 7000 2.46E-7 24687 11.82 3.12
7500 7500 2.64E-7 26861 13.94 3.60
8000 8000 2.83E-7 29050 15.61 4.09
8500 8500 3.01E-7 31693 17.43 4.63
9000 9000 3.17E-7 33879 19.19 5.34
9500 9500 3.35E-7 36287 20.77 6.24
10000 10000 3.52E-7 38491 23.26 6.51
Prueba:Dos

Esta prueba se hace con cuadro delimitador. La densidad del gráfico que se pasa es superior a la de la prueba 1. Para cada <SIZE> se ejecutaron 30 pruebas para obtener el medio. La consulta de arista que se prueba es:

WITH
    buffer AS (SELECT ST_Buffer(ST_Centroid(ST_Extent(the_geom)), SIZE) AS geom FROM ways),
    bbox AS (SELECT ST_Envelope(ST_Extent(geom)) as box from buffer)
SELECT gid as id, source, target, cost, reverse_cost FROM ways where the_geom && (SELECT box from bbox);

Las consultas probadas

SELECT count(*) FROM pgr_floydWarshall(<edge query>)
SELECT count(*) FROM pgr_johnson(<edge query>)

Los resultados de la prueba son:

TAMAÑO:es el tamaño del cuadro delimitador.
ARISTAS:es el numero de registros en la consulta
DENSIDAD:es la densidad de los datos \(\dfrac{E}{V \times (V-1)}\).
REGISTROS DEVUELTOS:
 es el número de registros devueltos por las consultas.
Floyd-Warshall:es el tiempo promedio de ejecución en segundos de pgr_floydWarshall.
Johnson:es el tiempo promedio de ejecución en segundos de pgr_johnson.
TAMAÑO ARISTAS DENSIDAD REGISTROS DEVUELTOS Floyd-Warshall Johnson
0.001 44 0.0608 1197 0.10 0.10
0.002 99 0.0251 4330 0.10 0.10
0.003 223 0.0122 18849 0.12 0.12
0.004 358 0.0085 71834 0.16 0.16
0.005 470 0.0070 116290 0.22 0.19
0.006 639 0.0055 207030 0.37 0.27
0.007 843 0.0043 346930 0.64 0.38
0.008 996 0.0037 469936 0.90 0.49
0.009 1146 0.0032 613135 1.26 0.62
0.010 1360 0.0027 849304 1.87 0.82
0.011 1573 0.0024 1147101 2.65 1.04
0.012 1789 0.0021 1483629 3.72 1.35
0.013 1975 0.0019 1846897 4.86 1.68
0.014 2281 0.0017 2438298 7.08 2.28
0.015 2588 0.0015 3156007 10.28 2.80
0.016 2958 0.0013 4090618 14.67 3.76
0.017 3247 0.0012 4868919 18.12 4.48