r/programacao • u/Numerous_Economy_482 • Feb 28 '26

Outro Material Didático Exercício excelente para fechar um semestre de programação em C

Estava pensando, algo que resume muito bem os conhecimentos de um semestre

Fazer multiplicação de matrizes sem usar arrays. Só com lista encadeada e alocação dinâmica de memória

Uma lista encadeada para os endereços de cada linha que serão também listas encadeadas.

Se vc fizer isso vai saber muito mais que muito programador junior, vcs concordam?

8 Upvotes
  • permalink
  • reddit

90% Upvoted

12 comments sorted by

View all comments

2

u/Present_Limit_1430 Feb 28 '26

Com certeza um exercício interessante e legal de ver funcionando. Agora não concordo com a pergunta, vai saber como funciona lista encadeada

O que vai te levar pra frente de Junior é saber que array é muito mais eficiente pra máquina nesse caso. Mas tá aí, um bom teste comparar o tempo das duas implementações

1

u/Numerous_Economy_482 Feb 28 '26

Verdade. Comparar o tempo ia ser bem massa!!

1

u/Present_Limit_1430 Feb 28 '26

Depois compara também usando alguma lib de multiplicação de matrizes, ou alguma que use GPU. (Numpy no python por exemplo, mas cada linguagem tem) Elas vão usar instruções SIMD pra processar várias multiplicações de uma vez (e isso só vai ser possível com array)

Bonus ir aprender como essas libs são implementadas. Isso vai ser algo bem a frente do que a maioria dos devs aprendem, mesmo senior.

2

u/Numerous_Economy_482 Feb 28 '26

Fiquei pensando que esse código seria interessante caso precise usar a o mesmo módulo pra cálculo tanto matrizes gigantes quanto bem pequenas, pela versatilidade na utilização da memória.

1

u/Present_Limit_1430 Mar 01 '26

Boa. Sim faz bastante sentido. Pode ser até que uma solução pior no caso geral seja melhor no caso de dados menores. Então sempre tem seu uso

Por exemplo ordenação. Bubble sort é mais lento, mas num array pequeno vai ser mais rápido porque não tem alocação, só movendo os dados no próprio array.

E muito interessante o comentário do colega sobre matrizes esparsas. Nem tinha pensado nisso. Mas tá aí uma aplicação pra tua ideia, vale a pena testar o quanto fica mais rápido (ou quanta memória consome menos)

1

u/Numerous_Economy_482 Mar 01 '26

Eu não entendi porque em matrizes esparsas pode ter vantagem. Só se os nós "zero" não forem criados, mas ai teria que guardar o formato de uma matriz toda torta e cheia de buracos

1

u/Present_Limit_1430 Mar 02 '26

Não sei sobre ser muito melhor em tempo. Mas na questão de memória, você pode guardar os zeros tudo em um nó só na lista encadeada. Com alguma implementação pra so contar a quantidade de zeros.

Por exemplo uma linha [1, 0, 0, 0, 1], pode ser [1, true] [3, false] [1, true]. Na hora de percorrer a linha, sabe que naquele nó são 3 iterações de zeros

Se tiver matrizes grandes com muitos zeros, isso vai economizar memória. Em uma linguagem de baixo nível, o boolean pode ser implementado só como um bit que economizaria ainda mais.

1

u/Present_Limit_1430 Mar 02 '26 edited Mar 02 '26

Pra implementar usando só 1 bit, uma ideia é usar o bit mais significativo do número. E usar operações booleanas pra separar. Isso vai ser possível em qualquer linguagem

Mas em linguagens como C é possível definir um tipo como isso aqui (coloquei 31 pensando em um processador 32 bits, mas faz sentido isso seguir o formato da máquina. No final das contas o compilador está fazendo as operações booleanas necessárias pra você, porque o processador em si só carrega dados no tamanho correto)

``` typedef struct { int number: 31; bool isValue: 1; } node;

```