0

今、[[10,20,30],[1,2,3],[5,3,8],[11,2,3]]のように、3つの数字のリストが複数あります。
これを規則に沿って並び替えたいです。

sort_method = [3,-1,2]のような規則をリストとして持たせたい場合
これは、リスト内の3番目の数字を1つ目に移動させ、1番目の数字の正負を反転した後に2つ目に移動、2番目の数字を3つ目に移動させることを意味しています。

日本語で説明するのは、やや難しいので、以下のコードを見てください。

numberListList = [[10,20,30],[1,2,3],[5,3,8],[11,2,3]]

sort_method = [3,-1,2]

numberListList_new = []

for numberList in numberListList:
    numberList_new = []
    
    for method in sort_method:
        number = numberList[abs(method)-1]
        if method < 0:
            number = -number
        numberList_new.append(number)
    
    numberListList_new.append(numberList_new)
    
print(numberListList_new)

このコードを実行すると、[[30, -10, 20], [3, -1, 2], [8, -5, 3], [3, -11, 2]]というリストが生成され、printされます。

この出力結果は私が望んだとおりのものではあるのですが、コードがあまりよくないのではないかと感じています。
現在、処理速度を少しでも速くしたいと考えており、このコードは速いかどうかという点に疑問があります。

もっと効率よく、処理速度を速めて処理負荷を減らすためにはどのような方法はありますでしょうか?
必ずしも、sort_methodは今のようなリストの形ではなくても構いません。
並び替える順番と、正負の反転の情報が分かるような方法であれば構いません。

このサンプルコードはPythonで記述しましたが、本番環境ではPython以外の言語で記述するつもりなので、なるべく他言語でも使用できるようなアルゴリズムになっていると嬉しいです。

また、上記のサンプルコードにおいてはnumberListListは1度に定義されていますが、実際には毎秒ごとに取得されるデータ群のようなものです。そのため、numberListListに一括で処理を行うようなことはできません。

1
  • Pythonだと上手く高速化するのは困難そうですが、メモリを直接操作できる言語なら大幅に高速化できそうです。
    – PicoSushi
    Commented 2021年10月18日 4:19

2 件の回答 2

1

計算量そのものは、次の計算量を超えないように思います。

  • 係数✕データ数✕各データの要素数(質問の例では3)

他方の回答のアイデアは計算量が次のようになり、技術的に可能なら良い方法です。

  • 係数✕データ数✕各データの要素数(質問の例では3)÷並列実行数

私自身は係数を多少小さくするアイデアに過ぎないのですが、

sort_method = [3,-1,2]

これを次のように変更することを提案します。

sort_order = [2,0,1]
sign_order = [1,-1,1]

こうすればabs関数とif文をなくせます。

留意点

  • アセンブラで書くことが前提なら期待できますが、インタプリタ型言語で書くなら誤差程度の効果しか期待できないと思います。
1

timeit で実行時間を計測してみました。

対象となる「3つの数字のリスト」の要素数(N)は 10000 で、ランダムに生成しています。最初は質問文に記載されているコード(for loop)、2番目はリスト内包表記、3番目は numpy で処理しています。

このサンプルコードはPythonで記述しましたが、本番環境ではPython以外の言語で記述するつもりなので、なるべく他言語でも使用できるようなアルゴリズムになっていると嬉しいです。

この場合、並列処理によって高速化が期待できるかと思いますので、プログラミング言語におけるアルゴリズムよりは GPGPU や SIMD などの利用を検討してみてはどうでしょうか。

def sort_by_index_for_loop(lst, idx):
  numberListList_new = []
  for numberList in lst:
    numberList_new = []
    for method in idx:
      number = numberList[abs(method)-1]
      if method < 0:
        number = -number
      numberList_new.append(number)
    numberListList_new.append(numberList_new)

  return numberListList_new

if __name__ == '__main__':
  import random
  import timeit
  import numpy as np

  N = 10000
  lst = [random.sample(range(10000), 3) for _ in range(N)]
  idx = [3, -1, 2]

  # for loop
  print('  for loop: ', timeit.timeit(
    'sort_by_index_for_loop(lst, idx)',
    number=1000, globals=globals()))

  # list comprehension
  print('list comp.: ', timeit.timeit(
    '[[_sign[i]*l[i] for i in _idx] for l in lst]',
    number=1000, globals=globals(), setup='''
_idx = [(abs(i)-1, abs(i)//i) for i in idx]
_sign = [i[1] for i in sorted(_idx, key=lambda x: x[0])]
_idx = [i[0] for i in _idx]
'''))

  # numpy  
  print('     numpy: ', timeit.timeit(
    '_lst[:, _idx] * _sign',
    number=1000, globals=globals(), setup='''
_lst = np.array(lst); _idx = np.array(idx)
_sign = np.sign(_idx); _idx = np.abs(_idx) - 1
'''))

# 実行結果(seconds)

  for loop:  4.9517041851067916
list comp.:  4.119111523032188
     numpy:  0.14930586703121662

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

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