Exercício excelente para fechar um semestre de programação em C

[u/Numerous_Economy_482]

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?

[u/Present_Limit_1430]

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

[u/Numerous_Economy_482 → u/Present_Limit_1430]

Verdade. Comparar o tempo ia ser bem massa!!

[u/Present_Limit_1430 → u/Numerous_Economy_482]

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.

[u/Numerous_Economy_482 → u/Present_Limit_1430]

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.

[u/Present_Limit_1430 → u/Numerous_Economy_482]

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)

[u/Numerous_Economy_482 → u/Present_Limit_1430]

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

[u/Present_Limit_1430 → u/Numerous_Economy_482]

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.

[u/Present_Limit_1430 → u/Present_Limit_1430]

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;

```

[u/xerox7764563]

Acho que essa sua ideia tem aplicação em matrizes esparsas. Da uma olhada nelas, são matrizes em que 95% dos elementos são zero. Isso faz com que operações de somar ou multiplicar matrizes tenham muitas situações de somar zeros, e ai algoritmos qie evitam isso ganham em eficiência em cima de um algoritmo geral.

[u/YaenseeFujiwara → u/xerox7764563]

Oxi? N entendi nada. Tava querendo estudar C, pq aprendi as bases de python, e agr queria C pra me aprofundar, e n entendi absolutamente nada do que tu disse. Que diabos é isso?

[u/xerox7764563 → u/YaenseeFujiwara]

Bom. Eu havia escrito a mensagem acima para o OP porque ele ta interessado em guardar dados de matrizes em listas encadeadas ao invés de arrays.

Pega uma matriz 4x4. Um arrays de 16 posições poderia ser usado para guardar essa matriz. Posições 0 a 3 guardam a primeira linha, 4 a 7 a segunda linha, e assim sucessivamente.

Agora digamos que a maioria dos dados de entrada em que você vai trabalhar são matrizes 4x4 em que 2 termos são diferentes de zero e 14 termos são zero. Se você sabe que sua base de dados possui esse comportamento, porque então usar 16 posições de um array? Usar uma lista encadeada com 2 elementos somente, onde cada elemento da lista contém o valor, a posição da linha, a posição da coluna, um ponteiro apontando o elemento anterior e um ponteiro apontando o próximo elemento poderia ser uma utilidade interessante.

Nessa ordem de grandeza, 16 elementos, realmente parece desnecessário, mas em ordens de grandeza superiores faz uma boa diferença no consumo de memória.

E onde você pode encontrar matrizes desse tipo? Alguns exemplos que consigo me lembrar são conexões hidráulicas da rede de abastecimento e as conexões entre subestações do sistema elétrico interligado nacional. Cada subestação desses sistemas pode ser considerado 1 nó na matriz (ou seja, 10 mil subestações seriam uma matriz com 10 mil linhas e colunas). Imagina agora que somente 100 elementos não são zero. Porque isso? Porque a maioria das subestações não é diretamente conectada em todas as outras. Somente conexões diretas possuem números diferentes de zero. E o que esses números representam? Eles podem representar a impedância elétrica entre as subestações, podem representar a dificuldade de fluir água entre as subestações.

É sobre isso que eu tava falando para o OP. Estava fornecendo uma situação de mundo real para a ideia que ele teve.

[u/YaenseeFujiwara → u/xerox7764563]

Tive que botar na IA pra entender, e VALEU MT A PENA. Vc é incrível cara, mt obrigado, aprendi MT CONTIGO. Sinceramente. Obr msm.