TAoCP 6.1 Sequential Searchingシーケンスルックアップアルゴリズムの実装

p.396アルゴリズムS
 
人類史上最も簡単で最も直感的で効率の低い検索アルゴリズムである.
 

# coding: utf-8

"""
   S

   lst      key 。
"""
def sequential_search(key, lst):
    n = len(lst)

    i = 0 
    while (i < n): 
        if lst[i] == key:
            return i
        else:
            i += 1

    return None

if __name__ == "__name__":
    l = [5,2,1,3,6,9]

    assert sequential_search(3, l) == 3
    assert sequential_search(7, l) is None

 
 
p.396アルゴリズムQ
 
Qアルゴリズムはkeyをリストの末尾に追加し,比較iにより探索が成功したか否かを判断し,Sアルゴリズムより内ループ判定の回数を減らした.
 

# coding: utf-8

"""
   Q

  key     lst    ，   i          。
"""
def quick_sequential_search(key, lst):
    n = len(lst)

    lst.append(key)
    new_n = len(lst)

    i = 0 
    while (i < new_n):
        if lst[i] != key:
            i += 1
        else:   
            break

    if i < n:
        return i
    else:
        return None

if __name__ == "__main__":
    l = [5,2,1,3,6,9]

    assert quick_sequential_search(3, l) == 3
    assert quick_sequential_search(7, l) is None

 
 
p.398アルゴリズムQ'
 
Q'アルゴリズムはQアルゴリズムから改良され、主に2をステップ成長iとし、keyとlst[i]、lst[i+1]の2つの要素を比較するたびに、i+=1の実行時間を半分節約した.
もちろん、リストの長さは偶数(%2==0)であっても奇数(%2!=0)であってもよいので、奇数の場合には注意が必要である.
 

# coding: utf-8

"""
   Q'

  2       i ，    key   lst[i] 、 lst[i+1]   。
   len(lst)     2   ，        lst[0] 。
"""
def quicker_sequential_search(key, lst):
    n = len(lst)
    i = 0 

    if n % 2 != 0:
        if lst[0] == key:
            return 0
        else:
            i += 1
    
    lst.append(key)
    while i < n:    
        if lst[i] == key:
            return i
        elif lst[i+1] == key:
            return i+1 if i+1 < n else None
        else:
            i +=2 

if __name__ == "__main__":
    # len(l) % 2 != 0
    l = [5,2,6,3,1]
    assert quicker_sequential_search(6, l) == 2
    assert quicker_sequential_search(7, l) is None

    # len(another) % 2 == 0
    another = [5,2,6,3,1,0]
    assert quicker_sequential_search(6, another) == 2
    assert quicker_sequential_search(7, another) is None

 
 
p.398アルゴリズムT
 
アルゴリズムTは、最も単純(最も非効率)な並べ替えリストの検索アルゴリズムである.
 

# coding: utf-8

"""
   T

   (       )             。
"""
def sequential_search_in_ordered_table(key, lst):
    assert sorted(lst) == lst 

    n = len(lst)
    i = 0 
    while i < n:
        if key <= lst[i]:
            return i if key == lst[i] else None
        else:
            i += 1

if __name__ == "__main__":
    l = [1, 2, 3, 5, 6]

    assert sequential_search_in_ordered_table(3, l) == 2
    assert sequential_search_in_ordered_table(4, l) is None
    assert sequential_search_in_ordered_table(10, l) is None

 
今から見れば、Sアルゴリズムだけが比較的簡単な場合に使用され、一般的には、比較的大きなリストを並べ替えてから検索したり、ツリーやハッシュテーブルなどの他のデータ構造を使用して処理したりしても、より効率的になります.
 
QとQ'アルゴリズムは実現が複雑で、エラーが発生しやすく、効果が著しくなく、薄くするための成分が大きい.