我正在尝试使用python中的bellman-ford图算法来满足我的需要。
我已经从json文件中找到了解析部分。
这是我在Github上找到的贝尔曼福特代码：
https://github.com/rosshochwert/arbitrage/blob/master/arbitrage.py
下面是我的代码，我从中改编：
import math, urllib2, json, re
def download():
graph = {}
page = urllib2.urlopen("https://bittrex.com/api/v1.1/public/getmarketsummaries")
jsrates = json.loads(page.read())
result_list = jsrates["result"]
for result_index, result in enumerate(result_list):
ask = result["Ask"]
market = result["MarketName"]
pattern = re.compile("([A-Z0-9]*)-([A-Z0-9]*)")
matches = pattern.match(market)
if (float(ask != 0)):
conversion_rate = -math.log(float(ask))
if matches:
from_rate = matches.group(1).encode('ascii','ignore')
to_rate = matches.group(2).encode('ascii','ignore')
if from_rate != to_rate:
if from_rate not in graph:
graph[from_rate] = {}
graph[from_rate][to_rate] = float(conversion_rate)
return graph
# Step 1: For each node prepare the destination and predecessor
def initialize(graph, source):
d = {} # Stands for destination
p = {} # Stands for predecessor
for node in graph:
d[node] = float('Inf') # We start admiting that the rest of nodes are very very far
p[node] = None
d[source] = 0 # For the source we know how to reach
return d, p
def relax(node, neighbour, graph, d, p):
# If the distance between the node and the neighbour is lower than the one I have now
if d[neighbour] > d[node] + graph[node][neighbour]:
# Record this lower distance
d[neighbour] = d[node] + graph[node][neighbour]
p[neighbour] = node
def retrace_negative_loop(p, start):
arbitrageLoop = [start]
next_node = start
while True:
next_node = p[next_node]
if next_node not in arbitrageLoop:
arbitrageLoop.append(next_node)
else:
arbitrageLoop.append(next_node)
arbitrageLoop = arbitrageLoop[arbitrageLoop.index(next_node):]
return arbitrageLoop
def bellman_ford(graph, source):
d, p = initialize(graph, source)
for i in range(len(graph)-1): #Run this until is converges
for u in graph:
for v in graph[u]: #For each neighbour of u
relax(u, v, graph, d, p) #Lets relax it
# Step 3: check for negative-weight cycles
for u in graph:
for v in graph[u]:
if d[v] < d[u] + graph[u][v]:
return(retrace_negative_loop(p, source))
return None
paths = []
graph = download()
print graph
for ask in graph:
path = bellman_ford(graph, ask)
if path not in paths and not None:
paths.append(path)
for path in paths:
if path == None:
print("No opportunity here :(")
else:
money = 100
print "Starting with %(money)i in %(currency)s" % {"money":money,"currency":path[0]}
for i,value in enumerate(path):
if i+1 < len(path):
start = path[i]
end = path[i+1]
rate = math.exp(-graph[start][end])
money *= rate
print "%(start)s to %(end)s at %(rate)f = %(money)f" % {"start":start,"end":end,"rate":rate,"money":money}
print "\n"
错误：
Traceback (most recent call last):
File "belltestbit.py", line 78, in <module>
path = bellman_ford(graph, ask)
File "belltestbit.py", line 61, in bellman_ford
relax(u, v, graph, d, p) #Lets relax it
File "belltestbit.py", line 38, in relax
if d[neighbour] > d[node] + graph[node][neighbour]:
KeyError: 'LTC'
当我打印图表时，我得到了所需的一切。它是“ltc”，因为它是列表中的第一个。我试过执行和过滤ltc，它给出了与图表上的名字相同的错误：
Traceback (most recent call last):
File "belltestbit.py", line 78, in <module>
path = bellman_ford(graph, ask)
File "belltestbit.py", line 61, in bellman_ford
relax(u, v, graph, d, p) #Lets relax it
File "belltestbit.py", line 38, in relax
if d[neighbour] > d[node] + graph[node][neighbour]:
KeyError: 'NEO'
我不知道该怎么解决。
谢谢大家。
附言：似乎有一个答案被删除了，我是新来的，所以我不知道发生了什么。我编辑了这篇文章，因为答案帮助我前进了：）
最佳答案
免责声明：请注意，虽然你可以通过这种方式找到“低效率”，但你真正利用它们赚钱的机会是相当低的。很可能你真的会放一些钱。从我在测试中看到的数据来看，这些“低效率”来自于这样一个事实，即汇率在几分钟内的波动比买卖价差更大。因此，你所看到的低效率可能只是一个陈旧的数据，你实际上无法快速执行所有要求的订单，使汇率稳定到足以赚钱。因此，请注意，如果您尝试使用此应用程序的目的不仅仅是为了满足您的好奇心，那么您可能会失去资金。
现在谈生意：
您的数据的格式与原始代码的设计格式不同。典型的数据如下：
{
"MarketName": "BTC-ETH",
"High": 0.05076884,
"Low": 0.04818392,
"Volume": 77969.61816991,
"Last": 0.04978511,
"BaseVolume": 3875.47491925,
"TimeStamp": "2017-12-29T05:45:10.18",
"Bid": 0.04978511,
"Ask": 0.04986673,
"OpenBuyOrders": 4805,
"OpenSellOrders": 8184,
"PrevDay": 0.04955001,
"Created": "2015-08-14T09:02:24.817"
}
你感兴趣的是
MarketName，Bid和Ask。你需要明白那些Bid and Ask意味着什么。粗略地说，Ask的价值意味着如果你想以BTC的价格卖出ETH的话，有一个买家（或者说不久前）愿意用BTC的汇率买入你的0.04986673 BTC。同样地，如果你想以低于cc>的价格出售，那么有一个买家愿意以低于cc>的汇率购买你的产品。注意，这个结构意味着您将没有一个1 ETH的记录，因为它没有提供额外的数据。所以知道你可以用适当的距离来填充你的
Bid，这是相应速率的对数。另外，我认为代码中还有一个bug：ETH的参数BTC实际上是前置节点的字典，ETH以相反的顺序返回负循环。因为你的图是有方向的，所以同一个循环在一个方向上可能是正的，在另一个方向上可能是负的。import math, urllib2, json, re
def download():
graph = {}
page = urllib2.urlopen("https://bittrex.com/api/v1.1/public/getmarketsummaries")
data = page.read()
jsrates = json.loads(data)
result_list = jsrates["result"]
for result_index, result in enumerate(result_list):
ask = result["Ask"]
bid = result["Bid"]
market = result["MarketName"]
pattern = re.compile("([A-Z0-9]*)-([A-Z0-9]*)")
matches = pattern.match(market)
if matches:
from_rate = matches.group(1).encode('ascii', 'ignore')
to_rate = matches.group(2).encode('ascii', 'ignore')
# different sign of log is effectively 1/x
if ask != 0:
if from_rate not in graph:
graph[from_rate] = {}
graph[from_rate][to_rate] = math.log(float(ask))
if bid != 0:
if to_rate not in graph:
graph[to_rate] = {}
graph[to_rate][from_rate] = -math.log(float(bid))
return graph # Step 1: For each node prepare the destination and predecessor
def initialize(graph, source):
d = {} # Stands for destination
p = {} # Stands for predecessor
for node in graph:
d[node] = float('Inf') # We start admiting that the rest of nodes are very very far
p[node] = None
d[source] = 0 # For the source we know how to reach
return d, p
def relax(node, neighbour, graph, d, p):
# If the distance between the node and the neighbour is lower than the one I have now
dist = graph[node][neighbour]
if d[neighbour] > d[node] + dist:
# Record this lower distance
d[neighbour] = d[node] + dist
p[neighbour] = node
def retrace_negative_loop(p, start):
arbitrageLoop = [start]
prev_node = start
while True:
prev_node = p[prev_node]
if prev_node not in arbitrageLoop:
arbitrageLoop.append(prev_node)
else:
arbitrageLoop.append(prev_node)
arbitrageLoop = arbitrageLoop[arbitrageLoop.index(prev_node):]
# return arbitrageLoop
return list(reversed(arbitrageLoop))
def bellman_ford(graph, source):
d, p = initialize(graph, source)
for i in range(len(graph) - 1): # Run this until is converges
for u in graph:
for v in graph[u]: # For each neighbour of u
relax(u, v, graph, d, p) # Lets relax it
# Step 3: check for negative-weight cycles
for u in graph:
for v in graph[u]:
if d[v] < d[u] + graph[u][v]:
return retrace_negative_loop(p, v)
return None
graph = download()
# print graph
for k, v in graph.iteritems():
print "{0} => {1}".format(k, v)
print "-------------------------------"
paths = []
for currency in graph:
path = bellman_ford(graph, currency)
if path not in paths and not None:
paths.append(path)
for path in paths:
if path == None:
print("No opportunity here :(")
else:
money = 100
print "Starting with %(money)i in %(currency)s" % {"money": money, "currency": path[0]}
for i, value in enumerate(path):
if i + 1 < len(path):
start = path[i]
end = path[i + 1]
rate = math.exp(-graph[start][end])
money *= rate
print "%(start)s to %(end)s at %(rate)f = %(money)f" % {"start": start, "end": end, "rate": rate,
"money": money}
print "\n"
此外，检查
0.04978511 BTC可能是不够的，因为它不过滤我们的1 ETH s，这只是彼此的旋转，但我也不费心去修复它。关于python - 在python中实现Bellman-Ford，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47995901/