二分探索,ヒストグラム


プログラム


  1. 簡単な探索プログラム

    def find_linear(data,name):       # 配列dataからnameを発見
      for i in range(0, len(data)):
        if (data[i] == name):         # 見つけた!
          return True
      return False                    # 見つからなかった
    
  2. 二分探索プログラム

    def find_bisection(data, name):   # 整列済み配列 data から name を発見。
      start = 0                       # 左端
      end = len(data) - 1             # 右端
      while start != end:
        center = (start + end) // 2
        if data[center] == name:
          return True                 # 見つけた
        if name < data[center]:
          end = center                # 中央より左にある
        else:
          start = center + 1          # 中央より右にある
      return False                    # 見つからなかった
    
  3. ヒストグラム作成プログラム

    def histogram(data):             # dataのヒストグラムを作成
      result = []                    # 結果格納用
      for i in range(0, len(data)):
        put_item(result, data[i])    # 各要素の個数を増やす
      return result
    
    def put_item(res, item):         # 各要素の個数を増やす
      for i in range(0, len(res)):
        if res[i][0] == item:        # その要素を発見
          res[i][1] = res[i][1] + 1
          return                     # その要素の個数を増やして終了
      res.append([item, 1])          # その要素が見つからなかったので新たに作る
    
  4. 整列済みの場合のヒストグラム

    def histogram_sorted(data):      # 整列済み配列dataのヒストグラム
      result = []
      item = data[0]                 # 現在数えている商品
      c = 1                          # 現在数えている商品の個数
      for i in range(1, len(data)):
        if item == data[i]:          # 隣と同じ
          c = c + 1
        else:                        # 新しい商品を発見
          result.append([item, c])
          c = 1
          item = data[i]
      result.append([item, c])
      return result
    
  5. 出現回数上位 n 件

    def to_histogram(data, n):    # data のヒストグラムの出現回数上位 n 件
      h = histogram(data)         # ヒストグラムを取得
      h.sort(key=cmp)             # 出現回数が多い順に整列
      return h[0 : n]
    
    def cmp(kv):
      return -kv[1]               # 出現回数をマイナスにして出力
    

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