今回はPythonの標準ライブラリで提供されている、array.arrayについて使いどころを書きました。

array.arrayの使い方

まず、公式の解説をみてみましょう。

このモジュールでは、基本的な値 (文字、整数、浮動小数点数) のアレイ (array、配列) をコンパクトに表現できるオブジェクト型を定義しています。アレイはシーケンス (sequence) 型であり、中に入れるオブジェクトの型に制限があることを除けば、リストとまったく同じように振る舞います。

array --- 効率のよい数値アレイ

「中に入れるオブジェクトの型に制限があることを除けば、リストとまったく同じように振る舞います。」と書いてある通り、使い方は、ほぼリストと同じです。初期化する際には型を指定します。

試しに値も追加してみましょう。

import array

# 数値型の空の配列を初期化
arr = array.array('i', [])
# 値を加える。
arr.append(1)
print(arr)

array('i', [1])

型が違う値を加えようとすると、エラーになります。

arr.append('hoge')

TypeError: an integer is required (got type str)

次に要素の削除です。リストと同様にpop()メソッドを使います。

# 次の数字を加える
arr.append(2)
arr.append(3)
print('加えた後')
print(arr)
# 二番目の数字を削除
arr.pop(1)
print('削除した後')
print(arr)

加えた後
array('i', [1, 2, 3])
削除した後
array('i', [1, 3])

挿入するときもリストと同様にinsert()メソッドを使います。

# 二番目に100を挿入
arr.insert(1, 100)
print(arr)

# 二番目に100を挿入
arr.insert(1, 100)
print(arr)

array('i', [1, 100, 3])

他にもlen(arr)としますと要素の長さが取得できますし、arr.count(1)としますと、要素の中の数を数えることができます。

型が制限されていることを除けば大体リストと同じです。

使いどころ

できることはリストと大体同じなんですが、リストよりもメモリ効率が良く、高速アクセスが可能な点に魅力があります。

具体的にはpop()とinsert()の速度が明らかに違います。

要素数100万の配列に対して１万回ずつpop()とinsert()を繰り返してみます。

import array
import time

a_list = [i for i in range(1000000)]

s = time.time()
for i in range(10000):
    a_list.pop(500000)
    a_list.insert(500000, 500000)
print('list：', time.time() - s)

arr = array.array('i', a_list)

s = time.time()
for i in range(10000):
    arr.pop(500000)
    arr.insert(500000, 500000)
print('array：', time.time() - s)

list： 5.113029718399048
array： 2.0941877365112305

arrayの方が顕著に速いです。

詳細は不明ですが、リストではそれぞれ線形で時間がかかるのに対して、arrayでは対数時間で処理しているような感じがあります。

これができると何が嬉しいかというと、bisect_leftモジュールなどと組み合わると、高速に順序付きの配列を保持することができます。

import array
from bisect import bisect_left

# 1から30までの奇数の配列
a_list = [i for i in range(30) if i % 2 == 1]

arr = array.array('i', a_list)
print('挿入前')
print(arr)
# 6を5の後に挿入する
index = bisect_left(arr, 6)
# 通常リストだとここに時間がかかるのがネック！arrだと速い
arr.insert(index, 6)
print('挿入後')
print(arr)

挿入前
array('i', [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29])
挿入後
array('i', [1, 3, 5, 6, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29])

30程度などの配列だとそんなに違いは感じませんが、サイズが大きくなるとパフォーマンスに影響します。

競プロなどでの活用

競プロなどではこの辺の実装を知らないと解けない問題が出たりします。

典型的な問題としては競技プログラミングの鉄則で紹介されているこちらでしょうか。

A55 - Set

以下の3 種類のクエリを高速に処理するプログラムを実装してください。

クエリ 1：x と書かれたカードが机に置かれる。

クエリ 2：x と書かれたカードが机から除去される。

クエリ 3：机にある x 以上のカードのうち最小のものを答える。

ただし、最初の時点では机の上に 1 個もカードが置かれていないものとします。

カードの追加と削除をする際にうまく順序を保つことが要件です。

C++などでは順序付きの集合が用意されていますが、Pythonにはないです。

こういう時にarrayとbisect_leftを組み合わせて管理します。

import array
from bisect import bisect_left

q = int(input())
arr = array.array('i', [])
for _ in range(q):
    t, x = map(int, input().split())
    if t == 1:
        idx = bisect_left(arr, x)
        arr.insert(idx, x)
    elif t == 2:
        idx = bisect_left(arr, x)
        arr.pop(idx)
    else:
        idx = bisect_left(arr, x)
        if idx == len(arr):
            print(-1)
        else:
            print(arr[idx])

おわりに

一般的な配列管理ではリストでほぼ事足りるかと思います。

しかし、値の順序を保持して配列を更新する必要がある際は、array.arrayを使うと高速で良いです。