superponer - buscando un algoritmo de comparación de tuplas

tuplas c#

Question

Necesito implementar una función de coincidencia de tuplas de cuerdas en memoria en C. Habrá una gran lista de tuplas asociadas con diferentes acciones y un gran volumen de eventos que se compararán con la lista.

Lista de tuplas:

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

evento ("uno", "dos", "tres", "cuatro") debe coincidir con el elemento de la lista ("uno", "cuatro") y ("uno") y ("tres") pero no ("cuatro", "cinco") y no ("seis")

mi enfoque actual usa un mapa de todos los valores de campo de tupla como claves para las listas de cada tupla que usa ese valor. hay una gran cantidad de hashing redundante e inserción de lista.

¿Hay una forma correcta o clásica de hacer esto?

Answer 1

No conozco ninguna forma clásica o correcta para hacer esto, así que esto es lo que haría: P

Parece que quieres decidir si A es un superconjunto de B, usando la jerga de la teoría de conjuntos. Una forma de hacerlo es ordenar A y B, y realizar una operación de combinación de ordenación en A y B, en la que intentas encontrar el valor de A en A en B. Esos elementos de B que también están en A, tendrán duplicados, y los otros elementos no. Debido a que tanto A como B están clasificados, esto no debería ser demasiado horrible.

Por ejemplo, toma el primer valor de B y camina A hasta que encuentre su duplicado en A. Luego toma el segundo valor de B y comienza a caminar A desde donde lo dejó anteriormente. Si llega al final de A sin encontrar una coincidencia, entonces A no es un superconjunto de B, y usted devuelve falso.

Si estas tuplas pueden permanecer clasificadas, el costo de clasificación solo se incurre una vez.

Answer 2

Si solo tiene una pequeña cantidad de valores de tupla posibles, tendría sentido escribir algún tipo de función de hash que podría convertirlos en índices enteros para una búsqueda rápida.

Si hay <32 valores, podrías hacer algo con las máscaras de bits:

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
}

Si hay demasiados valores para hacer una solución de máscara de bits, podría tener una matriz de listas vinculadas. Repase cada elemento en el evento. Si el elemento coincide con key_one, recorra las tuplas con esa primera clave y verifique el evento para la segunda clave:

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;

Este código no se ha probado de ninguna manera y es probable que tenga muchos errores pequeños, pero debe entenderse. (Un error que se corrigió fue la condición de prueba para una coincidencia de tuplas)

Si la velocidad de procesamiento de eventos es de suma importancia, tendría sentido iterar a través de todas las tuplas construidas, contar el número de ocurrencias y posiblemente reordenar la clave / clave dos de cada tupla para que el valor más exclusivo aparezca primero .

Answer 3

Si tiene un número pequeño de cadenas posibles, puede asignar un índice a cada una y usar mapas de bits. De esta manera, un simple bitwise y le dirá si hay superposición.

Si eso no es práctico, su configuración de índice invertido probablemente será difícil de igualar con la velocidad, especialmente si solo tiene que construirlo una vez. (¿la lista de tuplas cambia en tiempo de ejecución?)

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

Una posible solución sería asignar un número primo único a cada una de las palabras.

Luego, si multiplicas las palabras juntas en cada tupla, entonces tienes un número que representa las palabras en la lista.

Divida una lista por otra, y si obtiene un resto entero, entonces la lista está contenida en la otra.