10

I'm looking for a functional data structure that represents finite bijections between two types, that is space-efficient and time-efficient.

For instance, I'd be happy if, considering a bijection f of size n:

  • extending f with a new pair of elements has complexity O(ln n)
  • querying f(x) or f^-1(x) has complexity O(ln n)
  • the internal representation for f is more space efficient than having 2 finite maps (representing f and its inverse)

I am aware of efficient representation of permutations, like this paper, but it does not seem to solve my problem.

esope
  • 760
  • 3
  • 12
  • 10
    Having two finite maps is pretty space efficient... it's O(n) space. I can't imagine you can do better than that. – Daniel Wagner May 19 '12 at 22:27
  • 4
    Start with two finite maps, and worry about something more clever when you run out of memory. Hashmaps are good, if you can hash the two types. – augustss May 19 '12 at 23:19
  • 3
    Seems like if your function is strictly monotone you could search the same tree for both function and inverse. It's a long shot, I guess. – Jeffrey Scofield May 20 '12 at 04:18
  • Another special case is when the two types are the same (permutation). One map is enough, if the map records both the image and the pre-image of an element. – esope May 22 '12 at 18:11

2 Answers2

12

Please have a look at my answer for a relatively similar question. The provided code can handle general NxM relations, but also be specialized to just bijections (just as you would for a binary search tree).

Pasting the answer here for completeness:

The simplest way is to use a pair of unidirectional maps. It has some cost, but you won't get much better (you could get a bit better using dedicated binary trees, but you have a huge complexity cost to pay if you have to implement it yourself). In essence, lookups will be just as fast, but addition and deletion will be twice as slow. Which isn't so bad for a logarithmic operation. Another advantage of this technique is that you can use specialized maps types for the key or value type if you have one available. You won't get as much flexibility with a specific generalist data structure.

A different solution is to use a quadtree (instead of considering a NxN relation as a pair of 1xN and Nx1 relations, you see it as a set of elements in the cartesian product (Key*Value) of your types, that is, a spatial plane), but it's not clear to me that the time and memory costs are better than with two maps. I suppose it needs to be tested.

Community
  • 1
  • 1
gasche
  • 31,259
  • 3
  • 78
  • 100
  • Your data structure seems similar in spirit to a [kd-tree](https://en.wikipedia.org/wiki/Kd-tree). – esope May 21 '12 at 15:13
6

Although it doesn't satisfy your third requirement, bimaps seem like the way to go. (They just make two finite maps, one in each direction, convenient to use.)

Daniel Wagner
  • 145,880
  • 9
  • 220
  • 380