다른 키의 부분 문자열 인 사전에서 키를 제거하는 기능 수행

Question

코드에서 줄을 제거하면 성능이 크게 향상되는 이유가 궁금합니다. 함수 자체는 사전을 가져와 다른 키의 하위 문자열 인 모든 키를 제거합니다. IS 아래로 내 코드를 느리게

라인 :

if sub in reduced_dict and sub2 in reduced_dict: 

여기 내 함수의 : 서브 SUB2 여러 번에있는 경우

def reduced(dictionary): 
    reduced_dict = dictionary.copy() 
    len_dict = defaultdict(list) 
    for key in dictionary: 
     len_dict[len(key)].append(key) 
    start_time = time.time() 
    for key, subs in len_dict.items(): 
     for key2, subs2 in len_dict.items(): 
      if key2 > key: 
       for sub in subs: 
        for sub2 in subs2: 
         if sub in reduced_dict and sub2 in reduced_dict: # Removing this line gives a significant performance boost 
          if sub in sub2: 
           reduced_dict.pop(sub, 0) 
    print time.time() - start_time 
    return reduced_dict 

기능 검사가. 나는이 비교가 이미 이루어 졌는지를 확인하면 시간을 절약 할 수 있다고 생각했다. 이것은 사실이 아닌 것 같습니다. 왜 사전에서 조회를위한 일정 시간 함수가 나를 감속 시키는가?

저는 초보자입니다. 개념에 관심이 있습니다.

문제의 줄이 False를 반환하는지 테스트했을 때 그 줄이 나타납니다.

• 19.6360001564 초 : 나는 함수의 입력 사전에 14,805 키를 들어 다음과 같은

  def reduced(dictionary): 
      reduced_dict = dictionary.copy() 
      len_dict = defaultdict(list) 
      for key in dictionary: 
       len_dict[len(key)].append(key) 
      start_time = time.time() 
      for key, subs in len_dict.items(): 
       for key2, subs2 in len_dict.items(): 
        if key2 > key: 
         for sub in subs: 
          for sub2 in subs2: 
           if sub not in reduced_dict or sub2 not in reduced_dict: 
            print 'not present' # This line prints many thousands of times 
           if sub in sub2: 
            reduced_dict.pop(sub, 0) 
      print time.time() - start_time 
      return reduced_dict 
  

  이것을 테스트했습니다. 라인이없는 경우

• 33.1449999809 초 줄을 가지고

다음은 3 가지 사전 예제입니다. Biggest sample dictionary with 14805 keys, medium sample dictionary 및 smaller sample dictionary

I가 가장 큰 예를 사전에 제 14,000 키에 대한 키 (X)의 #의 입력 크기 VS 초 (Y)에있는 시간 그래프. 이 모든 함수는 지수 적으로 복잡합니다. 이 질문에

매트 사전 을 비교 한

Matt exponential이없는이 질문에 대한 나의 알고리즘

• 존 Zwinck answer이 문제에 나의 첫 번째 시도에서입니다. 이것은 76s를 가지고 갔다
• 매트이 비교를위한이 질문에있는 알고리즘은 dict 비교 라인
• tdelaney solution이 질문에 대한 알고리즘이다. 관련 질문의 순서 알고리즘 1 & 2
• 게오르그 solution 내가 허용 대답은 분명히 선형 시간에 실행

물었다. 나는 마법 비율을 찾을 수 놀랐어요

입력 크기에 존재하는 곳에 DICT 룩업 == 문자열 검색 실행 시간.

Answer 1

, 그것은 훨씬 더 빨리 모든 가능한을 테스트 할 수 있어요 하위 키 :

def reduced(dictionary): 
    keys = set(dictionary.iterkeys()) 
    subkeys = set() 
    for key in keys: 
     for n in range(1, len(key)): 
      for i in range(len(key) + 1 - n): 
       subkey = key[i:i+n] 
       if subkey in keys: 
        subkeys.add(subkey) 

    return {k: v 
      for (k, v) in dictionary.iteritems() 
      if k not in subkeys} 

내 시스템 (i7-3720QM 2.6GHz)에서 약 0.2 초 걸립니다.

Answer 2

len_dict를 만들지 만 같은 크기의 키를 그룹화하더라도 비교할 때 여러 번 모두 트래버스해야합니다. 기본 계획은 옳습니다. 크기별로 정렬하고 같은 크기 이상을 비교하는 것뿐입니다.하지만 다른 방법이 있습니다. 아래에서는 키 크기별로 정렬 된 일반 목록을 만든 다음 역순으로 반복하여 내가 간략하게 내용을 다듬을 수 있도록했습니다. 그 실행 시간이 당신과 얼마나 비교되는지 궁금합니다. 작은 dict 예제를 .049 초 내에 만들었습니다.

(나는 그것이 실제로 일을 바랍니다!)

def myfilter(d): 
    items = d.items() 
    items.sort(key=lambda x: len(x[0])) 
    for i in range(len(items)-2,-1,-1): 
     k = items[i][0] 
     for k_fwd,v_fwd in items[i+1:]: 
      if k in k_fwd: 
       del items[i] 
       break 
    return dict(items) 

편집 몇 번을 모두 실행 한 후 k_fwd, v_fwd을 (개봉하지 않음으로써 상당한 속도 증가, 이건 정말 아니었다

속도 향상. 뭔가 다른 PC에서 잠시 동안 먹고 있어야합니다).

def myfilter(d): 
    items = d.items() 
    items.sort(key=lambda x: len(x[0])) 
    for i in range(len(items)-2,-1,-1): 
     k = items[i][0] 
     for kv_fwd in items[i+1:]: 
      if k in kv_fwd[0]: 
       del items[i] 
       break 
    return dict(items) 

Answer 3

나는 약간 다르게 할 것입니다. 다음은 "좋은"키만을 제공하는 생성기 기능입니다. 이렇게하면 키별로 크게 손상 될 수있는 사전을 만들지 않습니다. 또한 "for"루프와 두 가지 간단한 최적화를 통해 일치 항목을보다 빨리 찾고 불가능한 일치 항목을 검색하지 않아도됩니다.

def reduced_keys(dictionary): 
    keys = dictionary.keys() 
    keys.sort(key=len, reverse=True) # longest first for max hit chance                          
    for key1 in keys: 
     found_in_key2 = False 
     for key2 in keys: 
      if len(key2) <= len(key1): # no more keys are long enough to match                        
       break 
      if key1 in key2: 
       found_in_key2 = True 
       break 
     if not found_in_key2: 
      yield key1 

이를 사용하여 실제 딕셔너리를 확인하려면

수행 할 수 있습니다

샘플 신체, 또는 가장 키가 작은하는 모든 코퍼스를 들어

{ key: d[key] for key in reduced_keys(d) }