Реализация Bellman-Ford в Python
Я пытаюсь адаптировать алгоритм графа Беллмана-Форда в Python к своим потребностям.
Я разработал часть анализа из файла JSON.
Вот код Bellman Ford, который я нашел на 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'
Я не вижу, как я мог это исправить.
Спасибо всем.
PS: Похоже, что ответ был удален, я новичок в SO, поэтому я не знаю, что случилось. Я отредактировал пост, потому что ответ помог мне продвинуться:)
1 ответ
Отказ от ответственности: обратите внимание, что, хотя вы можете найти "неэффективность" таким образом, шансы, что вы действительно можете использовать их, чтобы заработать деньги, довольно низки. Скорее всего, вы бы потеряли немного денег. AFAICS из данных, которые я видел во время тестирования, эти "неэффективности" происходят из-за того, что обменные курсы более изменчивы в течение минут, чем спред Bid-Ask. Таким образом, то, что вы видите как неэффективность, это, вероятно, просто устаревшие данные, и вы не можете фактически выполнить все необходимые заказы достаточно быстро, чтобы обменный курс был достаточно стабильным, чтобы зарабатывать деньги. Так что имейте в виду, что вы можете потерять свои деньги, если вы попытаетесь использовать это приложение для чего-то большего, чем ваше любопытство.
Так что теперь к делу: ваши данные в другом формате, чем тот, для которого был разработан оригинальный код. Типичный фрагмент данных выглядит так:
{
"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 а такжеAsk имею в виду. Грубо говоря Ask значение означает, что если вы хотите продать BTC за ETH есть (точнее, не так давно) покупатель, который готов купить BTC используя обменный курс 0.04986673 BTC за 1 ETH, Точно так же Bid значение означает, что если вы хотите продать ETH за BTC есть (был) покупатель, который готов купить ETH используя обменный курс 0.04978511 BTC за 1 ETH, Обратите внимание, что эта структура означает, что у вас не будет записи с "MarketName": "ETH-BTC" потому что он не предоставляет никаких дополнительных данных.
Так зная, что вы можете заполнить свой graph с надлежащими расстояниями, которые являются логарифмами соответствующих скоростей. Также я считаю, что в вашем коде есть еще одна ошибка: после аргумента p из retrace_negative_loop на самом деле словарь узлов-предшественников, retrace_negative_loop возвращает отрицательный цикл в обратном порядке. И поскольку ваш график направлен, тот же цикл может быть положительным в одном направлении и отрицательным в другом.
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"
Также проверка if path not in paths and not None: потенциально недостаточно, потому что он не фильтрует наши pathЭто просто повороты друг друга, но я не стал их исправлять.