Корзины с предохранителями для поиска классов эквивалентности

Ответ 1

Здесь некоторый psuedo (код С#, который я не тестировал), который демонстрирует ваши S '= < {a}, {b, c} > + < {b}, {b, c} > . За исключением требований к пространству, которые при использовании целочисленного индекса для элемента незначительны; общая эффективность и скорость для добавления и тестирования кортежей должны быть очень быстрыми. Если вы хотите получить практическое решение, то у вас уже есть тот, который вам нужен только для использования правильных ADT.

ElementType[] domain = new ElementType[]; // a simple array of domain elements
  FillDomain(domain); // insert all domain elements
  SortArray(domain); // sort the domain elements  K log K time
SortedDictionary<int, HashSet<int>> subsets; // int are index/ref into domain
subsets = new SortedDictionary<int, HashSet<int>>();
//
void AddTuple(SortedDictionary<int, HashSet<int>> tuples, ElementType[] domain, ElementType first, elementType second) {
    int a = BinarySearch(domain, first); // log K time (binary search)
    int b = BinarySearch(domain, second); // log K time (binary search)
    if(tuples.ContainsKey(a)) { // log N time (binary search on sorted keys)
        if(!tuples[a].Contains(b)) { // constant time (hash lookup)
            tuples[a].Add(b); // constant time (hash add)
        }         
    } else { // constant time (instance + hash add)
        tuples[a] = new HashSet<in>();
        tuples[a].Add(b);
    }
}
//
bool ContainsTuple(SortedDictionary<int, HashSet<int>> tuples, ElementType[] domain, ElementType first, ElementType second) {
    int a = BinarySearch(domain, first); // log K time (binary search)
    int b = BinarySearch(domain, second); // log K time (binary search)
    if(tuples.ContainsKey(a)) { // log N time (binary search on sorted keys)
        if(tuples[a].Contains(b)) { // constant time (hash test)
            return true;
        }
    }
    return false;
}

Экономия пространства для оптимизации вашего подмножества S 'не приведет к снижению производительности самого процесса оптимизации. Для оптимизации размера (если вы знаете, что вы K будет меньше 65536, вы можете использовать короткие целые числа вместо целых чисел в SortedDictionary и HashSet. Но даже целые числа 50 mil занимают всего 4 байта на 32-битное целое * 50 mil ~ = 200 MB.

ИЗМЕНИТЬ Здесь другой подход, кодирующий/сопоставляя ваши кортежи с строкой, вы можете использовать сравнение бинарных строк и тот факт, что кодировка UTF-16/UTF-8 очень эффективна по размеру. Опять же, это еще не делает оптимизацию слияния, которую вы хотите, но скорость и эффективность будут очень хорошими.

Вот несколько быстрых псевдокодов в JavaScript.

Array.prototype.binarySearch = function(elm) {
  var l = 0, h = this.length - 1, i; 
  while(l <= h) { 
    i = (l + h) >> 1; 
    if(this[i] < elm) l = ++i; 
    else if(this[i] > elm) h = --i; 
    else return i; 
  } 
  return -(++l); 
};
// map your ordered domain elements to characters 
// For example JavaScript UTF-16 should be fine
// UTF-8 would work as well
var domain = {
  "a": String.fromCharCode(1),
  "b": String.fromCharCode(2),
  "c": String.fromCharCode(3),
  "d": String.fromCharCode(4)
}
var tupleStrings = [];
// map your tuple to the string encoding
function map(tuple) {
  var str = "";
  for(var i=0; i<tuple.length; i++) {
    str += domain[tuple[i]];
  }
  return str;
}
function add(tuple) {
  var str = map(tuple);
  // binary search
  var index = tupleStrings.binarySearch(str);
  if(index < 0) index = ~index;
  // insert depends on tupleString type implementation
  tupleStrings.splice(index, 0, str);
}
function contains(tuple) {
  var str = map(tuple);
  // binary search 
  return tupleString.binarySearch(str) >= 0;
}

add(["a","b"]);
add(["a","c"]);
add(["b","b"]);
add(["b","c"]);
add(["c","c"]);
add(["d","a"]);
alert(contains(["a","a"]));
alert(contains(["d","a"]));
alert(JSON.stringify(tupleStrings, null, "\n"));