我正在尝试在Python中调整Bellman-Ford图算法以满足我的需求。
我已经从json文件中解决了解析部分。
这是我在github上找到的Bellman Ford代码： 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的新手，所以我不知道发生了什么。 我编辑了这篇文章，因为答案帮我推进了:)
I'm trying to adapt a Bellman-Ford graph algorithm in Python to my needs.
I've worked out the parsing part from a json file.
Here is the Bellman Ford code I found on github: https://github.com/rosshochwert/arbitrage/blob/master/arbitrage.py
And here is my code I adapted from it:
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"Error:
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'When I print the graph I got everything needed. It is 'LTC' because it is the first one the list. I tried executing and filtering LTC, it gives me the same error with the first name coming on the graph:
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'I don't see how could I fix this.
Thanks everyone.
PS: It appears that an answer was deleted, I'm new to SO, so I don't know what happened. I edited the post, because the answer helped me to advance :)
最满意答案
免责声明 ：请注意，虽然您可以通过这种方式找到“效率低下”，但实际使用它们赚钱的可能性非常低。 很可能你实际上会放松一些钱。 根据我在测试过程中看到的数据，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那么（或者不是很久以前）买家愿意以1 ETH汇率0.04986673 BTC购买你的BTC 。 同样， Bid价值意味着如果您想卖出BTC ETH ，那么买家愿意以1 ETH汇率0.04978511 BTC买入您的1 ETH 。 请注意，此结构意味着您将没有"MarketName": "ETH-BTC"记录"MarketName": "ETH-BTC"因为它不提供其他数据。
因此，知道您可以使用适当的距离填充graph ，这些距离是相应费率的对数。 另外我相信你的代码中还有另一个错误：因为retrace_negative_loop的参数p实际上是前任节点的字典， 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 ，但我也没有费心去修复它。
Disclaimer: Note that although you can find "inefficiencies" in this way, the chances you could actually use them to earn money are quite low. Most probably you would actually loose some money. AFAICS from the data I've seen during testing, those "inefficiencies" come from the fact that exchange rates are more volatile over course of minutes than the Bid-Ask spread. So what you see as an inefficiency is probably just a stale data and you can't actually execute all the required orders fast enough for the exchange rate to be stable enough to earn money. So be advised that you might loose your money if you try to use this application for anything more than your curiosity.
So now to the business: Your data is in a different format than the one that the original code was designed for. Typical piece of data looks like this:
{ "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" }What you are interested in is MarketName, Bid and Ask. And you need to understand what those Bid and Ask mean. Roughly speaking the Ask value means that if you want to sell BTC for ETH there is (or rather was not too long ago) a buyer who is willing to buy your BTC using exchange rate 0.04986673 BTC for 1 ETH. Similarly the Bid value means that if you want to sell ETH for BTC there is (was) a buyer who is willing to buy your ETH using exchange rate 0.04978511 BTC for 1 ETH. Note that this structure means that you will not have a record with "MarketName": "ETH-BTC" because it provides no additional data.
So knowing that you can fill your graph with proper distances, which are logarithms of the corresponding rates. Also I believe that there is another bug in your code: since the argument p of the retrace_negative_loop is actually dictionary of predecessor nodes, retrace_negative_loop returns the negative loop in the reverse order. And since your graph is directed the same loop might be positive in one direction and negative in the other one.
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"Also the check if path not in paths and not None: is potentially not enough because it doesn't filter our paths that are just rotations of one another but I didn't bother with fixing that as well.
更多推荐
发布评论