ищет алгоритм соответствия кортежей

Question

Мне нужно реализовать функцию сопоставления кортежей строк в памяти в C. Будет большой список кортежей, связанных с различными действиями, и большое количество событий, которые будут сопоставлены со списком.

Список кортежей:

("one", "four")
("one")
("three")
("four", "five")
("six")    

Событие («один», «два», «три», «четыре») должно соответствовать элементам списка («один», «четыре») и («один») и («три»), но не (« четыре "," пять "), а не (" шесть ")

мой текущий подход использует карту всех значений полей кортежей в качестве ключей для списков каждого кортежа, использующего это значение. есть много избыточного хэширования и вставки списка.

Есть ли правильный или классический способ сделать это?

Answer 1

Если у вас есть только небольшое количество возможных значений кортежей, имеет смысл написать какую-то хеш-функцию, которая может превратить их в целочисленные индексы для быстрого поиска.

Если есть <32 значений, вы можете сделать что-то с битовыми масками: </p>

unsigned int hash(char *value){...}

typedef struct _tuple {
    unsigned int bitvalues;
    void * data
} tuple;

tuple a,b,c,d;
a.bitvalues  = hash("one");
a.bitvalues |= hash("four");
//a.data = something;

unsigned int event = 0;
//foreach value in event;
event |= hash(string_val);

// foreach tuple
if(x->bitvalues & test == test)
{
     //matches
}

Если существует слишком много значений для решения битовой маски, у вас может быть массив связанных списков. Пройдите каждый пункт в событии. Если элемент соответствует key_one, пройдитесь по кортежам с первым ключом и проверьте событие для второго ключа:

typedef struct _tuple {
    unsigned int key_one;
    unsigned int key_two;
    _tuple *next;
    void * data;
} tuple;

tuple a,b,c,d;
a.key_one = hash("one");
a.key_two = hash("four");

tuple * list = malloc(/*big enough for all hash indexes*/
memset(/*clear list*/);

//foreach touple item
if(list[item->key_one])
   put item on the end of the list;
else
   list[item->key_one] = item;


//foreach event
   //foreach key
      if(item_ptr = list[key])
        while(item_ptr.next)
           if(!item_ptr.key_two || /*item has key_two*/)
              //match
           item_ptr = item_ptr.next;

Этот код никоим образом не проверен и, вероятно, содержит много мелких ошибок, но вы должны понять. (одна ошибка, которая была исправлена, была условием проверки соответствия кортежей)

---

Если скорость обработки событий имеет первостепенное значение, имеет смысл перебирать все ваши построенные кортежи, подсчитывать количество вхождений и проходить, возможно, переупорядочение ключа один / ключ два из каждого кортежа, чтобы получить наиболее уникальное значение указан первым

Answer 2

Возможным решением будет присвоить уникальное простое число каждому из слов.

Тогда, если вы умножите слова вместе в каждом кортеже, то у вас будет число, которое представляет слова в списке.

Разделите один список на другой, и если вы получите целочисленный остаток, то один список будет содержаться в другом.

Answer 3

Я не знаю ни одного классического или правильного способа сделать это, поэтому вот что я бы сделал: P

Похоже, вы хотите решить, является ли A надмножеством B, используя теорию множеств. Один из способов сделать это - отсортировать A и B и выполнить операцию сортировки слиянием слиянием для A и B, в которой вы пытаетесь найти, где в A находится значение в B. Те элементы B, которые также находятся в A, будут иметь дубликаты, а другие элементы не будут. Поскольку и A, и B отсортированы, это не должно быть слишком ужасно.

Например, вы берете первое значение B и идете A, пока не найдете его дубликат в A. Затем вы берете второе значение B и начинаете идти с того места, где вы остановились ранее. Если вы дошли до конца A, не найдя соответствия, то A не является надмножеством B, и вы возвращаете false.

Если эти кортежи могут оставаться отсортированными, то затраты на сортировку производятся только один раз.

Answer 4

    public static void Main()
    {
        List<List<string>> tuples = new List<List<string>>();

        string [] tuple = {"one", "four"};
        tuples.Add(new List<string>(tuple));

        tuple = new string [] {"one"};
        tuples.Add(new List<string>(tuple));

        tuple = new string [] {"three"};
        tuples.Add(new List<string>(tuple));

        tuple = new string[]{"four", "five"};
        tuples.Add(new List<string>(tuple));

        tuple = new string[]{"six"};
        tuples.Add(new List<string>(tuple));

        tuple = new string[] {"one", "two", "three", "four"};

        List<string> checkTuple = new List<string>(tuple);

        List<List<string>> result = new List<List<string>>();

        foreach (List<string> ls in tuples)
        {
            bool ok = true;
            foreach(string s in ls)
                if(!checkTuple.Contains(s))
                {
                    ok = false;
                    break;
                }
            if (ok)
                result.Add(ls);
        }
    }

Answer 5

Если у вас есть небольшое количество возможных строк, вы можете назначить индекс для каждой и использовать растровые изображения. Таким образом, простой побитовый и скажет вам, если есть перекрытие.

Если это нецелесообразно, вероятно, вам будет сложно подобрать скорректированную настройку обратного индекса, особенно если вам нужно построить ее только один раз. (меняется ли список кортежей во время выполнения?)