Jump to content
sh4rk23

Um algoritmo um pouco lento a realizar cálculos, é normal?

Recommended Posts

sh4rk23

Boas pessoal...

É o seguinte, implementei uma classe que importa cria uma matriz, a partir de uma base de dados. A matriz é composta por utilizadores, filmes e classificações que cada  utilizador atribui a um filme. A minha questão é que desenvolvi um algoritmo que determine, através da similaridade do cosseno, a semelhança entre perfis de utilizadores. O meu problema é que para a matriz usada com cerca de 2000 utilizadores e 10000 filmes demora uma eternidade a realizar o cálculo para cada utilizador. Modifiquei o algoritmo e implementei inclusive com threads, mas mesmo assim continua bastante lento. É normal ser tão lento, mesmo tendo de fazer cálculos para os 2000 utilizadores?  🤔

Share this post


Link to post
Share on other sites
KTachyon

Sem ver o algoritmo torna-se complicado dizer porque é tão lento.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
brunoais

Outra coisa:

Se usares valores mais objetivos também ajudaria muito mais. Dizeres q demora muito tempo "eternidade" não é algo que eu saiba definir para avaliar


"[Os jovens da actual geração]não lêem porque não envolve um telecomando que dê para mirar e atirar, não falam porque a trapalhice é rainha e o calão é rei" autor: thoga31

Life is a genetically transmitted disease, induced by sex, with death rate of 100%.

Share this post


Link to post
Share on other sites
sh4rk23

Outra coisa:

Se usares valores mais objetivos também ajudaria muito mais. Dizeres q demora muito tempo "eternidade" não é algo que eu saiba definir para avaliar

Pensando bem tens alguma razão.  😳

Por exemplo para todos os registos, ou seja, a matriz correspondente a todos os itens (+-10000) e utilizadores (+-2000) pus a simular os respectivos cálculos e fiquei à espera cerca de 40 minutos e nada.  😲 E isto apenas para um utilizador.  :nono1:

Posteriormente reduzia a matriz no número de utilizadores para 1000  e mantendo os 10000 itens, fazendo os cálculos para um utilizador demorou 6 minutos.

Eu percebo que demore algum tempo para a realização de cálculos, mas 6 minutos apenas para um utilizador, não sei se será muito normal. É mais neste sentido a minha questão. Qual a vossa opinião?

Eu apenas não coloquei o código por estar algo desorganizado e poder ser de difícil entendimento, mas se acharem necessário posto. Contudo o código não consiste em muito mais que um conjunto de for's que calcula a similaridade dos vectores entre cada linha da matriz.

Cumps  :)

Share this post


Link to post
Share on other sites
pedrosorio

Que cálculo é que estás a realizar exactamente? Determinar e devolver a similaridade de um utilizador com todos os outros?

Dado que a similaridade entre dois vectores é dada pelo seu produto interno a dividir pelo produto das suas normas, seria interessante guardar a norma do vector de cada utilizador (i.e. cada vez que actualizares os dados de um utilizador, calcula a norma do seu vector e guarda-a). Desta forma podes ficar com um vector que contém as normas de cada um dos utilizadores.

A partir daí, calcular a similaridade de um utilizador com outro exige 10000 multiplicações e 9999 somas (produto interno), mais uma multiplicação de normas e divisão.

Se estiveres a fazer o que eu penso (calcular a norma dos utilizadores sempre que achas a similaridade), dado que o cálculo da norma requer 10000 multiplicações, 9999 somas e uma raíz quadrada, e tens que fazer duas destas, o tempo deve reduzir-se para menos de 1/3 do actual, o que ainda é lento. Usa C :)

P.S.: De qualquer forma é esquisito. ~60.000 operações * 1000 utilizadores não devia correr em 6 minutos. Pode até ser que a raíz quadrada seja muito lenta. Experimenta fazer o que disse e dá feedback.


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
mjamado

Edit: o que ele ^^ disse...  :)

O que é que estás a fazer?

Imagino que a tua matriz tenha os filmes num eixo e os utilizadores noutro, certo? Logo, ao comparar dois utilizadores, é a pontuação dada a cada um dos 10.000 filmes que constitui o vector de cada um deles.

Como tal, para calcular a similitude, o pseudo-código será qualquer coisa deste estilo:

Seja matriz = [utilizadores, filmes];
Seja user1 = indice do utilizador 1;
Seja user2 = indice do utilizador 2;

Seja squ1, squ2, sp = 0; // somatorios dos quadrados e somatório do produto

Para cada index em (eixo dos filmes em matriz)
    squ1 = matriz[user1, index] ^ 2;
    squ2 = matriz[user2, index] ^ 2;
    sp = matriz[user1, index] * matriz[user2, index]

Seja similitude = sp / (sqrt(squ1) * sqrt(squ2));

Ora, mesmo para 10.000 filmes, isto é suposto calcular de calcanhar... Por isso, deves ter aí um gatito qualquer. Coloca aí o código relevante, equivalente a este pseudo-código.


"Para desenhar um website, não tenho que saber distinguir server-side de client-side" - um membro do fórum que se auto-intitula webdesigner. Temo pelo futuro da web.

Share this post


Link to post
Share on other sites
sh4rk23

Possivelmente a causa da lentidão deverá ser a forma como calculo a similaridade do cosseno entre os utilizadores. Este calculo tem que ser realizado da seguinte forma: similaridade do utilizador 1 com o user 2, similaridade do user 1 com o user 3 e assim sucessivamente para os 2000 users calculando a similaridade 2000 vezes. O sistema determina quais os utilizadores mais semelhantes ao utilizador 1 (p.e) e calcula a avaliação que o utilizador 1 daria ao item que ele ainda nao viu.

Ou seja, dos 10000 itens o sistema para cada item que o utilizador não viu, calcula 2000 similaridades para determinar os utilizadores com classificações de filmes mais semelhantes a si e calcula a classificação que o utilizador daria ao item não visto com base na avaliação dos dois utilizadores mais proximos. Logo no pior caso seriam 2000*10000=20000000 de cálculos.

Share this post


Link to post
Share on other sites
pedrosorio

Pois. Não só estás a calcular a norma dos vectores de cada vez que calculas a similaridade, como para cada item que o utilizador não viu estás a calcular a similaridade entre ele e todos os que viram esse item, ou seja -> explosão de tempo de execução.

Para melhorar em muito o tempo de execução:

Primeiro -> Calcular normas de todos os utilizadores

Segundo -> Calcular similaridade entre o utilizador e todos os outros

Terceiro -> Fazer sort deste vector de similaridades

Quarto -> Para cada item que o utilizador não viu, percorrer o vector de similaridades até encontrar os dois utilizadores com maior similaridade que viram o item e calcular a predição

Os passos 1-3 podem ser realizados apenas quando um utilizador altera as suas classificações, ou em alternativa (talvez melhor) num período de pouca actividade, realizar os passos 1-3 para todos os utilizadores (o tempo de execução deve ser O(N^2 / 2) já que a similaridade é simétrica - basta calcular similaridade(1,2) para saber similaridade(2,1)) . Desta forma, o quarto passo é o único que precisa de ser realizado se for necessário fazer predições e é praticamente instantâneo.


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
sh4rk23

Pois. Não só estás a calcular a norma dos vectores de cada vez que calculas a similaridade, como para cada item que o utilizador não viu estás a calcular a similaridade entre ele e todos os que viram esse item, ou seja -> explosão de tempo de execução.

Para melhorar em muito o tempo de execução:

Primeiro -> Calcular normas de todos os utilizadores

Segundo -> Calcular similaridade entre o utilizador e todos os outros

Terceiro -> Fazer sort deste vector de similaridades

Quarto -> Para cada item que o utilizador não viu, percorrer o vector de similaridades até encontrar os dois utilizadores com maior similaridade que viram o item e calcular a predição

Os passos 1-3 podem ser realizados apenas quando um utilizador altera as suas classificações, ou em alternativa (talvez melhor) num período de pouca actividade, realizar os passos 1-3 para todos os utilizadores (o tempo de execução deve ser O(N^2 / 2) já que a similaridade é simétrica - basta calcular similaridade(1,2) para saber similaridade(2,1)) . Desta forma, o quarto passo é o único que precisa de ser realizado se for necessário fazer predições e é praticamente instantâneo.

Boas sugestões. Vou tentar implementar, penso que me irá ajudar, principalmente se não tiver sempre que calcular as 2000 similaridades para cada item.

:)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.