0votos

Calculo de distancia a partir de 2 numeros ingresados (en Python) en Haskell

por josejuan hace 4 años

Parece que el profesor tomó el enunciado de wikipedia :D No obstante, hay varias formas de obtener eficientemente esa distancia mínima. Por ejemplo usando un k-d tree, se pueden ir insertando los N puntos (coste medio de O(log n) total O(n log n)) a la vez que se considera sus distancia mínima. Otra forma muy cómoda es triangular por delaunay y buscar la arista más corta. Lógicamente el algoritmo indicado en el enunciado tendrá la constante multiplicativa más pequeña, pero éstos otros son inmedi

Hay que a partir de un archivo de muchos numeros que vayan juntos de a par,obtener el par de puntos diferentes cuya distancia euclidea sea minima. La distancia euclidea entre los pares de puntos (x0, y0) y (x1, y1) se define de la siguiente manera: distancia ((x0, y0),(x1, y1)) ≡ raizcuad((x1-x0)^2 +(y1-y0)^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import System.Environment 
import Data.List 
import Data.Vector.Class 
import Data.Vector.V2 
import Graphics.Triangulation.Delaunay 
 
a % b = (vmag (a - b), (a, b)) 
 
-- Algoritmo trivial con coste O(n^2) 
closestPair :: [Vector2] -> (Double, (Vector2, Vector2)) 
closestPair = head . sortBy ((.fst).compare.fst) . allPairs 
              where allPairs [] = [] 
                    allPairs (p:ps) = [p % q | q <- ps] ++ allPairs ps 
 
-- Usando delaunay con coste O(n log n) 
closestPair' :: [Vector2] -> (Double, (Vector2, Vector2)) 
closestPair' = head . sortBy ((.fst).compare.fst) . allEdges . triangulate 
               where allEdges [] = [] 
                     allEdges ((a,b,c):ps) = [a % b, a % c, b % c] ++ allEdges ps 
 
 
 
 
 
-- Por ejemplo, para comparar las implementaciones: 
main = do 
  funcType <- head `fmap` getArgs 
  let func = case funcType of 
               "cuadratic"  -> closestPair 
               "logaritmic" -> closestPair' 
  (map ((\[x,y] -> Vector2 (read x) (read y)).words) . lines) `fmap` getContents >>= print . func 
 
{- 
 
# compilando... 
 
 
closestpoints$ ghc -O3 -fllvm closestPoints.hs 
[1 of 1] Compiling Main             ( closestPoints.hs, closestPoints.o ) 
You are using a new version of LLVM that hasn't been tested yet! 
We will try though... 
Linking closestPoints ... 
 
 
 
# comparando implementaciones para 1000..4000 puntos aleatorios 
 
closestpoints$ for i in 1 2 3 4 5; do time -f "%E, %M" ./closestPoints logaritmic < ${i}000.points; time -f "%E, %M" ./closestPoints cuadratic < ${i}000.points; done 
(5.552511480548015e-4,(Vector2 {v2x = 0.738264329903107, v2y = 0.855223896579275},Vector2 {v2x = 0.737721486390985, v2y = 0.855107171437325})) 
0:01.81, 6224 
(5.552511480548015e-4,(Vector2 {v2x = 0.737721486390985, v2y = 0.855107171437325},Vector2 {v2x = 0.738264329903107, v2y = 0.855223896579275})) 
0:01.69, 102024 
(1.5333655932024164e-4,(Vector2 {v2x = 0.595287481872109, v2y = 0.398113400039477},Vector2 {v2x = 0.59541029760879, v2y = 0.398021593747494})) 
0:05.07, 9088 
(1.5333655932024164e-4,(Vector2 {v2x = 0.59541029760879, v2y = 0.398021593747494},Vector2 {v2x = 0.595287481872109, v2y = 0.398113400039477})) 
0:06.77, 429652 
(2.540249469749139e-4,(Vector2 {v2x = 0.277886287311635, v2y = 0.414721694162196},Vector2 {v2x = 0.277981724716756, v2y = 0.414957109487503})) 
0:09.98, 16744 
(2.540249469749139e-4,(Vector2 {v2x = 0.277886287311635, v2y = 0.414721694162196},Vector2 {v2x = 0.277981724716756, v2y = 0.414957109487503})) 
0:15.19, 962140 
(1.6558279250144736e-4,(Vector2 {v2x = 0.545319354675438, v2y = 0.221625521514859},Vector2 {v2x = 0.545482399675077, v2y = 0.221654400387159})) 
0:16.45, 21496 
(1.6558279250144736e-4,(Vector2 {v2x = 0.545319354675438, v2y = 0.221625521514859},Vector2 {v2x = 0.545482399675077, v2y = 0.221654400387159})) 
0:42.52, 1829116 
(1.398912529509957e-4,(Vector2 {v2x = 0.355762406402359, v2y = 0.716193690000374},Vector2 {v2x = 0.355656911493124, v2y = 0.716101818422736})) 
0:25.30, 25684 
(1.398912529509957e-4,(Vector2 {v2x = 0.355762406402359, v2y = 0.716193690000374},Vector2 {v2x = 0.355656911493124, v2y = 0.716101818422736})) 
2:17.59, 1855108 
 
 
# tabulado tenemos 
 
Delaunay  Cuadrático 
0:01.81   0:01.69 
0:05.07   0:06.77 
0:09.98   0:15.19 
0:16.45   0:42.52 
0:25.30   2:17.59 
 
 
-} 
6 comentarios
0votos

Escrito por Felipe hace 4 años

MUCHAS GRACIAS! LA VERDAD YO NO ESTUDIO UNA CARRERA DE COMPUTACION, en este caso debo hacer este programa y es mas bien inroductorio a la computacion, y espero que se entienda lo que pongo a continuacion, porque masomenos por esa linea es como necesito ir. Luego me faltaria la parte de este ejercicio 1, parte 3 y 4. En la que tengo que generar un grafico. Y bueno, si bien de la forma en la que lo implementaste puede ser util, yo no me puedo relacionar con haskell y tampoco puedo importar funciones desde otro lado.
Espero que se entiendan mis dudas y si estas con ganas me respondas, porque la verdad es que esto me esta costando muchisimo y serias de una enorme de ayuda.
Gracias!
0votos

Escrito por Felipe hace 4 años

Ejercicio 1

1. Algoritmo de fuerza bruta
  1. Genera una lista de números float ingresados por el usuario. Crea una lista de pequeñas lista de a pares.
def crearlista():
g=open("listanum.py")
a=[]
p=[]
for x in g.readlines():
x=x[0:len(x)-1]
p=x.split()
for i in range(0,len(p)):
p[i]=float(p[i])
a=a+[p]
g.close()
return a
0votos

Escrito por Felipe hace 4 años

Calcula distancia euclidea entre dos puntos ingresados que van a ser tomados de la lista de numeros cargada.
def distancia(a,b):
return ((a[0]-b[0])2 + (a[1]-b[1])2)(1/2)
0votos

Escrito por Felipe hace 4 años

Calcula la distancia minima de una lista de numerous agrupados en pares, tomando como comparacion inicial que la distancia minima va a ser eventualemente menor a 100 unidades.
0votos

Escrito por Felipe hace 4 años

def distmin(L):
minimo=1000
for i in range(0,len(L)-1):
for j in range (i+1, len(L)):
0votos

Escrito por Felipe hace 4 años

print(distancia(L[i], L[j]))
if (distancia(L[i], L[j])< minimo):
minimo=distancia(L[i], L[j])
return minimo

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.