Como impedir a criação de objetos intermediários em cascata operadores?
https://stackoverflow.com/questions/114859
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu uso uma classe Matrix costume na minha candidatura, e eu frequentemente adicionar várias matrizes:
Matrix result = a + b + c + d; // a, b, c and d are also Matrices
No entanto, isto cria uma matriz intermédia para cada operação de adição. Desde que esta é uma adição simples, é possível evitar os objetos intermediários e criar o resultado, adicionando os elementos de todos os 4 matrizes de uma só vez. Como posso fazer isso?
NOTA:. Sei que posso definir várias funções como Add3Matrices(a, b, c), Add4Matrices(a, b, c, d), etc. mas eu quero manter a elegância do result = a + b + c + d
Solução
Você poderia limitar-se a uma única pequena intermediária usando avaliação preguiçosa. Algo como
public class LazyMatrix
{
public static implicit operator Matrix(LazyMatrix l)
{
Matrix m = new Matrix();
foreach (Matrix x in l.Pending)
{
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
m.Contents[i, j] += x.Contents[i, j];
}
return m;
}
public List<Matrix> Pending = new List<Matrix>();
}
public class Matrix
{
public int[,] Contents = { { 0, 0 }, { 0, 0 } };
public static LazyMatrix operator+(Matrix a, Matrix b)
{
LazyMatrix l = new LazyMatrix();
l.Pending.Add(a);
l.Pending.Add(b);
return l;
}
public static LazyMatrix operator+(Matrix a, LazyMatrix b)
{
b.Pending.Add(a);
return b;
}
}
class Program
{
static void Main(string[] args)
{
Matrix a = new Matrix();
Matrix b = new Matrix();
Matrix c = new Matrix();
Matrix d = new Matrix();
a.Contents[0, 0] = 1;
b.Contents[1, 0] = 4;
c.Contents[0, 1] = 9;
d.Contents[1, 1] = 16;
Matrix m = a + b + c + d;
for (int i = 0; i < 2; ++i)
{
for (int j = 0; j < 2; ++j)
{
System.Console.Write(m.Contents[i, j]);
System.Console.Write(" ");
}
System.Console.WriteLine();
}
System.Console.ReadLine();
}
}
Outras dicas
Algo que, pelo menos, evitar a dor de
Matrix Add3Matrices(a,b,c) //and so on
seria
Matrix AddMatrices(Matrix[] matrices)
Em C ++, é possível usar Template Metaprogramas e também aqui , usando modelos para fazer exatamente isso. No entanto, a programação modelo é não-trivial. Eu não sei se uma técnica similar está disponível em C #, muito possivelmente não.
Esta técnica, em c ++ faz exatamente o que você quer. A desvantagem é que, se algo não está certo, então as mensagens de erro do compilador tendem a correr para várias páginas e são quase impossíveis de decifrar.
Sem essas técnicas eu suspeito que você está limitado a funções como Add3Matrices.
Mas para C # esta ligação pode ser exatamente o que você precisa: Programação Matrix eficiente em C # embora pareça trabalho ligeiramente diferente para expressões de modelo C ++.
Você não pode evitar a criação de objetos intermediários.
No entanto, você pode usar modelos de expressão como descrito aqui para minimizá-los e fazer fantasia avaliação preguiçosa dos modelos.
No nível mais simples, o modelo de expressão pode ser um objeto que armazena referências a várias matrizes e chama uma função apropriada como Add3Matrices () mediante a cessão. No nível mais avançado, os modelos de expressão vai fazer coisas como calcular a quantidade mínima de informações de uma forma preguiçosa mediante solicitação.
Esta não é a solução mais limpa, mas se você souber a ordem de avaliação, você poderia fazer algo parecido com isto:
result = MatrixAdditionCollector() << a + b + c + d
(ou a mesma coisa com nomes diferentes). O MatrixCollector então implementos + como + =, isto é, começa com um 0-matriz de tamanho indefinido, leva um tamanho uma vez que o primeiro + é avaliada e adiciona tudo em conjunto (ou, cópias da primeira matriz). Isso reduz a quantidade de objetos intermediários como 1 (ou mesmo 0, se você implementar a atribuição em um bom caminho, porque o MatrixCollector pode ser / conter o resultado imediatamente.)
Eu não sou inteiramente certo se este é feia como o diabo ou um dos hacks mais agradáveis ??que se poderia fazer. Uma certa vantagem é que ele é meio óbvio que está acontecendo.
Posso sugerir um MatrixAdder que se comporta como um StringBuilder. Você adiciona matrizes ao MatrixAdder e, em seguida, chamar um método ToMatrix () que faria as adições para você em uma implementação preguiçoso. Isso que você obtenha o resultado desejado, pode ser expansível para qualquer tipo de LazyEvaluation, mas também não introduzir quaisquer implementações inteligentes que poderia confundir outros mantenedores do código.
Eu pensei que você poderia apenas fazer o comportamento add-in-place desejado explícito:
Matrix result = a;
result += b;
result += c;
result += d;
Mas, como apontado por Doug nos comentários sobre este post, este código é tratado pelo compilador como se eu tivesse escrito:
Matrix result = a;
result = result + b;
result = result + c;
result = result + d;
para temporários ainda são criados.
Eu tinha acabado de apagar esta resposta, mas parece que outros podem ter o mesmo equívoco, por isso considero este um contra-exemplo.
Bjarne Stroustrup tem um curto papel chamado Abstração, bibliotecas e eficiência em C ++ , onde ele menciona técnicas usadas para conseguir o que você está procurando. Especificamente, ele menciona a biblioteca Blitz ++ , uma biblioteca para cálculos científicos que também tem operações eficientes para matrizes, juntamente com algumas outras bibliotecas interessantes. Além disso, eu recomendo a leitura uma conversa com Bjarne Stroustrup no artima.com sobre esse assunto.
Não é possível, usando operadores.
Minha primeira solução seria algo ao longo destas linhas (para adicionar na classe Matrix se possível):
static Matrix AddMatrices(Matrix[] lMatrices) // or List<Matrix> lMatrices
{
// Check consistency of matrices
Matrix m = new Matrix(n, p);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
foreach (Maxtrix mat in lMatrices)
m[i, j] += mat[i, j];
return m;
}
Eu tinha na classe Matrix, porque você pode contar com os métodos privados e propriedades que poderiam ser úteis para a sua função no caso da implementação da mudança da matriz (lista ligada de nós não vazias em vez de uma grande variedade de casal , por exemplo).
Claro, você iria perder a elegância de result = a + b + c + d. Mas você teria algo ao longo das linhas de result = Matrix.AddMatrices(new Matrix[] { a, b, c, d });.
Existem várias maneiras de implementar a avaliação lenta para conseguir isso. Mas é importante lembrar que nem sempre o seu compilador será capaz de obter o melhor código de todos eles.
Eu já fiz implementações que trabalharam muito bem em GCC e até mesmo superceeded o desempenho dos vários tradicional para código ilegível porque levam o compilador para observar que não houve aliases entre os segmentos de dados (somethign difícil de entender com matrizes vindo do nada ). Mas alguns dos que foram um completo fracasso em MSVC e vice-versa sobre outras implementações. Infelizmente essas são muito tempo para postar aqui (não acho que vários milhares de linhas de ajuste de código aqui).
Uma biblioteca muito complexo, com grande int conhecimentos incorporados ele área é biblioteca Blitz ++ para a computação científica.
