поиска эффективна в словаре

Question

У меня есть длинный словарь форма строки в строку, как

{'a':'b' , 'c':'d'} 

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

Answer 1

Если у вас есть словарь d и хотите проверить на членство ключевого k, вы можете просто использовать k in d или k not in d. Например:

>>> d = {'a':'b' , 'c':'d'} 
>>> 'a' in d 
True 
>>> 'x' in d 
False 
>>> 'a' not in d 
False 
>>> 'x' not in d 
True 
>>> 

Эти проверки должны быть очень эффективными, поскольку словари (и наборы) реализованы с помощью хэш-таблиц.

Answer 2

Существует уже интересный квест на How are Python's Built In Dictionaries Implemented ...

, но почему бы не попробовать и измерить здесь (после того, как прочитал о времени coplexity в реализации Python):

#! /usr/bin/env python 
from __future__ import division, print_function 

import dis # for disassembling (bottom) 
import string # string.printable as sample character source 
import timeit 


chars = tuple(string.printable) 
cartesian = tuple(a + b for a in chars for b in chars) 
assert 10000 == len(cartesian), print(len(cartesian)) 
d = dict((a + b, b) for a in cartesian for b in chars) 

assert 1000000 == len(d), print(len(d)) 
assert d['zzz'] == 'z' 

setup = """ 
import string 
chars = tuple(string.printable) 
d = dict((a + b, b) for a in chars for b in chars) 
""" 

assert 1000000/10000 == 100 
setup_100x = """ 
import string 
chars = tuple(string.printable) 
cartesian = tuple(a + b for a in chars for b in chars) 
d = dict((a + b, b) for a in cartesian for b in chars) 
""" 

stmt = """ 
'zzz' in d 
""" 


t = timeit.timeit(stmt=stmt, setup=setup, timer=timeit.default_timer, 
        number=timeit.default_number) 

print("# Timing[secs] for 1x10000:", t) 

t_100x = timeit.timeit(stmt=stmt, setup=setup_100x, timer=timeit.default_timer, 
         number=timeit.default_number) 

print("# Timing[secs] for 100x10000:", t_100x) 

disassemble_me = "'zzz' in {'a': 'b'}" 
print("# Disassembly(lookup in dict with 1 string entry):") 
print("#", disassemble_me) 
dis.dis(disassemble_me) 

disassemble_me = "'zzz' in {'a': 'b', 'c': 'd'}" 
print("# Disassembly(lookup in dict with 2 string entries):") 
print("#", disassemble_me) 
dis.dis(disassemble_me) 

disassemble_me = "'zzz' in {'a': 'b', 'c': 'd', 'e': 'f'}" 
print("# Disassembly(lookup in dict with 3 string entries):") 
print("#", disassemble_me) 
dis.dis(disassemble_me) 

На моей машине с Python 2.7.11 это дает:

# Timing[secs] for 1x10000: 0.0406861305237 
# Timing[secs] for 100x10000: 0.0472030639648 
# Disassembly(lookup in dict with 1 string entry): 
# 'zzz' in {'a': 'b'} 
     0 <39>   
     1 SETUP_FINALLY 31354 (to 31358) 
     4 <39>   
     5 SLICE+2   
     6 BUILD_MAP  8302 
     9 <123>   24871 
     12 <39>   
     13 INPLACE_DIVIDE 
     14 SLICE+2   
     15 <39>   
     16 DELETE_GLOBAL 32039 (32039) 
# Disassembly(lookup in dict with 2 string entries): 
# 'zzz' in {'a': 'b', 'c': 'd'} 
     0 <39>   
     1 SETUP_FINALLY 31354 (to 31358) 
     4 <39>   
     5 SLICE+2   
     6 BUILD_MAP  8302 
     9 <123>   24871 
     12 <39>   
     13 INPLACE_DIVIDE 
     14 SLICE+2   
     15 <39>   
     16 DELETE_GLOBAL 11303 (11303) 
     19 SLICE+2   
     20 <39>   
     21 DUP_TOPX  14887 
     24 SLICE+2   
     25 <39>   
     26 LOAD_CONST  32039 (32039) 
# Disassembly(lookup in dict with 3 string entries): 
# 'zzz' in {'a': 'b', 'c': 'd', 'e': 'f'} 
     0 <39>   
     1 SETUP_FINALLY 31354 (to 31358) 
     4 <39>   
     5 SLICE+2   
     6 BUILD_MAP  8302 
     9 <123>   24871 
     12 <39>   
     13 INPLACE_DIVIDE 
     14 SLICE+2   
     15 <39>   
     16 DELETE_GLOBAL 11303 (11303) 
     19 SLICE+2   
     20 <39>   
     21 DUP_TOPX  14887 
     24 SLICE+2   
     25 <39>   
     26 LOAD_CONST  11303 (11303) 
     29 SLICE+2   
     30 <39>   
     31 LOAD_NAME  14887 (14887) 
     34 SLICE+2   
     35 <39>   
     36 BUILD_TUPLE  32039 

Таким образом, 10000 записей искали «zz» в 10^4 входах в ок. 40 миллисекунд в среднем (timeit.default_number == 1000000) и менее 50 миллисекунд в 100 раз больше, то есть 10^6 записей (для поиска 'zzz').

# Timing[secs] for 1x10000: 0.0406861305237 
# Timing[secs] for 100x10000: 0.0472030639648 

измерение означает воспроизводимость :-), таким образом, запустить его снова:

# Timing[secs] for 1x10000: 0.0441079139709 
# Timing[secs] for 100x10000: 0.0460820198059 

оседает просто (с другими пробегов здесь не показаны вокруг Dict с этими ключевыми типами и длинами связей (ключи более крупный диктофон также длиннее!), что есть здесь no Линейный наихудший случай реализован. Это больше похоже на 10% более продолжительное время работы для 100-кратного большего количества dict (количество записей qua) и длину ключа на 50%.

Выглядит хорошо. Предложите всегда измерять и разбирать, когда сомневаетесь. HTH.

PS: OP может по-прежнему хотят, чтобы обеспечить более некоторый контекст кода в будущем вопросы, как структура данных лучше всего выбирается зная, как это wioll использовать ;-)

PPS: Raymond Hettinger и др. часто оптимизированная реализация CPython с «любовью к деталям» (извините, у меня нет лучшего английского выражения для этого), поэтому ожидайте всегда конкретные развертывания для небольших «размерных» проблем, поэтому разбор проблемы с игрушечным вариантом может существенно различаться от одного, реализованного для огромных задач. Вот почему я часто предпочитаю время и (профильные измерения) по разборке, но мы должны привыкнуть к чтению байтовых кодов, чтобы получить идеи, когда измеренная производительность не оправдает наши ожидания.

В противном случае: Наслаждайтесь разборку поиска :-)

Update: ...и если вы измените заявление приурочено, что маленький ДИКТ geceives хита 'zz' и большой не один (наоборот, чем выше), вы можете также encouter этих timeings:

# Timing[secs] for 1x10000: 0.0533709526062 
# Timing[secs] for 100x10000: 0.0458760261536 

где испытание, если 'zz' in d занимает 53 милли секунд в малых и 46 миллисекунд в больших (в среднем 1000000 испытаний).

Answer 3

Вы можете использовать функцию str.translate для замены символов строки, используя таблицу (в данном случае dict) от ключа до значения.