単純整列法,併合整列法,さまざまなデータ構造


プログラム


  1. 単純整列法

    def simplesort(a):
      for i in range(0, len(a)):
        j = min_index(a, i)        # i より右で最小の値の位置を調べる
        swap(a, i, j)              # i 番目の値を最小の値と入れ替える
      return a
    
    def min_index(a, i):
      min = a[i]
      index = i
      for i in range(i + 1, len(a)):
        if a[i] < min:
          min = a[i]
          index = i
      return index
    
    def swap(a, i, j):
      tmp = a[i]
      a[i] = a[j]
      a[j] = tmp
    
  2. 併合整列法

    def mergesort(a):                        # 配列 a を整列
      n = len(a)
      if n <= 1:                             # 短いときはそれでよし
        return a
      else: 
        l = mergesort(a[0 : n//2])           # 前半と後半をそれぞれ整列
        r = mergesort(a[n//2 : n])
        return merge(l, r)                   # 整列した結果を併合
    
    def merge(a,b):                          # 整列済みの配列aとbを併合
      r = ita.array.make1d(len(a) + len(b))  # 結果の格納先を用意
      ai = 0                                 # aは何番目まで処理したか?
      bi = 0                                 # bは何番目まで処理したか?
      for i in range(0, len(r)):
        if (bi >= len(b) or 
            (ai < len(a) and a[ai] < b[bi])): 
            # a と b の先頭を比較 (長さを超えないよう注意)
          r[i] = a[ai]
          ai = ai + 1
        else: 
          r[i] = b[bi]
          bi = bi + 1                        # a と b の先頭の小さい方を r へ
      return r
    
  3. 辞書を使ったヒストグラム

    def histogram_dict(data):                # 辞書を利用するヒストグラム
      result = {}                            # 結果格納用の辞書
      for i in range(0, len(data)):
        item = data[i]
        if item in result:                   # 既知の商品
          result[item] = result[item] + 1
        else:                                # 未知の商品
          result[item] = 1
      return result
    
  4. n-gramを求めるプログラム

    def ngram(s, n):            # 文字列 s に対する n-gram を求める
      m = len(s)
      result = {}               # 結果格納用の辞書
      s = s + '$' * n           # 末尾に $ を付加
      for i in range(0, m):
        result[s[i: i+ n]] = i  # s のi文字目からn文字はi文字目から始まる
      return result
    
  5. n-gram から検索するプログラム

    def ng_search(s, ngram, n, query):        # 文字列 s の n-gram データ ngram から query を発見
      nq = (query + '$' * n)[0 : n]           # query の先頭 n 文字.末尾には $ を付加
      if nq in ngram:
        idx = ngram[nq]                       # idx 文字目からが候補
        if s[idx: idx+ len(query)] == query:  # idx 文字目からが実際に query と一致
          return idx
      return -1                               # 見つからなかった
    

2021年12月19日作成
伊知地 宏
Copyright (C) Hiroshi Ichiji, 2021. All rights reserved.