Как мне представить разреженные массивы в Pari / GP? - PullRequest
Новая
       25

Как мне представить разреженные массивы в Pari / GP?

0 голосов
/ 06 мая 2018

У меня есть функция, которая возвращает целочисленные значения для целочисленного ввода. Выходные значения относительно редки; функция возвращает только около 2 ^ 14 уникальных выходов для входных значений 1 .... 2 ^ 16. Я хочу создать набор данных, который позволит мне быстро найти входные данные, которые дают любой заданный вывод.

В настоящее время я храню свой набор данных в карте списков, где каждое выходное значение служит ключом для списка входных значений. Это кажется медленным и, кажется, использует все пространство стека. Есть ли более эффективный способ создания / хранения / доступа к моему набору данных?

Добавлено: Оказывается, время, затраченное моей функцией 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
}

Ответы [ 2 ]

0 голосов
/ 08 мая 2018

В некоторой степени поведение, которое вы видите, следует ожидать. PARI передает списки и карты по значению, а не по ссылке, за исключением специальных встроенных функций для управления ими. Это можно увидеть, создав функцию-оболочку, например mylistput(list,item)=listput(list,item);. Когда вы попытаетесь использовать эту функцию, вы обнаружите, что она не работает, потому что она работает с копией списка. Возможно, это ошибка в PARI, но, возможно, у них есть свои причины. Результатом этого поведения является то, что каждый раз, когда вы добавляете элемент в один из списков, хранящихся на карте, весь список копируется, возможно, дважды.

Ниже приведено решение, позволяющее избежать этой проблемы. 

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(...), но вы, вероятно, захотите матрицу для обработки, поскольку на карте нет встроенной функции получить список ключей.

Я немного переработал вышесказанное, чтобы попытаться сделать что-то более похожее на GroupBy в C #. (функция, которая может быть полезна для многих вещей) 

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).

0 голосов
/ 07 мая 2018

Используйте методы mapput, mapget и mapisdefined на карте, созданной с помощью Map(). Если требуется несколько измерений, используйте полиномиальный или векторный ключ.

Полагаю, это то, что вы уже делаете, и я не уверен, что есть лучший способ. У вас есть код? Исходя из личного опыта, значения 2 ^ 16 с ключами 2 ^ 14 не должны вызывать проблем со скоростью или памятью - в вашей реализации может происходить ненужное копирование.

...