Поиск частичного ключа в python dict [duplicate]
Отсутствует «extern» в объявлениях / определениях переменной const (только для C ++)
Для людей, прибывающих с C, может показаться неожиданным, что в C ++ глобальные переменные const имеют внутренние (или статические) связь. В C это не так, поскольку все глобальные переменные неявно extern (т.е. когда отсутствует ключевое слово static).
Пример:
// file1.cpp
const int test = 5; // in C++ same as "static const int test = 5"
int test2 = 5;
// file2.cpp
extern const int test;
extern int test2;
void foo()
{
int x = test; // linker error in C++ , no error in C
int y = test2; // no problem
}
correct would использовать файл заголовка и включить его в file2.cpp и file1.cpp
extern const int test;
extern int test2;
. В качестве альтернативы можно было бы объявить переменную const в файле file1.cpp с явным extern
2 ответа
Без предварительной обработки dict, O(n) - это лучшее, что вы можете сделать. Это не должно быть сложным:
any(key.startswith(mystr) for key in mydict)
(Не используйте dict и str в качестве имен переменных, это уже имена двух встроенных функции .)
Если вы можете препроизвести dict, подумайте о том, чтобы положить ключи в дерево префикса (aka trie ). Существует даже реализация Python в статье в Википедии.
-
1– abarnert 5 August 2013 в 21:38
-
2– user 5 August 2013 в 23:29
-
3– abarnert 6 August 2013 в 00:02
-
4– user 6 August 2013 в 00:53
-
5– Mr. Llama 22 April 2018 в 19:29
Вы можете поместить все префиксы вставленных ключей в dict, поэтому для клавиши foo вы должны вставить f, fo и foo. У вас был бы поиск O (1), но вы бы потратили время на предварительную обработку (O (k), где k - длина ключа) и потратили много памяти:
def insert_with_prefixes(key, value, dict_):
prefixes = (key[:i+1] for i in xrange(len(key)))
dict_.update((prefix, value) for prefix in prefixes)
Для повседневного использования я (и я иду) с помощью метода в ответе arshajii's . И, конечно, иметь в виду возможные столкновения для коротких префиксов (здесь: "h"):
>>> a = {}
>>> insert_with_prefixes('hello', 'world', a)
>>> insert_with_prefixes('homo', 'sapiens', a)
>>> a
{'h': 'sapiens', 'hom': 'sapiens', 'homo': 'sapiens', 'ho': 'sapiens',
'hel': 'world', 'hell': 'world', 'hello': 'world', 'he': 'world'}