83176


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

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

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

[code]

    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)
    
[/code]

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

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

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

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

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


CC BY-SA 4.0
2021-10-18T02:53:38.647
83152
2021-10-20T03:09:54.877
34471
question
python アルゴリズム
3つの数字を特定の規則で効率よく並び替えたい


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

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

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

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

[code]

    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
    
[/code]


CC BY-SA 4.0
2021-10-18T12:06:54.090
83162
2021-10-18T12:34:17.673
2021-10-18T12:34:17.673
47127
47127
83152
answer


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

  * 係数✕データ数✕各データの要素数（質問の例では3）

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

  * 係数✕データ数✕各データの要素数（質問の例では3）÷並列実行数

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

[code]

    sort_method = [3,-1,2]
    
[/code]

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

[code]

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

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

留意点

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


CC BY-SA 4.0
2021-10-19T18:50:38.653
83176
2021-10-20T03:09:54.877
2021-10-20T03:09:54.877
48452
48452
83152
answer