質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.50%

  • Python 3.x

    9865questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

  • AWS Lambda

    129questions

6桁の「1」と「0」のフラグ置換処理の速度を改善させたい

解決済

回答 3

投稿

  • 評価
  • クリップ 3
  • VIEW 507

Otazoman

score 29

前提・実現したいこと

6桁の1と0のフラグがあって、そのフラグを返却する関数を作成しています。

・フラグが「101100」の場合→関数からの戻り値は「101100」
・フラグが「210110」の場合→関数からの戻り値は「110110」と「0110110」

関数に2が渡された場合はその2を「1」と「0」に置きかえて返すものです。
ひとまず機能は何とか実現できたのですが、ループで処理しているのでフラグが「222222」の様に
すべて「2」で指定された場合の処理時間がかかってしまうため実用に耐えません。
改善策を色々と調べてみましたがこれというアイデアがないため困っております。
どうかお知恵を拝借できますでしょうか。

該当のソースコード

現在のやり方は
1.渡された6桁のフラグを2桁ずつに分解する。
2.2桁に分けたフラグを判定させて新たなフラグを生成する。
例:「22」→「00,10,11,01」
もとのフラグが10の場合は10のままとする。
3.3つに分解したフラグを結合する。
4.付加キーを付加する。

def make_search_key(companycode,searchkey):
  try:
    result=[]
    wh='2'
    afk=[] 
    sm=''
    sb=''
    if searchkey: 
      sf=searchkey[:6]
      #桁ずれ処理
      if searchkey[6:9] == '100':
         sm=searchkey[6:9]
         sb=searchkey[9:10]
      else:
         sm=searchkey[6:8]
         sb=searchkey[8:10]
      mf = wh in sf
      addkey = ['0','1','01','11','001','011','101','111']
      if mf:
         kv1=[]
         kv2=[]
         kv3=[]
         #先頭2桁
         s1=sf[0:2]
         if s1 == '02':
              kv1=['00','01']
         elif s1 == '12':
              kv1=['10','11']
         elif s1 == '20':
              kv1=['00','10'] 
         elif s1 == '21':
              kv1=['01','11']
         elif s1 == '22':
              kv1=['00','01','10','11']
         else:
              kv1=[s1]
         #中間2桁
         s2=sf[2:4]
         if s2 == '02':
              kv2=['00','01']
         elif s2 == '12':
              kv2=['10','11']
         elif s2 == '20':
              kv2=['00','10'] 
         elif s2 == '21':
              kv2=['01','11']
         elif s2 == '22':
              kv2=['00','01','10','11']
         else:
              kv2=[s2]
         #後ろ2桁
         s3=sf[4:6]
         if s3 == '02':
              kv3=['00','01']
         elif s3 == '12':
              kv3=['10','11']
         elif s3 == '20':
              kv3=['00','10'] 
         elif s3 == '21':
              kv3=['01','11']
         elif s3 == '22':
              kv3=['00','01','10','11']
         else:
              kv3=[s3]

         print("s1:{0}".format(kv1))
         print("s2:{0}".format(kv2))
         print("s3:{0}".format(kv3))

         start = time.time()

         afk=[ i+j+k for i in kv1 for j in kv2  for k in kv3 ]

         elapsed_time = time.time() - start
         print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

      if afk:
         result = [ i+sm+j for i in afk for j in addkey ]
    return result
  except Exception as e:
    print(e)
    raise e

試したこと

処理速度(できれば1秒程度に短縮させたい。)
・3つのうち1つだけに2が1つだけ指定された場合→3秒程度
・3つともに2が1つだけ入っている場合→10秒程度
・全体に2が指定された場合→30秒程度

6桁を合体させた状態でループを減らす様にしてみましたが、やはり「222222」で32パターン程の
フラグを生成することとなり、付加キーを付け加える箇所でパフォーマンスが劣化していました。
そのため速度は改善できませんでした。

CPUの性能を上げれば多少は改善するかと思ってLambdaのスペックを128MBから256MBにしてみたりも
しましたが速度改善はありませんでした。

補足情報(FW/ツールのバージョンなど)

AWS/Lambda
python3.7

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • hayataka2049

    2019/05/14 20:31

    試してみましたが、極めて高速に実行できます。また、質問文に書かれている仕様と異なっている気がします。
    None, "101100"を渡す→空リストが返る
    None, "210110"を渡す→長さ512のリストが返る
    仕様を明確にじてください。また、遅いのはこの部分ではなく、他の部分が原因なのでは?

    キャンセル

  • yayakona

    2019/05/14 22:57

    コードが文章と合っていない気がしてしまうのですが、一旦無視します。
    (6桁以外の文字列が返ってくるのは仕様ですか?)

    実際に実行してみると爆速だったため確認して見たいことがあります。

    私のしょぼい環境でsearchkey="222222"で実行すると

    elapsed_time:2.6226043701171875e-05[sec]

    と出力されました。

    これを2.6秒と読んでいませんか?
    2.6×10の-5乗[秒]のはずなので早いと思います。

    間違っていればごめんなさい。

    キャンセル

  • Otazoman

    2019/05/15 13:23

    >また、質問文に書かれている仕様と異なっている気がします。
    if afk:のelse部分が漏れていました。なのでNoneが返ってしまっています。申し訳ありません。
    >elapsed_time:2.6226043701171875e-05[sec]
    >これを2.6秒と読んでいませんか?
    >2.6×10の-5乗[秒]のはずなので早いと思います。
    2.6秒で読んでおりました。すいません。

    キャンセル

回答 3

+2

変換部をワンライナーで書いてみました(itertoolsを使用してますが)

from itertools import product

target = '00222200'

ret = [target.replace('2','{}').format(*d) for d in product(*[['0','1']]*target.count('2'))]
#['00000000', '00000100', '00001000', '00001100', '00010000', '00010100', '00011000', '00011100', '00100000', '00100100', '00101000', '00101100', '00110000', '00110100', '00111000', '00111100']

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/15 17:58

    1行で行けるのですね。目から鱗です。
    pythonまだまだ分からない点がありますが頑張っていきたいと思います。
    これからもよろしくお願いいたします。

    キャンセル

checkベストアンサー

+1

関数に2が渡された場合はその2を「1」と「0」に置きかえて返すものです。

任意桁に拡張してみました。当方環境では'2222222222'などでも一瞬で計算が終わります。

def make_key(key,lst):

    if not key:
        return lst

    if key[0] == '2':
        if not lst:
            lst.append('0')
            lst.append('1')
        else:
            lst0,lst1 = lst[:],lst[:]
            for i in range(len(lst)):
                lst0[i] += '0'
                lst1[i] += '1'
            lst = lst0 + lst1
    else:
        if not lst:
            lst.append(key[0])
        else:
            for i in range(len(lst)):
                lst[i] += key[0]

    return make_key(key[1:],lst)

print( make_key('101100',[])) # ['101100']
print( make_key('210110',[])) # ['010110', '110110']


なお、提示コードも処理自体にそこまで時間がかかるとは考えにくいです。
ネットワークI/Oなど他の処理に時間がかかっている可能性があります。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/15 17:56

    ご回答ありがとうございました。拡張性の部分が非常に参考になりました。
    もう一度計測してみたのですが、該当の処理箇所自体は以下の様な感じでした。
    処理時間:0.00012135505676269531秒とほぼほぼ影響ない範囲でした。

    別の箇所を計測してみると1秒程度を要している箇所がありそこがネックとなっているようなので
    その箇所について少し突っ込んで確認してみます。
    せっかくご教示いただきましたがその箇所が問題個所ではありませんでした。反省です。

    将来的な拡張を考えるとこちらの実装の方が断然いいのでベストアンサーとさせていただきます。

    キャンセル

  • 2019/05/15 19:06

    補足です。原因分かりました。

    LambdaからDynamoDBを呼び出す際に上記のフラグを検索に使用しているのですが
    222222を指定するとテーブルに存在しないキーまで検索に行ってしまっていて不要な検索に
    処理時間を要しているようです。2222の4桁までであればまだ数千の検索なので許容範囲なのですが
    222222となると数万単位でヒットしないものの検索まで行っていてそれが原因で処理に時間がかかっていたようです。

    1.フラグの中で検索可能フラグ判定ロジックを間に噛ませて検索を制御する。
    2.222222の中でありえない禁止のキーの組み合わせを入れておいてそのフラグは返さないようにする。

    恐らく、今回は1のロジックで回避せざるを得ないかと考えております。
    ご協力ありがとうございました。

    キャンセル

  • 2019/05/15 19:12

    なるほど、別処理に原因あったのですね。
    コメントありがとうございます。
    原因分かりスッキリしました。

    キャンセル

+1

計算量からそれほど負荷になるような演算じゃないとは思うので、単なる思いつき程度ですが、あらかじめdictのリテラルを↓こんなテキトーなんでいいはずなんでローカルで生成して、その辞書から値を引いて使うのはだめですかね?
(パッケージサイズは解凍後サイズで250MBまでらしいんで、空きがあればってことで)

def somefunc(a):
  return [i + j for i in charToList(a[0]) for j in charToList(a[1])]

def charToList(n):
    if(n == "0" or n == "1"):
      return [n]
    return ["0","1"]

print('{' + ",".join(['"'+str(i)+str(j)+'":["'+ '","'.join(somefunc(str(i)+str(j)))+'"]' for i in range(3) for j in range(3) if 2 in [i, j]]) + '}')

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/15 17:57

    ありがとうございます。関数を呼び出している元の箇所の時間を計測するとネックとなる箇所が
    見えてきたのでそちらを確認してみます。

    キャンセル

同じタグがついた質問を見る

  • Python 3.x

    9865questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

  • AWS Lambda

    129questions