XOR query

performance_test.py

#!/usr/bin/env python3

# Test the performance of XOR query
# Copyright (C) 2016 Raphael McSinyx
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.

from sys import argv
from random import randrange, choice
from time import monotonic

import xorquery
import xorquery0


def geninp(q):
    l = []
    with open("xorquery.inp", 'w') as f:
        f.write("{}\n".format(q))
        for _ in range(q):
            c = choice("+-?" if l else "+?")
            if c == "+":
                x = randrange(1000000001)
                l.append(x)
                f.write("+ {}\n".format(x))
            elif c == "-":
                f.write("- {}\n".format(l.pop(randrange(len(l)))))
            else:
                f.write("? {}\n".format(randrange(1000000001)))


def main(name, n=20, q=0, *args):
    try:
        n = int(n)
        q = int(q)
    except:
        print("Usage: performance_test.py [number_of_tests [queries_per_test]]")
    else:
        l = [q] * n if q > 0 else [randrange(200001) for _ in range(n)]
        for q0 in l:
            geninp(q0)
            t0 = monotonic()
            xorquery.main()
            t1 = monotonic()
            xorquery0.main()
            t2 = monotonic()
            print("{}\t{}\n\t{}".format(q0, t1 - t0, t2 - t1))


if __name__ == "__main__":
    main(*argv)

xorquery.py

#!/usr/bin/env python3

# XOR query
# Copyright (C) 2016 Raphael McSinyx
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.


def main():
    # for the love of God, I won't use uppercase filenames
    with open('xorquery.inp') as inp, open('xorquery.out', 'w') as out:
        s = {0: 1}
        q = int(inp.readline())
        for _ in range(q):
            l = inp.readline().split()
            c, x = l[0], int(l[1])
            if c == '+':
                s[x] = s.get(x, 0) + 1
            elif c == '-':
                if s[x] == 1: del s[x]
                else: s[x] -= 1
            else:   # assume that c would be '?'
                out.write(str(max(x ^ y for y in s)) + '\n')


if __name__ == '__main__':
    main()

xorquery0.py

#!/usr/bin/env python3

# XOR query
# Copyright (C) 2016 Raphael McSinyx
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.

s = dict.fromkeys(['0' * i for i in range(1, 31)], 1)


def plus(x):
    global s
    b = "{:030b}".format(x)

    for i in range(1, 31):
        b0 = b[:i]
        s[b0] = s.get(b0, 0) + 1


def minus(x):
    global s
    b = "{:030b}".format(x)

    for i in range(1, 31):
        b0 = b[:i]
        if s[b0] == 1:
            del s[b0]
        else:
            s[b0] -= 1


def question(x):
    global s
    b = "{:030b}".format(x)
    y = ""

    for i in b:
        n = int(i)
        l = []

        for c in "01":
            if y + c in s:
                l.append((int(c) ^ n, c))

        if len(l) == 1:
            y += l[0][1]
        else:
            y += l[0][1] if l[0][0] > l[1][0] else l[1][1]

    return "{}\n".format(x ^ int(y, 2))


def main():
    # for the love of God, I won't use uppercase filenames
    with open('xorquery.inp') as inp, open('xorquery.out', 'w') as out:
        q = int(inp.readline())

        for _ in range(q):
            l = inp.readline().split()
            c, x = l[0], int(l[1])

            if c == '+':
                plus(x)
            elif c == '-':
                minus(x)
            else:
                out.write(question(x))

    #global s
    #print(s)


if __name__ == '__main__':
    main()