1

整数値を整数入力に返す関数があります。出力値は比較的まばらです。この関数は、入力値 1....2^16 に対して約 2^14 の一意の出力のみを返します。特定の出力を生成する入力をすばやく見つけることができるデータセットを作成したいと考えています。

現在、データセットをリストのマップに保存しており、各出力値が入力値のリストのキーとして機能しています。これは遅いようで、スタック スペース全体を使用しているように見えます。データセットを作成/保存/アクセスするより効率的な方法はありますか?

追加: 私の sparesearray() 関数にかかる時間は、入力値 (リストに格納された値) に対する出力値 (つまりキー) の比率によって大きく異なることがわかりました。以下は、多数のリストを必要とし、それぞれに少数の値しかない関数にかかった時間です。

? sparsearray(2^16,x->x\7);
time = 126 ms.

それぞれが多くの値を持ついくつかのリストのみを必要とする関数にかかる時間は次のとおりです。

? sparsearray(2^12,x->x%7);
time = 218 ms.
? sparsearray(2^13,x->x%7);
time = 892 ms.
? sparsearray(2^14,x->x%7);
time = 3,609 ms.

ご覧のとおり、時間は指数関数的に増加します。

これが私のコードです：

\\ sparsearray takes two arguments, an integer "n"  and a closure "myfun", 
\\ and returns a Map() in which each key a number, and each key is associated 
\\ with a List() of the input numbers for which the closure produces that output. 
\\ E.g.:
\\ ? sparsearray(10,x->x%3)
\\ %1 = Map([0, List([3, 6, 9]); 1, List([1, 4, 7, 10]); 2, List([2, 5, 8])])
sparsearray(n,myfun=(x)->x)=
{
    my(m=Map(),output,oldvalue=List());
    for(loop=1,n,
        output=myfun(loop);                      
        if(!mapisdefined(m,output), 
        /* then */
            oldvalue=List(),
        /* else */    
            oldvalue=mapget(m,output));
        listput(oldvalue,loop);
        mapput(m,output,oldvalue));
    m
}
4

3 に答える 3

1

参照による引数の受け渡しは GP のメモリ モデルで制限される必要があるため、ガベージ コレクションが発生する方法のため、適切なネイティブ GP ソリューションはありません (バージョン 2.13 以降、~修飾子を使用する関数引数ではサポートされますが、マップ コンポーネントではサポートされません)。

これは、ベクトル内の同一オブジェクトの等価クラスを返すlibpari関数を使用したソリューションです。vec_equiv()

install(vec_equiv,G);
sparsearray(n, f=x->x)=
{
  my(v = vector(n, x, f(x)), e  = vec_equiv(v));
  [vector(#e, i, v[e[i][1]]), e];
}

? sparsearray(10, x->x%3)
%1 = [[0, 1, 2], [Vecsmall([3, 6, 9]), Vecsmall([1, 4, 7, 10]), Vecsmall([2, 5, 8])]]

（与えられた3つのインデックスセットに対応する3つの値があります）

動作は予想どおり線形です

 ? sparsearray(2^20,x->x%7);
 time = 307 ms.
 ? sparsearray(2^21,x->x%7);
 time = 670 ms.
 ? sparsearray(2^22,x->x%7);
 time = 1,353 ms.
于 2021-08-24T10:55:38.727 に答える
1

表示されている動作は、ある程度想定されたものです。PARI は、リストとマップを操作するための特別な組み込み関数を除いて、参照ではなく値で渡すように見えます。これは、 のようなラッパー関数を作成することで確認できますmylistput(list,item)=listput(list,item);。この関数を使用しようとすると、リストのコピーを操作しているため、機能しないことがわかります。おそらく、これは PARI のバグですが、おそらく理由があります。この動作の結果として、マップに格納されているリストの 1 つに要素を追加するたびに、リスト全体が (おそらく 2 回) コピーされます。

以下は、この問題を回避する解決策です。

sparsearray(n,myfun=(x)->x)=
{
   my(vi=vector(n, i, i)); \\ input values
   my(vo=vector(n, i, myfun(vi[i]))); \\ output values
   my(perm=vecsort(vo,,1)); \\ obtain order of output values as a permutation
   my(list=List(), bucket=List(), key);
   for(loop=1, #perm, 
      if(loop==1||vo[perm[loop]]<>key, 
          if(#bucket, listput(list,[key,Vec(bucket)]);bucket=List()); key=vo[perm[loop]]);
      listput(bucket,vi[perm[loop]])
   );

   if(#bucket, listput(list,[key,Vec(bucket)])); 
   Mat(Col(list))
}

出力は、マップと同じ形式のマトリックスです。マップが必要な場合は、 で変換できますがMap(...)、マップにはキーのリストを取得する組み込み関数がないため、おそらく処理用のマトリックスが必要です。 .

上記を少し手直しして、C# の GroupBy に似たものを作成しようとしました。（多くのことに役立つ機能）

VecGroupBy(v, f)={
   my(g=vector(#v, i, f(v[i]))); \\ groups
   my(perm=vecsort(g,,1)); 
   my(list=List(), bucket=List(), key);
   for(loop=1, #perm, 
      if(loop==1||g[perm[loop]]<>key, 
          if(#bucket, listput(list,[key,Vec(bucket)]);bucket=List()); key=g[perm[loop]]);
      listput(bucket, v[perm[loop]])
   );
   if(#bucket, listput(list,[key,Vec(bucket)])); 
   Mat(Col(list))
}

のように使用しますVecGroupBy([1..300],i->i%7)。

于 2018-05-08T17:57:08.267 に答える