#!/usr/bin/python # tz_chooser.py # --copyright-- Copyright 2010 (C) Tranzoa, Co. All rights reserved. Warranty: You're free and on your own here. This code is not necessarily up-to-date or of public quality. # --url-- http://www.tranzoa.net/tzpython/ # --email-- pycode is the name to send to. tranzoa.com is the place to send to. # --bodstamps-- # December 25, 2010 bar # December 26, 2010 bar # November 29, 2011 bar pyflake cleanup # May 27, 2012 bar doxygen namespace # November 7, 2017 bar maxint->maxsize # --eodstamps-- ## \file # \namespace tzpython.tz_chooser # # # This thing incrementally sorts an array of things, telling the owner which things don't have information for comparison. # The owner tells the array of things how to compare each pair of things given to the owner. # The end result is an array of things roughly in order. # As time goes on, and the owner has told the array pair-comparisons, the things will be better ordered. # # TODO: # pick pairs that will yield the biggest tree if they were decided - choices that when resolved will combine chains # find ends of chains and see about linking them - low end to high # pick pairs with far-apart names? # # import random import sys import tzlib CHUNK_SIZE = sys.maxsize # do the choices in groups of this many building up to when we can sort them all EXTEND_LEARNING = False # when we learn, we teach others that seem like they could know, too. Cuts down on the number of sorts needed to home in on a good distribution, but eats CPU. EXTEND_COMPARE = False # can we look around for choices to link, given they have unambiguous links between them through other choices? AGE = 0.5 # when aging, take out the older of this multiple of the memory class a_cmp(object) : def __init__(me, c, r) : me.c = c me.r = -1 if r < 0 else 1 if r > 0 else 0 # a_cmp class a_choice(object) : """ This a one of the things to be ordered. 'data' is anything you want it to be. The 'name' must be unique among all the choices known to the chooser. """ def __init__(me, name, data) : me.name = name me.data = data me.cmps = {} # indexed by other a_choices we've been compared to. value of the a_cmp comparison (!= None) me.zero_order_total() me.ci = 0 # for owner to track when we were last chosen me.si = 0 me.found_cnt = 0 def get_button_text(me) : return(me.name) def start_sort(me) : me.si = random.randint(0, sys.maxsize / 2) def knows(me, om) : return((om.name in me.cmps) or (me.name in om.cmps)) def cmp(me, om) : if om.name in me.cmps : ca = me.cmps[om.name] return(ca[me.si % len(ca)].r) return(None) # we've never compared ourself to this other a_choice def _find_cmp(me, om, r, cd) : for c in me.cmps.get(om.name, []) : if c.r == r : return(True) pass for ca in me.cmps.values() : c = ca[0] if c.c.name not in cd : for c in ca : if (c.r == r) : cd[c.c.name] = True if c.c._find_cmp(om, r, cd) : return(True) break # go on to the next link pass pass pass return(False) def find_cmp(me, om) : if not me.knows(om) : m = me._find_cmp(om, -1, { me.name : True, om.name : True, }) p = me._find_cmp(om, 1, { me.name : True, om.name : True, }) if not (m and p) : if me._find_cmp( om, 0, { me.name : True, om.name : True, }) : if not (m or p) : return(0) pass else : return(-1 if m else 1 if p else None) pass pass return(None) def _find_tweens(me, fnd, path, om, r, cd) : """ Fill 'fnd' with key:choice name value:choice The choices are on between me and om on paths only of acceptable type 'r'. """ longest = 0 if me.name == om.name : for c in path : fnd[c.name] = c pass else : path.append(me) for n, ca in me.cmps.items() : if n not in cd : if n != om.name : cd[n] = True for c in ca : if c.r * r > 0 if r else not c.r : longest = max(longest, c.c._find_tweens(fnd, path, om, r, cd)) break # go on to the next link pass pass pass path.pop() return(longest) def find_tweens(me, om, r) : fnd = {} cd = { me.name : True, } me._find_tweens(fnd, [], om, r, cd) if me.name in fnd : del(fnd[me.name]) return(fnd.values()) def _branch_out(me, fnd, r, cd) : """ Fill 'fnd' with key:choice name value:choice The choices are on the ends of paths only of acceptable type 'r'. """ for n, ca in me.cmps.items() : if n not in cd : cd[n] = True for c in ca : if c.r * r > 0 if r else not c.r : fnd[n] = c.c c.c._branch_out(fnd, r, cd) break # go on to the next link pass pass pass pass def find_branches(me) : """ Find any other choices that, by implication, we can link to. 3 lists are returned: A list of choices that we have a negative relation to - that is, the choices that are better than us. A list of choices that are equal to us. A list of choices we are better than. The caller can call a_chooser.learn_only_if_new(), passing these lists and their relationships (-1, 0, 1). """ m = {} z = {} p = {} me._branch_out(m, -1, { me.name : True, }) me._branch_out(z, 0, { me.name : True, }) me._branch_out(p, 1, { me.name : True, }) mk = m.keys() pk = p.keys() zk = z.keys() for n in mk : if n in p : del(p[n]) if n in z : del(z[n]) for n in pk : if n in m : del(m[n]) if n in z : del(z[n]) for n in zk : if n in m : del(m[n]) if n in p : del(p[n]) return(m.keys(), z.keys(), p.keys()) # give the tell the caller all the learnable names (so he can add them under lock protection - while making sure that they don't have refs to us or vice versa) def _extend_learning(me, om, r, cd) : for ca in me.cmps.values() : c = ca[0] if (om.name not in c.c.cmps) and (c.c.name not in cd) : ambig = False for c in ca : if (c.r != r) and (c.r != 0) : ambig = True # note: on the other hand, we could just zap things, or we could allow our learning when the majority of the links are the rite direction break pass if not ambig : for c in ca : if (c.r == r) or (c.r == 0) : c.c.cmps[om.name] = [] c.c.cmps[om.name].append(a_cmp(om, -r)) print "@@@@ xlearned", c.c.name, om.name, -r cd[c.c.name] = True c.c._extend_learning(om, r, cd) break # did the direction we search down, so we're done with this array of connections (all elements in the array have the same c.c) pass pass pass pass pass def extend_learning(me, om, r) : me._extend_learning(om, -r, { me.name : True, om.name : True }) def learn(me, om, r, extend = True) : if r != None : me.cmps[om.name] = me.cmps.get(om.name, []) me.cmps[om.name].append(a_cmp(om, r)) if extend and EXTEND_LEARNING : me.extend_learning(om, r) return(True) return(False) def learn_only_if_new(me, om, r) : if r != None : if om.name not in me.cmps : me.cmps[om.name] = [ a_cmp(om, r), ] return(True) pass return(False) def zero_order_total(me) : me.otot = 0 me.ocnt = 0 def learn_order(me, o) : me.otot += o me.ocnt += 1 def order(me) : return( me.otot / float(me.ocnt) if me.ocnt else 0) def age(me, n = None) : if n != None : n = float(min(1.0, max(0, n))) t = 0 for name in me.cmps.keys() : ca = me.cmps[name] if (n != None) and len(ca) : ln = len([ nn for nn in xrange(len(ca)) if random.random() >= n ]) if ln : ca = ca[-ln:] else : ca = [] if len(ca) : me.cmps[name] = ca else : del(me.cmps[name]) pass t += len(ca) return(t) # a_choice class a_chooser(object) : """ This is an array of choices. At any time, you can get the best guess of the order they should be in by calling sort_as_best_we_can(). But, until you've called and handled the results of find_pair() a lot, the order will be pretty random. You call find_pair() and it returns a tuple telling you whether it has successfully sorted the choices (twice) without needing a pair comparison value. It also tells you a pair of choices that it would like you to provide a comparison between. You call learn() passing the two choices and the comparison value (an int, like the python cmp() function would give for them). That cmp() value does not need to be the same each time you provide it. (Each time a_chooser is sorted, it uses just one of the results you have returned at one time or another for each pair of choices.) """ def __init__(me, chunk_size = CHUNK_SIZE, *kargs, **kwargs) : super(a_chooser, me).__init__(*kargs, **kwargs) me.set_chunk_size(chunk_size) me.known_cnt = 0 me.hurry_up = 0 me.next_abs = [] me.all_done = False me.learn_cnt = 0 me.found_cnt = 0 me.learned = {} me.choices = [] def __len__(me) : return(len(me.choices)) def __iter__(me) : return(iter(me.choices)) def __getitem__(me, ky) : return(me.choices.__getitem__(ky)) def __setitem__(me, ky, v) : r = me.choices.__setitem__(ky, v) me.all_done = False return(r) def __delitem__(me, ky) : r = me.choices.__delitem__(ky) me.all_done = False return(r) def __getslice__(me, i, j) : return(me.choices.__getslice__(i, j)) def __setslice__(me, i, j, seq) : r = me.choices.__setslice__(i, j, seq) me.all_done = False return(r) def __delslice__(me, i, j) : r = me.choices.__delslice__(i, j) me.all_done = False return(r) def __add__(me, om) : if isinstance(om, a_chooser) : me.choices += om.choices else : me.choices += om me.all_done = False return(me) def append(me, c) : me.choices.append(c) me.all_done = False def choices_cmp(me, a, b) : if a.name <= b.name : # so we have a stable sort neg = False ( aa, bb ) = ( a, b ) else : neg = True ( bb, aa ) = ( a, b ) r = aa.cmp(bb) if r == None : me.next_abs.append([ a, b ]) r = 0 if neg : r = -r return(r) def set_chunk_size(me, chunk_size = None) : ov = getattr(me, 'chunk_size', 16) if chunk_size != None : me.chunk_size = 16 if chunk_size <= 1 else chunk_size return(ov) def set_hurry_up(me, v) : ov = me.hurry_up if v != None : me.hurry_up = v return(ov) def find_best_ab(me) : me.alldone = False random.shuffle(me.next_abs) # so that equal ones will come in different orders each time i = tzlib.min_index([ max(ab[0].found_cnt, ab[1].found_cnt) for ab in me.next_abs ]) ab = me.next_abs[i] # print "@@@@", ab[0].found_cnt, ab[1].found_cnt, me.found_cnt, "\n " + "\n ".join([ str([ba[0].found_cnt, ba[1].found_cnt ]) for ba in me.next_abs ]) ab[0].found_cnt = me.found_cnt ab[1].found_cnt = me.found_cnt return(False, ab[0], ab[1]) def find_pair(me) : """ Return: bool whether we managed to do a full sort without any ambiguity (not necessarily implying that all things are known in relation to all other things. two items whose comparison we don't know or that seem to be pretty ambiguously rated. """ if len(me) < 2 : me.alldone = False return(True, None, None) me.found_cnt += 1 if me.known_cnt < len(me) : bi = max(0, min(len(me) - me.chunk_size, me.known_cnt)) ei = min(len(me), bi + me.chunk_size) me.all_done = False else : bi = 0 ei = len(me) me.next_abs = [] if (bi != 0) or (ei != len(me)) : me.all_done = False a = list(me.choices[bi:ei]) for c in me.choices[bi:ei] : c.start_sort() a.sort(me.choices_cmp) for ci, c in enumerate(a) : c.learn_order(ci * len(me) / float(ei - bi)) me.choices[bi:ei] = a if not len(me.next_abs) : random.shuffle(me.choices) for c in me.choices : c.start_sort() me.choices.sort(me.choices_cmp) for ci, c in enumerate(me.choices) : c.learn_order(ci) if len(me.next_abs) : return(me.find_best_ab()) if me.known_cnt < ei : me.known_cnt = ei me.alldone = False return(me.find_pair()) # find a pair in the next chunk or the whole thing if bi != 0 : me.alldone = False return(me.find_pair()) # find a pair in the whole thing nd1 = tzlib.make_index_dictionary([ c.name for c in me.choices ]) random.shuffle(me.choices) for c in me.choices : c.start_sort() me.choices.sort(me.choices_cmp) if len(me.next_abs) : return(me.find_best_ab()) if not me.all_done : for c in me.choices : c.zero_order_total() me.all_done = True for ci, c in enumerate(me.choices) : c.learn_order(ci) nd2 = tzlib.make_index_dictionary([ c.name for c in me.choices ]) da = [ [ abs(nd1[n] - nd2[n]) * (me.found_cnt - me.choices[nd2[n]].found_cnt + 4), n ] for n in nd1.keys() ] # find how far away from itself in the two sorts each item is da.sort() a = me.choices[nd2[da[-2][1]]] b = me.choices[nd2[da[-1][1]]] a.found_cnt = me.found_cnt b.found_cnt = me.found_cnt return(True, a, b) # return the two items that sorted most differently in array index scaled by how recently they've been chosen def make_old(me, a = None, b = None) : me.found_cnt += 1 if a : a.found_cnt = me.found_cnt if b : b.found_cnt = me.found_cnt pass def make_choice_dict(me) : cd = {} for cc in me.choices : cd[cc.name] = cc return(cd) def learn(me, a, b, r, extend = True) : me.all_done = False if r != None : a.learn(b, r, extend = extend) b.learn(a, -r, extend = extend) me.learn_cnt += 1 me.put_choice_to_extend_learning(a) me.put_choice_to_extend_learning(b) return(True) return(False) def _learn_only_if_new(me, c, names, r, cd) : lnames = [] for n in names : if n in cd : om = cd[n] if c.learn_only_if_new(om, r) : me.put_choice_to_extend_learning(om) lnames.append(n) if not om.learn_only_if_new(c, -r) : raise ValueError("%s %s" % ( c.name, om.name ) ) pass pass pass return(lnames) def learn_only_if_new(me, c, m, z, p) : cd = me.make_choice_dict() m = me._learn_only_if_new(c, m, -1, cd) z = me._learn_only_if_new(c, z, 0, cd) p = me._learn_only_if_new(c, p, 1, cd) return(m, z, p) def queue_newly_learned(me, m, z, p) : """ Put the choices in the return value from learn_only_if_new() to the learning queue. """ cd = me.make_choice_dict() for n in m : me.put_choice_to_extend_learning(cd[n].find_tweens(cd[n], -1)) for n in z : me.put_choice_to_extend_learning(cd[n].find_tweens(cd[n], 0)) for n in p : me.put_choice_to_extend_learning(cd[n].find_tweens(cd[n], 1)) def get_choice_to_extend_learning(me) : if len(me.learned) : n = random.choice(me.learned.keys()) c = me.learned[n] del(me.learned[n]) return(c) return(None) def put_choice_to_extend_learning(me, c_or_ca) : if not isinstance(c_or_ca, ( tuple, list )) : c_or_ca = [ c_or_ca ] for c in c_or_ca : me.learned[c.name] = c pass def find_tweens(me, cnm, onm, r) : ca = [] cd = me.make_choice_dict() if (cnm in cd) and (onm in cd) : ca = cd[cnm].find_tweens(cd[onm], r) return(ca) def find_distant_pair(me) : if (not me.all_done) and (len(me.choices) >= 8) : ( aa, bb ) = random.sample(me.choices, 2) r = aa.find_cmp(bb) # search aa's tree for a path to bb if (not me.hurry_up) and (r != None) : return(r, aa, bb) pass return(None, None, None) def sort_as_best_we_can(me) : ( r, a, b ) = me.find_pair() me.choices.sort(lambda a, b : cmp(a.order(), b.order())) return(r) def relearn_order(me, cnt = None) : r = True cnt = cnt if cnt > 0 else 10 for c in me.choices : c.zero_order_total() for i in xrange(cnt) : random.shuffle(me.choices) me.next_abs = [] for c in me.choices : c.start_sort() me.choices.sort(me.choices_cmp) if len(me.next_abs) : r = False for ci, c in enumerate(me.choices) : c.learn_order(ci) r &= me.sort_as_best_we_can() return(r) def age(me, n = None) : t = 0 for c in me.choices : t += c.age(n) if n != None : me.all_done = False return(t) # a_chooser if __name__ == '__main__' : t = tzlib.elapsed_time() how_many = 65 if len(sys.argv) > 1 : how_many = int(sys.argv[1]) until_relearn = False me = a_chooser() me += [ a_choice(str(n), "") for n in range(how_many) ] random.shuffle(me) print [ n.name for n in me ] cnt = 0 while True : ( r, a, b ) = me.find_pair() if EXTEND_LEARNING and r : break if r : print "Trying" if (until_relearn and me.relearn_order()) or ((not until_relearn) and me.find_pair()[0]) : break pass if not r : if b.name in a.cmps : print "BUG!", b.name, a.name if a.name in b.cmps : print "BUG!", a.name, b.name # print a.name, b.name rr = int(a.name) - int(b.name) # rr = int(sys.stdin.readline().strip()) me.learn(a, b, rr) if not EXTEND_LEARNING : cds = {} while True : c = me.get_choice_to_extend_learning() if not c : break if c not in cds : cds[c] = True ( m, z, p ) = c.find_branches() if m or z or p : # if m : print "learning", c.name, m, -1 # if z : print "learning", c.name, z, 0 # if p : print "learning", c.name, p, 1 ( m, z, p ) = me.learn_only_if_new(c, m, z, p) me.queue_newly_learned(m, z, p) # print "learned", c.name, m, z, p pass pass pass cnt += 1 es = "" pn = -1 for c in me : i = int(c.name) if i <= pn : es += "BUG not in order %s %d\n" % ( c.name, pn ) pn = i t = tzlib.elapsed_time() print "results", cnt, me.age(), r, "\n " + "\n ".join([ "%5s %7s %5s" % ( c.name, str(round(c.order(), 1)), str(c.ocnt) ) for c in me ]) # note: they may not be in order because all comparisons between all items aren't necessarily known r = me.sort_as_best_we_can() print round(tzlib.elapsed_time() - t, 2) r = me.relearn_order() print "relearn", cnt, me.age(), r, "\n " + "\n ".join([ "%5s %7s %5s" % ( c.name, str(round(c.order(), 1)), str(c.ocnt) ) for c in me ]) # note: they may not be in order because all comparisons between all items aren't necessarily known print cnt, me.age() if es : print es for c in me : for ca in c.cmps.values() : if len(ca) > 1 : print "BUG ca len > 1", c.name, [ str([cc.c.name, cc.r ]) for cc in ca ] pass pass pass for c in me : for ca in c.cmps.values() : om = ca[0].c if c.name not in om.cmps : print "BUG unreciprical", c.name, om.name elif ca[0].r != -om.cmps[c.name][0].r : print "BUG disagree", c.name, om.name, ca[0].r, om.cmps[c.name][0].r pass pass pass # # # # eof