поиск алгоритма соответствия кортежа
Я думаю, что самый простой способ сопоставления символов, таких как
\^$.?*|+()[
, использует классы символов изнутри R. Рассмотрим, как очистить заголовки столбцов от файла данных, которые могут содержать пробелы и пунктуацию characters:
> library(stringr)
> colnames(order_table) <- str_replace_all(colnames(order_table),"[:punct:]|[:space:]","")
Этот подход позволяет нам вводить классы символов в соответствие с символами пунктуации, в дополнение к символам пробелов, что вам обычно нужно было бы избежать с помощью \\ для обнаружения. Вы можете узнать больше о классах символов в этой таблице ниже, и вы также можете ввести ?regexp, чтобы узнать больше об этом.
https://www.rstudio.com/wp -поперечник / добавления / 2016/09 / RegExCheatsheet.pdf
5 ответов
Если бы у Вас только есть небольшое количество возможных значений кортежа, имело бы смысл писать своего рода хеш-функцию, которая могла превратить их в целочисленные индексы для быстрого поиска.
Если существует <32 значения, Вы могли бы сделать что-то с битовыми масками:
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;
Этот код никоим образом не тестируется и вероятно имеет много небольших ошибок, но необходимо получить идею. (одна ошибка, которая была исправлена, была условием испытания для соответствия кортежа),
Если бы скорость обработки событий имеет наибольшее значение, что имело бы смысл выполнять итерации через все Ваши созданные кортежи, считать количество случаев и проходить возможное переупорядочение ключа один/ключ два из каждого кортежа, таким образом, самое уникальное значение перечислено сначала.
Возможное решение состояло бы в том, чтобы присвоить уникальный простой номер каждому из слов.
Затем при умножении слов вместе в каждом кортеже затем у Вас есть число, которое представляет слова в списке.
Разделите один список на другого, и если Вы получаете целочисленный остаток, затем один список содержится в другом.
Если у Вас есть небольшое количество возможных строк, можно присвоить индекс каждому и использовать битовые массивы. Тот способ, которым простое поразрядное и скажет Вам, если будет перекрытие.
Если это не практично, Ваша установка инвертированного индекса, вероятно, будет трудной соответствовать для скорости, особенно если только необходимо создать ее однажды. (список кортежей изменяется во времени выполнения?)
Я не знаю ни о каком классическом или правильном способе сделать это, таким образом, вот то, что я сделал бы :P
Похоже, что Вы хотите решить, является ли A надмножеством B, с помощью жаргона теории множеств. Одним путем можно сделать это, должен отсортировать A и B, и сделать операцию сортировки-слиянием-esque на A и B, в этом Вы пытаетесь найти, куда в значение в B идет. Те элементы B, которые находятся также в A, будут иметь дубликаты, и другие элементы не будут. Поскольку и A и B отсортированы, это не должно быть слишком ужасно.
Например, Вы принимаете первое значение B и идете, пока Вы не находите его дубликат в A. Затем Вы принимаете второе значение B и начинаете идти от того, где Вы кончили ранее. Если Вы добираетесь до конца, не находя соответствие, то A не является надмножеством B, и Вы возвращаете false.
Если эти кортежи могут остаться отсортированными, то стоимость сортировки только понесена однажды.
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);
}
}