0

pythonにおいて、
16進文字列に対してビット単位でデータを切り出す関数を実現したいと考えております。
文字列ベースで、進数変換を行い、ビット切り出しをすることはできたのですが、
処理性能やメモリ消費量で課題を感じております。

高速、かつ、低メモリで実装するにはどのような方法で処理するのがよいでしょうか。

■INPUT
 16進文字列    :"01AC"
 切り出し開始バイト:0    ※0始まり
 切り出し開始ビット:4    ※0始まり
 切り出しビット数 :8

■OUTPUT
 切り出されたビット:00011111

■現在の処理実現方法

  1. 16進文字列を整数化            :"01AC" => 428
  2. 処理1をもとに2進文字列に変換        :"0000000110101100"
  3. 処理2に対してsliceで該当ビットの切り出し :"00011010"

■その他
bytesを利用することを考えましたが、
文字エンコードをしたいわけではなく、
値としてそのまま利用したかったため、
利用ケースにはマッチしないと判断しました。

5
  • 1
    入力値の条件、「高速かつ低メモリ」の具体的な目標と現状のベンチマークを質問を編集して追記してください。
    – suzukis
    Commented 2023年11月19日 3:44
  • 3
    現在のコードを提示してください。「処理性能やメモリ消費量で課題を」と言われても、検証が不可能です。
    – hata
    Commented 2023年11月19日 3:45
  • 他のコメントにもあるように, 現在のコード示したほうがよいでしょう。また仕様も不明です。例えば '001' だとどのように解釈するのか, 0x0001 と見なすのか, その場合開始バイト 0とは, 00 の方か (前ゼロ無しで数値としての始まりの) 01 の方か, など
    – oriri
    Commented 2023年11月19日 3:56
  • この辺の記事が類似の話題を扱っているようで参考になるかもしれません。Extract ‘k’ bits from a given position in a number., Python Slicing | Extract ‘k’ bits from a given position, BitManipulation, Bitwise operations on strings Python3.7
    – kunif
    Commented 2023年11月19日 5:02
  • とりあえず入力文字列をそのままスライスにした方がメモリ効率が良くなると思いますよ。それ以外は環境によるし、計測して各入力パラメータの変化に対して、速度とメモリがどう変わるかをロジックごとに全て計測しないといけないと思います。なおCPythonならpythonでロジックを書くよりは、nativeな組み込み関数を使った方が速くなることが多いです。
    – dameo
    Commented 2023年11月19日 7:48

3 件の回答 3

0

以下、[2^13, 2^60) から整数をランダムに 10,000,000 個抽出して計測してみました。実行環境は以下の通りです。

$ grep -E '^model name' /proc/cpuinfo | uniq
model name  : Intel(R) Core(TM) i5-8500T CPU @ 2.10GHz

$ uname -isr
Linux 6.5.0-10-generic x86_64

$ lsb_release -ir
Distributor ID: Ubuntu
Release:    23.10

$ python3 -V
Python 3.11.6

cut_out_bitscut_out_bits2 も同様の処理(文字列処理)ですが、ごく僅かに cut_out_bits の方が速いです。もっとも、実行速度を重視するのであれば Python ではなく、他のプログラミング言語の方を使う方がよいかと思います。

def cut_out_bits(hex_string, offset_bytes, offset_bits, nbits):
    bits = bin(int(hex_string, 16))[2:]
    bits = '0'*((rem:=len(bits)%8) and (8-rem)) + bits
    b = offset_bytes * 8 + offset_bits
    e = b + nbits
    return bits[b:e]

def cut_out_bits_2(hex_string, offset_bytes, offset_bits, nbits):
    v = int(hex_string, 16)
    w = (v.bit_length() + 7) // 8 * 8
    bits = format(v, f'0{w}b')
    b = offset_bytes * 8 + offset_bits
    e = b + nbits
    return bits[b:e]

if __name__ == '__main__':
    import random
    import timeit
    from pprint import pprint

    hex_strings = [hex(i)[2:] for i in random.sample(range(2**13, 2**60), k=10_000_000)]
    def apply(func, hex_strings):
        for h in hex_strings:
            func(h, 0, 4, 8)

    result = timeit.repeat('apply(cut_out_bits, hex_strings)', globals=globals(), number=1)
    pprint(result)
    result = timeit.repeat('apply(cut_out_bits_2, hex_strings)', globals=globals(), number=1)
    pprint(result)

# cut_out_bits
# [5.886475351173431,
#  5.877643479034305,
#  5.87063645105809,
#  5.877712128916755,
#  5.881971047958359]
# 
# cut_out_bits2
# [6.823900946881622,
#  6.91018356801942,
#  6.978068734984845,
#  6.980364801129326,
#  6.996410653926432]
3
  • 多分私の書いたコメントに反応したんだと思うのでコメントしておくと、入力文字列はKB長とかMB長のものを想定していて、あのようなコメントをしました。ようは処理対象の文字列が長くなればなるほど、抽出処理を先にした方が良いよというだけの話です。
    – dameo
    Commented 2023年11月19日 9:03
  • コメントや他の回答は読んでいませんので……
    – metropolis
    Commented 2023年11月19日 9:07
  • そうなんですね。了解です。
    – dameo
    Commented 2023年11月19日 9:25
-1

数値にしたあとビットごとの論理演算すればそれですみます
C言語であれば、

kekka = suu & 0x001f;

てことになろうかと。

#質問文がいまいち意味不明ですが

-1

回答ではありません

コメントに書いた入力文字列を直にスライスした例です。

def hexstr2binstr(hexstr: str, bit_start: int, bit_length: int):
    bit_end = bit_start + bit_length
    char_start = bit_start >> 2
    bit_start &= 3
    char_end = (bit_end + 3)>> 2
    bit_end &= 3
    hexstr = hexstr[char_start:char_end]
    hexstr = '0' + hexstr if (char_end - char_start) & 1 == 1 else hexstr
    number = int.from_bytes(bytes.fromhex(hexstr), 'big')
    number >>= (4 - bit_end) & 3
    number &= (1 << bit_length) - 1
    return format(number, 'b').zfill(bit_length)

print(hexstr2binstr("01AC", 4, 8))
# 00011010

毎回書いてる気がしますが、マイナス評価をするなら、理由を明快にしてください。
理由がなければ記述修正のしようがありません。私から返事をしないことはなく、私から通報したりしないので、削除に至って経緯が分からなくなることもありません。

もし(毎度自分ではないと言いながら毎回同じ)コメントを頂くnekketsuさんのように、

回答ではありません

が理由なのであれば同じ寿命を持つ代替手段を用意しましょう。

何度も書いているのに伝わらないので不毛ですが、

コメントにコードが付記できないこのサイトの仕様の問題

であり、回答欄利用はただの回避策でしかありません。また私はただの利用者なので、Metaに移動してこのサイトの問題に関わるような、無駄な時間を使いたくもありません


metropolisさんのコードを元に多少調べたところ、変換効率は古い形の方が良いようなので、そちらに合わせてみました。調査用のコードを載せておきます。環境も自動出力されるので、多少動かしやすいです。

def cut_out_bits(hex_string, offset_bytes, offset_bits, nbits):
    bits = bin(int(hex_string, 16))[2:]
    bits = '0'*((rem:=len(bits)%8) and (8-rem)) + bits
    b = offset_bytes * 8 + offset_bits
    e = b + nbits
    return bits[b:e]

def cut_out_bits_2(hex_string, offset_bytes, offset_bits, nbits):
    v = int(hex_string, 16)
    w = (v.bit_length() + 7) // 8 * 8
    bits = format(v, f'0{w}b')
    b = offset_bytes * 8 + offset_bits
    e = b + nbits
    return bits[b:e]

def cut_out_bits_dameo(hexstr, byte_start, bit_start, bit_length):
    bit_start += byte_start << 3
    bit_end = bit_start + bit_length
    char_start = bit_start >> 2
    bit_start &= 3
    char_end = (bit_end + 3)>> 2
    bit_end &= 3
    hexstr = hexstr[char_start:char_end]
    number = int(hexstr, 16)
    number >>= (4 - bit_end) & 3
    number &= (1 << bit_length) - 1
    return format(number, 'b').zfill(bit_length)

if __name__ == '__main__':
    #print(cut_out_bits_dameo('01AC', 0, 4, 8))
    #print(cut_out_bits_dameo('01AC', 0, 3, 8))
    #print(cut_out_bits_dameo('01AC', 0, 3, 7))
    #print(cut_out_bits_dameo('01AC', 0, 3, 9))
    #print(cut_out_bits_dameo('01AC', 1, 3, 9))
    import random
    import timeit
    from pprint import pprint
    import re
    import platform
    import subprocess
    import gc
    if platform.system() == 'Linux':
        import resource

    #hex_strings = ['00'*1024 + hex(i)[2:] for i in random.sample(range(2**13, 2**60), k=100_000)]
    hex_strings = [hex(i)[2:] for i in random.sample(range(2**13, 2**60), k=100_000)]

    def apply(func, hex_strings):
        for h in hex_strings:
            func(h, 0, 4, 8)

    print('platform: ' + re.sub("(?<=node=')[^']*(?=')", '(secret)', str(platform.uname())))
    print(f'python: {platform.python_version()}({platform.python_implementation()})')
    if platform.system() == 'Linux':
        subprocess.run("cat /proc/cpuinfo | grep -E 'model name|Hardware' | head -1", shell=True)

    for f in [cut_out_bits, cut_out_bits_2, cut_out_bits_dameo]:
        print(f'{f.__name__}:')
        gc.collect()
        result = timeit.repeat('apply(f, hex_strings)', globals=globals(), number=1)
        pprint(result)
        if platform.system() == 'Linux':
            print(f'maxrss: {resource.getrusage(resource.RUSAGE_SELF).ru_maxrss}')

出力例1)

platform: uname_result(system='Linux', node='(secret)', release='5.4.0-166-generic', version='#183-Ubuntu SMP Mon Oct 2 11:28:33 UTC 2023', machine='x86_64')
python: 3.12.0(CPython)
model name      : AMD Ryzen 5 1400 Quad-Core Processor
cut_out_bits:
[0.10711397799605038,
 0.10440667600050801,
 0.10588842300057877,
 0.1049301109960652,
 0.10589057600009255]
maxrss: 37444
cut_out_bits_2:
[0.1255985719981254,
 0.12540653299947735,
 0.12455804500496015,
 0.12410445700515993,
 0.1246860809987993]
maxrss: 37444
cut_out_bits_dameo:
[0.0949812360049691,
 0.09481637700082501,
 0.09427214299648767,
 0.09485356300137937,
 0.09463742200023262]
maxrss: 37444

出力例2)

platform: uname_result(system='Linux', node='(secret)', release='5.4.0-166-generic', version='#183-Ubuntu SMP Mon Oct 2 11:28:33 UTC 2023', machine='x86_64')
python: 3.10.13(PyPy)
model name      : AMD Ryzen 5 1400 Quad-Core Processor
cut_out_bits:
[0.11100042500038398,
 0.0960047550033778,
 0.0952699890040094,
 0.10096091699961107,
 0.09546179300377844,
 0.09636991799925454,
 0.09681477599951904]
maxrss: 85784
cut_out_bits_2:
[0.12166648599668406,
 0.10946445100125857,
 0.11415980899619171,
 0.10995085700415075,
 0.10962170299899299,
 0.1089542249974329,
 0.10933569900225848]
maxrss: 85784
cut_out_bits_dameo:
[0.03335564000008162,
 0.02236169999378035,
 0.021013475001382176,
 0.02122562799922889,
 0.021220968999841716,
 0.021201859002758283,
 0.021020799002144486]
maxrss: 85784

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。